基于聚类排序选择方法的进化算法

计算机科学与探索 ›› 2008, Vol. 2 ›› Issue (3): 321-329.

基于聚类排序选择方法的进化算法

徐开阔¹,唐常杰¹⁺,刘胤田²,张天庆¹,段磊¹

1. 四川大学计算机学院，成都 610065
2. 四川大学数学学院，成都 610064

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-06-20 发布日期:2008-06-20
通讯作者: 徐开阔

Clustering-ranking selection method for evolutionary algorithm

XU Kaikuo¹, TANG Changjie¹⁺, LIU Yintian², ZHANG Tianqing¹, DUAN Lei¹

1. School of Computer Science， Sichuan University， Chengdu 610065， China
2. School of Mathematics， Sichuan University， Chengdu 610064， China

Received:1900-01-01 Revised:1900-01-01 Online:2008-06-20 Published:2008-06-20
Contact: XU Kaikuo

摘要/Abstract

摘要： 为提高进化算法的效率，提出了聚类排序选择方法。主要工作有：（1）提出了新的种群内个体相似度度量，并使用种群所包含不同簇的数量来描述和度量种群的多样性；（2）为解决早熟问题提出了新的基于种群聚类和排序选择的聚类-排序选择方法；（3）导出了选择压力-种群多样性（SP-PD）方程，该方程能描述进化过程中选择压力随种群多样性变化的规律。在基于全面学习粒子群算法环境中作了详实的实验，对16个多峰函数进行了优化。实验结果表明，在10维和30维条件下，在15个函数优化中，新方法明显优于指数排序选择方法，最高能使精度提高4个数量级。

关键词: 聚类排序选择, 进化计算, 指数排序选择, 早熟问题, 基于全面学习的粒子群算法

Abstract: To improve the efficiency of evolutionary algorithms， this paper proposes a novel selection method， i.e. clustering-ranking selection. The main contributions include：（1）Proposes a measurement of the similarity between individuals in a population and uses the number of clusters for a population to measure the population diversity of this population. （2）Proposes the new clustering-ranking selection method to solve the premature convergence problem. （3）Derives the Selection Pressure-Population Diversity（SP-PD） equation， which describes how selection pressure adapts to the variation of population diversity. Experiments apply this selection method to the Comprehensive Learning Particle Swarm Optimization（CLPSO） on optimizing multimodal functions and compare the performance of the proposed selection scheme with that of the canonical exponential ranking scheme. Experiment results demonstrate that the proposed selection method outperforms canonical exponential ranking on fifteen of sixteen-benchmark functions for both 10-D and 30-D problems， which could improve the precision by at most four orders of magnitude.

Key words: clustering-ranking selection, evolutionary algorithms, exponential ranking selection, premature convergence problem, Comprehensive Learning Particle Swarm Optimization （CLPSO）

徐开阔1 ,唐常杰1+ ,刘胤田2 ,张天庆1 ,段磊1 . 基于聚类排序选择方法的进化算法[J]. 计算机科学与探索, 2008, 2(3): 321-329.

XU Kaikuo¹, TANG Changjie¹⁺, LIU Yintian², ZHANG Tianqing¹, DUAN Lei¹. Clustering-ranking selection method for evolutionary algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2008, 2(3): 321-329.