유전 알고리즘의 조기수렴 저감을 위한 연산자 소인방법 연구 = On Sweeping Operators for Reducing Premature Convergence of Genetic Algorithms

다국어 초록 (Multilingual Abstract)

GA (Genetic Algorithms) are efficient for searching for global optima but may have some problems such as premature convergence, convergence to local extremum and divergence. These phenomena are related to the evolutionary operators. As population diversity converges to low value, the search ability of a GA decreases and premature convergence or converging to local extremum may occur but population diversity converges to high value, then genetic algorithm may diverge. To guarantee that genetic algorithms converge to the global optima, the genetic operators should be chosen properly. In this paper, we analyze the effects of the selection operator, crossover operator, and mutation operator on convergence properties, and propose the sweeping method of mutation probability and elitist propagation rate to maintain the diversity of the GA's population for getting out of the premature convergence. Results of simulation studies verify the feasibility of using these sweeping operators to avoid premature convergence and convergence to local extrema.

참고문헌 (Reference)

1 이대우, "유전 이론을 이용한 위성 임무 스케줄링 알고리즘의 제어상수에 따른 적합도 변화 연구" 제어·로봇·시스템학회 16 (16): 572-578, 2010

2 G. Rudolph, "Self adaptive mutations lead to premature convergence" 5 (5): 410-414, 2001

3 M. Affenzeller, "SASEGASA: An evolutionary algorithm for retarding premature convergence by self-adaptive selection pressure steering, Computational Methods in Neural Modelling" Springer 2686 : 438-445, 2003

4 문병로, "Raising Mutation Rate in the Context of Hybrid Genetic Algorithms" ACM 157-158, 2011

5 P. N. Suganthan, "Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization" Natural Computing Laboratory, Department of Computer Science, National Chiao Tung University 2005

6 M. Rocha, "Preventing premature convergence to local optima in genetic algorithms via random offspring generation" 127-136, 1999

7 H. Wang, "Opposition-based particle swarm algorithm with cauchy mutation" 4750-4756, 2007

8 B. Chakraborty, "On the use of genetic algorithm with elitism in robust and nonparametric multivariate analysis" 32 (32): 13-27, 2003

9 H.-K. Lee, "On parameter selection for reducing premature convergence of genetic algorithms" 214-219, 2010

10 S.-H. Bae, "Mutation rates in the context of hybrid genetic algorithms" 381-382, 2004

11 W. Cedeno, "Multi-niche crowding in genetic algorithms and its application to the assembly of DNA restriction-fragments" 2 : 321-345, 1995

12 D. Goldberg, "Genetic algorithms with sharing for multimodal function optimization" 41-49, 1987

13 T. Jones, "Fitness distance correlation as a measure of problem difficulty for genetic algorithms" 184-192, 1995

14 S. Nolfi, "Evolutionary Robotics" MIT Press 2000

15 H.-K. Lee, "Convergence properties of genetic algorithms" 172-176, 2004

16 G. Rudolph, "Convergence analysis of canonical genetic algorithms" 5 (5): 96-101, 1994

17 M. Pelikan, "Bayesian optimization algorithm, population sizing, and time to convergence" 275-282, 2000

18 Y. Gao, "An upper bound on the convergence rates of canonical genetic algorithms" 5 : 1-9, 1998

19 J. Zhang, "An improved multi-objective adaptive niche genetic algorithm based on pareto front" 300-304, 2009

20 S. Nijssen, "An analysis of behavior of evolutionary algorithms on trap functions" 7 (7): 11-22, 2003

21 M. Srinivas, "Adaptive probabilities of crossover and mutation in genetic algorithms" 24 (24): 656-667, 1994

22 D. Beasley, "A sequential niche technique for multimodal function optimization" 1 (1): 101-125, 1993

23 D. E. Goldberg, "A practical schema theorem for genetic algorithm design and tuning" 328-335, 2001

24 Y. Zhang, "A novel niche genetic algorithm for multimodal optimization" 6 (6): 255-262, 2011