动态进化多目标优化中的串式记忆方法

doi:10.11896/j.issn.1002-137X.2016.12.044

摘要/Abstract

摘要： 如何利用过去搜索到的最优解对新的环境变化做出快速响应,是动态进化多目标优化(Dynamic Evolutio-nary Multi- objective Optimization,DEMO)研究的一大挑战。为此提出了一种串式记忆(Bunchy Memory,BM)方法。设计了基于极小化效应函数的抽取过程,从非支配集中抽取一串记忆串,以便保持记忆的多样性;将记忆体组织成串式队列的方式,以便将过去数次环境变化下抽取的记忆串存入记忆体;提出了基于二进制锦标赛选择的检索过程以复用记忆体中过去的最优解,来快速响应新的变化。BM方法具有良好的记忆效果,显著地提高了DEMO算法的收敛性和多样性。4个标准测试问题上的实验结果表明,BM方法比其它3种方法具有更好的记忆能力。相应地,集成了BM方法的DEMO算法所获得解集的收敛性与多样性也明显好于其它3种DEMO算法。

关键词: 进化计算,多目标优化,动态环境,记忆,Pareto最优前沿

Abstract: One of the challenges in dynamic evolutionary multi-objective optimization (DEMO) is how to exploit past optimal solutions to help DEMO algorithm track and adapt to the changing environment quickly.To alleviate the above difficulty,this paper proposed a bunchy memory (BM) method for DEMO.In the BM method,firstly,a sampling procedure based on minimized utility function is designed to sample a bunch of memory points from the non- dominate set so as to maintain good diversity of memory.Then,the memory is organized as a bunchy queue,so that a number of bunches of memory points sampled from past environment changes can be easily stored in the memory.Next,past optimal solutions stored in the memory are reused to rapidly respond to the new change by using a retrieving procedure based on binary tournament selection.The BM method has good memory effect and improves the convergence and diversity of DEMO algorithm significantly.Experiment results on four benchmark test problems indicate that the proposed BM method has better memory performance than other three methods.Accordingly,the convergence and diversity of the DEMO algorithm,which incorporates the BM method,are also obviously better than those of the other three DEMO algorithms.

Key words: Evolutionary computation,Multi-objective optimization,Dynamic environment,Memory,Pareto optimal front

刘敏,曾文华,刘玉珍. 动态进化多目标优化中的串式记忆方法[J]. 计算机科学, 2016, 43(12): 241-247. https://doi.org/10.11896/j.issn.1002-137X.2016.12.044

LIU Min, ZENG Wen-hua and LIU Yu-zhen. Bunchy Memory Method for Dynamic Evolutionary Multi-objective Optimization[J]. Computer Science, 2016, 43(12): 241-247. https://doi.org/10.11896/j.issn.1002-137X.2016.12.044

参考文献

[1] Coello Coello C A,Lamont G B,Van Veldhuizen D A.Evolutio-nary Algorithms for Solving Multi-Objective Problems(2nd ed)[M].New York:Springer-Verlag,2007
[2] Farina M,Deb K,Amato P.Dynamic multiobjective optimization problems:Test cases,approximations,and applications [J].IEEE Transaction on Evolutionary Computation,2004,8(5):425-442
[3] Goh C K,Tan K C.A competitive-cooperative coevolutionaryparadigm for dynamic multiobjective optimization [J].IEEE Transaction on Evolutionary Computation,2009,13(1):103-127
[4] Branke J.Evolutionary Optimization in Dynamic Environments[M].Boston:Kluwer Academic Publishers,2002
[5] Shang R H,Jiao L C,Gong M G,et al.An immune algorithm for dynamic multi-objective optimization[J].Journal of Software,2007,8(11):2700-2711(in Chinese) 尚荣华,焦李成,公茂果,等.免疫克隆算法求解动态多目标优化问题[J].软件学报,2007,18(11):2700-2711
[6] Liu M,Zeng W H.Memory enhanced dynamic multi-objectiveevolutionary algorithm based on decomposition[J].Journal of Software,2013,24(7):1571-1588(in Chinese) 刘敏,曾文华.记忆增强的动态多目标分解进化算法[J].软件学报,2013,24(7):1571-1588
[7] Muruganantham A,Tan K C,et al.Evolutionary dynamic multiobjective optimization via kalman filter prediction[J].IEEE Transactions on Cybernetics,2015,5(99):1-12
[8] Hu C Y,Yao H,Yan X S.Multiple particle swarms coevolutio-nary algorithm for dynamic multi-objective optimization problems and its application[J].Journal of Computer Research and Deve-lopment,2013,50(6):1313-1323(in Chinese) 胡成玉,姚宏,颜雪松.基于多粒子群协同的动态多目标优化算法及应用[J].计算机研究与发展,2013,50(6):1313-1323
[9] Zhang S W,Li Z Y,Chen S M,et al.Dynamic multi-objective optimization algorithm based on ecological strategy[J].Journal of Computer Research and Development,2014,51(6):1313-1330(in Chinese) 张世文,李智勇,陈少淼,等.基于生态策略的动态多目标优化算法[J].计算机研究与发展,2014,51(6):1313-1330
[10] Liu R C,Ma Y J,Zhang L,et al.Dynamic multi-objective immune optimization algorithm based on predictaion strategy[J].Chinese Journal of Computers,2015,38(8):1544-1560(in Chinese) 刘若辰,马亚娟,张浪,等.基于预测策略的动态多目标免疫优化算法[J].计算机学报,2015,38(8):1544-1560
[11] Deb K,Rao U B N,Karthik S.Dynamic multi-objective optimization and decision-making using modified NSGA-II:A case study on hydro-thermal power scheduling [C]∥Proc of the 4th International Conference on Evolutionary Multi-criterion Optimization (EMO 2007).Berlin Heidelberg:Springer-Verlag,2007:803-817
[12] Huang L,Suh I H,Abraham A.Dynamic multi-objective optimization based on membrane computing for control of time-varying unstable plants [J].Information Sciences,2011,182(11):2370-2391
[13] Zhang Z H.Multiobjective optimization immune algorithm in dynamic environments and its application to greenhouse control [J].Applied Soft Computing,2008,8(2):959-971
[14] Nguyen S,Zhang M,et al.Automatic design of scheduling policies for dynamic multi-objective job shop scheduling via cooperative coevolution genetic programming [J].IEEE Transactions on Evolutionary Computation,2014,18(2):193-208
[15] Ghannadpour S F,Noori S,et al.A multi-objective dynamic vehicle routing problem with fuzzy time windows:Model,solution and application [J].Applied Soft Computing,2014,14(3):504-527
[16] Zhou A,Jin Y C,Zhang Q F.A population prediction strategy for evolutionary dynamic multiobjective optimization[J].IEEE Transactions on Cybernetics,2014,44(1):40-53
[17] Zheng J H,Peng Z,Zhou J,et al.A predication strategy based on guide-individual for dynamic multi-objective optimization[J].Acta Electronica Sinica,2015,43(9):1816-1825(in Chinese) 郑金华,彭舟,邹娟,等.基于引导个体的预测策略求解动态多目标优化问题[J].电子学报,2015,43(9):1816-1825
[18] Yang S X,Yao X.Population-based incremental learning with associative memory for dynamic environments [J].IEEE Trans on Evolutionary Computation,2008,12(5):542-561
[19] Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II [J].IEEE Trans on Evolutio-nary Computation,2002,6(2):182-197
[20] Wang Y,Li B.Multi-strategy ensemble evolutionary algorithmfor dynamic multi-objective optimization [J].Memetic Computing,2010,2(1):3-24
[21] Koo W T,Goh C K,Tan K C.A predictive gradient strategy for multiobjective evolutionary algorithms in a fast changing environment [J].Memetic Computing,2010,2(2):87-110
[22] Li X D,Branke J,Kirley M.On performance metrics and particle swarm methods for dynamic multiobjective optimization problems [C]∥Proceedings of the 2007 Congress on Evolutionary Computation (CEC 2007).Singapore:IEEE Press,2007:576-583
[23] Liu M,Zheng J H,et al.An adaptive diversity introduction me-thod for dynamic evolutionary multiobjective optimization [C]∥Proceedings of the 2014 Congress on Evolutionary Computation (CEC2014).Beijing,IEEE Press,2014:3160-3167

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed