Skip to main content
Top
Published in: Natural Computing 3/2021

24-11-2020

On the use of \((1,\lambda )\)-evolution strategy as efficient local search mechanism for discrete optimization: a behavioral analysis

Authors: Sara Tari, Matthieu Basseur, Adrien Goëffon

Published in: Natural Computing | Issue 3/2021

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A major issue while conceiving or parameterizing an optimization heuristic is to ensure an appropriate balance between exploitation and exploration of the search. Evolution strategies and neighborhood-based metaheuristics constitute relevant high-level frameworks, which ease the problem solving but are often complex to configure. Moreover, their effective behavior, according to the particularities of the search landscapes, remains difficult to grasp. In this paper, we deeply investigate the sampled walk search algorithm, which is a local search equivalent of the \((1,\lambda )\)-evolution strategy, considering that the neighborhood relation describes mutation possibilities. We specifically designed experiments to better understand the behavior of such a strategy offering a fine way to deal with the exploration versus exploitation dilemma. The main contribution is the analysis of search trajectories by evaluating and visualizing both their width (exploration) and their height (exploitation). More generally, we aim at bringing insights about the behavior of the \((1,\lambda )\)-ES in a discrete optimization context and within a fitness landscape perspective.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
go back to reference Amitrano C, Peliti L, Saber M (1989) Population dynamics in a spin-glass model of chemical evolution. J Mol Evol 29(6):513–525CrossRef Amitrano C, Peliti L, Saber M (1989) Population dynamics in a spin-glass model of chemical evolution. J Mol Evol 29(6):513–525CrossRef
go back to reference Back T, Hoffmeister F, Schwefel H-P (1991) A survey of evolution strategies. In: Proceedings of the fourth international conference on genetic algorithms, vol 2. Morgan Kaufmann Publishers San Mateo, CA Back T, Hoffmeister F, Schwefel H-P (1991) A survey of evolution strategies. In: Proceedings of the fourth international conference on genetic algorithms, vol 2. Morgan Kaufmann Publishers San Mateo, CA
go back to reference Basseur M, Goëffon A (2013) Hill-climbing strategies on various landscapes: an empirical comparison. In: Proceedings of the 15th annual conference on Genetic and evolutionary computation, pp 479–486 Basseur M, Goëffon A (2013) Hill-climbing strategies on various landscapes: an empirical comparison. In: Proceedings of the 15th annual conference on Genetic and evolutionary computation, pp 479–486
go back to reference Cai J, Thierauf G (1996) Evolution strategies for solving discrete optimization problems. Adv Eng Softw 25(2–3):177–183CrossRef Cai J, Thierauf G (1996) Evolution strategies for solving discrete optimization problems. Adv Eng Softw 25(2–3):177–183CrossRef
go back to reference Daolio F, Liefooghe A, Verel S, Aguirre H, Tanaka K (2017) Problem features versus algorithm performance on rugged multiobjective combinatorial fitness landscapes. Evolut Comput 25(4):555–585CrossRef Daolio F, Liefooghe A, Verel S, Aguirre H, Tanaka K (2017) Problem features versus algorithm performance on rugged multiobjective combinatorial fitness landscapes. Evolut Comput 25(4):555–585CrossRef
go back to reference Garey MR (1979) A guide to the theory of NP-completeness. Computers and intractability Garey MR (1979) A guide to the theory of NP-completeness. Computers and intractability
go back to reference Glover F, Laguna M (1998) Tabu search. In: Du DZ, Pardalos PM (eds) Handbook of combinatorial optimization. Springer, Berlin, pp 2093–2229CrossRef Glover F, Laguna M (1998) Tabu search. In: Du DZ, Pardalos PM (eds) Handbook of combinatorial optimization. Springer, Berlin, pp 2093–2229CrossRef
go back to reference Hansen N, Müller SD, Koumoutsakos P (2003) Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolut Comput 11(1):1–18CrossRef Hansen N, Müller SD, Koumoutsakos P (2003) Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolut Comput 11(1):1–18CrossRef
go back to reference Hoos HH, Stützle T (2004) Stochastic local search: foundations and applications. Elsevier, AmsterdamMATH Hoos HH, Stützle T (2004) Stochastic local search: foundations and applications. Elsevier, AmsterdamMATH
go back to reference Jones TC (1995) Evolutionary algorithms, fitness landscapes and search. PhD thesis, CiteseerD Jones TC (1995) Evolutionary algorithms, fitness landscapes and search. PhD thesis, CiteseerD
go back to reference Kauffman SA, Weinberger ED (1989) The NK model of rugged fitness landscapes and its application to maturation of the immune response. J Theor Biol 141(2):211–245CrossRef Kauffman SA, Weinberger ED (1989) The NK model of rugged fitness landscapes and its application to maturation of the immune response. J Theor Biol 141(2):211–245CrossRef
go back to reference Lissack MR (1999) Complexity: the science, its vocabulary, and its relation to organizations. Emergence 1(1):110–126CrossRef Lissack MR (1999) Complexity: the science, its vocabulary, and its relation to organizations. Emergence 1(1):110–126CrossRef
go back to reference Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristics. Springer, Berlin, pp 320–353CrossRef Lourenço HR, Martin OC, Stützle T (2003) Iterated local search. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristics. Springer, Berlin, pp 320–353CrossRef
go back to reference Malan KM, Engelbrecht AP (2013) A survey of techniques for characterising fitness landscapes and some possible ways forward. Inf Sci 241:148–163CrossRef Malan KM, Engelbrecht AP (2013) A survey of techniques for characterising fitness landscapes and some possible ways forward. Inf Sci 241:148–163CrossRef
go back to reference Merz P (2004) Advanced fitness landscape analysis and the performance of memetic algorithms. Evolut Comput 12(3):303–325CrossRef Merz P (2004) Advanced fitness landscape analysis and the performance of memetic algorithms. Evolut Comput 12(3):303–325CrossRef
go back to reference Neveu B, Trombettoni G, Glover F (2004) ID walk: a candidate list strategy with a simple diversification device. In: Wallace M (ed) International conference on principles and practice of constraint programming. Springer, Berlin, pp 423–437 Neveu B, Trombettoni G, Glover F (2004) ID walk: a candidate list strategy with a simple diversification device. In: Wallace M (ed) International conference on principles and practice of constraint programming. Springer, Berlin, pp 423–437
go back to reference Ochoa G, Malan KM, Blum C (2020) Search trajectory networks of population-based algorithms in continuous spaces. In: Castillo P, Jiménez LJ, FernándezdeVega F (eds) International conference on the applications of evolutionary computation. Springer, Berlin, pp 70–85CrossRef Ochoa G, Malan KM, Blum C (2020) Search trajectory networks of population-based algorithms in continuous spaces. In: Castillo P, Jiménez LJ, FernándezdeVega F (eds) International conference on the applications of evolutionary computation. Springer, Berlin, pp 70–85CrossRef
go back to reference Ochoa G, Tomassini M, Vérel S, Darabos C (2008) A study of NK landscapes’ basins and local optima networks. In: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pp 555–562 Ochoa G, Tomassini M, Vérel S, Darabos C (2008) A study of NK landscapes’ basins and local optima networks. In: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pp 555–562
go back to reference Palmer ME, Smith SJ (1992) Improved evolutionary optimization of difficult landscapes: control of premature convergence through scheduled sharing. Complex Syst 5(5):443–458 Palmer ME, Smith SJ (1992) Improved evolutionary optimization of difficult landscapes: control of premature convergence through scheduled sharing. Complex Syst 5(5):443–458
go back to reference Palubeckis G (2004) Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann Oper Res 131(1–4):259–282MathSciNetCrossRef Palubeckis G (2004) Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann Oper Res 131(1–4):259–282MathSciNetCrossRef
go back to reference Pitzer E, Affenzeller M (2012) A comprehensive survey on fitness landscape analysis. In: Fodor J, Klempous R, Suárez Araujo CP (eds) Recent advances in intelligent engineering systems, Springer, Berlin, pp 161–191CrossRef Pitzer E, Affenzeller M (2012) A comprehensive survey on fitness landscape analysis. In: Fodor J, Klempous R, Suárez Araujo CP (eds) Recent advances in intelligent engineering systems, Springer, Berlin, pp 161–191CrossRef
go back to reference Richter H (2014) Fitness landscapes: from evolutionary biology to evolutionary computation. In: Richter H, Engelbrecht A (eds) Recent advances in the theory and application of fitness landscapes. Springer, Berlin, pp 3–31CrossRef Richter H (2014) Fitness landscapes: from evolutionary biology to evolutionary computation. In: Richter H, Engelbrecht A (eds) Recent advances in the theory and application of fitness landscapes. Springer, Berlin, pp 3–31CrossRef
go back to reference Richter H, Engelbrecht A (2014) Recent advances in the theory and application of fitness landscapes. Springer, BerlinCrossRef Richter H, Engelbrecht A (2014) Recent advances in the theory and application of fitness landscapes. Springer, BerlinCrossRef
go back to reference Stadler PF (2002) Fitness landscapes. In: Lässig M, Valleriani A (eds) Biological evolution and statistical physics. Springer, Berlin, pp 183–204CrossRef Stadler PF (2002) Fitness landscapes. In: Lässig M, Valleriani A (eds) Biological evolution and statistical physics. Springer, Berlin, pp 183–204CrossRef
go back to reference Tari S, Basseur M, Goëffon A (2016) Toward the design of efficient pivoting rules for local search. In: Proceedings of the 2016 on genetic and evolutionary computation conference companion, pp 55–56 Tari S, Basseur M, Goëffon A (2016) Toward the design of efficient pivoting rules for local search. In: Proceedings of the 2016 on genetic and evolutionary computation conference companion, pp 55–56
go back to reference Tari S, Basseur M, Goëffon A (2017) Sampled walk and binary fitness landscapes exploration. In: Lutton E, Legrand P, Parrend P, Monmarché N, Schoenauer M (eds) International conference on artificial evolution. Springer, Berlin, pp 47–57 Tari S, Basseur M, Goëffon A (2017) Sampled walk and binary fitness landscapes exploration. In: Lutton E, Legrand P, Parrend P, Monmarché N, Schoenauer M (eds) International conference on artificial evolution. Springer, Berlin, pp 47–57
go back to reference Tari S, Basseur M, Goëffon A (2018) Worst improvement based iterated local search. In: Liefooghe A, López-Ibáñez M (eds) Evolutionary computation in combinatorial optimization. Springer, Berlin, pp 50–66CrossRef Tari S, Basseur M, Goëffon A (2018) Worst improvement based iterated local search. In: Liefooghe A, López-Ibáñez M (eds) Evolutionary computation in combinatorial optimization. Springer, Berlin, pp 50–66CrossRef
go back to reference Vassilev VK, Fogarty TC, Miller JF (2003) Smoothness, ruggedness and neutrality of fitness landscapes: from theory to application. In: Ghosh A, Tsutsui S (eds) Advances in evolutionary computing. Springer, Berlin, pp 3–44CrossRef Vassilev VK, Fogarty TC, Miller JF (2003) Smoothness, ruggedness and neutrality of fitness landscapes: from theory to application. In: Ghosh A, Tsutsui S (eds) Advances in evolutionary computing. Springer, Berlin, pp 3–44CrossRef
go back to reference Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evolut Comput 1(1):67–82CrossRef Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evolut Comput 1(1):67–82CrossRef
go back to reference Wright S (1932) The roles of mutation, inbreeding, crossbreeding, and selection in evolution Wright S (1932) The roles of mutation, inbreeding, crossbreeding, and selection in evolution
Metadata
Title
On the use of -evolution strategy as efficient local search mechanism for discrete optimization: a behavioral analysis
Authors
Sara Tari
Matthieu Basseur
Adrien Goëffon
Publication date
24-11-2020
Publisher
Springer Netherlands
Published in
Natural Computing / Issue 3/2021
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-020-09822-2

Other articles of this Issue 3/2021

Natural Computing 3/2021 Go to the issue

EditorialNotes

Preface

Premium Partner