Top

Published in:

2019 | OriginalPaper | Chapter

Scaling in Concurrent Evolutionary Algorithms

Authors : Juan J. Merelo, J. L. J. Laredo, Pedro A. Castillo, José-Mario García-Valdez, Sergio Rojas-Galeano

Published in: Applied Computer Sciences in Engineering

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The concept of channel, a computational mechanism used to convey state to different threads of process execution, is at the core of the design of multi-threaded concurrent algorithms. In the case of concurrent evolutionary algorithms, channels can be used to communicate messages between several threads performing different evolution tasks related to genetic operations or mixing of populations. In this paper we study to what extent the design of these messages in a communicating sequential process context may influence scaling and performance of concurrent evolutionary algorithms. For this aim, we designed a channel-based concurrent evolutionary algorithm that is able to effectively solve different benchmark binary problems (e.g. OneMax, LeadingOnes, RoyalRoad), showing that it provides a good basis to leverage the multi-threaded and multi-core capabilities of modern computers. Although our results indicate that concurrency is advantageous to scale-up the performance of evolutionary algorithms, they also highlight how the trade–off between concurrency, communication and evolutionary parameters affect the outcome of the evolved solutions, opening-up new opportunities for algorithm design.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Solving Large Dynamical Systems by Constraint Sampling

next chapter Sine-Cosine Algorithm for OPF Analysis in Distribution Systems to Size Distributed Generators

Andrews, G.R.: Concurrent Programming: Principles and Practice. Benjamin/Cummings Publishing Company, San Francisco (1991)MATH

Armstrong, J.: Concurrency Oriented Programming in Erlang (2003). http://ll2.ai.mit.edu/talks/armstrong.pdf

Barwell, A.D., Brown, C., Hammond, K., Turek, W., Byrski, A.: Using program shaping and algorithmic skeletons to parallelise an evolutionary multi-agent system in Erlang. Comput. Inform. 35(4), 792–818 (2017)MathSciNetMATH

Briggs, F., O’Neill, M.: Functional genetic programming and exhaustive program search with combinator expressions. Int. J. Know.-Based Intell. Eng. Syst. 12(1), 47–68 (2008). http://dl.acm.org/citation.cfm?id=1375341.1375345CrossRef

Castagna, G.: Covariance and controvariance: a fresh look at an old issue (a primer in advanced type systems for learning functional programmers). CoRR abs/1809.01427 (2018). http://arxiv.org/abs/1809.01427

Dagum, L., Menon, R.: OpenMP: an industry-standard API for shared-memory programming. Comput. Sci. Eng. (1), 46–55 (1998)CrossRef

delaOssa, L., Gámez, J.A., Puerta, J.M.: Migration of probability models instead of individuals: an alternative when applying the Island model to EDAs. In: Yao, X., et al. (eds.) PPSN 2004. LNCS, vol. 3242, pp. 242–252. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30217-9_25CrossRef

García-Valdez, J.M., Merelo-Guervós, J.J.: A modern, event-based architecture for distributed evolutionary algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO. ACM, New York (2018)

Gelernter, D.: Generative communication in Linda. ACM Trans. Program. Lang. Syst. (TOPLAS) 7(1), 80–112 (1985)CrossRef

10.

Gropp, W.D., Gropp, W., Lusk, E., Skjellum, A.: Using MPI: Portable Parallel Programming with the Message-Passing Interface, vol. 1. MIT Press, Cambridge (1999)CrossRef

11.

Hawkins, J., Abdallah, A.: A generic functional genetic algorithm. In: Proceedings of the ACS/IEEE International Conference on Computer Systems and Applications. IEEE Computer Society, Washington (2001)

12.

Hoare, C.A.R.: Communicating sequential processes. Commun. ACM 21(8), 666–677 (1978). https://doi.org/10.1145/359576.359585CrossRefMATH

13.

Huelsbergen, L.: Toward simulated evolution of machine-language iteration. In: Proceedings of the First Annual Conference on Genetic Programming, GECCO 1996, pp. 315–320. MIT Press, Cambridge (1996)

14.

Jiménez-Laredo, J.L., Eiben, A.E., van Steen, M., Merelo-Guervós, J.J.: EvAg: a scalable peer-to-peer evolutionary algorithm. Genet. Program. Evolvable Mach. 11(2), 227–246 (2010)CrossRef

