Abstract
Neuroevolution commonly uses speciation strategies to better explore the search space of neural network architectures. One such speciation strategy is the use of islands, which are also popular in improving the performance of distributed evolutionary algorithms. However, islands may experience stagnation, which prevents their convergence towards better solutions and can result in wasted computation. This work evaluates utilizing an island extinction and repopulation mechanism to avoid premature convergence using Evolutionary eXploration of Augmenting Memory Models (EXAMM), an asynchronous island based neuroevolution algorithm that progressively evolves recurrent neural networks (RNNs). In island extinction and repopulation, all members of the worst performing island are erased periodically and repopulated with mutated versions of the global best RNN. This island based strategy is additionally compared to NEAT’s (NeuroEvolution of Augmenting Topologies) speciation strategy. Experiments were performed using two different real-world time series datasets (coal-fired power plant and aviation flight data). With statistical significance, results show that in addition to being more scalable, this island extinction and repopulation strategy evolves better global best genomes than both EXAMM’s original island based strategy and NEAT’s speciation strategy. The extinction and repopulation strategy is easy to implement, and can be generically applied to other neuroevolution algorithms.
This material is based upon work supported by the U.S. Department of Energy, Office of Science, Office of Advanced Combustion Systems under Award Number #FE0031547 and by the Federal Aviation Administration and MITRE Corporation under the National General Aviation Flight Information Database (NGAFID) award.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
These data sets are made publicly available at EXAMM GitHub repository: https://github.com/travisdesell/exact/tree/master/datasets/ for reproduction of these results.
References
Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Trans. Evol. Comput. 6(5), 443–462 (2002)
Chung, J., Gulcehre, C., Cho, K., Bengio, Y.: Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv:1412.3555 (2014)
Collins, J., Sohl-Dickstein, J., Sussillo, D.: Capacity and trainability in recurrent neural networks. arXiv preprint arXiv:1611.09913 (2016)
De Falco, I., Della Cioppa, A., Maisto, D., Scafuri, U., Tarantino, E.: Biological invasion-inspired migration in distributed evolutionary algorithms. Inf. Sci. 207, 50–65 (2012)
Desell, T., ElSaid, A., Ororbia, A.G.: An empirical exploration of deep recurrent connections using neuro-evolution. In: The 23nd International Conference on the Applications of Evolutionary Computation (EvoStar: EvoApps 2020), Seville, Spain, April 2020
ElSaid, A.E.R., Ororbia, A.G., Desell, T.J.: Ant-based neural topology search (ANTS) for optimizing recurrent networks. In: Castillo, P.A., Jiménez Laredo, J.L., Fernández de Vega, F. (eds.) EvoApplications 2020. LNCS, vol. 12104, pp. 626–641. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-43722-0_40
Fuqua, L.M., Bralower, T.J., Arthur, M.A., Patzkowsky, M.E.: Evolution of calcareous nannoplankton and the recovery of marine food webs after the cretaceous-paleocene mass extinction. Palaios 23(4), 185–194 (2008)
Gallala, N., Zaghbib-Turki, D., Arenillas, I., Arz, J.A., Molina, E.: Catastrophic mass extinction and assemblage evolution in planktic foraminifera across the Cretaceous/Paleogene (K/PG) boundary at Bidart (SW France). Mar. Micropaleontol. 72(3–4), 196–209 (2009)
Glorot, X., Bengio, Y.: Understanding the difficulty of training deep feedforward neural networks. Aistats 9, 249–256 (2010)
Goldberg, D.E., Richardson, J., et al.: Genetic algorithms with sharing for multimodal function optimization. In: Genetic algorithms and their applications: Proceedings of the Second International Conference on Genetic Algorithms, Hillsdale, NJ, pp. 41–49. Lawrence Erlbaum (1987)
Greewood, G., Fogel, G.B., Ciobanu, M.: Emphasizing extinction in evolutionary programming. In: Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), vol. 1, pp. 666–671. IEEE (1999)
Grefenstette, J.J., et al.: Genetic algorithms for changing environments. In: PPSN, vol. 2, pp. 137–144. Citeseer (1992)
Hadjiivanov, A., Blair, A.: Complexity-based speciation and genotype representation for neuroevolution. In: 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 3092–3101. IEEE (2016)
He, K., Zhang, X., Ren, S., Sun, J.: Delving deep into rectifiers: surpassing human-level performance on ImageNet classification. In: Proceedings of the IEEE International Conference on Computer Vision, pp. 1026–1034 (2015)
Hernández, A., Botello, S., et al.: Repairing normal EDAs with selective repopulation. Appl. Math. Comput. 230, 65–77 (2014)
Hochreiter, S., Schmidhuber, J.: Long short-term memory. Neural Comput. 9(8), 1735–1780 (1997)
Jozefowicz, R., Zaremba, W., Sutskever, I.: An empirical exploration of recurrent network architectures. In: International Conference on Machine Learning, pp. 2342–2350 (2015)
Knapp, J.S., Peterson, G.L.: Natural evolution speciation for neat. In: 2019 IEEE Congress on Evolutionary Computation (CEC), pp. 1487–1493. IEEE (2019)
Krčah, P.: Effects of speciation on evolution of neural networks in highly dynamic environments. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, pp. 425–430. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34413-8_39
Krink, T., Thomsen, R.: Self-organized criticality and mass extinction in evolutionary algorithms. In: Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No. 01TH8546), vol. 2, pp. 1155–1161. IEEE (2001)
Lehman, J., Miikkulainen, R.: Enhancing divergent search through extinction events. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 951–958 (2015)
Lehman, J., Stanley, K.O.: Abandoning objectives: evolution through the search for novelty alone. Evol. Comput. 19(2), 189–223 (2011)
Liu, Y., Sun, Y., Xue, B., Zhang, M., Yen, G.: A survey on evolutionary neural architecture search. arXiv preprint arXiv:2008.10937 (2020)
Mathias, H.D., Ragusa, V.R.: An empirical study of crossover and mass extinction in a genetic algorithm for pathfinding in a continuous environment. In: 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 4111–4118. IEEE (2016)
Newman, M., Roberts, B.W.: Mass extinction: evolution and the effects of external influences on unfit species. Proc. Royal Soc. London. Ser. B: Biol. Sci. 260(1357), 31–37 (1995)
Ororbia, A., ElSaid, A., Desell, T.: Investigating recurrent neural network memory structures using neuro-evolution. In: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO 2019, pp. 446–455. ACM, New York, NY, USA (2019). https://doi.org/10.1145/3321707.3321795
Ororbia II, A.G., Mikolov, T., Reitter, D.: Learning simpler language models with the differential state framework. Neural Comput. 1–26 (2017). https://doi.org/10.1162/neco_a_01017, pMID: 28957029
Pascanu, R., Mikolov, T., Bengio, Y.: On the difficulty of training recurrent neural networks. In: International Conference on Machine Learning, pp. 1310–1318 (2013)
Rochester Institute of Technology: research computing services (2019). https://doi.org/10.34788/0S3G-QD15, https://www.rit.edu/researchcomputing/
Spears, W.: Speciation using tag bits. Handbook of Evolutionary Computation (1995)
Stanley, K., Miikkulainen, R.: Evolving neural networks through augmenting topologies. Evol. Comput. 10(2), 99–127 (2002)
Stanley, K.O., Clune, J., Lehman, J., Miikkulainen, R.: Designing neural networks through neuroevolution. Nat. Mach. Intell. 1(1), 24–35 (2019)
Stanley, K.O., D’Ambrosio, D.B., Gauci, J.: A hypercube-based encoding for evolving large-scale neural networks. Artif. Life 15(2), 185–212 (2009)
Sun, Y., Xue, B., Zhang, M., Yen, G.G.: Evolving deep convolutional neural networks for image classification. IEEE Trans. Evol. Comput. 24, 394–407 (2019)
Trujillo, L., Olague, G., Lutton, E., Fernández de Vega, F.: Discovering several robot behaviors through speciation. In: Giacobini, M., et al. (eds.) EvoWorkshops 2008. LNCS, vol. 4974, pp. 164–174. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78761-7_17
Verbancsics, P., Stanley, K.O.: Evolving static representations for task transfer. J. Mach. Learn. Res. 11(May), 1737–1769 (2010)
Wan, J., Chu, P., Jiao, Y., Li, Y.: Improvement of machine learning enhanced genetic algorithm for nonlinear beam dynamics optimization. Nucl. Instrum. Meth. Phys. Res. Sect. A: Accelerators, Spectrometers, Detectors Associated Equipment 946, 162683 (2019)
Werbos, P.J.: Backpropagation through time: what it does and how to do it. Proc. IEEE 78(10), 1550–1560 (1990)
Xie, X.F., Zhang, W.J., Yang, Z.L.: Hybrid particle swarm optimizer with mass extinction. In: IEEE 2002 International Conference on Communications, Circuits and Systems and West Sino Expositions, vol. 2, pp. 1170–1173. IEEE (2002)
Zhou, G.-B., Wu, J., Zhang, C.-L., Zhou, Z.-H.: Minimal gated unit for recurrent neural networks. Int. J. Autom. Comput. 13(3), 226–234 (2016). https://doi.org/10.1007/s11633-016-1006-2
Acknowledgements
Most of the computation of this research was done on the high performance computing clusters of Research Computing at Rochester Institute of Technology [29]. We would like to thank the Research Computing team for their assistance and the support they generously offered to ensure that the heavy computation this study required was available.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Lyu, Z., Karns, J., ElSaid, A., Mkaouer, M., Desell, T. (2021). Improving Distributed Neuroevolution Using Island Extinction and Repopulation. In: Castillo, P.A., Jiménez Laredo, J.L. (eds) Applications of Evolutionary Computation. EvoApplications 2021. Lecture Notes in Computer Science(), vol 12694. Springer, Cham. https://doi.org/10.1007/978-3-030-72699-7_36
Download citation
DOI: https://doi.org/10.1007/978-3-030-72699-7_36
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-72698-0
Online ISBN: 978-3-030-72699-7
eBook Packages: Computer ScienceComputer Science (R0)