摘要
现实世界的很多优化问题都是由多个互相作用且互相冲突的目标组成的,它的最优解不是一个解,而是一组均衡解,这组解被称为Pareto最优解集。进化算法作为一种群体智能搜索方法十分适合用来求解多目标优化问题。从20世纪80年代中期开始,进化算法就被应用于求解多目标优化问题。近年来涌现出大量的多目标进化算法,其中一些已成功应用到工程实践中,进化多目标优化也因此成为目前进化计算和多目标优化领域的一个研究热点。多目标0/1背包问题是经典的组合优化问题,具有重要的理论研究和工程应用价值,并且常常被用来测试多目标进化算法的性能。
本文旨在通过对多目标进化算法进行深入的探索和研究,针对多目标0/1背包问题设计高效的求解策略,并进行相应的实验和理论分析。本论文的研究内容主要包括以下几个方面:
(1)针对多目标0/1背包问题,提出了两种新的加权修复策略。自Zitzler等人提出SPEA算法以来,多目标进化算法被广泛地用于求解多目标0/1背包问题。多目标0/1背包问题必须满足容量约束,然而进化算法在求解过程中会产生超出容量的不可行解。最直接最有效的方法之一是通过修复操作将不可行解变成可行解,而目前最常用的基于最大化利率的修复策略并没有全面考虑物品对各个包的影响。因此,本文提出了两种新的加权修复策略,分别基于背包容量和个体约束违反程度。将这两种新的修复策略分别应用到经典算法SPEA2中来求解多目标0/1背包问题,实验结果表明新的修复策略不仅在2到4个目标的样本上收敛性有较大提高,并且分布性也有一定的改善。与此同时,在目标数超过4个的高维多目标0/1背包问题上性能也有明显提高。
(2)针对多目标优化问题,基于Minkowski距离和对各个目标值进行加权,提出了多种新的密度评估策略。多目标优化的目标就是找到一个解集。这个解集要满足两个要求,即收敛性和分布性。收敛性就是要使得到的解集在目标空间上与真正Pareto最优前沿的距离尽可能小,而分布性则是要使这个解集在目标空间尽可能均匀分布。当前多目标进化算法的设计正是围绕着这两个要求来进行的。引入Pareto支配关系是为了尽可能保证算法的收敛性,而密度函数的引入则主要是为了尽可能保证算法有更好的分布性。当然,这两方面是相互关联、相互影响的。当非支配解的数目超过归档群体大小时,就需要根据密度函数删除一部分个体。而在遗传选择时,大量支配关系相同的个体就要根据密度函数来决定其优劣。因此,密度评估策略对多目标进化算法的性能是很重要的,但对于高维多目标问题,现有密度评估策略的可扩展性却存在一定问题。为此,本文更全面地考虑目标空间上各个子目标的影响,基于Minkowski距离和对各个子目标值进行加权,提出了几种新的密度评估策略。在4到9个目标的多目标0/1背包问题样本上的实验结果表明,使用新的密度评估策略的多目标进化算法能更有效的收敛到Pareto前沿。然后,将其与本文提出的修复策略相结合,实验结果表明二者结合后使得算法收敛性有更大提高。此外,进一步将已有的基于欧氏距离与随机距离的密度评估策略相结合提出了混合密度评估策略,并用实验验证了它的有效性。
(3)针对多目标进化算法,提出了多种新的遗传选择策略。遗传选择是多目标进化算法的一个重要步骤。现有的多目标进化算法在进行遗传选择时,大都是从外部群体中来选择父代个体,并且基本是采用基于局部竞争的选择方法,如锦标赛选择等。竞争获胜的标准一般是根据适应度的大小来判断,而适应度的大小通常由个体间的Pareto支配关系和个体信息(比如密度函数)来共同决定。当目标数增多时,非支配解的数目急剧增加,外部群体中的大多数个体均为非支配解,此时哪个个体获胜完全依赖于密度函数的值,偏向于保持解集的分布性,这显然不够合理。因此,通过在锦标赛选择时加入考虑两个体间各子目标值的具体对比情况,本文提出了多种新的遗传选择策略。实验结果表明,使用新的遗传选择策略的多目标进化算法在求解超过4个目标的多目标0/1背包问题时性能有很大提高。然后,将其与本文提出的修复策略相结合,实验结果表明二者结合后对于算法收敛性有更大提高,对于算法的分布性也并没有不利的影响。
本论文以多目标优化问题为背景,对多目标0/1背包问题的修复策略、多目标进化算法中的密度评估策略、遗传选择策略进行了较为深入的研究。这不仅对多目标进化算法的研究有着重要的意义,也对多目标优化的实际应用有着重要的意义。
Many optimization problems in the real world are composed of several conflict objectives. Its optimal solution is not one but a set of solutions, and they are called the Pareto Optimal Set. As population-based global search methods, Evolutionary Algorithms (EAs) are very promising to solve the multiobjective optimization problems (MOPs). Since the mid 1980s, EAs have been applied to solve MOPs. Recently many Evolutionary Multioptimization Algorithms have been proposed, and some of them have been successfully applied in engineering. Therefore, the research of evolutionary multiobjective optimization (EMO) has become a hot research field in Evolutionary Computation community. The Multiobjective 0/1 Knapsack Problem (MOKP) is one of the most traditional combinatorial problems. It is important for theoretic research and engineering applications, and is often used to test the performance of EMOs.
The aim of this dissertation is to explore the theories and mechanisms of EMOs and to design effective strategies for MOKP, and to do the corresponding theoretic and experimental analyses. The main research works in this dissertation consist of the following aspects.
(1) For Multiobjective 0/1 knapsack problem, two novel weighted repair strategies are proposed. Since Zitzler proposed SPEA, EMO has been widely used to solve MOKP. The capacity constraints must be satisfied in MOKP but infeasible solutions will come into being when MOKP is solved by EAs. One of the most useful methods is repair strategy which can change infeasible solutions to feasible ones. However, the most widely used repair strategy which is based on maximum profit/weight ratio can not involve the different impacts of each item on all knapsacks. In this paper, two novel repair strategies are proposed, which are based on knapsack capacities and constraint violations respectively. These two novel strategies are applied in SPEA2 to solve MOKP. The experimental results show that SPEA2 with the novel repair strategies not only have much better convergence to the Pareto-optimal front but also better distribution on the test cases with two to four objectives. Meanwhile, the performance of SPEA2 with the novel repair strategies is significantly improved.
(2) For Multiobjective optimization problem, several novel density estimation strategies are proposed which are based hybrid Minkowski distances and weighted scalar sub objective values. The aim of multiobjective optimization is to find a solution set which has good convergence and distribution. Good convergence means the distance from the solution set to the Pareto optimal front is as small as possible and good distribution means the solutions are as uniform as possible. Now the design of multiobjective optimization evolutionary algorithms is to satisfy these two conditions. Pareto domination guarantees good convergence and density estimation guarantees good distribution in EMO. However, these two strategies associate and influence each other. If the number of non-dominated solutions exceeds the size of archive set, some solutions will be deleted according to the density. The solutions with the same pareto domination will be judged by their density in the genetic selection. So the density estimation strategy is very important in EMO but the scalability of currently used strategies are not good when the number of objectives becomes more than four. In this paper, the different impacts of each sub objective are much more generally considered and several novel density estimation strategies are proposed which are based Minkowski distance and weighted scalar sub objective values. The experimental results on MOKP cases with four to nine objectives show that EMO with new density estimation strategies have better convergence to the Pareto optimal front. Then they are combined with the novel repair strategies and the performance of the algorithm is obviously enhanced. Moreover, a novel hybrid density estimation strategy is proposed which is combined by Euclid distance and random distance. The experimental results also show its validity.
(3) For evolutionary multiobjective algorithm, several novel selection strategies are proposed. Genetic selection is an important step in EMO. Parent individuals are mostly selected from the archive set and the selection is usually based on competition, e.g. tournament selection. The criterion of winner depends on its fitness value which is determined by pareto relation and individual information, e.g. density function. When the objective number becomes larger, the number of non-dominated solutions will increase quickly and most of the solutions in the archive set are non-dominated. So which one will be chosen as parent just depends on density information and it is not reasonable to mainly consider its distribution. In this paper, several novel selection strategies are proposed by adopting comparison of each sub objective for two individuals. The experimental results on MOKP test cases with four to nine objectives demonstrate that the convergence of the algorithm is greatly improved by novel selection strategies. Then they are combined with the novel repair strategies to SPEA2 and the convergence of the algorithm becomes much better and the distribution is not worse.
In this dissertation, with the studies in evolutionary multiobjective optimization and multiobjective 0/1 knapsack problem, two novel repair strategies are designed for MOKP, several novel density estimation strategies and several novel genetic selection strategies are proposed for Evolutionary Multiobjective Optimization. The works in this dissertation are very important not only to the research of the multiobjective optimization evolutionary algorithms but also to the optimization applications of EMOs in the real world.
引文
王宇平,焦永昌,张福顺(2003). "解多目标优化的均匀正交遗传算法."系统工程学报18(6): 481-486.
朱学军,陈彤,薛量(2001). "多个体参与交叉的Pareto多目标遗传算法."电子学报29(1): 106-109.
崔逊学,李森,方廷健(2001). "多目标协调进化算法研究."计算机学报24(9): 978-984.
曾三友,魏巍,康立山,姚书振(2005). "基于正交设计的多目标演化算法."计算机学报28(7): 1153-1162.
张敏(2008).约束优化和多目标优化的进化算法研究.合肥,中国科学技术大学. Ph.D. Thesis
张敏,罗文坚,王煦法(2009). "一种基于正态分布交叉算子的ε-MOEA."软件学报20(2): 305-314.
谢涛,陈火旺,康立山(2003). "多目优化的演化算法."计算机学报26(8): 997-1003.
赵曙光,焦李成,王宇平,杨万海(2004). "基于均匀设计的多目标自适应遗传算法及应用." 电子学报32(10): 1723-1725,1729.
郑金华(2007).多目标进化算法及其应用.北京,科学出版社.
陈国良,王煦法,庄镇泉,王东生(1996).遗传算法及其应用.北京,人民邮电出版社.
关志华,寇纪淞,李敏强(2002). "基于ε-约束方法的增广Lagrnagina多目标协同进化算法." 系统工程与电子技术24(9): 33-37.
马清亮,胡昌华(2004). "进化算法在系统可靠性多目标优化中的应用."上海航天21(2): 7-10.
Bhaskar K (1979). "A multiple objective approach to capital budgeting." Accounting and Business Research 9: 25-46.
Brockhoff D. and Zitzler E. (2006). Are All Objectives Necessary? On Dimensionality Reduction in Evolutionary Multiobjective Optimization. Proceedings of the Conference on Parallel Problem Solving from Nature (PPSN IX). Reykjavik, Iceland, Springer. LNCS 4193: 533-542.
Chu P C and Beasley J E (1998). "A Genetic Algorithm for the Multidimensional Knapsack Problem." Journal of Heuristics 4: 63-86.
Coello C. A. Coello (2006). "Evolutionary multi-objective optimization: a historical view of the field." IEEE Computational Intelligence Magazine 1(1): 28-36.
Deb K and Saxena DK (2005). On finding Pareto-optimal solutions through dimensionalityreduction for certain large-dimensional multi-objective optimization problems.
Deb K., Mohan M. and Mishra S. (2005). "Evaluating theε-Domination Based Multi-Objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions." Evolutionary Computation 13(4): 501-525.
Deb K., Pratap A., Agarwal S. and Meyarivan T. (2002). "A fast and elitist multiobjective genetic algorithm: NSGA-II." IEEE Transactions on Evolutionary Computation 6(2): 182-197.
Deb K., Thiele L., Laumanns M. and Zitzler E. (2002). Scalable Multi-Objective Optimization Test Problems. Proceedings of the 2002 Congress on Evolutionary Computation. Honolulu, Hawaii, IEEE Service Center: 825-830.
Laumanns M., Thiele L., Deb K and Zitzler E. (2002) Combining convergence and diversity in evolutionary multi-objective optimization. Evolutionary Computation 10(3): 263-282.
Deb Kalyanmoy (2001). Multi-Objective Optimization using Evolutionary Algorithms. Chicester, UK, John Wiley & Sons.
Deb Kalyanmoy, Pratap Amrit and Meyarivan T. (2001). Constrained Test Problems for Multi-objective Evolutionary Optimization. Proceedings of the 1st International Conference on Evolutionary Multi-Criterion Optimization. Zitzler E., Deb K., Thiele L., Coello C. A. C. and Corne D. Switzerland, Springer-Verlag. LNCS 1993: 284-298.
Deb Kalyanmoy, Thiele Lothar, Laumanns Marco and Zitzler Eckart (2005). Scalable Test Problems for Evolutionary Multiobjective Optimization. Evolutionary Multiobjective Optimization. Theoretical Advances and Applications. Abraham A., Jain L. and Goldberg R. USA, Springer: 105-145.
Drechsler N, Drechsler R and Becker B (2001). Multi-objective optimization based on relation favour. EMO 2001, Springer, Berlin: 154-166.
Fieldsend J, Everson R M and Singh S (2003). "Using unconstrained elite archives for multiobjective optimization Evolutionary Computation." IEEE Trans. on Evolutionanary Computation 7(3): 305-323.
Fonseca C. M. and Fleming P. J. (1993). Genetic algorithms for multiobjective Optimization: Formulation, discussion and generalization. Procedings of the 5th International Conference on Genetic Algorithms. Forrest S. California, Morgan Kauffman Publishers: 416-423.
Geoffrion A. M. (1968). "Proper efficiency and the theory of vector optimization." Journal of Mathematical Analysis and Application 41: 491-502.
Goldberg D. E. (1989). Genetic algorithms in search, optimizationand machine learning. Reading, MA, Addison Wesley.
Gong Maoguo, Jiao Licheng, Du Haifeng and Bo Liefeng (2008). "Multiobjective Immune Algorithm with Nondominated Neighbor-based Selection." Evolutionary Computation 16(2).
Haimes Y. Y., Lasdon L. S. and Wismer D. A. (1971). "On a bicriterion formulation of the problems of integrated systems identification and system optimization." IEEE Transactions System, Man, Cybernetics 1(3): 296-297.
Hans Kellerer Ulrich Pferschy, David Pisinger (2004). Knapsack Problems, Springer-Verlag Berlin Hernández-Díaz Alfredo G., Santana-Quintero Luis V., Coello Carlos A. Coello and Molina Julián (2007). "Pareto-adaptiveε-dominance." Evolutionary Computation 15(4): 493-517.
Horn J., Nafpliotis N. and Goldberg D. E. (1994). A niched pareto genetic algorithm for multiobjective optimization. Proceedings of the First IEEE Conference on Evolutionary Computation. Piscataway, NJ, IEEE Press: 82-87.
Huband S., Barone L., While L. and Hingston P. (2005). A scalable multiobjective test problem toolkit. Proceedings of the 3rd International Conference on Evolutionary Multi-Criterion Optimization. Berlin, Germany, Springer-Verlag. LNCS 3410: 280-294.
Huband Simon, Hingston Phil, Barone Luigi and While Lyndon (2006). "A Review of Multiobjective Test Problems and a Scalable Test Problem Toolkit." IEEE Transactions on Evolutionary Computation 10(5): 477-506.
Hughes Evan J. (2005). Evolutionary Many-Objective Optimisation: Many Once or One Many? Proceedings of the 2005 IEEE Congress on Evolutionary Computation Edinburgh, Scotland, IEEE Service Center: 222-227.
Ishibuchi H and Kaige S (2003). Effects of Repair Procedures on the Performance of EMO Algorithms for Multiobjective 0/1 Knapsack Problems. Proc. of 2003 Congress on Evolutionary Computation, Canberra, Australia. Ishibuchi H and Kaige S (2003). An empirical study on the effect of mating restriction on the search ability of EM0 algorithms. Proc. of Second International Conference on Evolutionary Multi-Criterion Optimization, Faro, Portugal.
Ishibuchi H, Tsukamoto N, Hitotsuyanagi Y and Nojima Y (2008). Effectiveness of Scalability Improvement Attempts on the Performance of NSGA-II for Many-Objective Problems. GECCO’08, Atlanta, Georgia, USA.
Jaszkiewicz A (2002). "On the performance of multiple-objective genetic local search on the 0/1 knapsack problem-A comparative experiment." IEEE Trans. on Evolutionanary Computation 2002,6(4): 402-412.
Jenkins L (2002). "A bicriteria knapsack problem for planning remediation of contaiminatedlightstation sites." European Journal of Operational Research 140: 227-433.
Kang Z, Kang L. S and Zeng S.Y (2007). A New Evolutionary Decision Theory for Many-Objective Optimization Problems. .ISICA 2007, LNCS 4683: 1-11.
Knowles J. D. and Corne D. W. (2000). "Approximating the nondominated front using the pareto archived evolution strategy." Evolutionary Computation 8(2): 149–172.
Knowles J. D. and Corne D. W. (2000). M-PAES: A memetic algorithm for multiobjective optimization. Proc. of 2000 Congress on Evolutionary Computation, San Diego, USA.
Koppen M. and Yoshida K (2007). Substitute distance assignments in NSGA-II for handling many-objective optimization problems. EMO 2007, Lecture Notes in Computer Science 4403. Springer, Berlin.
Korudu P, Das S and Welch SM (2007). Multi-Objective hybrid PSO usingμ-fuzzy dominance. Proc. of the Genetic and Evolutionary Computation, GECCO 2007, New York: ACM Press.
Kostreva M, Ogryczak W and Tonkyn DW (1999). "Relocation problems arising in conservation biology." Computers and Mathematics with Applications 37: 135-150.
Kwak W, Shi Y, Lee H and Lee C.F (1996). " Capital budgeting with multiple criteria and multiple decision makers." Review of Quantitative Finance and Accounting 7: 97-112.
Praditwong K and Yao X (2007). How Well Do Multi-objective Evolutionary Algorithms Scale to Large Problems. Proc. of 2007 IEEE Congress on Evolutionary Computation, Singapore.
Purshouse Robin C. and Fleming Peter J. (2003). Evolutionary Multi-Objective Optimisation: An Exploratory Analysis. Proceedings of the 2003 Congress on Evolutionary Computation. Canberra, Australia, IEEE Press. 3: 2066-2073.
Rosenberg R. S. (1967). Simulation of genetic populations with biochemical properties. Michigan, University of Michigan. Ph. D. Thesis
Runarsson Thomas Philip and Yao Xin (2000). "Stochastic ranking for constrained evolutionary optimization." IEEE Transactions on Evolutionary Computation 4(3): 284-294.
Sato H, Aguirre HE and Tanaka K (2007). Controlling dominance area of solutions and its impact on the performance of MOEAs. EMO 2007, Lecture Notes in Computer Science 4403. Springer, Berlin
Saxena DK and Deb K (2007). Non-Linear dimensionality reduction procedure for certain large-dimensional multi-objective optimization problems: Employing correntropy and a novel maximum variance unfolding. Proc. of the 4th Int’l Conf. on Evolutionary Multi-Criterion Optimization, EMO 2007, Berlin, Springer-Verlag.
Schaffer J. David (1984). Multiple Objective Optimization with Vector Evaluated GeneticAlgorithms, Vanderbilt University.
Srinivas N. and Deb K. (1994). "Multiobjective optimization using nondominated sorting in genetic algorithms." Evolutionary Computation 2(3): 221-248.
Teng J.Y and Tzeng G.H (1996). " A multiobjective planning approach for selecting non-independent transportation investment alternatives." Transportation Research B 30: 291-307.
Veldhuizen David A. Van (1999). Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations. Department of Electrical and Computer Engineering. Ohio, Air Force Institute of Technology, Wright-Patterson AFB.
Zadeh L. A. (1963). "Optimality and nonscalar-valued performance criteria." IEEE Transactions on Automatic Control 8(1): 59-60.
Zhang Min, Luo Wenjian, Pei Xingxin and Wang Xufa (2008a). The Self-Adaption Strategy for Parameterεinε-MOEA. Proceedings of the 2008 IEEE Congress on Evolutionary Computation (CEC'2008) Hongkong, China.
Zhang Min, Luo Wenjian and Wang Xufa (2008b). "Differential Evolution with Dynamic Stochastic Selection for Constrained Optimization." Information Sciences 178(15): 3043-3074.
Zitzler E., Deb K. and Thiele L. (2000). "Comparison of multiobjective evolutionary algorithms: Empirical results." Evolutionary Computation 8(2): 173-195.
Zitzler E., Laumanns M. and Thiele L. (2002). SPEA2: Improving the strength pareto evolutionary algorithm. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Giannakoglou K. Athens, Greece: 95-100.
Zitzler Eckart and Thiele Lothar (1999). "Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach." IEEE Transactions on Evolutionary Computation 3(4): 257-271.
Zitzler Eckart, Thiele Lothar, Laumanns Marco, Fonseca Carlos M. and Fonseca Viviane Grunert da (2003). "Performance Assessment of Multiobjective Optimizers: An Analysis and Review." IEEE Transactions on Evolutionary Computation 7(2): 117-132.
Zou X.F, Chen Y, Liu M.Z and Kang L.S (2008). "A New Evolutionary Algorithm for Solving Many-Objective Optimization Problems." IEEE Transactions on Systems, Man, and Cybernetics-Part B 38(5): 1402-1412.