基于角度轨迹和自适应权重的改进MOEA/D算法

An Improved MOEA/D Algorithm Based on Angle Trajectory and Self-Adaptive Weight

基于分解的多目标优化算法是解决多目标优化问题的有效方法,其主要思想是通过一组均匀分布的权重向量对目标进行加权,形成不同的子问题,在其邻域内通过协同进化得到帕累托最优解集。然而,这些均匀分布的权重向量不能很好地适应所有前沿形状的多目标问题,导致解集的多样性下降。为使算法能够高效地判断前沿类型,并有效地调整权重向量,本文提出了基于角度轨迹和自适应权重的改进MOEA/D算法,该算法通过基于角度的聚类方法,降低聚类时间复杂度,并利用聚类-合并策略,提高对前沿划分的准确性。在根据聚类结果判断出前沿类型后,算法根据其前沿类型,采用根据角度划分区域的分配策略,或是根据前沿分段长度和数量分配。这样可以有效地分配计算资源,提高多目标问题求解的效率,通过实验证明,算法的分配策略行之有效,能提高尖峰、长尾和不连续前沿的解集多样性,在收敛性和多样性上均优于对比算法。

Multi-objective optimization algorithm based on decomposition(MOEA/D)is an effective method to solve multi-objective optimization problems.The main idea is to weight the target by a set of evenly distributed weight vectors to form different scalar subproblems,and get the Pareto optimal solution set by coevolution in its neighborhood.However,these evenly distributed weight vectors can not be well adapted to the multi-objective problem of all frontier shapes,resulting in a decrease in the diversity of solution sets.In order to make the algorithm efficiently judge the frontier type and effectively adjust the weight vector,this paper proposes an improved MOEA/D algorithm based on angle trajectory and adaptive weight.The algorithm reduces the time complexity of clustering by using the angle-based clustering method,and improves the accuracy of frontier division by using the clustering-merging strategy.After judging the frontier type according to the clustering results,the algorithm adopts the allocation strategy of dividing regions according to the angle,or allocating according to the length and number of frontier segments.In this way,computing resources can be allocated effectively and the efficiency of solving multi-objective problems can be improved.Experiments have proved that the allocation strategy of the algorithm is effective and can improve the diversity of solution sets of peaks,long tails and discontinuous fronts,and it is superior to the comparison algorithm in convergence and diversity.