Comparative evaluation of parallelization strategies for evolutionary and stochastic heuristics

Sadiq M. Sait; Syed Sanaullah; Ali Mustafa Zaidi; Mustafa I. Ali

doi:10.1145/1068009.1068165

Comparative evaluation of parallelization strategies for evolutionary and stochastic heuristics

Sadiq M. Sait^*
, Syed Sanaullah
, Ali Mustafa Zaidi
, Mustafa I. Ali

^*Corresponding author for this work

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

2 Scopus citations

Abstract

In this paper we present an evaluation of selected parallel strategies for Simulated Annealing and Simulated Evolution, identifying the impact of various issues on the effectiveness of parallelization. Issues under consideration are the characteristics of these algorithms, the problem instance, and the implementation environment. Observations are presented regarding the impact of parallel strategies on runtime and achievable solution quality. Effective parallel algorithm design choices are identified, along with pitfalls to avoid. We further attempt to generalize our assessments to other heuristics.

Original language	English
Title of host publication	GECCO 2005 - Genetic and Evolutionary Computation Conference
Editors	H.G. Beyer, U.M. O'Reilly, D. Arnold, W. Banzhaf, C. Blum, E.W. Bonabeau, E. Cantu-Paz, D. Dasgupta, K. Deb, al et al
Pages	921-922
Number of pages	2
DOIs	https://doi.org/10.1145/1068009.1068165
State	Published - 2005

Publication series

Name	GECCO 2005 - Genetic and Evolutionary Computation Conference

Keywords

Combinatorial Optimization
Metaheuristics
Parallel Algorithms
Parallel Processing
Simulated Annealing
Simulated Evolution

ASJC Scopus subject areas

General Engineering

Access to Document

10.1145/1068009.1068165

Cite this

Sait, S. M., Sanaullah, S., Zaidi, A. M., & Ali, M. I. (2005). Comparative evaluation of parallelization strategies for evolutionary and stochastic heuristics. In H. G. Beyer, U. M. O'Reilly, D. Arnold, W. Banzhaf, C. Blum, E. W. Bonabeau, E. Cantu-Paz, D. Dasgupta, K. Deb, & A. et al (Eds.), GECCO 2005 - Genetic and Evolutionary Computation Conference (pp. 921-922). (GECCO 2005 - Genetic and Evolutionary Computation Conference). https://doi.org/10.1145/1068009.1068165

Sait, Sadiq M. ; Sanaullah, Syed ; Zaidi, Ali Mustafa et al. / Comparative evaluation of parallelization strategies for evolutionary and stochastic heuristics. GECCO 2005 - Genetic and Evolutionary Computation Conference. editor / H.G. Beyer ; U.M. O'Reilly ; D. Arnold ; W. Banzhaf ; C. Blum ; E.W. Bonabeau ; E. Cantu-Paz ; D. Dasgupta ; K. Deb ; al et al. 2005. pp. 921-922 (GECCO 2005 - Genetic and Evolutionary Computation Conference).

@inproceedings{d167ee4c51ee4221a3822643d832a898,

title = "Comparative evaluation of parallelization strategies for evolutionary and stochastic heuristics",

abstract = "In this paper we present an evaluation of selected parallel strategies for Simulated Annealing and Simulated Evolution, identifying the impact of various issues on the effectiveness of parallelization. Issues under consideration are the characteristics of these algorithms, the problem instance, and the implementation environment. Observations are presented regarding the impact of parallel strategies on runtime and achievable solution quality. Effective parallel algorithm design choices are identified, along with pitfalls to avoid. We further attempt to generalize our assessments to other heuristics.",

keywords = "Combinatorial Optimization, Metaheuristics, Parallel Algorithms, Parallel Processing, Simulated Annealing, Simulated Evolution",

author = "Sait, \{Sadiq M.\} and Syed Sanaullah and Zaidi, \{Ali Mustafa\} and Ali, \{Mustafa I.\}",

year = "2005",

doi = "10.1145/1068009.1068165",

language = "English",

isbn = "1595930108",

series = "GECCO 2005 - Genetic and Evolutionary Computation Conference",

pages = "921--922",

editor = "H.G. Beyer and U.M. O'Reilly and D. Arnold and W. Banzhaf and C. Blum and E.W. Bonabeau and E. Cantu-Paz and D. Dasgupta and K. Deb and \{et al\}, al",

booktitle = "GECCO 2005 - Genetic and Evolutionary Computation Conference",

}

Sait, SM, Sanaullah, S, Zaidi, AM & Ali, MI 2005, Comparative evaluation of parallelization strategies for evolutionary and stochastic heuristics. in HG Beyer, UM O'Reilly, D Arnold, W Banzhaf, C Blum, EW Bonabeau, E Cantu-Paz, D Dasgupta, K Deb & A et al (eds), GECCO 2005 - Genetic and Evolutionary Computation Conference. GECCO 2005 - Genetic and Evolutionary Computation Conference, pp. 921-922. https://doi.org/10.1145/1068009.1068165

Comparative evaluation of parallelization strategies for evolutionary and stochastic heuristics. / Sait, Sadiq M.; Sanaullah, Syed; Zaidi, Ali Mustafa et al.
GECCO 2005 - Genetic and Evolutionary Computation Conference. ed. / H.G. Beyer; U.M. O'Reilly; D. Arnold; W. Banzhaf; C. Blum; E.W. Bonabeau; E. Cantu-Paz; D. Dasgupta; K. Deb; al et al. 2005. p. 921-922 (GECCO 2005 - Genetic and Evolutionary Computation Conference).

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

TY - GEN

T1 - Comparative evaluation of parallelization strategies for evolutionary and stochastic heuristics

AU - Sait, Sadiq M.

AU - Sanaullah, Syed

AU - Zaidi, Ali Mustafa

AU - Ali, Mustafa I.

PY - 2005

Y1 - 2005

N2 - In this paper we present an evaluation of selected parallel strategies for Simulated Annealing and Simulated Evolution, identifying the impact of various issues on the effectiveness of parallelization. Issues under consideration are the characteristics of these algorithms, the problem instance, and the implementation environment. Observations are presented regarding the impact of parallel strategies on runtime and achievable solution quality. Effective parallel algorithm design choices are identified, along with pitfalls to avoid. We further attempt to generalize our assessments to other heuristics.

AB - In this paper we present an evaluation of selected parallel strategies for Simulated Annealing and Simulated Evolution, identifying the impact of various issues on the effectiveness of parallelization. Issues under consideration are the characteristics of these algorithms, the problem instance, and the implementation environment. Observations are presented regarding the impact of parallel strategies on runtime and achievable solution quality. Effective parallel algorithm design choices are identified, along with pitfalls to avoid. We further attempt to generalize our assessments to other heuristics.

KW - Combinatorial Optimization

KW - Metaheuristics

KW - Parallel Algorithms

KW - Parallel Processing

KW - Simulated Annealing

KW - Simulated Evolution

UR - https://www.scopus.com/pages/publications/32444446371

U2 - 10.1145/1068009.1068165

DO - 10.1145/1068009.1068165

M3 - Conference contribution

AN - SCOPUS:32444446371

SN - 1595930108

T3 - GECCO 2005 - Genetic and Evolutionary Computation Conference

SP - 921

EP - 922

BT - GECCO 2005 - Genetic and Evolutionary Computation Conference

A2 - Beyer, H.G.

A2 - O'Reilly, U.M.

A2 - Arnold, D.

A2 - Banzhaf, W.

A2 - Blum, C.

A2 - Bonabeau, E.W.

A2 - Cantu-Paz, E.

A2 - Dasgupta, D.

A2 - Deb, K.

A2 - et al, al

ER -

Sait SM, Sanaullah S, Zaidi AM, Ali MI. Comparative evaluation of parallelization strategies for evolutionary and stochastic heuristics. In Beyer HG, O'Reilly UM, Arnold D, Banzhaf W, Blum C, Bonabeau EW, Cantu-Paz E, Dasgupta D, Deb K, et al A, editors, GECCO 2005 - Genetic and Evolutionary Computation Conference. 2005. p. 921-922. (GECCO 2005 - Genetic and Evolutionary Computation Conference). doi: 10.1145/1068009.1068165

Comparative evaluation of parallelization strategies for evolutionary and stochastic heuristics

Abstract

Publication series

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this