2022年遗传算法求解多目标问题的有关方法综述 .pdf

《2022年遗传算法求解多目标问题的有关方法综述 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法求解多目标问题的有关方法综述 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、遗传算法求解多目标问题的有关方法将目标函数综合的方法遗传算法需要一个标量的适应度信息才能进行计算，所以很自然的都会想到将所有的目标函数用加法， 乘法或者其他的各种可能想出来的数学方法综合成为一个单一目标。但是这种方法存在明显的问题，首选是在目标函数取值范围内必须能够提供精确的信息，以避免其中的一个目标函数会明显优于其他值，这就要求我们至少在某种程序上可以估计出每个目标函数的取值，而这对于现实的问题往往会是一个相当昂贵的，无法承受的过程。但是，如果将所有目标函数综合起来的方法确实可行，那它不仅仅是一个最简单的方法，而且也将是最有效的方法，因为不再需要其他需要决策者参与的交互过程。而且如果 GA算

2、法成功的找到了适应度最佳的点，那么该点至少是一个可能的最优点。1. 权重法这种方法将所有的目标函数乘以不同的权重，再加和起来作为有待优化的单一目标。kiiixf1min不同的权重将得到不同的结果，而对于如何选取权重知之甚少，所以用这权重法求解的一种方法就是采用各种不同的权重，从而得到一组解，但是这时仍然需要决策者从这些可行解中根据自己的要求做出最佳选择。需要指出的是权重系数虽然可以反应各个目标函数值的重要性，但是却并不成比例关系。如果我们希望权重可以与目标函数成比例，那就需要将它们转化成统一的单位。应用优点与缺点这种方法是采用遗传算法求解多目标问题的第一种方法。这种方法的优点就是它的效率（单纯

3、从计算量的角度考虑），同时可以得到一个很好的非劣解作为其他方法的一个初值，主要缺点则是在我们没有足够的关于此问题的信息时，无法确定合适的权重系数。此时得到的任何最优解都是权重系数的函数。大多数的研究都使用简单的线性函数，由多次不同权重的计算来生成非劣解集。这种方法非常简单，易于使用，但是有时会丢失非劣解集平面的凹陷部分1，这是一个相当严重的问题。2.目标规划法 (Goal Programming) Charnes 2 and Ijiri 3 提出了线性模型的目标规划法，在解决工业问题的计算中起了相当重要的作用。在这种方法中，决策者需要确定每一个目标函数所要达到的值，这些要求作为额外的约束条件引

