research-article

Open access

A partially asynchronous global parallel genetic algorithm

Author:

Darren M. ChittyAuthors Info & Claims

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Pages 1771 - 1778

https://doi.org/10.1145/3449726.3463190

Published: 08 July 2021 Publication History

Abstract

Population-based meta-heuristics such as Genetic Algorithms (GA) are ideal for exploiting multiple processor cores. With parallel architectures now standard computationally intensive methods need to harness them to best effect. A synchronous globally parallel GA creates and evaluates population members in parallel at each generation resulting in considerable processor time spent waiting for threads. An asynchronous approach whereby parallel threads continue evolution without waiting addresses this issue but can result in memory conflicts. This paper introduces an asynchronous global GA model for shared memory CPUs without memory conflicts. Experiments demonstrate performance gains of 1.35 to 12 fold dependant on problem and population sizes. However, an asynchronous model leads to non-uniform evolution reducing accuracy. Consequently, this paper demonstrates that combining synchronous and asynchronous methods into a partially asynchronous model retains a speed advantage whilst improving solution accuracy.

References

[1]

Enrique Alba and José M Troya. 2001. Analyzing synchronous and asynchronous parallel distributed genetic algorithms. Future Generation Computer Systems 17, 4 (2001), 451--465.

Digital Library

[2]

Marko Bozikovic, Marin Golub, and Leo Budin. 2003. Solving n-Queen problem using global parallel genetic algorithm. In The IEEE Region 8 EUROCON 2003. Computer as a Tool., Vol 2. IEEE, 104--107.

[3]

Su Chen, Spencer Davis, Hai Jiang, and Andy Novobilski. 2011. CUDA-based genetic algorithm on traveling salesman problem. In Computer and Information Science 2011. Springer, 241--252.

[4]

Darren M Chitty. 2017. Applying ACO to Large Scale TSP Instances. In UK Workshop on Computational Intelligence. Springer, 104--118.

[5]

James P Cohoon, Shailesh U Hegde, Worthy N Martin, and D Richards. 1987. Punctuated equilibria: a parallel genetic algorithm. In Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms: July 28-31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA. Hillsdale, NJ: L. Erlhaum Associates, 1987.

[6]

Georges A Croes. 1958. A method for solving traveling-salesman problems. Operations research 6, 6 (1958), 791--812.

[7]

Matjaž Depolli, Roman Trobec, and Bogdan Filipič. 2013. Asynchronous master-slave parallelization of differential evolution for multi-objective optimization. Evolutionary computation 21, 2 (2013), 261--291.

[8]

Marco Dorigo and Luca Maria Gambardella. 1997. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on evolutionary computation 1, 1 (1997), 53--66.

Digital Library

[9]

Russell Eberhart and James Kennedy. 1995. Particle swarm optimization. In Proceedings of the IEEE international conference on neural networks, Vol. 4. Citeseer, 1942--1948.

[10]

Marin Golub and Leo Budin. 2000. An asynchronous model of global parallel genetic algorithms. In Second ICSC Symposium on Engineering of Intelligent Systems EIS2000, University of Paisley, Scotland, UK. Citeseer, 353--359.

[11]

John J Grefenstette. 1981. Parallel adaptive algorithms for function optimization. Vanderbilt University, Nashville, TN, Tech. Rep. CS-81-19 (1981).

[12]

Michael Guntsch and Martin Middendorf. 2002. A population based approach for ACO. In Workshops on Applications of Evolutionary Computation. Springer, 72--81.

[13]

Tomohiro Harada and Keiki Takadama. 2020. Analysis of semi-asynchronous multi-objective evolutionary algorithm with different asynchronies. Soft Computing 24, 4 (2020), 2917--2939.

Digital Library

[14]

John H Holland. 1975. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. U Michigan Press.

[15]

Gabriel Luque, Enrique Alba, and Bernabé Dorronsoro. 2009. An asynchronous parallel implementation of a cellular genetic algorithm for combinatorial optimization. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation. 1395--1402.

Digital Library

[16]

Bernard Manderick and Piet Spiessens. 1989. Fine-grained parallel genetic algorithms. In Proceedings of the third international conference on Genetic algorithms. 428--433.

Digital Library

[17]

Heinz Mühlenbein. 1989. Parallel genetic algorithms, population genetics and combinatorial optimization. In Workshop on Parallel Processing: Logic, Organization, and Technology. Springer, 398--406.

Digital Library

[18]

Heinz Mühlenbein. 1991. Evolution in time and space-the parallel genetic algorithm. In Foundations of genetic algorithms. Vol. 1. Elsevier, 316--337.

[19]

Frédéric Pinel, Bernabé Dorronsoro, and Pascal Bouvry. 2010. A new parallel asynchronous cellular genetic algorithm for scheduling in grids. In 2010 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW). IEEE, 1--8.

[20]

Petr Pospichal, Jiri Jaros, and Josef Schwarz. 2010. Parallel genetic algorithm on the cuda architecture. In European conference on the applications of evolutionary computation. Springer, 442--451.

