A survey on algorithm adaptation in evolutionary computation

Abstract

Evolutionary computation (EC) is one of the fastest growing areas in computer science that solves intractable optimization problems by emulating biologic evolution and organizational behave iors in nature. To design an EC algorithm, one needs to determine a set of algorithmic configurations like operator selections and parameter settings. How to design an effective and efficient adaptation scheme for adjusting the configurations of EC algorithms has become a significant and promising research topic in the EC research community. This paper intends to provide a comprehensive survey on this rapidly growing field. We present a classification of adaptive EC (AEC) algorithms from the perspective of how an adaptation scheme is designed, involving the adaptation objects, adaptation evidences, and adaptation methods. In particular, by analyzing the population distribution characteristics of EC algorithms, we discuss why and how the evolutionary state information of EC can be estimated and utilized for designing effective EC adaptation schemes. Two AEC algorithms using the idea of evolutionary state estimation, including the clustering-based adaptive genetic algorithm and the adaptive particle swarm optimization algorithm are presented in detail. Some potential directions for the research of AECs are also discussed in this paper.

Keywords

evolutionary algorithm (EA) / evolutionary computation (EC) / algorithm adaptation / parameter control

References

[1] Eiben A E, Smith J E. Introduction to Evolutionary Computation. Springer, 2003

[2] De Jong K A. An analysis of the behaviour of a class of genetic adaptive systems. Dissertation for the Doctoral Degree. Ann Arbor, MI: University of Michigan, 1975

[3] Bäack T, Hammel U, Schwefel H. Evolutionary computation: Comments on the history and current state. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 3-17

[4] Hesser J, Mäanner R. Towards an optimal mutation probability for genetic algorithms. Lecture Notes in Computer Science, 1991, 496: 23-32

[5] Schwefel H P. Numerical Optimisation of Computer Models. New York: Wiley, 1981

[6] BäackT, Fogel D B, Michalewicz Z. Handbook of Evolutionary Computation. Bristol: Institute of Physics Publishing and New York: Oxford University Press, 1997

[7] Goldberg D E. Genetic Algorithms in Search, Optimization and Machine Learning. eading, MA: Addison Wesley, 1989

[8] Stephens C R, Garćıa Olmedo I, Mora Vargas J, Waelbroeck H. Self-adaptation in evolving systems. Artificial Life, 1998, 4(2): 183-201

[9] Zhan Z H, Xiao J, Zhang J, Chen W. Adaptive control of acceleration coefficients for particle swarm optimization based on clustering analysis. In: Proceedings of IEEE Congress on Evolutionary Computation. 2007, 3276-3282

[10] Eiben A E, Hinterding R, Michalewicz Z. Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 1999, 3(2): 124-141

[11] Zhang J, Chung H S H, Lo W L. Clustering-based adaptive crossover and mutation probabilities for genetic algorithms. IEEE Transactions on Evolutionary Computation, 2007, 11(3): 326-335

[12] Zhan Z H, Zhang J, Li Y, Chung H S H. Adaptive particle swarm optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2009, 39(6): 1362-1381

[13] Srinivas M, Patnaik L M. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 1994, 24(4): 656-667

[14] Dai C H, Zhu Y F, Chen W R. Adaptive probabilities of crossover and mutation in genetic algorithms based on cloud model. In: Proceedings of IEEE Information Theory Workshop. 2006, 710-713

[15] Shi Y, Eberhart R. A modified particle swarm optimizer. In: Proceedings of the 1998 IEEE International Conference on Evolutionary Computation. 1998, 69-73

[16] Cai Z, Huang H, Qin Y, Ma X. Ant colony optimization based on adaptive volatility rate of pheromone trail. International Journal of Communications, Network and System Sciences, 2009, (2): 792-796

[17] Hao Z, Huang H, Qin Y, Cai R. An ACO algorithm with adaptive volatility rate of pheromone trail. In: Proceedings of International Conference of Computational Science. 2007, 1167-1170

[18] Mezura-Montes E, Veléazquez-Reyes J, Coello C A C. A comparative study of differential evolution variants for global optimization. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. 2006, 485-492

[19] Shi X H, Wan LM, Lee H P, Yang XW,Wang LM, Liang Y C. An improved genetic algorithm with variable population size and a PSO-GA based hybrid evolutionary algorithm. In:Proceedings of the 2nd International Conference on Machine Learning and Cybernetics. 2004, 1735-1740

[20] Tse S M, Liang Y, Leung K S, LeeK H, MokT S K. A memetic algorithm for multiple-drug cancer chemotherapy schedule optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2007, 37(1): 84-91

[21] Teng N S, Teo J, Hijazi M H A. Self-adaptive population sizing for a tune-free differential evolution. Soft Computing, 2009, 13(7): 709-724

