09第九章 多目标优化算法
第九章多目标优化算法习题与答案
1. 填空题
（1）多目标优化问题由于存在目标，使得同时优化的对象增多。由于目标之间往往相互冲突，某一目标性能的提高会引起其他目标性能的，因此只能通过的方法使所有目标尽可能达到最优。
（2）多目标优化问题需要求解一个由不同程度折中的组成的解集，并且需要保证解集的和，这就导致多目标优化问题的求解难度远远大于单目标优化问题。
解释：
本题考查多目标优化算法的基础知识。
具体内容请参考课堂视频“第9章多目标优化算法”及其课件。
答案：
（1）多个，降低，权衡折中
（2）最优解，收敛性，均匀性
2.如何理解多目标优化问题？
解释：
本题考查多目标优化问题的形式和实质。
内容请参考课堂视频“第9章多目标优化算法”及其课件。
答案：
多目标优化问题由于存在多个目标，优化对象增多，且目标之间往往是相互冲突的，某一目标性能的提高会引起其他目标性能的降低，因此只能通过权衡折中的方法使所有目标尽可能达到最优。不同于单目标优化只需求得一个最优解，多目标优化需要求解一个由不同程度折中的最优解组成的解集，且需同时保证解集的收敛性和均匀性。例如，购买汽车时考虑到汽车性能和价格两个方面，往往
当性能较好时性能优良且价格昂贵，而性能较差时价格低廉，人们总是想得到价格便宜同时性能又好的汽车，但这两方面往往不能同时兼优，只能在某一方面有所偏重，这就形成了一个以汽车性能（比如百米加速时间）和价格为两个冲突目标的多目标优化问题。
3. 试举例说明Pareto 支配关系具有传递性。 解释：
本题考查Pareto 支配关系的性质。
内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案：
假设两目标最小优化的三个个体，123=(2,2)=(3,3)=(4,4)C C C ，，，则1
2C C ，
2
3C C ，又因为1
3C C ，所以Pareto 支配关系具有传递性。
4. 考虑一个具有两个目标最小化问题，20个个体的进化群体，进行Pareto 非支配排序分层。20个个体定义如下：C 1=(9,1)，C 2=(7,2)，C 3=
(5,4)，C 4=(4,5)，C 5=(3,6)，C 6=(2,7)，C 7=(1,9)，C 8=(10,1)，C 9=(8,5)，C 10=(7,6)，C 11=(5,7)，C 12=(4,8)，C 13=(3,9)，C 14=(10,5)，C 15=(9,6)，C 16=(8,7)，C 17=(7,9)，C 18=(10,6)，C 19=(9,7)，C 20=(8,9)
解释：
本题考查基于Pareto 支配的排序方法。
内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案：
由于{}18C C ；{}2349,,C C C C ；{}234510,,,C C C C C ；{}345611,,,C C C C C
；
{}
45612
,,C C C C ；
{}
56713
,,C C C C ；
{}
12348914
,,,,,C C C C C C C ；{}
1234591015
,,,,,,C C C C C C C C ；
{}
234569101116
,,,,,,,C C C C C C C C C ；
{}
2345671011121317
,,,,,,,,,C C C C C C C C C C C ；{}123458910141518,,,,,,,,,C C C C C C C C C C C
；{}
12345691011151619
,,,,,,,,,,C C C C C C C C C C C C ；
{}
234567910111213161720
,,,,,,,,,,,,C C C C C C C C C C C C C C
根据以上支配关系，这20个个体具有下列4个层次：
{}11234567,,,,,,P C C C C C C C =
{}28910111213,,,,,P C C C C C C =
{}314151617,,,P C C C C =
{}
4181920,,P C C C =
5. 简述NSGA-II 算法的基本流程。 解释：
本题考查NSGA-II 算法思想。
内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案：
首先，随机产生规模为N 的初始种群t P ，产生子代种群t Q ，并将两个种群联合在一起形成大小为2N 的种群t R ；其次，将父代种群与子代种群合并，进行快速非支配排序并且分层，同时对每个非支配层中的个体进行拥挤度计算，根据非支配关系以及个体的拥挤度选取合适的个体组成新的父代种群1t P +，最后，通过遗传算法的基本操作产生新的子代种群1t Q +，将1t P +与1t Q +合并形成新的种群
t R ，重复以上操作，直到满足程序结束的条件。
6. 简述NSGA-II 与NSGA-III 的不同之处。 解释：
本题考查NSGA-III 算法思想。
内容请参考课堂视频“第9章多目标优化算法”及其课件。
答案：
NSGA-III 的基本框架与NSGA-II 算法类似，不同之处在于多样性维护策略，其采用基于参考点的小生境保留策略：首先，在关联操作将每个个体关联到对应的参考点上之后，定义第j 个参考点的小生境数为j
ρ，它表示/t l S F 中与第j 个参考点相关联的个体数；然后，选取具有最小
j
ρ的参考点组成参考点集
{
}min :argmin j j
j ρ=J 。如果min
1
>J
，则从中随机选择一个参考点min j -
∈J 。如果关键
层l F 中没有个体与参考点j 相关联，则此参考点在当前代不再考虑，同时更新min
J 并重新选择j 。否则，参考点j 将被考虑：当0j ρ=时，关联参考点j 并隶属于关
键层l F 的个体中，选取其中到第j 个参考线垂直距离最近的个体添加到种群1t +P ，同时
j
ρ增加1；当
j ρ>，从关联参考点j 并隶属于关键层l F 的个体中随机选取
一个个体添加到种群1t +P ，同时
j
ρ增加1。
7. 分析MOEA/D 算法三种分解方式的优缺点。 解释：
本题考查MOEA/D 算法思想。
内容请参考课堂视频“第9章多目标优化算法”及其课件。 答案：
MOEA/D 算法利用预先设定的多组权重向量将多目标优化问题分解成多个单目标子问题，并利用不同的分解策略对子问题进行求解。常用的三种分解方式：加权和法，切比雪夫法，惩罚边界交集法。加权和法简单，收敛速度快，但由于实质是不同目标函数构成凸组合，所以不适用于求解真实PF 为非凸的多目标优化问题；切比雪夫法适用于不同形状的前沿，但对于对于连续问题的聚合曲线不平滑，且在目标数增多时，并不能保证分布性；惩罚边界交集法适用于不同形状的前沿和目标数多的情况，但存在一参数难以事先确定，不易调节。
8. 试说明NSGA-III 算法和MOEA/D 算法的区别和联系，及各自的优缺点。
解释：
本题考查NSGA-III算法和MOEA/D算法思想对比分析。
内容请参考课堂视频“第9章多目标优化算法”及其课件。
答案：
NSGA-III算法和MOEA/D算法均采用了均匀分布的参考点，但作用完全不同：前者采用参考点来评价种群个体的密度；而后者用于聚合函数的权重向量。两者求解多目标优化问题的机理不一样：前者仍然将多个目标同时优化，采用Pareto支配关系进行比较，由于要进行非支配排序，求解速度较慢；而后者将多目标优化问题分解成多个单目标子问题协同求解，求解速度快，但在高维多目标优化问题上效果不理想。