research-article

Evolving continuous optimisers from scratch

Author:

Michael A. LonesAuthors Info & Claims

Genetic Programming and Evolvable Machines, Volume 22, Issue 4

Pages 395 - 428

https://doi.org/10.1007/s10710-021-09414-8

Published: 01 December 2021 Publication History

Abstract

This work uses genetic programming to explore the space of continuous optimisers, with the goal of discovering novel ways of doing optimisation. In order to keep the search space broad, the optimisers are evolved from scratch using Push, a Turing-complete, general-purpose, language. The resulting optimisers are found to be diverse, and explore their optimisation landscapes using a variety of interesting, and sometimes unusual, strategies. Significantly, when applied to problems that were not seen during training, many of the evolved optimisers generalise well, and often outperform existing optimisers. This supports the idea that novel and effective forms of optimisation can be discovered in an automated manner. This paper also shows that pools of evolved optimisers can be hybridised to further increase their generality, leading to optimisers that perform robustly over a broad variety of problem types and sizes.

References

[1]

M. Andrychowicz, M. Denil, S. Gomez, M.W. Hoffman, D. Pfau, T. Schaul, B. Shillingford, N. De Freitas, Learning to learn by gradient descent by gradient descent. In: NIPS’16: Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 3988–3996 (2016)

[2]

J. de Armas, E. Lalla-Ruiz, S.L. Tilahun, S. Voß, Similarity in metaheuristics: a gentle step towards a comparison methodology. Nat. Compu. (2021).

[3]

A. Auger, N. Hansen, A restart CMA evolution strategy with increasing population size. In: Proceedings of the IEEE Congress on Evolutionary Computation, IEEE CEC ’05, vol. 2, pp. 1769–1776. IEEE (2005)

[4]

Blum C and Ochoa G A comparative analysis of two matheuristics by means of merged local optima networks Eur. J. Oper. Res. 2021 290 1 36-56

[5]

Blum C and Raidl GR Hybrid Metaheuristics: Powerful Tools for Optimization 2016 Berlin Springer

[6]

A. Bogdanova, J.P. Junior, C. Aranha, Franken-swarm: grammatical evolution for the automatic generation of swarm-like meta-heuristics. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’19, pp. 411–412. ACM (2019)

[7]

Burke EK, Gendreau M, Hyde M, Kendall G, Ochoa G, Özcan E, and Qu R Hyper-heuristics: a survey of the state of the art J. Oper. Res. Soc. 2013 64 12 1695-1724

[8]

L.A. Christie, A.E. Brownlee, J.R. Woodward, Investigating benchmark correlations when comparing algorithms with parameter tuning. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 209–210 (2018)

[9]

C. Cotta, L. Mathieson, P. Moscato, Memetic algorithms. In: R. Martí, P.M. Pardalos, M.G.C. Resende (eds.) Handbook of Heuristics. Springer, Berlin (2017)

[10]

L. Dioşan, M. Oltean, Evolving crossover operators for function optimization. In: European Conference on Genetic Programming, pp. 97–108. Springer (2006)

[11]

B. Edmonds, Meta-genetic programming: co-evolving the operators of variation. Tech. Rep. CPM Report pp. 98–32, Manchester Metropolitan University (1998)

[12]

Gallagher M and Yuan B A general-purpose tunable landscape generator IEEE Trans. Evol. Comput. 2006 10 5 590-603

[13]

B.W. Goldman, D.R. Tauritz, Self-configuring crossover. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’11, pp. 575–582. ACM (2011)

[14]

K. Graham, An investigation of factors influencing algorithm selection for high dimensional continuous optimisation problems. Ph.D. thesis, Computing Science and Mathematics, University of Stirling (2019)

[15]

N. Hansen, A. Auger, R. Ros, S. Finck, P. Pošík, Comparing results of 31 algorithms from the black-box optimization benchmarking BBOB-2009. In: Proceedings of the 12th annual conference companion on Genetic and evolutionary computation, pp. 1689–1696 (2010)

[16]

J.P. Junior, C. Aranha, T. Sakurai, A training difficulty schedule for effective search of meta-heuristic design. In: 2020 IEEE Congress on Evolutionary Computation, CEC 2020, pp. 1–8 (2020)

[17]

N.R. Kamrath, A.S. Pope, D.R. Tauritz, The automated design of local optimizers for memetic algorithms employing supportive coevolution. In: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, pp. 1889–1897 (2020)