Digital Library

[21]

Khaled Rasheed and Brian D Davison. 1999. Effect of global parallelism on the behavior of a steady state genetic algorithm for design optimization. In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), Vol. 1. IEEE, 534--541.

[22]

Reiko Tanese. 1987. Parallel genetic algorithm for a hypercube. In Genetic algorithms and their applications: proceedings of the second International Conference on Genetic Algorithms: July 28-31, 1987 at the Massachusetts Institute of Technology, Cambridge, MA. Hillsdale, NJ: L. Erlhaum Associates, 1987.

[23]

Pablo Vidal and Enrique Alba. 2010. Cellular genetic algorithm on graphic processing units. In Nature Inspired Cooperative Strategies for Optimization (NICSO 2010). Springer, 223--232.

Cited By

Chitty DYates WKeedwell E(2024)Using Evolutionary Routing Optimisation to Transition to Electric Vehicle FleetsAdvances in Computational Intelligence Systems10.1007/978-3-031-55568-8_41(489-501)Online publication date: 19-May-2024
https://doi.org/10.1007/978-3-031-55568-8_41
Chitty DLewis JKeedwell ESilva SPaquete L(2023)Using a Parallel Ensemble of Sequence-Based Selection Hyper-Heuristics for Electric Bus SchedulingProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596340(1712-1720)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596340
Harada T(2022)A frequency-based parent selection for reducing the effect of evaluation time bias in asynchronous parallel multi-objective evolutionary algorithmsNatural Computing10.1007/s11047-022-09940-zOnline publication date: 29-Dec-2022
https://doi.org/10.1007/s11047-022-09940-z
Show More Cited By

Index Terms

A partially asynchronous global parallel genetic algorithm
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

Asynchronous parallel cartesian genetic programming
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference Companion

The run-time of evolutionary algorithms (EAs) is typically dominated by fitness evaluation. This is particularly the case when the genotypes are complex, such as in genetic programming (GP). Evaluating multiple offspring in parallel is appropriate in ...
Hybrid Taguchi-genetic algorithm for global numerical optimization

In this paper, a hybrid Taguchi-genetic algorithm (HTGA) is proposed to solve global numerical optimization problems with continuous variables. The HTGA combines the traditional genetic algorithm (TGA), which has a powerful global exploration capability,...
Development of a parallel optimization method based on genetic simulated annealing algorithm

This paper presents a parallel genetic simulated annealing (PGSA) algorithm that has been developed and applied to optimize continuous problems. In PGSA, the entire population is divided into sub-populations, and in each sub-population the algorithm ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference Companion

July 2021

2047 pages

ISBN:9781450383516

DOI:10.1145/3449726

Editor:
Francisco Chicano
University of Malaga
,
General Chair:
Krzysztof Krawiec
Poznan University of Technology

Copyright © 2021 ACM.

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]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '21

Sponsor:

SIGEVO

GECCO '21: Genetic and Evolutionary Computation Conference

July 10 - 14, 2021

Lille, France

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
276
Total Downloads

Downloads (Last 12 months)114
Downloads (Last 6 weeks)11

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chitty DYates WKeedwell E(2024)Using Evolutionary Routing Optimisation to Transition to Electric Vehicle FleetsAdvances in Computational Intelligence Systems10.1007/978-3-031-55568-8_41(489-501)Online publication date: 19-May-2024
https://doi.org/10.1007/978-3-031-55568-8_41
Chitty DLewis JKeedwell ESilva SPaquete L(2023)Using a Parallel Ensemble of Sequence-Based Selection Hyper-Heuristics for Electric Bus SchedulingProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596340(1712-1720)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596340
Harada T(2022)A frequency-based parent selection for reducing the effect of evaluation time bias in asynchronous parallel multi-objective evolutionary algorithmsNatural Computing10.1007/s11047-022-09940-zOnline publication date: 29-Dec-2022
https://doi.org/10.1007/s11047-022-09940-z
Chitty DKeedwell E(2022)Defining a Quality Measure Within Crossover: An Electric Bus Scheduling Case StudyArtificial Evolution10.1007/978-3-031-42616-2_6(73-88)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-42616-2_6
Chitty D(2022)Combining Edge Recombination Crossover with Ant Colony Optimisation for Improved RoutingIntelligent Systems and Applications10.1007/978-3-031-16078-3_13(215-235)Online publication date: 1-Sep-2022
https://doi.org/10.1007/978-3-031-16078-3_13
Chitty D(2021)A Greedy Approach to Ant Colony Optimisation Inspired Mutation for Permutation Type Problems2021 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI50451.2021.9660169(1-8)Online publication date: 5-Dec-2021
https://doi.org/10.1109/SSCI50451.2021.9660169
Chitty D(2021)ACO Inspired GA Mutation Applied to the TSPAdvances in Computational Intelligence Systems10.1007/978-3-030-87094-2_9(95-107)Online publication date: 18-Nov-2021
https://doi.org/10.1007/978-3-030-87094-2_9

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents