Abstract:

Concerning the high time-complexity of multi-objective evolutionary algorithm based on Pareto dominated solution sorting, considering the potential features of non-dominated solution sorting, a fast sorting method which only handles individuals with the highest rank in current population was introduced. The individuals could be chosen into the next generation during the sorting. The algorithm was terminated when the population of next generation was selected enough, which reduced the number of individuals for sorting process and the time complexity. In addition, a method of uniform crowding distance calculation was given. Finally, a Fast Multi-Objective Differential Evolution (FMODE) algorithm was proposed which incorporated the introduced sorting method and uniform crowding distance into Differential Evolution (DE). Simulation experiments were conducted on the standard multi-objective optimization problems including ZDTl~ZDT4 and ZDT6. The time consumption of FMODE was far less than NSGAⅡ in large size of population, and its overall performance was much better than the classic NSGAⅡ, SPEAⅡ and DEMO. Moreover, the uniform crowding distance method provided better performance than classic crowding distance in framework of FMODE. The parameters of FMODE were also obtained by experiments. The simulation results show that the proposed algorithm has lower time complexity of calculating level, and better performance in convergence and diversity.

摘要：

为解决基于帕累托(Pareto)支配解排序的多目标进化算法高时间复杂度问题，依据非支配解排序潜在特性，介绍了一种快速的非支配解排序方法，每次只处理当前种群中最高等级个体，且在分配等级的同时，能选择个体进入下一代，下一代被选足时即结束程序，减少了排序处理个体的数量，大幅度降低时间复杂度；另外，给出一种均匀的拥挤距离计算方法；最后，将快速非支配解排序和均匀拥挤距离计算与微分进化算法结合，提出基于非支配解排序的快速多目标微分进化算法(FMODE)。采用标准多目标优化问题ZDTl～ZDT4和ZDT6进行仿真实验：当种群个体较多(大于500)时，FMODE所用时间远小于NSGAⅡ；FMODE的总体性能上均优于经典的NSGAⅡ、SPEAⅡ和DEMO；在FMODE框架内，采用均匀拥挤距离在性能上也明显优于经典拥挤计算方法；并通过实验确定了FMODE算法的参数。实验结果表明FMODE能够减少计算等级时的处理时间，并在收敛性和多样性指标上明显优于对比算法。