Full Text:   <310>

Summary:  <39>

CLC number: TP391

On-line Access: 2020-08-07

Received: 2019-06-28

Revision Accepted: 2019-12-02

Crosschecked: 2020-07-21

Cited: 0

Clicked: 593

Citations:  Bibtex RefMan EndNote GB/T7714

 ORCID:

Ming-gang Dong

https://orcid.org/0000-0001-7078- 3942

Chao Jing

https://orcid.org/0000-0002-4695-8746

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2020 Vol.21 No.8 P.1171-1190

http://doi.org/10.1631/FITEE.1900321


A many-objective evolutionary algorithm based on decomposition with dynamic resource allocation for irregular optimization


Author(s):  Ming-gang Dong, Bao Liu, Chao Jing

Affiliation(s):  College of Information Science and Engineering, Guilin University of Technology, Guilin 541004, China; more

Corresponding email(s):   jingchao@glut.edu.cn

Key Words:  Many-objective optimization problems, Irregular Pareto front, External archive, Dynamic resource allocation, Shift-based density estimation, Tchebycheff approach


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.

@article{title="A many-objective evolutionary algorithm based on decomposition with dynamic resource allocation for irregular optimization",
author="Ming-gang Dong, Bao Liu, Chao Jing",
journal="Frontiers of Information Technology & Electronic Engineering",
volume="21",
number="8",
pages="1171-1190",
year="2020",
publisher="Zhejiang University Press & Springer",
doi="10.1631/FITEE.1900321"
}

%0 Journal Article
%T A many-objective evolutionary algorithm based on decomposition with dynamic resource allocation for irregular optimization
%A Ming-gang Dong
%A Bao Liu
%A Chao Jing
%J Frontiers of Information Technology & Electronic Engineering
%V 21
%N 8
%P 1171-1190
%@ 2095-9184
%D 2020
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1900321

TY - JOUR
T1 - A many-objective evolutionary algorithm based on decomposition with dynamic resource allocation for irregular optimization
A1 - Ming-gang Dong
A1 - Bao Liu
A1 - Chao Jing
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 21
IS - 8
SP - 1171
EP - 1190
%@ 2095-9184
Y1 - 2020
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1900321


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.

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

董明刚1,2,刘宝1,敬超1,2,3
1桂林理工大学信息科学与工程学院,中国桂林市,541004
2广西嵌入式技术与智能系统重点实验室,中国桂林市,541004
3广西可信软件重点实验室,桂林电子科技大学,中国桂林市,541004

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

关键词:高维多目标优化问题;不规则帕累托前沿;外部存档;动态资源分配;转化的密度评估方法;切比雪夫分解方法

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Asafuddoula M, Ray T, Sarker R, 2015. A decomposition- based evolutionary algorithm for many objective optimization. IEEE Trans Evol Comput, 19(3):445-460.

[2]Cai XY, Li YX, Fan Z, et al., 2015. An external archive guided multiobjective evolutionary algorithm based on decomposition for combinatorial optimization. IEEE Trans Evol Comput, 19(4):508-523.

[3]Cai XY, Yang ZX, Fan Z, et al., 2017. Decomposition-based- sorting and angle-based-selection for evolutionary multi- objective and many-objective optimization. IEEE Trans Cybern, 47(9):2824-2837.

[4]Cai XY, Mei ZW, Fan Z, et al., 2018. A constrained decomposition approach with grids for evolutionary multiobjective optimization. IEEE Trans Evol Comput, 22(4):564-577.

[5]Chand S, Wagner M, 2015. Evolutionary many-objective optimization: a quick-start guide. Surv Oper Res Manag Sci, 20(2):35-42.

[6]Cheng R, Jin YC, Olhofer M, et al., 2016. A reference vector guided evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput, 20(5):773-791.

[7]Cheng R, Li MQ, Tian Y, et al., 2018. Benchmark Functions for the CEC’2018 Competition on Many-Objective Optimization. University of Birmingham, United Kingdom.

[8]Coello CAC, 2006. Evolutionary multi-objective optimization: a historical view of the field. IEEE Comput Intell Mag, 1(1):28-36.

[9]Coello CAC, Lechuga MS, 2002. MOPSO: a proposal for multiple objective particle swarm optimization. Proc Congress on Evolutionary Computation, p.1051-1056.

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

[11]Das I, Dennis JE, 1998. Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM J Optim, 8(3): 631-657.

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

[13]Deb K, Jain H, 2014. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE Trans Evol Comput, 18(4):577-601.

[14]Deb K, Pratap A, Agarwal S, et al., 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput, 6(2):182-197.

[15]Deb K, Thiele L, Laumanns M, et al., 2005. Scalable test problems for evolutionary multiobjective optimization. In: Abraham A, Jain L, Goldberg R (Eds.), Evolutionary Multiobjective Optimization. Springer, London, p.105- 145.

[16]Elarbi M, Bechikh S, Gupta A, et al., 2018. A new decomposition-based NSGA-II for many-objective optimization. IEEE Trans Syst Man Cybern Syst, 48(7):1191- 1210.

[17]He C, Tian Y, Jin YC, et al., 2017. A radial space division based evolutionary algorithm for many-objective optimization. Appl Soft Comput, 61:603-621.

[18]He ZN, Yen GG, 2016. Many-objective evolutionary algorithm: objective space reduction and diversity improvement. IEEE Trans Evol Comput, 20(1):145-160.

[19]Huband S, Hingston P, Barone L, et al., 2006. A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans Evol Comput, 10(5):477-506.

