research-article

Exploration and exploitation in evolutionary algorithms: A survey

Authors:

Matej Črepinšek,

Shih-Hsi Liu,

Marjan MernikAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 45, Issue 3

Article No.: 35, Pages 1 - 33

https://doi.org/10.1145/2480741.2480752

Published: 03 July 2013 Publication History

Get Access

Abstract

“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.

References

[1]

Adra, S. F. and Fleming, P. J. 2011. Diversity management in evolutionary many-objective optimization. IEEE Trans. Evol. Comput. 15, 2, 183--195.

Digital Library

Google Scholar

[2]

Alba, E. and Dorronsoro, B. 2005. The exploration/exploitation tradeoff in dynamic cellular genetic algorithms. IEEE Trans. Evol. Comput. 9, 3, 126--142.

Digital Library

Google Scholar

[3]

Amor, H. B. and Rettinger, A. 2005. Intelligent exploration for genetic algorithms: Using self-organizing maps in evolutionary computation. In Proceedings of the 7th Genetic and Evolutionary Computation Conference. 1531--1538.

Digital Library

Google Scholar

[4]

Araujo, L. and Merelo, J. J. 2011. Diversity through multiculturality: Assessing migrant choice policies in an island model. IEEE Trans. Evol. Comput. 15, 4, 456--468.

Digital Library

Google Scholar

[5]

Bäck, T. 1994. Selective pressure in evolutionary algorithms: A characterization of selection mechanisms. In Proceedings of the 1st Conference on Evolutionary Computing. 57--62.

Crossref

Google Scholar

[6]

Bäck, T. 1996. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press.

Digital Library

Google Scholar

[7]

Bäck, T., Eiben, A. E., and van der Vaart, N. A. L. 2000. An empirical study on gas without parameters. In Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, Springer-Verlag, 315--324.

Digital Library

Google Scholar

[8]

Bäck, T. and Schwefel, H.-P. 1993. An overview of evolutionary algorithms for parameter optimization. Evol. Comput. 1, 1, 1--23.

Digital Library

Google Scholar

[9]

Bartz-Beielstein, T., Lasarczyk, C. W. G., and Preuss, M. 2005. Sequential parameter optimization. In Proceedings of the IEEE Congress on Evolutionary Computation. 773--780.

Google Scholar

[10]

Becerra, R. L. and Coello Coello, C. A. 2006. Cultured differential evolution for constrained optimization. Comput. Methods Appl. Mech. Eng. 195, 33--36, 4303--4322.

Google Scholar

[11]

Bersano-Begey, T. 1997. Controlling exploration, diversity and escaping local optima in GP: Adopting weights of training sets to model resource consumption. In Proceedings of the Late Breaking Papers at the Genetic Programming Conference. 7--10.

Google Scholar

[12]

Beyer, H.-G. and Deb, K. 2001. On self-adaptive features in real-parameter evolutionary algorithms. IEEE Trans. Evol. Comput. 5, 3, 250--270.

Digital Library

Google Scholar

[13]

Birattari, M., Stützle, T., Paquete, L., and Varrentrapp, K. 2002. A racing algorithm for configuring metaheuristics. In Proceedings of the Genetic and Evolutionary Computation Conference. 11--18.

Digital Library

Google Scholar

[14]

Blum, C., Puchinger, J., Raidl, G. A., and Roli, A. 2011. Hybrid metaheuristics in combinatorial optimization: A survey. Appl. Soft Comput. 11, 6, 4135--4151.

Digital Library

Google Scholar

[15]

Blum, C. and Roli, A. 2003. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Comput. Surv. 35, 3, 268--308.

Digital Library

Google Scholar

[16]

Bogon, T., Poursanidis, G., Lattner, A. D., and Timm, I. J. 2011. Extraction of function features for an automatic configuration of particle swarm optimization. In Proceedings of the 3^rd International Conference on Agents and Artificial Intelligence. 51--60.

Google Scholar

[17]

Bosman, P. and Thierens, D. 2003. The balance between proximity and diversity in multiobjective evolutionary algorithms. IEEE Trans. Evol. Comput. 7, 2, 174--188.

Digital Library

Google Scholar

[18]

Brest, J., Greiner, S., Boškovič, B., Mernik, M., and Žumer, V. 2006. Self-adapting control parameters in differential evolution: A comparative study on numerical benchmark problems. IEEE Trans. Evol. Comput. 10, 6, 646--657.

Digital Library

Google Scholar

[19]

Burke, E., Gustafson, S., and Kendall, G. 2004. Diversity in genetic programming: An analysis of measures and correlation with fitness. IEEE Trans. Evol. Comput. 8, 1, 47--62.

Digital Library

Google Scholar

[20]

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.

Digital Library

Google Scholar

[21]

Calegary, P., Coray, G., Hertz, A., Kobler, D., and Kuonen, P. 1999. A taxonomy of evolutionary algorithms in combinatorial optimization. J. Heuristics 5, 2, 145--158.

Digital Library

Google Scholar

[22]

Chaiyaratana, N., Piroonratana, T., and Sangkawelert, N. 2007. Effects of diversity control in single-objective and multi-objective genetic algorithms. J. Heuristics 13, 1--34.

Digital Library

Google Scholar

[23]

