What kind of problems is simulated annealing better suited for compared to genetic algorithms?
From my experience, genetic algorithms seem to perform better than simulated annealing for most problems.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Could you clarify what you mean by "perform better" - e.g. does GA find the better solution, is it faster to run, does it use less memory, storage or CPU resources? Also name the problems you have tried SA vs GA on . . . $\endgroup$– Neil SlaterDec 12, 2018 at 9:35
-
$\begingroup$ See also this SO question: stackoverflow.com/q/4092774/3924118. $\endgroup$– nbroFeb 21, 2019 at 11:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Simulated Annealing vs genetic algorithm?
Simulated annealing is a materials science analogy and involves the introduction of noise to avoid search failure due to local minima. See images below. To improve the odds of finding the global minimum rather than a sub-optimal local one, a stochastic element is introduced by simulating Brownian (thermal) motion. Variants of simulated annealing include injection of random numbers with various distributions and the averaging effect of mini-batching (dividing a batch into segments and performing network parameter adjustment after each).
Genetic algorithms are search methods based on principles of mutation, meiosis, symbiosis, test, elimination of inadequacy, and recursion. The advantages of such approaches is the simulation of sexual reproduction, where the possibility of dominant genetic features from two individuals producing a child individual containing the best of both exists. In a population of children, the probability of such a hybrid emerging is higher. Over several generations, even higher than that.
What kind of problems does simulated annealing perform better than genetic algorithms if any?
This question can only be answered well if comparing original, pure versions of both, not the variants that have developed since their introduction.
Simulated annealing or other stochastic gradient descent methods usually work better with continuous function approximation requiring high accuracy, since pure genetic algorithms can only select one of two genes at any given position.
From my experience, genetic algorithm seems to perform better than simulated annealing for most problems.
Those performance results would be of value to others and should be published as a paper, presented as an open source project, or published creative commons in the appropriate AI venue. At the very minimum, the results could be placed in the above question or an answer to it.
References
[1] Optimization by Simulated Annealing, Science S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Science New Series, Vol. 220, No. 4598, May 1983, pp. 671-680
[2] N. Metropolis, A. Rosenbluth, M. Rosenbluth., A. Teller. E. Teller, J. Chem. Phys. 21. 1087 110511
Optimised simulated annealing for Ising spin glasses, 2015, S.V. Isakov et. al.
A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows, 2014, Chao Wang et. al.
Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem, 2015, Ruggero Bellio et. al.
Images from Other Answers
answered Jan 22, 2019 at 2:25
$\begingroup$
$\endgroup$
Simulated annealing algorithms are generally better at solving mazes, because they are less likely to get suck in a local minima because of their probabilistic "mutation" method. See here. Genetic algorithms are better at training neural networks, because of their genetically inspired training algorithm. This makes them more versatile and efficient in more complex situations.
