Gray-box local search with groups of step sizes
Abstract
Local search methods play an important role in several approaches to solving complex optimization problems. However, black-box local search methods for continuous optimization problems tend to be excessively time-consuming and their performance typically deteriorates when dealing with large-scale problems. In this context, we propose the Gray-Box Local Search with Groups of Step Sizes (GBO-LSGSS) algorithm. GBO-LSGSS explores the problem structure through partial evaluations and subcomponents for improving its efficiency. Thus, this proposed method implements an orchestrator module to learn and select the most promissory subproblems. Overall, an experimental study revealed the competitive GBO-LSGSS performance even compared to some of the main algorithms for solving large-scale continuous problems. The comparison between GBO-LSGSS and its original version provides evidence that the proposed method can find better solutions and save up to 90% of processing time for fully and partially large-scale problems.
References
[1]
Abbasi-khazaei T and Rezvani MH Energy-aware and carbon-efficient VM placement optimization in cloud datacenters using evolutionary computing methods Soft Comput 2022 26 18 9287-9322
[2]
Ackley D A connectionist machine for genetic hillclimbing The Kluwer international series in engineering and computer science vol SECS28 1987 Boston Kluwer Academic Publishers
[3]
Bouter A, Alderliesten T, Bel A, Witteveen C, and Bosman PAN Large-scale parallelization of partial evaluations in evolutionary algorithms for real-world problems Proceedings of the genetic and evolutionary computation conference 2018 New York Association for Computing Machinery 1199-1206
[4]
Boyd S and Vandenberghe L Convex optimization 2004 Cambridge University Press
[5]
Charris ES, Prins C, and Santos AC Local search based metaheuristics for the robust vehicle routing problem with discrete scenarios Appl Soft Comput 2015 32 518-531
[6]
Chicano F, Whitley D, and Sutton AM Efficient identification of improving moves in a ball for pseudo-boolean problems Proceedings of the 2014 annual conference on genetic and evolutionary computation 2014 New York Association for Computing Machinery 437-444
[7]
Chicano F, Whitley D, and Tinós R Efficient hill climber for constrained pseudo-boolean optimization problems Proceedings of the genetic and evolutionary computation conference 2016 New York ACM 309-316
[8]
Chicano F, Whitley D, and Tinós R Chicano F, Hu B, and García-Sánchez P Efficient hill climber for multi-objective pseudo-boolean optimization Evolutionary computation in combinatorial optimization 2016 Cham Springer International Publishing 88-103
[9]
Chicano F, Whitley D, Ochoa G, and Tinós R Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search Proceedings of the genetic and evolutionary computation conference 2017 New York Association for Computing Machinery 753-760
[10]
Chicano F, Ochoa G, Whitley D, and Tinós R Enhancing partition crossover with articulation points analysis Proceedings of the genetic and evolutionary computation conference 2018 New York Association for Computing Machinery 269-276
[11]
Dutta P and Mahanand B Mishra S, Tripathy HK, Mallick PK, Sangaiah AK, and Chae GS Chapter 9: affordable energy-intensive routing using metaheuristics Cognitive big data intelligence with a metaheuristic approach, cognitive data science in sustainable computing 2022 Academic Press 193-210
[12]
Gao Y and Culberson J On the treewidth of NK landscapes Proceedings of the 2003 international conference on genetic and evolutionary computation: partI 2003 Berlin Springer-Verlag 948-954
[13]
Ghorbanian V, Mohammadi MH, Ibrahim I, Lowther D, and Hendershot J An HPC-based data-driven process for design exploration and optimization of motor drives IEEE international electric machines and drives conference (IEMDC) 2019 San Diego Institute of Electrical and Electronics Engineers 597-602
[14]
Gomes TM, de Freitas ARR, and Lopes RA Multi-heap constraint handling in gray box evolutionary algorithms Proceedings of the genetic and evolutionary computation conference 2019 New York Association for Computing Machinery 829-836
[15]
Hadi AA, Mohamed AW, and Jambi KM Lshade-spa memetic framework for solving large-scale optimization problems Complex Intell Syst 2019 5 1 25-40
[16]
Hu XM, He FL, Chen WN, and Zhang J Cooperation coevolution with fast interdependency identification for large scale optimization Inf Sci 2017 381 142-160
[17]
Liang J, Meyerson E, Hodjat B, Fink D, Mutch K, and Miikkulainen R Evolutionary neural automl for deep learning Genetic and evolutionary computation conference 2019 New York Association for Computing Machinery 401-409
[18]
Li X, Tang K, Omidvar MN, Yang Z, Qin K (2013) Benchmark functions for the CEC’2013 special session and competition on large-scale global optimization. Tech. rep
[19]
Lopes RA, Gomes TM, and de Freitas ARR A symbolic evolutionary algorithm software platform Proceedings of the genetic and evolutionary computation conference companion 2019 New York Association for Computing Machinery 1366-1373
[20]
Lopes RA, Silva RCP, and de Freitas ARR An abstract interface for large-scale continuous optimization decomposition methods Proceedings of the genetic and evolutionary computation conference companion 2021 New York Association for Computing Machinery 1267-1274
[21]
Lopes R, Freitas A, and Silva R Local search with groups of step sizes Oper Res Lett 2021 49 3 385-392
[22]
López ED, Puris A, and Bello RR Vmode: a hybrid metaheuristic for the solution of large scale optimization problems Investigación Oper 2015 36 3 232-240
[23]
Mahdavi S, Shiri ME, and Rahnamayan S Metaheuristics in large-scale global continues optimization: a survey Inf Sci 2015 295 407-428
[24]
Mei Y, Omidvar MN, Li X, and Yao X A competitive divide-and-conquer algorithm for unconstrained large-scale black-box optimization ACM Trans Math Softw 2016 42 2 1-24
[25]
Molina D (2023) Taco: toolkit for automatic comparison of optimizers. https://tacolab.org/
[26]
Molina D and Herrera F Iterative hybridization of de with local search for the CEC’2015 special session on large scale global optimization IEEE Congr Evolut Comput 2015
[27]
Molina D, LaTorre A, and Herrera F Shade with iterative local search for large-scale global optimization IEEE congress on evolutionary computation (CEC) 2018 Rio de Janeiro Institute of Electrical and Electronics Engineers 1-8
[28]
Omidvar MN and Li X Evolutionary large-scale global optimization: An introduction Proceedings of the genetic and evolutionary computation conference companion 2017 New York Association for Computing Machinery 807-827
[29]
Omidvar MN, Li X, Mei Y, and Yao X Cooperative co-evolution with differential grouping for large scale optimization IEEE Trans Evolut Comput 2013 18 378-393
[30]
Omidvar MN, Li X, and Tang K Designing benchmark problems for large-scale continuous optimization Inf Sci 2015 316 419-436
[31]
Omidvar MN, Yang M, Mei Y, Li X, and Yao X Dg2: a faster and more accurate differential grouping for large-scale black-box optimization IEEE Trans Evol Comput 2017 21 6 929-942
[32]
Powell MJD An efficient method for finding the minimum of a function of several variables without calculating derivatives Comput J 1964 7 2 155-162
[33]
Raja V, Kokkolaras M, and Isaksson O A simulation-assisted complexity metric for design optimization of integrated architecture aero-engine structures Struct Multidiscip Optim 2019 60 1 287-300
[34]
Rao S Engineering optimization: theory and practice 2009 4 New Jersey John Wiley and Sons
[35]
Rao SS (2019) Engineering optimization: theory and practice. John Wiley and Sons
[36]
RStudio (2023) Wilcoxon test. https://www.rdocumentation.org/packages/rstatix/versions/0.7.0/topics/wilcox_test
[37]
Sun Y, Kirley M, Li X (2018) Cooperative co-evolution with online optimizer selection for large-scale optimization. Proceedings of the genetic and evolutionary computation conference. Association for Computing Machinery, New York, pp 1079–1086.
[38]
Sun Y, Omidvar MN, Kirley M, and Li X Adaptive threshold parameter estimation with recursive differential grouping for problem decomposition Proceedings of the genetic and evolutionary computation conference 2018 New York Association for Computing Machinery 889-896
[39]
Sun Y, Li X, Ernst A, and Omidvar MN Decomposition for large-scale optimization problems with overlapping components IEEE congress on evolutionary computation (CEC) 2019 Rio de Janeiro Institute of Electrical and Electronics Engineers 326-333
[40]
Tinós R, Whitley D, and Chicano F Partition crossover for pseudo-boolean optimization Proceedings of the 2015 ACM conference on foundations of genetic algorithms XIII 2015 New York Association for Computing Machinery 137-149
[41]
Whitley D and Chen W Constant time steepest descent local search with lookahead for NK-landscapes and max-ksat Proceedings of the 14th annual conference on genetic and evolutionary computation 2012 New York Association for Computing Machinery 1357-1364
[42]
Whitley LD, Chicano F, and Goldman BW Gray box optimization for MK landscapes NK landscapes and max-ksat Evol Comput 2016 24 3 491-519
[43]
Yang M, Omidvar MN, Li C, Li X, Cai Z, Kazimipour B, and Yao X Efficient resource allocation in cooperative co-evolution for large-scale global optimization IEEE Trans Evol Comput 2017 21 4 493-505
Index Terms
- Gray-box local search with groups of step sizes
Index terms have been assigned to the content through auto-classification.
Recommendations
Superior solution guided particle swarm optimization combined with local search techniques
Particle swarm optimization (PSO) is an evolutionary algorithm known for its simplicity and effectiveness in solving various optimization problems. PSO should have strong yet balanced exploration and exploitation capabilities to enhance its performance. ...
A novel local search method for LSGO with golden ratio and dynamic search step
AbstractDepending on the developing technology, large-scale problems have emerged in many areas such as business, science, and engineering. Therefore, large-scale optimization problems and solution techniques have become an important research field. One ...
Memetic Algorithm with Local Search Chaining for Continuous Optimization Problems: A Scalability Test
ISDA '09: Proceedings of the 2009 Ninth International Conference on Intelligent Systems Design and ApplicationsMemetic algorithms arise as very effective algorithms to obtain reliable and high accurate solutions for complex continuous optimization problems. Nowadays, higher dimensional optimization problems are an interesting field of research, that introduces ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2023. 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.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 13 September 2023
Accepted: 18 August 2023
Author Tags
Qualifiers
- Research-article
Funding Sources
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 09 Jan 2025