Exploration and exploitation in evolutionary algorithms

ACM Computing Surveys - Tập 45 Số 3 - Trang 1-33 - 2013
Matej Črepinšek1, Shih-Hsi Liu2, Marjan Mernik1
1University of Maribor, Maribor, Slovenia
2California State University, Fresno, CA

Tóm tắt

“Exploration and exploitation are the two cornerstones of problem solving by search.” For more than a decade, Eiben and Schippers' advocacy for balancing between these two antagonistic cornerstones still greatly influences the research directions of evolutionary algorithms (EAs) [1998]. This article revisits nearly 100 existing works and surveys how such works have answered the advocacy. The article introduces a fresh treatment that classifies and discusses existing work within three rational aspects: (1) what and how EA components contribute to exploration and exploitation; (2) when and how exploration and exploitation are controlled; and (3) how balance between exploration and exploitation is achieved. With a more comprehensive and systematic understanding of exploration and exploitation, more research in this direction may be motivated and refined.

Từ khóa


Tài liệu tham khảo

10.1109/TEVC.2010.2058117

10.1109/TEVC.2005.843751

10.1145/1068009.1068250

10.1109/TEVC.2010.2064322

10.1109/ICEC.1994.350042

Bäck T., Evolutionary Programming, Genetic Algorithms

Bäck T., Proceedings of the 6th International Conference on Parallel Problem Solving from Nature

10.1162/evco.1993.1.1.1

Bartz-Beielstein T., Proceedings of the IEEE Congress on Evolutionary Computation. 773--780

Becerra R. L., 2006, Cultured differential evolution for constrained optimization, Comput. Methods Appl. Mech. Eng., 195, 33

Bersano-Begey T., 1997, Proceedings of the Late Breaking Papers at the Genetic Programming Conference. 7--10

10.1109/4235.930314

Birattari M., Proceedings of the Genetic and Evolutionary Computation Conference. 11--18

10.1016/j.asoc.2011.02.032

10.1145/937503.937505

Bogon T., Proceedings of the 3rd International Conference on Agents and Artificial Intelligence. 51--60

10.1109/TEVC.2003.810761

10.1109/TEVC.2006.872133

10.1109/TEVC.2003.819263

Burke E. Gustafson S. Kendall G. and Krasnogor N . 2002 . Advanced population diversity measures in genetic programming. In Proceedings of Parallel Problem Solving from Nature Lecture Notes in Computer Science vol. 2439 Springer 341--350. Burke E. Gustafson S. Kendall G. and Krasnogor N. 2002. Advanced population diversity measures in genetic programming. In Proceedings of Parallel Problem Solving from Nature Lecture Notes in Computer Science vol. 2439 Springer 341--350.

10.1023/A:1009625526657

10.1007/s10732-006-9003-1

10.1109/TEVC.2008.2011742

10.1109/TEVC.2010.2040180

Cobb H. G., Proceedings of the 5th International Conference on Genetic Algorithms. 523--530

10.1504/IJICA.2011.037947

10.1177/1059712306072335

10.1109/TEVC.2004.831262

Darwen P. J., Proceedings of the Congress of Evolutionary Computation. 987--994

De Jong E. D., Proceedings of the 3rd Genetic and Evolutionary Computation Conference. 11--18

De Jong K. A., Evolutionary Computation

10.1007/BF01530777

Deb K., Proceedings of the 3rd International Conference on Genetic Algorithms. 42--50

D'haeseleer P. and Bluming J. 1994. Advances in Genetic Programming. MIT Press Cambridge MA. D'haeseleer P. and Bluming J. 1994. Advances in Genetic Programming. MIT Press Cambridge MA.

10.1145/1570256.1570301

10.1109/4235.771166

Eiben A. E. Marchiori E. and Valko V. A . 2004 . Evolutionary algorithms with on-the-fly population size adjustment. In Proceedings of Parallel Problem Solving from Nature Lecture Notes in Computer Science vol. 3242 Springer 41--50. Eiben A. E. Marchiori E. and Valko V. A. 2004. Evolutionary algorithms with on-the-fly population size adjustment. In Proceedings of Parallel Problem Solving from Nature Lecture Notes in Computer Science vol. 3242 Springer 41--50.

10.5555/2379195.2379198

10.1016/j.swevo.2011.02.001

Eiben A. E. and Smith J. E. 2008. Introduction to Evolutionary Computing. Springer Berlin. Eiben A. E. and Smith J. E. 2008. Introduction to Evolutionary Computing. Springer Berlin.

Eshelman L. J., 1991, The chc adaptive search algorithm: How to have safe search when engaging in nontraditional genetic recombination, Found. Genetic Algorith., 1, 265

Eshelman L. J., Proceedings of the 4th International Conference on Genetic Algorithms. 115--122

10.1016/j.asoc.2011.02.004

10.1016/j.asoc.2009.08.001

10.5555/645512.657249

Fogel L. J., Intelligence Through Simulated Evolution: Forty Years of Evolutionary Programming

Fonseca C. M., Proceedings of the 1st International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications. 45--52

Freisleben B., Proceedings of the International Conference on Evolutionary Computation. 616--621

10.1145/1276958.1277194

10.1145/1389095.1389276

10.1145/1830483.1830646

10.1016/j.asoc.2011.05.046

Gen M. and Cheng R. 1997. Genetic Algorithms and Engineering Design. John Wiley and Sons Itoboken NJ. Gen M. and Cheng R. 1997. Genetic Algorithms and Engineering Design. John Wiley and Sons Itoboken NJ.

Ghosh A., Proceedings of the Australian New Zealand Conference on Intelligent Information Systems. 276--279

10.1023/A:1022692631328

Goldberg D. E., Genetic Algorithms in Search, Optimization and Machine Learning. Dorling Kindersley

Goldberg D. E. and Deb K. 1991. A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms. Morgan Kaufmann Burlington MA 69--93. Goldberg D. E. and Deb K. 1991. A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms. Morgan Kaufmann Burlington MA 69--93.

Goldberg D. E., Proceedings of the 2nd International Conference on Genetic Algorithms. 41--49

10.1016/j.amc.2008.08.053

Greenwood G. W., Proceedings of the Congress of Evolutionary Computation. 666--671

10.1109/TSMC.1986.289288

Grefenstette J. J., 1992, Proceedings of Parallel Problem Solving from Nature

10.5555/645514.658086

Harik G. R. and Lobo F. 1999. A parameter-less genetic algorithm. Tech. rep. University of Illinois at Urbana-Champaign IL. Harik G. R. and Lobo F. 1999. A parameter-less genetic algorithm. Tech. rep. University of Illinois at Urbana-Champaign IL.

10.1109/4235.797971

Herrera F. and Lozano M. 1996. Adaptation of genetic algorithm parameters based on fuzzy logic controllers. Genetic Algorith. Soft Comput. 95--125. Herrera F. and Lozano M. 1996. Adaptation of genetic algorithm parameters based on fuzzy logic controllers. Genetic Algorith. Soft Comput. 95--125.

Hesser J. and Männer R . 1991 . Toward an optimal mutation probability for genetic algorithms. In Proceedings of the 1st Conference of Parallel Problem Solving from Nature Lecture Notes in Computer Science vol. 496 Springer 23--32. Hesser J. and Männer R. 1991. Toward an optimal mutation probability for genetic algorithms. In Proceedings of the 1st Conference of Parallel Problem Solving from Nature Lecture Notes in Computer Science vol. 496 Springer 23--32.

Holland J. H., Adaptation in Natural and Artificial Systems, 10.7551/mitpress/1090.001.0001

Horn J., Proceedings of the 1st IEEE Conference on Evolutionary Computation. 82--87

10.1109/TEVC.2005.863127

Ishibuchi H., 2010, Nature: Part I

10.1016/j.ejor.2007.04.007

10.1109/TEVC.2010.2043365

10.1109/TEVC.2003.810752

10.1016/j.ins.2011.03.018

Jin X., Proceedings of the Congress on Evolutionary Computation. 1672--1678

10.1016/j.asoc.2009.12.037

10.1016/j.ins.2007.01.003

Kohonen T., Self-Organizing Maps, 3

10.1109/TEVC.2005.860765

Koza J. R., 1992, Genetic Programming: On the Programming of Computers by Means of Natural Selection

10.1109/TEVC.2005.850260

Krink T., Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, Springer-Verlag

Langdon W. B., Data Structures and Genetic Programming: Genetic Programming &plus, 10.1007/978-1-4615-5731-9

10.1016/j.asoc.2011.01.010

10.1109/72.623217

10.1109/4235.910464

10.1162/106365602760234081

10.1007/s11771-004-0066-6

10.3923/itj.2011.2378.2384

10.1016/j.asoc.2010.06.017

10.1016/j.asoc.2010.05.007

10.1109/TEVC.2011.2150754

Liu S.-H., Proceedings of the International Conference on Bioinspired Optimization Methods and their Applications. 41--50

10.1145/1244002.1244166

10.5555/1735203.1735211

Lobo F. J. Lima C. F. and Michalewicz Z. 2007. Parameter Setting in Evolutionary Algorithms. Springer Berlin. Lobo F. J. Lima C. F. and Michalewicz Z. 2007. Parameter Setting in Evolutionary Algorithms. Springer Berlin.

10.1016/j.ins.2008.07.031

Luerssen M. H., Recent Advances in Artificial Life

Mahfoud S. W., Niching methods for genetic algorithms. Tech. rep

10.1109/ICKS.2008.12

10.1016/j.asoc.2010.04.024