4、入到问题中去。于是目标函数就转化为最小化这些目标函数值与相应要求值之间的差距。最简单的表述形式是4: kiiiTxf1)(min更常见的一种形式是再在上式基础上进行加权5，也常称通用用目标规划法6, 7，这种方法也被一些人称为目标向量优化8. 优点与缺点如果所决定的目标点在可行域内，这种方法可以得到一个非劣解，同时由于明确了所要名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 搜索的目标，所以计算效率很高。但是由于此目标是由决策者

5、给出的，并且由他决定权重，因此需要预告可以知道搜索空间的形关。并且，如果可行域很难接近，那么这种方法的效率将会变得非常之低。另外就是这种方法也许更加适用于目标函数为线性或分段线性的情况，因为有现成的计算程序。3. Goal Attainment 由决策者给出各个目标函数值f1,f2, fk低于或高于预期值b1, b2,bk时的权重向量12 ,k，最优解 x为求解以下问题所得到的结果：Minimize subject to: 0)(xgjj=1,2,.,m)(xfbiiii=1,2, k需要指出的是得到的最优解将向决策者表示他所预期的目标是否可以得到。为负值表明目标可以达到，而正值则相反。优点与

6、缺点Goal attainment 法有不少缺点，其中最主要的一点就是在计算过种中有可能会出现错误的选择。例如，假设有两个点的目标函数值有一个相同，而另一个有差别，但却可能有相同的 goal-attainment 值，这意味着对于GA算法来说二者没有优劣的差别。4. Constraint 法这种方法提出对所有目标函数中首要的一个进行最小化，而将其余各个目标函数视为在某种程度上 i可以违反的约束条件，然后通过选取不同的i可以得到非劣解集。(1)对第r个目标函数进行最小化：)(min)(*xfxfrFxr附加约束条件为：iixf)(i=1,2, k, ir (2)对于不同的 i重复上述过程，直到得

7、到一个决策者满意的解为止。根据问题的需要也可能要求选取不同的目标函数，并且可以先用其他的方法针对每一个目标函数进行优化，求出它的最佳值，以此作为参考来确定i。Ritzel 和Wayland 1 提出优化过种中将除了某一个目标函数之外的其余各项均设为常数，。优点与缺点最明显的缺点就是耗时太多，而且如果某个问题具有太多目标函数时，针对其进行编码时可能会有很大困难，甚至不可能。这种方法还试图找到一些较非劣解稍次的解，但是在某些实际问题（如结构优化）中是不合适的。尽管如此，该方法相对简单，使得在研究的最初阶段还是很常见的。为了克服在将各个目标函数进行综合时出现的各种问题，相应的又提出了一些方法，这些方

8、法一般都是基于population policies，或者对目标函数进行特定的处理。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 5.A Non-Generational Genetic Algorithm这是由 Valenzuela-Rend on和Uresti-Charre9 提出来的一种方法， 在这种方法里每个个体的适应度都是在增长的，此方法的思想来源于Learning Classifier Systems(LGS) 1

9、0，那篇文章的研究表时每次只将个体中最差的一个替换掉的non-generational 的遗传算法较之传统的遗传算法要好。在将这种方法应用到多目标优化时，Valenzuela-Rend on和Uresti-Charre 将目标函数值的比较与各个点之间的分布情况作为两个指标进行线性综合，得到一个单一的优化目标。Carlos 11 针对这一方法中两个指标的计算做了相应的修改，得到的算法比原来有所改进。优点与缺点这种方法实际上只是Bentley 和 Wakefield 12 所提出权重平均排序法（weighted average ranking- WAR）的一种更为精细的版本，主要的优点就在于它可以

10、用一种效率较高的方法来得到较好的解的分布。主要缺点是没有办法将决策者对于各个指标不同的关心程序加入进去，因此会影响对于实际问题的应用，而且也没有提供明确的确定各个附加参数的方法，往往需要进行很精细的调试才行。基于Pareto 非劣解概念的方法Goldberg 10 首先提出在多目标遗传算法的优化中引入基于Pareto 非劣解概念的适应度，下图给出这种方法的基本思路，对个体的优劣性进行排序可以分为几个集合，然后选择父代个体，在以上信息的指引下使整个种群向着Pareto 解的最前线移动。为了防止 GA收敛于最前沿的某一个点，在后来的研究中Goldberg 还引入了 niche 的概念。优点与缺点基

11、于 Pareto 非劣解概念进行排序的方法最大的缺点在于，没有一种有效的算法在一组可行解中确定各个非劣解集合8。 传统的算法在个体数增加和目标数增多时性能下降很明显。而且引入 niche概念后其中的参数如何确定也是个问题，而整个算法的性能在很大程度上又依赖于这个参数的选择。但是无论如何，基于此方法的算法仍然是最合适的用来生成整个 Pareto 非劣解前沿算法， 它的主要优点就在于此方法不用对于非劣解前沿的形状或连续性没有特殊的要求，而这对于纯粹的数学规划方法却是很严重的问题。1 Multiple Objective Genetic Algorithm名师资料总结 - - -精品资料欢迎下载 -

12、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - Fonseca 和 Fleming 13 提出了基于一代个体数量的排序方法。如果个体xi在 t 这一代有tip个体优于它，那么它的rank 就是：tiiptxrank1),(所有的非劣解的 rank都为1， 而那些较次的点则根据在trade-off 平面上对应域的种群密度加上一个惩罚函数。适应度的计算通过如下方法进行13：1.根据各个点的 rank 对个体进行排序2.用Goldberg 10 提出的方法，计算从最优到最差各点

13、和适应度。3.将具有相同 rank 的各点的适应度进行平均，这样它们将具有相同的被选中的概率。这一过程可以使在保证适当的选择率的情况下整个种群的适应度是个定值。Goldberg 14 指出这种分段式的适应度计算法有可能使算法出现早熟的现象。为了防止这种情况， Fonseca 和 Fleming 提出引入 niche 信息的方法，与那些基于变量的方法不同，他们提出的方法是基于目标函数值的。优点与缺点MOGA 主要的不足是如果niche 信息是基于目标函数的，那么两个具有相同目标函数向量的不同的个是无法在同一代种群是存在的，这显然是我们不希望看到的，因为这样两个解可能恰恰就是决策者想要得到的结果。

14、这种方法的优点则是效率较高，而且易于实现。2 Non-Dominated Sorting Genetic AlgorithmNon-dominated Sorting Genetic Algorithm (NSGA)是由Srinivas 和 Deb 15 提出的，这种方法对个体做很多层次的分类。在进行选择前， 整个种群先根据非劣解性进行排序，所有的非劣解个体都被归为一类，同时指定一个虚假的适应度（适应度的值可以根据这些个体占种群个体数的比例来给出）。为了保证种群的分布，这些个体都具有相同的适应度。然后这一部分个体被取出其余的个体再采用相同的方法进行分类，直到所有的个体都被分类完毕。 然后采用随

15、机的方法选出个体，因为在最前沿的个体具有最大的适应度，所以被传递到下一代的可能性也就越大。优点与缺点这种方法可以搜索非劣解区域，而且可以使种群很快收敛到这一区域。本算法效率的集中在那个虚假的适应度上，可以解决目标函数为任意数量的问题16，无论是最大化还是最小化。 同时由于是在变量空间进行比较，所以可以允许具有相同目标函数的不同点的存在。有些研究者 8提出这种算法的主要缺点是相对MOGA 而言效率较低 （不仅仅是计算速度，也包括所生成Pareto 非劣解前沿的质量），而且也更依赖于，但也有些研究表时它可以得到在Pareto 非劣解前沿很好的一个分布。3 Niched Pareto Genetic

16、 AlgorithmHorn 和 Nafpliotis 17 提出一个基于 Pareto 概念的对比选择方法。 与两两比较的方法不同，这种方法同时要引入种群中其他的一些个体作为参考（大多数在10个左右），在这种比较的情况下如果两个个体还是没有优劣的区分，那才将它们的适应度进行平均18 。与其他方法相比，这个种方法的种群要明显大很多，所以在种群中出现的niche 可以抵消选择个体时噪音的影响18 。 Horn 和 Nafpliotis 17 更提出了将目标函数空间和变量空间结合起来对适应度进行分配的方法，他们称之为nested sharing 。名师资料总结 - - -精品资料欢迎下载 - -

17、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 优点与缺点这种方法并不是整个种群中进行Pareto 非劣解的选择， 而仅仅是在每次迭代中的一段进行，所以运行起来很快， 而且可以在很多代都保证一个很好的非劣解的前沿区域8。缺点就是要选择一个很好的参考个体的数目，使得方法在实际应用中较为复杂。 关于模糊数学在多目标遗传算法中的应用也已经有一定的研究，Brian J19,20 提出了用隶属度函数的形式来计算适应度：NiiffNF1)(1)()()()(minminiiiiiiiiii

18、EOfEOfSffEOf0)()()(iiiiiiffEOfEO)()()()(maxmaxiiiiiiiiiiEOffEOSffEOf其中 Oi为各个目标函数的实验值，Ei为可接受误差，Smin和Smax是系数。 在某些情况下不同的目标函数对于决策者来说具有不同的重要性，综合目标进行优化的方法可以利用权重来表达这方面的信息，而对于基于Pareto 非劣解概念的排序法却不能直接提供相应的对策。Fonseca13 提出用一个效用函数结合MOGA21, 22来处理，需要有一个从决策者到算法的反馈过程，这个过程也可以由专家系统来完成13 ，但是这种方法仍然要求决策者事先就知道有关各个目标函数取值范围

19、的信息，这是极其复杂的过程，有时几乎就是不可能实现的。Bentley 和Wakefield 12 提出用权重来预计已经得到点的重要性程度，Greenwood 30则将目标综合法与排序法结合起来，可以在某种程度上定义对目标函数的偏好，这个定义过程也可以由GA自己来完成， 而不用决策者的参与，但是决策者仍然要预先确定所以搜索的非劣解平面的区域，从而才能限定GA在其中进行搜索。Voget 100 提出的方法通过预先设定的目标来设计一个模糊控制，利用它来确定选择率，在实际应用中它的确可以有效地减小与预期值之间的偏差。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

20、- - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 1. Brian J. Ritzel, J. Wayland Eheart, and S. Ranjithan. Using genetic algorithms to solve a multiple objective groundwater pollution containment problem. Water Resources Research, 30(5):1589-1603, may 19942. A. Charnes and W. W. Coope

21、r. Management Models and Industrial Applications of Linear Programming , volume 1. John Wiley, New York, 1961.3. Y. Ijiri. Management Goals and Accounting for Control.North-Holland, Amsterdan, 1965.4. L. Duckstein.Multiobjective Optimization in Structural Design: The Model Choice Problem. In E. Atre

22、k, R. H. Gallagher, K. M. Ragsdell, and O. C. Zienkiewicz, editors, New Directions in Optimum Structural Design, pages 459-481. John Wiley and Sons, 1984.5.Y. Y. Haimes, W. Hall, and H. Freedman. Multi-Objective Optimization in Water Resources Systems: The Surrogate Trade-Off Method. Elsevier, Amste

23、rdam, 1975. 6.J. P. Ignizio. Goal Programming and Extensions . Heath, Lexington, Massachusetts, 1976. 7.J. P. Ignizio. The determination of a subset of efficient solutions via goal programming. Computing and Operations Research, 3:9-16, 1981. 8.Carlos Artemio Coello Coello. An Empirical Study of Evo

24、lutionary Techniques for Multiobjective Optimization in Engineering Design. PhD thesis, Department of Computer Science, Tulane University, New Orleans, LA, apr 1996. 9.Manuel Valenzuela-Rendon and Eduardo Uresti-Charre. A Non-Generational Genetic Algorithm for Multiobjective Optimization. In Thomas

25、B.ack, editor, Proceedings of the Seventh International Conference on Genetic Algorithms , pages 658665, San Mateo, California, July 10.David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, Reading, Massachusetts, 1989.11.Carlos C.H. B

26、orges and Helio J.C. Barbosa. A Non-generational Genetic Algorithm for Multiobjective Optimization , In 2000 Congress on Evolutionary Computation, San Diego, California, July 2000. IEEE Service Center12. P. J. Bentley and J. P. Wakefield. Finding Acceptable Solutions in the Pareto-Optimal Range usin

27、g Multiobjective Genetic Algorithms. In Proceedings of the 2nd On-Line World Conference on Soft Computing in Engineering Design and Manufacturing (WSC2), page http:/ June1997. 13. Carlos M. Fonseca and Peter J. Fleming. Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and

28、Generalization. In Stephanie Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms, pages 416-423, San Mateo, California, 1993.University of Illinois at Urbana-Champaign, Morgan Kau_man Publishers. 14. David E. Goldberg and Kalyanmoy Deb. A comparison of selection

29、schemes used in genetic algorithms. In G.J. E. Rawlins, editor, Foundations of Genetic Algorithms , pages 69-93. Morgan Kaufmann, San Mateo, California, 1991. 15. N. Srinivas and K. Deb. Multiobjective optimization using nondominated sorting in genetic algorithms. Technical report, Department of Mec

30、hanical Engineering, Indian Institute of Technology, Kanput, India, 1993. 16. N. Srinivas and Kalyanmoy Deb. Multiobjective Optimization Using Non-dominated 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - Sorting in Genetic Algorithms. Evol

31、utionary Computation , 2(3):221-248, fall 1994. 17. J. Horn and N. Nafpliotis. Multiobjective Optimization using the Niched Pareto Genetic Algorithm. Technical Report Illi GAl Report 93005, University of Illinois at Urbana-Champaign, Urbana, Illinois, USA, 1993. 18. David E. Goldberg and J. Richards

32、on. Genetic algorithm with sharing for multimodal function optimization. In J. J. Grefenstette, editor, Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms , pages 41-49. Lawrence Erlbaum, 1987 19.Brian J. Reardon. Fuzzy Logic vs. Niche

33、d Pareto Multiobjective Genetic Algorithm Optimization: Part II. A Simplified Born-Mayer Problem, Technical Report LA-UR-97-3676, Los Alamos National Laboratory, Los Alamos, New Mexico, September 199720. Brian J. Reardon. Optimization of Densification Modeling Parameters of Beryllium Powder using a

34、Fuzzy Logic Based Multiobjective Genetic Algorithm, Technical Report LA-UR-98-1036, Los Alamos National Laboratory, Los Alamos, New Mexico, March 199821. Carlos M. Fonseca and Peter J. Fleming. An overview of evolutionary algorithms in multiobjective optimization. Technical report, Department. of Au

35、tomatic Control and Systems Engineering, University of Shefield, Shefield, U. K., 1994. 22. Carlos M. Fonseca and Peter J. Fleming. An overview of evolutionary algorithms in multiobjective optimization . Evolutionary Computation , 3(1): 1-16, Spring 1995. 23. Garrison W. Greenwood, Xiaobo Sharon Hu,

36、 and Joseph G. DAmbrosio. Fitness Functions for Multiple Objective Optimization Problems: Combining Preferences with Pareto Rankings. In Richard K. Belew and Michael D.Vose, editors, Foundations of Genetic Algorithms 4 , pages 437-455. Morgan Kaufmann, San Mateo, California, 1997. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -