决策空间定向搜索的高维多目标优化策略
作者:
作者简介:

郑金华(1963-),男,湖南邵东人,博士,教授,博士生导师,CCF高级会员,主要研究领域为进化计算,多目标优化算法,机器学习;邹娟(1977-),女,博士,副教授,CCF专业会员,主要研究领域为人工智能,优化算法设计,进化算法;董南江(1992-),男,硕士生,CCF学生会员,主要研究领域为多目标进化计算;杨圣祥(1972-),男,博士,教授,博士生导师,主要研究领域为智能计算,动态多目标进化优化;阮干(1993-),男,博士生,主要研究领域为动态多目标进化计算.

通讯作者:

董南江,E-mail:643260047@qq.com;邹娟,E-mail:zoujuan@xtu.edu.cn

中图分类号:

TP301

基金项目:

国家自然科学基金(61772178,61502408,61673331);湖南省教育厅重点项目(17A212);湖南省自然科学基金(2017JJ4001);湖南省科技计划(2016TP1020)


High-dimensional Multi-objective Optimization Strategy Based on Decision Space Oriented Search
Author:
Fund Project:

National Natural Science Foundation of China (61772178, 61502408, 61673331); Key Project of Hu'nan Provincial Education Department (17A212); Natural Science Foundation of Hu'nan Province of China (2017JJ4001); Science and Technology Plan Project of Hu'nan Province of China (2016TP1020)

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [32]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    传统的多目标进化算法(MOEA)对于低维连续的多目标优化问题已经具有良好的性能,但是随着优化问题目标维数的增加,优化难度也将剧增,主要原因是算法本身搜索能力不足,维数增加时选择压力变小,收敛性和分布性冲突难以平衡.利用连续多目标优化问题的特性,针对高维多目标优化的难点所在,提出了一种在决策空间的定向搜索策略(decision space,简称DS),该策略可与基于支配关系的MOEA相结合.DS首先对优化问题进行采样分析,对问题特性进行解析,得到收敛性子空间控制向量和分布性子空间控制向量.将算法搜索过程分为收敛性搜索阶段和分布性搜索阶段,分别对应收敛性子空间和分布性子空间,在不同阶段搜索时,利用采样分析结果,对生成子代个体的区域进行宏观的影响.将收敛性和分布性分阶段考虑,避免了收敛性和分布性难以平衡的难点,同时,具体在某一阶段内搜索资源相对集中,一定程度上增加了算法的搜索能力.实验结合了DS策略的NSGA-Ⅱ,SPEA2算法与原NSGA-Ⅱ,SPEA2算法进行实验对比,并以DS-NSGA-Ⅱ为例,与其他高维算法MOEAD-PBI,NSGA-Ⅲ,Hype,MSOPS,LMEA进行对比实验.实验结果表明,DS策略的引入,使得NSGA-Ⅱ,SPEA2算法在高维多目标优化问题上的性能有了显著提高,DS-NSGAⅡ与现有的经典高维多目标算法相比有较强的竞争力.

    Abstract:

    Traditional multi-objective evolutionary algorithm (MOEA) have sound performance when solving low dimensional continuous multi-objective optimization problems. However, as the optimization problems' dimensions increase, the difficulty of optimization will also increase dramatically. The main reasons are the lack of algorithms' search ability, and the smaller selection pressure when the dimension increases as well as the difficulty to balance convergence and distribution conflicts. In this study, after analyzing the characteristics of the continuous multi-objective optimization problem, a directional search strategy based on decision space (DS) is proposed to solve high dimensional multi-objective optimization problems. This strategy can be combined with the MOEAs based on the dominating relationship. DS first samples solutions from the population and analyzes them, and obtains the controlling vectors of convergence subspace and distribution subspace by analyzing the problem characteristics. The algorithm is divided into convergence search stage and distribution search stage, which correspond to convergent subspace and distributive subspace respectively. In different stages of search, sampling analysis are used results to macroscopically control the region of offspring generation. The convergence and distribution are divided and emphasized in different stages to avoid the difficulty of balancing them. Additionally, it can also relatively focuses the search resources on certain aspect in certain stages, which facilitates the searching ability of the algorithm. In the experiment, NSGA-Ⅱ and SPEA2 algorithms are compared combining DS strategy with original NSGA-Ⅱ and SPEA2 algorithms, and DS-NSGA-Ⅱ is used as an example to compare it with other state-of-the-art high-dimensional algorithms, such as MOEAD-PBI, NSGA-Ⅲ, Hype, MSOPS, and LMEA. The experimental results show that the introduction of the DS strategy greatly improves the performance of NSGA-Ⅱ and SPEA2 when addressing high dimensional multi-objective optimization problems. It is also shown that DS-NSGA-Ⅱ is more competitive when compared the existing classical high dimensional multi-objective algorithms.

    参考文献
    [1] Zheng JH, Zou J. Multi-Objective Evolutionary Optimization. Beijing:Science Press, 2017(in Chinese).
    [2] Cui XX. Multi-Objective Evolutionary Algorithm and its Application. Beijing:National Defence Industry Press, 2006(in Chinese).
    [3] Deb K, Agrawal RB. Simulated binary crossover for continuous search space. Complex Systems, 1994,9(3):115-148.
    [4] Deb K. Real-Coded genetic algorithms with simulated binary crossover:Studies on multimodal and multiobjective problems. Complex Systems, 1995. 9.
    [5] Deb K, Goyal M. A Combined Genetic Adaptive Search (GeneAS) for Engineering Design. 1996. 30-45.
    [6] Price K, Price K. Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Kluwer Academic Publishers, 1997.[doi:10.1023/a:1008202821328]
    [7] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ. IEEE Trans. on Evolutionary Computation, 2002,6(2):182-197.[doi:10.1109/4235.996017]
    [8] Zitzler E, Laumanns M, Thiele L. SPEA2:Improving the performance of the strength Pareto evolutionary algorithm. In:Proc. of the Int'l Conf. on Parallel Problem Solving from Nature (PPSN 2004), 2004. 742-751.[doi:10.1007/978-3-540-30217-9_75]
    [9] Zhang Q, Li H. MOEA/D:A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation, 2007,11(6):712-731.[doi:10.1109/TEVC.2007.892759]
    [10] Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I:Solving problems with box constraints. IEEE Trans. on Evolutionary Computation, 2014,18(4):577-601.[doi:10.1109/TEVC.2013.2281535]
    [11] Emmerich M, Beume N, Naujoks B. An EMO algorithm using the hypervolume measure as selection criterion. In:Proc. of the Evolutionary Multi-Criterion Optimization. Berlin, Heidelberg:Springer-Verlag, 2005. 62-76.[doi:10.1007/978-3-540-31880-4_5]
    [12] Ikeda K, Kita H, Kobayashi S. Failure of Pareto-based MOEAs:Does non-dominated really mean near to optimal? In:Proc. of the 2001 Congress on Evolutionary Computation, Vol.2. IEEE, 2001. 957-962.[doi:10.1109/CEC.2001.934293]
    [13] Brockhoff D, Friedrich T, Hebbinghaus N, et al. On the effects of adding objectives to plateau functions. IEEE Trans. on Evolutionary Computation, 2009,13(3):591-603.[doi:10.1109/tevc.2008.2009064]
    [14] Schutze O, Lara A, Coello CAC. On the influence of the number of objectives on the hardness of a multiobjective optimization problem. IEEE Trans. on Evolutionary Computation, 2011,15(4):444-455.[doi:10.1109/TEVC.2010.2064321]
    [15] Batista LS, Campelo F, Guimaraes FG, et al. A comparison of dominance criteria in many-objective optimization problems. In:Proc. of the Evolutionary Computation. IEEE, 2011. 2359-2366.[doi:10.1109/CEC.2011.5949909]
    [16] Li M, Yang S, Liu X. Pareto or non-Pareto:Bi-criterion evolution in multiobjective optimization. IEEE Trans. on Evolutionary Computation, 2016,20(5):645-665.[doi:10.1109/TEVC.2015.2504730]
    [17] Miettinen K. Nonlinear Multiobjective Optimization. Boston:Kluwer Academic, 1999.
    [18] Hillermeier C. Nonlinear Multiobjective Optimization-A GeneralizedHomotopy Approach. Boston:Birkhauser, 2001.[doi:10.2307/254267]
    [19] Zhang X, Tian Y, Cheng R, et al. A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization. IEEE Trans. on Evolutionary Computation, 2018,22(1):97-112.[doi:10.1109/TEVC.2016.2600642]
    [20] Zou J, Fu L, Yang S, et al. A many-objective evolutionary algorithm based on rotated grid. In:Proc. of the Applied Soft Computing. 2018. 67.[doi:10.1016/j.asoc.2018.02.031]
    [21] Zou J, Zhang Y, Yang S, et al. Adaptive neighborhood selection for many-objective optimization problems. Applied Soft Computing, 2018,64:186-198.[doi:10.1016/j.asoc.2017.11.041]
    [22] Liu Y, Zheng JH, Zou J, Yu G. Preparation of papers for acta automatica sinica. Acta Automatica Sinica, 2017,44(7):1304-1320(in Chinese with English abstract).[doi:10.16383/j.aas.2017.c160315]
    [23] Gan R, Yu G, Zheng J, et al. 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]
    [24] Hughes EJ. Multiple single objective Pareto sampling. In:Proc. of the 2003 Congress on Evolutionary Computation (CEC 2003), Vol.4. IEEE, 2004. 2678-2684.[doi:10.1109/CEC.2003.1299427]
    [25] Deb K, Thiele L, Laumanns M, et al. Scalable Test Problems for Evolutionary Multiobjective Optimization. 2005. 105-145.[doi:10.1007/1-84628-137-7_6]
    [26] Huband S, Hingston P, Barone L, et al. A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. on Evolutionary Computation, 2006,10(5):477-506.[doi:10.1109/tevc.2005.861417]
    [27] Zhang Q, Zhou A, Jin Y. RM-MEDA:A regularity model-based multiobjective estimation of distribution algorithm. IEEE Trans. on Evolutionary Computation, 2008,12(1):41-63.[doi:10.1109/TEVC.2007.894202]
    [28] While L, Hingston P, Barone L, et al. A faster algorithm for calculating hypervolume. IEEE Trans. on Evolutionary Computation, 2006,10(1):29-38.[doi:10.1109/TEVC.2005.851275]
    附中文参考文献:
    [1] 郑金华.邹娟.多目标进化优化.北京:科学出版社,2017.
    [2] 崔逊学.多目标进化算法及其应用.北京:国防工业出版社,2006.
    [22] 刘元,郑金华,邹娟,喻果.基于领域竞赛的多目标优化算法.自动化学报,2017,44(7):1304-1320.[doi:10.16383/j.aas.2017. c160315]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

郑金华,董南江,阮干,邹娟,杨圣祥.决策空间定向搜索的高维多目标优化策略.软件学报,2019,30(9):2686-2704

复制
分享
文章指标
  • 点击次数:2036
  • 下载次数: 4860
  • HTML阅读次数: 1520
  • 引用次数: 0
历史
  • 收稿日期:2018-08-08
  • 最后修改日期:2019-01-07
  • 在线发布日期: 2019-05-24
文章二维码
您是第19754391位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号