Gray-box local search with groups of step sizes | Soft Computing Skip to main content

Advertisement

Springer Nature Link
Log in

Gray-box local search with groups of step sizes

  • Optimization
  • Published:
Soft Computing Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Algorithm 1:
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Availability of data and material

The datasets analyzed during the current study are available in the git repository https://github.com/RodolfoALopes/continuous_optimization.

Code Availability

The source code used in this study is available in the git repository https://github.com/RodolfoALopes/continuous_optimization.

Notes

  1. github.com/RodolfoALopes/continuous_optimization.

  2. tacolab.org/bench.

References

  • Abbasi-khazaei T, Rezvani MH (2022) Energy-aware and carbon-efficient VM placement optimization in cloud datacenters using evolutionary computing methods. Soft Comput 26(18):9287–9322. https://doi.org/10.1007/s00500-022-07245-y

    Article  Google Scholar 

  • Ackley D (1987) A connectionist machine for genetic hillclimbing. The Kluwer international series in engineering and computer science vol SECS28. Kluwer Academic Publishers, Boston

    Google Scholar 

  • Bouter A, Alderliesten T, Bel A, Witteveen C, Bosman PAN (2018) Large-scale parallelization of partial evaluations in evolutionary algorithms for real-world problems. Proceedings of the genetic and evolutionary computation conference. Association for Computing Machinery, New York, pp 1199–1206

    Chapter  Google Scholar 

  • Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge University Press

    Book  MATH  Google Scholar 

  • Charris ES, Prins C, Santos AC (2015) Local search based metaheuristics for the robust vehicle routing problem with discrete scenarios. Appl Soft Comput 32:518–531. https://doi.org/10.1016/j.asoc.2015.03.058

    Article  Google Scholar 

  • Chicano F, Whitley D, Sutton AM (2014) Efficient identification of improving moves in a ball for pseudo-boolean problems. Proceedings of the 2014 annual conference on genetic and evolutionary computation. Association for Computing Machinery, New York, pp 437–444

    Chapter  Google Scholar 

  • Chicano F, Whitley D, Tinós R (2016a) Efficient hill climber for constrained pseudo-boolean optimization problems. Proceedings of the genetic and evolutionary computation conference. ACM, New York, pp 309–316

    Google Scholar 

  • Chicano F, Whitley D, Tinós R (2016b) Efficient hill climber for multi-objective pseudo-boolean optimization. In: Chicano F, Hu B, García-Sánchez P (eds) Evolutionary computation in combinatorial optimization. Springer International Publishing, Cham, pp 88–103

    Chapter  Google Scholar 

  • Chicano F, Whitley D, Ochoa G, Tinós R (2017) Optimizing one million variable NK landscapes by hybridizing deterministic recombination and local search. Proceedings of the genetic and evolutionary computation conference. Association for Computing Machinery, New York, pp 753–760

    Chapter  Google Scholar 

  • Chicano F, Ochoa G, Whitley D, Tinós R (2018) Enhancing partition crossover with articulation points analysis. Proceedings of the genetic and evolutionary computation conference. Association for Computing Machinery, New York, pp 269–276

    Chapter  Google Scholar 

  • Dutta P, Mahanand B (2022) Chapter 9: affordable energy-intensive routing using metaheuristics. In: Mishra S, Tripathy HK, Mallick PK, Sangaiah AK, Chae GS (eds) Cognitive big data intelligence with a metaheuristic approach, cognitive data science in sustainable computing. Academic Press, pp 193–210. https://doi.org/10.1016/B978-0-323-85117-6.00013-3

    Chapter  Google Scholar 

  • Gao Y, Culberson J (2003) On the treewidth of NK landscapes. Proceedings of the 2003 international conference on genetic and evolutionary computation: partI. Springer-Verlag, Berlin, pp 948–954

    MATH  Google Scholar 

  • Ghorbanian V, Mohammadi MH, Ibrahim I, Lowther D, Hendershot J (2019) An HPC-based data-driven process for design exploration and optimization of motor drives. IEEE international electric machines and drives conference (IEMDC). Institute of Electrical and Electronics Engineers, San Diego, pp 597–602

    Chapter  Google Scholar 

  • Gomes TM, de Freitas ARR, Lopes RA (2019) Multi-heap constraint handling in gray box evolutionary algorithms. Proceedings of the genetic and evolutionary computation conference. Association for Computing Machinery, New York, pp 829–836

    Chapter  Google Scholar 

  • Hadi AA, Mohamed AW, Jambi KM (2019) Lshade-spa memetic framework for solving large-scale optimization problems. Complex Intell Syst 5(1):25–40

    Article  Google Scholar 

  • Hu XM, He FL, Chen WN, Zhang J (2017) Cooperation coevolution with fast interdependency identification for large scale optimization. Inf Sci 381:142–160

    Article  Google Scholar 

  • Liang J, Meyerson E, Hodjat B, Fink D, Mutch K, Miikkulainen R (2019) Evolutionary neural automl for deep learning. Genetic and evolutionary computation conference. Association for Computing Machinery, New York, pp 401–409

    Chapter  Google Scholar 

  • 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

  • Lopes RA, Gomes TM, de Freitas ARR (2019) A symbolic evolutionary algorithm software platform. Proceedings of the genetic and evolutionary computation conference companion. Association for Computing Machinery, New York, pp 1366–1373

    Chapter  Google Scholar 

  • Lopes RA, Silva RCP, de Freitas ARR (2021a) An abstract interface for large-scale continuous optimization decomposition methods. Proceedings of the genetic and evolutionary computation conference companion. Association for Computing Machinery, New York, pp 1267–1274. https://doi.org/10.1145/3449726.3463188

    Chapter  Google Scholar 

  • Lopes R, Freitas A, Silva R (2021b) Local search with groups of step sizes. Oper Res Lett 49(3):385–392

    Article  MathSciNet  MATH  Google Scholar 

  • López ED, Puris A, Bello RR (2015) Vmode: a hybrid metaheuristic for the solution of large scale optimization problems. Investigación Oper 36(3):232–240

    MathSciNet  MATH  Google Scholar 

  • Mahdavi S, Shiri ME, Rahnamayan S (2015) Metaheuristics in large-scale global continues optimization: a survey. Inf Sci 295:407–428. https://doi.org/10.1016/j.ins.2014.10.042

    Article  MathSciNet  Google Scholar 

  • Mei Y, Omidvar MN, Li X, Yao X (2016) A competitive divide-and-conquer algorithm for unconstrained large-scale black-box optimization. ACM Trans Math Softw 42(2):1–24

    Article  MathSciNet  Google Scholar 

  • Molina D (2023) Taco: toolkit for automatic comparison of optimizers. https://tacolab.org/

  • Molina D, Herrera F (2015) Iterative hybridization of de with local search for the CEC’2015 special session on large scale global optimization. IEEE Congr Evolut Comput. https://doi.org/10.1109/CEC.2015.7257127

    Article  Google Scholar 

  • Molina D, LaTorre A, Herrera F (2018) Shade with iterative local search for large-scale global optimization. IEEE congress on evolutionary computation (CEC). Institute of Electrical and Electronics Engineers, Rio de Janeiro, pp 1–8

    Google Scholar 

  • Omidvar MN, Li X (2017) Evolutionary large-scale global optimization: An introduction. Proceedings of the genetic and evolutionary computation conference companion. Association for Computing Machinery, New York, pp 807–827. https://doi.org/10.1145/3067695.3067706

    Chapter  Google Scholar 

  • Omidvar MN, Li X, Mei Y, Yao X (2013) Cooperative co-evolution with differential grouping for large scale optimization. IEEE Trans Evolut Comput 18:378–393

    Article  Google Scholar 

  • Omidvar MN, Li X, Tang K (2015) Designing benchmark problems for large-scale continuous optimization. Inf Sci 316:419–436

    Article  Google Scholar 

  • Omidvar MN, Yang M, Mei Y, Li X, Yao X (2017) Dg2: a faster and more accurate differential grouping for large-scale black-box optimization. IEEE Trans Evol Comput 21(6):929–942. https://doi.org/10.1109/TEVC.2017.2694221

    Article  Google Scholar 

  • Powell MJD (1964) An efficient method for finding the minimum of a function of several variables without calculating derivatives. Comput J 7(2):155–162. https://doi.org/10.1093/comjnl/7.2.155

    Article  MathSciNet  MATH  Google Scholar 

  • Raja V, Kokkolaras M, Isaksson O (2019) A simulation-assisted complexity metric for design optimization of integrated architecture aero-engine structures. Struct Multidiscip Optim 60(1):287-300

    Article  Google Scholar 

  • Rao S (2009) Engineering optimization: theory and practice, 4th edn. John Wiley and Sons, New Jersey

    Book  Google Scholar 

  • Rao SS (2019) Engineering optimization: theory and practice. John Wiley and Sons

  • RStudio (2023) Wilcoxon test. https://www.rdocumentation.org/packages/rstatix/versions/0.7.0/topics/wilcox_test

  • 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. https://doi.org/10.1145/3205455.3205625

  • Sun Y, Omidvar MN, Kirley M, Li X (2018) Adaptive threshold parameter estimation with recursive differential grouping for problem decomposition. Proceedings of the genetic and evolutionary computation conference. Association for Computing Machinery, New York, pp 889–896

    Chapter  Google Scholar 

  • Sun Y, Li X, Ernst A, Omidvar MN (2019) Decomposition for large-scale optimization problems with overlapping components. IEEE congress on evolutionary computation (CEC). Institute of Electrical and Electronics Engineers, Rio de Janeiro, pp 326–333. https://doi.org/10.1109/CEC.2019.8790204

    Chapter  Google Scholar 

  • Tinós R, Whitley D, Chicano F (2015) Partition crossover for pseudo-boolean optimization. Proceedings of the 2015 ACM conference on foundations of genetic algorithms XIII. Association for Computing Machinery, New York, pp 137–149

    Chapter  Google Scholar 

  • Whitley D, Chen W (2012) 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. Association for Computing Machinery, New York, pp 1357–1364

    Google Scholar 

  • Whitley LD, Chicano F, Goldman BW (2016) Gray box optimization for MK landscapes NK landscapes and max-ksat. Evol Comput 24(3):491–519. https://doi.org/10.1162/EVCO_a_00184

    Article  Google Scholar 

  • Yang M, Omidvar MN, Li C, Li X, Cai Z, Kazimipour B, Yao X (2017) Efficient resource allocation in cooperative co-evolution for large-scale global optimization. IEEE Trans Evol Comput 21(4):493–505. https://doi.org/10.1109/TEVC.2016.2627581

    Article  Google Scholar 

Download references

Acknowledgements

This work has been supported by the Brazilian Agencies State of Minas Gerais Research Foundation - FAPEMIG (APQ-00040-14); Coordination for the Improvement of Higher Level Personnel - CAPES, Brazil; National Council of Scientific and Technological Development - CNPq, Brazil (402956/2016-8); and UFOP, Brazil.

Funding

Partial financial support was received from the State of Minas Gerais Research Foundation - FAPEMIG and National Council of Scientific and Technological Development - CNPq (Grant numbers APQ-00040-14 and 402956/2016-8).

Author information

Authors and Affiliations

  1. Federal University of Ouro Preto, Ouro Preto, MG, Brazil

    Rodolfo A. Lopes

  2. The C++ Alliance, Inc, Westlake Village, CA, 91362, USA

    Alan R. R. Freitas

Authors
  1. Rodolfo A. Lopes
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alan R. R. Freitas
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

RAL: Conceptualization, Methodology, Software, Formal analysis, Investigation, Writing-Original Draft; ARRF: Conceptualization, Methodology, Formal analysis, Investigation, Writing-Review and Editing, Supervision, Project administration, Funding acquisition.

Corresponding author

Correspondence to Rodolfo A. Lopes.

Ethics declarations

Conflict of interest

All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.

Ethical approval

Not applicable.

Consent to participate

Not applicable.

Consent for publication

Not applicable.

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lopes, R.A., Freitas, A.R.R. Gray-box local search with groups of step sizes. Soft Comput 27, 18709–18722 (2023). https://doi.org/10.1007/s00500-023-09129-1

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-023-09129-1

Keywords

Search

Navigation