CODEWITHSUNDEEP
heuristicssimulated-annealing
mohammad khamechian
mohammad khamechian

Reputation: 31

How to get out of local optimum using simulated annealing?

I have a conceptual question. I am working on an optimization project in which I used a simulated annealing metaheuristic to get better solutions. for creating neighbors in SA I have used both SWAP and 2-OPT methods to create neighbors by creating a new sequence. results even for small problem sizes show that 7 out of 10 times when I run the program (with more than 500 iterations) the best objective value achieved is the initial objective value which has been achieved heuristically. question is what could cause such behavior?

is there something else that I am missing?

Upvotes: 0

Views: 305

Answers (1)

Willem Hendriks
Willem Hendriks

Reputation: 1487

You need to keep track of the percentage, accepted solutions. For instance, every 100 proposals, print the number of accepted solutions.

  • Start with a random solution, not close to optimal one.

  • In early phase, >80% should be accepted. If this is not the case, increase the temperature until so.

  • In last phase, <10% should be accepted, if this is not the case, lower the stop temperature.

  • Cooling scheme has only small influence on solution quality, just lower by cooling factor is good enough, between 0.99 and 0.8. (You can repeat N times on each temperature to increase the proposals)

  • You can experiment with different proposals.

  • If you apply on traveling salesman, you can 2-opt your output of simulated annealing (SA). Most likely, your SA with a 2-opt to 'clean' the solution, is better than 2-opt without SA.

Hope this helps.

Upvotes: 0

Related Questions