多目标进化算法的一种基于生成树的分布性维护方法

Spanning tree-based diversity maintenance in multi-objective evolutionary algorithms

针对多目标进化算法的种群维护和运行效率相矛盾的问题,提出了一种基于生成树的分布性维护方法,即对整个种群构造一棵生成树,定义一种密度估计指标——树聚集距离,并结合树中的最短树枝和个体度数对种群进行维护。由于树聚集距离和度数具有动态性,每移出一个个体,种群中与之相连个体的信息都会发生相应的变化,因而可即时反映出种群的分布情况。与三个著名的算法NSGA-Ⅱ、SPEA2和C-NSGA-Ⅱ的比较实验表明,该方法能在得到良好分布性解集的同时,能以较快的速度对种群进行维护,具有较好的时间效率。

The paper proposes a new method for maintaining the diversity of multi-objective evolutionary algorithms （MOEA） using the spanning tree. The method defines a density estimation metric, the spanning tree crowding distance. Moreover, it applies the shortest edge and the degree in the spanning tree combined with the spanning tree crowding distance to population tnmcation. The extensive comparative study with the three other classical methods of NSGA- Ⅱ , SPEA2 and C- NSGA- Ⅱ on four performance metrics and twelve test problems, indicates that the proposed method has a good balance among uniformity, extent and execution time.