Evolutionary Multi/Many-Objective Optimisation via Bilevel Decomposition

Shouyong Jiang; Jinglei Guo; Yong Wang; Shengxiang Yang

doi:10.1109/JAS.2024.124515

Volume 11 Issue 9

Sep. 2024

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 15.3, Top 1 (SCI Q1)

CiteScore: 23.5, Top 2% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2024 > 11(9): 1973-1986

S. Jiang, J. Guo, Y. Wang, and S. Yang, “Evolutionary multi/many-objective optimisation via bilevel decomposition,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 9, pp. 1973–1986, Sept. 2024. doi: 10.1109/JAS.2024.124515

Citation:

S. Jiang, J. Guo, Y. Wang, and S. Yang, “Evolutionary multi/many-objective optimisation via bilevel decomposition,” IEEE/CAA J. Autom. Sinica, vol. 11, no. 9, pp. 1973–1986, Sept. 2024. doi: 10.1109/JAS.2024.124515

Citation:

PDF( 3028 KB)

Evolutionary Multi/Many-Objective Optimisation via Bilevel Decomposition

doi: 10.1109/JAS.2024.124515

Funds: This work was supported in part by the National Natural Science Foundation of China (62376288, U23A20347), the Engineering and Physical Sciences Research Council of UK (EP/X041239/1), and the Royal Society International Exchanges Scheme of UK (IEC/NSFC/211404)

More Information

Author Bio:
Shouyong Jiang (Member, IEEE) received the B.Sc. degree in information and computation science and the M.Sc. degree in control theory and control engineering from Northeastern University in 2011 and 2013, respectively, and the Ph.D. degree in computer science from De Montfort University UK in 2017. He is a Professor with the School of Automation, Central South University. His current research interests include computational intelligence, artificial intelligence and relevant interdisciplinary research

Jinglei Guo received the B.S. and M.S. degrees in computer science from Wuhan University of Technology in 1999 and 2002 respectively, the Ph.D. degree in computer science from Wuhan University in 2011. She is currently an Associate Professor with the School of Computer Science, Central China Normal University. Her research interest includes intelligent computing, large-scale global optimization, and parallel computing. She has published more than 20 international journal/conference papers. She serves as a Reviewer for more than ten international journals

Yong Wang (Senior Member, IEEE) received the Ph.D. degree in control science and engineering from the Central South University in 2011. He is a Professor with the School of Automation, Central South University. His current research interests include intelligent learning and optimization and their interdisciplinary applications.Dr. Wang was a recipient of Cheung Kong Young Scholar by the Ministry of Education, China in 2018, a Web of Science Highly Cited Researcher in computer science in 2017 and 2018, and a Elsevier’s Most Cited Chinese Researcher in 2021–2023. He is an Associate Editor of the IEEE Transactions on Evolutionary Computation and the Swarm and Evolutionary Computation

Shengxiang Yang (Senior Member, IEEE) received the Ph.D. degree in systems engineering from Northeastern University in 1999. He is currently a Professor of computational intelligence and the Deputy Director of the Institute of Artificial Intelligence, School of Computer Science and Informatics, De Montfort University, UK. His current research interests include evolutionary computation, swarm intelligence, artificial neural networks, data mining and data stream mining, and relevant real-world applications.Prof. Yang has over 440 publications with an H-index of 74 according to Google Scholar. He serves as an Associate Editor/Editorial Board Member for a number of international journals, such as the IEEE Transactions on Evolutionary Computation, IEEE Transactions on Cybernetics, Information Sciences, Enterprise Information Systems, and CAAI Transactions on Intelligence Technology
Corresponding author: Shouyong Jiang, e-mail: sjiang@csu.edu.cn; Yong Wang, e-mail: ywang@csu.edu.cn
¹ Supplementary Material of this paper can be found in link https://github.com/chang88ye/M2M-BL.
Received Date: 2024-01-29
Revised Date: 2024-03-26
Accepted Date: 2024-04-07

