Multi-objective Random Bit Climbers with Weighted Permutation on Large Scale Binary MNK-Landscapes
Pages 169 - 185
Abstract
Multi-Objective Evolutionary Algorithms have proven to be very effective when solving Multi-Objective Optimization Problems. However, their performance decreases significantly when solving large scale problems, which can have hundreds or thousands of variables. Although several algorithms have been proposed to tackle this problem in the recent years, most of them are designed for continuous problems, and only a few focus on binary ones. In this paper, we propose a modification to multi-objective random one-bit climbers that achieves better performance in large scale binary problems by learning the trend of the values of the decision variables from previously found solutions and applying that information to decide which ones to focus on when executing the bit climb. We present the implemented algorithm, compare its performance to other well known evolutionary algorithms and study some of its properties.
References
[1]
Aguirre, H., Oyama, A., Tanaka, K.: Adaptive -sampling and -hood for evolutionary many-objective optimization. In: Purshouse, R.C., Fleming, P.J., Fonseca, C.M., Greco, S., Shaw, J. (eds.) EMO 2013. LNCS, vol. 7811, pp. 322–336. Springer, Heidelberg (2013).
[2]
Aguirre, H., Tanaka, K.: Insights on properties of multiobjective mnk-landscapes. In: Proceedings of the 2004 Congress on Evolutionary Computation, vol. 1, pp. 196–203 (2004).
[3]
Aguirre, H., Tanaka, K.: Random bit climbers on multiobjective mnk-landscapes: Effects of memory and population climbing. IEICE Trans. 88-A, 334–345 (2005).
[4]
Aguirre H and Tanaka K Working principles, behavior, and performance of moeas on mnk-landscapes Eur. J. Oper. Res. 2007 181 3 1670-1690
[5]
Aguirre H, Zapotecas S, Liefooghe A, Verel S, and Tanaka K Bonnevay S, Legrand P, Monmarché N, Lutton E, and Schoenauer M Approaches for many-objective optimization: analysis and comparison on mnk-landscapes Artificial Evolution 2016 Cham Springer 14-28
[6]
Antonio, L., Coello, C.: Use of cooperative coevolution for solving large scale multiobjective optimization problems. In: IEEE Congress on Evolutionary Computation, pp. 2758–2765. IEEE (2013).
[7]
Beume N, Naujoks B, and Emmerich M Sms-emoa: multiobjective selection based on dominated hypervolume Eur. J. Oper. Res. 2007 181 3 1653-1669
[8]
Brewer, K., Carraway, L., Ingram, D.: Forward selection as a candidate for constructing nonregular robust parameter designs. Arkansas State University, Tech. rep. (2010)
[9]
Brockhoff D, Wagner T, and Trautmann H R2 indicator-based multiobjective search Evol. Comput. 2015 23 3 369-395
[10]
Coello, C., Van Veldhuizen, D., Lamont, G.: Evolutionary Algorithms for Solving Multi-Objective Problems. Genetic Algorithms and Evolutionary Computation, Springer, US, USA (2013)
[11]
Deb, K.: Multi-Objective Optimization Using Evolutionary Algorithms. Wiley Interscience Series in Systems and Optimization, Wiley
[12]
Deb K, Pratap A, Agarwal S, and Meyarivan T A fast and elitist multiobjective genetic algorithm: Nsga-ii IEEE Trans. Evol. Comput. 2002 6 2 182-197
[13]
Hadka D and Reed P Borg: an auto-adaptive many-objective evolutionary computing framework Evol. Comput. 2013 21 2 231-259
[14]
He C, Cheng R, and Yazdani D Adaptive offspring generation for evolutionary large-scale multiobjective optimization IEEE Trans. Systems Man Cybernet. Syst. 2022 52 2 786-798
[15]
Hong W, Yang P, and Tang K Evolutionary computation for large-scale multi-objective optimization: A decade of progresses Int. J. Autom. Comput. 2021 18 155-169
[16]
Jain H and Deb K 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. 2014 18 4 602-622
[17]
Kauffman, S.: The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, England (1993)
[18]
Laumanns M, Thiele L, Deb K, and Zitzler E Combining convergence and diversity in evolutionary multiobjective optimization Evol. Comput. 2002 10 3 263-282
[19]
Mahdavi S, Shiri ME, and Rahnamayan S Metaheuristics in large-scale global continues optimization: a survey Inf. Sci. 2015 295 407-428
[20]
Pelikan, M.: Nk landscapes, problem difficulty, and hybrid evolutionary algorithms. In: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, pp. 665-672. Association for Computing Machinery, New York (2010).
[21]
Tian Y, Wang C, Zhang X, and Jin Y An evolutionary algorithm for large-scale sparse multi-objective optimization problems IEEE Trans. Evol. Comput. 2019 24 2 380-393
[22]
Tian Y, Lu C, Zhang X, Tan KC, and Jin Y Solving large-scale multiobjective optimization problems with sparse optimal solutions via unsupervised neural networks IEEE Trans. Cybernet. 2021 51 6 3115-3128
[23]
Tian Y, Si L, Zhang X, Cheng R, He C, Tan KC, and Jin Y Evolutionary large-scale multi-objective optimization: a survey ACM Comput. Surv. 2021 54 8 1-34
[24]
Verel S, Liefooghe A, Jourdan L, and Dhaenens C On the structure of multiobjective combinatorial search space: Mnk-landscapes with correlated objectives Eur. J. Oper. Res. 2013 227 2 331-342
[25]
Von Lücken C, Brizuela C, and Baran B An overview on evolutionary algorithms for many-objective optimization problems Wiley Interdisc. Rev. Data Mining Knowl. Dis. 2018 9 1
[26]
Zapotecas-Martínez, S., Aguirre, H.E., Tanaka, K., Coello, C.A.C.: On the low-discrepancy sequences and their use in moea/d for high-dimensional objective spaces. In: IEEE Congress on Evolutionary Computation, pp. 2835–2842. IEEE (2015).
[27]
Zapotecas-Martínez S, Coello CAC, Aguirre HE, and Tanaka K Challenging test problems for multi- and many-objective optimization Swarm Evol. Comput. 2023 81
[28]
Zhang Q and Li H Moea/d: a multiobjective evolutionary algorithm based on decomposition IEEE Trans. Evol. Comput. 2007 11 6 712-731
[29]
Zhang X, Tian Y, Cheng R, and Jin Y A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization IEEE Trans. Evol. Comput. 2018 22 1 97-112
[30]
Zille, H., Ishibuchi, H., Mostaghim, S., Nojima, Y.: Weighted optimization framework for large-scale multi-objective optimization. In: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion, pp. 83-84. Association for Computing Machinery, New York (2016).
[31]
Zitzler E, Künzli S, et al. Yao X et al. Indicator-based selection in multiobjective search Parallel Problem Solving from Nature - PPSN VIII 2004 Heidelberg Springer 832-842
[32]
Zitzler, E.: Evolutionary algorithms for multiobjective optimization: methods and applications. Springer, US, USA (1999)
Index Terms
- Multi-objective Random Bit Climbers with Weighted Permutation on Large Scale Binary MNK-Landscapes
Index terms have been assigned to the content through auto-classification.
Recommendations
Simple Distributed Bit Climber for Many-objective Optimization of Binary Epistatic Problems
GECCO '24 Companion: Proceedings of the Genetic and Evolutionary Computation Conference CompanionWe study a distributed bit climbing algorithm for many-objective optimization of binary epistatic problems. This algorithm decomposes the many-objective problem into a minimum number of single-objective problems, specified by the original evaluation ...
A hybrid method for solving multi-objective global optimization problems
AbstractReal optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a ...
Multi-objective modified differential evolution algorithm with archive-base mutation for solving multi-objective $$p$$p-xylene oxidation process
Maximizing the diversity of the obtained objective vectors and increasing the convergence speed to the true Pareto front are two important issues in the design of multi-objective evolutionary algorithms (MOEAs). To solve complex multi-objective ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sep 2024
462 pages
ISBN:978-3-031-70084-2
DOI:10.1007/978-3-031-70085-9
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 14 September 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Feb 2025