下载掌阅APP，畅读海量书库
立即打开
多目标优化问题（Multi-objective Optimization Problem，MOP）是一类普遍存在于现实生活中的复杂优化问题。相较于只有一个目标函数的优化问题，多目标优化问题往往包含多个相互冲突的目标。其中，一个目标的改善很有可能引起其他目标的损失，因此需要在多个目标中进行协商、寻求平衡，找到能综合考虑所有目标的最优解。例如，在日常生活中，出租车往往是时间成本最低的出行方式，但费用昂贵。采用公交或地铁出行的费用较低，却比较耗时。平衡出行费用和时间成本、制订合适的出行方案对市民出行来说意义重大。
在过去的二十年中，进化计算方法已成为求解多目标优化问题的重要途径，多目标进化算法（Multi-Objective Evolutionary Algorithm，MOEA）是进化计算领域备受关注的研究方向之一。多目标进化算法继承了进化计算自适应、自组织、自学习和基于种群演化的特性，能够在单次算法执行中有效地找到一组能综合考虑所有目标的最优解，提高了求解多目标优化问题的效率。目前，学者们提出了许多多目标进化算法，主要包括基于非支配排序的MOEA、基于分解的MOEA、基于指标的MOEA等。本节将结合多目标优化问题的定义，对这三类多目标进化算法进行介绍。
不失一般性，一个具有 M 个目标函数的多目标优化问题可以描述为
其中， Ω 是决策空间， x =（ x 1 ， x 2 ，…， x N ） T 表示一个包含 N 个决策变量的候选解。 F （ x ）包含了 M 个目标函数， f i : Ω → R ， i =1，2，…， M ， R M 是目标空间。由于多个目标之间往往是相互冲突的，改善某个目标会引起其他目标的损失，因此， F （ x ）中不存在能够同时使得所有目标函数达到最优的解。所以，多目标优化问题的目的并不是寻找一个最优解，而是寻找一组帕累托最优解（Pareto optimal solution），定义如下。
定义2-1（帕累托支配） 假设 Ω 中存在两个向量， x =（ x 1 ， x 2 ，…， x N ） T 和 y =（ y 1 ， y 2 ，…， y N ） T ，当且仅当
则称
x
相比
y
是帕累托占优的，记作
，称为
x
支配
y
。
定义2-2（帕累托最优解集）
假设
，若不存在
，使得
，则称
x
*
为帕累托最优解。所有帕累托最优解组成帕累托最优解集（Pareto Optimal Set，POS）。
定义2-3（帕累托最优前沿） 所有帕累托最优解对应的目标向量组成的集合即为帕累托最优前沿（Pareto Optimal Front，POF）。
进一步地，以一个两目标优化问题为例，即
M
=2，上述定义的示意图如图2-1所示。图中的一个点代表一个候选解在目标空间中的对应位置。在图2-1a中，根据定义（2-1），
，也就是说
x
支配
y
。在图2-1b中，POS中的候选解对应的目标向量被标记为〇。在图2-1c中，黑色连线代表所有帕累托最优解对应的目标向量组成的光滑曲线，即POF。