Available Online: 2024-07-04

Abstract

Abstract

Decomposition of a complex multi-objective optimisation problem (MOP) to multiple simple subMOPs, known as M2M for short, is an effective approach to multi-objective optimisation. However, M2M facilitates little communication/collaboration between subMOPs, which limits its use in complex optimisation scenarios. This paper extends the M2M framework to develop a unified algorithm for both multi-objective and many-objective optimisation. Through bilevel decomposition, an MOP is divided into multiple subMOPs at upper level, each of which is further divided into a number of single-objective subproblems at lower level. Neighbouring subMOPs are allowed to share some subproblems so that the knowledge gained from solving one subMOP can be transferred to another, and eventually to all the subMOPs. The bilevel decomposition is readily combined with some new mating selection and population update strategies, leading to a high-performance algorithm that competes effectively against a number of state-of-the-arts studied in this paper for both multi- and many-objective optimisation. Parameter analysis and component analysis have been also carried out to further justify the proposed algorithm.
- Bilevel decomposition,
- evolutionary algorithm,
- many-objective optimisation,
- multi-objective optimisation

FullText(HTML)

¹ Supplementary Material of this paper can be found in link https://github.com/chang88ye/M2M-BL.

References(51)

References

[1]	K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms. Chichester, UK: John Wiley and Sons, 2001.
[2]	S. Huband, L. Barone, L. While, and P. Hingston, “A scalable multi-objective test problem toolkit,” in Proc. Evolutionary Multi-Criterion Optimization, Guanajuato, Mexico, 2005, pp. 280–295.
[3]	K. Qiao, J. Liang, Z. Liu, K. Yu, C. Yue, and B. Qu, “Evolutionary multitasking with global and local auxiliary tasks for constrained multi-objective optimization,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 10, pp. 1951–1964, Oct. 2023. doi: 10.1109/JAS.2023.123336
[4]	W. Li, X. Yao, K. Li, R. Wang, T. Zhang, and L. Wang, “Coevolutionary framework for generalized multimodal multi-objective optimization,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 7, pp. 1544–1556, Jul. 2023. doi: 10.1109/JAS.2023.123609
[5]	Y. Tian, H. Chen, H. Ma, X. Zhang, K. Tan, and Y. Jin, “Integrating conjugate gradients into evolutionary algorithms for large-scale continuous multi-objective optimization,” IEEE/CAA J. Autom. Sinica, vol. 9, no. 10, pp. 1801–1817, Oct. 2022. doi: 10.1109/JAS.2022.105875
[6]	K. Deb, “Multi-objective optimisation using evolutionary algorithms: An introduction,” Indian Institute of Technology Kanpur, Kanpur, India, Tech. Rep. 2011003, 2011.
[7]	Q. Zhang and H. Li, “MOEA/D: A multiobjective evolutionary algorithm based on decomposition,” IEEE Trans. Evol. Comput., vol. 11, no. 6, pp. 712–731, Dec. 2007. doi: 10.1109/TEVC.2007.892759
[8]	T. Murata, H. Ishibuchi, and M. Gen, “Specification of genetic search directions in cellular multi-objective genetic algorithms,” in Proc. 1st Int. Conf. Evolutionary Multi-Criterion Optimization, Zurich, Switzerland, 2001, pp. 82–95.
[9]	E. Zitzler and S. Künzli, “Indicator-based selection in multiobjective search,” in Proc. 8th Int. Conf. Parallel Problem Solving from Nature, Birmingham, UK, 2004, pp. 832–842.
[10]	H. Sato, “Analysis of inverted PBI and comparison with other scalarizing functions in decomposition based MOEAs,” J. Heuristics, vol. 21, no. 6, pp. 819–849, Dec. 2015. doi: 10.1007/s10732-015-9301-6
[11]	S. Jiang, S. Yang, Y. Wang, and X. Liu, 2018. “Scalarizing functions in decomposition-based multiobjective evolutionary algorithms.” [Online]. Available: https://repository.essex.ac.uk/21656.
[12]	K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints,” IEEE Trans. Evol. Comput., vol. 18, no. 4, pp. 577–601, Aug. 2014. doi: 10.1109/TEVC.2013.2281535
[13]	S. Jiang and S. Yang, “A strength Pareto evolutionary algorithm based on reference direction for multiobjective and many-objective optimization,” IEEE Trans. Evol. Comput., vol. 21, no. 3, pp. 329–346, Jun. 2017. doi: 10.1109/TEVC.2016.2592479
[14]	H.-L. Liu, F. Gu, and Q. Zhang, “Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems,” IEEE Trans. Evol. Comput., vol. 18, no. 3, pp. 450–455, Jun. 2014. doi: 10.1109/TEVC.2013.2281533
[15]	H. Seada and K. Deb, “U-nsga-iii: a unified evolutionary optimization procedure for single, multiple, and many objectives: Proof-of-principle results,” in Proc. Int. Conf. Evolutionary Multi-Criterion Optimization, Guimaraes, Portugal, 2015, pp. 34–49. doi: 10.1109/TEVC.2015.2459718
[16]	L. Zhang, Q. Kang, Q. Deng, L. Xu, and Q. Wu, “A line complex-based evolutionary algorithm for many-objective optimization,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 5, pp. 1150–1167, May 2023. doi: 10.1109/JAS.2023.123495
[17]	L. Chen, H.-L. Liu, K. C. Tan, Y.-M. Cheung, and Y. Wang, “Evolutionary many-objective algorithm using decomposition-based dominance relationship,” IEEE Trans. Cybern., vol. 49, no. 12, pp. 4129–4139, Dec. 2019. doi: 10.1109/TCYB.2018.2859171
[18]	N. C. Sahoo, S. Ganguly, and D. Das, “Fuzzy-pareto-dominance driven possibilistic model based planning of electrical distribution systems using multi-objective particle swarm optimization,” Expert Systems with Applications, vol. 39, no. 1, pp. 881–893, 2012.
[19]	Z. Liu, Y. Wang, and P. Huang, “And: A many-objective evolutionary algorithm with angle-based selection and shift-based density estimation,” Information Sciences, vol. 509, pp. 400–419, 2020.
[20]	M. Asafuddoula, T. Ray, and R. Sarker, “A decomposition-based evolutionary algorithm for many objective optimization,” 2015. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/6857344.
[21]	R. Cheng, Y. Jin, M. Olhofer, and B. Sendhoff, “A reference vector guided evolutionary algorithm for many-objective optimization,” 2016. [Online]. Available: http://www.soft-computing.net/RVEA Checked.pdf.
[22]	S. Jiang and S. Yang, “An improved multiobjective optimization evolutionary algorithm based on decomposition for complex Pareto fronts,” IEEE Trans. Cybern., vol. 46, no. 2, pp. 421–437, Feb. 2016. doi: 10.1109/TCYB.2015.2403131
[23]	Y. Hua, Q. Liu, K. Hao, and Y. Jin, “A survey of evolutionary algorithms for multi-objective optimization problems with irregular Pareto fronts,” IEEE/CAA J. Autom. Sinica, vol. 8, no. 2, pp. 303–318, Feb. 2021. doi: 10.1109/JAS.2021.1003817
[24]	M. Elarbi, S. Bechikh, C. A. C. Coello, M. Makhlouf, and L. Ben Said, “Approximating complex Pareto fronts with predefined normal-boundary intersection directions,” IEEE Trans. Evol. Comput., vol. 24, no. 5, pp. 809–823, Oct. 2020. doi: 10.1109/TEVC.2019.2958921
[25]	X. Cai, Z. Mei, Z. Fun, and Q. Zhang, “A constrained decomposition approach with grids for evolutionary multiobjective optimization,” 2018. [Online]. Available: http://imagelab.stu.edu.cn/upload/files/2018101918193597.pdf.
[26]	M. Wu, K. Li, S. Kwong, Q. Zhang, and J. Zhang, “Learning to decompose: A paradigm for decomposition-based multiobjective optimization,” 2019. [Online]. Available: http://hdl.handle.net/10871/37967.
[27]	S. Yang, S. Jiang, and Y. Jiang, “Improving the multiobjective evolutionary algorithm based on decomposition with new penalty schemes,” Soft Comput., vol. 21, no. 16, pp. 4677–4691, Aug. 2017. doi: 10.1007/s00500-016-2076-3
[28]	M. Wu, K. Li, S. Kwong, Y. Zhou, and Q. Zhang, “Adaptive two-level matching-based selection for decomposition multi-objective optimization,” 2017. [Online]. Available: https://arxiv.org/pdf/1608.08607v1.
[29]	M. Li and X. Yao, “What weights work for you? Adapting weights for any Pareto front shape in decomposition-based evolutionary multiobjective optimisation,” Evol. Comput., vol. 28, no. 2, pp. 227–253, Jun. 2020. doi: 10.1162/evco_a_00269
[30]	M.-F. Leung and J. Wang, “A collaborative neurodynamic approach to multiobjective optimization,” IEEE Trans. Neural Netw. Learn. Syst., vol. 29, no. 11, pp. 5738–5748, Nov. 2018. doi: 10.1109/TNNLS.2018.2806481
[31]	J. Wang, Y. Su, Q. Lin, L. Ma, D. Gong, J. Li, and Z. Ming, “A survey of decomposition approaches in multiobjective evolutionary algorithms,” Neurocomputing, vol. 408, pp. 308–330, 2020.
[32]	Z. Wang, Q. Zhang, A. Zhou, M. Gong, and L. Jiao, “Adaptive replacement strategies for MOEA/D,” IEEE Trans. Cybern., vol. 46, no. 2, pp. 474–486, Feb. 2016. doi: 10.1109/TCYB.2015.2403849
[33]	H. Sato, “Chain-reaction solution update in MOEA/D and its effects on multi- and many-objective optimization,” Soft Comput., vol. 20, no. 10, pp. 3803–3820, Oct. 2016. doi: 10.1007/s00500-016-2092-3
[34]	Q. Zhang, W. Liu, and H. Li, “The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances,” in Proc. IEEE Congr. Evolutionary Computation, Trondheim, Norway, 2009, pp. 203–208.
[35]	M.-F. Leung and S.-C. Ng, “A hybrid algorithm based on MOEA/D and local search for multiobjective optimization,” in Proc. IEEE Congr. Evolutionary Computation, Glasgow, UK, 2020, pp. 1–8.
[36]	J. Shi, Q. Zhang, and J. Sun, “PPLS/D: Parallel Pareto local search based on decomposition,” IEEE Trans. Cybern., vol. 50, no. 3, pp. 1060–1071, Mar. 2020. doi: 10.1109/TCYB.2018.2880256
[37]	K. Li, K. Deb, Q. Zhang, and S. Kwong, “An evolutionary many-objective optimization algorithm based on dominance and decomposition,” IEEE Trans. Evol. Comput., vol. 19, no. 5, pp. 694–716, Oct. 2015. doi: 10.1109/TEVC.2014.2373386
[38]	Y. Sun, K. Xiao, S. Wang, and Q. Lv, “An evolutionary many-objective algorithm based on decomposition and hierarchical clustering selection,” Applied Intelligence, vol. 52, no. 8, pp. 8464–8509, 2022.
[39]	J. Zou, Z. Zhang, J. Zheng, and S. Yang, “A many-objective evolutionary algorithm based on dominance and decomposition with reference point adaptation,” Knowledge-Based Systems, vol. 231, pp. 107392, 2021.
[40]	X. Cai, H. Sun, Q. Zhang, and Y. Huang, “A grid weighted sum Pareto local search for combinatorial multi and many-objective optimization,” IEEE Trans. Cybern., vol. 49, no. 9, pp. 3586–3598, Sep. 2019. doi: 10.1109/TCYB.2018.2849403
[41]	H. Xu, W. Zeng, D. Zhang, and X. Zeng, “MOEA/HD: A multiobjective evolutionary algorithm based on hierarchical decomposition,” IEEE Trans. Cybern., vol. 49, no. 2, pp. 517–526, Feb. 2019. doi: 10.1109/TCYB.2017.2779450
[42]	F. Gu and H.-L. Liu, “A hierarchical decomposition-based evolutionary many-objective algorithm,” in Proc. 11th Int. Conf. Simulated Evolution and Learning, Shenzhen, China, 2017, pp. 211–223.
[43]	Y.-H. Zhang, Y.-J. Gong, T.-L. Gu, H.-Q. Yuan, W. Zhang, S. Kwong, and J. Zhang, “DECAL: Decomposition-based coevolutionary algorithm for many-objective optimization,” IEEE Trans. Cybern., vol. 49, no. 1, pp. 27–41, Jan. 2019. doi: 10.1109/TCYB.2017.2762701
[44]	H. Liu, L. Chen, Q. Zhang, and K. Deb, “Adaptively allocating search effort in challenging many-objective optimization problems,” 2018. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/7976380.
[45]	. Blank, K. Deb, Y. Dhebar, S. Bandaru, and H. Seada, “Generating well-spaced points on a unit simplex for evolutionary many-objective optimization,” Michigan State University, East Lansing, USA, Tech. Rep. 2020002, 2021.
[46]	H. Ishibuchi, “Research topics on evolutionary many-objective optimization,” 2016. [Online]. Available: https://titan.csit.rmit.edu.au/~e46507/ecml/talks/ishibuchi-presentation-nov-25-rmit.pdf.
[47]	L. R. C. de Farias and A. F. R. Araújo, “A decomposition-based many-objective evolutionary algorithm updating weights when required,” Swarm Evol. Comput., vol. 68, p. 100980, Feb. 2022. doi: 10.1016/j.swevo.2021.100980
[48]	L. Li, G. G. Yen, A. Sahoo, L. Chang, and T. Gu, “On the estimation of Pareto front and dimensional similarity in many-objective evolutionary algorithm,” Inf. Sci., vol. 563, pp. 375–400, Jul. 2021. doi: 10.1016/j.ins.2021.03.008
[49]	H. Chen, Y. Tian, W. Pedrycz, G. Wu, R. Wang, and L. Wang, “Hyperplane assisted evolutionary algorithm for many-objective optimization problems,” IEEE Trans. Cybern., vol. 50, no. 7, pp. 3367–3380, Jul. 2020. doi: 10.1109/TCYB.2019.2899225
[50]	J. Yuan, H.-L. Liu, F. Gu, Q. Zhang, and Z. He, “Investigating the properties of indicators and an evolutionary many-objective algorithm using promising regions,” IEEE Trans. Evol. Comput., vol. 25, no. 1, pp. 75–86, Feb. 2021. doi: 10.1109/TEVC.2020.2999100
[51]	Y. Tian, R. Cheng, X. Zhang, and Y. Jin, “PlatEMO: A MATLAB platform for evolutionary multi-objective optimization [educational forum],” IEEE Comput. Intell. Mag., vol. 12, no. 4, pp. 73–87, Nov. 2017. doi: 10.1109/MCI.2017.2742868

Supplements(0)

Cited By

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(14) / Tables(1)

Get Citation

PDF

XML

Article Metrics

Article views (146) PDF downloads(52)

Highlights

Bilevel decomposition of problems into upper-level leaders and lower-level followers
Active interaction between leaders and followers for fast information propagation
New mating selection to balance local exploitation and global exploration
New solution replacement to enhance the quality of replacement and usage of offspring

Evolutionary Multi/Many-Objective Optimisation via Bilevel Decomposition

doi: 10.1109/JAS.2024.124515

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Highlights

Export File

Citation

Format

Content