<sub id="bz1nl"></sub><sub id="bz1nl"></sub>
        <sub id="bz1nl"></sub>

        <sub id="bz1nl"></sub><sub id="bz1nl"></sub>

          2.793

          2018影响因子

          (CJCR)

          • 中文核心
          • EI
          • 中国科技核心
          • Scopus
          • CSCD
          • 英国科学文摘

          留言板

          尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

          姓名
          邮箱
          手机号码
          标题
          留言内容
          验证码

          动态多目标优化进化算法研究进展

          马永杰 陈敏 龚影 程时升 王甄延

          马永杰, 陈敏, 龚影, 程时升, 王甄延. 动态多目标优化进化算法研究进展. 自动化学报, 2020, 46(11): 2302?2318. doi: 10.16383/j.aas.c190489
          引用本文: 马永杰, 陈敏, 龚影, 程时升, 王甄延. 动态多目标优化进化算法研究进展. 自动化学报, 2020, 46(11): 2302?2318. doi: 10.16383/j.aas.c190489
          Ma Yong-Jie, Chen Min, Gong Ying, Cheng Shi-Sheng, Wang Zhen-Yan. Research progress of dynamic multi-objective optimization evolutionary algorithm. Acta Automatica Sinica, 2020, 46(11): 2302?2318. doi: 10.16383/j.aas.c190489
          Citation: Ma Yong-Jie, Chen Min, Gong Ying, Cheng Shi-Sheng, Wang Zhen-Yan. Research progress of dynamic multi-objective optimization evolutionary algorithm. Acta Automatica Sinica, 2020, 46(11): 2302?2318. doi: 10.16383/j.aas.c190489

          动态多目标优化进化算法研究进展


          DOI: 10.16383/j.aas.c190489
          详细信息
            作者简介:

            西北师范大学物理与电子工程学院电子系教授. 主要研究方向为进化算法. 本文通信作者. E-mail: myjmyj@nwnu.edu.cn

            西北师范大学物理与电子工程学院硕士研究生. 主要研究方向为进化算法. E-mail: cm9690@126.com

            西北师范大学物理与电子工程学院硕士研究生. 主要研究方向为智能计算. E-mail: 15320834175@163.com

            西北师范大学物理与电子工程学院硕士研究生. 主要研究方向为智能计算. E-mail: shishengcss@163.com

            西北师范大学物理与电子工程学院硕士研究生. 主要研究方向为智能计算. E-mail: wzy1136390111@163.com

          • 基金项目:  国家自然科学基金(62066041, 41861047)资助

          Research Progress of Dynamic Multi-objective Optimization Evolutionary Algorithm

          More Information
          • Fund Project:  Supported by National Natural Science Foundation of China (62066041, 41861047)
          • 摘要: 动态多目标优化问题(Dynamic multi-objective optimization problems, DMOPs)已成为工程优化的研究热点, 其目标函数, 约束函数和相关参数都可能随时间不断变化, 如何利用搜索到的历史最优解对新的环境变化做出快速响应, 是设计动态多目标优化进化算法(Dynamic multi-objective optimization evolutionary algorithm, DMOEA)的重点和难点. 本文在介绍DMOEA的基础上, 分析了近年来基于个体和种群级别的环境响应策略, 多策略混合等的DMOEA主要研究进展, 并介绍了DMOEA的性能测试函数, 评价指标以及在工程优化领域中的应用, 分析了DMOEA研究中仍面临的主要问题, 展望了未来的研究方向.
          • 图  1  DMOEA的设计流程框图

            Fig.  1  The design flow chart of DMOEA

            图  2  基于卡尔曼滤波的预测模型图

            Fig.  2  Relationship of EA with KF model

            图  3  动态环境中多种群调度方法的框架

            Fig.  3  Framework for multi-population methods with scheduling in dynamic environments

            图  4  BSCA算法体系结构图

            Fig.  4  The architecture of BSCA inspired by human NEI systems

            图  5  多种群的粒子群优化框架示意图

            Fig.  5  The framework of multi-swarm particle swarm optimization

            图  6  动态进化环境模型框图

            Fig.  6  A general framework of dynamic environment evolutionary model

            七星彩规则
          • [1] 刘淳安. 动态多目标优化进化算法研究综述. 海南大学学报自然科学版, 2010, 28(2): 176?182

            Liu Chun-An. Research on dynamic multiobjective optimization evolutionary algorithms. Natural Science Journal of Hainan University, 2010, 28(2): 176?182
            [2] 李智勇, 李峥, 陈恒勇, 张世文. 基于正交设计的动态多目标优化算法. 计算机工程与应用, 2016, 52(14): 42?49 doi:  10.3778/j.issn.1002-8331.1409-0064

            Li Zhi-Yong, Li Zheng, Chen Heng-Yong, Zhang Shi-Wen. Orthogonal design-based dynamic multi-objective optimization algorithm. Computer Engineering and Applications, 2016, 52(14): 42?49 doi:  10.3778/j.issn.1002-8331.1409-0064
            [3] Jiang S Y, Yang S X. Evolutionary dynamic multiobjective optimization: Benchmarks and algorithm comparisons. IEEE Transactions on Cybernetics, 2017, 47(1): 198?211 doi:  10.1109/TCYB.2015.2510698
            [4] Marichelvam M K, Prabaharan T, Yang X S. A discrete firefly algorithm for the multi-objective hybrid flowshop scheduling problems. IEEE Transactions on Evolutionary Computation, 2014, 18(2): 301?305 doi:  10.1109/TEVC.2013.2240304
            [5] Farina M, Deb K, Amato P. Dynamic multiobjective optimization problems: Test cases, approximation, and applications. In: Proceedings of the 2nd International Conference on Evolutionary Multi-Criterion Optimization. Faro, Portugal: Springer, 2003. 311?326
            [6] Farina M, Deb K, Amato P. Dynamic multiobjective optimization problems: Test cases, approximations, and applications. IEEE Transactions on Evolutionary Computation, 2004, 8(5): 425?442 doi:  10.1109/TEVC.2004.831456
            [7] Deb K, Rao N U B, Karthik S. Dynamic multi-objective optimization and decision-making using modified NSGA-II: A case study on hydro-thermal power scheduling. In: Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization. Matsushima, Japan: Springer, 2007. 803?817
            [8] 刘淳安, 王宇平. 动态多目标优化的进化算法及其收敛性分析. 电子学报, 2007, 35(6): 1118?1121 doi:  10.3321/j.issn:0372-2112.2007.06.023

            Liu Chun-An, Wang Yu-Ping. Evolutionary algorithm for dynamic multi-objective optimization problems and its convergence. Acta Electronica Sinica, 2007, 35(6): 1118?1121 doi:  10.3321/j.issn:0372-2112.2007.06.023
            [9] Greeff M, Engelbrecht A P. Solving dynamic multi-objective problems with vector evaluated particle swarm optimisation. In: Proceedings of the 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence). Hong Kong, China: IEEE, 2008. 2917?2924
            [10] Koo W T, Goh C K, Tan K C. A predictive gradient strategy for multiobjective evolutionary algorithms in a fast changing environment. Memetic Computing, 2010, 2(2): 87?110 doi:  10.1007/s12293-009-0026-7
            [11] 武燕, 刘小雄, 池程芝. 动态多目标优化的预测遗传算法. 控制与决策, 2013, 28(5): 677?682

            Wu Yan, Liu Xiao-Xiong, Chi Cheng-Zhi. Predictive multiobjective genetic algorithm for dynamic multiobjective optimization problems. Control and Decision, 2013, 28(5): 677?682
            [12] 郑金华, 彭舟, 邹娟, 申瑞珉. 基于引导个体的预测策略求解动态多目标优化问题. 电子学报, 2015, 43(9): 1816?1825 doi:  10.3969/j.issn.0372-2112.2015.09.021

            Zheng Jin-Hua, Peng Zhou, Zou Juan, Shen Rui-Min. A prediction strategy based on guide-lndividual for dynamic multi-objective optimization. Acta Electronica Sinica, 2015, 43(9): 1816?1825 doi:  10.3969/j.issn.0372-2112.2015.09.021
            [13] Muruganantham A, Tan K C, Vadakkepat P. Evolutionary dynamic multiobjective optimization via kalman filter prediction. IEEE Transactions on Cybernetics, 2016, 46(12): 2862?2873 doi:  10.1109/TCYB.2015.2490738
            [14] Ruan G, Yu G, Zheng J H, Zou J, Yang S X. The effect of diversity maintenance on prediction in dynamic multi-objective optimization. Applied Soft Computing, 2017, 58: 631?647 doi:  10.1016/j.asoc.2017.05.008
            [15] Zou J, Li Q Y, Yang S X, Zheng J H, Peng Z, Pei T R. A dynamic multiobjective evolutionary algorithm based on a dynamic evolutionary environment model. Swarm and Evolutionary Computation, 2019, 44: 247?259 doi:  10.1016/j.swevo.2018.03.010
            [16] Isaacs A, Puttige V, Ray T, Smith W, Anavatti S. Development of a memetic algorithm for dynamic multi-objective optimization and its applications for online neural network modeling of UAVs. In: Proceedings of the 2008 IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence). Hong Kong, China: IEEE, 2008. 548?554
            [17] Ismayilov G, Topcuoglu H R. Neural network based multi-objective evolutionary algorithm for dynamic workflow scheduling in cloud computing. Future Generation Computer Systems, 2020, 102: 307?322 doi:  10.1016/j.future.2019.08.012
            [18] Sahmoud S, Topcuoglu H R. A general framework based on dynamic multi-objective evolutionary algorithms for handling feature drifts on data streams. Future Generation Computer Systems, 2020, 102: 42?52 doi:  10.1016/j.future.2019.07.069
            [19] Hu W Z, Jiang M, Gao X, Tan K C, Cheung Y M. Solving dynamic multi-objective optimization problems using incremental Support vector machine. In: Proceedings of the 2019 IEEE Congress on Evolutionary Computation (CEC). Wellington, New Zealand: IEEE, 2019. 2794?2799
            [20] Orouskhani M, Teshnehlab M, Nekoui M A. Evolutionary dynamic multi-objective optimization algorithm based on Borda count method. International Journal of Machine Learning and Cybernetics, 2019, 10(8): 1931?1959 doi:  10.1007/s13042-017-0695-3
            [21] Coello C A C, Lamont G B, Van Veldhuizen D A. Evolutionary algorithms for solving multi-objective problems (Second edition). New York: Springer, 2007.
            [22] 彭舟. 动态环境下多目标进化优化的预测和保持种群多样性策略研究[硕士学位论文], 湘潭大学, 中国, 2015

            Peng Zhou. Research on Strategies of Prediction and Maintaining Population Diversity for Multi-objective Evolutionary Optimization in Dynamic Environment [Master thesis], Xiangtan University, China, 2015
            [23] 刘淳安, 王宇平. 基于新模型的动态多目标优化进化算法. 计算机研究与发展, 2008, 45(4): 603?611

            Liu Chun-An, Wang Yu-Ping. Dynamic multi-objective optimization evolutionary algorithm based on new model. Journal of Computer Research and Development, 2008, 45(4): 603?611
            [24] Trojanowski K, Michalewicz Z, Xiao J. Adding memory to the evolutionary planner/navigator. In: Proceedings of the 1997 IEEE International Conference on Evolutionary Computation. Indianapolis, USA : IEEE, 1997. 483?487
            [25] Trojanowski K, Michalewicz Z. Searching for optima in non-stationary environments. In: Proceedings of the 1999 Congress on Evolutionary Computation-CEC99(Cat. No. 99TH8406). Washington, USA: IEEE, 1999.
            [26] 刘敏, 曾文华. 记忆增强的动态多目标分解进化算法. 软件学报, 2013, 24(7): 1571?1588

            Liu Min, Zeng Wen-Hua. Memory enhanced dynamic multi-objective evolutionary algorithm based on decomposition. Journal of Software, 2013, 24(7): 1571?1588
            [27] Yang S X. Memory-based immigrants for genetic algorithms in dynamic environments. In: Genetic and Evolutionary Computation Conference. Washington DC, USA: ACM, 2005. 1115?1122
            [28] Azzouz R, Bechikh S, Said L B. A dynamic multi-objective evolutionary algorithm using a change severity-based adaptive population management strategy. Soft Computing-A Fusion of Foundations, Methodologies and Applications, 2017, 21(4): 885?906
            [29] Turky A, Abdullah S, Dawod A. A dual-population multi operators harmony search algorithm for dynamic optimization problems. Computers & Industrial Engineering, 2018, 117: 19?28
            [30] Hatzakis I, Wallace D. Dynamic multi-objective optimization with evolutionary algorithms: A forward-looking approach. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. Seattle, USA: ACM, 2006. 1201?1208
            [31] 丁进良, 杨翠娥, 陈立鹏, 柴天佑. 基于参考点预测的动态多目标优化算法. 自动化学报, 2017, 43(2): 313?320

            Ding Jin-Liang, Yang Cui-E, Chen Li-Peng, Chai Tian-You. Dynamic multi-objective optimization algorithm based on reference point prediction. Acta Automatica Sinica, 2017, 43(2): 313?320
            [32] 彭星光, 徐德民, 高晓光. 基于Pareto解集关联与预测的动态多目标进化算法. 控制与决策, 2011, 26(4): 615?618

            Peng Xing-Guang, Xu De-Min, Gao Xiao-Guang. A dynamic multi-objective evolutionary algorithm based on Pareto set linkage and prediction. Control and Decision, 2011, 26(4): 615?618
            [33] 耿焕同, 周山胜, 陈哲, 韩伟民. 基于分解的预测型动态多目标粒子群优化算法. 控制与决策, 2019, 34(6): 1307?1318

            Geng Huan-Tong, Zhou Shan-Sheng, Chen Zhe, Han Wei-Min. Decomposition-based predictive dynamic multi-objective particle swarm optimization algorithm. Control and Decision, 2019, 34(6): 1307?1318
            [34] Zhou A M, Jin Y C, Zhang Q F. A population prediction strategy for evolutionary dynamic multiobjective optimization. IEEE Transactions on Cybernetics, 2014, 44(1): 40?53 doi:  10.1109/TCYB.2013.2245892
            [35] Li Z Y, Chen H Y, Xie Z X, Chen C, Sallam A. Dynamic multiobjective optimization algorithm based on average distance linear prediction model. The Scientific World Journal, 2014, 2014: Article No. 389742
            [36] Zou J, Li Q Y, Yang S X, Bai H, Zhen J H. A prediction strategy based on center points and knee points for evolutionary dynamic multi-objective optimization. Applied Soft Computing, 2017, 61: 806?818 doi:  10.1016/j.asoc.2017.08.004
            [37] 李智翔, 李赟, 贺亮, 沈超. 使用新预测模型的动态多目标优化算法. 西安交通大学学报, 2018, 52(10): 8?15

            Li Zhi-Xiang, Li Yun, He Liang, Shen Chao. A dynamic multiobjective optimization algorithm with a new prediction model. Journal of Xi'an Jiaotong University, 2018, 52(10): 8?15
            [38] Jiang M, Huang Z Q, Qiu L M, Huang W Z, Yen G G. Transfer learning-based dynamic multiobjective optimization algorithms. IEEE Transactions on Evolutionary Computation, 2018, 22(4): 501?514 doi:  10.1109/TEVC.2017.2771451
            [39] Jiang M, Qiu L M, Huang Z Q, Yen G G. Dynamic multi-objective estimation of distribution algorithm based on domain adaptation and nonparametric estimation. Information Sciences, 2018, 435: 203?223 doi:  10.1016/j.ins.2017.12.058
            [40] Zhou J W, Zou J, Yang S X, Ruan G, Ou J W, Zheng J H. An evolutionary dynamic multi-objective optimization algorithm based on center-point prediction and sub-population autonomous guidance. In: Proceedings of the 2018 IEEE Symposium Series on Computational Intelligence (SSCI). Bangalore, India: IEEE, 2018. 2148?2154
            [41] Branke J, Kaussler T, Schmidt C, Schmeck H. A multi-population approach to dynamic optimization problems. Evolutionary Design and Manufacture. London: Springer, 2000. 299?307
            [42] 龙文. 一种改进的动态多种群并行差分进化算法. 计算机应用研究, 2012, 29(7): 2429?2431 doi:  10.3969/j.issn.1001-3695.2012.07.007

            Long Wen. Dynamic multi-species parallel differential evolution algorithm. Application Research of Computers, 2012, 29(7): 2429?2431 doi:  10.3969/j.issn.1001-3695.2012.07.007
            [43] 胡成玉, 姚宏, 颜雪松. 基于多粒子群协同的动态多目标优化算法及应用. 计算机研究与发展, 2013, 50(6): 1313?1323 doi:  10.7544/issn1000-1239.2013.20110847

            Hu Cheng-Yu, Yao Hong, Yan Xue-Song. Multiple particle swarms coevolutionary algorithm for dynamic multi-objective optimization problems and its application. Journal of Computer Research and Development, 2013, 50(6): 1313?1323 doi:  10.7544/issn1000-1239.2013.20110847
            [44] 张世文, 李智勇, 陈少淼, 李仁发. 基于生态策略的动态多目标优化算法. 计算机研究与发展, 2014, 51(6): 1313?1330 doi:  10.7544/issn1000-1239.2014.20120757

            Zhang Shi-Wen, Li Zhi-Yong, Chen Shao-Miao, Li Ren-FA. Dynamic multi-objective optimization algorithm based on ecological strategy. Journal of Computer Research and Development, 2014, 51(6): 1313?1330 doi:  10.7544/issn1000-1239.2014.20120757
            [45] Kordestani J K, Ranginkaman A E, Meybodi M R, Novoa-Hernández P. A novel framework for improving multi-population algorithms for dynamic optimization problems: A scheduling approach. Swarm and Evolutionary Computation, 2019, 44: 788?805 doi:  10.1016/j.swevo.2018.09.002
            [46] Yang Z, Jin Y, Hao K. A bio-inspired self-learning coevolutionary dynamic multiobjective optimization algorithm for Internet of Things services. IEEE Transactions on Evolutionary Computation, 2018, 23(4): 675?688 doi:  10.1109/TEVC.2018.2880458
            [47] Cobb H G, Grefenstette J J. Genetic algorithms for tracking changing environments. In: Proceedings of the 5th International Conference on Genetic Algorithms. Urbana-Champaign, USA: IEEE, 1993. 523?530
            [48] Vavak F, Fogarty T C, Jukes K. A genetic algorithm with variable range of local search for tracking changing environments. In: International Conference on Evolutionary Computation — The 4th International Conference on Parallel Problem Solving from Nature. Berlin, Germany: Springer, 1996. 376?385
            [49] Woldesenbet Y G, Yen G G. Dynamic evolutionary algorithm with variable relocation. IEEE Transactions on Evolutionary Computation, 2009, 13(3): 500?513 doi:  10.1109/TEVC.2008.2009031
            [50] Eriksson R, Olsson B. On the performance of evolutionary algorithms with life-time adaptation in dynamic fitness landscapes. In: Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753). Portland, USA: IEEE, 2004. 1293?1300
            [51] Grefenstette J J. Genetic algorithms for changing environments. In: Proceedings of the 2nd Parallel Problem Solving From Nature 2. Brussels, Belgium: Elsevier, 1992. 137?144
            [52] Yang S X, Tinós R. A hybrid immigrants scheme for genetic algorithms in dynamic environments. International Journal of Automation and Computing, 2007, 4(3): 243?254 doi:  10.1007/s11633-007-0243-9
            [53] Mavrovouniotis M, Yang S X. Genetic algorithms with adaptive immigrants for dynamic environments. In: Proceedings of the 2013 IEEE Congress on Evolutionary Computation. Cancun, Mexico: IEEE, 2013. 2130?2137
            [54] Yang S X. Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evolutionary Computation, 2008, 16(3): 385?416 doi:  10.1162/evco.2008.16.3.385
            [55] Gee S B, Tan K C, Abbass H A. A benchmark test suite for dynamic evolutionary multiobjective optimization. IEEE Transactions on Cybernetics, 2017, 47(2): 461?472
            [56] Liu R C, Li J X, Fan J, Mu C H, Jiao L C. A coevolutionary technique based on multi-swarm particle swarm optimization for dynamic multi-objective optimization. European Journal of Operational Research, 2017, 261(3): 1028?1051 doi:  10.1016/j.ejor.2017.03.048
            [57] Rong M, Gong D, Zhang Y, Jin Y. Multidirectional prediction approach for dynamic multiobjective optimization problems. IEEE Transactions on Cybernetics, 2018, 49(9): 3362?3374
            [58] Liang Z P, Zheng S X, Zhu Z X, Yang S X. Hybrid of memory and prediction strategies for dynamic multiobjective optimization. Information Sciences, 2019, 485: 200?218 doi:  10.1016/j.ins.2019.01.066
            [59] 郑金华, 申瑞珉, 李密青, 邹娟, 袁琦钊. 多目标优化的进化环境模型及实现. 计算机学报, 2014, 37(12): 2530?2547

            Zheng Jin-Hua, Shen Rui-Min, Li Mi-Qing, Zou Juan, Yuan Qi-Zhao. An evolutionary environment model of multiobjective optimization and its realization. Chinese Journal of Computers, 2014, 37(12): 2530?2547
            [60] Yu X, Jin Y C, Tang K, Yao X. Robust optimization over time ? a new perspective on dynamic optimization problems. In: Proceedings of the 2010 IEEE Congress on Evolutionary Computation. Barcelona, Spain: IEEE, 2010. 1?6
            [61] Liu C A. New dynamic multiobjective evolutionary algorithm with core estimation of distribution. In: Proceedings of the 2010 International Conference on Electrical and Control Engineering. Wuhan, China: IEEE, 2010. 1345?1348
            [62] Turky A M, Abdullah S. A multi-population electromagnetic algorithm for dynamic optimisation problems. Applied Soft Computing, 2014, 22: 474?482 doi:  10.1016/j.asoc.2014.04.032
            [63] Liu C A, Jia H M. Dynamic multiobjective evolutionary algorithm with two stages evolution operation. Intelligent Automation and Soft Computing, 2015, 21(4): 575?588
            [64] 耿焕同, 孙家清, 贾婷婷. 基于自适应启动策略的混合交叉动态约束多目标优化算法. 模式识别与人工智能, 2015, 28(5): 411?421

            Geng Huan-Tong, Sun Jia-Qing, Jia Ting-Ting. A mixture crossover dynamic constrained multi-objective evolutionary algorithm based on self-adaptive start-up strategy. Pattern Recognition and Artificial Intelligence, 2015, 28(5): 411?421
            [65] 焦儒旺, 曾三友, 李晰, 李长河. 基于学习的动态多目标方法求解约束优化问题. 武汉大学学报(理学版), 2017, 63(2): 177?183

            Jiao Ru-Wang, Zeng San-You, Li Xi, Li Chang-He. Constrained optimization by solving equivalent dynamic constrained multi-objective based on learning. Journal of Wuhan University (Natural Science Edition), 2017, 63(2): 177?183
            [66] 陈美蓉, 郭一楠, 巩敦卫, 杨振. 一类新型动态多目标鲁棒进化优化方法. 自动化学报, 2017, 43(11): 2014?2032

            Chen Mei-Rong, Guo Yi-Nan, Gong Dun-Wei, Yang Zhen. A novel dynamic multi-objective robust evolutionary optimization method. Acta Automatica Sinica, 2017, 43(11): 2014?2032
            [67] Barba-González C, García-Nieto J, Nebro A J, Cordero J A, Durillo J J, Navas-Delgado I, et al. jMetalSP: A framework for dynamic multi-objective big data optimization. Applied Soft Computing, 2018, 69: 737?748 doi:  10.1016/j.asoc.2017.05.004
            [68] Zhang Q F, Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712?731 doi:  10.1109/TEVC.2007.892759
            [69] Wang R, Ishibuchi H, Zhang Y, Zheng X K, Zhang T. On the effect of localized PBI method in MOEA/D for multi-objective optimization. In: Proceedings of the 2016 IEEE Symposium Series on Computational Intelligence (SSCI). Athens, Greece: IEEE, 2016. 1?8
            [70] Luo J P, Yang Y, Li X, Liu Q Q, Chen M R, Gao K Z. A decomposition-based multi-objective evolutionary algorithm with quality indicator. Swarm and Evolutionary Computation, 2018, 39: 339?355 doi:  10.1016/j.swevo.2017.11.004
            [71] 李智翔, 李赟, 贺亮. 采用新邻居模型的多目标分解进化算法. 计算机工程与应用, 2018, 54(14): 1?6 doi:  10.3778/j.issn.1002-8331.1803-0114

            Li Zhi-Xiang, Li Yun, He Liang. Decomposition multiobjective optimization algorithm with new neighborhood model. Computer Engineering and Applications, 2018, 54(14): 1?6 doi:  10.3778/j.issn.1002-8331.1803-0114
            [72] Biswas P P, Suganthan P N, Amaratunga G A J. Decomposition based multi-objective evolutionary algorithm for windfarm layout optimization. Renewable Energy, 2018, 115: 326?337 doi:  10.1016/j.renene.2017.08.041
            [73] 李智翔, 贺亮, 韩杰思, 游凌. 一种基于偶图匹配的多目标分解进化算法. 控制与决策, 2018, 33(10): 1782?1788

            Li Zhi-Xiang, He Liang, Han Jie-Si, You Ling. A bigraph matching method for decomposition multiobjective optimization. Control and Decision, 2018, 33(10): 1782?1788
            [74] Liu R C, Li J X, Fan J, Jiao L C. A dynamic multiple populations particle swarm optimization algorithm based on decomposition and prediction. Applied Soft Computing, 2018, 73: 434?459
            [75] Qiao J F, Zhou H B, Yang C L, Yang S X. A decomposition-based multiobjective evolutionary algorithm with angle-based adaptive penalty. Applied Soft Computing, 2019, 74: 190?205
            [76] Cao L L, Xu L H, Goodman E D, Li H. Decomposition-based evolutionary dynamic multiobjective optimization using a difference model. Applied Soft Computing, 2019, 76: 473?490
            [77] 黄亮. 膜计算优化方法研究[博士学位论文], 浙江大学, 中国, 2007

            Huang L. Research on membrane computing optimization methods[Ph. D. dissertation], Zhejiang University, China, 2007
            [78] 陈兵华, 尤嘉兴, 陈基漓, 董明刚. 基于投影映射的动态多目标粒子群优化算法. 计算机仿真, 2016, 33(12): 233?238 doi:  10.3969/j.issn.1006-9348.2016.12.049

            Chen Bin-Hua, You Jia-Xing, Chen Ji-Li, Dong Ming-Gang. Dynamic multi-objective particle swarm optimization based on projection mapping. Computer Simulation, 2016, 33(12): 233?238 doi:  10.3969/j.issn.1006-9348.2016.12.049
            [79] 尤嘉兴, 陈基漓, 董明刚. 基于档案交叉的动态多目标粒子群优化算法. 计算机工程与设计, 2015, 36(2): 507?513

            You Jia-Xing, Chen Ji-Li, Dong Ming-gang. Dynamic multi-objective particle swarm optimization based on archive crossover. Computer Engineering and Design, 2015, 36(2): 507?513
            [80] 尚荣华, 焦李成, 公茂果, 马文萍. 免疫克隆算法求解动态多目标优化问题. 软件学报, 2007, 18(11): 2700?2711 doi:  10.1360/jos182700

            Shang Rong-Hua, Jiao Li-Cheng, Gong Mao-Guo, Ma Wen-Ping. An immune clonal algorithm for dynamic multi-objective optimization. Journal of Software, 2007, 18(11): 2700?2711 doi:  10.1360/jos182700
            [81] 郑金华, 邹娟. 多目标进化优化. 北京: 科学出版社, 2017

            Zheng Jin-Hua, Zou Juan. Multi-objective Evolutionary Optimization. Beijing:Science Press , 2017
            [82] Nguyen T T, Yang S X, Branke J. Evolutionary dynamic optimization: A survey of the state of the art. Swarm and Evolutionary Computation, 2012, 6: 1?24
            [83] Goh C K, Tan K C. A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization. IEEE Transactions on Evolutionary Computation, 2009, 13(1): 103?127
            [84] Van Veldhuizen D A, Lamont G B. On measuring multiobjective evolutionary algorithm performance. In: Proceedings of the 2000 Congress on Evolutionary Computation. La Jolla, USA: IEEE, 2000. 204?211
            [85] Van Veldhuizen D A. Multiobjective Evolutionary Algorithms: Classifications, Analyses, and New Innovations[Ph. D. dissertation], Air Force Institute of Technology, USA, 1999.
            [86] Van Veldhuizen D A, Lamont G B. Evolutionary computation and convergence to a Pareto front. In: Proceedings of Late Breaking Papers at the Genetic Programming 1998 Conference. California, USA: Stanford University, 1998. 221?228
            [87] Liu M, Liu Y Z. A dynamic evolutionary multi-objective optimization algorithm based on decomposition and adaptive diversity introduction. In: Proceedings of the 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery (ICNC-FSKD). Changsha, China: IEEE, 2016. 235?240
            [88] Li X D, Branke J, Kirley M. On performance metrics and particle swarm methods for dynamic multiobjective optimization problems. In: Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Singapore: IEEE, 2007. 576?583
            [89] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182?197
            [90] Schott J R. Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization [Master thesis], Massachusetts Institute of Technology, USA, 1995
            [91] Yang S X. Memory-enhanced univariate marginal distribution algorithms for dynamic optimization problems. In: Proceedings of the 2005 IEEE Congress on Evolutionary Computation. Edinburgh, UK: IEEE, 2005. 2560?2567
            [92] Azzouz R, Bechikh S, Said L B, Trabelsi W. Handling time-varying constraints and objectives in dynamic evolutionary multi-objective optimization. Swarm and Evolutionary Computation, 2018, 39: 222?248
            [93] Cámara M, Ortega J, de Toro F. A single front genetic algorithm for parallel multi-objective optimization in dynamic environments. Neurocomputing, 2009, 72(16-18): 3570?3579
            [94] Camara M, Ortega J, Toro F J. Parallel processing for multi-objective optimization in dynamic environments. In: Proceedings of the 2007 IEEE International Parallel and Distributed Processing Symposium. Rome, Italy: IEEE, 2007. 1?8
            [95] 戴文战. 一种动态多目标决策模型及其应用. 控制与决策, 2000, 15(2): 197?200 doi:  10.3321/j.issn:1001-0920.2000.02.017

            Dai Wen-Zhan. A new kind of model of the dynamic multiple attribute decision making based on new effective function and its application. Control and Decision, 2000, 15(2): 197?200 doi:  10.3321/j.issn:1001-0920.2000.02.017
            [96] Vallerio M, Telen D, Cabianca L, Manenti F, van Impe J V, Logist F. Robust multi-objective dynamic optimization of chemical processes using the Sigma Point method. Chemical Engineering Science, 2016, 140: 201?216 doi:  10.1016/j.ces.2015.09.012
            [97] Qiao J F, Zhang W. Dynamic multi-objective optimization control for wastewater treatment process. Neural Computing and Applications, 2018, 29(11): 1261?1271 doi:  10.1007/s00521-016-2642-8
            [98] Han J, Yang C H, Zhou X J, Gui W H. Dynamic multi-objective optimization arising in iron precipitation of zinc hydrometallurgy. Hydrometallurgy, 2017, 173: 134-148
            [99] Luna R, Matias-Guiu P, López F, Pérez-Correa J R. Quality aroma improvement of Muscat wine spirits: A new approach using first-principles model-based design and multi-objective dynamic optimisation through multi-variable analysis techniques. Food and Bioproducts Processing, 2019, 115: 208?222 doi:  10.1016/j.fbp.2019.04.004
            [100] Guo Y N, Cheng J, Luo S, Gong D W, Xue Y. Robust dynamic multi-objective vehicle routing optimization method. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2018, 15(6): 1891?1903 doi:  10.1109/TCBB.2017.2685320
            [101] Kanoh H, Hara K. Hybrid genetic algorithm for dynamic multi-objective route planning with predicted traffic in a real-world road network. In: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation. Atlanta, USA: ACM, 2008. 657?664
            [102] Ghannadpour S F, Noori S, Tavakkoli-Moghaddam R, Ghoseiri K. A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application. Applied Soft Computing, 2014, 14: 504?527 doi:  10.1016/j.asoc.2013.08.015
            [103] Fernández-Rodríguez A, Fernández-Cardador A, Cucala A P. Balancing energy consumption and risk of delay in high speed trains: A three-objective real-time eco-driving algorithm with fuzzy parameters. Transportation Research Part C: Emerging Technologies, 2018, 95: 652?678 doi:  10.1016/j.trc.2018.08.009
            [104] Fernández-Rodríguez A, Fernández-Cardador A, Cucala A P. Real time eco-driving of high speed trains by simulation-based dynamic multi-objective optimization. Simulation Modelling Practice and Theory, 2018, 84: 50?68 doi:  10.1016/j.simpat.2018.01.006
            [105] Maravall D, de Lope J. Multi-objective dynamic optimization with genetic algorithms for automatic parking. Soft Computing, 2007, 11(3): 249?257 doi:  10.1007/s00500-006-0066-6
            [106] Min H Q, Zhu J H, Zheng X J. Obstacle avoidance with multi-objective optimization by PSO in dynamic environment. In: Proceedings of the 2005 International Conference on Machine Learning and Cybernetics. Guangzhou, China: IEEE, 2005. 2950?2956.
            [107] Cheng H, Yang S X, Cao J N. Dynamic genetic algorithms for the dynamic load balanced clustering problem in mobile ad hoc networks. Expert Systems with Applications, 2013, 40(4): 1381?1392 doi:  10.1016/j.eswa.2012.08.050
            [108] Jiao R W, Sun Y Z, Sun J Q, Jiang Y H, Zeng S Y. Antenna design using dynamic multi-objective evolutionary algorithm. IET Microwaves, Antennas & Propagation, 2018, 12(13): 2065?2072
            [109] 陈哲. 基于多样性策略的动态多目标粒子群优化算法研究及应用[硕士学位论文], 南京信息工程大学, 中国, 2017

            Chen Zhe. Research and Application on Dynamic Multi-Objective Particle Swarm Optimization Based on Diversity Strategy [Master thesis], Nanjing University of Information Engineering, China, 2017
            [110] 洪博文, 郭力, 王成山, 焦冰琦, 刘文建. 微电网多目标动态优化调度模型与方法. 电力自动化设备, 2013, 33(3): 100?107 doi:  10.3969/j.issn.1006-6047.2013.03.017

            Hong Bo-Wen, Guo Li, Wang Cheng-Shan, Jiao Bing-Qi, Liu Wen-Jian. Model and method of dynamic multi-objective optimal dispatch for microgrid. Electric Power Automation Equipment, 2013, 33(3): 100?107 doi:  10.3969/j.issn.1006-6047.2013.03.017
            [111] Discenzo F M, Chung D, Zevchek J K. System and Method for Dynamic Multi-Objective Optimization of Pumping System Operation and Diagnostics, U.S. Patent 7143016, November 2006.
            [112] Liu X L, Luo J G. A dynamic multi-objective optimization model with interactivity and uncertainty for real-time reservoir flood control operation. Applied Mathematical Modelling, 2019, 74: 606?620 doi:  10.1016/j.apm.2019.05.009
            [113] Huang L, Suh I H, Abraham A. Dynamic multi-objective optimization based on membrane computing for control of time-varying unstable plants. Information Sciences, 2011, 181(11): 2370?2391 doi:  10.1016/j.ins.2010.12.015
            [114] Ding J L, Yang C E, Xiao Q, Chai T Y, Jin Y C. Dynamic evolutionary multiobjective optimization for raw ore allocation in mineral processing. IEEE Transactions on Emerging Topics in Computational Intelligence, 2019, 3(1): 36?48
            [115] Hasan M M, Lwin K, Imani M, Shabut A, Bittencourt L F, Hossain M A. Dynamic multi-objective optimisation using deep reinforcement learning: Benchmark, algorithm and an application to identify vulnerable zones based on water quality. Engineering Applications of Artificial Intelligence, 2019, 86: 107?135 doi:  10.1016/j.engappai.2019.08.014
            [116] Jiang S Y, Yang S X. A steady-state and generational evolutionary algorithm for dynamic multiobjective optimization. IEEE Transactions on Evolutionary Computation, 2017, 21(1): 65?82 doi:  10.1109/TEVC.2016.2574621
            [117] 刘若辰, 马亚娟, 张浪, 尚荣华. 基于预测策略的动态多目标免疫优化算法. 计算机学报, 2015, 38(8): 1544?1560 doi:  10.11897/SP.J.1016.2015.01544

            Liu Ruo-Chen, Ma Ya-Juan, Zhang Lang, Shang Rong-Hua. Dynamic multi-objective immune optimization algorithm based on prediction strategy. Chinese Journal of Computer, 2015, 38(8): 1544?1560 doi:  10.11897/SP.J.1016.2015.01544
            [118] 付锐, 张雅丽, 袁伟. 生态驾驶研究现状及展望. 中国公路学报, 2019, 32(3): 1?12

            Fu Rui, Zhang Ya-Li, Yuan Wei. Progress and prospect in research on eco-driving. China Journal of Highway and Transport, 2019, 32(3): 1?12
            [119] 吴国政. 从F03项目资助情况分析我国自动化学科的发展现状与趋势. 自动化学报, 2019, 45(9): 1611?1619

            Wu Guo-Zheng. Analysis of the status and trend of the development of China's automation discipline From F03 Funding of NSFC. Acta Automatica Sinica, 2019, 45(9): 1611?1619
            [120] Yang C E, Ding J L. Constrained dynamic multi-objective evolutionary optimization for operational indices of beneficiation process. Journal of Intelligent Manufacturing, 2019, 30(7): 2701?2713 doi:  10.1007/s10845-017-1319-1
            [121] Kyriakides A S, Voutetakis S, Papadopoulou S, Seferlis P. Integrated design and control of various hydrogen production flowsheet configurations via membrane based methane steam reforming. Membranes, 2019, 9(1): Article No. 14 doi:  10.3390/membranes9010014
          • [1] 叶凌箭. 间歇过程的批内自优化控制[J]. 自动化学报, 2020, 45(): 1-11. doi: 10.16383/j.aas.c190855
            [2] 付雅婷, 原俊荣, 李中奇, 杨辉. 基于钩缓约束的重载列车驾驶过程优化[J]. 自动化学报, 2019, 45(12): 2355-2365. doi: 10.16383/j.aas.c190223
            [3] 张晗, 杨继斌, 张继业, 宋鹏云, 徐晓惠. 燃料电池有轨电车能量管理Pareto多目标优化[J]. 自动化学报, 2019, 45(12): 2378-2392. doi: 10.16383/j.aas.c190044
            [4] 孙燕, 张弛, 路兴龙, 王靖戈, 付俊. 具有不等式路径约束的微分代数方程系统的动态优化[J]. 自动化学报, 2019, 45(5): 897-905. doi: 10.16383/j.aas.c180302
            [5] 汤鹏杰, 王瀚漓, 许恺晟. LSTM逐层多目标优化及多层概率融合的图像描述[J]. 自动化学报, 2018, 44(7): 1237-1249. doi: 10.16383/j.aas.2017.c160733
            [6] 乔俊飞, 韩改堂, 周红标. 基于知识的污水生化处理过程智能优化方法[J]. 自动化学报, 2017, 43(6): 1038-1046. doi: 10.16383/j.aas.2017.c170088
            [7] 苏兆品, 张国富, 蒋建国, 岳峰, 张婷. 基于非支配排序差异演化的应急资源多目标分配算法[J]. 自动化学报, 2017, 43(2): 195-214. doi: 10.16383/j.aas.2017.c160076
            [8] 陈美蓉, 郭一楠, 巩敦卫, 杨振. 一类新型动态多目标鲁棒进化优化方法[J]. 自动化学报, 2017, 43(11): 2014-2032. doi: 10.16383/j.aas.2017.c160300
            [9] 丁进良, 杨翠娥, 陈立鹏, 柴天佑. 基于参考点预测的动态多目标优化算法[J]. 自动化学报, 2017, 43(2): 313-320. doi: 10.16383/j.aas.2017.c150811
            [10] 刘丁, 张新雨, 陈亚军. 基于多目标人工鱼群算法的硅单晶直径检测图像阈值分割方法[J]. 自动化学报, 2016, 42(3): 431-442. doi: 10.16383/j.aas.2016.c150587
            [11] 左兴权, 王春露, 赵新超. 一种结合多目标免疫算法和线性规划的双行设备布局方法[J]. 自动化学报, 2015, 41(3): 528-540. doi: 10.16383/j.aas.2015.c140082
            [12] 陈振兴, 严宣辉, 吴坤安, 白猛. 融合张角拥挤控制策略的高维多目标优化[J]. 自动化学报, 2015, 41(6): 1145-1158. doi: 10.16383/j.aas.2015.c140555
            [13] 陈志旺, 白锌, 杨七, 黄兴旺, 李国强. 区间多目标优化中决策空间约束、支配及同序解筛选策略[J]. 自动化学报, 2015, 41(12): 2115-2124. doi: 10.16383/j.aas.2015.c150218
            [14] 孔维健, 柴天佑, 丁进良, 吴志伟. 镁砂熔炼过程全厂电能分配实时多目标优化方法研究[J]. 自动化学报, 2014, 40(1): 51-61. doi: 10.3724/SP.J.1004.2014.00051
            [15] 于坤杰, 王昕, 王振雷. 基于反馈的精英教学优化算法[J]. 自动化学报, 2014, 40(9): 1976-1983. doi: 10.3724/SP.J.1004.2014.01976
            [16] 高维尚, 邵诚. 复杂非凸约束优化难题与迭代动态多样进化算法[J]. 自动化学报, 2014, 40(11): 2469-2479. doi: 10.3724/SP.J.1004.2014.02469
            [17] 胡云卿, 刘兴高. 处理动态优化问题中控制变量路径约束的方法[J]. 自动化学报, 2013, 39(4): 440-449. doi: 10.3724/SP.J.1004.2013.00440
            [18] 卫忠, 徐晓飞, 战德臣, 邓胜春. 协同供应链多级库存控制的多目标优化模型及其求解方法[J]. 自动化学报, 2007, 33(2): 181-187. doi: 10.1360/aas-007-0181
            [19] 李艳君, 吴铁军. 一种混合动力学系统多目标优化控制问题的求解方法[J]. 自动化学报, 2002, 28(4): 606-609.
            [20] 达庆利, 何建敏, 徐南荣. 区域水环境经济系统的多目标递阶规划[J]. 自动化学报, 1992, 18(1): 70-79.
          • 加载中
          图(6)
          计量
          • 文章访问数:  52
          • HTML全文浏览量:  7
          • PDF下载量:  29
          • 被引次数: 0
          出版历程
          • 收稿日期:  2019-06-26
          • 录用日期:  2019-11-15
          • 刊出日期:  2020-11-20

          动态多目标优化进化算法研究进展

          doi: 10.16383/j.aas.c190489
            基金项目:  国家自然科学基金(62066041, 41861047)资助
            作者简介:

            西北师范大学物理与电子工程学院电子系教授. 主要研究方向为进化算法. 本文通信作者. E-mail: myjmyj@nwnu.edu.cn

            西北师范大学物理与电子工程学院硕士研究生. 主要研究方向为进化算法. E-mail: cm9690@126.com

            西北师范大学物理与电子工程学院硕士研究生. 主要研究方向为智能计算. E-mail: 15320834175@163.com

            西北师范大学物理与电子工程学院硕士研究生. 主要研究方向为智能计算. E-mail: shishengcss@163.com

            西北师范大学物理与电子工程学院硕士研究生. 主要研究方向为智能计算. E-mail: wzy1136390111@163.com

          摘要: 动态多目标优化问题(Dynamic multi-objective optimization problems, DMOPs)已成为工程优化的研究热点, 其目标函数, 约束函数和相关参数都可能随时间不断变化, 如何利用搜索到的历史最优解对新的环境变化做出快速响应, 是设计动态多目标优化进化算法(Dynamic multi-objective optimization evolutionary algorithm, DMOEA)的重点和难点. 本文在介绍DMOEA的基础上, 分析了近年来基于个体和种群级别的环境响应策略, 多策略混合等的DMOEA主要研究进展, 并介绍了DMOEA的性能测试函数, 评价指标以及在工程优化领域中的应用, 分析了DMOEA研究中仍面临的主要问题, 展望了未来的研究方向.

          English Abstract

          马永杰, 陈敏, 龚影, 程时升, 王甄延. 动态多目标优化进化算法研究进展. 自动化学报, 2020, 46(11): 2302?2318. doi: 10.16383/j.aas.c190489
          引用本文: 马永杰, 陈敏, 龚影, 程时升, 王甄延. 动态多目标优化进化算法研究进展. 自动化学报, 2020, 46(11): 2302?2318. doi: 10.16383/j.aas.c190489
          Ma Yong-Jie, Chen Min, Gong Ying, Cheng Shi-Sheng, Wang Zhen-Yan. Research progress of dynamic multi-objective optimization evolutionary algorithm. Acta Automatica Sinica, 2020, 46(11): 2302?2318. doi: 10.16383/j.aas.c190489
          Citation: Ma Yong-Jie, Chen Min, Gong Ying, Cheng Shi-Sheng, Wang Zhen-Yan. Research progress of dynamic multi-objective optimization evolutionary algorithm. Acta Automatica Sinica, 2020, 46(11): 2302?2318. doi: 10.16383/j.aas.c190489
          • 在工业应用和科学研究中, 例如作业车间调度、组合优化、工程设计、电力调度、投资管理、图像分割、网络通信、数据挖掘等优化领域, 决策者经常会遇到一类具有多个目标且随时间变化的优化问题[1], 这类问题通常称为动态多目标优化问题(Dynamic multi-objective optimization problems, DMOPs). DMOPs是指目标函数和决策变量与时间(环境)相关的一种优化问题, 它的最优解是一组动态地随时间(环境)变化的Pareto最优解集[2].

            与求解静态多目标优化问题不同, 处理此类优化问题时, 不仅需要对若干个相互之间存在冲突的目标进行优化, 还要同时应对目标函数和约束条件的变化[3]. 也就是说, 动态多目标优化算法必须能够及时跟踪变化的Pareto最优前沿[4], 用以提供多样性的解集来得到最新的随时间变化的近似Pareto最优前沿. 但是当环境变化的速度比较快时, 问题的求解会更加困难.

            自1960年以来, 研究者以大自然的生物进化理论(如孟德尔的遗传理论和达尔文的“物竞天择”进化论)为灵感来源, 模拟生物进化过程中的繁殖、变异、竞争和选择四个基本形式, 获得了解决复杂优化问题, 尤其是求解动态多目标优化问题的一种极为有效的新方法 — 动态多目标优化进化算法(Dynamic multi-objective optimization evolutionary algorithm, DMOEA). 自进化算法产生至今, 一直受到人们的广泛关注. 进化算法的主要特点是对问题的整个参数空间给出一种编码方案, 而不是直接对问题的具体参数进行处理. 进化算法的搜索过程不是从某一个单一的初始点开始搜索, 而是从一组初始点搜索, 通过对这些点进行交叉, 变异形成新的点, 并且利用优胜劣汰的规则在每一次迭代中选择多个最优的个体, 因此非常适合用于具有多个最优解的DMOPs的求解.

            近年来, 针对DMOPs的研究, 学者们做了许多工作. 自2003年, Farina等[5-6]第一次在多目标优化问题模型的基础上结合实际优化问题, 提出了动态多目标优化模型及其详细的数学表达式并构造了相应测试函数集, 有大量研究者投身于这项研究中, 并且也得到了很多不错的研究成果. 2007年, Deb等[7]通过改进经典多目标优化算法(Non-dominated sorting genetic algorithms) NSGA-II提出两个新的适合动态多目标优化的算法, 即引入一定比例随机个体的DNSGA-II-A算法和对现有个体增加变异率的DNSGA-II-B算法; 刘淳安等[8]设计了关于动态多目标优化算法的一个新的模型, 并证明了算法的收敛性; 2008年, Greeff等[9]采用每个目标利用一个粒子群进行优化的向量评估粒子群算法解决动态多目标优化问题; Koo等[10]提出了一种动态的多目标梯度搜索算法, 利用历史记忆法改善种群的分布, 帮助种群更好地收敛; 武燕等[11]通过对最优解的预测提出了一种新的多目标遗传算法, 利用历史信息进行最优解的预测; 郑金华等[12]提出了求解动态多目标优化问题的基于引导个体的预测策略, 指导种群更好地进行搜索; Murugananham等[13]提出了一种基于卡尔曼滤波的预测模型有助于引导搜索向着变化的最优解的方向进行, 从而加速种群收敛; Ruan等[14]提出一种混合分集维护的方法, 提高了Pareto前沿面在环境变化后的预测精度; Zou等[15]提出了一种基于动态进化环境模型的动态多目标进化算法, 通过引导方法提高种群的多样性, 使环境和种群同时进化. 近年来, 一些研究者将其他人工智能算法引入动态多目标优化, 尝试从新的角度提出新的动态多目标优化模型, 设计高效, 实用的动态多目标优化算法[2, 16-20].

            本文首先介绍了动态多目标优化进化算法, 包括DMOPs的相关数学定义, 分类及算法流程; 然后详细总结了近年来动态多目标优化进化算法的主要研究方向及其研究进展; 介绍了DMOEA的性能评价标准, 包括测试函数和评价指标等; 最后介绍了动态多目标优化在工程优化领域的应用, 指出了该研究领域目前仍存在的问题及未来的研究方向.

            • 一般地, 以最小化为例, 动态多目标优化问题可定义为如下形式[6]:

              $$ \left\lbrace \begin{aligned} &{\rm{min}}{ F}({ x}, t) = {f_1({ x},t),f_2({ x}, t),\cdots,f_m({ x}, t)}\\ &{\rm s.t.} \quad g_i({ x}, t)\leq 0, i = 1,2,\cdots,p\\ &\qquad h_j({ x}, t) = 0, j = 1,2,\cdots,q \end{aligned} \right. $$ (1)

              其中, t表示时间变量, $ { x} = (x_1,x_2,\cdots,x_n) $n维决策变量, 其定义域是$\Omega,$ $ { F} = (f_1,f_2,\cdots,f_m) $m维最小化问题的目标向量, $g_i({ x}, t)\leq 0\;(1\leq i\leq p)$为第i个不等式约束, $h_j({ x},t) = 0\;(1\leq j\leq q)$为第j个等式约束.

              定义1 (Pareto支配). pq是种群中任意两个个体, p支配q表示为$ f(p)\prec f(q) $, 当且仅当$f_i(p)\leq f_i(q)$, $\forall i = {1,2,\cdots,m}$$\exists \;j\in{1,2,\cdots,m}$满足$ f_j(p)< f_j(q) $.

              定义2 (Pareto最优解集, PS). $ { x} $为决策变量, $ \Omega $为决策空间, F为目标函数, 则PS定义为[21]:

              $$ \{PS = {x\in\Omega|\neg \exists x^*\in\Omega,{ F}(x^*)\prec { F}(x)}\} $$ (2)

              定义3 (Pareto最优前沿, PF). $ { x} $为决策变量, F为目标函数, 则PF定义为[21]:

              $$ PF = \{y = { F}({ x})| x\in PS\} $$ (3)

              DMOPs决策空间中的PS以及目标空间中的PF会随着时间的变化而变化, Farina等[5-6]针对PS和PF的变化类型将DMOPs分为以下4类:

              1) PS随时间变化, 而PF不随时间变化;

              2) PS和PF都随时间变化;

              3) PS不随时间变化, 而PF随时间变化;

              4) 问题环境发生改变, 但PS和PF都不随时间变化.

              上述这四类问题包涵了大部分动态多目标优化问题的PS和PF的变化情况. 除此之外, 实际应用中还存在另外一种相对比较特殊的情况, 当问题发生改变时, 上面几种变化的类型可能会在时间尺度内同时存在, 但在研究中一般只考虑前三种类型.

            • 对于求解DMOPs的算法, 在设计过程中往往需要考虑其随时间变化的强度或频率. 一般来说, 有两个方面, 即1) DMOPs随时间$ t $变化, 但是这种变化发生的相对比较缓慢, 即DMOPs在整个时间段内的变化非常稳定, 变化幅度维持在一个相对比较小的误差之内; 2) DMOPs随时间$ t $的变化而发生突变, 即在一个小的时间间隔内变化发生的不大或保持不变, 但会随机发生突然的变化. DMOEA的设计流程框图[22]图1所示.

              图  1  DMOEA的设计流程框图

              Figure 1.  The design flow chart of DMOEA

            • 进化算法是一种比较成熟的全局优化方法, 鲁棒性强, 适用性广. 它极具动态自适应性, 自组织, 自学习的特点, 可以高效地解决传统优化算法无法解决的复杂问题并且不受问题性质的限制, 近年来被广泛应用于动态多目标优化问题的求解. 目前针对DMOEA的研究大多集中在以下几个方面:

            • 1) 将动态问题转化为静态问题

              由于动态问题具有时间相关性, 可以将动态问题在时间序列上划分成多个时间段, 然后根据每个特定的时间段的静态问题进行优化, 有效降低了算法的收敛难度[9]. 刘淳安等[8, 23]将时间变量进行等区间离散化, 利用静态序值方差和静态密度方差将动态多目标优化问题转成多个双目标静态优化问题. 但是这种方法难于进行时间的划分, 时间划分间隔过大或过小都不具备代表性, 都有可能影响问题的优化. 此外, 这种方法在环境变化较小时能够跟踪动态多目标优化问题的最优解, 当环境变化较大时优化效果不是很理想.

              2) 基于记忆的方法

              基于记忆的方法, 并在搜索过程中进行更新. 当检测到变化时, 存储的解将被重新插入到当前种群中, 并对种群进行筛选使其只包含最优解. Trojanowski等[24]利用额外记忆来扩展每个个体, 使其可以获得双亲信息; 在随后的研究[25]中采取在每一次环境变化后, 种群中的一些个体被随机产生的个体所替代的方法改进算法. 刘敏等[26]设计了一种基于子问题的串联记忆方法, 利用过去相似环境中得到的最优解, 有效地响应新的环境变化, 实验结果显示这种方法有较强的动态跟踪性能, 更强的记忆能力, 能以最快的速度获得具有更好收敛性与分布性的解集. Yang等[27]提出了一种混合记忆和随机迁移算法, 以记忆中的最优解为基础, 生成随机移民来代替种群中表现不好的个体. 这样既能保持多样性, 又能使遗传算法更有效地适应变化的环境. 在文献[28]中, Azzouz等提出了一种结合记忆局部搜索和随机策略的自适应混合种群管理策略, 有效地解决部分环境变化较剧烈的DMOP问题.

              3) 基于预测的方法

              基于预测的方法主要是使用一个学习算法从以前的搜索中学习一些类型的模式, 并用来预测未来的变化趋势[29]. 通过每次环境变化后的预测机制为种群进化提供指导方向, 帮助算法快速响应新的变化. 针对预测策略, 主要有以下三个关键问题: a) DMOPs最终得到的是最优解集, 如果对所有的解进行预测, 计算量太大, 时间复杂度太高, 反而事与愿违. 因此如何选择有效的历史信息, 并能准确地描述Pareto最优前沿的一些特征点尤为关键; b) 应该采取什么样的预测模型, 使得算法能够更加准确地预测种群的进化方向; c) 采用什么样的措施来弥补预测误差.

              Hatzakis等[30]提出了一种前向反馈预测方法(Forward prediction strategy, FPS), 当检测到环境发生变化时, 重新初始化种群. 但是这种方法单纯地采用自回归模型, 忽视了Pareto最优前沿的分布特性, 影响预测效果[31], 这种方法假设仅靠2, 3个特征点便能刻画整个Pareto前沿, 若Pareto前沿的形状较为复杂, 算法的结果很可能与其所期望的结果不符[32]. Koo等[10]提出了一种动态多目标梯度算法, 使预测梯度的更新解保持在新的Pareto最优解集附近, 并帮助其他种群收敛, 该策略的优点在于计算成本低, 是一种适用于时间关键问题的动态处理技术. 彭星光等[32]利用动态优化过程中产生的Pareto最优解集与前一时刻解集进行关联建立时间序列, 并用线性预测方法生成新环境下的初始种群. 武燕等[11]提出了动态多目标优化的预测遗传算法, 与Pareto前沿的分布特征相结合, 通过聚类分析得到解集的质心进而得到预测解集, 但是如同文献[33]所言, 该算法根据有代表性的解预测环境变化后的解集, 当环境变化较大时, 预测的解集易出现偏差.

              Zhou等[34]在种群中心点构造时间序列的同时考虑Pareto最优前沿的分布特点, 进而设计出一种基于种群预测的优化算法(Population prediction strategy, PPS), 文献[31]指出这种算法要求动态Pareto最优解集或环境的变化模态之间要有相似性或显性规律, 因而会降低算法的适应性, 同时因在环境刚开始变化阶段历史信息的积累不足导致收敛性较差. Li等[35]提出了一种平均距离线性预测模型来解决一类特定具有平移Pareto最优解的动态多目标优化问题. 郑金华等[12]预测最优解的移动方向, 通过记录每次环境变化刚开始时和种群自主进化一小段时间内中心点位置的变化, 同时根据在该方向上均匀分布的多个检测个体, 选出一部分非支配的个体作为当前环境下的引导个体, 为了避免算法陷入局部最优, 在选出的引导个体周围一个小的范围内随机产生多个伴随引导个体, 但是由于基于种群中心点的位置变化判断种群进化方向的方法在种群尚未较好地收敛的情况下可能出现判断误差. 所以如何设计更加精准的判断算子来减少判断误差是未来需要继续努力的方向, 也是所有基于预测的算法的研究重点. Zou等[36]从前馈中心点预测Pareto最优解集, 并在预测种群中引入一个特殊点集(边界点或拐点), 来更准确地跟踪PF或PS. 丁进良等[31]提出基于参考点预测的方法, 将历史的预测误差作为反馈添加到预测模型中, 使预测结果更加准确.

              近年来, 新出现一些基于卡尔曼滤波的预测模型的算法, 卡尔曼滤波是利用包括噪声在内的观测数据预测未来数据, 能够快速准确地跟踪线性系统的变化, 计算复杂度低, 抗干扰能力强, 适合在环境变化时快速逼近最优解. Murugananham等[13]提出了一种基于卡尔曼滤波的预测模型(如图2所示)旨在解决一些特定的DMOPs, 这种方法有助于引导搜索向着变化的最优解的方向进行, 从而加速种群收敛. 李智翔等[37]提出了一种基于卡尔曼滤波的预测模型的算法, 将中心点预测值与垂直扰动分量相结合, 利用卡尔曼滤波模型跟踪不同时刻的解集中心点并预测其变化, 与其他优秀算法在公开测试集上的对比实验结果证明了该算法的有效性.

              图  2  基于卡尔曼滤波的预测模型图

              Figure 2.  Relationship of EA with KF model

              基于预测的算法的主要不足在于它们完全依赖于训练模型, 且在许多情况下, 训练过程中使用的数据并不能反映真实的场景[29]. 另外, 从统计学的角度看, 这种观点意味着动态优化问题的解集服从相同的分布. 就是说, 在某种程度上, 用来构造预测模型的解集和通过预测模型预测的解集服从独立同分布假设[38], 因而忽略了数据的非独立性和同分布性. 鉴于此, Jiang等[39]提出了一种新的基于域适应和非参数估计的分布式估计动态多目标算法, 将蒙特卡洛方法和迁移学习方法结合, 以维持算法在时间和空间的勘探开发平衡. 但是这方面的研究目前来说还是不够多. 所以, 如果未来能在克服独立同分布性带来的局限的研究中取得进一步突破的话, 基于预测的算法的性能可以有很大的提升空间.

            • 1) 多种群策略

              多种群策略把种群划分成多个子种群, 一部分用于进一步开发, 跟踪当前的极值点, 另一部分继续探索整个解集空间, 寻找新的极值点, 从而提升算法的搜索效率. 通过多种群维持种群多样性的方式有助于探索有前景的搜索区域[40]. Branke 等[41]提出了一种自组织侦察群方法, 即当发现一个峰值时, 种群将划分出一个子种群来监视这个峰值, 其余个体(称为主种群)继续寻找新的峰值, 这种方法在一些动态测试问题中表现出很好的性能. 龙文[42]通过佳点集这种方法产生初始的种群来增强算法的鲁棒性和全局搜索能力; 然后在个体的适应度的水平上将种群分别分成三个子种群, 并执行利用不同实验向量产生策略和控制参数设置的差分算法, 在不增加算法的复杂性的基础上保证了各子种群算法的独立性和优越性.

              胡成玉等[43]利用多种群竞争和合作两种模式, 从而快速有效地求解DMOPs. 多种群竞争模式主要目的是对解集空间进行“勘探” (Exploration)搜索, 当竞争失败时, 自适应切换到协作模式对解集空间进行“开采” (Exploitation)搜索. 张世文等[44]采用不同的生态策略来处理不同种群对环境的变化, 进而追踪该问题的Pareto最优解, 结果表明算法有较强的收敛能力和跟踪Pareto前沿变化的能力以及保持种群多样性的能力. 文献[45]提出了一种求解动态优化问题性能的改进算法的新框架, 将调度的概念引入多种群方法中, 对性能最好的子种群进行更多的评估. 在此框架的基础上, 提出了两种子种群调度方法, 第一种方法将子种群的质量和多样性水平结合作为一个反馈参数–性能指标, 用于检测表现最优的子种群, 如图3 (a)所示; 第二种方法以学习自动机为中心单元对多个子种群进行调度操作, 如图3 (b)所示.

              图  3  动态环境中多种群调度方法的框架

              Figure 3.  Framework for multi-population methods with scheduling in dynamic environments

              最近, 文献[46]从人体内多个系统之间的协作机制出发, 提出了一种基于生物启发的自学习协同进化算法(Bio-inspired self-learning coevolutionary algorithm, BSCA), 并将该算法成功用于物联网服务的动态多目标优化, 以降低能耗和服务时间. BSCA由三层组成(体系结构如图4所示), 第一层是由多个子种群协同进化而成, 以获得不一样的Pareto前沿; 在第一层得到的解集的基础上, 第二层进一步增加解集的多样性; 第三层采用自适应梯度细化搜索策略和动态优化方法对第二层找到的解集进行细化, 以应对并发的多个服务请求的变化, 有效提高了解集的精度.

              图  4  BSCA算法体系结构图

              Figure 4.  The architecture of BSCA inspired by human NEI systems

              2) 保持或增加种群多样性

              如果种群多样性过快丧失, 容易使算法陷入局部收敛或者早熟, 但是过高的多样性也可能会导致进化停滞[40], 所以如何确定适合的多样性以探索更有前景的搜索区域是研究的重点.

              当检测到环境变化时, 通过使用某种特定类型的方法来增加种群的多样性. 根据环境变化剧烈程度的不同, 这种方法又可以分为两类. 当环境变化范围较大时, 采用种群重新初始化的方法; 当环境变化范围较小时, 采用超变异或随机移民的方法.

              Cobb等[47]提出了触发超突变法, 该方法的基本思想是当检测到环境变化时, 突变率会立即增加, 这将使收敛的种群再次发散. 这种方法需要一些改进, 其中之一就是突变率在整个过程中处于不受控制的变化状态, 最终会导致算法性能下降. 因此, Vavak等[48]提出了一种变异算子VLS (Variable local search, VLS)来解决这个问题, VLS采用的策略是逐步提高突变率. Cobb等[47]比较了固定变异率, 过度变异和随机移民三种不同变异方法在动态环境中的应用, 结果表明, 利用过度变异的遗传算法在缓慢变化的环境中(低强度)表现最好, 若环境发生较大变化, 随机移民的方法会更好一些.

              Woldesenbet等[49]提出了一种动态进化算法, 该算法根据个体由于环境的变化而引起的函数值的变化, 以及决策变量对目标空间中相应变化的平均敏感性来重新定位个体, 这种方法在一定程度上避免了以往方法的缺点. Eriksson等[50]提出了一种利用“Life time adaptation” 策略的进化算法, 也就是在进化算法的整个进化过程中, 对个体估值之前先要利用某种适应性调节策略对个体进行调节, 通过这种方法来保持种群的多样性. Deb等[7]提出一种随机初始化种群个体的方法, 这虽然会在一定程度上增加种群多样性, 但却是一种盲目增加种群多样性的方法, 当环境的变化程度加剧时, 算法性能会下降. Zou等[36]通过在预测解附近加入高斯扰动来增加种群多样性, 使所提出的算法能够在保持种群多样性的同时增加收敛速度. 李智翔等[37]在预测的新解中加入了一个垂直于预测变化方向的超平面随机扰动, 以增强解集的多样性, 避免陷入局部最优.

              在保持多样性的方法中, 大多数算法都假设避免种群收敛可以帮助算法尽快跟踪变化的最优解, 保持多样性是实现这一目标的有效手段之一. Grefenstette等[51]提出一种随机移民的方法, 即在每一代, 种群中的部分个体都会被换成随机产生的个体, 这种方法在种群中引入新的遗传物质, 可以避免整个种群在进化过程中向一个小区域收敛. 然而, 随机移民方法的缺点是引入个体的适应度值通常会比较低, 因此会在选择阶段大量被淘汰, 很难将不同的基因引入种群中. 为了解决这一问题, 提出了混合移民框架[52-53], 基于记忆[54]和基于精英策略[54]的移民方法, 这些方法都能有效地解决周期性变化的动态多目标优化问题, 但是如果动态环境的知识是有限的话, 效率会大大降低. 对一个动态多目标优化进化算法来说, 它应该能在几代之间寻找最佳的权衡结果, 种群的多样性直接影响到算法的跟踪寻优能力, 因此保持种群的多样性则显得更为重要[55].

            • Ruan等[14]为了提高预测精度, 提出了一种混合分集维护方法. 第一步, 基于中心点的移动方向, 通过预测将一些解重新定位到新的Pareto前沿附近; 第二步, 逐步搜索适用于决策空间中产生的一些均匀的解集, 以弥补第一步产生的误差, 同时进一步提高收敛性和种群的多样性; 第三步, 在下一个可能的PS区域内随机产生一些不同的个体, 增加种群的多样性. 最后, 对这三个步骤生成的组合解进行非支配排序后, 选择收敛性和多样性较好的解, 使得预测更加准确. Liu等[56]提出一种基于多种群的粒子群优化框架(框架示意图如图5所示), 用于动态环境下的优化问题. 目标函数的数量决定粒子群的数量, 所有这些粒子群利用信息共享策略协同进化. 在此基础上, 提出了一种新的速度更新方程和有效的边界约束技术, 使用相似性检测操作符来检测环境是否发生了变化, 然后使用基于记忆的动态机制来响应变化, 结果显示该方法相对于其他对比的算法有更好的表现, 尤其是在决策变量非线性相关的问题上.

              图  5  多种群的粒子群优化框架示意图

              Figure 5.  The framework of multi-swarm particle swarm optimization

              Rong等[57]提出一种多种群的预测算法, 根据提出的分类策略, 将种群聚类为若干具有代表性的群体, 群体的数量根据环境变化的强度来调整. 但是, 该方法只考虑决策空间中两个连续变化相似且线性的情况, 为了使所提出的方法适用于更多的实际案例, 今后还需要进行更多的研究. Liang等[58]采取记忆和预测混合的合成算法检测环境变化, 并识别变化与历史变化的相似性, 如果检测到的变化与任何历史变化不相似, 则使用基于前两个连续的种群中心的差异预测来重新安置新环境中的种群个体; 否则使用一种基于记忆的技术来预测种群成员的新位置. 两种响应机制都将部分现有解与随机生成的解混合使用, 以减轻由于急剧或不规则变化而导致的预测误差的影响.

            • 随着上述求解动态多目标优化问题方法的不断改进, DMOPs的其他研究成果也不断涌现出来. 郑金华等[59]提出了一种多目标进化模型, 用进化环境记录群体进化过程中产生的信息, 反过来指导种群搜索, 进而达到环境与种群的共同进化. 之后, Zou等[15]提出了一种基于动态进化环境模型的算法, 当环境不变时, 算法利用进化环境记录进化过程中产生的知识和信息, 进而指导搜索. 当检测到变化, 建立动态进化环境模型(模型框图如图6所示)来帮助种群适应新的环境, 通过引导方法提高种群的多样性, 使环境和种群同时进化, 与其他几种算法相比, 这种方法在处理设计变量之间存在线性或非线性相关的测试问题上更有效.

              图  6  动态进化环境模型框图

              Figure 6.  A general framework of dynamic environment evolutionary model

              Yu等[60]提出了跟随时间的鲁棒优化找到一组随时间推移而逐渐健壮的解集来解决连续变化的动态多目标优化问题. Liu等[61]利用核心分布模型, 估计未来环境中的Pareto解, 当检测到环境的变化, 从以前的搜索算法使用收集到的环境信息预测下一个环境Pareto解的位置, 仿真结果表明, 该算法能够在不同的环境下找到动态多目标优化问题的最优解. Turky等[62]提出了一种多种群的电磁算法来解决动态最优问题, 这种方法说明了基于种群的方法对于保持种群多样性的重要性, 特别是在处理动态优化问题时, 由于这些变化发生在优化过程中, 而该算法能够跟踪这些变化. Liu等[63]提出了一种两阶段进化操作的算法来解决Pareto最优前沿随时间连续且缓慢变化的问题. 耿焕同等[64]采用自适应的冷热启动策略交叉来解决带约束的DMOPs, 该算法能在不同环境下动态识别变化的程度, 增加初始种群多样性以提高算法的跟踪效果, 且能在同一环境下自适应调整交叉算子以提高算法的收敛速度. 焦儒旺等[65]采用基于学习的机制求解相关约束优化问题. 陈美蓉等[66]提出了时间鲁棒性和性能鲁棒性定义, 并转化为两种鲁棒优化模型, 构造了动态多目标分解鲁棒优化方法, 结果表明该方法能够得到满足决策者精度要求, 且具有较长平均生存时间的动态鲁棒Pareto最优解. Barba-González等[67]将jmetal框架的多目标优化特性与Apache Spark集群计算系统相结合, 提出了一种基于jmetal的大数据优化软件平台来解决基于纽约市实时交通数据的旅行商问题(Travelling salesman problem, TSP)的动态双目标实例.

              另一方面, 自2007年Zhang等[68]提出基于分解的多目标优化进化算法以来, 这种将多目标优化问题分解为若干子问题进行计算, 使得适应度分配和多样性控制的难度有所降低的简单有效的分解概念吸引了越来越多的研究人员的关注[69-73], 并在动态多目标优化问题中得到了很好的应用. Liu等[74]提出每个目标由一个种群优化, 每个种群与其他种群共享信息的种群独立进化的算法, 采用外部存档来存储进化过程中从所有种群中选择的非劣解, 并将该存档作为最终解输出. Qiao等[75]提出了基于分解的单角度自适应惩罚的多目标进化算法能够在整个进化过程中动态地调整每一个权重向量的惩罚值. Cao等[76]提出基于分解的利用差分模型的动态多目标优化进化算法, 随着时间变化的近似Pareto最优解的运动代表了质心的运动, 假设其他解的运动和质心一样, 用最新的质心位置的历史信息来建立差分模型估计当检测到环境变化时质心的下一个位置, 其他解的新的位置依靠他们当前的位置和估计的运动预测. 预测的解和一些保留解结合形成一个新种群来探索新的环境, 用来更好地跟踪新的Pareto最优解集或者Pareto最优前沿.

              另外, 许多研究人员将动态多目标优化进化算法与其他策略(如膜计算[77], 投影映射[78], 档案交叉[79], 免疫克隆[80], 正交设计[2]和神经网络[16-18]等)进行了融合, 也取得了较好的效果.

            • 测试函数在评价算法性能和指导算法设计方面发挥着重要作用, 在DMOEA的研究中, 通常采用FDA[5-6]和DMOP[7]两个系列的测试函数集来测试算法的性能[81]. 在FDA测试集中, PF和PS随时间而变化, 而在整个运行过程中, 决策变量的数量, 目标的数量和搜索空间的边界保持不变. FDA测试集的另一个特点是决策变量之间是线性相关的, DMOP系列测试函数集是对FDA的延伸. 此外, Zhou等[34]提出了F5$ \sim $F9系列动态多目标测试函数集, 决策变量是非线性相关的, 函数集中F5$ \sim $F7是双目标问题, F8是多目标问题, F9是复杂的双目标问题, 和其他双目标问题相比, 收敛难度比较大. 最近, Jiang等[3]设计了一类基准生成器, 关注一些具有挑战性的且在现有文献中很少被考虑到的DMOP特性, 例如混合的Pareto前沿(凸和凹), 非单调性, 时变变量的联系, 混合类型的变化, 随机变化的类型等, 他们还从该基准生成器中生成了一个包含十个具有不同动态特性的实例的测试套件.

              事实上, 研究者在选择基准测试问题时寻找的不是它们是如何生成的, 而是它们代表了什么样的动态类型以及它们具有什么特性. 文献[82]总结了每个通用测试问题的特性, 并根据以下不同的标准将问题分为不同的组:

              1)时间相关性: 问题的未来行为是否取决于算法找到的当前和/或以前的解集;

              2)可预测性: 所生成的变化是否遵循规则模式(例如, 以固定的步长移动的最优解, 循环/周期的变化以及预先可记录的变化区间)是可预测的还是不可预测的;

              3)可见性: 优化算法是否可以检测到变化, 如果可以, 是否可以仅使用几个检测算子检测变化(在搜索空间中重新评估目标函数或约束函数以检测变化的特殊位置);

              4)约束问题: 问题是否受约束, 如果是, 约束是否随时间变化;

              5)目标数量: 问题有一个目标还是有多个目标;

              6)变化类型: 详细说明变化如何发生;

              7)变化是否是循环或周期性的;

              8)变化的因素: 变量域, 目标函数, 变量数量, 约束或其他参数.

            • 动态多目标优化的目标不仅是获得一组接近最优且多样化的PFA, 而且是要追踪动态的不断变化的PF, PFA是指在t时刻存储在归档集中的一组非劣解. 因此, DMOEA的性能指标必须要遵循以下准则[83]: 1)在面对不断变化的空间时, 算法在实现优化目标(近似性, 多样性和抗干扰)方面的有效性; 2)算法收敛到新解集的速度, 因为可能存在时间限制.

              近年来被广泛应用的有反转世代距离评价指标(Inverted generational distance, IGD)[84], 超体积比指标(Hyper volume ratio, HVR)[85]等, 由于这些指标大多是用来度量多目标优化算法的性能, 一些研究人员将这些指标进行调整并将其运用于度量动态多目标优化算法的性能.

              1) 世代距离-GD

              GD是Van Veldhuizen与Lamont[86]在1998年提出来的一种评价方法, 用来表示所获得解集的收敛性, GD值越小, 表示算法得到的解集越接近真实的Pareto最优解集, 函数定义如下:

              $$ GD = \frac{\sqrt{\displaystyle\sum \nolimits_{i = 1}^n{d_i}^2}}{n} $$ (4)

              n$ d_i $分别表示通过算法获得的Pareto最优解的数量, 算法中第i个解到PF的最小的欧几里得距离.

              2) 反世代距离-IGD

              Van Veldhuizen等[84]提出的IGD用于同时评价解集的收敛性和多样性, IGD的函数定义如下:

              $$ IGD(PF_t,P_t) = \frac{\displaystyle\sum \nolimits_{v\in PF_t}{d(v,P_t)}}{\left|PF_t\right|} \hspace{3pt} $$ (5)
              $$ d(v,P_t) = {\rm{min}}_{u\in P_t}\sqrt{\sum\limits_{j = 1}^m(f_j^v-f_j^u)^2} $$ (6)

              $ PF_t $代表在t时刻均匀分布在真实最优前沿上的一组Pareto最优点的集合, $ P_t $表示由算法在t时刻得到的近似Pareto点的集合, dvu之间的最小的欧几里得距离, vu分别为PFtPt中的点. IGD值越低, 表明该算法的收敛性和多样性越好.

              为了度量动态多目标优化算法的性能, 文献[34, 37, 87]引入MIGD进行度量:

              $$ MIGD = \frac{1}{|T|}\sum\limits_{t\in T}{{IGD}(t)} $$ (7)

              式中, IGD(t)表示t时刻的IGD值, T是运行中的一组离散时间点, $ \left|T\right| $T的基数.

              一般情况下, 可用1)中的GD和2)中的IGD来计算最优解和近似解在决策空间中的差值, 是因为它们提供了不同的优化度量, 而它们之间又紧密相关. 通过研究这两个指标在代际间的兼容性, 可以更好地理解算法的优化性能. 例如, 如果两个度量指标在同一方向上移动, 我们可以得出这样的结论: 算法的解集正在接近或偏离PS或PF. 如果这两个指标朝着不同的方向移动, 我们就无法对算法的优化性能得出太多结论[55].

              3) 鲁棒性-Robustness

              在动态环境中, 应尽可能地保证算法的鲁棒性, 也就是说, 算法必须抵抗变化, 不受不确定性和不相关的干扰的影响. 为此, 文献[3]提出Robustness指标度量算法在一系列动态环境变化后的鲁棒性, 函数定义如下:

              $$ R(PM) = \sqrt{\frac{1}{T_s-1}\sum\limits_{t = 1}^{T_s}(PM_t-\overline{PM})^2} $$ (8)
              $$ \overline{PM} = \sum\limits_{t = 1}^{T_s}{\frac{PM_t}{T_s}} $$ (9)

              其中R(PM)表示时间步长$ T_s $的指标PM的鲁棒性, 指标PM可以是接近多目标优化目标的任何一元性能指标, 多样性或分布性, PMt表示t时刻种群的PM值, $ \overline{PM} $PM经历$ T_s $时间后的平均值. R(PM)的值越小, 表明指标PM 的鲁棒性能越好.

              4) 超体积比-HVR

              超体积比HVR是在超体积(Hyper volume, HV)[84]的基础上发展而来的, 作为DMOEA的评价指标时, 函数定义如下[88]:

              $$ HV\!R(t) = \frac{HV(S(t))}{HV(P^*(t))} $$ (10)
              $$ HV = volume \left(\bigcup\limits_{i = 1}^{|S|}{v_i}\right) $$ (11)

              S(t)是算法得到的非支配解集, P*(t)表示动态变化的Pareto前沿, volume表示体积, vi 表示P*(t)与第i个解集构成的超体积. HV表示算法获得的非支配解集与P*(t)围成的目标空间中区域的体积. HVR$( t )$可以给出算法保持多样性的信息, 当S(t)和P*(t)重合时, HVR(t)的最大值为1. HVR$( t)$的值越大, 说明算法的多样性越好.

              5) 空间评价指标-$ \Delta $和SP

              Deb等[89]提出评价近似解集中个体在目标空间的分布状况的评价指标$ \Delta $, 定义为:

              $$ \Delta = {\Sigma_{i = 1}^{|PF|}{\frac{d_i-\overline{d}}{|PF|}}} $$ (12)

              式中, $ d_i $是解中非支配边界上两个连续的向量的欧几里得距离, $ \overline{d} $是所有解欧几里得距离的平均距离. 这种评价方法相对来说较适合用于2维目标空间之中, 在高维目标问题(尤其是当目标大于3时)效果不太理想.

              类似于上面$ \Delta $空间评价指标, 文献[90]提出了计算解集分布性的方法, 该指标用来衡量在目标空间的解集分布是否均匀, 其函数定义为:

              $$ SP = \sqrt{\frac{1}{n-1}\sum\limits_{i = 1}^n{(\overline{d}-d_i)^2}} $$ (13)
              $$ d_i = {\rm{min}}_{j}\left(\sum\limits_{k = 1}^m{|f_k^i(x)\!-\!f_k^j(x)|}\right),\quad i,j = 1,2,\cdots,n $$ (14)

              式中, $ d_i $是第i个解与其最近解之间的欧几里得距离, $ \overline{d} $为所有$ d_i $的平均距离, n是已知Pareto边界的大小. SP反映了算法所得到的Pareto前沿的均匀性, SP越小说明算法得到的Pareto最优解分布的越是均匀. 当这种方法与其他方法结合时, 它能提供所得解的分布信息, 从而使结果更加准确. 与$ \Delta $的不同之处在于, 此类方法能够较好地应用于2维以上的情况, 但是这种方法的计算复杂度较高.

              6)收敛性指标-$ \overline{F}_{BOG} $

              以在经历过所有的环境下寻优的最优解的均值来度量算法的收敛性, 公式如下[91]:

              $$ \overline{F}_{BOG} = \frac{1}{G}\sum\limits_{i = 1}^G \left(\frac{1}{N}\sum_{j = 1}^{N}{F_{BOGij}}\right) $$ (15)

              式中, G是运行次数, N是环境变化的次数, $ {F_{BOGij}} $为第i次运行第j个环境下的最优个体适应值.

              事实上, 随着算法的不断改进, 评价指标也会有相应的调整, Azzouz等[92]采用了最大传播度量(Maximum spread, MS), Goh等[83]用变量迭代距离(Variable generational distance, VGD)进行度量, Cámara等[93-94]通过优化系统的准确度, 稳定性对算法性能评估等.

            • 伴随着动态多目标优化进化算法的不断发展, 它在现实生活中的应用领域也在不断扩大, 或者说动态多目标优化进化算法的发展是随着它在工程优化等诸多领域的广泛应用而不断发展的, 因为算法的终极设计目标是为了服务于实际生产生活. 因此针对动态多目标优化的研究有重要的理论价值和工程价值.

              1) 城市经济效益评估

              文献[95]提出一个多目标决策模型, 构造出一种新的转换函数, 根据转换函数将决策矩阵归一化为效用矩阵, 提高了决策的分辨精度, 突出了“奖惩”原则, 并且将这个方法应用到某省五个城市三年综合经济效益的整体评估中, 得到了满意的结果.

              2) 化学工程

              动态优化求解在很大程度上依赖于基础数学模型的精度. 然而, 这些模型只代表了真实动态过程的近似结果, 它们的预测依赖于一组参数值. 当应用基于模型的最优解时, 这些参数值很难精确估计. 文献[96]讨论了一种基于Sigma点的高效鲁棒动态优化方法, 并给出了该方法在不确定性非线性动态化学气相沉积反应器实例研究中的应用.

              文献[97]针对污水处理过程提出一种动态多目标优化框架, 可以同时动态优化多个性能指标的溶解氧浓度和硝酸盐浓度的设定值, 除此之外, 还结合神经网络, 提出一种只需要工厂的处理数据的在线建模方法建立性能指标和优化变量之间的映射关系. 结果表明, 所提方法在满足污水排放要求的同时, 能显著降低能耗.

              此外, 文献[98-99]也都分别将动态优化应用于湿法炼锌和葡萄酒最佳配方的选择, 并且得到了不错的成果.

              3) 路径规划

              文献[100]重点研究了导致环境污染和能源消耗的燃料消耗问题, 车辆的负荷和行驶距离, 在此基础上建立相应的碳排放模型, 并将其作为优化目标, 并且建立了动态多目标车辆路径问题模型. 提出了一种两阶段动态多目标车辆路径选择方法. 结果表明, 该方法得到的路径具有较好的稳定性和鲁棒性. 在文献[101-102]也有关于路径规划的应用. 此外, 在生态驾驶[103-104], 汽车类机器人控制[105-106]也有不少的应用.

              4) 移动自组网

              文献[107]将动态负载均衡聚类问题(Dynamic Load Balanced Clustering Problem, DLB-CP)转化为一个动态优化问题. 在此基础上, 提出了利用一系列动态遗传算法来解决移动自组网(Mobile Ad Hoc Network, MANET)中的DLB-CP问题. 其中, 每个个体代表一个可行的聚类结构, 并根据负载平衡指标对其适应度进行评估. 利用各种动态处理技术帮助种群更好地处理拓扑变化并生成紧密相关的高质量的解. 实验结果表明, 这些算法可以很好地用于DLB-CP问题, 并且性能优于不考虑动态网络优化要求的传统算法.

              文献[108]为提高天线设计的鲁棒性和稳定性, 提出了一种将天线设计问题建模为约束优化问题(Constraint Optimization Problem, COP)的新方法, 介绍了一个求解COP的框架. 该框架将COP转换为等价的动态约束多目标优化问题(Dynamic constrained multi-objective optimization problem, DCMOP). 采用动态约束多目标进化算法对转换后的DCMOP进行求解, 解决天线的设计问题. 然后, 应用该方法设计了多种天线. 对这几种天线的计算结果表明, 所提出的方法能较好地满足天线的设计要求.

              5) 系统优化问题

              文献[109]提出新的粒子群优化算法并将其应用到动态电力系统优化问题中, 仿真实验表明, 该算法在求解实际动态问题时表现较好.

              文献[110]为实现微电网系统运行的经济和环境双重优化目标, 以独立的系统仿真模块和运行优化模块为核心, 建立了微电网多目标动态优化调度的一般模型. 在算法中引入了初始点引导技术和去重操作, 有效地改善了算法的收敛性能和Pareto前沿的分布特性. 并将该模型和方法应用于典型风光蓄柴微电网系统的日前优化调度, 证实了所建模型和所提方法的有效性.

              文献[111-113]分别将动态多目标优化应用到电动泵控制系统设计, 水库实时防洪调度, 时变不稳定系统的最优控制等问题中, 并证明了这种结合的有效性.

              6) 矿石分配

              文献[114]将矿石分配问题转化为动态多目标优化问题, 为解决这个问题, 提出一个新的非支配排序精英遗传算法(DNSGA-Ⅱ). 结果显示, 该算法可以有效地得到动态多目标原矿分配优化问题的PF, 并且可以在保持良好的种群多样性的同时加速种群收敛, 尤其是在环境变化比较大的情况下.

              7) 与神经网络结合

              文献[16-18, 115]通过将动态多目标优化与神经网络等结合, 并应用于无人机控制, 云计算, 数据流分类以及深度强化学习. 结果显示, 这种结合有效提升了算法的收敛速度, 同时拓宽了动态多目标优化算法的应用领域.

            • 随着动态多目标问题优化更深层次的要求的出现, 动态多目标优化进化算法已成为解决此类问题的有效手段, DMOEA的研究也逐步成为研究的热点. 但是由于动态多目标问题的要求复杂, 情况多变, 尚有许多研究工作有待深入开展.

              1) 如何才能更加有效地检测环境变化. 检测环境变化是动态多目标优化算法设计的第一步, 也是非常重要的一个环节, 越及时精确地检测环境变化, 得到的算法的优化效果越好. 因此, 如何设计出更加精确, 适合的检测算子并及时检测环境变化, 进而提高之后的环境响应策略的实施效率是首先需要解决的问题. 通常来说, 检测环境变化主要通过重新评估个体, 或者检测种群的统计信息, 如果这些数据发生变化, 则说明环境发生变化[34]. 此外, 文献[116]提出以稳态方式检测变化, 在每一次迭代中, 个体(按随机顺序)被逐一检查其以前的目标值和重新评估的目标值之间的差异, 如果种群个体中存在差异, 则视为成功检测到环境的变化, 且不再需要对其他个体进行进一步检查. 该检测方法有利于对环境变化的快速, 稳定反应, 但计算成本较高. 这些新的环境变化的检测方法都是值得关注的.

              2) 如何选择基于预测的方法. 基于预测的方法是该领域目前的研究热点, 但同时也存在几个问题: a) 动态多目标优化问题最终得到的是最优解集, 若对所有的解进行预测, 计算量太大, 时间复杂度太高. 因此如何选择有效的历史信息, 并能准确地描述Pareto最优前沿的一些特征点尤为关键; b) 应该采取什么样的方法建立什么样的预测模型, 使得算法能够更加准确地预测种群的进化方向; c) 采用什么样的措施来弥补预测误差.

              3) 保持种群多样性是确保算法性能的关键. 种群多样性的过高过低都会影响进化结果, 所以如何确定适合的多样性以探索更有前景的搜索区域, 进而提升算法的跟踪寻优能力也是进一步研究的重点.

              4) 如前文所述的各种研究方法侧重点不同, 优化效果也不大相同, 各有优缺点, 所以在今后的研究中如何针对求解的问题, 结合各种策略的优点设计出性能更好的算法, 以更有效地追踪优化问题随时间变化的最优解的运行方向, 也是需要关注的问题.

              5) 如何进一步完善评价标准. 考虑不同特点的动态多目标优化问题, 进一步完善算法的性能评价标准, 确保其能够准确地反映算法的性能.

              6) 实际应用. 如何改进现有算法, 引入人工智能等方法并将其更好地应用到实际工程或其他场景中[117], 使算法得到更好的实践效果.

            • 近年来, 随着智能计算技术以及相关学科理论知识的进一步发展, 动态多目标优化问题的研究已经引起学者的极大兴趣. 展望未来, 相信这一研究将会取得更好的成果, 理论将更加完善, 算法将更加有效, 解决问题的能力将会进一步提高, 相关领域的应用将会更加广阔, 其前景值得学者关注.

              随着社会的发展, 城镇化水平的不断提升, 城市交通问题愈发显著, 而“如何使交通技术能够登上一个新的台阶”也成为研究的热点. 例如Eco-driving, 即生态驾驶, 是一种节能和环境可持续发展的手段, 起源于20世纪90年代. 在高速铁路运行系统中, 生态驾驶是一项重要的节能交通运营措施. 生态驾驶优化可以在线应用于高速列车运行调整阶段, 以改善列车延误问题; 或在一般情况下, 使列车适应线路不断变化的情况. 文献[103]利用列车仿真结果的实时性和准确性将列车运行调整问题描述为一个动态多目标优化模型. 优化模型的目标是通过动态多目标优化算法不断地计算出一组最优速度曲线并且在列车运行过程中进行实时更新, 其仿真结果有助于提高铁路运行人员对列车正点率(反映铁路工作水平、考核铁路运输组织工作的综合性指标之一)的信心. 该文的研究表明, 列车运动仿真具有模型灵活性和准确性的优点, 可以实时地对列车运动进行仿真, 以最大限度地减少能量消耗. 使用这种算法可以节省能源, 还允许铁路运营商平衡能源消耗和延迟到达的风险, 在不降低服务质量的情况下, 系统的能源性能得到改善[104].

              依托互联网技术, 自动驾驶技术和信息传输技术, 实现信息共享, 结合生态驾驶技术, 建立智慧型交通系统将是未来的发展趋势[118], 而人工智能技术的飞速发展和不断完善, 为这一领域的发展提供了无限的可能. 同时随着我国八纵八横的高速铁路网宏大蓝图的实现, 生态驾驶必将大放异彩, 而动态多目标优化也必将成为这宏大蓝图背后强有力的理论支撑.

              在检测技术与自动化装置方面, 我国在动态系统的容错控制和智能电网的研究方面有了显著的进展, 已经处于国际领先水平, 但仍有许多问题需要解决, 如动态系统早期微小故障检测, 动态系统的预测与维护中的多目标函数优化以及将火力发电厂的控制融入智能电网等问题[119]. 而在未来, 这一系列问题的解决都将离不开动态多目标优化这一领域的理论支撑.

              流程工业发展趋势是在两化深度融合基础上实现制造过程智能化和绿色化. 以人工智能驱动的自动化为主要内容, 借助云计算、大数据、物联网等技术, 推动全流程精准建模和分析, 打造贯穿全流程生产、全供应链运营、全生命周期管控的一体化控制决策平台, 进而提升生产效率, 提高企业经济效益和社会效益, 最终实现流程工业升级转型[119], 而文献[96-97, 114, 120-121]证明了动态多目标优化在这一领域的巨大贡献.

          参考文献 (121)

          目录

            /

            返回文章
            返回