Computer Science ›› 2016, Vol. 43 ›› Issue (12): 241-247.doi: 10.11896/j.issn.1002-137X.2016.12.044

Previous Articles     Next Articles

Bunchy Memory Method for Dynamic Evolutionary Multi-objective Optimization

LIU Min, ZENG Wen-hua and LIU Yu-zhen   

  • Online:2018-12-01 Published:2018-12-01

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

[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

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[7] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .
[8] WANG Shuai, LIU Juan, BI Yao-yao, CHEN Zhe, ZHENG Qun-hua and DUAN Hui-fang. Automatic Recognition of Breast Gland Based on Two-step Clustering and Random Forest[J]. Computer Science, 2018, 45(3): 247 -252 .
[9] LI Shan and RAO Wen-bi. Video-based Detection of Human Motion Area in Mine[J]. Computer Science, 2018, 45(4): 291 -295 .
[10] HAN Kui-kui, XIE Zai-peng and LV Xin. Fog Computing Task Scheduling Strategy Based on Improved Genetic Algorithm[J]. Computer Science, 2018, 45(4): 137 -142 .