First Steps Towards a Runtime Analysis of Neuroevolution

DOI10.1145/3594805.3607125MaRDI QIDQ6120967zbMATH OpenFDO

Authors Paul Fischer, Carsten Witt

Publication date 23 February 2024

Published in Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2307.00799

zbMATH Keywords

neuroevolutionruntime analysistheory

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We 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 runtime analyses for networks with a single neuron and for a more advanced structure with several neurons and two layers. Our results show that the proposed algorithm is generally efficient on two example problems designed for one neuron and efficient with at least constant probability on the example problem for a two-layer network. In particular, the so-called harmonic mutation operator choosing steps of size $j$ with probability proportional to $1/j$ turns out as a good choice for the underlying search space. However, for the case of one neuron, we also identify situations with hard-to-overcome local optima. Experimental investigations of our neuroevolutionary algorithm and a state-of-the-art CMA-ES support the theoretical findings.

Cites work

• (1+1) EA on Generalized Dynamic OneMax
• Algorithmic analysis of a basic evolutionary algorithm for continuous optimization
• Analyzing evolutionary algorithms. The computer science perspective.
• Automata, Languages and Programming
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• First-hitting times under drift
• scientific article; zbMATH DE number 4166898 (Why is no real title available?)
• scientific article; zbMATH DE number 1754585 (Why is no real title available?)
• Multiplicative drift analysis
• On the analysis of the \((1+1)\) evolutionary algorithm
• Precision, local search and unimodal functions
• Reinforcement learning. An introduction
• Self-adjusting mutation rates with provably optimal success rules
• Static and self-adjusting mutation strengths for multi-valued decision variables
• Theory of evolutionary computation. Recent developments in discrete optimization
• Training a Single Sigmoidal Neuron Is Hard

Cited in

(3)

• Tight runtime bounds for evolutionary algorithms on sorting and crossing minimisation for layered graph drawings
• A self-adjusting compact genetic algorithm
• Runtime analysis of evolutionary neural architecture search for binary classification

This page was built for publication: First Steps Towards a Runtime Analysis of Neuroevolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6120967)