abstract

A Comparative Study of Synchronization of Parallel ACO on Multi-core Processor

Authors:

GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Pages 777 - 778

https://doi.org/10.1145/2739482.2764895

Published: 11 July 2015 Publication History

Get Access

Abstract

This paper proposes parallelization methods of ACO algorithms on a multi-core processor aiming at fast execution to find acceptable solutions. As an ACO algorithm, we use the cAS (cunning Ant System) and test on several sizes of Quadratic Assignment Problem (QAP) instances. As the parallelization method, we use agent level parallelization in one colony. According to the synchronization and exclusive control modes among threads, we propose three types of parallel ACO algorithms. Among them, that which we call the rough asynchronous parallel model shows the most promising results.

References

[1]

S. Tsutsui. cAS: Ant Colony Optimization with Cunning Ants, PPSN IX, 2006.

Digital Library

Google Scholar

[2]

M. Manfrin, M. Birattari, T. St"tzle, and M. Dorigo. Parallel ant colony optimization for the traveling salesman problems, ANTS-2006, pp. 224--234, 2006.

Digital Library

Google Scholar

[3]

R.E. Burkard, E. Cela, S. Karisch, and F. Rendl. QAPLIB ww.seas.upenn.edu/qaplib, 2009.

Google Scholar

[4]

S. Tsutsui. ACO on Multiple GPUs with CUDA for Faster Solution of QAPs, PPSN 2012, Part II, pp. 174--184, 2012.

Digital Library

Google Scholar

[5]

S. Tsutsui and N. Fujimoto. Parallel Ant Colony Optimization Algorithm on a Multi-core Processor, ANTS-2010 pp. 488--495, 2010.

Digital Library

Google Scholar

Cited By

View all

Shobaki GMuyan-Özçelik PHutton JLinck BMalyshenko VKerbow ARamirez-Ortega RGordon V(2024)Instruction Scheduling for the GPU on the GPU2024 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO57630.2024.10444869(435-447)Online publication date: 2-Mar-2024
https://doi.org/10.1109/CGO57630.2024.10444869
Ning JZhang CSun PFeng Y(2018)Comparative Study of Ant Colony Algorithms for Multi-Objective OptimizationInformation10.3390/info1001001110:1(11)Online publication date: 30-Dec-2018
https://doi.org/10.3390/info10010011

Index Terms

A Comparative Study of Synchronization of Parallel ACO on Multi-core Processor
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Parallel ant colony optimization on multi-core SIMD CPUs

Ant colony optimization (ACO) is a population-based metaheuristic for solving hard combinatorial optimization problems. Many studies are dedicated to accelerating ACO by parallel hardware, especially by graphics processing units (GPUs). However, due to ...
Study on hybrid PS-ACO algorithm

Ant colony optimization (ACO) algorithm is a recent meta-heuristic method inspired by the behavior of real ant colonies. The algorithm uses parallel computation mechanism and performs strong robustness, but it faces the limitations of stagnation and ...
A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP

Swarm-inspired optimization has become very popular in recent years. Particle swarm optimization (PSO) and Ant colony optimization (ACO) algorithms have attracted the interest of researchers due to their simplicity, effectiveness and efficiency in ...

Comments

Information & Contributors

Information

Published In

GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

July 2015

1568 pages

ISBN:9781450334884

DOI:10.1145/2739482

Editor:
Sara Silva
Universidade de Lisboa, Portugal
,
General Chair:
Anna I. Esparcia-Alcázar
Universitat Politècnica de València, Spain

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2015

Check for updates

Author Tags

Qualifiers

Abstract

Conference

GECCO '15

Sponsor:

SIGEVO

GECCO '15: Genetic and Evolutionary Computation Conference

July 11 - 15, 2015

Madrid, Spain

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
83
Total Downloads

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

Reflects downloads up to 07 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Shobaki GMuyan-Özçelik PHutton JLinck BMalyshenko VKerbow ARamirez-Ortega RGordon V(2024)Instruction Scheduling for the GPU on the GPU2024 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO57630.2024.10444869(435-447)Online publication date: 2-Mar-2024
https://doi.org/10.1109/CGO57630.2024.10444869
Ning JZhang CSun PFeng Y(2018)Comparative Study of Ant Colony Algorithms for Multi-Objective OptimizationInformation10.3390/info1001001110:1(11)Online publication date: 30-Dec-2018
https://doi.org/10.3390/info10010011

View Options

Get Access

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

Parallel ant colony optimization on multi-core SIMD CPUs

Study on hybrid PS-ACO algorithm

A comparative study of the improvement of performance using a PSO modified by ACO applied to TSP