An Adaptive GA in Partitioned Search Space
Keywords:
Genetic Algorithms, Adaptive Parameter Control, Crossover Rate, Mutation RateAbstract
Evolutionary algorithms are population based meta-heuristics inspired from natural survival of fittest phenomena.
Despite their reasonable performance, these algorithms suffer from some weaknesses including the need for finding the values of their parameters that affect their performance.
A new algorithm is proposed that divide the search space into equal sized partitions.
Each partition is assigned with two parameters that determine the intensification and diversification rates.
The partitions will be intensified or diversified adaptively with regards to the corresponding parameters.
Traditional crossover and mutation operators are replaced with two new parameter-free operators.
The experiments conducted on a wide range of multi-modal and epistatic problems showed the superiority of the proposed method in comparison to other algorithms in literature.
References
Thomas Back and Martin Schutz. Intelligent mutation rate control in canonical genetic algorithms. In Foundations of Intelligent Systems, pages 158{167. Springer, 1996.
Shumeet Baluja. Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning. Science, CMU-CS-94-(CMUCS- 94-163):1{41, 1994.
Christian Blum and Andrea Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv., 35(3):268{308, 2003.
Felipe Houat de Brito, Artur Noura Teixeira, Otavio Noura Teixeira, and Roberto C. L. Oliveira. A fuzzy approach to control genetic algorithm parameters. SADIO Electronic Journal of Informatics and Operations Research, 1(1):12{23, 2007.
Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing, STOC '71, pages 151{158, New York, NY, USA, 1971. ACM.
W.A. de Landgraaf, A.E. Eiben, and V. Nannen. Parameter calibration using metaalgorithms. In Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, pages 71 {78, sept. 2007.
A.E. Eiben, M.C. Schut, and A.R. de Wilde. Boosting genetic algorithms with (self-) adaptive selection. In Proceedings of the IEEE Conference on Evolutionary Computation (CEC 2006), pages 1584{1589. IEEE, 2006. http://dx.doi.org/10.1109/CEC.2006.1688348
A.E. Eiben and J.E. Smith. Introduction to Evolutionary Computing. Natural Computing Series. Springer, 2 edition, 2007.
Gusz Eiben and Martijn C. Schut. New ways to calibrate evolutionary algorithms. In Patrick Siarry and Zbigniew Michalewicz, editors, Advances in Metaheuristics for Hard Optimization, Natural Computing Series, pages 153{177. Springer, 2008.
Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990.
J. Gu. Local search for satisability (sat) problem. Systems, Man and Cybernetics, IEEE Transactions on, 23(4):1108 {1129, July/August 1993.
G.R. Harik, F.G. Lobo, and D.E. Goldberg. The compact genetic algorithm. In Evolutionary Computation Proceedings, 1998. IEEE World Congress on Computational Intelligence., The 1998 IEEE International Conference on, pages 523 {528, 4-9 1998.
Kenneth A. De Jong. Evolutionary Computation. A Unied Approach. MIT Press, 2006.
Kenneth A. De Jong and William M. Spears. Using genetic algorithms to solve NP-complete problems. In J. David Schaer, editor, ICGA, pages 124{132. Morgan Kaufmann, 1989.
Kenneth A. De Jong and William M. Spears. A formal analysis of the role of multi-point crossover in genetic algorithms, 1992.
Ting Kuo and Shu-Yuen Hwang. Why dgas work well on ga-hard functions? New Gen. Comput., 14:459{479, October 1996.
Fernando G. Lobo and David E. Goldberg. The parameter-less genetic algorithm in practice. Information Sciences, 167(1-4):217{232, 2004.
Fernando Miguel Pais da Graa Lobo. The Parameter-Less Genetic Algorithm: Rational and Automated Parameter Selection for Simplied Genetic Algorithm Operation. PhD thesis, 2000.
M. Lozano and C. Garca-Martnez. Hybrid metaheuristics with evolutionary algorithms specializing in intensication and diversication: Overview and progress report. Comput. Oper. Res., 37:481{497, March 2010.
S. McClintock, T. Lunney, and A. Hashim. A fuzzy logic controlled genetic algorithm environment. In Systems, Man, and Cybernetics, 1997. 'Computational Cybernetics and Simulation'., 1997 IEEE International Conference on, volume 3, pages 2181{2186 vol.3, 1997.
Heinz Muhlenbein, Thilo Mahnig, and Alberto Ochoa Rodriguez. Schemata, distributions and graphical models in evolutionary optimization. Journal of Heuristics, 5:215{247, 1999.
F. Nadi and A.T. Khader. Managing search in a partitioned search space in ga. In Cy-bernetics and Intelligent Systems (CIS), 2010 IEEE Conference on, pages 114 {119, june 2010.
Farhad Nadi and Ahamad Tajudin Abdul Khader. A parameter-less genetic algorithm with customized crossover and mutation operators. In Natalio Krasnogor and Pier Luca Lanzi, editors, GECCO, pages 901{908. ACM, 2011.
Volker Nannen, Selmar K. Smit, and Agoston E. Eiben. Costs and benets of tuning parameters of evolutionary algorithms. In Proceedings of the 10th international conference on Parallel Problem Solving from Nature, pages 528{538. Springer-Verlag, Berlin, Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-87700-4_53
Martin Pelikan, David E. Goldberg, and Fernando Lobo. A survey of optimization by building and using probabilistic models. IlliGAL Report No. 99018, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 1999.
Kumara Sastry and David E. Goldberg. On extended compact genetic algorithm. Technical report, GECCO-2000, late breaking papers, Genetic And Evolutionary Computation Conference, 2000.
Selmar K. Smit and A. E. Eiben. Comparing Parameter Tuning Methods for Evolutionary Algorithms. In IEEE Congress on Evolutionary Computation (CEC), pages 399{406, May 2009.
Jim Smith and Terence C. Fogarty. Adaptively parameterised evolutionary systems: Selfadaptive recombination and mutation in a genetic algorithm. In Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberger, and Hans-Paul Schwefel, editors, PPSN, volume 1141 of Lecture Notes in Computer Science, pages 441{450. Springer, 1996.
William M. Spears. Evolutionary Algorithms: The Role of Mutation and Recombination (Natural Computing Series). Springer, June 2000.
M. Srinivas and Lalit M. Patnaik. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 24(4):656{667, 1994.
Fatemeh Vafaee. Controlling Genetic Operator Rates in Evolutionary Algorithms. PhD thesis, Dept. Computer Science, 2011.
Fatemeh Vafaee and Peter C. Nelson. An explorative and exploitative mutation scheme. In IEEE Congress on Evolutionary Computation, pages 1{8. IEEE, 2010.
Peter Vajda, Agoston E. Eiben, and Wiebe Hordijk. Parameter control methods for selection operators in genetic algorithms. In Proceedings of the 10th international conference on Parallel Problem Solving from Nature, pages 620{630, Berlin, Heidelberg, 2008. Springer-Verlag. http://dx.doi.org/10.1007/978-3-540-87700-4_62
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
