Skip to main content
Top
Published in: Soft Computing 2/2021

23-07-2020 | Methodologies and Application

Upper confidence tree for planning restart strategies in multi-modal optimization

Authors: Amaury Dubois, Julien Dehos, Fabien Teytaud

Published in: Soft Computing | Issue 2/2021

Log in

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

search-config
loading …

Abstract

In the context of gradient-free multi-modal optimization, numerous algorithms are based on restarting evolution strategies. Such an algorithm classically performs many local searches, for finding all the global optima of the objective function. The strategy used to select the restarting points (i.e., the initial points of the local searches) is a crucial step of the method. In previous works, a strategy based on reinforcement learning has been proposed: the search space is partitioned and a multi-armed bandit algorithm is used to select an interesting region to sample. This strategy significantly improves the main optimization algorithm but is limited to small dimensional problems. In this paper, we propose an algorithm tackling this problem. The main contributions are (1) a tree-based scheme for hierarchically partition the search space and (2) a multi-armed bandit strategy for traversing this tree. Thus, a node in the tree corresponds to a region of the search space, and its children partition this region according to one dimension. The multi-armed bandit strategy is used to traverse the tree by selecting interesting children recursively. We have experimented our algorithm on difficult multi-modal functions, with small and large dimensions. For small dimensions, we observe performances comparable to previous state-of-the-art algorithms. For large dimensions, we observe better results as well as lower memory consumption.

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 "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!

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!

Literature
go back to reference Ahrari A, Deb K, Preuss M (2017) Multimodal optimization by covariance matrix self-adaptation evolution strategy with repelling subpopulations. Evol Comput 25(3):439–471CrossRef Ahrari A, Deb K, Preuss M (2017) Multimodal optimization by covariance matrix self-adaptation evolution strategy with repelling subpopulations. Evol Comput 25(3):439–471CrossRef
go back to reference Auer P, Cesa-Bianchi N, Fischer P (2002a) Finite-time analysis of the multiarmed bandit problem. Mach Learn 47(2–3):235–256CrossRef Auer P, Cesa-Bianchi N, Fischer P (2002a) Finite-time analysis of the multiarmed bandit problem. Mach Learn 47(2–3):235–256CrossRef
go back to reference Auer P, Cesa-Bianchi N, Fischer P (2002b) Finite-time analysis of the multiarmed bandit problem. Mach Learn 47(2–3):235–256CrossRef Auer P, Cesa-Bianchi N, Fischer P (2002b) Finite-time analysis of the multiarmed bandit problem. Mach Learn 47(2–3):235–256CrossRef
go back to reference Auger A, Hansen N (2005) A restart CMA evolution strategy with increasing population size. In: 2005 IEEE congress on evolutionary computation, vol 2. pp 1769–1776 Auger A, Hansen N (2005) A restart CMA evolution strategy with increasing population size. In: 2005 IEEE congress on evolutionary computation, vol 2. pp 1769–1776
go back to reference Bubeck S, Munos R, Stoltz G, Szepesvári C (2011) X-armed bandits. J Mach Learn Res 12(May):1655–1695MathSciNetMATH Bubeck S, Munos R, Stoltz G, Szepesvári C (2011) X-armed bandits. J Mach Learn Res 12(May):1655–1695MathSciNetMATH
go back to reference De Jong KA (1975) An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan De Jong KA (1975) An analysis of the behavior of a class of genetic adaptive systems. PhD thesis, University of Michigan
go back to reference Deng W, Zhao H, Yang X, Xiong J, Sun M, Li B (2017) Study on an improved adaptive pso algorithm for solving multi-objective gate assignment. Appl Soft Comput 59:288–302CrossRef Deng W, Zhao H, Yang X, Xiong J, Sun M, Li B (2017) Study on an improved adaptive pso algorithm for solving multi-objective gate assignment. Appl Soft Comput 59:288–302CrossRef
go back to reference Deng W, Xu J, Song Y, Zhao H (2019a) An effective improved co-evolution ant colony optimization algorithm with multi-strategies and its application. Int J Bio-Inspired Comput Deng W, Xu J, Song Y, Zhao H (2019a) An effective improved co-evolution ant colony optimization algorithm with multi-strategies and its application. Int J Bio-Inspired Comput
go back to reference Deng W, Xu J, Zhao H (2019b) An improved ant colony optimization algorithm based on hybrid strategies for scheduling problem. IEEE Access 7:20281–20292CrossRef Deng W, Xu J, Zhao H (2019b) An improved ant colony optimization algorithm based on hybrid strategies for scheduling problem. IEEE Access 7:20281–20292CrossRef
go back to reference Dubois A, Dehos J, Teytaud F (2018) Improving multi-modal optimization restart strategy through multi-armed bandit. In: IEEE ICMLA 2018: 17th IEEE international conference on machine learning and applications Dubois A, Dehos J, Teytaud F (2018) Improving multi-modal optimization restart strategy through multi-armed bandit. In: IEEE ICMLA 2018: 17th IEEE international conference on machine learning and applications
go back to reference Gelly S, Silver D (2007) Combining online and offline knowledge in UCT. In: International conference of machine learning Gelly S, Silver D (2007) Combining online and offline knowledge in UCT. In: International conference of machine learning
go back to reference Goldberg DE, Richardson J et al (1987) Genetic algorithms with sharing for multimodal function optimization. In: Genetic algorithms and their applications: proceedings of the second international conference on genetic algorithms. pp 41–49 Goldberg DE, Richardson J et al (1987) Genetic algorithms with sharing for multimodal function optimization. In: Genetic algorithms and their applications: proceedings of the second international conference on genetic algorithms. pp 41–49
go back to reference Kadioglu S, Sellmann M, Wagner M (2017) Learning a reactive restart strategy to improve stochastic search. In: International conference on learning and intelligent optimization. pp 109–123 Kadioglu S, Sellmann M, Wagner M (2017) Learning a reactive restart strategy to improve stochastic search. In: International conference on learning and intelligent optimization. pp 109–123
go back to reference Kocsis L, Szepesvári C (2006) Bandit based Monte-Carlo planning. In: European conference on machine learning. pp 282–293 Kocsis L, Szepesvári C (2006) Bandit based Monte-Carlo planning. In: European conference on machine learning. pp 282–293
go back to reference Lacroix B, Christie LA, Mcall JA (2017) Interpolated continuous optimisation problems with tunable landscape features. In: Proceedings of GECCO ’17 companion Lacroix B, Christie LA, Mcall JA (2017) Interpolated continuous optimisation problems with tunable landscape features. In: Proceedings of GECCO ’17 companion
go back to reference Li X (2016) Multimodal optimization using niching methods. American Cancer Society, New York, pp 1–8 Li X (2016) Multimodal optimization using niching methods. American Cancer Society, New York, pp 1–8
go back to reference Mahfoud SW (1995) Niching methods for genetic algorithms. Urbana 51:62–94 Mahfoud SW (1995) Niching methods for genetic algorithms. Urbana 51:62–94
go back to reference Mason K, Duggan J, Howley E (2018) Maze navigation using neural networks evolved with novelty search and differential evolution. In: Adaptive and learning agents workshop (at ICML-AAMAS 2018) Mason K, Duggan J, Howley E (2018) Maze navigation using neural networks evolved with novelty search and differential evolution. In: Adaptive and learning agents workshop (at ICML-AAMAS 2018)
go back to reference Mengshoel OJ, Goldberg DE et al (1999) Probabilistic crowding: deterministic crowding with probabilistic replacement. In: Proceedings of the genetic and evolutionary computation conference, vol 1. Morgan Kauffman, pp 409–416 Mengshoel OJ, Goldberg DE et al (1999) Probabilistic crowding: deterministic crowding with probabilistic replacement. In: Proceedings of the genetic and evolutionary computation conference, vol 1. Morgan Kauffman, pp 409–416
go back to reference Petrowski A (1996) A clearing procedure as a Niching method for genetic algorithms. In: Proceedings of IEEE international conference on evolutionary computation. pp 798–803 Petrowski A (1996) A clearing procedure as a Niching method for genetic algorithms. In: Proceedings of IEEE international conference on evolutionary computation. pp 798–803
go back to reference Preuss M (2015) Multimodal optimization by means of evolutionary algorithms, 1st edn. Springer, BerlinCrossRef Preuss M (2015) Multimodal optimization by means of evolutionary algorithms, 1st edn. Springer, BerlinCrossRef
go back to reference Preux P, Munos R, Valko M (2014) Bandits attack function optimization. In: IEEE congress on evolutionary computation Preux P, Munos R, Valko M (2014) Bandits attack function optimization. In: IEEE congress on evolutionary computation
go back to reference Rechenberg I (1973) Evolutionsstrategie: optimierung technischer Systeme nach Prinzipien der biologischen evolution. Number 15 in Problemata. Frommann-Holzboog Rechenberg I (1973) Evolutionsstrategie: optimierung technischer Systeme nach Prinzipien der biologischen evolution. Number 15 in Problemata. Frommann-Holzboog
go back to reference Schoenauer M, Teytaud F, Teytaud O (2011) A rigorous runtime analysis for quasi-random restarts and decreasing stepsize. In: Artificial evolution. Angers, France Schoenauer M, Teytaud F, Teytaud O (2011) A rigorous runtime analysis for quasi-random restarts and decreasing stepsize. In: Artificial evolution. Angers, France
go back to reference Silver D (2009) Reinforcement learning and simulation-based search. PhD thesis, University of Alberta Silver D (2009) Reinforcement learning and simulation-based search. PhD thesis, University of Alberta
go back to reference Singh G, Deb DR K (2006) Comparison of multi-modal optimization algorithms based on evolutionary algorithms. In: Proceedings of the 8th annual conference on genetic and evolutionary computation. pp 1305–1312 Singh G, Deb DR K (2006) Comparison of multi-modal optimization algorithms based on evolutionary algorithms. In: Proceedings of the 8th annual conference on genetic and evolutionary computation. pp 1305–1312
go back to reference Teytaud F, Teytaud O (2016) Qr mutations improve many evolution strategies: a lot on highly multimodal problems. In: Proceedings of the 2016 GECCO conference. pp. 35–36 Teytaud F, Teytaud O (2016) Qr mutations improve many evolution strategies: a lot on highly multimodal problems. In: Proceedings of the 2016 GECCO conference. pp. 35–36
go back to reference Valko M, Carpentier A, Munos R (2013) Stochastic simultaneous optimistic optimization. In: Proceedings of the 30th international conference on machine learning, vol 28 Valko M, Carpentier A, Munos R (2013) Stochastic simultaneous optimistic optimization. In: Proceedings of the 30th international conference on machine learning, vol 28
go back to reference Zhao H, Liu H, Xu J, Deng W (2019) Performance prediction using high-order differential mathematical morphology gradient spectrum entropy and extreme learning machine. IEEE Trans Instrum Meas 69(7):4165–4172CrossRef Zhao H, Liu H, Xu J, Deng W (2019) Performance prediction using high-order differential mathematical morphology gradient spectrum entropy and extreme learning machine. IEEE Trans Instrum Meas 69(7):4165–4172CrossRef
go back to reference Zhao H, Zheng J, Deng W, Song Y (2020) Semi-supervised broad learning system based on manifold regularization and broad network. IEEE Trans Circuits Syst I Regul Pap 67(3):983–994MathSciNetCrossRef Zhao H, Zheng J, Deng W, Song Y (2020) Semi-supervised broad learning system based on manifold regularization and broad network. IEEE Trans Circuits Syst I Regul Pap 67(3):983–994MathSciNetCrossRef
Metadata
Title
Upper confidence tree for planning restart strategies in multi-modal optimization
Authors
Amaury Dubois
Julien Dehos
Fabien Teytaud
Publication date
23-07-2020
Publisher
Springer Berlin Heidelberg
Published in
Soft Computing / Issue 2/2021
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-020-05196-w

Other articles of this Issue 2/2021

Soft Computing 2/2021 Go to the issue

Premium Partner