[22] Teo J. Exploring dynamic self-adaptive populations in differential evolution. Soft Computing, 2006, 10(8): 673-686

[23] Tan K C, Lee T H, Khor E F. Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization. IEEE Transactions on Evolutionary Computation, 2001, 5(6): 565-588

[24] Kennedy J, Mendes R. Population structure and particle swarm performance. In: Proceedings of the 2002 Congress on Evolutionary Computation. 2002, 1671-1676

[25] Janson S, Middendorf M. A hierarchical particle swarm optimizer and its adaptive variant. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2005, 35(6): 1272-1282

[26] Montes de Oca M A, Stutzle T, Birattari M, Dorigo M. Frankenstein’s PSO a composite particle swarm optimization algorithm. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 1120-1132

[27] Ong Y S, Lim M H, Zhu N, Wong K W. Classification of adaptive memetic algorithms: A comparative study. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2006, 36(1): 141-152

[28] Zhang J, Chung H S H, Lo W L. Pseudocoevolutionary genetic algorithms for power electronic circuits optimization. IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, 2006, 36(4): 590-598

[29] Zhan Z H, Zhang J. Parallel particle swarm optimization with adaptive asynchronous migration strategy. Lecture Notes in Computer Science, 2009, 5574: 490-501

[30] Das S, Konar A, Chakraborty U K. Two improved differential evolution schemes for faster global search. In: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation. 2005, 991-998

[31] Merkle D, Middendorf M, Schmeck H. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 2002, 6(4): 333-346

[32] Zhang J, Sanderson A C. JADE: Adaptive differential evolution with optional external archive. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 945-958

[33] Ali M M, Töorn A. Population set based global optimization algorithms: Some modifications and numerical studies. Computers & Operations Research, 2004, 31(10): 1703-1725

[34] Shi Y, Eberhart R C. Fuzzy adaptive particle swarm optimization. In: Proceedings of the 2001 Congress on Evolutionary Computation. 2001, 101-106

[35] Zhu J, Zhao J, Li X. A new adaptive particle swarm optimization algorithm. In: Proceedings of the 2008 International Workshop on Modelling, Simulation and Optimization. 2008, 456-458

[36] Pappala V S, Erlich I. A new approach for solving the unit commitment problem by adaptive particle swarm optimization. In: Proceedings of Power and Energy Society General Meeting. 2008, 1-6

[37] Liu X P, Liu Y. Adaptive genetic algorithm based on population diversity. In: Proceedings of International Forum on Information Technology and Applications. 2009, 510-512

[38] Zhu K Q. A diversity-controlling adaptive genetic algorithm for the vehicle routing problem with time windows. In: Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence. 2003, 176-183

[39] Wang H F, Yang S X, Ip W H, Wang D W. Adaptive primal-dual genetic algorithms in dynamic environments. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2009, 39(6): 1348-1361

[40] Qian WY, Li A. Adaptive differential evolution algorithm for multiobjective optimization problems. Applied Mathematics and Computation, 2008, 201(1-2): 431-440

[41] Li X, Fu H, Zhang C. A self-adaptive particle swarm optimization algorithm. In: Proceedings of the 2008 International Conference on Computer Science and Software Engineering. 2008, 186-189

[42] Wang L, Kang Q, Xiao H, Wu Q D. A modified adaptive particle swarm optimization algorithm. In: Proceedings of IEEE International Conference on Industrial Technology. 2005, 209-214

[43] Nguyen Q H, Ong Y S, Lim M H. A probabilistic memetic framework. IEEE Transactions on Evolutionary Computation, 2009, 13(3): 604-623

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

[45] Wu Z, Zhou J. A self-adaptive particle swarm optimization algorithm with individual coefficients adjustment. In: Proceedings of the 2007 International Conference on Computational Intelligence and Security. 2007, 133-136

[46] Auger A, Hansen N. A restart CMA evolution strategy with increasing population size. In: Proceedings of the 2005 Congress on Evolutionary Computation. 2005, 1769-1776

[47] Igel C, Hansen N, Roth S. Covariance matrix adaptation for multi-objective optimization. Evolutionary Computation, 2007, 15(1): 1-28

[48] Shir O M, Bäack T. Niche radius adaptation in the CMA-ES niching algorithm. Lecture Notes in Computer Science, 2006, 4193: 142-151

[49] Suttorp T, Hansen N, Igel C. Efficient covariance matrix update for variable metric evolution strategies. Machine Learning, 2009, 75(2): 167-197

[50] Spears W M. Adapting crossover in evolutionary algorithms. In: Proceedings of the 4th Annual Conference on Evolutionary Programming. 1995

[51] Angeline P J, Fogel D B, Fogel L J. A comparison of selfadaptation methods for finite state machines in dynamic environments. In: Proceedings of the 5th Annual Conference on Evolutionary Programming. 1996

[52] Bäack T. The interaction of mutation rate, selection, and selfadaptation within a genetic algorithm. In: Proceedings of the 2nd Conference on Parallel Problem Solving from Nature. 1992, 85-94

[53] Hinterding R. Gaussian mutation and self-adaption in numeric genetic algorithms. In: Proceedings of the 2nd IEEE Conference on Evolutionary Computation. 1995, 384-389

[54] Qin A K, Huang V L, Suganthan P N. Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Transactions on Evolutionary Computation,2009, 13(2): 398-417

[55] Hao Z F, Cai R C, Huang H. An adaptive parameter control strategy for ACO. In: Proceedings of the 2006 International Conference on Machine Learning and Cybernetics. 2006, 203-206

[56] Zhan Z H, Zhang J. Self-adaptive differential evolution based on PSO learning strategy. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation. 2010, 39-46

[57] Herrera F, Lozano M. Adaptive genetic operators based on coevolution with fuzzy behaviors. IEEE Transactions on Evolutionary Computation, 2001, 5(2): 149-165

[58] Yang L, Widyantoro D H, Ioerger T, Yen J. An entropybased adaptive genetic algorithm for learning classification rules. In: Proceedings of the 2001 Congress on Evolutionary Computation. 2001, 790-796

[59] Xing Y, Chen Z, Sun J, Hu L. An improved adaptive genetic algorithm for job-shop scheduling problem. In: Proceedings of the 3rd International Conference on Natural Computation. 2007, 287-291

[60] Li Y, Zhou S. Adaptive ACO for complicated optimization problems. In: Proceedings of the 2009 International Forum on Information Technology and Applications. 2009, 15-18

[61] Ahmadi P, Hajabdollahi H, Dincer I. Cost and entropy generation minimization of a cross-flow plate fin heat exchanger using multi-objective genetic algorithm. Journal of Heat Transfer — Transactions of the ASME, 2011, 133(2): 021801

[62] Fu P, Luo K. Clustering analysis of immune-genetic algorithm based on information entropy. Computer Engineering, 2008, 34(6): 227-232 (in Chinese)

[63] Wang J, Liu B. Advanced genetic algorithm based twodimensional fuzzy entropy image segmentation algorithm. Science & Technology Review, 2010, 28(20): 43-47

[64] Xue F, Wang C-g, Mu F. Genetic and ant colony collaborative optimization algorithm based on information entropy and chaos theory. Control and Decision, 2011, 26(1): 44-48 (in Chinese)

[65] Shen Z, Hao Y, Li K. Application research of an adaptive genetic algorithms based on information entropy in path planning. In: Proceedings of the 2010 International Conference on Information and Automation. 2010

[66] Li Z, Wang Y, Yu J, Zhang Y, Li X. A novel cloud-based fuzzy self-adaptive ant colony system. In: Proceedings of the 4th International Conference on Natural Computation. 2008, 460-465

[67] Xiong W, Wang C. Feature selection: A hybrid approach based on self-adaptive ant colony and support vector machine. In: Proceedings of the 2008 International Conference on Computer Science and Software Engineering. 2008, 751-754

[68] Yu W J, Hu X M, Zhang J, Huang R. Self-adaptive ant colony system for the traveling salesman problem. In: Proceedings of IEEE International Conference on Systems, Man and Cybernetics. 2009, 1399-1404

[69] Favuzza S, Graditi G, Sanseverino E R. Adaptive and dynamic ant colony search algorithm for optimal distribution systems reinforcement strategy. Applied Intelligence, 2006, 24(1): 31-42

[70] Wu H, Shi Y F, Jin X, Wang G, Dong H. A fuzzy adaptive particle swarm optimization for RNA secondary structure prediction. In: Proceedings of the 2011 International Conference on Information Science and Technology. 2011, 1390-1393

[71] Chang W, Luo X, Yu H. A fuzzy adaptive particle swarm optimization for long-term optimal scheduling of cascaded hydropower station. In: Proceedings of IEEE/PES Power Systems Conference and Exposition. 2009, 1-5

[72] Tou J T, Gonzalez R C. Pattern Recognition Principles. Reading, MA: Addison-Wesley, 1974

[73] Duda R O, Hart P E, Stork D G. Pattern Classification. New York: Wiley, 2001

[74] Zhang J, Zhan Z H, Lin Y, Chen N, Gong Y J, Zhong J H, Chung H S H, Li Y, Shi Y H. Evolutionary computation meets machine learning: A survey. IEEE Computational Intelligence Magazine, 2011, 6(4): 68-75

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg