A Runtime Analysis of Bias-invariant Neuroevolution and Dynamic Fitness Evaluation
Pages 1560 - 1568
Abstract
In the field of neuroevolution (NE), evolutionary algorithms are used to update the weights, biases and topologies of artificial neural networks (ANNs). A recent theoretical work presented the first runtime analysis of NE in a simple setting, considering a single neuron and intuitive benchmark function classes. However, this work was limited by the unrealistic settings with regard to activation functions and fitness measurements.
In this paper, we extend upon this first work by overcoming the two shortcomings. Firstly, we consider a more realistic setting in which the NE also evolves a third parameter, termed the bend, allowing the previous benchmark function classes to be solved efficiently even in the fixed bias case. This setting mimics rectified linear unit activation functions, which are common in real-world applications of ANNs. Secondly, we consider a dynamic fitness function evaluation paradigm where the weights and biases are updated after each new sample. Experimental results in both cases support the presented theoretical results.
References
[1]
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. 2016. Understanding deep neural networks with rectified linear units. arXiv preprint arXiv:1611.01491 (2016).
[2]
H. A. David and H. N. Nagaraja. 2003. Order Statistics. Vol. 3rd. Wiley.
[3]
Benjamin Doerr, Carola Doerr, and Franziska Ebel. 2015. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science 567 (2015), 87--104.
[4]
Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2018. Static and self-adjusting mutation strengths for multi-valued decision variables. Algorithmica 80 (2018), 1732--1768.
[5]
Benjamin Doerr, Daniel Johannsen, and Carola Winzen. 2010. Multiplicative drift analysis. In Proceedings of the 12th annual conference on Genetic and evolutionary computation. 1449--1456.
[6]
Benjamin Doerr and Zhongdi Qu. 2023. Runtime analysis for the NSGA-II: Provable speed-ups from crossover. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37. 12399--12407.
[7]
Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1+ 1) evolutionary algorithm. Theoretical Computer Science 276, 1-2 (2002), 51--81.
[8]
Paul Fischer, Emil Lundt Larsen, and Carsten Witt. 2023. First Steps towards a Runtime Analysis of Neuroevolution. In Proceedings of the Workshop on Foundations of Genetic Algorithms (FOGA '23).
[9]
Matteo Fischetti and Jason Jo. 2018. Deep neural networks and mixed integer linear optimization. Constraints 23, 3 (2018), 296--309.
[10]
Edgar Galván and Peter Mooney. 2021. Neuroevolution in deep neural networks: Current trends and future challenges. IEEE Transactions on Artificial Intelligence 2, 6 (2021), 476--493.
[11]
George T Hall, Pietro S Oliveto, and Dirk Sudholt. 2020. Fast perturbative algorithm configurators. In Parallel Problem Solving from Nature-PPSN XVI: 16th International Conference, PPSN 2020, Leiden, The Netherlands, September 5-9, 2020, Proceedings, Part I 16. Springer, 19--32.
[12]
Zeqiong Lv, Chao Qian, and Yanan Sun. 2024. A First Step Towards Runtime Analysis of Evolutionary Neural Architecture Search. arXiv:2401.11712 [cs.NE]
[13]
Kenneth O Stanley, Jeff Clune, Joel Lehman, and Risto Miikkulainen. 2019. Designing neural networks through neuroevolution. Nature Machine Intelligence 1, 1 (2019), 24--35.
[14]
Kenneth O Stanley and Risto Miikkulainen. 2002. Evolving neural networks through augmenting topologies. Evolutionary computation 10, 2 (2002), 99--127.
[15]
Vincent Tjeng, Kai Xiao, and Russ Tedrake. 2017. Evaluating robustness of neural networks with mixed integer programming. arXiv preprint arXiv:1711.07356 (2017).
[16]
Hamit Taner Ünal and Fatih Başçiftçi. 2022. Evolutionary design of neural network architectures: a review of three decades of research. Artificial Intelligence Review (2022), 1--80.
[17]
Weijie Zheng and Benjamin Doerr. 2023. Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives. IEEE Transactions on Evolutionary Computation (2023).
Index Terms
- A Runtime Analysis of Bias-invariant Neuroevolution and Dynamic Fitness Evaluation
Recommendations
Towards a Runtime Comparison of Natural and Artificial Evolution
Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative ...
First Steps Towards a Runtime Analysis of Neuroevolution
FOGA '23: Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic AlgorithmsWe consider a simple setting in neuroevolution where an evolutionary algorithm optimizes the weights and activation functions of a simple artificial neural network. We then define simple example functions to be learned by the network and conduct rigorous ...
First Steps Towards a Runtime Comparison of Natural and Artificial Evolution
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary ComputationEvolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse their runtime on many illustrative problems. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
1657 pages
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 July 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Independent Research Fund Denmark
Conference
GECCO '24
Sponsor:
GECCO '24: Genetic and Evolutionary Computation Conference
July 14 - 18, 2024
VIC, Melbourne, Australia
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 110Total Downloads
- Downloads (Last 12 months)110
- Downloads (Last 6 weeks)35
Reflects downloads up to 12 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in