DOI: 10.3724/SP.J.1001.2009.03496

Journal of Software (软件学报) 2009/20:11 PP.2925-2938

M-Elite Coevolutionary Algorithm for Numerical Optimization

The M-elite coevolutionary algorithm (MECA) is proposed for high-dimensional unconstrained numerical optimization problems based on the concept of coevolutionary algorithm and elitist strategy. In the MECA, the individuals with high fitness, called elite population, is considered to play dominant roles in the evolutionary process. The whole population is divided into two subpopulations which are elite population composed of M elites and common population including other individuals, and team members are selected to form M teams by M elites acting as the cores of the M teams (named as core elites) respectively. If the team member selected is another elite individual, it will exchange information with the core elite with the cooperating operation defined in the paper; If the team member is chosen from the common population, it will be led by the core elite with the leading operation. The cooperating and leading operation above are defined by different combinations of several crossover operators or mutation operators. The algorithm is proved to converge to the global optimization solution with probability one. Tests on 15 benchmark problems show that the algorithm can find the global optimal solution or near-optimal solution for most problems tested. Compared with three existing algorithms, MECA achieves an improved accuracy with the same number of function evaluations. Meanwhile, the runtime of MECA is less, even compared with the standard genetic algorithm with the same parameter setting. Moreover, the parameters of the MECA are analyzed in experiments and the results show that MECA is insensitive to parameters and easy to use.

Key words:unconstrained optimization problem (UOP),numerical optimization,elitist strategy,evolutionary algorithm,coevolutionary algorithm

ReleaseDate:2014-07-21 14:51:54

Funds:Supported by the National Natural Science Foundation of China under Grant Nos.60703107, 60703108, 60703109, 60702062 the National High-Tech Research and Development Plan of China under Grant Nos.2006AA01Z107, 2007AA12Z136, 2007AA12Z223 the National Basic Research Program of China under Grant No.2006CB705700 the Program for Cheung Kong Scholars and Innovative Research Team in University of China under Grant No.IRT0645

[1] Yao X, Liu Y, Lin GM. Evolutionary programming made faster. IEEE Trans. on Evolutionary Computation, 1999,3(2):82-102.

[2] Leung YW, Wang YP. An orthogonal genetic algorithm with quantization for global numerical optimization. IEEE Trans. on Evolutionary Computation, 2001,5(1):41-53.

[3] Zhang L, Zhang B. Good point set based genetic algorithm. Chinese Journal of Computers, 2001,24(9):917-922 (in Chinese with English abstract). 张铃,张钹.佳点集遗传算法.计算机学报,2001,24(9):917-922.

[4] Potter MA, De Jong KA. A cooperative coevolutionary approach to function optimization. In: Davidor Y, Schwefel HP, Männer R, eds. Proc. of the Parallel Problem Solving from Nature—PPSN III, Int’l Conf. on Evolutionary Computation. LNCS 866, Berlin: Springer-Verlag, 1994. 249-257.

[5] van den Bergh F, Engelbrecht AP. A cooperative approach to particle swarm optimization. IEEE Trans. on Evolutionary Computation, 2004,8(3):225-239.

[6] Cao XB, Luo WJ, Wang XF. A co-evolution pattern based on ecological population competition model. Journal of Software, 2001, 12(4):556-562 (in Chinese with English abstract). 曹先彬,罗文坚,王煦法.基于生态种群竞争模型的协同进化.软件学报,2001,12(4):556-562. view_abstract.aspx?file_no=20010410&flag=1

[7] Hu SC, Xu XF, Li XY. A virus coevolution genetic algorithm for project optimization scheduling. Journal of Software, 2004, 15(1):49-57 (in Chinese with English abstract). 胡仕成,徐晓飞,李向阳.项目优化调度的病毒协同进化遗传算法.软件学报,2004,15(1):49-57. 15/49.htm

[8] Tan KC, Yang YJ, Goh CK. A distributed cooperative coevolutionary algorithm for multiobjective optimization. IEEE Trans. on Evolutionary Computation, 2006,10(5):527-549.

[9] Liu J, Zhong WC, Jiao LC. An Organizational Evolutionary Algorithm for Numerical Optimization. IEEE Trans. on Systems, Man, and Cybernetics—Part B: Cybernetics, 2007,37(4):1052-1064.

[10] Ahn CW, Ramakrishna RS. Elitism-Based compact genetic algorithms. IEEE Trans. on Evolutionary Computation, 2003,7(4): 367-385.