多目标进化优化

目录

1.多目标优化问题数学模型及最优解

2.Pareto 最优解

3.解的支配关系

4.用进化算法解决多目标优化问题

参考文献

---

 

        在许多实际问题中，我们常常要处理的数学模型不止有一个目标函数。例如在产品 加工与配送系统中，通常要求加工和配送的成本尽可能低，而所花的时间尽可能少，从 而使总利润最大。有些多目标优化问题中各个目标之间会有冲突，无法同时取得最优， 例如工人的工资和企业的总利润。

        以遗传算法为代表的许多进化算法，具有生成多个点并进行多方向搜索的特征，因 此非常适合求解这种最优解的搜索空间非常复杂的多目标优化问题。

1.多目标优化问题数学模型及最优解

        多目标优化问题是在给定约束条件的前提下，求多个目标函数的最大或最小的问 题。一般可表述为如下形式： 

         这里，zk = fk(x), k = 1, 2, · · · , r 是 r 个线性或非线性的目标函数。有的可能是最大化目标函数，有的可能是最小化目标函数。为了方便处理，可以把各目标函数统一换为最小化或最大化。多个目标之间可能会拥有不同的单位，也可能在优化某个目标时损害其他目标。但这并不意味着多目标优化问题可能没有最优解，事实上是可以有的，为了求出比较合理的解，这里引入多目标优化问题的合理解集——Pareto 最优解 (pareto optimal solution)。

2.Pareto 最优解

        在求解单目标问题时，可以在所有候选解中选出唯一最好的解。但是在多目标优化问题里，由于各个目标之间可能存在冲突，所以最优解不一定只有一个。我们如下定义多目标的最优解：

 

 

         由上面的定义可知，在目标空间 S 中强帕累托最优解均落在粗曲线上;弱帕累托最优解则都落在细的直线上。
        值得一提的是，我们常常习惯把强 Pareto 最优解简称为 Pareto 最优解。另外，Pareto 最优解又称为“非支配解”。显然若 X∗ 是强非支配的，那么它同时也是弱非支配的。下面我们就仔细研究解的支配关系。

3.解的支配关系

         上面的关系很容易混淆一点：“非支配”不是指“不构成支配”，而是指“不被支 配”。“非支配”的反义是“被支配”。

4.用进化算法解决多目标优化问题

        下面展示一种经典的基于 Pareto 的多目标进化算法的算法流程：

         进化算法如遗传算法、粒子群算法、差分进化算法等都可以很好地解决多目标优化 问题。以遗传算法为例，目前具有代表性的多目标优化遗传算法按历史进程分类如下：

        1) 第 1 代：帕累托排序法。

        向量评价遗传算法 (vector evaluated genetic algorithms, veGA)[1]

        2) 第 2 代：非支配排序 + 保持种群多样性。

        多目标遗传算法 (Multiobjective Genetic Algorithm, moGA)[2]

        非支配排序多目标遗传算法 (non-dominated sorting genetic algorithm, nsGA)[3]

        3) 第 3 代：多目标函数加权；改进非支配排序选择；基于分解；基于评价指标；等等。

        随机权重遗传算法 (random weight GA, rwGA)[4]

        适应性权重遗传算法 (adaptive weight GA: awGA)[5]

        Pareto 强度进化算法 II(strength Pareto E A II, spEA-II)[6]

        非支配排序遗传算法 II(non-dominated sorting G A II, nsGA-II)[7]

        基于超体积作为选择指标的 EMO 进化优化算法 [8]

        交互式适应性权重遗传算法 (interactive adaptive weight GA, i-awGA)[9]

        基于分解的多目标进化算法 (A Multiobjective Evolutionary Algorithm Based on Decomposition, MOEA/D)[10]

        4) 第 4 代：基于参考点的多目标进化优化算法：

        基于非支配排序及参考点的 NSGA III 算法 [11]

        由参考向量引导的进化优化算法 (Reference vector guided evolutionary algorithm, RVEA)[12]

        实际上，以上划分的界限是不那么明显的，也不存在一种绝对最优、全面领先其他 的多目标进化优化算法，各种算法各有优劣，各有擅长之处。除此之外，还有难以数尽 的成百上千中改进的多目标进化优化算法，这里就不一一赘述了。

        对于一个具体的多目标进化算法 (Multi-objective Evolutionary Algorithm : MOEA) 而言，如何构造非支配集，采用什么策略来调整非支配集的大小，如何提高非支配集中解的分布性和提高收敛速度，是决定其算法性能的重要内容，这些也是当前相关研究的热点。

参考文献

[1] Schaffer J D. Multiple objective optimization with vector evaluated genetic algorithms[C]. Proceedings of 1st International Conference on Genetic Algorithms and Their Applications, p. 93-100, 1985.

[2] Fonseca C M, Fleming P J. Genetic algorithms for multiobjective optimization: formulation, discussion and generalization[C]. Proceedings of 5st International Conference on Genetic Algorithms and Their Applications, pp. 416-423, 1993.

[3] Srinivas N, Deb K. Multiobjective function optimization using nondominated sorting genetic algorithms[M]. Evlutionary Computation, Chapter 3, pp. 221-248, 1995.

[4] Ishibuchi H,Murata T. A multiobjective genetic local search algorithm and its application to flowshop scheduling[J]. IEEE Transactions on Systems, Man and Cybernetics, vol. 28, no, 3,pp, 392-403,1998.

[5] Gen M. Cheng R. Genetic Algorithms and Engineering Optimization[M]. New York, John Wiley & Sons, 2000.

[6] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization[C]. Proceedings of the EUROGEN Conference, pp. 95-100,2002.

[7] Deb K, Pratap A, Agarwal S, Meyarivan T. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, val, 6, no.2, pp, 182-197,2002.

[8] Emmerich M , Beume N , Naujoks B . An EMO Algorithm Using the Hypervolume Measure as Selection Criterion[M]// Evolutionary Multi-Criterion Optimization. Springer Berlin Heidelberg, 2005.

[9] Lin L, Gen M. Bicriteria Network Design Problem Using Interactive Adaptive-weight GA and Priority-based Encoding Method[J]. IEEE Trans, on Evolutionary Computation, 2006.

[10] Zhang Q , Li H . MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation, 2008, 11(6):712-731.

[11] Deb K , Jain H . An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4):577-601.

[12] Cheng R , Jin Y , Olhofer M , et al. A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2016:1-1