Chen, G., Low, C. P., and Yang, Z. 2009. Preserving and exploiting genetic diversity in evolutionary programming algorithms. IEEE Trans. Evol. Comput. 13, 3, 661--673.

Digital Library

Google Scholar

[24]

Chow, C. K. and Yuen, S. Y. 2011. An evolutionary algorithm that makes decision based on the entire previous search history. IEEE Trans. Evol. Comput. 15, 6, 741--769.

Crossref

Google Scholar

[25]

Cobb, H. G. and Grefenstette, J. J. 1993. Genetic algorithms for tracking changing environments. In Proceedings of the 5th International Conference on Genetic Algorithms. 523--530.

Digital Library

Google Scholar

[26]

Črepinšek, M., Mernik, M., and Liu, S.-H. 2011. Analysis of exploration and exploitation in evolutionary algorithms by ancestry trees. Int. J. Innovative Comput. Appl. 3, 1, 11--19.

Digital Library

Google Scholar

[27]

Curran, D. and O'Riordan, C. 2006. Increasing population diversity through cultural learning. Adapt. Behav. 14, 4, 315--338.

Digital Library

Google Scholar

[28]

Czarn, A., MacNish, C., Vijayan, K., Turlach, B., and Gupta, R. 2004. Statistical exploratory analysis of genetic algorithms. IEEE Trans. Evol. Comput. 8, 4, 405--421.

Digital Library

Google Scholar

[29]

Darwen, P. J. and Yao, X. 2001. Why more choices cause less cooperation in iterated prisoner's dilemma. In Proceedings of the Congress of Evolutionary Computation. 987--994.

Google Scholar

[30]

De Jong, E. D., Watson, R. A., and Pollack, J. B. 2001. Reducing bloat and promoting diversity using multi-objective methods. In Proceedings of the 3rd Genetic and Evolutionary Computation Conference. 11--18.

Google Scholar

[31]

De Jong, K. A. 1975. An analysis of the behavior of a class of genetic adaptive systems. Ph.D. dissertation, University of Michigan, Ann Arbor, MI.

Digital Library

Google Scholar

[32]

De Jong, K. A. 2002. Evolutionary Computation. MIT Press, Cambridge, MA.

Digital Library

Google Scholar

[33]

De Jong, K. A. and Spears, W. 1992. A formal analysis of the role of multi-point crossover in genetic algorithms. Ann. Math. Artif. Intell. 5, 1, 1--26.

Crossref

Google Scholar

[34]

Deb, K. and Goldberg, D. E. 1989. An investigation of niche and species formation in genetic function optimization. In Proceedings of the 3rd International Conference on Genetic Algorithms. 42--50.

Digital Library

Google Scholar

[35]

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

Google Scholar

[36]

Dréo, J. 2009. Using performance fronts for parameter setting of stochastic metaheuristics. In Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference. 2197--2200.

Digital Library

Google Scholar

[37]

Eiben, A. E., Hinterding, R., and Michalewicz, Z. 1999. Parameter control in evolutionary algorithms. IEEE Trans. Evol. Comput. 3, 2, 124--141.

Digital Library

Google Scholar

[38]

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.

Google Scholar

[39]

Eiben, A. E. and Schippers, C. 1998. On evolutionary exploration and exploitation. Fundamenta Informaticae 35, 35--50.

Digital Library

Google Scholar

[40]

Eiben, A. E. and Smit, S. K. 2011. Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm Evol. Comput. 1, 1, 19--31.

Crossref

Google Scholar

[41]

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

Digital Library

Google Scholar

[42]

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--283.

Google Scholar

[43]

Eshelman, L. J. and Schaffer, J. 1991. Preventing premature convergence in genetic algorithms by preventing incest. In Proceedings of the 4th International Conference on Genetic Algorithms. 115--122.

Google Scholar

[44]

Fernandez-Prieto, J. A., Canada-Bago, J., Gadeo-Martos, M. A., and Velasco, J. R. 2011. Optimisation of control parameters for genetic algorithms to test computer networks under realistic traffic loads. Appl. Soft Comput. 11, 4, 3744--3752.

Digital Library

Google Scholar

[45]

Fister, I., Mernik, M., and Filipič, B. 2010. A hybrid self-adaptive evolutionary algorithm for marker optimization in the clothing industry. Appl. Soft Comput. 10, 2, 409--422.

Digital Library

Google Scholar

[46]

Fogarty, T. C. 1989. Varying the probability of mutation in the genetic algorithm. In Proceedings of the 3rd International Conference on Genetic Algorithms. 104--109.

Digital Library

Google Scholar

[47]

Fogel, L. J. 1999. Intelligence Through Simulated Evolution: Forty Years of Evolutionary Programming. Wiley, Itoboken, NJ.

Digital Library

Google Scholar

[48]

Fonseca, C. M. and Fleming, P. J. 1995. Multiobjective genetic algorithms made easy: Selection, sharing and mating restriction. In Proceedings of the 1st International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications. 45--52.

Google Scholar

[49]

Freisleben, B. and Merz, P. 1996. A genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems. In Proceedings of the International Conference on Evolutionary Computation. 616--621.

Google Scholar

[50]

Friedrich, T., Hebbinghaus, N., and Neumann, F. 2007. Rigorous analyses of simple diversity mechanisms. In Proceedings of the Genetic and Evolutionary Computation Conference. 1219--1225.

Digital Library

