不规则优化问题中基于动态资源分配的高维多目标优化算法

董明刚; 刘宝; 敬超

doi:10.1631/FITEE.1900321

Your Location：

Home >

Browse articles >

不规则优化问题中基于动态资源分配的高维多目标优化算法

常规文章 | Updated：2022-05-19

- 不规则优化问题中基于动态资源分配的高维多目标优化算法
- A many-objective evolutionary algorithm based on decomposition with dynamic resource allocation for irregular optimization
- 信息与电子工程前沿（英文） 2020年21卷第8期页码：1171-1190
- Affiliations：
  
  College of Information Science and Engineering, Guilin University of Technology, Guilin 541004, China
  Guangxi Key Laboratory of Embedded Technology and Intelligent System, Guilin 541004, China
  Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic & Technology, Guilin 541004, China
- Author bio：
  
  Chao JING, E-mail: jingchao@glut.edu.cn
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos. 61563012, 61802085, and 61203109), the Guangxi Natural Science Foundation of China (Nos. 2014GXNSFAA118371, 2015GXNSFBA139260, and 2020GXNSFAA159038), the Guangxi Key Laboratory of Embedded Technology and Intelligent System Foundation (No. 2018A-04), and the Guangxi Key Laboratory of Trusted Software Foundation (Nos. kx202011 and kx201926)
- DOI：10.1631/FITEE.1900321
  中图分类号： TP391
- 收稿：2019-06-28，
  
  修回：2020-;7-21，
  
  纸质出版：2020-08
- Accepted：
Scan QR Code
董明刚, 刘宝, 敬超. 不规则优化问题中基于动态资源分配的高维多目标优化算法[J]. 信息与电子工程前沿（英文）, 2020,21(8):1171-1190.

