CODEWITHSUNDEEP
algorithmrandomsimulated-annealing
Rayan Aradha
Rayan Aradha

Reputation: 510

What is the purpose of comparing with a random value in [0, 1] in this simulated annealing algorithm?

In the simulated annealing algorithm at the line number 13 (IF random([0,1]) ≤ accept THEN), why do we need to generate a random number to compare with the evolution value with next node? What is the purpose of generating a random number every time without using constant value to compare?

1: INITIALIZE startTemperature, endTemperature, maxNumberIterations
2: coolingRate = eˆ(log(endTemperature/startTemperature)/maxNumberIterations)
3: INITIALIZE dataStructures
4: COMPUTE initialSolution
5: INITIALIZE currentSolution, bestSolution, currentObjective, bestObjective
6: currentTemperature = startTemperature ∗ initialObjective
7: globalIteration = 0
8: WHILE currentTemperature > endTemperature ∗ initialObjective DO
9: currentTemperature = currentTemperature ∗ coolingRate
10:EXECUTE randomMove(movesWeight, currentSolution)
11:tentativeObjective = currentObjective + moveCost
12:accept = eˆ(currentObjective − tentativeObjective)/currentTemperature)
13:IF random([0,1]) ≤ accept THEN
14:currentSolution = tentativeSolution
15:IF tentativeObjective < bestObjective THEN
16:bestSolution = tentativeSolution
17:END IF
18:END IF
19:globalIteration = globalIteration +1
20: END WHILE
21: PRINT bestSolution, bestObjective

Upvotes: 0

Views: 153

Answers (1)

mkrieger1
mkrieger1

Reputation: 23139

The purpose is to execute the following code only with a given probability of accept.

If accept is 0.3 for instance, a random number between 0 and 1 will be less than or equal to this value only in 30% of all possible cases.

A new random number needs to be drawn in every iteration of the algorithm, otherwise the following code would be executed either always or never, for a given run of the algorithm.

Upvotes: 2

Related Questions