Abstract
Evaluating large-scale multi-objective problems is usually time-consuming due to the vast number of decision variables. However, most of the existing algorithms for large-scale multi-objective optimization require a significant number of problem evaluations to achieve satisfactory results, which makes the optimization process very inefficient. To address this issue, a fast interpolation-based multi-objective evolutionary algorithm is proposed in this paper for solving large-scale multi-objective optimization problems with high convergence speed and accuracy. In the proposed algorithm, decision variables are generated based on a small number of variables using an interpolation function. With this approach, only a small number of variables need to be optimized, so that the convergence speed can be greatly improved to make it possible to obtain satisfactory results with relatively low computation cost. The experimental results verified the superiority of our proposed algorithm over other state-of-the-art algorithms in terms of convergence speed and convergence accuracy on 108 test instances with up to 1000 decision variables.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability
All relevant data are within the paper.
References
Agarwal D, Singh P, Sayed MAE (2023) The Karush–Kuhn–Tucker (KKT) optimality conditions for fuzzy-valued fractional optimization problems. Math Comput Simul 205:861–877. https://doi.org/10.1016/j.matcom.2022.10.024
Antonio LM, Coello CAC (2013) Use of cooperative coevolution for solving large scale multiobjective optimization problems. In: Proceedings of IEEE congress evolutionary computation (CEC), Cancun, Mexico. pp 2758–2765. https://doi.org/10.1109/CEC.2013.6557903
Antonio LM, Coello CAC (2016) Indicator-based cooperative coevolution for multi-objective optimization. In: Proceedings of IEEE congress evolutionary computation (CEC), Vancouver, BC, Canada. pp 991–998 . https://doi.org/10.1109/CEC.2016.7743897
Antonio LM, Coello CAC, Morales MAR, Brambila SG, González JF, Tapia GC (2020) Coevolutionary operations for large scale multi-objective optimization. In: Proceedings of IEEE congress evolutionary computation (CEC). pp 1–8. https://doi.org/10.1109/CEC48606.2020.9185846
Bader J, Zitzler E (2011) HypE: an algorithm for fast hypervolume-based many-objective optimization. Evol Comput 19(1):45–76
Beume N, Naujoks B, Emmerich MTM (2007) SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur J Oper Res 181(3):1653–1669. https://doi.org/10.1016/j.ejor.2006.08.008
Bosman PAN, Thierens D (2003) The balance between proximity and diversity in multiobjective evolutionary algorithms. IEEE Trans Evol Comput 7(2):174–188
Cai X, Mei Z, Fan Z (2018) A decomposition-based many-objective evolutionary algorithm with two types of adjustments for direction vectors. IEEE Trans Cybern 48(8):2335–2348
Cheng R, ** Y, Olhofer M, sendhoff B (2017) Test problems for large-scale multiobjective and many-objective optimization. IEEE Trans Cybern 47(12):4108–4121. https://doi.org/10.1109/TCYB.2016.2600577
Corne D, Knowles JD, Oates MJ (2000) The pareto envelope-based selection algorithm for multi-objective optimisation. In: Proceedings of parallel problem solving from nature-PPSN VI, 6th international conference, vol 1917. Paris, pp 839–848
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. https://doi.org/10.1137/S1052623496307510
Deb K, Beyer H-G (2001) Self-adaptive genetic algorithms with simulated binary crossover. Evol Comput 9(2):197–221. https://doi.org/10.1162/106365601750190406
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
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197. https://doi.org/10.1109/4235.996017
El Sayed MA, Abo-Sinna MA (2021) A novel approach for fully intuitionistic fuzzy multi-objective fractional transportation problem. Alex Eng J 60(1):1447–1463. https://doi.org/10.1016/j.aej.2020.10.063
El Sayed MA, Baky IA, Singh P (2020) A modified topsis approach for solving stochastic fuzzy multi-level multi-objective fractional decision making problem. OPSEARCH 57(4):1374–1403. https://doi.org/10.1007/s12597-020-00461-w
Elarbi M, Bechikh S, Gupta A, Ben Said L, Ong Y (2018) A new decomposition-based NSGA-II for many-objective optimization. IEEE Trans Syst Man Cybern Syst 48(7):1191–1210
Elsisy MA, Elsaadany AS, Sayed MAE (2020) Using interval operations in the Hungarian method to solve the fuzzy assignment problem and its application in the rehabilitation problem of valuable buildings in egypt. Complex 2020(9207650):11. https://doi.org/10.1155/2020/9207650
Elsisy MA, El Sayed MA, Abo-Elnaga Y (2021) A novel algorithm for generating pareto frontier of bi-level multi-objective rough nonlinear programming problem. Ain Shams Eng J 12(2):2125–2133. https://doi.org/10.1016/j.asej.2020.11.006
Han F, Chen W, Ling Q-H, Han H (2021a) Multi-objective particle swarm optimization with adaptive strategies for feature selection. Swarm Evol Comput 62:100847. https://doi.org/10.1016/j.swevo.2021.100847
Han F, Zheng M, Ling Q (2021b) An improved multiobjective particle swarm optimization algorithm based on tripartite competition mechanism. Appl Intell 52:5784–5816. https://doi.org/10.1007/s10489-021-02665-z
He C, Li L, Tian Y, Zhang X, Cheng R, ** Y, Yao X (2019) Accelerating large-scale multiobjective optimization via problem reformulation. IEEE Trans Evol Comput 23(6):949–961. https://doi.org/10.1109/TEVC.2019.2896002
He C, Cheng R, Li L, Tan KC, ** Y (2022a) Large-scale multiobjective optimization via reformulated decision variable analysis. IEEE Trans Evol Comput. https://doi.org/10.1109/TEVC.2022.3213006
He C, Cheng R, Yazdani D (2022b) Adaptive offspring generation for evolutionary large-scale multiobjective optimization. IEEE Trans Syst Man Cybern Syst 52(2):786–798. https://doi.org/10.1109/TSMC.2020.3003926
Ishibuchi H, Murata T (1998) A multi-objective genetic local search algorithm and its application to flowshop scheduling. IEEE Trans Syst Man Cybern C Appl Rev 28(3):392–403
Jiang J, Han F, Wang J, Ling Q, Han H, Fan Z (2021) Improving decomposition-based multiobjective evolutionary algorithm with local reference point aided search. Inf Sci 576:557–576. https://doi.org/10.1016/j.ins.2021.06.068
Kadak U (2022) Multivariate fuzzy neural network interpolation operators and applications to image processing. Expert Syst Appl 206:117771. https://doi.org/10.1016/j.eswa.2022.117771
Kalyanmoy Deb, Goyal M (1996) A combined genetic adaptive search (GeneAS) for engineering design. Comput Sci Inform 26(1):30–45
Kim M, Hiroyasu T, Miki M, Watanabe S (2004) SPEA2+: improving the performance of the strength pareto evolutionary algorithm 2. In: Proceedings of parallel problem solving from nature-PPSN VIII, 8th international conference, vol 3242. Birmingham, pp 742–751
Lin Q, Li J, Du Z, Chen J, Ming Z (2015) A novel multi-objective particle swarm optimization with multiple search strategies. Eur J Oper Res 247(3):732–744. https://doi.org/10.1016/j.ejor.2015.06.071
Lin S-C, Chuang K, Chang C-W, Chen J-H (2021) Efficient interpolation method for wireless communications and signal processing applications. IEEE Trans Microw Theory Tech 69:2753–2761. https://doi.org/10.1109/TMTT.2021.3061563
Liu H, Gu F, Zhang Q (2014) Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems. IEEE Trans Evol Comput 18(3):450–455
Luo J, Huang X, Yang Y, Li X, Wang Z, Feng J (2020) A many-objective particle swarm optimizer based on indicator and direction vectors for many-objective optimization. Inf. Sci. 514:166–202. https://doi.org/10.1016/j.ins.2019.11.047
Ma X, Liu F, Qi Y, Wang X, Li L, Jiao L, Yin M, Gong M (2016) A multiobjective evolutionary algorithm based on decision variable analyses for multiobjective optimization problems with large-scale variables. IEEE Trans Evol Comput 20(2):275–298. https://doi.org/10.1109/TEVC.2015.2455812
Madani A, Engelbrecht AP, Ombuki-Berman BM (2023) Cooperative coevolutionary multi-guide particle swarm optimization algorithm for large-scale multi-objective optimization problems. Swarm Evol Comput 78:101262. https://doi.org/10.1016/j.swevo.2023.101262
Mahdavi S, Shiri ME, Rahnamayan S (2015) Metaheuristics in large-scale global continues optimization: a survey. Inf Sci 295:407–428
Miguel Antonio L, Coello Coello CA (2018) Coevolutionary multiobjective evolutionary algorithms: Survey of the state-of-the-art. IEEE Trans Evol Comput 22(6):851–865. https://doi.org/10.1109/TEVC.2017.2767023
Qin S, Sun C, ** Y, Tan Y, Fieldsend J (2021) Large-scale evolutionary multiobjective optimization assisted by directed sampling. IEEE Trans Evol Comput 25(4):724–738. https://doi.org/10.1109/TEVC.2021.3063606
Sayed MAE, Farahat FA, Elsisy MA (2022) A novel interactive approach for solving uncertain bi-level multi-objective supply chain model. Comput Ind Eng 169:108225. https://doi.org/10.1016/j.cie.2022.108225
Srinivas N, Deb K (1994) Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evol Comput 2(3):221–248
Tan KC, Yang YJ, Goh CK (2006) A distributed cooperative coevolutionary algorithm for multiobjective optimization. IEEE Trans Evol Comput 10(5):527–549. https://doi.org/10.1109/TEVC.2005.860762
Tian Y, Cheng R, Zhang X, ** Y (2017) PlatEMO: a MATLAB platform for evolutionary multi-objective optimization [Educational Forum]. IEEE Comput Intell Mag 12(4):73–87
Tian Y, Cheng R, Zhang X, Cheng F, ** Y (2018) An indicator-based multiobjective evolutionary algorithm with reference point adaptation for better versatility. IEEE Trans Evol Comput 22(4):609–622
Tian Y, Cheng R, Zhang X, Su Y, ** Y (2019) A strengthened dominance relation considering convergence and diversity for evolutionary many-objective optimization. IEEE Trans Evol Comput 23(2):331–345
Tian Y, Liu R, Zhang X, Ma H, Tan KC, ** Y (2020a) A multi-population evolutionary algorithm for solving large-scale multi-modal multi-objective optimization problems. IEEE Trans Evol Comput. https://doi.org/10.1109/TEVC.2020.3044711
Tian Y, Zheng X, Zhang X, ** Y (2020b) Efficient large-scale multiobjective optimization based on a competitive swarm optimizer. IEEE Trans Cybern 50(8):3696–3708. https://doi.org/10.1109/TCYB.2019.2906383
Wang H, Jiao L, Shang R, He S, Liu F (2015) A memetic optimization strategy based on dimension reduction in decision space. Evol Comput 23(1):69–100. https://doi.org/10.1162/EVCO_a_00122
Wen L, Zhang L, Bai J, Wang Y, Wei Z, Liu H (2022) Optimizing spatial interpolation method and sampling number for predicting cadmium distribution in the largest shallow lake of north china. Chemosphere 309:136789. https://doi.org/10.1016/j.chemosphere.2022.136789
Wu M, Li K, Kwong S, Zhang Q (2020) Evolutionary many-objective optimization based on adversarial decomposition. IEEE Trans Cybern 50(2):753–764
Yuan Y, Xu H, Wang B, Zhang B, Yao X (2016) Balancing convergence and diversity in decomposition-based many-objective optimizers. IEEE Trans Evol Comput 20(2):180–198
Zhang X, Tian Y, ** Y (2015a) A knee point-driven evolutionary algorithm for many-objective optimization. IEEE Trans Evol Comput 19(6):761–776
Zhang X, Tian Y, Cheng R, ** Y (2015b) An efficient approach to nondominated sorting for evolutionary multiobjective optimization. IEEE Trans Evol Comput 19(2):201–213. https://doi.org/10.1109/TEVC.2014.2308305
Zhang H, Zhou A, Song S, Zhang Q, Gao X, Zhang J (2016) A self-organizing multiobjective evolutionary algorithm. IEEE Trans Evol Comput 20(5):792–806. https://doi.org/10.1109/TEVC.2016.2521868
Zhang X, Tian Y, Cheng R, ** Y (2018a) A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization. IEEE Trans Evol Comput 22(1):97–112
Zhang X, Zheng X, Cheng R, Qiu J, ** Y (2018b) A competitive mechanism based multi-objective particle swarm optimizer with fast convergence. Inf Sci 427:63–76. https://doi.org/10.1016/j.ins.2017.10.037
Zhang C, Wu T, Xu S, Liu J (2023) Multiscale topology optimization for solid-lattice-void hybrid structures through an ordered multi-phase interpolation. Comput Aided Des 154:103424. https://doi.org/10.1016/j.cad.2022.103424
Zhou A, ** Y, Zhang Q, Sendhoff B, Tsang E (2006) Combining model-based and genetics-based offspring generation for multi-objective optimization using a convergence criterion. In: Proceedings of IEEE international conference evolutionary computation. pp 892–899 . https://doi.org/10.1109/CEC.2006.1688406
Zille H, Ishibuchi H, Mostaghim S, Nojima Y (2018) A framework for large-scale multiobjective optimization based on problem transformation. IEEE Trans Evol Comput 22(2):260–275. https://doi.org/10.1109/TEVC.2017.2704782
Funding
This work was supported by the National Natural Science Foundation of China (Nos. 61976108, 61572241, 62306013).
Author information
Authors and Affiliations
Contributions
All authors contributed to the study conception and design. Material preparation, data collection and analysis were performed by ZL, FH, QL, HH and JJ. The first draft of the manuscript was written by ZL and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.
Corresponding author
Ethics declarations
Conflict of interest
All authors declare that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Informed consent
Informed consent was obtained from all individual participants included in the study.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Liu, Z., Han, F., Ling, Q. et al. A fast interpolation-based multi-objective evolutionary algorithm for large-scale multi-objective optimization problems. Soft Comput 28, 6475–6499 (2024). https://doi.org/10.1007/s00500-023-09468-z
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-023-09468-z