计算机科学 ›› 2016, Vol. 43 ›› Issue (12): 241-247.doi: 10.11896/j.issn.1002-137X.2016.12.044

• 智能优化 • 上一篇    下一篇

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

刘敏,曾文华,刘玉珍   

  1. 湖南科技大学计算机科学与工程学院 湘潭411201;知识处理与网络化制造湖南省普通高等学校重点实验室 湘潭411201,厦门大学软件学院 厦门361005,湖南科技大学计算机科学与工程学院 湘潭411201;知识处理与网络化制造湖南省普通高等学校重点实验室 湘潭411201
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受湖南省教育厅资助

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

摘要: 如何利用过去搜索到的最优解对新的环境变化做出快速响应,是动态进化多目标优化(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

[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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75, 88 .
[2] 夏庆勋,庄毅. 一种基于局部性原理的远程验证机制[J]. 计算机科学, 2018, 45(4): 148 -151, 162 .
[3] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[4] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[5] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[6] 钟菲,杨斌. 基于主成分分析网络的车牌检测方法[J]. 计算机科学, 2018, 45(3): 268 -273 .
[7] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99, 116 .
[8] 王帅,刘娟,毕姚姚,陈哲,郑群花,段慧芳. 基于两步聚类和随机森林的乳腺腺管自动识别方法[J]. 计算机科学, 2018, 45(3): 247 -252 .
[9] 李珊,饶文碧. 基于视频的矿井中人体运动区域检测[J]. 计算机科学, 2018, 45(4): 291 -295 .
[10] 韩奎奎,谢在鹏,吕鑫. 一种基于改进遗传算法的雾计算任务调度策略[J]. 计算机科学, 2018, 45(4): 137 -142 .