Google Scholar

[51]

Friedrich, T., Oliveto, P. S., Sudholt, D., and Witt, C. 2008. Theoretical analysis of diversity mechanisms for global exploration. In Proceedings of the Genetic and Evolutionary Computation Conference. 945--952.

Digital Library

Google Scholar

[52]

Galván-López, E., McDermott, J., O'Neill, M., and Brabazon, A. 2010. Towards an understanding of locality in genetic programming. In Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation. 901--908.

Digital Library

Google Scholar

[53]

Gao, H. and Xu, W. 2011. Particle swarm algorithm with hybrid mutation strategy. Appl. Soft Comput. 11, 8, 5129--5142.

Digital Library

Google Scholar

[54]

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

Digital Library

Google Scholar

[55]

Ghosh, A., Tsutsui, S., and Tanaka, H. 1996. Individual aging in genetic algorithms. In Proceedings of the Australian New Zealand Conference on Intelligent Information Systems. 276--279.

Google Scholar

[56]

Goh, K. S., Lim, A., and Rodrigues, B. 2003. Sexual selection for genetic algorithms. Artif. Intell. Rev. 19, 123--152.

Digital Library

Google Scholar

[57]

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

Google Scholar

[58]

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.

Google Scholar

[59]

Goldberg, D. E. and Richardson, J. 1987. Genetic algorithms with sharing for multimodal function optimization. In Proceedings of the 2nd International Conference on Genetic Algorithms. 41--49.

Digital Library

Google Scholar

[60]

Gong, W., Cai, Z., and Jiang, L. 2008. Enhancing the performance of differential evolution using orthogonal design method. Appl. Math. Comput. 206, 1, 56--69.

Crossref

Google Scholar

[61]

Greenwood, G. W., Fogel, G. B., and Ciobanu, M. 1999. Emphasizing extinction in evolutionary programming. In Proceedings of the Congress of Evolutionary Computation. 666--671.

Google Scholar

[62]

Grefenstette, J. J. 1986. Optimization of control parameters for genetic algorithms. IEEE Trans. Syst., Man Cybernetics 16, 1, 122--128.

Digital Library

Google Scholar

[63]

Grefenstette, J. J. 1992. Genetic algorithms for changing environments. In Proceedings of Parallel Problem Solving from Nature, Elsevier, Amsterdam, 137--144.

Google Scholar

[64]

Harik, G. R. 1995. Finding multimodal solutions using restricted tournament selection. In Proceedings of the 6th International Conference on Genetic Algorithms. 24--31.

Digital Library

Google Scholar

[65]

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

Google Scholar

[66]

Harik, G. R., Lobo, F., and Goldberg, D. E. 1999. The compact genetic algorithm. IEEE Trans. Evol. Comput. 3, 4, 287--297.

Digital Library

Google Scholar

[67]

Hart, W. E. 1994. Adaptive global optimization with local search. Ph.D. dissertation, University of California, San Diego, CA.

Digital Library

Google Scholar

[68]

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

Google Scholar

[69]

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.

Digital Library

Google Scholar

[70]

Holland, J. H. 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI.

Google Scholar

[71]

Horn, J., Nafpliotis, N., and Goldberg, D. E. 1994. A niched pareto genetic algorithm for multiobjective optimization. In Proceedings of the 1st IEEE Conference on Evolutionary Computation. 82--87.

Google Scholar

[72]

Hutter, M. and Legg, S. 2006. Fitness uniform optimization. IEEE Trans. Evol. Comput. 10, 5, 568--589.

Digital Library

Google Scholar

[73]

Ishibuchi, H., Hitotsuyanagi, Y., Wajamatsu, Y., and Nojima, Y. 2010a. How to choose solutions for local search in multiobjective combinatorial memetic algorithms. In Proceedings of the 11th Conference of Parallel Problem Solving from Nature: Part I, Lecture Notes in Computer Science, vol. 6238, Springer, 516--525.

Digital Library

Google Scholar

[74]

Ishibuchi, H., Narukawa, K., Tsukamoto, N., and Nojima, Y. 2008. An empirical study on similarity-based mating for evolutionary multiobjective combinatorial optimization. Europ. J. Oper. Res. 188, 1, 57--75.

Crossref

Google Scholar

[75]

Ishibuchi, H., Tsukamoto, N., and Nojima, Y. 2010b. Diversity improvement by non-geometric binary crossover in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 14, 6, 985--998.

Digital Library

Google Scholar

[76]

Ishibuchi, H., Yoshida, T., and Murata, T. 2003. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans. Evol. Comput. 7, 2, 204--223.

Digital Library

Google Scholar

[77]

Jia, D., Zheng, G., and Khan, M. K. 2011. An effective memetic differential evolution algorithm based on chaotic local search. Inform. Sci. 181, 15, 3175--3187.

Digital Library

Google Scholar

[78]

Jin, X. and Reynolds, R. 1999. Using knowledge-based evolutionary computation to solve nonlinear constraint optimization problems: A cultural algorithm approach. In Proceedings of the Congress on Evolutionary Computation. 1672--1678.

Google Scholar

[79]

Joan-Arinyo, R., Luzon, M. V., and Yeguas, E. 2011. Parameter tuning of pbil and chc evolutionary algorithms applied to solve the root identification problem. Appl. Soft Comput. 11, 1, 754--767.

Digital Library

Google Scholar

[80]

Jose-Revuelta, L. M. S. 2007. A new adaptive genetic algorithm for fixed channel assignment. Inform. Sci. 177, 2655--2678.

Digital Library

Google Scholar

[81]

Kohonen, T. 2001. Self-Organizing Maps 3rd Ed. Springer-Verlag, New York, NY.

Digital Library

Google Scholar

[82]

Koumousis, V. and Katsaras, C. P. 2006. A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance. IEEE Trans. Evol. Comput. 10, 1, 19--28.

Digital Library

Google Scholar

[83]

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

Digital Library

Google Scholar

[84]

Krasnogor, N. and Smith, J. 2005. A tutorial for competent memetic algorithms: Model, taxonomy, and design issues. IEEE Trans. Evol. Comput. 9, 5, 474--488.

Digital Library

Google Scholar

[85]

Krink, T., Rickers, P., and Thomsen, R. 2000. Applying self-organised criticality to evolutionary algorithms. In Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, Springer-Verlag, New York, NY, 375--384.

Digital Library

Google Scholar

[86]

Langdon, W. B. 1998. Data Structures and Genetic Programming: Genetic Programming + Data Structures = Automatic Programming. Kluwer, Alphen aan den Rjin, Netherlands.

Digital Library

Google Scholar

[87]

Lee, J.-Y., Kim, M.-S., and Lee, J.-J. 2011. Compact genetic algorithm using belief vectors. Appl. Soft Comput. 11, 4, 3385--3401.

Digital Library

Google Scholar

[88]

Leung, Y., Gao, Y., and Xu, Z. 1997. A perspective on premature convergence in genetic algorithms and its markov chain analysis. Trans. Neural Netw. 8, 5, 1165--1176.

Digital Library

Google Scholar

[89]

Leung, Y. and Wang, Y. 2001. An orthogonal genetic algorithm with quantization for global numerical optimization. IEEE Trans. Evol. Comput. 5, 1, 41--53.

Digital Library

Google Scholar

[90]

Li, J.-P., Balazs, M. E., Parks, G. T., and Clarkson, J. P. 2002. A species conserving genetic algorithm for multimodal function optimization. Evol. Comput. 10 3, 207--234.

Digital Library

Google Scholar

[91]

Li, M., Cai, Z., and Sun, G. 2004. An adaptive genetic algorithm with diversity-guided mutation and its global convergence property. J. Central South Univ. Technol. 11, 3, 323--327.

Crossref

Google Scholar

[92]

Li, Z. and Wang, X. 2011. Chaotic differential evolution algorithm for solving constrained optimization problems. Inform. Technol. J. 10, 12, 2378--2384.

Crossref

Google Scholar

[93]

Liang, Y. and Leung, K.-S. 2011. Genetic algorithm with adaptive elitist-population strategies for multimodal function optimization. Appl. Soft Comput. 11, 2, 2017--2034.

Digital Library

Google Scholar

[94]

Liao, T. W. 2010. Two hybrid differential evolution algorithms for engineering design optimization. Appl. Soft Comput. 10, 4, 1188--1199.

Digital Library

Google Scholar

[95]

Lin, J.-Y. and Chen, Y.-P. 2011. Analysis on the collaboration between global search and local search in memetic computation. IEEE Trans. Evol. Comput. 15, 5, 608--622.

Digital Library

Google Scholar

[96]

Liu, S.-H., Mernik, M., and Bryant, B. R. 2004. Parameter control in evolutionary algorithms by domain-specific scripting language PPC_EA. In Proceedings of the International Conference on Bioinspired Optimization Methods and their Applications. 41--50.

Google Scholar

[97]

Liu, S.-H., Mernik, M., and Bryant, B. R. 2007. A clustering entropy-driven approach for exploring and exploiting noisy functions. In Proceedings of the 22nd ACM Symposium on Applied Computing. 738--742.

Digital Library

Google Scholar

[98]

Liu, S.-H., Mernik, M., and Bryant, B. R. 2009. To explore or to exploit: An entropy-driven approach for evolutionary algorithms. Int. J. Knowl. Intell. Eng. Syst. 13, 3, 185--206.

Digital Library

Google Scholar

[99]

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

Digital Library

Google Scholar

[100]

Lozano, M., Herrera, F., and Cano, J. R. 2008. Replacement strategies to preserve useful diversity in steady-state genetic algorithms. Inform. Sci. 178, 23, 4421--4433.

Digital Library

Google Scholar

[101]

Luerssen, M. H. 2005. Phenotype diversity objectives for graph grammar evolution. In Recent Advances in Artificial Life, World Scientific Publishing, Singapore, 159--170.

Google Scholar

[102]

Mahfoud, S. W. 1995. Niching methods for genetic algorithms. Tech. rep., University of Illinois at Urbana Champaign, IL.

Google Scholar

[103]

Majig, M. and Fukushima, M. 2008. Adaptive fitness function for evolutionary algorithm and its applications. In Proceedings of the International Conference on Informatics Education and Research for Knowledge-Circulating Society. 119--124.

Digital Library

Google Scholar

[104]

Mallipeddi, R., Suganthan, P. N., Pan, Q. K., and Tasgetiren, M. F. 2011. Differential evolution algorithm with ensemble of parameters and mutation strategies. Appl. Soft Comput. 11, 2, 1679--1696.

