Analysis of parallel implementations of the ant colony optimization applied to the minimum weight vertex cover problem

Raka Jovanovic; Milan Tuba; Dana Simian

Analysis of parallel implementations of the ant colony optimization applied to the minimum weight vertex cover problem

Raka Jovanovic^*, Milan Tuba, Dana Simian

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Citations (Scopus)

Abstract

In this paper we analyze various parallel implementations of the Ant Colony Optimization (ACO) applied to the Minimum Weight Vertex Cover Problem (MWVCP). We investigated the ACO algorithms applied to the MWCVP before. Here, we observe the behavior of different parallel topologies and corresponding algorithms like fully connected, replace worst, ring and independent parallel runs. We also present a variation of the algorithm corresponding to the ring topology that maintains the diversity of the search, but still moves to areas with better solutions.

Original language	English
Title of host publication	Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining
Pages	254-259
Number of pages	6
Publication status	Published - 2009
Externally published	Yes
Event	9th WSEAS International Conference on Simulation, Modelling and Optimization, SMO '09, Includes 5th WSEAS Int. Symp. Grid Computing, 5th WSEAS Int. Symp. Digital Libraries, 5th WSEAS Int. Symp. Data Mining and Intelligent Information Processing - Budapest, Hungary Duration: 3 Sept 2009 → 5 Sept 2009

Publication series

Name	Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining

Conference

Conference	9th WSEAS International Conference on Simulation, Modelling and Optimization, SMO '09, Includes 5th WSEAS Int. Symp. Grid Computing, 5th WSEAS Int. Symp. Digital Libraries, 5th WSEAS Int. Symp. Data Mining and Intelligent Information Processing
Country/Territory	Hungary
City	Budapest
Period	3/09/09 → 5/09/09

Keywords

Ant colony optimization
Combinatorial optimization
Minimum weight vertex cover
Parallel computing
Population based algorithms

Cite this

Jovanovic, R., Tuba, M., & Simian, D. (2009). Analysis of parallel implementations of the ant colony optimization applied to the minimum weight vertex cover problem. In Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining (pp. 254-259). (Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining).

Jovanovic, Raka ; Tuba, Milan ; Simian, Dana. / Analysis of parallel implementations of the ant colony optimization applied to the minimum weight vertex cover problem. Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining. 2009. pp. 254-259 (Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining).

@inproceedings{1790c172038f4798aaac676c60332cd0,

title = "Analysis of parallel implementations of the ant colony optimization applied to the minimum weight vertex cover problem",

abstract = "In this paper we analyze various parallel implementations of the Ant Colony Optimization (ACO) applied to the Minimum Weight Vertex Cover Problem (MWVCP). We investigated the ACO algorithms applied to the MWCVP before. Here, we observe the behavior of different parallel topologies and corresponding algorithms like fully connected, replace worst, ring and independent parallel runs. We also present a variation of the algorithm corresponding to the ring topology that maintains the diversity of the search, but still moves to areas with better solutions.",

keywords = "Ant colony optimization, Combinatorial optimization, Minimum weight vertex cover, Parallel computing, Population based algorithms",

author = "Raka Jovanovic and Milan Tuba and Dana Simian",

year = "2009",

language = "English",

isbn = "9789604741137",

series = "Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining",

pages = "254--259",

booktitle = "Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining",

note = "9th WSEAS International Conference on Simulation, Modelling and Optimization, SMO '09, Includes 5th WSEAS Int. Symp. Grid Computing, 5th WSEAS Int. Symp. Digital Libraries, 5th WSEAS Int. Symp. Data Mining and Intelligent Information Processing ; Conference date: 03-09-2009 Through 05-09-2009",

}

Jovanovic, R, Tuba, M & Simian, D 2009, Analysis of parallel implementations of the ant colony optimization applied to the minimum weight vertex cover problem. in Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining. Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining, pp. 254-259, 9th WSEAS International Conference on Simulation, Modelling and Optimization, SMO '09, Includes 5th WSEAS Int. Symp. Grid Computing, 5th WSEAS Int. Symp. Digital Libraries, 5th WSEAS Int. Symp. Data Mining and Intelligent Information Processing, Budapest, Hungary, 3/09/09.

Analysis of parallel implementations of the ant colony optimization applied to the minimum weight vertex cover problem. / Jovanovic, Raka; Tuba, Milan; Simian, Dana.
Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining. 2009. p. 254-259 (Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Analysis of parallel implementations of the ant colony optimization applied to the minimum weight vertex cover problem

AU - Jovanovic, Raka

AU - Tuba, Milan

AU - Simian, Dana

PY - 2009

Y1 - 2009

N2 - In this paper we analyze various parallel implementations of the Ant Colony Optimization (ACO) applied to the Minimum Weight Vertex Cover Problem (MWVCP). We investigated the ACO algorithms applied to the MWCVP before. Here, we observe the behavior of different parallel topologies and corresponding algorithms like fully connected, replace worst, ring and independent parallel runs. We also present a variation of the algorithm corresponding to the ring topology that maintains the diversity of the search, but still moves to areas with better solutions.

AB - In this paper we analyze various parallel implementations of the Ant Colony Optimization (ACO) applied to the Minimum Weight Vertex Cover Problem (MWVCP). We investigated the ACO algorithms applied to the MWCVP before. Here, we observe the behavior of different parallel topologies and corresponding algorithms like fully connected, replace worst, ring and independent parallel runs. We also present a variation of the algorithm corresponding to the ring topology that maintains the diversity of the search, but still moves to areas with better solutions.

KW - Ant colony optimization

KW - Combinatorial optimization

KW - Minimum weight vertex cover

KW - Parallel computing

KW - Population based algorithms

UR - http://www.scopus.com/inward/record.url?scp=78149368189&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:78149368189

SN - 9789604741137

T3 - Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining

SP - 254

EP - 259

BT - Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining

T2 - 9th WSEAS International Conference on Simulation, Modelling and Optimization, SMO '09, Includes 5th WSEAS Int. Symp. Grid Computing, 5th WSEAS Int. Symp. Digital Libraries, 5th WSEAS Int. Symp. Data Mining and Intelligent Information Processing

Y2 - 3 September 2009 through 5 September 2009

ER -

Jovanovic R, Tuba M, Simian D. Analysis of parallel implementations of the ant colony optimization applied to the minimum weight vertex cover problem. In Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining. 2009. p. 254-259. (Proc. 9th WSEAS Int. Conf. Simulation, Modelling and Optimization, SMO '09, 5th WSEAS Int. Symp. Grid Computing, Proc. 5th WSEAS Int. Symp. Digital Libraries, Proc. 5th WSEAS Int. Symp. Data Mining).

Analysis of parallel implementations of the ant colony optimization applied to the minimum weight vertex cover problem

Abstract

Publication series

Conference

Keywords

Other files and links

Fingerprint

Cite this