The ability of evolutionary processes to innovate and scale up over long periods of time, observed in nature, remains a central mystery in evolutionary biology, and a challenge for algorithm designers to emulate and explain in evolutionary computation (EC). The Major Transitions in Evolution is a compelling theory that explains evolvability through a multi-scale process whereby individuality (and hence selection and variation) is continually revised by the formation of associations between formerly independent entities, a process still not fully explored in EC. Deep Optimisation (DO) is a new type of model-building optimization algorithm (MBOA) that exploits deep learning methods to enable multi-scale optimization. DO uses an autoencoder model to induce a multi-level representation of solutions, capturing the relationships between the lower-level units that contribute to the quality of a solution. Variation and selection are then performed within the induced representations, causing model-informed changes to multiple solution variables simultaneously. Here, we first show that DO has impressive performance compared with other leading MBOAs (and other rival methods) on multiple knapsack problems, a standard combinatorial optimization problem of general interest. Going deeper, we then carry out a detailed investigation to understand the differences between DO and other MBOAs, identifying key problem characteristics where other MBOAs are afflicted by exponential running times, and DO is not. This study serves to concretize our understanding of the Major Transitions theory, and why that leads to evolvability, and also provides a strong motivation for further investigation of deep learning methods in optimization.
|Title of host publication||Applications of Evolutionary Computation - 24th International Conference, EvoApplications 2021, Held as Part of EvoStar 2021, Proceedings|
|Editors||Pedro A. Castillo, Juan Luis Jiménez Laredo|
|Number of pages||16|
|Publication status||Published - 2021|
|Event||24th International Conference on the Applications of Evolutionary Computation, EvoApplications 2021 held as Part of EvoStar 2021 - Virtual, Online|
Duration: 7 Apr 2021 → 9 Apr 2021
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||24th International Conference on the Applications of Evolutionary Computation, EvoApplications 2021 held as Part of EvoStar 2021|
|Period||7/04/21 → 9/04/21|
Bibliographical noteFunding Information:
Acknowledgements. We acknowledge financial support from the EPSRC Centre for Doctoral Training in Next Generation Computational Modelling grant EP/L015382/1.
© 2021, Springer Nature Switzerland AG.
- Deep autoencoder
- Model-Building Optimisation Algorithms
- Multi-scale search
- Problem structure
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)