多目标优化算法——基于分解的多目标进化算法（MOEA-D）

MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition

一、算法简介

1. 简介：本文提出了一种基于分解的多目标进化算法（MOEA/D）。它将多目标优化问题分解为多个标量优化子问题，并同时进行优化。每个子问题仅利用其相邻子问题的信息进行优化，使得MOEA/D每代的计算复杂度低于MOGLS和非支配排序遗传算法II （NSGA-II）。实验结果表明，采用简单分解方法的MOEA/D在多目标0-1背包问题和连续多目标优化问题上优于或近似于MOGLS和NSGA-II。结果表明，采用目标归一化的MOEA/D方法可以处理不等尺度的目标，而采用高级分解方法的MOEA/D方法可以为有3个目标问题的测试实例生成一组分布非常均匀的解。
2. 多目标优化问题的形式化定义为：

$$MinimizeF(x)=[f_1(x),f_2(x),\dots ,f_m(x)]$$

• x∈X: 决策变量空间

• F(x)∈Y: 目标空间

• m: 目标数量。

  由于多个目标之间可能存在冲突（例如，一个目标的改进会导致另一个目标的恶化），无法同时优化所有目标，需要找到一组折衷解，称为帕累托最优解。MOEA-D算法广泛应用于工程优化、资源分配、路径规划等领域，尤其是在多个相互冲突的目标之间寻求平衡时表现出色。

3. MOEA-D的特点：
   • MOEA/D为多目标进化计算中引入分解方法提供了一种简单而有效的方法。
   • 可以更容易处理适应度分配和多样性维护等问题。
   • 与NSGA-II和MOGLS相比，MOEA/D每代的计算复杂度更低。
   • 目标归一化技术可以使MOEA/D能处理不同尺度的目标。
   • 使用标量优化方法，每个解决方案都与一个标量优化问题相关联。

二、问题分解

1. 加权和法分解（Weighted Sum Approach）

   将所有目标的线性加权和作为单目标函数，假设待优化的多目标问题有m个目标，该函数通过一个非负权重向量：

$$\vec{\lambda }=({\lambda }_1\dots \dots {\lambda }_m)$$

​ 加权到每个目标上将问题转换为单目标问题。每一个单目标问题都可以如下表示，

​ 不同的问题有不同的权重向量，对于所有的i=1,2,…,m，λi>=0，权重和为1。

​ 缺点：在最优Pareto面的形状为非凸面的情况下，这种方法并不能获得每一个Pareto最优向量。为此，人们将其他技术，如 ε约束( ε -constraint)等，结合到该方法中。

2. 切比雪夫（Tchebycheff）法分解

   通过将每个目标的目标值与理想点之间的差距与一个权重向量相乘，来衡量解的质量

   最小化最大距离

​ Zi=min{fi(x)|x∈Ω}*

Z*为参考点（代表算法理想值，最小化问题取某个目标上的出现过的最小值作为该目标上的理想位置）

缺点：它的聚合函数对于连续的MOP来说不是平滑的。

3. 边界交叉法分解

   最大化连续MOP问题的PF前沿会是目标函数集的右上部分，最小化MOP的PF前沿是左下部分

   

   当处理最小化问题时：
   

   约束确保 F(x)总是在 L上，即方向为 λ 并通过 Z*的直线

缺点是必须处理等式约束。我们使用惩罚法来处理该约束（惩罚边界交叉法）：

当处理最小化问题时：

θ > 0 为预定义惩罚参数，一般取5

三、邻域

四、算法流程

1. 符号定义：

2. 采用Tchebycheff 法的算法流程：