[20]Jain H, Deb K, 2014. An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, part II: handling constraints and extending to an adaptive approach. IEEE Trans Evol Comput, 18(4):602-622.

[21]Kukkonen S, Lampinen J, 2005. GDE3: the third evolution step of generalized differential evolution. IEEE Congress on Evolutionary Computation, p.443-450.

[22]Li BD, Li JL, Tang K, et al., 2015. Many-objective evolutionary algorithms: a survey. ACM Comput Surv, 48(1):13.

[23]Li H, Zhang QF, 2009. Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Trans Evol Comput, 13(2):284-302.

[24]Li K, Deb K, Zhang QF, et al., 2015. An evolutionary many-objective optimization algorithm based on dominance and decomposition. IEEE Trans Evol Comput, 19(5):694-716.

[25]Li MQ, Yang SX, Liu XH, 2014. Shift-based density estimation for Pareto-based algorithms in many-objective optimization. IEEE Trans Evol Comput, 18(3):348-365.

[26]Li MQ, Yang SX, Liu XH, 2015. Bi-goal evolution for many-objective optimization problems. Artif Intell, 228:45-65.

[27]Liu YP, Gong DW, Sun XY, et al., 2017. Many-objective evolutionary optimization based on reference points. Appl Soft Comput, 50:344-355.

[28]Purshouse RC, Fleming PJ, 2007. On the evolutionary optimization of many conflicting objectives. IEEE Trans Evol Comput, 11(6):770-784.

[29]Qi YT, Ma XL, Liu F, et al., 2014. MOEA/D with adaptive weight adjustment. Evol Comput, 22(2):231-264.

[30]Ruan WY, Duan HB, 2020. Multi-UAV obstacle avoidance control via multi-objective social learning pigeon- inspired optimization. Front Inform Technol Electron Eng, 21(5):740-748.

[31]Santiago A, Huacuja HJF, Dorronsoro B, et al., 2014. 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. Springer, Cham, p.453-465.

[32]Seada H, Deb K, 2016. A unified evolutionary optimization procedure for single, multiple, and many objectives. IEEE Trans Evol Comput, 20(3):358-369.

[33]Seada H, Abouhawwash M, Deb K, 2019. Multiphase balance of diversity and convergence in multiobjective optimization. IEEE Trans Evol Comput, 23(3):503-513.

[34]Tian Y, Cheng R, Zhang XY, et al., 2017. PlatEMO: a MATLAB platform for evolutionary multi-objective optimization [Educational Forum]. IEEE Comput Intell Mag, 12(4):73-87.

[35]Tian Y, Cheng R, Zhang XY, et al., 2018. An indicator-based multiobjective evolutionary algorithm with reference point adaptation for better versatility. IEEE Trans Evol Comput, 22(4):609-622.

[36]Trivedi A, Srinivasan D, Sanyal K, et al., 2017. A survey of multiobjective evolutionary algorithms based on decomposition. IEEE Trans Evol Comput, 21(3):440-462.

[37]Wang GP, Jiang HW, 2007. Fuzzy-dominance and its application in evolutionary many objective optimization. Int Conf on Computational Intelligence and Security Workshops, p.195-198.

[38]Wang TC, Ting CK, 2018. Fitness inheritance assisted MOEA/D-CMAES for complex multi-objective optimization problems. IEEE Congress on Evolutionary Computation, p.1-8.

[39]Wen XY, Chen WN, Lin Y, et al., 2017. A maximal clique based multiobjective evolutionary algorithm for overlapping community detection. IEEE Trans Evol Comput, 21(3):363-377.

[40]Yang SX, Li MQ, Liu XH, et al., 2013. A grid-based evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput, 17(5):721-736.

[41]Zeng YJ, Sun YG, 2014. Comparison of multiobjective particle swarm optimization and evolutionary algorithms for optimal reactive power dispatch problem. IEEE Congress on Evolutionary Computation, p.258-265.

[42]Zhang HP, Hui Q, 2019. Many objective cooperative bat searching algorithm. Appl Soft Comput, 77:412-437.

[43]Zhang L, Zhang JY, Li T, et al., 2017. Multi-objective aerodynamic optimization design of high-speed train head shape. J Zhejiang Univ-Sci A (Appl Phys & Eng), 18(11):841-854.

[44]Zhang QF, Li H, 2007. MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput, 11(6):712-731.

[45]Zhang QF, Liu WD, Tsang E, et al., 2010. Expensive multiobjective optimization by MOEA/D with Gaussian process model. IEEE Trans Evol Comput, 14(3):456-474.

[46]Zhang XY, Tian Y, Jin YC, 2015. A knee point-driven evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput, 19(6):761-776.

[47]Zhou AM, Jin YC, Zhang QF, et al., 2006. Combining model- based and genetics-based offspring generation for multi- objective optimization using a convergence criterion. IEEE Int Conf on Evolutionary Computation, p.892-899.

[48]Zhu QL, Zhang QF, Lin QZ, et al., 2019. MOEA/D with two types of weight vectors for handling constraints. IEEE Congress on Evolutionary Computation, p.1359-1365.

[49]Zitzler E, Künzli S, 2004. Indicator-based selection in multiobjective search. Proc 8th Int Conf on Parallel Problem Solving from Nature, p.832-842.

[50]Zitzler E, Laumanns M, Thiele L, 2001. 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).

[51]Zou XF, Chen Y, Liu MZ, et al., 2008. A new evolutionary algorithm for solving many-objective optimization problems. IEEE Trans Syst Man Cybern, 38(5):1402-1412.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE