面向复杂多目标优化问题的进化算法研究

现实世界的大量工业生产和设计问题都可以建模成多目标优化问题（Multiobjective Optimization Problem, MOP）。多目标优化问题通常需要同时优化多个相互冲突的目标，因此其最优解为一组相互权衡的解集（称为帕累托最优解集）而非单一解。进化算法是一种群体智能优化方法，它能在一次运行中能得到一组解，且不依赖于问题的数学性质。因此，进化算法已经成为求解多目标优化问题的主流方法。
现实世界中存在一类含有“支配抵抗解（Dominance-Resistant Solution, DRS）”的多目标优化问题（称为DRS-MOP）。支配抵抗解不是帕累托最优解，但其通常很难被其它解支配并且具备较高的多样性。因此，支配抵抗解的存在，给进化算法在搜索多目标优化问题的帕累托解集过程中平衡收敛性和多样性带来了严重的挑战。本论文针对DRS-MOP，对其性质和相应的求解进化算法展开研究。主要贡献总结如下：
（1）本文首先就支配抵抗解与极凸帕累托前沿边界解之间存在的困境展开研究。本文通过对DRS-MOP 进行分析和调研，总结了此类问题的性质和解决策略。此外通过设计一个两目标的问题来揭示在此类问题上，存在消除支配抵抗解和保留极凸帕累托前沿边界解的困境。最后本文提出了一个可拓展的测试问题对以上策略进行了评价和总结。
（2）本文就非均衡问题中的支配抵抗解展开研究，提出了一种可以同时兼顾种群多样性和收敛性的算法。非均衡问题是指在实际的优化过程中，存在一部分解较难搜索到或者搜索到之后较难维持的一类问题。但是支配抵抗解对算法的多样性维持机制较为敏感，因此在处理非均衡问题时，往往会使得部分解的“支配抵抗”现象更加严重。基于此，本文提出了一种多目标进化算法——MOEA/D-OMDEA（Multi-objective Decomposition Evolutionary Algorithm with Objective Modificationbased Dominance and External Archive），该算法使用一种新的松弛支配机制，同时结合了M2M 分解策略和归档集选择策略。最后该算法与六个主流算法进行比较，通过数值实验结果表明，本文所提出的算法相较于对比算法更加优异。

[1] MARLER R T, ARORA J S. Survey of multi-objective optimization methods for engineering[J]. Structural and Multidisciplinary Optimization, 2004, 26: 369-395.

[2] GUNANTARA N. A review of multi-objective optimization: Methods and its applications[J].Cogent Engineering, 2018, 5(1): 1502242.

[3] KONAK A, COIT D W, SMITH A E. Multi-objective optimization using genetic algorithms:A tutorial[J]. Reliability Engineering & System Safety, 2006, 91(9): 992-1007.

[4] DEB K, DEB K. Multi-objective optimization[M]//Search Methodologies: Introductory Tutorialsin Optimization and Decision Support Techniques. Springer, 2013: 403-449.

[5] DUAN Z, SUN H, WU C, et al. Multi-objective optimization of the aircraft environment controlsystem based on component-level parameter decomposition[J]. Energy, 2022, 245: 123330.

[6] PRATS X, PUIG V, QUEVEDO J. A multi-objective optimization strategy for designing aircraftnoise abatement procedures. Case study at Girona airport[J]. Transportation Research Part D:Transport and Environment, 2011, 16(1): 31-41.

[7] CAI Y, RAJARAM D, MAVRIS D N. Multi-mission multi-objective optimization in commercialaircraft conceptual design[C]//AIAA Aviation 2019 Forum. 2019: 3577.

[8] HUANG H Z. Fuzzy multi-objective optimization decision-making of reliability of series system[J]. Microelectronics Reliability, 1997, 37(3): 447-449.

[9] MENG K, LOU P, PENG X, et al. Multi-objective optimization decision-making of quality dependentproduct recovery for sustainability[J]. International Journal of Production Economics,2017, 188: 72-85.

[10] RIDHA H M, GOMES C, HIZAM H, et al. Multi-objective optimization and multi-criteriadecision-making methods for optimal design of standalone photovoltaic system: A comprehensivereview[J]. Renewable and Sustainable Energy Reviews, 2021, 135: 110202.

[11] NGATCHOU P, ZAREI A, EL-SHARKAWI A. Pareto multi objective optimization[C]//Proceedings of the 13th International Conference on, Intelligent Systems Application to PowerSystems. IEEE, 2005: 84-91.

