research-article

An asynchronous parallel implementation of a cellular genetic algorithm for combinatorial optimization

Authors:

Gabriel Luque,

Enrique Alba,

Bernabé DorronsoroAuthors Info & Claims

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

Pages 1395 - 1402

https://doi.org/10.1145/1569901.1570088

Published: 08 July 2009 Publication History

Get Access

Abstract

Cellular genetic algoritms (cGAs) are characterized by its grid structure population, in which individuals can only interact with their neighbors. This kind of algorithms has demonstrated to have a high numerical performance thanks to the good exploration/exploitation balance they perform in the search space. Although cGAs seem very appropriate for parallelism, there is a low number of works proposing or studing parallel models for clusters of computers. This is probably because the model requires a high communication level between sub-populations due to the tight interactions among individuals. These parallel versions are however needed to cope with the high computational requirements of the current real-world problems. This article proposes a new parallel cellular genetic algorithm which maintains (or even improves because its asynchronicity) the numerical behaviour of a serial cGA, while at the same time it provokes an important reduction on the execution time for finding the optimal solution.

References

[1]

E. Alba, editor. Parallel Metaheuristics: A New Class of Algorithms. Wiley, 2005.

Digital Library

Google Scholar

[2]

E. Alba, F. Almeida, M. Blesa, C. Cotta, M. Díaz, I. Dorta, J. Gabarro, C. León, G. Luque, J. Petit, C. Rodríguez, A. Rojas, and F. Xhafa. Efficient parallel LAN/WAN algorithms for optimization. The mallba project. Parallel Computing, 32(5-6):415--440, 2006.

Digital Library

Google Scholar

[3]

E. Alba and B. Dorronsoro. Cellular Genetic Algorithms, volume 42 of Operations Research/Computer Science Interfaces. Springer-Verlag Heidelberg, 2008.

Digital Library

Google Scholar

[4]

E. Alba, B. Dorronsoro, M. Giacobini, and M. Tomassini. Handbook of Bioinspired Algorithms and Applications, chapter 7, Decentralized Cellular Evolutionary Algorithms, pages 103--120. CRC Press, 2006.

Google Scholar

[5]

E. Alba and M. Tomassini. Parallelism and evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 6(5):443--462, October 2002.

Digital Library

Google Scholar

[6]

J. Beasley. A note on solving large-median problems. European Journal on Operations Reserach, 21:270--273, 1985.

Crossref

Google Scholar

[7]

R.C. and S.R. Central facilities location. Geographical Analysis, 2:30--42, 1970.

Google Scholar

[8]

E. Cantú-Paz. Efficient and Accurate Parallel Genetic Algorithms, volume 1 of Book Series on Genetic Algorithms and Evolutionary Computation. Kluwer Academic Publishers, 2nd edition, 2000.

Digital Library

Google Scholar

[9]

M. Garey and D. Johnson, editors. Computers and Intractability. A guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.

Digital Library

Google Scholar

[10]

K.D.D. Goldberg and J. Horn. Massively multimodality, deception and genetic algorithms. In R. Männer and B. Manderick, editors, Proceedings of the PPSN II, pages 37--46. North-Holland, 1992.

Google Scholar

[11]

K.D. Jong, M. Potter, and W. Spears. Using problem generators to explore the effects of epistasis. In T. Bäck, editor, Proceedings of the Seventh International Conference on Genetic Algorithms (ICGA), pages 338--345. Morgan Kaufmann, 1997.

Google Scholar

Cited By

View all

Ivanovic MSimic V(2022)Efficient evolutionary optimization using predictive auto-scaling in containerized environmentApplied Soft Computing10.1016/j.asoc.2022.109610129:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.asoc.2022.109610
Chitty DKrawiec K(2021)A partially asynchronous global parallel genetic algorithmProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3463190(1771-1778)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3463190
Ferhat Taleb SBenalia NSadoun R(2021)Evolutionary algorithm applications for IoTs dedicated to precise irrigation systems: state of the artEvolutionary Intelligence10.1007/s12065-021-00676-w16:2(383-400)Online publication date: 12-Nov-2021
https://doi.org/10.1007/s12065-021-00676-w
Show More Cited By

Index Terms

An asynchronous parallel implementation of a cellular genetic algorithm for combinatorial optimization

Recommendations

A novel quantum-inspired evolutionary algorithm for solving combinatorial optimization problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

In this paper, we propose a novel quantum-inspired evolutionary algorithm, called NQEA, for solving combinatorial optimization problems. NQEA uses a new Q-bit update operator to increase the balance between the exploration and exploitation of the search ...
Analysis of speedups in parallel evolutionary algorithms and ( 1 + λ ) EAs for combinatorial optimization

Evolutionary algorithms are popular heuristics for solving various combinatorial problems as they are easy to apply and often produce good results. Island models parallelize evolution by using different populations, called islands, which are connected ...
A multi-start quantum-inspired evolutionary algorithm for solving combinatorial optimization problems
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Quantum-inspired evolutionary algorithms (QIEAs), as a subset of evolutionary computation, are based on the principles of quantum computing such as quantum bits and quantum superposition. In this paper, we propose a multi-start quantum-inspired ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

July 2009

2036 pages

ISBN:9781605583259

DOI:10.1145/1569901

General Chair:
Franz Rothlauf
University of Mainz, Germany

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO09

Sponsor:

GECCO09: Genetic and Evolutionary Computation Conference

July 8 - 12, 2009

Québec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
223
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ivanovic MSimic V(2022)Efficient evolutionary optimization using predictive auto-scaling in containerized environmentApplied Soft Computing10.1016/j.asoc.2022.109610129:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.asoc.2022.109610
Chitty DKrawiec K(2021)A partially asynchronous global parallel genetic algorithmProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3449726.3463190(1771-1778)Online publication date: 7-Jul-2021
https://dl.acm.org/doi/10.1145/3449726.3463190
Ferhat Taleb SBenalia NSadoun R(2021)Evolutionary algorithm applications for IoTs dedicated to precise irrigation systems: state of the artEvolutionary Intelligence10.1007/s12065-021-00676-w16:2(383-400)Online publication date: 12-Nov-2021
https://doi.org/10.1007/s12065-021-00676-w
Galán S(2021)Extending cellular evolutionary algorithms with message passingSoft Computing10.1007/s00500-021-05612-9Online publication date: 2-Feb-2021
https://doi.org/10.1007/s00500-021-05612-9
Fernandes CFachada NLaredo JMerelo JRosa A(2020)Population Sizing of Cellular Evolutionary AlgorithmsSwarm and Evolutionary Computation10.1016/j.swevo.2020.100721(100721)Online publication date: Jun-2020
https://doi.org/10.1016/j.swevo.2020.100721
Alba ELuque GNesmachnow S(2012)Parallel metaheuristics: recent advances and new trendsInternational Transactions in Operational Research10.1111/j.1475-3995.2012.00862.x20:1(1-48)Online publication date: 13-Aug-2012
https://doi.org/10.1111/j.1475-3995.2012.00862.x
Nielsen SDorronsoro BDanoy GBouvry P(2012)Novel efficient asynchronous cooperative co-evolutionary multi-objective algorithms2012 IEEE Congress on Evolutionary Computation10.1109/CEC.2012.6252903(1-7)Online publication date: Jun-2012
https://doi.org/10.1109/CEC.2012.6252903

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A novel quantum-inspired evolutionary algorithm for solving combinatorial optimization problems

Analysis of speedups in parallel evolutionary algorithms and ( 1 + λ ) EAs for combinatorial optimization

A multi-start quantum-inspired evolutionary algorithm for solving combinatorial optimization problems