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.

Key words： 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