【学习笔记】多目标优化问题分解成若干简单多目标子问题--MOEA/D-M2M
- 算法简介
- 主要思想
-
- 1.分解
- 2.算法
算法简介
MOEA/D-M2M，一种基于分解的多目标优化进化算法。该算法将多目标优化问题分解成若干个简单的多目标子问题。以协作方式解决这些子问题。每个子问题都有自己的种群，并在每一代接受计算。
通过这种方式，可以保持种群多样性，这对于解决一些多目标优化问题至关重要。在处理一些多目标优化问题的多目标进化算法中，种群多样性比收敛性更重要。这也解释了为什么MOEA/M2M表现更好。
主要思想
定义要优化的多目标问题为
1.分解
由于方便起见，我们假设要优化的多目标问题（1）中的每个目标函数即
非负，因此，所有的目标向量，以及（1）的PF（pareto font）都在Rm +（非负数）中。
MOEA/D-M2M背后的主要思想是将（1）分解成一组简单的多目标优化子问题，然后在一次运行中解决它们。【eg.（1）中的m等于六，我们可以将六个目标函数分成三组，每组有两个目标函数】
为了能够完成上面的操作，我们选择K个单位向量，
然后利用这K个单位向量将Rm +划分成K个此区域，每个次区域满足公式（2）。
<u,v>的意思是u，v之间的锐角。
举个简单的例子来解释公式（2）
如下图是一个二维的多目标优化函数F(X)=(f1x，f2x）
在黄色区域里的个体和单位向量v2的夹角角度要小于和单位向量v1的夹角角度，因此黄色区域里的点属于次区域2，同理蓝色区域里的点属于区域1.
根据这种划分方式，我们可以将问题（1）重新划分成K个子问题：
2.算法
MOEA/D-M2M使用上述提出的分解策略将(1)分解成K个多目标优化子问题，并以协作方式解决它们。在每一代，MOEA/D-M2M维持着K个亚种群:
Pk是第k个子问题的种群。每个亚种群始终包含着S个个体可行解；每个个体的F-value（即目标函数向量的值）都会保存；
算法1是MOEA/D-M2M的伪代码：算法1中的第1行和第13行都使用多个单独的解来设置P1，…，PK。我们使用算法2中描述的简单方法来实现它。
算法2确保每个Pk在每一代都有S个个体可行解，因此，在搜索过程中促进了种群多样性。
当一些多目标子问题比其他子问题困难得多时，这一点非常重要。大多数帕累托优势算法可能无法以有效的方式解决此类多目标优化问题。因为帕累托优势算法在其选择中进行全局非优势排序。因此，如果某些困难的多目标子问题的可行域中的当前解完全被其他解所支配，那么这些子问题很可能很少甚至没有下一代问题的解。其结果是，将造成人口多样性的巨大损失。
算法2的第7行使用NSGA II中的非支配排序方法。实际上，任何其他选择策略都可以用于此目的。