REVIEW ARTICLE

A survey on algorithm adaptation in evolutionary computation

  • Jun ZHANG ,
  • Wei-Neng CHEN ,
  • Zhi-Hui ZHAN ,
  • Wei-Jie YU ,
  • Yuan-Long LI ,
  • Ni CHEN ,
  • Qi ZHOU
Expand
  • Department of Computer Science, Sun Yat-sen University, Guangzhou 510275, China; Key Laboratory of Digital Life, Ministry of Education, Guangzhou 510275, China; Key Laboratory of Software Technology, Education Department of Guangdong Province, Guangzhou 510275, China

Received date: 14 Oct 2011

Accepted date: 27 Nov 2011

Published date: 05 Mar 2012

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg

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.

Cite this article

Jun ZHANG , Wei-Neng CHEN , Zhi-Hui ZHAN , Wei-Jie YU , Yuan-Long LI , Ni CHEN , Qi ZHOU . A survey on algorithm adaptation in evolutionary computation[J]. Frontiers of Electrical and Electronic Engineering, 2012 , 7(1) : 16 -31 . DOI: 10.1007/s11460-012-0192-0

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

Outlines

/