[12] BRANKE J, DEB K, DIEROLF H, et al. Finding knees in multi-objective optimization[C]//Parallel Problem Solving from Nature-PPSN VIII: 8th International Conference, Birmingham,UK, September 18-22, 2004. Proceedings 8. Springer, 2004: 722-731.

[13] WANG G G, SHAN S. An efficient pareto set identification approach for multi-objective optimizationon black-box functions[C]//International Design Engineering Technical Conferencesand Computers and Information in Engineering Conference: volume 46946. 2004: 279-291.

[14] JIN Y. Multi-objective machine learning: volume 16[M]. Springer Science & Business Media,2006.

[15] ZHANG J, HUANG Y, WANG Y, et al. Multi-objective optimization of concrete mixture proportionsusing machine learning and metaheuristic algorithms[J]. Construction and BuildingMaterials, 2020, 253: 119208.

[16] ZOU F, YEN G G, TANG L, et al. A reinforcement learning approach for dynamic multiobjectiveoptimization[J]. Information Sciences, 2021, 546: 815-834.

[17] WIEGAND S, IGEL C, HANDMANN U. Evolutionary multi-objective optimisation of neuralnetworks for face detection[J]. International Journal of Computational Intelligence and Applications,2004, 4(03): 237-253.

[18] BRAUERS W K. Optimization methods for a stakeholder society: a revolution in economicthinking by multi-objective optimization: volume 73[M]. Springer Science & Business Media,2003.

[19] SINDHYA K, MIETTINEN K, DEB K. A hybrid framework for evolutionary multi-objectiveoptimization[J]. IEEE Transactions on Evolutionary Computation, 2012, 17(4): 495-511.

[20] HERABAT P, TANGPHAISANKUN A. Multi-objective optimization model using constraintbasedgenetic algorithms for Thailand pavement management[J]. Journal of the Eastern AsiaSociety for Transportation Studies, 2005, 6: 1137-1152.

[21] MEI B, BARNOON P, TOGHRAIE D, et al. Energy, exergy, environmental and economic analyzes(4E) and multi-objective optimization of a PEM fuel cell equipped with coolant channels[J]. Renewable and Sustainable Energy Reviews, 2022, 157: 112021.

[22] KHARRICH M, MOHAMMED O H, ALSHAMMARI N, et al. Multi-objective optimizationand the effect of the economic factors on the design of the microgrid hybrid system[J]. SustainableCities and Society, 2021, 65: 102646.

[23] HIROYASU T, MIKI M, KAMIURA J, et al. Multi-objective optimization of diesel engineemissions and fuel economy using genetic algorithms and phenomenological model[J]. SAEpaper, 2002, 78.

[24] MAYER M J, SZILÁGYI A, GRÓF G. Environmental and economic multi-objective optimizationof a household level hybrid renewable energy system by genetic algorithm[J]. AppliedEnergy, 2020, 269: 115058.

[25] HAMDY M, HASAN A, SIREN K. Applying a multi-objective optimization approach for designof low-emission cost-effective dwellings[J]. Building and Environment, 2011, 46(1): 109-123.

[26] HORI K, KIM J, KAWASE R, et al. Local energy system design support using a renewableenergy mix multi-objective optimization model and a co-creative optimization process[J]. RenewableEnergy, 2020, 156: 1278-1291.

[27] ALEXANDROPOULOS S A N, ARIDAS C K, KOTSIANTIS S B, et al. Multi-objective evolutionaryoptimization algorithms for machine learning: A recent survey[J]. Approximation andOptimization: Algorithms, Complexity and Applications, 2019: 35-55.

[28] DEB K, GOEL T. A hybrid multi-objective evolutionary approach to engineering shape design[C]//Evolutionary Multi-Criterion Optimization: First International Conference, EMO 2001Zurich, Switzerland, March 7–9, 2001 Proceedings 1. Springer, 2001: 385-399.

[29] DEB K, GUPTA H. Searching for robust Pareto-optimal solutions in multi-objective optimization[C]//Evolutionary Multi-Criterion Optimization: Third International Conference, EMO2005, Guanajuato, Mexico, March 9-11, 2005. Proceedings 3. Springer, 2005: 150-164.

[30] MA H, WEI H, TIAN Y, et al. A multi-stage evolutionary algorithm for multi-objective optimizationwith complex constraints[J]. Information Sciences, 2021, 560: 68-91.

[31] 林武. 面向复杂多目标优化问题的进化算法研究[D]. 深圳大学, 2020.

[32] 马小姝, 李宇龙, 严浪, 等. 传统多目标优化方法和多目标遗传算法的比较综述[J]. 电气传动自动化, 2010, 32(3): 48-50.

[33] 朱庆灵. 面向进化多目标优化的进化操作与算法的研究[D]. 深圳大学, 2016.

[34] SCHAFFER J D. Multiple objective optimization with vector evaluated genetic algorithms[C]//Proceedings of the first International Conference on Genetic Algorithms and their Applications,1985. Lawrence Erlbaum Associates. Inc., Publishers, 1985.

[35] LI H, ONG Y S, GONG M, et al. Evolutionary multitasking sparse reconstruction: Frameworkand case study[J]. IEEE Transactions on Evolutionary Computation, 2018, 23(5): 733-747.

[36] ZHANG Y, GONG D W, CHENG J. Multi-objective particle swarm optimization approachfor cost-based feature selection in classification[J]. IEEE/ACM Transactions on ComputationalBiology and Bioinformatics, 2015, 14(1): 64-75.

[37] LI J Q, PAN Q K, LIANG Y C. An effective hybrid tabu search algorithm for multi-objectiveflexible job-shop scheduling problems[J]. Computers & Industrial Engineering, 2010, 59(4):647-662.

[38] ZHAO X, GAO X S, HU Z C. Evolutionary programming based on non-uniform mutation[J].Applied Mathematics and Computation, 2007, 192(1): 1-11.

[39] 陈璐. 基于问题转化和多任务的大规模高维多目标优化[D]. 西安电子科技大学, 2021.

[40] 田野. 基于进化算法的复杂多目标优化问题求解[D]. 安徽大学, 2018.

[41] 李良昊. 复杂多目标优化问题的演化算法研究[D]. 华中科技大学, 2019.

[42] 刘红平, 黎福海. 面向多目标优化问题的自适应差分进化算法[J]. 计算机应用与软件,2015, 32(12): 249-252.

[43] ZHANG W J, XIE X F. DEPSO: hybrid particle swarm with differential evolution operator[C]//SMC’03 Conference Proceedings. 2003 IEEE International Conference on Systems, Manand Cybernetics. Conference Theme-System Security and Assurance (Cat. No. 03CH37483):volume 4. IEEE, 2003: 3816-3821.

[44] TANABE R, ISHIBUCHI H. Review and analysis of three components of the differential evolutionmutation operator in MOEA/D-DE[J]. Applied Soft Computing, 2019, 23(23): 12843-12857.

[45] KNOWLES J D, CORNE D W. Approximating the nondominated front using the Paretoarchived evolution strategy[J]. Evolutionary computation, 2000, 8(2): 149-172.

[46] ZITZLER E, LAUMANNS M, THIELE L. SPEA2: Improving the strength Pareto evolutionaryalgorithm[J]. TIK-Report, 2001, 103.

[47] ZOLPAKAR N A, LODHI S S, PATHAK S, et al. Application of multi-objective genetic algorithm(MOGA) optimization in machining processes[J]. Optimization of Manufacturing Processes,2020: 185-199.

[48] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[49] ZITZLER E, KÜNZLI S. Indicator-based selection in multiobjective search[C]//InternationalConference on Parallel Problem Solving from Nature. Springer, 2004: 832-842.

[50] BEUME N, NAUJOKS B, EMMERICH M. SMS-EMOA: Multiobjective selection based ondominated hypervolume[J]. European Journal of Operational Research, 2007, 181(3): 1653-1669.

[51] BADER J, ZITZLER E. HypE: An algorithm for fast hypervolume-based many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2011, 19(1): 45-76.

[52] ZHANG Q, LI H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.

[53] MISHRA V, SINGH V. Vector evaluated genetic algorithm-based distributed query plan generationin distributed database[C]//Proceedings of the International Conference on Recent Cognizancein Wireless Communication & Image Processing: ICRCWIP-2014. Springer, 2016:325-337.

[54] MASHWANI W K, SALHI A. A decomposition-based hybrid multiobjective evolutionary algorithmwith dynamic resource allocation[J]. Applied Soft Computing, 2012, 12(9): 2765-2780.

[55] LI K, DEB K, ZHANG Q, et al. An evolutionary many-objective optimization algorithm basedon dominance and decomposition[J]. IEEE Transactions on Evolutionary Computation, 2014,19(5): 694-716.

[56] SHARMA S, KUMAR V. A Comprehensive Review on Multi-objective Optimization Techniques:Past, Present and Future[J]. Archives of Computational Methods in Engineering, 2022,29(7): 5605-5633.

[57] YUAN Y, XU H, WANG B, et al. Balancing convergence and diversity in decomposition-basedmany-objective optimizers[J]. IEEE Transactions on Evolutionary Computation, 2015, 20(2):180-198.

[58] HERNANDEZ-DIAZ A G, SANTANA-QUINTERO L V, COELLO COELLO C A, et al.Pareto-adaptive 𝜀-dominance[J]. Evolutionary Computation, 2007, 15(4): 493-517.

[59] IKEDA K, KITA H, KOBAYASHI S. Failure of Pareto-based MOEAs: Does non-dominatedreally mean near to optimal?[C]//IEEE Conference on Evolutionary Computation (CEC): volume2. IEEE, 2001: 957-962.

[60] FARINA M, AMATO P. A fuzzy definition of” optimality” for many-criteria optimization problems[J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans,2004, 34(3): 315-326.

[61] KÖPPEN M, VICENTE-GARCIA R, NICKOLAY B. Fuzzy-pareto-dominance and its applicationin evolutionary multi-objective optimization[C]//International Conference on EvolutionaryMulti-Criterion Optimization. Springer, 2005: 399-412.

[62] LI F, CHENG R, LIU J, et al. A two-stage R2 indicator based evolutionary algorithm for manyobjectiveoptimization[J]. Applied Soft Computing, 2018, 67: 245-260.

[63] LI H, ZHANG Q. Multiobjective optimization problems with complicated Pareto sets, MOEA/Dand NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2008, 13(2): 284-302.

[64] ZHANG S X, ZHENG L M, LIU L, et al. Decomposition-based multi-objective evolutionaryalgorithm with mating neighborhood sizes and reproduction operators adaptation[J]. AppliedSoft Computing, 2017, 21(21): 6381-6392.

[65] LIU H L, GU F, ZHANG Q. Decomposition of a multiobjective optimization problem into anumber of simple multiobjective subproblems[J]. IEEE Transactions on Evolutionary Computation,2013, 18(3): 450-455.

[66] DEB K, SINDHYA K, OKABE T. Self-adaptive simulated binary crossover for real-parameteroptimization[C]//Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation.2007: 1187-1194.

[67] YUAN Y, XU H, WANG B, et al. A new dominance relation-based evolutionary algorithm formany-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 20(1):16-37.

[68] ZITZLER E, THIELE L, LAUMANNS M, et al. Performance assessment of multiobjectiveoptimizers: An analysis and review[J]. IEEE Transactions on Evolutionary Computation, 2003,7(2): 117-132.

[69] ZHANG Q, ZHOU A, JIN Y. RM-MEDA: A regularity model-based multiobjective estimationof distribution algorithm[J]. IEEE Transactions on Evolutionary Computation, 2008, 12(1):41-63.

[70] FLORIAN A. An efficient sampling scheme: updated latin hypercube sampling[J]. ProbabilisticEngineering Mechanics, 1992, 7(2): 123-130.

[71] ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: a comparative case study andthe strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4):257-271.

[72] ISHIBUCHI H, IMADA R, MASUYAMA N, et al. Dynamic specification of a reference pointfor hypervolume calculation in SMS-EMOA[C]//IEEE Conference on Evolutionary Computation(CEC). IEEE, 2018: 1-8.

[73] ISHIBUCHI H, MATSUMOTO T, MASUYAMA N, et al. Effects of dominance resistant solutionson the performance of evolutionary multi-objective and many-objective algorithms[C]//Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). Springer,2020: 507-515.

[74] ISHIBUCHI H, DOI K, NOJIMA Y. Reference point specification in MOEA/D for multiobjectiveand many-objective problems[C]//2016 IEEE International Conference on Systems,Man, and Cybernetics (SMC). IEEE, 2016: 004015-004020.

[75] WANG Z, ONG Y S, ISHIBUCHI H. On scalable multiobjective test problems with hardlydominated boundaries[J]. IEEE Transactions on Evolutionary Computation, 2018, 23(2): 217-231.

[76] LAUMANNS M, THIELE L, DEB K, et al. Combining convergence and diversity in evolutionarymultiobjective optimization[J]. Evolutionary Computation, 2002, 10(3): 263-282.

