多目标优化算法思维导图-NSGA-II, NSGA-III, MOEA/D, C-TSEA, CMOEA-MS
需积分: 0 46 浏览量
更新于2024-12-15
收藏 1.76MB PDF 举报
内容概要：本文系统介绍了五个多目标优化算法，包括NSGA-II、NSGA-III、MOEA/D、C-TSEA和CMOEA-MS。其中，NSGA-II和NSGA-III通过非支配排序和拥挤度计算以及参考点采样来处理多目标优化问题，MOEA/D通过将多目标优化问题分解为若干个标量优化子问题，提高了解的多样性和全局收敛性，而C-TSEA采用两阶段进化机制分别优化收敛性和多样性，CMOEA-MS则通过多重选择标准和交替优化机制处理高维优化问题。
适合人群：对多目标优化理论感兴趣的研究人员和技术人员。
使用场景及目标：适用于需要解决多目标优化问题的实际应用中，如工程设计、经济决策、环境管理等领域。通过学习这些算法，可以深入了解多目标优化的基本原理和最新进展。
阅读建议：建议读者结合实例进行深入研究，并在实际项目中尝试应用这些算法，以便更好地理解和掌握其优缺点。
1011论⽂汇报
NSGA-II
解决的问题
多⽬标优化中，⽬标通常是相互冲突的，找到单
⼀解并不合适，因此需要找到Pareto前沿上的⼀
组⾮⽀配解。NSGA-II 是⼀个经典的多⽬标进化
算法，旨在通过遗传算法框架，保持种群的多样
性，并快速找到Pareto前沿。
主要部分
⾮⽀配排序
根据解的⾮⽀配关系进⾏排序，优先选择低排序
的解。
拥挤度计算 计算解的邻域距离，确保种群多样性。
选择机制
NSGA-II 使⽤的是基于排序和拥挤距离的选择机
制。它⾸先基于⾮⽀配排序选择低层级的解，然
后根据拥挤距离进⾏选择。当层级相同时，优先
保留拥挤距离⼤的解。
改进点
相较于 NSGA-I，NSGA-II 的 时间复杂度降⾄
O(N log N)，极⼤提⾼了计算效率。
引⼊了 拥挤度距离 来代替共享函数，从⽽在
Pareto前沿上保持解的多样性。
不⾜
在处理⾼维⽬标问题时（如超过三四个⽬标），
NSGA-II 的性能可能下降。
对于需要复杂多样性的⾼维优化问题，拥挤度距
离的效果有限。
NSGA-III
解决的问题
随着⽬标维度的增加，NSGA-II 的表现逐渐变
差，尤其是在处理五个及以上⽬标的⾼维多⽬标
优化问题时。NSGA-III 针对⾼维⽬标问题，改进
了 NSGA-II 的种群选择机制。
主要部分
参考点采样
NSGA-III 针对⾼维多⽬标优化引⼊了参考点机
制。参考点的作⽤是引导解集更好地覆盖 Pareto
前沿，尤其是在⾼维⽬标空间中：
通过简单的⼏何⽅法或超平⾯，预先⽣成参考
点，均匀分布在⽬标空间中。
每个参考点代表⼀个⽬标组合的理想解，在种群
进化过程中，每个解会被分配到最接近的参考点
区域，确保所有参考点都有解覆盖，从⽽避免种
群集中在某些特定区域。
⾮⽀配排序
和 NSGA-II 类似，NSGA-III 也采⽤⾮⽀配排
序，但重点在于如何有效分配解集到不同的参考
点上，以增强在⾼维⽬标问题上的表现。
选择策略
在每⼀代的选择过程中，NSGA-III 基于⾮⽀配排
序和参考点分配进⾏解的选择。具体步骤如下：
将种群解集映射到参考点，计算每个参考点区域
的解数⽬。
如果某个参考点区域的解不⾜，将优先选择分配
到该参考点区域的解，以保证 Pareto 前沿的⼴
泛覆盖。
改进点
NSGA-III 引⼊了 参考点分布机制，相⽐于
NSGA-II，仅依赖拥挤度距离的⽅法，能更有效
地解决⾼维问题。
通过参考点的分配，可以在⾼维⽬标空间 中获得
更好的 Pareto 解集。
不⾜
参考点的选择仍然是⼀个挑战，需要根据问题具
体定义合理数量和分布的参考点。
算法在处理极其复杂的多模态问题时可能仍不⾜
够鲁棒。
MOEA/D
解决的问题
MOEA/D主要解决的是多⽬标优化问题，传统的
进化算法如NSGA-II和SPEA2等，通常通过⾮⽀
配排序等机制处理多个⽬标，但这些算法在⾼维
⽬标空间中会⾯临收敛性和计算复杂性等问题。
MOEA/D则通过将MOP分解为⼀系列加权的单⽬
标优化问题，分别求解这些问题来获取帕累托前
沿，从⽽提⾼算法的效率。
主要部分
MOEA/D的核⼼思想是将多⽬标优化问题分解为
若⼲个标量优化问题（单⽬标优化问题），然后
通过并⾏或协同的⽅式来解决这些⼦问题。其主
要步骤包括
问题分解：MOEA/D使⽤加权和法、切⽐雪夫法
或其他标量化⽅法将多⽬标问题转化为多个标量
⼦问题。
邻域定义：MOEA/D将每个⼦问题与其邻居进⾏
关联，邻居定义为在权重空间中距离较近的⼦问
题。
解的进化：通过交叉、变异等操作，⽣成新解，
并通过⽐较当前解和邻居解的适应度来更新解
集。
协同演化：不同的⼦问题共享信息，推动整个群
体向帕累托前沿收敛。
加权和⽅法（向量投影⻆度理解） 不适应凸函数，因为凸函数没办法做投影
切⽐雪夫聚合法（最⼤距离最⼩化⻆度理解）
边界交叉聚合⽅法-BI Approach（最⼩化最⼩值
参考点与权重向量上的所求解之间的距离）
引⼊惩罚函数
流程图
改进点
MOEA/D相较于传统的多⽬标优化算法具有以下
显著的改进：
基于分解的策略：通过将多⽬标优化问题分解为
若⼲个标量优化问题，简化了多⽬标优化问题的
求解难度，使算法能够处理更⾼维度的⽬标问
题。
邻域共享机制：通过⼦问题之间的协同演化，充
分利⽤邻域信息，促进全局收敛性，并提⾼多样
性。
标量化⽅法灵活：不同于传统的Pareto排序，
MOEA/D可以根据问题需求使⽤多种标量化⽅法
来分解多⽬标问题。
不⾜
权重向量的选取：MOEA/D依赖于权重向量的合
理选取，权重的设计需要对问题有深⼊了解，若
设计不当可能导致结果不理想。
⾮均匀问题表现不佳：对于⽬标分布不均匀或⾼
度复杂的帕累托前沿，MOEA/D可能在多样性维
护和精确收敛上表现不如其他基于Pareto排序的
算法。
计算复杂度：虽然MOEA/D在处理多⽬标问题上
有所改进，但在⼤规模的⾼维多⽬标优化问题
上，随着⼦问题数量的增加，计算复杂度也会增
加。
C-TSEA
解决的问题
针对多⽬标优化问题中的 收敛性和多样性 问
题，C-TSEA 提出了两阶段进化算法，重点解决
如何在快速收敛的同时保证 Pareto 前沿解集的
多样性。
主要部分
两阶段进化
C-TSEA 使⽤两阶段进化的⽅式分别优化收敛性
和多样性。每个阶段采⽤不同的优化策略：
第⼀阶段：主要关注收敛性，通过⽬标函数的精
确优化，使解尽快逼近 Pareto 前沿。在这⼀阶
段，算法强调解在⽬标值上的改进，采⽤激进的
搜索策略。忽略约束并逼近PF，找到均匀分布的
解，并且通过存档更新策略储存最优解。
第⼆阶段：主要关注多样性。此阶段通过引⼊多
样化机制，扩展解集在 Pareto 前沿上的分布，
避免解集过于集中。这通常通过更为宽松的选择
标准，结合拥挤度或距离度量来实现。考虑约束
找到CPF。
收敛和多样性机制分离
通过不同阶段分别优化收敛和多样性，避免互相
影响。第⼆阶段注重多样性，通过多样化机制扩
展解的分布。
改进点
相⽐于 NSGA 系列算法，C-TSEA 的 两阶段机制
在处理收敛与多样性平衡上更加精细，针对不同
优化阶段施加不同压⼒。
算法对 Pareto前沿的覆盖效果 优于单⼀机制的
进化算法。
不⾜
算法的两阶段机制使得计算复杂度增加，实际应
⽤中可能存在参数调优困难的问题。
对于⾼维问题，第⼆阶段的多样化机制可能仍然
需要进⼀步改进。
CMOEA-MS
解决的问题
⾼维多⽬标优化（Many-objective
Optimization）下，传统的拥挤度或参考点⽅法
难以⾼效⼯作。CMOEA-MS 针对这些问题，采
⽤多重选择标准，以提⾼⾼维优化问题中的表
现。
主要部分
多重选择标准
结合多个⽬标选择机制，如 拥挤度、距离、覆盖
度 等标准，确保解集的全⾯性和多样性。
交替优化
在不同代中切换不同的选择标准，避免单⼀标准
导致的局部收敛。根据可⾏解数量来决定到底到
A 阶段还是到B阶段。
改进点
相较于 NSGA-III，CMOEA-MS 的 多重选择机制
能更灵活地应对复杂的多⽬标优化问题。
通过交替选择机制，能够更好地 保持种群的多样
性 并避免过早收敛。
不⾜
多重选择标准增加了算法的复杂性，选择不同标
准的频率及优先级成为⼀个难点。
算法可能需要更⾼的计算资源，尤其在极⾼维⽬
标问题中。
总结与思考
总结
NSGA-II 的主要贡献在于通过⾮⽀配排序和拥挤
距离解决了低维多⽬标优化中的收敛与多样性问
题。
NSGA-III 针对⾼维多⽬标问题，采⽤参考点采样
来增强解集在⾼维 Pareto 前沿的覆盖。
C-TSEA 则将收敛和多样性分成两个阶段分别优
化，确保快速逼近 Pareto 前沿的同时保持多样
性。
CMOEA-MS 通过多重选择标准和交替优化机
制，更灵活地处理⾼维多⽬标问题，避免了单⼀
优化标准带来的局限性。
问题
如何在处理更⾼维多⽬标问题时减少计算复杂
度，同时保持解集的多样性和收敛性？
多⽬标优化算法中的 参考点设置和多样性保证机
制 如何进⼀步改进，特别是在超⾼维问题中？
未来改进⽅向
动态参考点⽣成
探索如何根据解集的进化状态动态⽣成参考点，
⽽不是事先固定参考点。
⾃适应参数调优
现有算法在具体应⽤中需要⼤量参数调优，未来
可考虑设计具有⾃适应参数调节的算法，使其更
具鲁棒性。
其关键优势在于其能够有效地平衡多样性和收敛性
1、利用单位单纯性表面上的点非负且和为
1的性质来确定参考点的生成区域。并在其
上均匀采点来保证参考点是均匀分布的。
2、将在多维单纯形上均匀采点转换为排列
组合问题，以简化问题的求解。并且事先
确定好种群维度（参考向量的个数），以
方便后续确定将单纯形边长均分的个数和
排列组合的总数，以保证基于分解的方法
的每个个体都可以对应一个参考向量。
特别的，对于MOEA-D算法，单个个体和参
考向量的对应是直接按照对应位置。
可行解不够的情况
可行解够了，主要是考虑约束了
X
+
Y
,
~
ref
·
Gate
>
fi
-
#F
=
EG
EFII
FEE
1
-
PF
i
2
-
(p
=
*
-
>
!
A
↓
B
55'REBEXER
下载后可阅读完整内容，剩余3页未读，立即下载
资源评论
小酒馆cc
- 粉丝: 28
- 资源: 4
