2020

Versatile Black-Box Optimization

Liu, Jialin, Moreau, Antoine, Preuss, Mike et al.

Understand

Choosing automatically the right algorithm using problem descriptors is a classical component of combinatorial optimization.

It is also a good tool for making evolutionary algorithms fast, robust and versatile.
We present Shiwa, an algorithm good at both discrete and continuous, noisy and noise-free, sequential and parallel, black-box optimization.
Our algorithm is experimentally compared to competitors on YABBOB, a BBOB comparable testbed, and on some variants of it, and then validated on several real world testbeds.

Built on

Ultra thin anti-reflective coatings designed using Differential Evolution
Original
Emmanuel Centeno, Amira Farahoui, Rafik Smaali, Angélique Bousquet, François Réveret, Olivier Teytaud, and Antoine Moreau. 2019 · 1904
Earlier work this paper cites.
Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks . 1942–1948
James Kennedy and Russell C. Eberhart. 1995 · 1948
Earlier work this paper cites.
Monte-Carlo Methods For Solving Multivariate Problems
J. M. Hammersley. 1960 · 1960
Earlier work this paper cites.
An efficient method for finding the minimum of a function of several variables without calculating derivatives
M. J. D. Powell. 1964 · 1964
Earlier work this paper cites.
Genetic Algorithms and the Optimal Allocation of Trials
John H. Holland. 1973 · 1973
Earlier work this paper cites.
The Algorithm Selection Problem
John Rischard Rice. 1976 · 1976
Earlier work this paper cites.
A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation
M. J. D. Powell. 1994 · 1994
Earlier work this paper cites.
Formal memetic algorithms. In Evolutionary Computing: AISB Workshop , T.C. Fogarty (Ed.). Springer Verlag LNCS 865, 1–16
N. J. Radcliffe and P. D. Surry. 1994 · 1994
Earlier work this paper cites.
Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In Proceedings of IEEE international conference on evolutionary computation . IEEE, 312–317
Nikolaus Hansen and Andreas Ostermeier. 1996 · 1996
Earlier work this paper cites.
From recombination of genes to the estimation of distributions I. Binary parameters. In International conference on parallel problem solving from nature . Springer, 178–187
Heinz Mühlenbein and Gerhard Paass. 1996 · 1996
Earlier work this paper cites.
Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces
Rainer Storn and Kenneth Price. 1997 · 1997
Earlier work this paper cites.
No free lunch theorems for optimization
D. H. Wolpert and W. G. Macready. 1997 · 1997
Earlier work this paper cites.
Efficient Global Optimization of Expensive Black-Box Functions
Donald R. Jones, Matthias Schonlau, and William J. Welch. 1998 · 1998
Earlier work this paper cites.
Expanding from Discrete to Continuous Estimation of Distribution Algorithms: The IDEA. In International Conference on Parallel Problem Solving from Nature . Springer, 767–776
Peter AN Bosman and Dirk Thierens. 2000 · 2000
Earlier work this paper cites.
The Theory of Evolution Strategies
H.-G. Beyer. 2001 · 2001
Earlier work this paper cites.
A survey of optimization by building and using probabilistic models
Martin Pelikan, David E Goldberg, and Fernando G Lobo. 2002 · 2002
Earlier work this paper cites.
On the discrepancy of the Halton sequences
Emanouil I Atanassov. 2004 · 2004
Earlier work this paper cites.
C4.5 competence map: a phase transition-inspired approach. In Machine Learning, Proceedings of the Twenty-first International Conference (ICML 2004), Banff, Alberta, Canada, July 4-8, 2004
Nicolas Baskiotis and Michèle Sebag. 2004 · 2004
Earlier work this paper cites.

Similar

Computing “ELO ratings” of move patterns in the game of Go
Rémi Coulom. 2007 · 2007
Cited alongside, same era.
Hoeffding and Bernstein Races for Selecting Policies in Evolutionary Direct Policy Search. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML ’09) . ACM, 401–408
Verena Heidrich-Meisner and Christian Igel. 2009 · 2009
Cited alongside, same era.
Cross-Disciplinary Perspectives on Meta-Learning for Algorithm Selection
Kate Amanda Smith-Miles. 2009 · 2009
Cited alongside, same era.
Algorithms for infinitely many-armed bandits. In Advances in Neural Information Processing Systems . 1729–1736
Yizao Wang, Jean-Yves Audibert, and Rémi Munos. 2009 · 2009
Cited alongside, same era.
An analysis of the operation of differential evolution at high and low crossover rates. In IEEE Congress on Evolutionary Computation . 1–8
J. Montgomery and S. Chen. 2010 · 2010
Cited alongside, same era.
Pure exploration in finitely-armed and continuous-armed bandits
Sébastien Bubeck, Rémi Munos, and Gilles Stoltz. 2011 · 2011
Cited alongside, same era.
Exploratory Landscape Analysis. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO) (Dublin, Ireland). ACM, 829 – 836
Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, and Günter Rudolph. 2011 · 2011
Cited alongside, same era.
http://lists.lri.fr/pipermail/bbob-discuss/2012-April/000270.html
Hans-Georg Beyer. 2012a · 2012
Cited alongside, same era.
http://lists.lri.fr/pipermail/bbob-discuss/2012-April/000258.html
Hans-Georg Beyer. 2012b · 2012
Cited alongside, same era.
http://lists.lri.fr/pipermail/bbob-discuss/2012-April/000257.html
Remi Coulom. 2012a · 2012
Cited alongside, same era.
http://lists.lri.fr/pipermail/bbob-discuss/2012-April/000252.html
Remi Coulom. 2012b · 2012
Cited alongside, same era.
Real-Parameter Black-Box Optimization Benchmarking: Experimental Setup
Nikolaus Hansen, Anne Auger, Steffen Finck, and Raymond Ros. 2012 · 2012
Cited alongside, same era.

Then

ASlib: A Benchmark Library for Algorithm Selection
Bernd Bischl, Pascal Kerschke, Lars Kotthoff, Thomas Marius Lindauer, Yuri Malitsky, Alexandre Fréchette, Holger H. Hoos, Frank Hutter, Kevin Leyton-Brown, Kevin Tierney, and Joaquin Vanschoren. 2016 · 2016
Later among the works it cites.
Algorithm portfolios for noisy optimization
Marie-Liesse Cauwet, Jialin Liu, Baptiste Rozière, and Olivier Teytaud. 2016 · 2016
Later among the works it cites.
Self-adaptation of Mutation Rates in Non-elitist Populations. In Parallel Problem Solving from Nature - PPSN XIV - 14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings . 803–813
Duc-Cuong Dang and Per Kristian Lehre. 2016 · 2016
Later among the works it cites.
Evolution Under Strong Noise: A Self-Adaptive Evolution Strategy Can Reach the Lower Performance Bound - The pcCMSA-ES. In Parallel Problem Solving from Nature – PPSN XIV , Julia Handl, Emma Hart, Peter R. Lewis, Manuel López-Ibáñez, Gabriela Ochoa, and Ben Paechter (Eds.). Springer International Publishing, Cham, 26–36
Michael Hellwig and Hans-Georg Beyer. 2016 · 2016
Later among the works it cites.
Efficient implementation of enhanced adaptive simultaneous perturbation algorithms. In 2016 Annual Conference on Information Science and Systems, CISS 2016, Princeton, NJ, USA, March 16-18, 2016 . 298–303
Pushpendre Rastogi, Jingyi Zhu, and James C. Spall. 2016 · 2016
Later among the works it cites.
Fast Genetic Algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO ’17) . ACM, 777–784
Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. 2017 · 2017
Later among the works it cites.
Evolutionary algorithms converge towards evolved biological photonic structures
Original
Mamadou Aliou Barry, Vincent Berthier, Bodo D. Wilts, Marie-Claire Cambourieux, Rémi Pollés, Olivier Teytaud, Emmanuel Centeno, Nicolas Biais, and Antoine Moreau. 2018 · 2018
Later among the works it cites.
Exploratory Landscape Analysis of the MLDA Problem Set. In Proceedings of PPSN18 Workshops
Marcus Gallagher and Sobia Saleem. 2018 · 2018
Later among the works it cites.
Automated Algorithm Selection: Survey and Perspectives
Pascal Kerschke, Holger H. Hoos, Frank Neumann, and Heike Trautmann. 2018 · 2018
Later among the works it cites.
Automated Algorithm Selection on Continuous Black-Box Problems By Combining Exploratory Landscape Analysis and Machine Learning
Pascal Kerschke and Heike Trautmann. 2018 · 2018
Later among the works it cites.
Large Scale Black-box Optimization by Limited-Memory Matrix Adaptation
I. Loshchilov, T. Glasmachers, and H.-G. Beyer. 2019 · 2018
Later among the works it cites.
Nevergrad - A gradient-free optimization platform
J. Rapin and O. Teytaud. 2018 · 2018
Later among the works it cites.
Artelys Knitro, winner of the 2019 BBComp edition
Artelys. 2019 · 2019
Later among the works it cites.
Fully Parallel Hyperparameter Search: Reshaped Space-Filling
M. L. Cauwet, C. Couprie, J. Dehos, P. Luc, J. Rapin, M. Riviere, F. Teytaud, and O. Teytaud. 2019 · 2019
Later among the works it cites.
Consistent population control: generate plenty of points, but with a bit of resampling. In Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA 2019, Potsdam, Germany, August 27-29, 2019 . 116–123
Vasil Khalidov, Maxime Oquab, Jérémy Rapin, and Olivier Teytaud. 2019 · 2019
Later among the works it cites.
Parallel Noisy Optimization in Front of Simulators: Optimism, Pessimism, Repetitions, Population Control. In Workshop Data-driven Optimization and Applications at CEC
Maxime Oquab, Jeremy Rapin, Olivier Teytaud, and Tristan Cazenave. 2019 · 2019
Later among the works it cites.
Openly revisiting derivative-free optimization. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2019, Prague, Czech Republic, July 13-17, 2019 , Manuel López-Ibáñez, Anne Auger, and Thomas Stützle (Eds.). ACM, 267–268
Jérémy Rapin, Pauline Dorval, Jules Pondard, Nicolas Vasilache, Marie-Liesse Cauwet, Camille Couprie, and Olivier Teytaud. 2019 · 2019
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…