一种改进的基于分解多目标优化算法

宋武　陈德祥

摘要：为了解决多目标优化问题，该文提出了一种改进的基于分解的多目标进化算法，算法非平衡的分配计算资源给每个子问题，每个子问题具有相对较大的密度时，能够分配较多的资源，实验结果表明改进的算法优于原有的基于分解的多目标优化算法。

关键词：多目标优化问题；多目标进化计算；分解

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2012）34-8316-03

实际问题一般都是多属性的，往往需要同时优化多个目标。根据选择机制的不同，可将多目标优化进化算法（MOEAs：MultiobjectiveEvolutionaryAlgorithms）当前的主流是基于Pareto的[1]。出现了许多经典的算法，如NSGA-II[2]等，但此类算法只能适用于处理低维优化问题，随着目标维数的增加，算法的搜索能力显著下降，无法找到优化问题的近似Pareto最优面。

针对基于聚集函数的多目标优化算法的不足，Zhang和Li[2]通过预先产生均匀分布的权值向量将多目标优化问题转换为一组单目标子问题，并为每个子问题分配一个个体，从而提出了MOEA/D（MultiobjectiveEvolutionaryAlgorithmbasedonDecomposition）[12]。实验表明，该算法能有效地处理高维问题及决策空间不连续问题[3]]。基于MOEA/D算法的优势。

由于MOEA/D在进化时，平均的分配给每一个子问题进行进化，严重制约了其性能的进一步提高。但是由于优化的问题在前沿面上，并不是均衡的，对应于子问题进化时也不是均衡的。导致了已经收敛的子问题，继续有进化的能力，而没有收敛的子问题获得较少的计算性资源，因此该文考虑了一种，在选择父亲进行交叉时，非平衡的选择父亲个体，从而完成了非平衡分配的方案，实验结果表明该算法具有一定可行性及有效性。

1改进的MOEA/D算法

MOEA/D在将多目标优化问题分解为一组单目标子问题并为每个子问题分配一个个体，由各个子问题上的个体组成初始种群，通过均匀的并行进化各个子问题而得到一组解集。基于邻域的进化是MOEA/D的有效搜索机制之一。此外，为了计算适应度，MOEA/D算法成功地将数学规划中常用的分解方法引入到进化多目标领域，使用分解方法计算适应度可以直接采用求解单目标优化问题时的适应度分配和多样性保持策略[21]。目前最常用的分解方法有：WeightedSum、Tchebycheff和Penalty-basedBoundaryIntersection（PBI）。

1）WeightedSum分解方法