Ming-gang DONG, Bao LIU, Chao JING. A many-objective evolutionary algorithm based on decomposition with dynamic resource allocation for irregular optimization[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(8): 1171-1190.
董明刚, 刘宝, 敬超. 不规则优化问题中基于动态资源分配的高维多目标优化算法[J]. 信息与电子工程前沿（英文）, 2020,21(8):1171-1190. DOI： 10.1631/FITEE.1900321.

Ming-gang DONG, Bao LIU, Chao JING. A many-objective evolutionary algorithm based on decomposition with dynamic resource allocation for irregular optimization[J]. Frontiers of Information Technology & Electronic Engineering, 2020, 21(8): 1171-1190. DOI： 10.1631/FITEE.1900321.

摘要

多目标优化问题广泛存在于高速列车头形设计、重叠社区检测、电力调度等领域。为解决这类问题，目前方法主要集中于求解具有规则性帕累托前沿的问题，而非具有不规则帕累托前沿的问题。针对这种情况，提出一种基于动态资源分配分解的高维多目标进化算法（MaOEA/D-DRA）进行不规则优化。该算法能够根据问题的帕累托前沿形状，将计算资源动态分配到不同搜索区域。在搜索过程中使用进化种群和外部存档，从外部存档中提取的信息用于引导进化种群到不同搜索区域。进化种群采用切比雪夫方法将问题分解为若干子问题，并以协作方式优化所有子问题。采用转化的密度估计方法更新外部档案。将所提算法与5种最先进的多目标进化算法对比。实验结果表明，所提算法在收敛速度和种群成员多样性方面优于5种对比算法。与加权和方法和基于惩罚的边界相交方法比较，将切比切夫方法集成到算法中，对性能有一定提高。

Abstract

The multi-objective optimization problem has been encountered in numerous fields such as high-speed train head shape design

overlapping community detection

power dispatch

and unmanned aerial vehicle formation. To address such issues

current approaches focus mainly on problems with regular Pareto front rather than solving the irregular Pareto front. Considering this situation

we propose a many-objective evolutionary algorithm based on decomposition with dynamic resource allocation (MaOEA/D-DRA) for irregular optimization. The proposed algorithm can dynamically allocate computing resources to different search areas according to different shapes of the problem's Pareto front. An evolutionary population and an external archive are used in the search process

and information extracted from the external archive is used to guide the evolutionary population to different search regions. The evolutionary population evolves with the Tchebycheff approach to decompose a problem into several subproblems

and all the subproblems are optimized in a collaborative manner. The external archive is updated with the method of shift-based density estimation. The proposed algorithm is compared with five state-of-the-art many-objective evolutionary algorithms using a variety of test problems with irregular Pareto front. Experimental results show that the proposed algorithm outperforms these five algorithms with respect to convergence speed and diversity of population members. By comparison with the weighted-sum approach and penalty-based boundary intersection approach

there is an improvement in performance after integration of the Tchebycheff approach into the proposed algorithm.

关键词

Keywords

references

M Asafuddoula , , , T Ray , , , R Sarker . . A decomposition- based evolutionary algorithm for many objective optimization . . IEEE Trans Evol Comput , , 2015 . . 19 ( ( 3 ): ): 445 - - 460 . . DOI: 10.1109/TEVC.2014.2339823 http://doi.org/10.1109/TEVC.2014.2339823 . .

XY Cai , , , YX Li , , , Z Fan , , , 等 . . An external archive guided multiobjective evolutionary algorithm based on decomposition for combinatorial optimization . . IEEE Trans Evol Comput , , 2015 . . 19 ( ( 4 ): ): 508 - - 523 . . DOI: 10.1109/TEVC.2014.2350995 http://doi.org/10.1109/TEVC.2014.2350995 . .

XY Cai , , , ZX Yang , , , Z Fan , , , 等 . . Decomposition-based- sorting and angle-based-selection for evolutionary multi- objective and many-objective optimization . . IEEE Trans Cybern , , 2017 . . 47 ( ( 9 ): ): 2824 - - 2837 . . DOI: 10.1109/TCYB.2016.2586191 http://doi.org/10.1109/TCYB.2016.2586191 . .

XY Cai , , , ZW Mei , , , Z Fan , , , 等 . . A constrained decomposition approach with grids for evolutionary multiobjective optimization . . IEEE Trans Evol Comput , , 2018 . . 22 ( ( 4 ): ): 564 - - 577 . . DOI: 10.1109/TEVC.2017.2744674 http://doi.org/10.1109/TEVC.2017.2744674 . .

S Chand , , , M Wagner . . Evolutionary many-objective optimization: a quick-start guide . . Surv Oper Res Manag Sci , , 2015 . . 20 ( ( 2 ): ): 35 - - 42 . . DOI: 10.1016/j.sorms.2015.08.001 http://doi.org/10.1016/j.sorms.2015.08.001 . .

R Cheng , , , YC Jin , , , M Olhofer , , , 等 . . A reference vector guided evolutionary algorithm for many-objective optimization . . IEEE Trans Evol Comput , , 2016 . . 20 ( ( 5 ): ): 773 - - 791 . . DOI: 10.1109/TEVC.2016.2519378 http://doi.org/10.1109/TEVC.2016.2519378 . .

R Cheng , , , MQ Li , , , Y Tian , , , 等 . . Benchmark Functions for the CEC'2018 Competition on Many-Objective Optimization , , : : United Kingdom University of Birmingham , , 2018 . . .

CAC Coello . . Evolutionary multi-objective optimization: a historical view of the field . . IEEE Comput Intell Mag , , 2006 . . 1 ( ( 1 ): ): 28 - - 36 . . DOI: 10.1109/MCI.2006.1597059 http://doi.org/10.1109/MCI.2006.1597059 . .

CAC Coello , , , MS Lechuga . . MOPSO: a proposal for multiple objective particle swarm optimization . . Proc Congress on Evolutionary Computation , , 2002 . . p.1051 - - 1056 . . DOI: 10.1109/CEC.2002.1004388 http://doi.org/10.1109/CEC.2002.1004388 . .

DW Corne , , , NR Jerram , , , JD Knowles , , , 等 . . PESA-Ⅱ: region-based selection in evolutionary multiobjective optimization . . Proc 3 rd Annual Conf on Genetic and Evolutionary Computation , , 2001 . . p.283 - - 290 . . . .

I Das , , , JE Dennis . . Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems . . SIAM J Optim , , 1998 . . 8 ( ( 3 ): ): 631 - - 657 . . DOI: 10.1137/S1052623496307510 http://doi.org/10.1137/S1052623496307510 . .

K Deb , , , M Goyal . . A combined genetic adaptive search (GeneAS) for engineering design . . Comput Sci Inform , , 1996 . . 26 ( ( 4 ): ): 30 - - 45 . . . .

K Deb , , , H Jain . . An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part Ⅰ: solving problems with box constraints . . IEEE Trans Evol Comput , , 2014 . . 18 ( ( 4 ): ): 577 - - 601 . . DOI: 10.1109/TEVC.2013.2281535 http://doi.org/10.1109/TEVC.2013.2281535 . .

K Deb , , , A Pratap , , , S Agarwal , , , 等 . . A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ . . IEEE Trans Evol Comput , , 2002 . . 6 ( ( 2 ): ): 182 - - 197 . . DOI: 10.1109/4235.996017 http://doi.org/10.1109/4235.996017 . .

K Deb , , , L Thiele , , , M Laumanns , , , 等 . . Scalable test problems for evolutionary multiobjective optimization. In: Abraham A, Jain L, Goldberg R (Eds.), Evolutionary Multiobjective Optimization , , : : London Springer , , 2005 . . p.105 - - 145 . . DOI: 10.1007/1-84628-137-7_6 http://doi.org/10.1007/1-84628-137-7_6 . .

M Elarbi , , , S Bechikh , , , A Gupta , , , 等 . . A new decomposition-based NSGA-Ⅱ for many-objective optimization . . IEEE Trans Syst Man Cybern Syst , , 2018 . . 48 ( ( 7 ): ): 1191 - - 1210 . . DOI: 10.1109/TSMC.2017.2654301 http://doi.org/10.1109/TSMC.2017.2654301 . .

C He , , , Y Tian , , , YC Jin , , , 等 . . A radial space division based evolutionary algorithm for many-objective optimization . . Appl Soft Comput , , 2017 . . 61 603 - - 621 . . DOI: 10.1016/j.asoc.2017.08.024 http://doi.org/10.1016/j.asoc.2017.08.024 . .

ZN He , , , GG Yen . . Many-objective evolutionary algorithm: objective space reduction and diversity improvement . . IEEE Trans Evol Comput , , 2016 . . 20 ( ( 1 ): ): 145 - - 160 . . DOI: 10.1109/tevc.2015.2433266 http://doi.org/10.1109/tevc.2015.2433266 . .

S Huband , , , P Hingston , , , L Barone , , , 等 . . A review of multiobjective test problems and a scalable test problem toolkit . . IEEE Trans Evol Comput , , 2006 . . 10 ( ( 5 ): ): 477 - - 506 . . DOI: 10.1109/tevc.2005.861417 http://doi.org/10.1109/tevc.2005.861417 . .

H Jain , , , K Deb . . An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part Ⅱ: handling constraints and extending to an adaptive approach . . IEEE Trans Evol Comput , , 2014 . . 18 ( ( 4 ): ): 602 - - 622 . . DOI: 10.1109/TEVC.2013.2281534 http://doi.org/10.1109/TEVC.2013.2281534 . .

S Kukkonen , , , J Lampinen . . GDE3: the third evolution step of generalized differential evolution . . IEEE Congress on Evolutionary Computation , , 2005 . . p.443 - - 450 . . DOI: 10.1109/CEC.2005.1554717 http://doi.org/10.1109/CEC.2005.1554717 . .

BD Li , , , JL Li , , , K Tang , , , 等 . . Many-objective evolutionary algorithms: a survey . . ACM Comput Surv , , 2015 . . 48 ( ( 1 ): ): 13 DOI: 10.1145/2792984 http://doi.org/10.1145/2792984 . .

H Li , , , QF Zhang . . Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-Ⅱ . . IEEE Trans Evol Comput , , 2009 . . 13 ( ( 2 ): ): 284 - - 302 . . DOI: 10.1109/TEVC.2008.925798 http://doi.org/10.1109/TEVC.2008.925798 . .

K Li , , , K Deb , , , QF Zhang , , , 等 . . An evolutionary many- objective optimization algorithm based on dominance and decomposition . . IEEE Trans Evol Comput , , 2015 . . 19 ( ( 5 ): ): 694 - - 716 . . DOI: 10.1109/TEVC.2014.2373386 http://doi.org/10.1109/TEVC.2014.2373386 . .

MQ Li , , , SX Yang , , , XH Liu . . Shift-based density estimation for Pareto-based algorithms in many-objective optimization . . IEEE Trans Evol Comput , , 2014 . . 18 ( ( 3 ): ): 348 - - 365 . . http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=2f3f2502d8399b54bae18d429a4b1622 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=2f3f2502d8399b54bae18d429a4b1622 , , . .

MQ Li , , , SX Yang , , , XH Liu . . Bi-goal evolution for many- objective optimization problems . . Artif Intell , , 2015 . . 228 45 - - 65 . . DOI: 10.1016/j.artint.2015.06.007 http://doi.org/10.1016/j.artint.2015.06.007 . .

YP Liu , , , DW Gong , , , XY Sun , , , 等 . . Many-objective evolutionary optimization based on reference points . . Appl Soft Comput , , 2017 . . 50 344 - - 355 . . DOI: 10.1016/j.asoc.2016.11.009 http://doi.org/10.1016/j.asoc.2016.11.009 . .

RC Purshouse , , , PJ Fleming . . On the evolutionary optimization of many conflicting objectives . . IEEE Trans Evol Comput , , 2007 . . 11 ( ( 6 ): ): 770 - - 784 . . DOI: 10.1109/TEVC.2007.910138 http://doi.org/10.1109/TEVC.2007.910138 . .

YT Qi , , , XL Ma , , , F Liu , , , 等 . . MOEA/D with adaptive weight adjustment . . Evol Comput , , 2014 . . 22 ( ( 2 ): ): 231 - - 264 . . DOI: 10.1162/EVCO_a_00109 http://doi.org/10.1162/EVCO_a_00109 . .

WY Ruan , , , HB Duan . . Multi-UAV obstacle avoidance control via multi-objective social learning pigeon-inspired optimization . . Front Inform Technol Electron Eng , , 2020 . . 21 ( ( 5 ): ): 740 - - 748 . . DOI: 10.1631/FITEE.2000066 http://doi.org/10.1631/FITEE.2000066 . .

A Santiago , , , HJF Huacuja , , , B Dorronsoro . . A survey of decomposition methods for multi-objective optimization. In: Castillo O, Melin P, Pedrycz W (Eds.), Recent Advances on Hybrid Approaches for Designing Intelligent Systems , , : : Cham Springer , , 2014 . . p.453 - - 465 . . DOI: 10.1007/978-3-319-05170-3_31 http://doi.org/10.1007/978-3-319-05170-3_31 . .

H Seada , , , K Deb . . A unified evolutionary optimization procedure for single, multiple, and many objectives . . IEEE Trans Evol Comput , , 2016 . . 20 ( ( 3 ): ): 358 - - 369 . . DOI: 10.1109/TEVC.2015.2459718 http://doi.org/10.1109/TEVC.2015.2459718 . .

H Seada , , , M Abouhawwash , , , K Deb . . Multiphase balance of diversity and convergence in multiobjective optimization . . IEEE Trans Evol Comput , , 2019 . . 23 ( ( 3 ): ): 503 - - 513 . . DOI: 10.1109/TEVC.2018.2871362 http://doi.org/10.1109/TEVC.2018.2871362 . .

Y Tian , , , R Cheng , , , XY Zhang , , , 等 . . PlatEMO: a MATLAB platform for evolutionary multi-objective optimization[Educational Forum] . . IEEE Comput Intell Mag , , 2017 . . 12 ( ( 4 ): ): 73 - - 87 . . DOI: 10.1109/MCI.2017.2742868 http://doi.org/10.1109/MCI.2017.2742868 . .

Y Tian , , , R Cheng , , , XY Zhang , , , 等 . . An indicator-based multiobjective evolutionary algorithm with reference point adaptation for better versatility . . IEEE Trans Evol Comput , , 2018 . . 22 ( ( 4 ): ): 609 - - 622 . . DOI: 10.1109/TEVC.2017.2749619 http://doi.org/10.1109/TEVC.2017.2749619 . .

A Trivedi , , , D Srinivasan , , , K Sanyal , , , 等 . . A survey of multiobjective evolutionary algorithms based on decomposition . . IEEE Trans Evol Comput , , 2017 . . 21 ( ( 3 ): ): 440 - - 462 . . DOI: 10.1109/TEVC.2016.2608507 http://doi.org/10.1109/TEVC.2016.2608507 . .

GP Wang , , , HW Jiang . . Fuzzy-dominance and its application in evolutionary many objective optimization . . Int Conf on Computational Intelligence and Security Workshops , , 2007 . . p.195 - - 198 . . DOI: 10.1109/CISW.2007.4425478 http://doi.org/10.1109/CISW.2007.4425478 . .

TC Wang , , , CK Ting . . Fitness inheritance assisted MOEA/D-CMAES for complex multi-objective optimization problems . . IEEE Congress on Evolutionary Computation , , 2018 . . p.1 - - 8 . . DOI: 10.1109/CEC.2018.8477898 http://doi.org/10.1109/CEC.2018.8477898 . .

XY Wen , , , WN Chen , , , Y Lin , , , 等 . . A maximal clique based multiobjective evolutionary algorithm for overlapping community detection . . IEEE Trans Evol Comput , , 2017 . . 21 ( ( 3 ): ): 363 - - 377 . . DOI: 10.1109/TEVC.2016.2605501 http://doi.org/10.1109/TEVC.2016.2605501 . .

SX Yang , , , MQ Li , , , XH Liu , , , 等 . . A grid-based evolutionary algorithm for many-objective optimization . . IEEE Trans Evol Comput , , 2013 . . 17 ( ( 5 ): ): 721 - - 736 . . DOI: 10.1109/TEVC.2012.2227145 http://doi.org/10.1109/TEVC.2012.2227145 . .

YJ Zeng , , , YG Sun . . Comparison of multiobjective particle swarm optimization and evolutionary algorithms for optimal reactive power dispatch problem . . IEEE Congress on Evolutionary Computation , , 2014 . . p.258 - - 265 . . DOI: 10.1109/CEC.2014.6900260 http://doi.org/10.1109/CEC.2014.6900260 . .

HP Zhang , , , Q Hui . . Many objective cooperative bat searching algorithm . . Appl Soft Comput , , 2019 . . 77 412 - - 437 . . DOI: 10.1016/j.asoc.2019.01.033 http://doi.org/10.1016/j.asoc.2019.01.033 . .

L Zhang , , , JY Zhang , , , T Li , , , 等 . . Multi-objective aerodynamic optimization design of high-speed train head shape . . J Zhejiang Univ-Sci A (Appl Phys & Eng) , , 2017 . . 18 ( ( 11 ): ): 841 - - 854 . . DOI: 10.1631/jzus.A1600764 http://doi.org/10.1631/jzus.A1600764 . .

QF Zhang , , , H Li . . MOEA/D: a multiobjective evolutionary algorithm based on decomposition . . IEEE Trans Evol Comput , , 2007 . . 11 ( ( 6 ): ): 712 - - 731 . . DOI: 10.1109/TEVC.2007.892759 http://doi.org/10.1109/TEVC.2007.892759 . .

QF Zhang , , , WD Liu , , , E Tsang , , , 等 . . Expensive multiobjective optimization by MOEA/D with Gaussian process model . . IEEE Trans Evol Comput , , 2010 . . 14 ( ( 3 ): ): 456 - - 474 . . DOI: 10.1109/TEVC.2009.2033671 http://doi.org/10.1109/TEVC.2009.2033671 . .

XY Zhang , , , Y Tian , , , YC Jin . . A knee point-driven evolutionary algorithm for many-objective optimization . . IEEE Trans Evol Comput , , 2015 . . 19 ( ( 6 ): ): 761 - - 776 . . DOI: 10.1109/TEVC.2014.2378512 http://doi.org/10.1109/TEVC.2014.2378512 . .

AM Zhou , , , YC Jin , , , QF Zhang , , , 等 . . Combining model- based and genetics-based offspring generation for multi- objective optimization using a convergence criterion . . IEEE Int Conf on Evolutionary Computation , , 2006 . . p.892 - - 899 . . DOI: 10.1109/CEC.2006.1688406 http://doi.org/10.1109/CEC.2006.1688406 . .

QL Zhu , , , QF Zhang , , , QZ Lin , , , 等 . . MOEA/D with two types of weight vectors for handling constraints . . IEEE Congress on Evolutionary Computation , , 2019 . . p.1359 - - 1365 . . DOI: 10.1109/CEC.2019.8790336 http://doi.org/10.1109/CEC.2019.8790336 . .

E Zitzler , , , S Künzli . . Indicator-based selection in multiobjective search . . Proc 8 th Int Conf on Parallel Problem Solving from Nature , , 2004 . . p.832 - - 842 . . DOI: 10.1007/978-3-540-30217-9_84 http://doi.org/10.1007/978-3-540-30217-9_84 . .

E Zitzler , , , M Laumanns , , , L Thiele , , , 等 . . SPEA2: improving the strength Pareto evolutionary algorithm. TIK-Report, Vol. 103. . . Eidgenössische Technische Hochschule Zürich (ETH), Institut für Technische Informatik und Kommunikationsnetze (TIK) , , 2001 . . DOI: 10.3929/ethz-a-004284029 http://doi.org/10.3929/ethz-a-004284029 . .

XF Zou , , , Y Chen , , , MZ Liu , , , 等 . . A new evolutionary algorithm for solving many-objective optimization problems . . IEEE Trans Syst Man Cybern , , 2008 . . 38 ( ( 5 ): ): 1402 - - 1412 . . DOI: 10.1109/TSMCB.2008.926329 http://doi.org/10.1109/TSMCB.2008.926329 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据