Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study
Identifieur interne : 003907 ( Main/Merge ); précédent : 003906; suivant : 003908Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study
Auteurs : Giuseppe A. Sena [États-Unis] ; Dalila Megherbi [États-Unis] ; Germinal Isern [États-Unis, Venezuela]Source :
- Future Generation Computer Systems [ 0167-739X ] ; 2001.
Abstract
A parallel version of a Genetic Algorithm (GA) is presented and implemented on a cluster of workstations. Even though our algorithm is general enough to be applied to a wide variety of problems, we used it to obtain optimal and/or suboptimal solutions to the well-known Traveling Salesman Problem. The proposed algorithm is implemented using the Parallel Virtual Machine (PVM) library over a network of workstations. A master–slave paradigm is used to implement the proposed parallel/distributed Genetic Algorithm (PDGA), which is based on a distributed-memory approach. Tests were performed with clusters of 1, 2, 4, 8, and 16 workstations, using several real problems and population sizes. Results are presented to show how the performance of the algorithm is affected by variations on the number of slaves, population size, mutation rate, and mutation interval. The results presented show the utility, versatility, efficiency and potential value of the proposed parallel and distributed Genetic Algorithm to tackle NP-complete problems of the same nature.
Url:
DOI: 10.1016/S0167-739X(99)00134-X
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000233
- to stream Istex, to step Curation: 000233
- to stream Istex, to step Checkpoint: 002896
Links to Exploration step
ISTEX:EB2CF7CFB3D01E1F69401F13C1B44AA2457F459DLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study</title><author><name sortKey="Sena, Giuseppe A" sort="Sena, Giuseppe A" uniqKey="Sena G" first="Giuseppe A." last="Sena">Giuseppe A. Sena</name></author><author><name sortKey="Megherbi, Dalila" sort="Megherbi, Dalila" uniqKey="Megherbi D" first="Dalila" last="Megherbi">Dalila Megherbi</name></author><author><name sortKey="Isern, Germinal" sort="Isern, Germinal" uniqKey="Isern G" first="Germinal" last="Isern">Germinal Isern</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:EB2CF7CFB3D01E1F69401F13C1B44AA2457F459D</idno><date when="2001" year="2001">2001</date><idno type="doi">10.1016/S0167-739X(99)00134-X</idno><idno type="url">https://api.istex.fr/document/EB2CF7CFB3D01E1F69401F13C1B44AA2457F459D/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000233</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000233</idno><idno type="wicri:Area/Istex/Curation">000233</idno><idno type="wicri:Area/Istex/Checkpoint">002896</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002896</idno><idno type="wicri:doubleKey">0167-739X:2001:Sena G:implementation:of:a</idno><idno type="wicri:Area/Main/Merge">003907</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study</title><author><name sortKey="Sena, Giuseppe A" sort="Sena, Giuseppe A" uniqKey="Sena G" first="Giuseppe A." last="Sena">Giuseppe A. Sena</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>College of Computer Science, Northeastern University, Boston, MA 02115</wicri:regionArea><placeName><region type="state">Massachusetts</region></placeName></affiliation><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Corresponding author. Present address: ON Technology Corporation, Cambridge, MA 02142</wicri:regionArea><placeName><region type="state">Massachusetts</region></placeName></affiliation><affiliation></affiliation></author><author><name sortKey="Megherbi, Dalila" sort="Megherbi, Dalila" uniqKey="Megherbi D" first="Dalila" last="Megherbi">Dalila Megherbi</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Division of Engineering, University of Denver, Denver, CO 80208</wicri:regionArea><placeName><region type="state">Colorado</region></placeName></affiliation></author><author><name sortKey="Isern, Germinal" sort="Isern, Germinal" uniqKey="Isern G" first="Germinal" last="Isern">Germinal Isern</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>College of Computer Science, Northeastern University, Boston, MA 02115</wicri:regionArea><placeName><region type="state">Massachusetts</region></placeName></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Venezuela</country><wicri:regionArea>1 On leave from GIRAS Group, Central University of Venezuela</wicri:regionArea><wicri:noRegion>Central University of Venezuela</wicri:noRegion></affiliation></author></analytic><monogr></monogr><series><title level="j">Future Generation Computer Systems</title><title level="j" type="abbrev">FUTURE</title><idno type="ISSN">0167-739X</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="2001">2001</date><biblScope unit="volume">17</biblScope><biblScope unit="issue">4</biblScope><biblScope unit="page" from="477">477</biblScope><biblScope unit="page" to="488">488</biblScope></imprint><idno type="ISSN">0167-739X</idno></series><idno type="istex">EB2CF7CFB3D01E1F69401F13C1B44AA2457F459D</idno><idno type="DOI">10.1016/S0167-739X(99)00134-X</idno><idno type="PII">S0167-739X(99)00134-X</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0167-739X</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">A parallel version of a Genetic Algorithm (GA) is presented and implemented on a cluster of workstations. Even though our algorithm is general enough to be applied to a wide variety of problems, we used it to obtain optimal and/or suboptimal solutions to the well-known Traveling Salesman Problem. The proposed algorithm is implemented using the Parallel Virtual Machine (PVM) library over a network of workstations. A master–slave paradigm is used to implement the proposed parallel/distributed Genetic Algorithm (PDGA), which is based on a distributed-memory approach. Tests were performed with clusters of 1, 2, 4, 8, and 16 workstations, using several real problems and population sizes. Results are presented to show how the performance of the algorithm is affected by variations on the number of slaves, population size, mutation rate, and mutation interval. The results presented show the utility, versatility, efficiency and potential value of the proposed parallel and distributed Genetic Algorithm to tackle NP-complete problems of the same nature.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/TelematiV1/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 003907 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 003907 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= TelematiV1
|flux= Main
|étape= Merge
|type= RBID
|clé= ISTEX:EB2CF7CFB3D01E1F69401F13C1B44AA2457F459D
|texte= Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study
}}
| This area was generated with Dilib version V0.6.31. |  |