Digital Library

Google Scholar

[105]

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.

Google Scholar

[106]

Mashinchi, M. H., Orgun, M. A., and Pedrycz, W. 2011. Hybrid optimization with improved tabu search. Appl. Soft Comput. 11, 2, 1993--2006.

Digital Library

Google Scholar

[107]

Masisi, L., Nelwamondo, V., and Marwala, T. 2008. The use of entropy to measure structural diversity. In Proceedings of the IEEE International Conference on Computational Cybernetics. 41--45.

Google Scholar

[108]

Matsui, K. 1999. New selection method to improve the population diversity in genetic algorithms. In Proceedings of IEEE International Conference on Systems, Man and Cybernetics. 625--630.

Crossref

Google Scholar

[109]

Mattiussi, C., Waibel, M., and Floreano, D. 2004. Measures of diversity for populations and distances between individuals with highly reorganizable genomes. Evol. Comput. 12, 4, 495--515.

Digital Library

Google Scholar

[110]

Mauldin, M. L. 1984. Maintaining diversity in genetic search. In Proceedings of the National Conference on Artificial Intelligence. 247--250.

Google Scholar

[111]

McGinley, B., Maher, J., O'Riordan, C., and Morgan, F. 2011. Maintaining healthy population diversity using adaptive crossover, mutation, and selection. IEEE Trans. Evol. Computat. 15, 5, 692--714.

Digital Library

Google Scholar

[112]

McPhee, N. F. and Hopper, N. J. 1999. Analysis of genetic diversity through population history. In Proceedings of the 1st Genetic and Evolutionary Computation Conference. 1112--1120.

Digital Library

Google Scholar

[113]

Mengshoel, O. J. and Goldberg, D. E. 1999. Probabilistic crowding: Deterministic crowding with probabilisitic replacement. In Proceedings of the Genetic and Evolutionary Computation Conference. 409--416.

Google Scholar

[114]

Mernik, M., Heering, J., and Sloane, A. 2005. When and how to develop domain-specific languages. ACM Comput. Sur. 37, 4, 316--344.

Digital Library

Google Scholar

[115]

Merz, P. and Freisleben, B. 2000. Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans. Evol. Comput. 4, 4, 337--352.

Digital Library

Google Scholar

[116]

Michalewicz, Z. 1996. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, New York, NY.

Digital Library

Google Scholar

[117]

Misevičius, A. 2011. Generation of grey patterns using an improved genetic-evolutionary algorithm: Some new results. Inform. Technol. Control 40, 4, 330--343.

Crossref

Google Scholar

[118]

Misevičius, A. and Rubliauskas, D. 2008. Enhanced improvement of individuals in genetic algorithms. Inform. Technol. Control 37, 3, 179--186.

Google Scholar

[119]

Mongus, D., Repnik, B., Mernik, M., and Žalik, B. 2012. A hybrid evolutionary algorithm for tuning a cloth-simulation model. Appl. Soft Comput. 12, 1, 266--273.

Digital Library

Google Scholar

[120]

Montero, E. and Riff, M.-C. 2011. On-the-fly strategies for evolutionary algorithms. Inform. Sci. 181, 552--566.

Digital Library

Google Scholar

[121]

Moraglio, A., Kim, Y.-H., Yoon, Y., and Moon, B.-R. 2007. Geometric crossovers for multiway graph partitioning. Evol. Comput. 15, 4, 445--474.

Digital Library

Google Scholar

[122]

Mori, N., Yoshida, J., Tamaki, H., Kita, H., and Nishikawa, Y. 1995. A thermodynamical selection rule for the genetic algorithm. In Proceedings of the 2nd IEEE International Conference on Evolutionary Computation. 188--192.

Google Scholar

[123]

Moscato, P. 1999. Memetic algorithms: A short introduction. In New Ideas in Optimization, McGraw Hill Ltd., Maidenhead, U.K., 219--234.

Digital Library

Google Scholar

[124]

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.

Digital Library

Google Scholar

[125]

Nannen, V. and Eiben, A. E. 2006. A method for parameter calibration and relevance estimation in evolutionary algorithms. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. 183--190.

Digital Library

Google Scholar

[126]

Nguyen, Q. H., Ong, Y.-S., and Lim, M. H. 2009. A probabilistic memetic framework. IEEE Trans. Evol. Comput. 13, 3, 604--623.

Digital Library

Google Scholar

[127]

Ochoa, G., Bilgin, B., and Korkmaz, E. E. 2008. A comprehensive analysis of hyper-heuristics. Intell. Data Anal. 12, 1, 3--23.

Digital Library

Google Scholar

[128]

Ong, Y.-S., Lim, M.-H., Zhu, N., and Wong, K.-W. 2006. Classification of adaptive memetic algorithms: A comparative study. IEEE Trans. Syst. Man Cybernetics (Part B), 141--152.

Digital Library

Google Scholar

[129]

Oppacher, F. and Wineberg, M. 1999. The shifting balance ga: Improving the ga in dynamic environment. In Proceedings of the 1st Genetic and Evolutionary Computation Conference. 504--510.

Google Scholar

[130]

Paenke, I., Jin, Y., and Branke, J. 2009. Balancing population- and individual-level adaptation in changing environments. Adapt. Behav. 17, 2, 153--174.

Digital Library

Google Scholar

[131]

Pan, Q.-K., Suganthan, P. N., Wang, L., Gao, L., and Mallipeddi, R. 2011. A differential evolution algorithm with self-adapting strategy and control parameters. Comput. Oper. Res. 38, 1, 394--408.

Digital Library

Google Scholar

[132]

Petrowski, A. 1996. A clearing procedure as a niching method for genetic algorithms. In Proceedings of the IEEE International Conference on Evolutionary Computation. 798--803.

Crossref

Google Scholar

[133]

Qin, A. K., Huang, V. L., and Suganthan, P. N. 2009. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans. Evol. Comput. 13, 2, 398--417.

Digital Library

Google Scholar

[134]

Rahnamayan, S., Tizhoosh, H. R., and Salama, M. M. A. 2008. Opposition-based differential evolution. IEEE Trans. Evol. Comput. 12, 1, 64--79.

Digital Library

Google Scholar

[135]

Ramsey, C. L. and Grefenstette, J. J. 1993. Case-based initialization of genetic algorithms. In Proceedings of the 5th International Conference on Genetic Algorithms. 84--91.

Digital Library

Google Scholar

[136]

Ronald, E. 1995. When selection meets seduction. In Proceedings of the 6th International Conference on Genetic Algorithms. 167--173.

Digital Library

Google Scholar

[137]

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

Google Scholar

[138]

Sareni, B. and Krähenbühl, L. 1998. Fitness sharing and niching methods revisited. IEEE Trans. Evol. Comput. 2, 3, 97--106.

Digital Library

Google Scholar

[139]

Schaffer, J. D., Caruana, R. A., Eshelman, L. J., and Das, R. 1989. A study of control parameters affecting online performance of genetic algorithms for function optimization. In Proceedings of the 3rd International Conference on Genetic Algorithms. 51--60.

Digital Library

Google Scholar

[140]

Shimodaira, H. 1997. Dcga: A diversity control oriented genetic algorithm. In Proceedings of the 2nd International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications. 444--449.

Crossref

Google Scholar

[141]

Singh, G. and Deb, K. 2006. Comparison of multi-modal optimization algorithms based on evolutionary algorithms. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. 1305--1312.

Digital Library

Google Scholar

[142]

Smit, S. K. and Eiben, A. E. 2009. Comparing parameter tuning methods for evolutionary algorithms. In Proceedings of the IEEE Congress on Evolutionary Computation. 399--406.

Digital Library

Google Scholar

[143]

Smith, J. E. and Fogarty, T. C. 1997. Operator and parameter adaptation in genetic algorithms. Soft Comput. 1, 2, 81--87.

Crossref

Google Scholar

[144]

Smith, R. E., Forrest, S., and Perelson, A. S. 1993. Searching for diverse, cooperative subpopulations with genetic algorithms. Evol. Comput. 1, 2, 127--149.

Digital Library

Google Scholar

[145]

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

Google Scholar

[146]

Soza, C., Becerra, R. L., Riff, M. C., and Coello Coello, C. A. 2011. Solving timetabling problems using a cultural algorithm. Appl. Soft Comput. 11, 1, 337--344.

Digital Library

Google Scholar

[147]

Spears, W. M. 1995. Adapting crossover in evolutionary algorithms. In Proceedings of the Evolutionary Programming Conference. 367--384.

Google Scholar

[148]

Srinivas, M. and Patnaik, L. M. 1994. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Trans. Syst. Man Cybernetics 24, 656--667.

Crossref

Google Scholar

[149]

Storch, T. 2004. On the choice of the population size. In Proceedings of the Genetic and Evolutionary Computation Conference. 748--760.

Crossref

Google Scholar

[150]

Storn, R. and Price, K. 1997. Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces. J. Global Optim. 11, 341--359.

Digital Library

Google Scholar

[151]

Talbi, E. G. 2002. A taxonomy of hybrid metaheuristics. J. Heuristics 8, 5, 541--564.

Digital Library

Google Scholar

[152]

Toffolo, A. and Benini, E. 2003. Genetic diversity as an objective in multi-objective evolutionary algorithms. Evol. Comput. 11, 2, 151--167.

Digital Library

Google Scholar

[153]

Tsujimura, Y. and Gen, M. 1998. Entropy-based genetic algorithm for solving tsp. In Proceedings of the 2nd International Conference on Knowledge-Based Intelligent Electronic Systems. 285--290.

Google Scholar

[154]

Tsutsui, S., Fujimoto, Y., and Ghosh, A. 1997a. Forking genetic algorithms: GAs with search space division schemes. Evol. Comput. 5, 1, 61--80.

Digital Library

Google Scholar

[155]

Tsutsui, S., Ghosh, A., Corne, D., and Fujimoto, Y. 1997b. A real coded genetic algorithm with an explorer and an exploiter populations. In Proceedings of the 7th International Conference on Genetic Algorithms. 238--245.

Google Scholar

[156]

Ursem, R. 2000. Multinational GAs: Multimodal optimization techniques in dynamic environments. In Proceedings of the 2nd Genetic and Evolutionary Computation Conference. 19--26.

Google Scholar

[157]

Ursem, R. 2002. Diversity-guided evolutionary algorithms. In Proceedings of Parallel Problem Solving from Nature, Lecture Notes in Computer Science, vol. 2439, Springer, 462--471.

Digital Library

Google Scholar

[158]

Wang, Y., Cai, Z., and Zhang, Q. 2012. Enhancing the search ability of differential evolution through orthogonal crossover. Inform. Sci. 185, 1, 153--177.

Digital Library

Google Scholar

[159]

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

Google Scholar

[160]

Whitley, D., Mathias, K., and Fitzhorn, P. 1991. Delta coding: An iterative search strategy for genetic algorithms. In Proceedings of the 4th International Conference on Genetic Algorithms. 77--84.

Google Scholar

[161]

Whitley, D. and Starkweather, D. 1990. Genitor-ii: A distributed genetic algorithm. J. Exp. Theor. Artif. Intell. 2, 3, 189--214.

Digital Library

Google Scholar

[162]

Wineberg, M. and Oppacher, F. 2003. Distance between populations. In Proceedings of the International Conference on Genetic and Evolutionary Computation. 1481--1492.

Digital Library

Google Scholar

[163]

Wong, Y.-Y., Lee, K.-H., Leung, K.-S., and Ho, C.-W. 2003. A novel approach in parameter adaptation and diversity maintenance for genetic algorithms. Soft Comput. 7, 506--515.

Digital Library

Google Scholar

[164]

Yang, S. 2008. Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evol. Comput. 16, 3, 385--416.

Digital Library

Google Scholar

[165]

Yao, X., Liu, Y., and Lin, G. 1999. Evolutionary programming made faster. IEEE Trans. Evol. Comput. 3, 2, 82--102.

Digital Library

Google Scholar

[166]

Yin, X. and Germay, N. 1993. A fast genetic algorithm with sharing scheme using cluster analysis method in multi-modal function optimization. In Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms. 450--457.

Google Scholar

[167]

Yu, E. L. and Suganthan, P. N. 2010. Ensemble of niching algorithms. Inform. Sci. 180, 15, 2815--2833.

Digital Library

Google Scholar

[168]

Yuen, S. Y. and Chow, C. K. 2009. A genetic algorithm that adaptively mutates and never revisits. IEEE Trans. Evol. Comput. 13, 2, 454--472.

Digital Library

Google Scholar

[169]

Zhang, J. and Sanderson, A. C. 2009. Jade: Adaptive differential evolution with optional external archive. IEEE Trans. Evol. Comput. 13, 5, 945--957.

Digital Library

Google Scholar

[170]

Zhao, X. 2011. Simulated annealing algorithm with adaptive neighborhood. Appl. Soft Comput. 11, 2, 1827--1836.

Digital Library

Google Scholar

[171]

Zielinski, K., Weitkemper, P., Laur, R., and Kammeyer, K.-D. 2009. Optimization of power allocation for interference cancellation with particle swarm optimization. IEEE Trans. Evol. Comput. 8, 2, 128--150.

Digital Library

Google Scholar

[172]

Zitzler, E., Deb, K., and Thiele, L. 2000. Comparison of multiobjective evolutionary algorithms: Empirical results. Evol. Comput. 8, 2, 173--195.

Digital Library

Google Scholar

[173]

Zitzler, E., Laumanns, M., and Thiele, L. 2002. Spea2: Improving the strength pareto evolutionary algorithm for multiobjective optimization. Evol. Meth. Design: Optim. Control, 95--100.

Google Scholar

[174]

Zitzler, E. and Thiele, L. 1999. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach. IEEE Trans. Evol. Comput. 3, 4, 257--271.

Digital Library

Google Scholar

Cited By

View all

Turner IBamber NAndrews JPelletier N(2025)Systematic review of the life cycle optimization literature, and recommendations for performance of life cycle optimization studiesRenewable and Sustainable Energy Reviews10.1016/j.rser.2024.115058208(115058)Online publication date: Feb-2025
https://doi.org/10.1016/j.rser.2024.115058
Yang YXiang H(2025)A New Analysis Framework for Solving Multiple Frequencies and Solutions of Nonlinear Piezoelectric Energy HarvestersCommunications in Nonlinear Science and Numerical Simulation10.1016/j.cnsns.2024.108433140(108433)Online publication date: Jan-2025
https://doi.org/10.1016/j.cnsns.2024.108433
Takahama TSakai S(2024)Adaptive Parameter Control Using Search State Estimation and Extreme Individuals for Differential EvolutionProceedings of the ISCIE International Symposium on Stochastic Systems Theory and its Applications10.5687/sss.2024.602024(60-67)Online publication date: 1-Apr-2024
https://doi.org/10.5687/sss.2024.60
Show More Cited By

Index Terms

Exploration and exploitation in evolutionary algorithms: A survey
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction

Recommendations

Constrained differential evolution with multiobjective sorting mutation operators for constrained optimization

The proposed constrained differential evolution framework uses nondominated sorting mutation operator based on fitness and diversity information for constrained optimization. This study proposes a new constraint differential evolution framework.Parents ...
Analysis of exploration and exploitation in evolutionary algorithms by ancestry trees

This paper introduces an ancestry tree-based approach for exploration and exploitation analysis. The approach introduces a data structure to record the evolution history of a population and a number of exploration and exploitation metrics. Such an ...
Analysis of Some Mating and Collaboration Strategies in Evolutionary Algorithms
SYNASC '08: Proceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