[77] GIAGKIOZIS I, PURSHOUSE R C, FLEMING P J. Generalized decomposition[C]//International Conference on Evolutionary Multi-Criterion Optimization (EMO). Springer,2013: 428-442.

[78] PANG L M, ISHIBUCHI H, SHANG K. NSGA-II with simple modification works well on awide variety of many-objective problems[J]. IEEE Access, 2020, 8: 190240-190250.

[79] WANG Z, DENG J, ZHANG Q, et al. On the Parameter Setting of the Penalty-Based BoundaryIntersection Method in MOEA/D.[C]//International Conference on Evolutionary Multi-Criterion Optimization (EMO). 2021: 413-423.

[80] LI L, CHEN H, LI J, et al. Preference-based evolutionary many-objective optimization for agilesatellite mission planning[J]. IEEE Access, 2018, 6: 40963-40978.

[81] ZHANG Y, FINKELSTEIN A, HARMAN M. Search based requirements optimisation: Existingwork and challenges[C]//International Working Conference on Requirements Engineering:Foundation for Software Quality. Springer, 2008: 88-94.

[82] DEB K, AGRAWAL R B, et al. Simulated binary crossover for continuous search space[J].Complex Systems, 1995, 9(2): 115-148.

[83] LIU H L, CHEN L, DEB K, et al. Investigating the effect of imbalance between convergenceand diversity in evolutionary multiobjective algorithms[J]. IEEE Transactions on EvolutionaryComputation, 2016, 21(3): 408-425.

[84] WANG Z, ONG Y S, SUN J, et al. A generator for multiobjective test problems with difficultto-approximate Pareto front boundaries[J]. IEEE Transactions on Evolutionary Computation,2018, 23(4): 556-571.

[85] FUKUMOTO H, OYAMA A. Coverage Enhancement of MOEA/D-M2M for Problems withDifficult-to-Approximate Pareto Front Boundaries[C]//2019 IEEE Congress on EvolutionaryComputation (CEC). IEEE, 2019: 1734-1741.

[86] CHEN L, LIU H L, LU C, et al. A novel evolutionary multi-objective algorithm based on smetric selection and m2m population decomposition[C]//Proceedings of the 18th Asia PacificSymposium on Intelligent and Evolutionary Systems-Volume 2. Springer, 2015: 441-452.

[87] WOLPERT D, MACREADY W. No free lunch theorems for optimization[J/OL]. IEEE Transactionson Evolutionary Computation, 1997, 1(1): 67-82. DOI: 10.1109/4235.585893.

[88] IMAN R L, CONOVER W. Small sample sensitivity analysis techniques for computer models.with an application to risk assessment[J]. Communications in Statistics-theory and Methods,1980, 9(17): 1749-1842.

[89] DEB K, MOHAN M, MISHRA S. Towards a quick computation of well-spread Pareto-optimalsolutions[C]//International Conference on Evolutionary Multi-Criterion Optimization (EMO).Springer, 2003: 222-236.

[90] LIU Y, ZHU N, LI M. Solving many-objective optimization problems by a Pareto-based evolutionaryalgorithm with preprocessing and a penalty mechanism[J]. IEEE Transactions onCybernetics, 2020.

[91] WANG Z, LI Q, YANG Q, et al. The dilemma between eliminating dominance-resistant solutionsand preserving boundary solutions of extremely convex Pareto fronts[J]. Complex &Intelligent Systems, 2021: 1-10.

[92] LAM F, LONGNECKER M. A modified Wilcoxon rank sum test for paired data[J]. Biometrika,1983, 70(2): 510-513.

[93] TIAN Y, CHENG R, ZHANG X, et al. PlatEMO: A MATLAB platform for evolutionary multiobjectiveoptimization[J]. IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87.

[94] TANABE R, ISHIBUCHI H. An easy-to-use real-world multi-objective optimization problemsuite[J]. Applied Soft Computing, 2020, 89: 106078.

[95] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-pointbasednondominated sorting approach, part I: solving problems with box constraints[J]. IEEETransactions on Evolutionary Computation, 2013, 18(4): 577-601.

[96] GU L, YANG R, THO C H, et al. Optimisation and robustness for crashworthiness of sideimpact[J]. International Journal of Vehicle Design, 2001, 26(4): 348-360.

[97] DEB K, GUPTA S, DAUM D, et al. Reliability-based optimization using evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5): 1054-1074.