一种基于Hypervolume指标的自适应邻域多目标进化算法  

Adaptive Neighbor Multi-Objective Evolutionary Algorithm Based on Hypervolume Indicator

作　　者：郑金华[1] 李珂[1] 李密青[1] 文诗华[1] 

机构地区：[1]湘潭大学信息工程学院,湖南湘潭411105

出　　处：《计算机研究与发展》2012年第2期312-326,共15页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60773047);湖南省自然科学基金项目(09JJ6089)

摘　　要：通过定义反映个体之间邻近程度的指标(个体的树邻域包含关系),在考虑个体间支配关系的基础上,利用个体与其周边个体的树邻域密度进行适应度赋值;提出了一种2,3维情况下个体独立支配区域的Hypervolume指标的计算方法,该方法用于评价个体对群体的贡献时只需要1次计算(同类方法需要2次计算);当外部种群中非支配个体数目超过规定规模时,根据个体独立支配区域的Hypervolume指标的大小对其进行修剪;在此基础上,提出了一种基于Hypervolume指标的自适应邻域多目标进化算法ANMOEA?HI.对比实验结果表明,ANMOEA?HI在保证了解集收敛性的同时亦拥有良好的分布性.There are two key factors in designing multi-objective evolutionary algorithms （MOEAs）. One is how to ensure the evolutionary procedure approaches to the Pareto optimal solutions set, and the other is how to obtain well distributed solutions set. A tree neighbor containing the relation which represents the close degree of individuals is defined. Along with the Pareto dominance relationship, a density estimation metric neighbor tree density is proposed to assign the fitness. In order to save the computational cost, a novel algorithm to calculate the exclusive hypervolume indicator is proposed. It is enough to calculate once （similar methods normally need to calculate twice） when evaluating an individual＇s contribution to total hypervolume. Moreover, if the size of external population exceeds the predefined threshold, the individual which contributes least to the exclusive hypervolume indicator will be eliminated. Based on all of these, an adaptive neighbor multi-objective evolutionary algorithm based on Hypervolume indicator （ANMOEA/HI） is proposed. In order to verify the efficiency of our proposed algorithm, it is tested with other 3 state-of-the-art MOEAs on 7 test problems. Four different kinds of metrics are used to give a fair judgment on their performances. Experimental results demonstrate that the proposed ANMOEA/HI obtains good performance in both convergence and distribution.

关 键 词：最小生成树 树邻域密度 适应度赋值 Hypervolume指标 种群维护 多目标进化算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]