[18]

W. Kantschik, P. Dittrich, M. Brameier, W. Banzhaf, Meta-evolution in graph GP. In: European Conference on Genetic Programming, EuroGP 1999, pp. 15–28. Springer (1999)

[19]

B. Lacroix, J. McCall, Limitations of benchmark sets and landscape features for algorithm selection and performance prediction. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 261–262 (2019)

[20]

Langdon WB Genetic programming and data structures: genetic Programming + data structures = automatic programming! 2012 Berlin Springer

[21]

Li X, Epitropakis MG, Deb K, and Engelbrecht A Seeking multiple solutions: an updated survey on niching methods and their applications IEEE Trans. Evol. Comput. 2016 21 4 518-538

[22]

M.A. Lones, Instruction-level design of local optimisers using Push GP. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’19, pp. 1487–1494. ACM (2019)

[23]

Lones MA Mitigating metaphors: a comprehensible guide to recent nature-inspired algorithms SN Comput. Sci. 2020 1 1 49

[24]

M.A. Lones, Optimising optimisers with Push GP. In: Proceedings of the 2020 European Conference on Genetic Programming (EuroGP), LNCS, vol. 12101. Springer (2020).

[25]

N. Lourenço, F. Pereira, E. Costa, Learning selection strategies for evolutionary algorithms. In: International Conference on Artificial Evolution (Evolution Artificielle), pp. 197–208. Springer (2013)

[26]

Martí R, Pardalos PM, and Resende MGC Handbook of Heuristics 2018 Berlin Springer

[27]

M.A. Martin, D.R. Tauritz, Evolving black-box search algorithms employing genetic programming. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’13, pp. 1497–1504. ACM (2013)

[28]

Mersmann O, Preuss M, Trautmann H, Bischl B, and Weihs C Analyzing the BBOB results by means of benchmarking concepts Evol. Comput. 2015 23 1 161-185

[29]

L. Metz, N. Maheswaranathan, J. Nixon, D. Freeman, J. Sohl-dickstein, Learned optimizers that outperform SGD on wall-clock and test loss. In: Proceedings of the 2nd Workshop on Meta-Learning, MetaLearn 2018 (2018)

[30]

J.B. Mouret, J. Clune, Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909 (2015)

[31]

Oltean M Evolving evolutionary algorithms using linear genetic programming Evol. Comput. 2005 13 3 387-410

[32]

Ong YS, Nair PB, and Keane AJ Evolutionary optimization of computationally expensive problems via surrogate modeling AIAA J. 2003 41 4 687-696

[33]

R. Poli, C. Di Chio, W.B. Langdon, Exploring extended particle swarms: a genetic programming approach. In: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation, pp. 169–176 (2005)

[34]

E. Real, C., Liang, D. So, Q. Le, AutoML-zero: evolving machine learning algorithms from scratch. In: Proceedings 37th International Conference on Machine Learning, ICML, pp. 8007–8019. PMLR (2020)

[35]

S.N. Richter, D.R. Tauritz, The automated design of probabilistic selection methods for evolutionary algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’18, pp. 1545–1552. ACM (2018)

[36]

S. van Rijn, H. Wang, M. van Leeuwen, T. Bäck, Evolving the structure of evolution strategies. In: 2016 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1–8. IEEE (2016)

[37]

Rönkkönen J, Li X, Kyrki V, and Lampinen J A framework for generating tunable test functions for multimodal optimization Soft Comput. 2011 15 9 1689-1706

[38]

B.J. Ross, Searching for search algorithms: experiments in meta-search. Technical Report CS-02-23, Department of Computer Science, Brock University (2002)

[39]

C. Ryan, J.J. Collins, M.O. Neill, Grammatical evolution: evolving programs for an arbitrary language. In: European Conference on Genetic Programming, pp. 83–96. Springer (1998)

[40]

P. Ryser-Welch, J.F. Miller, J. Swan, M.A. Trefzer, Iterative cartesian genetic programming: creating general algorithms for solving travelling salesman problems. In: European Conference on Genetic Programming, EuroGP ’16, pp. 294–310. Springer (2016)

[41]

S. Shirakawa, T. Nagao, Evolution of search algorithms using graph structured program evolution. In: European Conference on Genetic Programming, pp. 109–120. Springer (2009)

[42]

Sörensen K Metaheuristics—the metaphor exposed Int. Trans. Oper. Res. 2015 22 1 3-18

[43]

L. Spector, Autoconstructive evolution: Push, pushGP, and pushpop. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’19, vol. 137 (2001)

[44]

L. Spector, C. Perry, J, Klein, M. Keijzer, Push 3.0 programming language description. Tech. rep., HC-CSTR-2004-02, School of Cognitive Science, Hampshire College (2004)

[45]

Spector L and Robinson A Genetic programming and autoconstructive evolution with the push programming language Genet. Program. Evol. Mach. 2002 3 1 7-40

[46]

J. Stork, A.E. Eiben, T. Bartz-Beielstein, A new taxonomy of global optimization algorithms. Natural Computing pp. 1–24 (2020)

[47]

P.N. Suganthan, N. Hansen, J.J. Liang, K. Deb, Y.P. Chen, A. Auger, S. Tiwari, Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. KanGAL report 2005005(2005)

[48]

A. Teller, Evolving programmers: The co-evolution of intelligent recombination operators. In: P.J. Angeline, K.E. Kinnear, Jr. (eds.) Advances in Genetic Programming 2, chap. 3, pp. 45–68. MIT Press (1996)

[49]

O. Wichrowska, N. Maheswaranathan, M.W. Hoffman, S.G. Colmenarejo, M. Denil, M., N. de Freitas, J. Sohl-Dickstein, Learned optimizers that scale and generalize. In: Proceedings of the 34th International Conference on Machine Learning, Vol. 70, ICML ’17, pp. 3751–3760 (2017)

[50]

Wolpert DH and Macready WG No free lunch theorems for optimization IEEE Trans. Evol. Comput. 1997 1 1 67-82

[51]

J.R. Woodward, J. Swan, The automatic generation of mutation operators for genetic algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO ’12, pp. 67–74. ACM (2012)

Cited By

Stanovov VLi XHandl J(2024)Designing Black-Box Optimizers with PushGPProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654172(535-538)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654172
Wurth JStegherr HHeider MHähner JLi XHandl J(2024)GRAHF: A Hyper-Heuristic Framework for Evolving Heterogeneous Island Model TopologiesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654136(1054-1063)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654136
Tiso SCarvalho PLourenço NMachado PSilva SPaquete L(2023)Biological insights on grammar-structured mutations improve fitness and diversityProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590472(558-567)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590472
Show More Cited By

Index Terms

Evolving continuous optimisers from scratch
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Heuristic function construction
  2. Machine learning
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Index terms have been assigned to the content through auto-classification.

Recommendations

Optimising Optimisers with Push GP
Genetic Programming
Abstract
This work uses Push GP to automatically design both local and population-based optimisers for continuous-valued problems. The optimisers are trained on a single function optimisation landscape, using random transformations to discourage ...
Instruction-level design of local optimisers using push GP
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

This work uses genetic programming to explore the design space of local optimisation algorithms. Optimisers are expressed in the Push programming language, a stack-based language with a wide range of typed primitive instructions. The evolutionary ...
Evolving dynamic fitness measures for genetic programming
Highlights
- Further research is conducted on dynamic fitness measure genetic programming.
- ...
Abstract
This research builds on the hypothesis that the use of different fitness measures on the different generations of genetic programming (GP) is more effective than the convention of applying the same fitness measure individually ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Genetic Programming and Evolvable Machines

Genetic Programming and Evolvable Machines Volume 22, Issue 4

Dec 2021

240 pages

ISSN:1389-2576

Issue’s Table of Contents

© The Author(s) 2021.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 December 2021

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Stanovov VLi XHandl J(2024)Designing Black-Box Optimizers with PushGPProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3638530.3654172(535-538)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638530.3654172
Wurth JStegherr HHeider MHähner JLi XHandl J(2024)GRAHF: A Hyper-Heuristic Framework for Evolving Heterogeneous Island Model TopologiesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654136(1054-1063)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654136
Tiso SCarvalho PLourenço NMachado PSilva SPaquete L(2023)Biological insights on grammar-structured mutations improve fitness and diversityProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590472(558-567)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590472
Guha RAo WKelly SBoddeti VGoodman EBanzhaf WDeb KSilva SPaquete L(2023)MOAZ: A Multi-Objective AutoML-Zero FrameworkProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590391(485-492)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590391
Garrow FLones MStewart RWagner M(2022)Why functional program synthesis matters (in the realm of genetic programming)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534045(1844-1853)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534045

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents