一种协调勘探和开采的遗传算法:收敛性及性能分析  

A Genetic Algorithm by Coordinating Exploration and Exploitation——Convergence Properties and Performance Analyses

作　　者：江瑞[1] 罗予频[1] 胡东成[1] 司徒国业[2] 

机构地区：[1]清华大学自动化系,北京100084 [2]香港科技大学物理系

出　　处：《计算机学报》2001年第12期1233-1241,共9页Chinese Journal of Computers

摘　　要：提出了一种新的遗传算法结构 .在该结构中 ,每一代的新种群由保留种群、繁殖种群和随机种群三部分组成 ,而它们的相对数量则由不同的参数进行控制 ,这体现了该算法在运行过程中对搜索空间勘探和开采操作的协调和权衡 .通过把该算法建模为齐次的有限 Markov链 ,该文证明了该算法具有全局收敛性 .对试验数据的分析表明 ,该算法能够有效协调算法对问题解空间的勘探和开采操作 ,因而在处理复杂问题时表现出较高的性能 .A new kind of genetic algorithm architecture is brought forward in this paper. The simple philosophy underlying the new algorithm is to divide the population of a genetic algorithm into different parts and attach meaning to each sub-population to enable efficient tuning of the importance of exploration and exploitation during evolution by controlling the sizes of the sub-populations. In the algorithm architecture, the new population in each generation is created and constituted by three sub-populations: a preserved part, a reproduced part and a randomized part. The number of the preserved individuals measures the attention to exploitation; the number of the reproduced individuals measures the attention to the effect of various genetic operations while exploring the solution space of the given problem; the number of randomly generated individuals measures the attention paid to the effect of getting trapped in local optima. Corresponding parameters are introduced into the architecture to control the relative amount of each sub-population and through this way, the algorithm can achieve the coordination and balance between the exploration of the solution space of given problem and the exploitation of the information in past search, thus getting high performances while optimizing complex multi-modal functions. By treating the collection of individuals in each generation as a state and modeling the algorithm as a homogeneous finite Markov chain, it is proven that the new algorithm can guarantee the convergence towards the global optimum of the problem at hand. Experiments concerning various famous benchmark functions are designed to test the performance of the new algorithm and data analysis using a quite extensive set of evaluating criteria are made and compared with several traditional genetic algorithms. Results show strong evidence that since the new genetic algorithm can balance the exploration and exploitation to the problem's solution space effectively during evolution, it can get high performance while dealing

关 键 词：遗优算法 有限Markov链 收敛性 性能分析 

分 类 号：O242.23[理学—计算数学]