基于近似边界和层次聚类的超多目标进化算法-《计算机技术与发展》

文章信息/Info

Title:: Many-objective Evolutionary Algorithm Based on Approximate Boundary and Hierarchical Clustering

Author(s):: ZHANG Feng; GU Yi-fan; School of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing, 211100,China

Keywords:: many-objective optimization problem; nadir point; many-objective evolutionary algorithm; corner solution; hierarchical clustering

摘要:: 很多工程优化问题需要同时优化超过 3 个冲突的目标,这类问题就属于超多目标优化问题。由于超多目标优化问题的目标空间过于庞大,并且很多算法往往只能使用数量较少的种群来近似问题的结果, 这使得很多算法难以保持较好的多样性和收敛性,此外,许多算法往往忽略使用极值点的有效信息来加速算法收敛。为了解决上述问题, 提出了一种基于近似边界和层次聚类的超多目标进化算法。在一种求角点解方法的基础上,使用角点解近似边界(极值点)来加速算法收敛,并进一步提出使用层次聚类来挑选下一代种群,借此使得算法能够保持较好的收敛性和多样性。最后通过与多个流行的求解超多目标优化问题算法进行对比实验,证明了该算法的有效性。

Abstract:: Many engineering optimization problems need to optimize more than 3 conflicting objectives at the same time,and this type of problem belongs to many-objective optimization problem. The objective space of many-objective optimization problem is too large,and many algorithms can only use a small number of population to approximate the results of the problem,which makes it difficult for many algorithms to maintain better diversity and convergence. In addition,many algorithms often ignore valid information from nadir point to speed up the algorithm’s convergence. To solve the above problem, we propose a many-objective evolutionary algorithm based on approximate boundary and hierarchical clustering. On the basis of a corner solution method,the corner solutions is used to approximate the boundary (nadir point) to accelerate the convergence of the algorithm. We further propose the use of hierarchical clustering to select the next population,thereby enabling the algorithm to maintain better convergence and diversity. Finally,the effectiveness of the proposed algorithm is proved by comparing with many popular algorithms for solving super-multi-objective optimization problems.