多目标优化1

1.1 多目标优化问题的历史

现实中存在大量需要同时优化多个目标的问题（Multi-objective Optimization Problem,MOP）

 鉴于多目标优化问题在科学研究和实际应用中普遍存在，因此研究该问题的求解具有重要的现实意义。

多目标优化问题最早在经济和管理科学中得以研究。早期称多目标优化为多准则决策或多属性决策。多目标优化起源可以追溯到经济学家A.S关于经济平衡和F.Y.E对均衡竞争的研究。意大利经济学家L.P在1896年在其关于经济福利的著作中最早提出了多目标优化问题以及最优解的均衡状态。

 1.2 多目标优化问题的求解方式

多目标优化问题的求解方式：

1）早期（20世纪50年代初-20世纪80年代中期）直接搜索方法

      主要使用运筹学和数学上的理论和方法，例如

约束法 ：由 Marglin 于 1967 年提出，将 MOP 问题转化为带约束的单目标优化问题 (SOP)

(优点：通过设置不同的 获得不同的Pareto 最优解，可以求解非凸问题。

  缺点：获得的解对 的依赖性较大，目标增多，需要选择  的信息会更多。）

       最小-最大化：通过最小化 各目标值与预设的目标值之间的最大偏差来求解MOP。

2）多目标进化算法(MOEA)：群体搜索算法

     进化算法(EA)是一类模拟生物自然选择与自然进化的随机搜索算法，因其适应于求解高度复杂的非线性问题得到了广泛应用。

     1985 年，David Schaffer 首次在机器学习中实现了向量评估遗传算法(VEGA)，其被视为利用进化算法求解MOP问题的开创性工作。

     1989年，David Goldberg 在其著作中，提出了用进化算法实现多目标技术的优化技术。

1.3 MOEA的分类

按照进化机制的不同，MOEA可分为：基于分解的MOEA 、基于支配关系的MOEA、基于指标的MOEA 、新的进化机制的MOEA。

A. 基于分解的MOEA

     聚合函数方法，将所优化的子目标组合或聚集为单个目标，进而求解单目标优化问题。

     张青富等人，基于分解的思想，将数学规划方法和进化算法结合，提出了基于分解的多目标进化算法(MOEA/D,07)

     Ishibuchi 等人提出了在不同的搜索阶段使用不同聚类函数的方法 (2011)

     李珂等人将MOEA/D与蚁群优化结合，提出了MOEA/D-ACO（2013）

     喻果基于MOEA/D框架，提出了一种偏好多目标优化方法 (2015)

B. 基于支配关系的MOEA

    利用基于Pareto的适应度分配策略，从当前进化种群中找出所有非支配个体。

  （第一代多目标进化算法）

     1989年，Goldberg等人提出了非支配排序和小生境技术来解决MOP问题。

     后来基于这些思想提出了MOGA,NSGA,NPGA等

   （第二代多目标进化算法）

     NSGA-II，强度Pareto进化算法(SPEA)和改进版SPEA2，Pareto存档的进化策略(PAES)等。

C. 基于指标的MOEA

     使用性能评价指标来引导搜索过程和对解的选择过程，如IBEA,SMS-EMOA，基于超体积等算法。

D. 新的进化机制

  基于粒子群优化（PSO）的多目标粒子群优化算法 (MOPSO)；

  基于分布式估计算法(EDA)的多目标分布式估计算法RM-MEDA；

  基于不同机制的相混合的MOEA算法。

1.4 高维多目标优化问题

MOEA在解决目标个数较少的问题时具有较好的性能，当目标个数大于等于4时，这些算法的性能会出现不同程度

的下降，开销也会增长。

目前研究：

1）改进的支配关系

    拓展解的支配区域来提升每个解支配其他解的概率。如:  GPO支配

               对目标空间划分超网格来增加支配概率。                 如：grid支配

               利用模糊逻辑来定义强支配关系。                            如：自适应模糊支配

               基于目标向量角度的强支配关系SDR

               利用基于目标分解算法中所使用的权值向量来定义新的支配关系，如RP支配和支配

2）修改密度估计策略

    基于变换的密度估计方法，SDE。

    基于拐点的进化算法KnEA。

3）目标降维

    将最大方差展开方法与PCA结合的非线性目标降维方法。

    将高维多目标降维问题视为一个3-目标优化问题。

    将冗余的目标加权成一个新的目标给予优化。

4）基于聚合的方法

    多重单目标Pareto采样方法MSOPS。

    带约束的总体适应度排序算法 EFR-RR。

    加权和标量方法局部优化。

5）基于性能评估的方法

     HypE                        HV

     GDE-MOEA             GD

     MOMI-II                    R2

     MaOEA/IGD             IGD

     SRA                          SDE，

6）基于参考点集 

      从历史群体和当前种群中选择解点构造参考点集合，如：TAA，Two-Arch2。

      基于预设参考点的，如：NSGA-III，TC-SEA，REF-I-MOP。

      自适应方式产生参考点，如：RPEA，PaRP/EA。

7）基于偏好的

      加入决策者(DM)的偏好信息，讲解集中在DM感兴趣的区域(ROI)。

      r-占优方法，r-NSGAII，G-RVEA 等。