对于⼤多数多⽬标优化问题，其各个⽬标往往是相互冲突的，因此不可能使得所有的⽬标同时达到最优，⽽是⼀组各个⽬标值所折衷的解集，称之为Pareto 最优集。以下为⼀些基本定义(以最⼩化优化问题为例)： Definition 1: 多⽬标优化问题(multi-objective optimization problem(MOP))
Definition 2: Pareto ⽀配(Pareto Dominance)
x ⽀配y，记为 x y ，当且仅当 , (y), 且 , s.t. 。Definition 3: Pareto 最优解(Pareto Optimal Solution)
如果⼀个解 被称之为Pareto optimal solution ， 当且仅当 不被其他的解⽀配。
Definition 4: Pareto 集(Pareto Set)
⼀个MOP ，对于⼀组给定的最优解集，如果这个集合中的解是相互⾮⽀配的，也即两两不是⽀配关系，那么则称这个解集为Pareto Set 。Definition 5: Pareto 前沿(Pareto Front)
Pareto Set 中每个解对应的⽬标值向量组成的集合称之为Pareto Front, 简称为PF
Definition 6：近似集(Approximation Set)
⼀般来说，准确的Pareto Set 是很难得到的，其近似集相⽐来说容易得到，因此⼀般我们只需⽤⼀定数量的Approximation Set 来表⽰PS 。Definition 7： 近似前沿(Approximation Front)
Approximation Set 中每个解对应的⽬标值向量组成的集合称之为Approximation Front 。
⽬前来说，由于多⽬标问题的复杂性，传统的数学⽅法不能取得较为理想的结果，⽽进化在多⽬标优化问题上得到了很⼴泛的应⽤，通过种的不断进化迭代，进化算法能得到⼀个Approximation Set ，那么我们如何来评价得到的Approximation Set 的优劣呢，以下为两⽅⾯的评价标准。
Definition 7：收敛性(Convergence)
Approximation Front 与 PF 的贴近程度。
Definition 8: 分布性(Diversity)
描述Approximation Front 在PF 的分布情况，包括分布范围和均匀性。
具体来说，常⽤的两个指标分别是IGD(Inverted Generational Distance) 和 HV(Hypervolume)。其中，
IGD 需要知道PF 数据，且其具体计算为每个PF 中的点到其最近的Approximation Front 中的点的距离之和的均值。同时，需注意，这两种⽅法都能同时度量解的分布性和收敛性。
现在来讲讲主流的多⽬标进化算法。
从进化算法的⾓度来讲，⽬前已有遗传算法(GA)，粒⼦算法(PSO)，蚁算法(ACO)等⼀系列算法⽤来解决多⽬标优化问题，但⽤的⽐较多的还是遗传算法，粒⼦算法也有。
从多⽬标问题本⾝来说，主要分类如下：
- 基于Pareto ⽀配关系
- 基于分解的⽅法
- 基于Indicator ⽅法
F (x)=((x),…,(x))
f 1f ∈Ω
≺∀i ∈{1,2,...,m}(x)≤f i f i ∃j ∈{1,2,...,m}(x)<(y)f j f j x ∗x ∗
先来介绍下基于遗传算法的多⽬标优化算法的⼀些基本参数：
种⼤⼩：每次迭代都需保证种⼤⼩是⼀致的，且其⼤⼩应由初始化设定。
突变率：交叉产⽣的解发⽣突变的概率。
标准的遗传算法每次迭代都会将上⼀代的个体丢弃，虽然这符合⾃然规律，但对于遗传算法来说，这样效果不是特别好，因此，精英保留策略将上⼀代个体和当前个体混合竞争产⽣下⼀代，这种机制能较好的保留精英个体。
基于Pareto⽀配关系
最经典的⽅法是NSGA-II，该⽅法由Kalyanmoy Deb等⼈于2002年提出(A Fast and Elitist Multiobjective Genetic Algorithm:
NSGA-II)，该⽅法主要包括快速⾮⽀配排序，将每次交叉突变产⽣的解和前⼀代的解合并，然后利⽤⾮⽀配排序分层，其伪代码如下：
再就是把每层相加直到超过种个体，再在最后⼀层基于拥挤距离来选择解，拥挤距离伪代码如下：
具体来说，NSGA-II使⽤快速⾮⽀配排序来保证收敛性，并且利⽤拥挤距离来保证分布性。特别说下，在迭代后期，⼤多数解都是⾮⽀配的，也即⼤多数解都在第⼀层。
当然，随着NSGA-II的提出，很多基于此的算法如⾬后春笋般⼤量涌现，特别是在处理⾼维多⽬标优化问题时这种想法得到很多的应⽤，如VaEA，RVEA，NSGA-III等。
同时，SPEA2也是基于Pareto⽀配关系的⼀种较为流⾏的算法(SPEA2: Improving the Strength Pareto Evolutionary Algorithm)，该算法使⽤⼀个外部保存集来保存较为优秀的解，同时，对每⼀个解，利⽤其⽀配的解的数量和基于KNN的邻近解的距离来给每⼀个解打分，得分越⼩的解更优。
基于分解的⽅法
该⽅法第⼀次系统地被提出是在2007年由Qingfu Zhang 等⼈提出(MOEA/D: A Multiobjective Evolutio
nary Algorithm Based on
Decomposition)，该⽅法将MOP 分解为多个⼦问题，这样就可以优化每个⼦问题来求解⼀个MOP 。⼀般⽽⾔，基于分解的⽅法⾸先需要得到⼀组均匀分布的参照向量来指导选择操作。在此，有必要说说产⽣参照向量的⽅法。⽬前对于低维多⽬标优化问题，常⽤⽅法为Das and Dennis 于1998年提出的systematic approach(Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems).
对于每个参照向量，其指导选择的过程需要⽐较解的优劣，这就需要⽤到⼀些标量函数来定量衡量⼀个解对于这个参照向量的适应度值。常⽤的标量函数包括：
- Weighted Sum Approach
- Tchebycheff Approach
- penalty-based boundary intersection (PBI) approach
Weighted Sum Approach
其中 是参照向量，其运⾏机理如下图：
进化标记这⾥需要注意，标准的Weighted Sum Approach 不能处理⾮凸问题，因为由上图可知，对于⾮凸问题，
每个参照向量的垂线与其前沿不可能相切。对于这个问题，Rui Wang 等⼈与2016年提出相对应的改进(Localized weighted sum method for many-objective optimization)，主要是约束替换范围。
min (x|λ)=(x)
g ws ∑m i=1λi f i λ
Tchebycheff Approach
其中 是参照向量，其运⾏机理如下图：
标准的Tchebycheff Approach 得到的解不均匀，为此Yutao Qi 等⼈于2014年提出⼀种解决⽅法(MOEA/D with Adaptive Weight
Adjustment)， ，通过这个参照向量的转换即可得到分布均匀的解。
min (x|λ,)=max {((x)−)}
g te z ∗λi f i z ∗i λ=(,....,)λ∗1λ1∑m i=11λi 1λm ∑m i=11λi
penalty-based boundary intersection (PBI) approach
其中 ， 如上图所⽰。⼀般来说， 是⽐较常⽤的，Yuan Yuan 等⼈提出的 算法对 的取值有较为详细的讨论(A New Dominance Relation-Based Evolutionary Algorithm for Many-Objective Optimization)。
基于分解的进化⽅法框架如下：
基于Indicator ⽅法
相⽐于IGD 指标，Hypervolume 更容易⽤来作为⼀个测度在种进化过程中⽤来选择个体，因为IGD 需要知道真实的Pareto Front 数据，⽽这对于⼀个未知多⽬标优化问题是相当困难的。
⾄于具体的多⽬标进化算法后续将会详细介绍。min (x|λ,)=+θg pbi z ∗d 1d 2d 1d 2θ=5θ−DEA θ
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议