Java Simulated Annealing Acceptance Probability

Question

I have a program implementing simulated annealing. I'm having a problem with the acceptance probability, probably due to my lack of understanding of why raising euler's number to the power of (energy - energy') is useful.

The probability is always over 1.0 (100%), even when the temperature is very low, making this effectively a random search. How do I fix my acceptance probability to a normal rate for sA (high chance of accepting a worse solution at the beginning, low chance towards the end)?

Here is the method code:

if (mutatedSolutionFitness > originalSolutionFitness) {
        return 1.0;
    } else {
        System.out.println("Original solution fitness: "+originalSolutionFitness);
        System.out.println("Mutated solution fitness: "+mutatedSolutionFitness);
        System.out.println("Temperature: "+this.temperature);
        final double chance = Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature);
        System.out.println("Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): "+chance);
        System.out.println();
        return chance;
    }

And here's the output a few times:

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.5555555555555556
Temperature: 999998.000001
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.0000001111113395

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.6666666666666666
Temperature: 999997.000003
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.0

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.6666666666666666
Temperature: 999996.000006
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.0

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.5555555555555556
Temperature: 999995.00001
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.0000001111116728

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.4444444444444444
Temperature: 999994.0000149999
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.0000002222235802

Original solution fitness: 0.6666666666666666
Mutated solution fitness: 0.5555555555555556
Temperature: 999993.0000209998
Math.exp((originalSolutionFitness - mutatedSolutionFitness) / this.temperature): 1.000000111111895

Answer 1

In your example output the probability will always >= 1 as it's usually set to 1 if the new solution is better than the current one.

Following the classic original formulation (equivalent to yours; besides the if-else behaviour) available @wiki (Kirkpatrick et al):

• P(e, e', T) =
  • 1 if e' < e (as outlined above)
  • exp(-(e' - e) / T otherwise
  • where:
    • e: current solution
    • e': new solution candidate
    • T: temperature

Some examples:

• T = 100000
  • current: 0.666, new: 0.555
    • 1 as e' < e
  • current: ```0.555, new: 0.666
    • ~0.99999889
• T = 10
  • current: 0.666, new: 0.555
    • 1 (T does not change that fact)
  • current: 0.555, new: 0.666
    • ~0.9889614

So it still will do a complete random-search accepting every candidate as long as each new candidate is better. That's a design-decision taken. But when the candidates get worse than the current solution, the acceptance-procedure matters.

For other approaches / designs, you should be able to find a lot of resources. Matlab seems to always accept better candidates too, but uses a different formula elsewise.