15.

Jin, H., Jespersen, D., Mehrotra, P., Biswas, R., Huang, L., Chapman, B.: High performance computing using MPI and openmp on multi-core parallel systems. Parallel Comput. 37(9), 562–575 (2011)CrossRef

16.

Kerdprasop, K., Kerdprasop, N.: Concurrent computation for genetic algorithms. In: 1st International Conference on Software Technology, pp. 79–84 (2012)

17.

Lalwani, S., Sharma, H., Satapathy, S.C., Deep, K., Bansal, J.C.: A survey on parallel particle swarm optimization algorithms. Arab. J. Sci. Eng. 44(4), 2899–2923 (2019)CrossRef

18.

Laredo, J.L.J., Castillo, P.A., Mora, A.M., Merelo, J.J.: Exploring population structures for locally concurrent and massively parallel evolutionary algorithms. In: 2008 IEEE Congress on Evolutionary Computation, pp. 2605–2612, June 2008

19.

Laredo, J.L.J., Bouvry, P., Mostaghim, S., Merelo-Guervós, J.-J.: Validating a peer-to-peer evolutionary algorithm. In: Di Chio, C., et al. (eds.) EvoApplications 2012. LNCS, vol. 7248, pp. 436–445. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29178-4_44CrossRef

20.

Li, X., Liu, K., Ma, L., Li, H.: A concurrent-hybrid evolutionary algorithms with multi-child differential evolution and Guotao algorithm based on cultural algorithm framework. In: Cai, Z., Hu, C., Kang, Z., Liu, Y. (eds.) ISICA 2010. LNCS, vol. 6382, pp. 123–133. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16493-4_13CrossRef

21.

Merelo, J.J., García-Valdez, J.-M.: Going stateless in concurrent evolutionary algorithms. In: Figueroa-García, J.C., López-Santana, E.R., Rodriguez-Molano, J.I. (eds.) WEA 2018. CCIS, vol. 915, pp. 17–29. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00350-0_2CrossRef

22.

Merelo, J.J., García-Valdez, J.M.: Mapping evolutionary algorithms to a reactive, stateless architecture: using a modern concurrent language. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2018, pp. 1870–1877. ACM, New York (2018)

23.

Rojas-Galeano, S., Rodriguez, N.: A memory efficient and continuous-valued compact EDA for large scale problems. In: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, GECCO 2018, pp. 281–288. ACM (2012)

24.

Schippers, H., Van Cutsem, T., Marr, S., Haupt, M., Hirschfeld, R.: Towards an actor-based concurrent machine model. In: Proceedings of the 4th Workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems, ICOOOLPS 2009, pp. 4–9. ACM, New York (2009)

25.

Sher, G.I.: Handbook of Neuroevolution Through Erlang. Springer, Heidelberg (2013). https://doi.org/10.1007/978-1-4614-4463-3CrossRef

26.

Swan, J., et al.: A research agenda for metaheuristic standardization. In: Proceedings of the XI Metaheuristics International Conference (2015)

27.

Tagawa, K.: Concurrent differential evolution based on generational model for multi-core CPUs. In: Bui, L.T., Ong, Y.S., Hoai, N.X., Ishibuchi, H., Suganthan, P.N. (eds.) SEAL 2012. LNCS, vol. 7673, pp. 12–21. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34859-4_2CrossRef

28.

Valkov, L., Chaudhari, D., Srivastava, A., Sutton, C., Chaudhuri, S.: Synthesis of differentiable functional programs for lifelong learning. arXiv preprint arXiv:1804.00218 (2018)

29.

Walsh, P.: A functional style and fitness evaluation scheme for inducting high level programs. In: Banzhaf, W., et al. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference, vol. 2, pp. 1211–1216. Morgan Kaufmann (1999)

Title: Scaling in Concurrent Evolutionary Algorithms
Authors: Juan J. Merelo
J. L. J. Laredo
Pedro A. Castillo
José-Mario García-Valdez
Sergio Rojas-Galeano
Publisher: Springer International Publishing
Book: Applied Computer Sciences in Engineering
Print ISBN: 978-3-030-31018-9

Electronic ISBN: 978-3-030-31019-6

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-31019-6_2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner