Combined Simulated Annealing and Genetic Algorithm to Solve Optimization Problems

Authors: Younis R. Elhaddad

Abstract:

Combinatorial optimization problems arise in many scientific and practical applications. Therefore many researchers try to find or improve different methods to solve these problems with high quality results and in less time. Genetic Algorithm (GA) and Simulated Annealing (SA) have been used to solve optimization problems. Both GA and SA search a solution space throughout a sequence of iterative states. However, there are also significant differences between them. The GA mechanism is parallel on a set of solutions and exchanges information using the crossover operation. SA works on a single solution at a time. In this work SA and GA are combined using new technique in order to overcome the disadvantages' of both algorithms.

Keywords: Genetic Algorithm, Optimization problems, Simulated Annealing, Traveling Salesman Problem

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1057697

References:

[1] An Introduction to Genetic Algorithms for Electromagnetics. Haupt, R.L. 2, s.l. : IEEE, April 1995, Vol. 37, pp. 7-15.
[2] Parallel simulated annealing and genetic algorithms: A space of hybrid methods. H Chen, N S Flann. s.l: International Conference on Evolutionary Computation the Third Conference Parallel Problem Solving, 1994. 866.
[3] Genetic algorithms and very fast simulated reannealing: A comparison. Rosen, L. Ingber and B. 11, s.l. : Mathematical Computer Modeling, 1992, Vol. 16. 87-100.
[4] Metropolis, N, et al. Equation of State Calculations by Fast Computing Machines. Florida State University. (Online) 1953. (Cited: 2 17, 2008.) www.csit.fsu.edu/~beerli/mcmc/metropolis-et-al-1953.pdf.
[5] W. Thomas. Global Optimization Algorithms Theory and Application. Thomas Weise. (Online) 2008. (Cited: 11 7, 2008.) http://www.itweise. de/projects/book.pdf.
[6] S. Kirkpatrick, C. D. Gelatt, Jr., M. P. Vecchi. Optimization by Simulated Annealing. Computer Engineering Research Group. (Online) May 13, 1983. (Cited: 8 13, 2007.) http://www.eecg.utoronto.ca/~janders/ece1387/readings/sim_anneal.pdf.
[7] Bradley, J and Lambert, C. Simulated Annealing Applications. University of Victoria . (Online) November 18, 1999. (Cited: 4 12, 2008.) http://www.me.uvic.ca/~zdong/courses/mech620/SA_App.PDF.
[8] Beasley, D, Bull, D R and Martin, R. An Overview of Genetic Algorithms :. Part 1, Fundamentals. Norwegian University of Science and Technology. (Online) 93. (Cited: 3 24, 2008.) http://www.idi.ntnu.no/emner/it3704/lectures/papers/Beasley93GA.pdf.
[9] Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Holland, J. s.l. : The University of Michigan Press, 1975.
[10] An Improved Genetic Algorithm to Solve the Traveling Salesman Problem. Sallabi, Omar M and Elhaddad, Younis R. Rome : World Academy of Science, Engineering and Technology, 2009. pp. 471-474. Issue 52.
[11] http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/. Heidelberg University. (Online) (Cited: 1 22, 2007.)