Choosing selection pressure for wide-gap problems

被引：9
作者：
Chen, Tianshi [3 ]
He, Jun [2 ]
Chen, Guoliang [3 ]
Yao, Xin [1 ,3 ]
机构：
[1] Univ Birmingham, Sch Comp Sci, CERCIA, Birmingham B15 2TT, W Midlands, England
[2] Univ Wales, Dept Comp Sci, Aberystwyth SY23 3DB, Ceredigion, Wales
[3] Univ Sci & Technol China, Sch Comp Sci & Engn, NICAL, Hefei 230027, Anhui, Peoples R China
来源：
THEORETICAL COMPUTER SCIENCE | 2010年 / 411卷 / 06期
基金：
中国国家自然科学基金;
关键词：
Evolutionary algorithm; Selection pressure; First hitting time; Markov chain; Evolutionary computation theory; 1ST HITTING TIME; EVOLUTIONARY ALGORITHMS; OPTIMIZATION; POPULATION; COMPLEXITY; DRIFT;
D O I：
10.1016/j.tcs.2009.12.014
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
To exploit an evolutionary algorithm's performance to the full extent, the selection scheme should be chosen carefully. Empirically, it is commonly acknowledged that low selection pressure can prevent an evolutionary algorithm from premature convergence, and is thereby more suitable for wide-gap problems. However, there are few theoretical time complexity studies that actually give the conditions under which a high or a low selection pressure is better. In this paper, we provide a rigorous time complexity analysis showing that low selection pressure is better for the wide-gap problems with two optima. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码：926 / 934
页数：9
相关论文
共 24 条
[1]   The exploration/exploitation tradeoff in dynamic cellular genetic algorithms [J].
Alba, E ;
Dorronsoro, B .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2005, 9 (02) :126-142
[2]  
[Anonymous], 1991, Foundations of Genetic Algorithms
[3]  
Back T., 1994, Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence (Cat. No.94TH0650-2), P57, DOI 10.1109/ICEC.1994.350042
[4]  
Blickle T., 1995, A Comparison of Selection Schemes used in Genetic Algorithms
[5]   A New Approach for Analyzing Average Time Complexity of Population-Based Evolutionary Algorithms on Unimodal Problems [J].
Chen, Tianshi ;
He, Jun ;
Sun, Guangzhong ;
Chen, Guoliang ;
Yao, Xin .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 2009, 39 (05) :1092-1106
[6]   On the analysis of the (1+1) evolutionary algorithm [J].
Droste, S ;
Jansen, T ;
Wegener, I .
THEORETICAL COMPUTER SCIENCE, 2002, 276 (1-2) :51-81
[7]   Rigorous Hitting Times for Binary Mutations [J].
Garnier, Josselin ;
Kallel, Leila ;
Schoenauer, Marc .
EVOLUTIONARY COMPUTATION, 1999, 7 (02) :173-203
[8]   Towards an analytic framework for analysing the computation time of evolutionary algorithms [J].
He, J ;
Yao, X .
ARTIFICIAL INTELLIGENCE, 2003, 145 (1-2) :59-97
[9]   A comparative study of three evolutionary algorithms incorporating different amounts of domain knowledge for node covering problem [J].
He, J ;
Yao, X ;
Li, J .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS, 2005, 35 (02) :266-271
[10]   From an individual to a population: An analysis of the first hitting time of population-based evolutionary algorithms [J].
He, J ;
Yao, X .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2002, 6 (05) :495-511
123