摘要
怎样保证朝Pareto最优解的方向搜索和如何获得均匀分布且范围广泛的非支配解是多目标进化算法(MOEA)设计时的两个关键问题,它们很大程度上取决于适应度赋值和外部种群维护这两个重要部分.提出了一种基于最小生成树的多目标进化算法(MST_MOEA).在考虑了个体间支配关系的基础上,利用个体与非支配集的距离和不同等级个体的树聚集密度来对适应度赋值;在外部种群的非支配解个数超过规定的种群规模时,用树的度数和树聚集密度对其进行修剪.将其应用于不同维数下9个测试函数,并与NSGA-II,SPEA2进行对比,结果证实了算法良好的收敛性和分布性.
Fitness assignment and external population maintenance are the two critical parts of multi-objective evolutionary algorithms （MOEA）. They affect the two basic objectives （convergence and distribution） of MOEA design to a great extent. It is difficult for many existing MOEAs to obtain satisfying results. In this paper, a multi-objective evolutionary algorithm based on minimum spanning tree （MST MOEA） is proposed. In the algorithm, a density estimation metric, tree crowding density, is defined. And on the basis of Pareto dominance relationship, the algorithm assigns fitness using two factors, the distance between the current individual and non-dominated solutions set and the tree crowding density of different rank individual. Moreover, if the size of non-dominated solutions set exceeds that of population, the degree information of solution combined with tree crowding density is employed to truncate population. Particularly, the solutions which have higher degree will be eliminated, for the degree in minimum spanning tree represents not only the density of solution, but the situation in population to a certain extent. Finally, the proposed algorithm is applied to nine test functions on different dimensions and has an extensively comparative study with NSGA-II and SPEA2. Experimental results demonstrate that the proposed algorithm indicates good performance in convergence and distribution.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2009年第5期803-813,共11页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60773047
90104021)
湖南省自然科学基金项目(05JJ30125)
湖南省教育厅重点科研基金项目(06A074)
湘潭大学校级基金项目(08XZX23)~~
关键词
树聚集密度
适应度赋值
种群维护
最小生成树
多目标进化算法
tree crowding density
fitness assignment
population maintenance
minimum spanning tree
multi-objective evolutionary algorithm