The selection of mates in an evolutionary algorithm cansignificantly influence the exploration and the exploitationabilities of the search process. Currently there are severalstrategies to guide the mate selection or to restrict the matingpool. The aim ...

Reviews

Reviewer: Petrica C. Pop

In this survey paper, the authors tackle an important issue concerning the solution of an optimization problem using search. The paper revisits almost 100 papers in connection with exploration and exploitation in evolutionary algorithms (EAs). The paper addresses the following issues: How exploration and exploitation can be achieved in EAs; When and how to control exploration and exploitation; and How to balance exploration and exploitation in situations driven by diversity. It is commonly accepted that "exploration and exploitation in EAs is achieved by selection, mutation, and crossover," but it is difficult to distinguish between exploration and exploitation within these processes. Until now, it seemed like achieving a good balance between exploration and exploitation required proper settings for control parameters and the effective representation of individuals. Due to existing experimental studies, exploration and exploitation should be controlled online and balanced during the run. The authors classify different diversity measures at three levels: genotype, phenotype, and the composite measure. The surveyed genotype measures are based on difference, distance, entropy, probability, and history. The phenotypic diversity measures are based on difference, distance, entropy, and probability. The authors also present different techniques for maintaining the diversity of the population: non-niching approaches (those based on population, selection, crossover, and mutation, as well as a hybrid method) and niching approaches (those based on fitness, replacement, and preservation, as well as a hybrid method). The paper identifies other techniques for achieving exploration and exploitation through diversity control, diversity learning, and direct approaches. The paper ends with suggestions for important future research directions. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM Computing Surveys Volume 45, Issue 3

June 2013

575 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/2480741

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 July 2013

Accepted: 01 March 2012

Revised: 01 January 2012

Received: 01 September 2011

Published in CSUR Volume 45, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

967
Total Citations
View Citations
5,384
Total Downloads

Downloads (Last 12 months)491
Downloads (Last 6 weeks)57

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Turner IBamber NAndrews JPelletier N(2025)Systematic review of the life cycle optimization literature, and recommendations for performance of life cycle optimization studiesRenewable and Sustainable Energy Reviews10.1016/j.rser.2024.115058208(115058)Online publication date: Feb-2025
https://doi.org/10.1016/j.rser.2024.115058
Yang YXiang H(2025)A New Analysis Framework for Solving Multiple Frequencies and Solutions of Nonlinear Piezoelectric Energy HarvestersCommunications in Nonlinear Science and Numerical Simulation10.1016/j.cnsns.2024.108433140(108433)Online publication date: Jan-2025
https://doi.org/10.1016/j.cnsns.2024.108433
Takahama TSakai S(2024)Adaptive Parameter Control Using Search State Estimation and Extreme Individuals for Differential EvolutionProceedings of the ISCIE International Symposium on Stochastic Systems Theory and its Applications10.5687/sss.2024.602024(60-67)Online publication date: 1-Apr-2024
https://doi.org/10.5687/sss.2024.60
Jiao RZou F(2024)Quantum-Inspired Genetic Algorithm for Workforce Scheduling in Supply Chain and Logistics OperationsQuantum Computing and Supply Chain Management10.4018/979-8-3693-4107-0.ch023(376-394)Online publication date: 30-Jun-2024
https://doi.org/10.4018/979-8-3693-4107-0.ch023
AL-HAJJ RM. Fouad MZeki M(2024)Evolutionary optimization framework to train multilayer perceptrons for engineering applicationsMathematical Biosciences and Engineering10.3934/mbe.202413221:2(2970-2990)Online publication date: 2024
https://doi.org/10.3934/mbe.2024132
Wang SLi SYu H(2024)A power generation accumulation-based adaptive chaotic differential evolution algorithm for wind turbine placement problemsElectronic Research Archive10.3934/era.202421232:7(4659-4683)Online publication date: 2024
https://doi.org/10.3934/era.2024212
Guan JYu FWu HChen YXiang ZXia XLi Y(2024)Dynamic allocation of opposition-based learning in differential evolution for multi-role individualsElectronic Research Archive10.3934/era.202414932:5(3241-3274)Online publication date: 2024
https://doi.org/10.3934/era.2024149
Hodashinsky I(2024)Population Diversity Management of Swallow Swarm Optimization Algorithm for Fuzzy Classification ProblemAutomatic Documentation and Mathematical Linguistics10.3103/S000510552470011058:3(182-187)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.3103/S0005105524700110
Mezza AGiampiccolo RDe Sena EBernardini A(2024)Data-driven room acoustic modeling via differentiable feedback delay networks with learnable delay linesEURASIP Journal on Audio, Speech, and Music Processing10.1186/s13636-024-00371-52024:1Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1186/s13636-024-00371-5
Son PTrinh N(2024)Development of Novel Hybrid Multi-Verse Optimizer with Sine Cosine Algorithm for Better Global OptimizationInternational Journal of Computational Intelligence and Applications10.1142/S146902682450002023:02Online publication date: 14-Mar-2024
https://doi.org/10.1142/S1469026824500020
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Constrained differential evolution with multiobjective sorting mutation operators for constrained optimization

Analysis of exploration and exploitation in evolutionary algorithms by ancestry trees

Analysis of Some Mating and Collaboration Strategies in Evolutionary Algorithms

Reviews

Access critical reviews of Computing literature here