Martin W. N. Lienig J. and Cohoon J. P. 1999. Island (Migration) Models: Evolutionary Algorithms based on Punctuated Equilibria (In Handbook of Evolutionary Computation). Oxford University Press. Martin W. N. Lienig J. and Cohoon J. P. 1999. Island (Migration) Models: Evolutionary Algorithms based on Punctuated Equilibria (In Handbook of Evolutionary Computation). Oxford University Press.

10.1016/j.asoc.2010.06.015

Masisi L., Proceedings of the IEEE International Conference on Computational Cybernetics. 41--45

10.1109/ICSMC.1999.814164

10.1162/1063656043138923

Mauldin M. L., 1984, Proceedings of the National Conference on Artificial Intelligence. 247--250

10.1109/TEVC.2010.2046173

McPhee N. F., Proceedings of the 1st Genetic and Evolutionary Computation Conference. 1112--1120

Mengshoel O. J., Proceedings of the Genetic and Evolutionary Computation Conference. 409--416

10.1145/1118890.1118892

10.1109/4235.887234

Michalewicz Z., Genetic Algorithms &plus

10.5755/j01.itc.40.4.983

Misevičius A., 2008, Enhanced improvement of individuals in genetic algorithms, Inform. Technol. Control, 37, 179

10.1016/j.asoc.2011.08.047

10.1016/j.ins.2010.09.016

10.1162/evco.2007.15.4.445

Mori N., Proceedings of the 2nd IEEE International Conference on Evolutionary Computation. 188--192

Moscato P., New Ideas in Optimization

Mühlenbein H. and Paass G . 1996 . From recombination of genes to the estimation of distributions I. binary parameters. In Proceedings of Parallel Problem Solving from Nature Lecture Notes in Computer Science vol. 1141 Springer 178--187. Mühlenbein H. and Paass G. 1996. From recombination of genes to the estimation of distributions I. binary parameters. In Proceedings of Parallel Problem Solving from Nature Lecture Notes in Computer Science vol. 1141 Springer 178--187.

10.1145/1143997.1144029

10.1109/TEVC.2008.2009460

10.5555/1368027.1368029

10.1109/TSMCB.2005.856143

Oppacher F., Proceedings of the 1st Genetic and Evolutionary Computation Conference. 504--510

10.1177/1059712309103566

10.1016/j.cor.2010.06.007

10.1109/ICEC.1996.542703

10.1109/TEVC.2008.927706

10.1109/TEVC.2007.894200

Ramsey C. L., Proceedings of the 5th International Conference on Genetic Algorithms. 84--91

10.5555/645514.657916

Rosca J., 1995, Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, 23--32

10.1109/4235.735432

Schaffer J. D., Proceedings of the 3rd International Conference on Genetic Algorithms. 51--60

10.1049/cp:19971221

10.1145/1143997.1144200

Smit S. K., Proceedings of the IEEE Congress on Evolutionary Computation. 399--406

10.1007/s005000050009

10.1162/evco.1993.1.2.127

Smith R. E., 1995, Adaptively resizing populations: Algorithm, analysis, and first results, Complex Syst., 9, 47

10.1016/j.asoc.2009.11.024

Spears W. M., 1995, Proceedings of the Evolutionary Programming Conference. 367--384

10.1109/21.286385

10.1007/978-3-540-24854-5_76

10.1023/A:1008202821328

10.1023/A:1016540724870

10.1162/106365603766646816

Tsujimura Y., Proceedings of the 2nd International Conference on Knowledge-Based Intelligent Electronic Systems. 285--290

10.1162/evco.1997.5.1.61

Tsutsui S., Proceedings of the 7th International Conference on Genetic Algorithms. 238--245

Ursem R., 2000, Proceedings of the 2nd Genetic and Evolutionary Computation Conference. 19--26

Ursem R., Proceedings of Parallel Problem Solving from Nature

10.1016/j.ins.2011.09.001

Watson J. Baker T. Bell S. Gann A. Levine M. and Losick R. 2004. Molecular Biology of the Gene. Benjamin Cummings San Francisco CA. Watson J. Baker T. Bell S. Gann A. Levine M. and Losick R. 2004. Molecular Biology of the Gene. Benjamin Cummings San Francisco CA.

Whitley D., Proceedings of the 4th International Conference on Genetic Algorithms. 77--84

10.1080/09528139008953723

Wineberg M., Proceedings of the International Conference on Genetic and Evolutionary Computation. 1481--1492

10.1007/s00500-002-0235-1

10.1162/evco.2008.16.3.385

10.1109/4235.771163

Yin X., Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms. 450--457

10.1016/j.ins.2010.04.008

10.1109/TEVC.2008.2003008

10.1109/TEVC.2009.2014613

10.1016/j.asoc.2010.05.029

10.1109/TEVC.2008.920672

10.1162/106365600568202

Zitzler E., 2002, Design: Optim. Control, 95--100.

10.1109/4235.797969