Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

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

Login to get access
share
SHARE

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.

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 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

Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 15 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 15 Tage kostenlos.

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–525 CrossRef Amitrano C, Peliti L, Saber M (1989) Population dynamics in a spin-glass model of chemical evolution. J Mol Evol 29(6):513–525 CrossRef
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–183 CrossRef Cai J, Thierauf G (1996) Evolution strategies for solving discrete optimization problems. Adv Eng Softw 25(2–3):177–183 CrossRef
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–585 CrossRef 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–585 CrossRef
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–2229 CrossRef Glover F, Laguna M (1998) Tabu search. In: Du DZ, Pardalos PM (eds) Handbook of combinatorial optimization. Springer, Berlin, pp 2093–2229 CrossRef
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–18 CrossRef 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–18 CrossRef
go back to reference Hoos HH, Stützle T (2004) Stochastic local search: foundations and applications. Elsevier, Amsterdam MATH Hoos HH, Stützle T (2004) Stochastic local search: foundations and applications. Elsevier, Amsterdam MATH
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–245 CrossRef 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–245 CrossRef
go back to reference Lissack MR (1999) Complexity: the science, its vocabulary, and its relation to organizations. Emergence 1(1):110–126 CrossRef Lissack MR (1999) Complexity: the science, its vocabulary, and its relation to organizations. Emergence 1(1):110–126 CrossRef
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–353 CrossRef 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–353 CrossRef
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–163 CrossRef Malan KM, Engelbrecht AP (2013) A survey of techniques for characterising fitness landscapes and some possible ways forward. Inf Sci 241:148–163 CrossRef
go back to reference Merz P (2004) Advanced fitness landscape analysis and the performance of memetic algorithms. Evolut Comput 12(3):303–325 CrossRef Merz P (2004) Advanced fitness landscape analysis and the performance of memetic algorithms. Evolut Comput 12(3):303–325 CrossRef
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–85 CrossRef 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–85 CrossRef
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–282 MathSciNetCrossRef Palubeckis G (2004) Multistart tabu search strategies for the unconstrained binary quadratic optimization problem. Ann Oper Res 131(1–4):259–282 MathSciNetCrossRef
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–191 CrossRef 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–191 CrossRef
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–31 CrossRef 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–31 CrossRef
go back to reference Richter H, Engelbrecht A (2014) Recent advances in the theory and application of fitness landscapes. Springer, Berlin CrossRef Richter H, Engelbrecht A (2014) Recent advances in the theory and application of fitness landscapes. Springer, Berlin CrossRef
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–204 CrossRef Stadler PF (2002) Fitness landscapes. In: Lässig M, Valleriani A (eds) Biological evolution and statistical physics. Springer, Berlin, pp 183–204 CrossRef
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–66 CrossRef 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–66 CrossRef
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–44 CrossRef 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–44 CrossRef
go back to reference Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evolut Comput 1(1):67–82 CrossRef Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evolut Comput 1(1):67–82 CrossRef
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