A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
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
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

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
  • 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.

     

  • loading
  • 1 Supplementary Material of this paper can be found in link https://github.com/chang88ye/M2M-BL.
  • [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

Catalog

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

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

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(14)  / Tables(1)

    Article Metrics

    Article views (230) PDF downloads(65) Cited by()

    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

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return