Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study
Identifieur interne : 000233 ( Istex/Corpus ); précédent : 000232; suivant : 000234Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study
Auteurs : Giuseppe A. Sena ; Dalila Megherbi ; Germinal IsernSource :
- 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 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>
<affiliation><mods:affiliation>College of Computer Science, Northeastern University, Boston, MA 02115, USA</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>Corresponding author. Present address: ON Technology Corporation, Cambridge, MA 02142, USA</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>E-mail: tsena@on.com</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Megherbi, Dalila" sort="Megherbi, Dalila" uniqKey="Megherbi D" first="Dalila" last="Megherbi">Dalila Megherbi</name>
<affiliation><mods:affiliation>Division of Engineering, University of Denver, Denver, CO 80208, USA</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Isern, Germinal" sort="Isern, Germinal" uniqKey="Isern G" first="Germinal" last="Isern">Germinal Isern</name>
<affiliation><mods:affiliation>College of Computer Science, Northeastern University, Boston, MA 02115, USA</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>1 On leave from GIRAS Group, Central University of Venezuela, Venezuela.</mods:affiliation>
</affiliation>
</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>
</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><mods:affiliation>College of Computer Science, Northeastern University, Boston, MA 02115, USA</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>Corresponding author. Present address: ON Technology Corporation, Cambridge, MA 02142, USA</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>E-mail: tsena@on.com</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Megherbi, Dalila" sort="Megherbi, Dalila" uniqKey="Megherbi D" first="Dalila" last="Megherbi">Dalila Megherbi</name>
<affiliation><mods:affiliation>Division of Engineering, University of Denver, Denver, CO 80208, USA</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Isern, Germinal" sort="Isern, Germinal" uniqKey="Isern G" first="Germinal" last="Isern">Germinal Isern</name>
<affiliation><mods:affiliation>College of Computer Science, Northeastern University, Boston, MA 02115, USA</mods:affiliation>
</affiliation>
<affiliation><mods:affiliation>1 On leave from GIRAS Group, Central University of Venezuela, Venezuela.</mods:affiliation>
</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>
<istex><corpusName>elsevier</corpusName>
<author><json:item><name>Giuseppe A. Sena</name>
<affiliations><json:string>College of Computer Science, Northeastern University, Boston, MA 02115, USA</json:string>
<json:string>Corresponding author. Present address: ON Technology Corporation, Cambridge, MA 02142, USA</json:string>
<json:string>E-mail: tsena@on.com</json:string>
</affiliations>
</json:item>
<json:item><name>Dalila Megherbi</name>
<affiliations><json:string>Division of Engineering, University of Denver, Denver, CO 80208, USA</json:string>
</affiliations>
</json:item>
<json:item><name>Germinal Isern</name>
<affiliations><json:string>College of Computer Science, Northeastern University, Boston, MA 02115, USA</json:string>
<json:string>1 On leave from GIRAS Group, Central University of Venezuela, Venezuela.</json:string>
</affiliations>
</json:item>
</author>
<subject><json:item><lang><json:string>eng</json:string>
</lang>
<value>Genetic Algorithm</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Parallel computing</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Distributed system</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Message-passing</value>
</json:item>
<json:item><lang><json:string>eng</json:string>
</lang>
<value>Traveling Salesman Problem</value>
</json:item>
</subject>
<language><json:string>eng</json:string>
</language>
<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.</abstract>
<qualityIndicators><score>6.908</score>
<pdfVersion>1.2</pdfVersion>
<pdfPageSize>612 x 792 pts (letter)</pdfPageSize>
<refBibsNative>true</refBibsNative>
<keywordCount>5</keywordCount>
<abstractCharCount>1058</abstractCharCount>
<pdfWordCount>5724</pdfWordCount>
<pdfCharCount>33455</pdfCharCount>
<pdfPageCount>12</pdfPageCount>
<abstractWordCount>159</abstractWordCount>
</qualityIndicators>
<title>Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study</title>
<pii><json:string>S0167-739X(99)00134-X</json:string>
</pii>
<genre><json:string>research-article</json:string>
</genre>
<host><volume>17</volume>
<pii><json:string>S0167-739X(00)X0032-5</json:string>
</pii>
<editor><json:item><name>Albert Y.Zomaya</name>
</json:item>
<json:item><name>Fikret Ercal</name>
</json:item>
<json:item><name>Stephan Olariu</name>
</json:item>
</editor>
<pages><last>488</last>
<first>477</first>
</pages>
<conference><json:item><name>Workshop on Bio-inspired Solutions to Parallel Computing problems, San Juan, Puerto Rico BioSP3</name>
</json:item>
</conference>
<issn><json:string>0167-739X</json:string>
</issn>
<issue>4</issue>
<genre><json:string>Journal</json:string>
</genre>
<language><json:string>unknown</json:string>
</language>
<title>Future Generation Computer Systems</title>
<publicationDate>2001</publicationDate>
</host>
<categories><wos><json:string>COMPUTER SCIENCE, THEORY & METHODS</json:string>
</wos>
</categories>
<publicationDate>2001</publicationDate>
<copyrightDate>2001</copyrightDate>
<doi><json:string>10.1016/S0167-739X(99)00134-X</json:string>
</doi>
<id>EB2CF7CFB3D01E1F69401F13C1B44AA2457F459D</id>
<score>1</score>
<fulltext><json:item><original>true</original>
<mimetype>application/pdf</mimetype>
<extension>pdf</extension>
<uri>https://api.istex.fr/document/EB2CF7CFB3D01E1F69401F13C1B44AA2457F459D/fulltext/pdf</uri>
</json:item>
<json:item><original>true</original>
<mimetype>text/plain</mimetype>
<extension>txt</extension>
<uri>https://api.istex.fr/document/EB2CF7CFB3D01E1F69401F13C1B44AA2457F459D/fulltext/txt</uri>
</json:item>
<json:item><original>false</original>
<mimetype>application/zip</mimetype>
<extension>zip</extension>
<uri>https://api.istex.fr/document/EB2CF7CFB3D01E1F69401F13C1B44AA2457F459D/fulltext/zip</uri>
</json:item>
<istex:fulltextTEI uri="https://api.istex.fr/document/EB2CF7CFB3D01E1F69401F13C1B44AA2457F459D/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study</title>
</titleStmt>
<publicationStmt><authority>ISTEX</authority>
<publisher>ELSEVIER</publisher>
<availability><p>ELSEVIER</p>
</availability>
<date>2001</date>
</publicationStmt>
<notesStmt><note type="content">Fig. 1: PDGA: General design.</note>
<note type="content">Fig. 2: PDGA: MASTER task.</note>
<note type="content">Fig. 3: PDGA: SLAVE task.</note>
<note type="content">Fig. 4: Execution time as a function of the number of SLAVE tasks used and the population size.</note>
<note type="content">Fig. 5: Number of generations as a function of the number of SLAVE tasks used.</note>
<note type="content">Fig. 6: Effect of the mutation interval (mut_int) on the PDGA.</note>
<note type="content">Fig. 7: Effect of the mutation rate (m) on the PDGA.</note>
</notesStmt>
<sourceDesc><biblStruct type="inbook"><analytic><title level="a">Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study</title>
<author><persName><forename type="first">Giuseppe A.</forename>
<surname>Sena</surname>
</persName>
<email>tsena@on.com</email>
<affiliation>College of Computer Science, Northeastern University, Boston, MA 02115, USA</affiliation>
<affiliation>Corresponding author. Present address: ON Technology Corporation, Cambridge, MA 02142, USA</affiliation>
</author>
<author><persName><forename type="first">Dalila</forename>
<surname>Megherbi</surname>
</persName>
<affiliation>Division of Engineering, University of Denver, Denver, CO 80208, USA</affiliation>
</author>
<author><persName><forename type="first">Germinal</forename>
<surname>Isern</surname>
</persName>
<affiliation>College of Computer Science, Northeastern University, Boston, MA 02115, USA</affiliation>
<affiliation>1 On leave from GIRAS Group, Central University of Venezuela, Venezuela.</affiliation>
</author>
</analytic>
<monogr><title level="j">Future Generation Computer Systems</title>
<title level="j" type="abbrev">FUTURE</title>
<idno type="pISSN">0167-739X</idno>
<idno type="PII">S0167-739X(00)X0032-5</idno>
<meeting><addName>Workshop on Bio-inspired Solutions to Parallel Computing problems, San Juan, Puerto Rico</addName>
<addName>BioSP3</addName>
</meeting>
<editor><persName>Albert Y.Zomaya</persName>
</editor>
<editor><persName>Fikret Ercal</persName>
</editor>
<editor><persName>Stephan Olariu</persName>
</editor>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="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>
</monogr>
<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>
</fileDesc>
<profileDesc><creation><date>2001</date>
</creation>
<langUsage><language ident="en">en</language>
</langUsage>
<abstract xml:lang="en"><p>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.</p>
</abstract>
<textClass><keywords scheme="keyword"><list><head>Keywords</head>
<item><term>Genetic Algorithm</term>
</item>
<item><term>Parallel computing</term>
</item>
<item><term>Distributed system</term>
</item>
<item><term>Message-passing</term>
</item>
<item><term>Traveling Salesman Problem</term>
</item>
</list>
</keywords>
</textClass>
</profileDesc>
<revisionDesc><change when="2001">Published</change>
</revisionDesc>
</teiHeader>
</istex:fulltextTEI>
</fulltext>
<metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: ce:floats; body; tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration>
<istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"><istex:entity SYSTEM="gr1" NDATA="IMAGE" name="gr1"></istex:entity>
<istex:entity SYSTEM="gr2" NDATA="IMAGE" name="gr2"></istex:entity>
<istex:entity SYSTEM="gr3" NDATA="IMAGE" name="gr3"></istex:entity>
<istex:entity SYSTEM="gr4" NDATA="IMAGE" name="gr4"></istex:entity>
<istex:entity SYSTEM="gr5" NDATA="IMAGE" name="gr5"></istex:entity>
<istex:entity SYSTEM="gr6" NDATA="IMAGE" name="gr6"></istex:entity>
<istex:entity SYSTEM="gr7" NDATA="IMAGE" name="gr7"></istex:entity>
<istex:entity SYSTEM="fx1" NDATA="IMAGE" name="fx1"></istex:entity>
<istex:entity SYSTEM="fx2" NDATA="IMAGE" name="fx2"></istex:entity>
<istex:entity SYSTEM="fx3" NDATA="IMAGE" name="fx3"></istex:entity>
</istex:docType>
<istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>FUTURE</jid>
<aid>745</aid>
<ce:pii>S0167-739X(99)00134-X</ce:pii>
<ce:doi>10.1016/S0167-739X(99)00134-X</ce:doi>
<ce:copyright type="unknown" year="2001"></ce:copyright>
</item-info>
<head><ce:title>Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study</ce:title>
<ce:author-group><ce:author biographyid="VT1"><ce:given-name>Giuseppe A.</ce:given-name>
<ce:surname>Sena</ce:surname>
<ce:cross-ref refid="AFF1"><ce:sup>a</ce:sup>
</ce:cross-ref>
<ce:cross-ref refid="CORR1">*</ce:cross-ref>
<ce:e-address>tsena@on.com</ce:e-address>
</ce:author>
<ce:author biographyid="VT2"><ce:given-name>Dalila</ce:given-name>
<ce:surname>Megherbi</ce:surname>
<ce:cross-ref refid="AFF2"><ce:sup>b</ce:sup>
</ce:cross-ref>
</ce:author>
<ce:author biographyid="VT3"><ce:given-name>Germinal</ce:given-name>
<ce:surname>Isern</ce:surname>
<ce:cross-ref refid="FN1"><ce:sup>1</ce:sup>
</ce:cross-ref>
<ce:cross-ref refid="AFF1"><ce:sup>a</ce:sup>
</ce:cross-ref>
</ce:author>
<ce:affiliation id="AFF1"><ce:label>a</ce:label>
<ce:textfn>College of Computer Science, Northeastern University, Boston, MA 02115, USA</ce:textfn>
</ce:affiliation>
<ce:affiliation id="AFF2"><ce:label>b</ce:label>
<ce:textfn>Division of Engineering, University of Denver, Denver, CO 80208, USA</ce:textfn>
</ce:affiliation>
<ce:correspondence id="CORR1"><ce:label>*</ce:label>
<ce:text>Corresponding author. Present address: ON Technology Corporation, Cambridge, MA 02142, USA</ce:text>
</ce:correspondence>
<ce:footnote id="FN1"><ce:label>1</ce:label>
<ce:note-para>On leave from GIRAS Group, Central University of Venezuela, Venezuela.</ce:note-para>
</ce:footnote>
</ce:author-group>
<ce:abstract><ce:section-title>Abstract</ce:section-title>
<ce:abstract-sec><ce:simple-para>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.</ce:simple-para>
</ce:abstract-sec>
</ce:abstract>
<ce:keywords class="keyword"><ce:section-title>Keywords</ce:section-title>
<ce:keyword><ce:text>Genetic Algorithm</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Parallel computing</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Distributed system</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Message-passing</ce:text>
</ce:keyword>
<ce:keyword><ce:text>Traveling Salesman Problem</ce:text>
</ce:keyword>
</ce:keywords>
</head>
</converted-article>
</istex:document>
</istex:metadataXml>
<mods version="3.6"><titleInfo><title>Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study</title>
</titleInfo>
<titleInfo type="alternative" contentType="CDATA"><title>Implementation of a parallel Genetic Algorithm on a cluster of workstations: Traveling Salesman Problem, a case study</title>
</titleInfo>
<name type="personal"><namePart type="given">Giuseppe A.</namePart>
<namePart type="family">Sena</namePart>
<affiliation>College of Computer Science, Northeastern University, Boston, MA 02115, USA</affiliation>
<affiliation>Corresponding author. Present address: ON Technology Corporation, Cambridge, MA 02142, USA</affiliation>
<affiliation>E-mail: tsena@on.com</affiliation>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<name type="personal"><namePart type="given">Dalila</namePart>
<namePart type="family">Megherbi</namePart>
<affiliation>Division of Engineering, University of Denver, Denver, CO 80208, USA</affiliation>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<name type="personal"><namePart type="given">Germinal</namePart>
<namePart type="family">Isern</namePart>
<affiliation>College of Computer Science, Northeastern University, Boston, MA 02115, USA</affiliation>
<affiliation>1 On leave from GIRAS Group, Central University of Venezuela, Venezuela.</affiliation>
<role><roleTerm type="text">author</roleTerm>
</role>
</name>
<typeOfResource>text</typeOfResource>
<genre type="research-article" displayLabel="Full-length article"></genre>
<originInfo><publisher>ELSEVIER</publisher>
<dateIssued encoding="w3cdtf">2001</dateIssued>
<copyrightDate encoding="w3cdtf">2001</copyrightDate>
</originInfo>
<language><languageTerm type="code" authority="iso639-2b">eng</languageTerm>
<languageTerm type="code" authority="rfc3066">en</languageTerm>
</language>
<physicalDescription><internetMediaType>text/html</internetMediaType>
</physicalDescription>
<abstract 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.</abstract>
<note type="content">Fig. 1: PDGA: General design.</note>
<note type="content">Fig. 2: PDGA: MASTER task.</note>
<note type="content">Fig. 3: PDGA: SLAVE task.</note>
<note type="content">Fig. 4: Execution time as a function of the number of SLAVE tasks used and the population size.</note>
<note type="content">Fig. 5: Number of generations as a function of the number of SLAVE tasks used.</note>
<note type="content">Fig. 6: Effect of the mutation interval (mut_int) on the PDGA.</note>
<note type="content">Fig. 7: Effect of the mutation rate (m) on the PDGA.</note>
<subject><genre>Keywords</genre>
<topic>Genetic Algorithm</topic>
<topic>Parallel computing</topic>
<topic>Distributed system</topic>
<topic>Message-passing</topic>
<topic>Traveling Salesman Problem</topic>
</subject>
<relatedItem type="host"><titleInfo><title>Future Generation Computer Systems</title>
</titleInfo>
<titleInfo type="abbreviated"><title>FUTURE</title>
</titleInfo>
<name type="conference"><namePart>Workshop on Bio-inspired Solutions to Parallel Computing problems, San Juan, Puerto Rico</namePart>
<namePart>BioSP3</namePart>
</name>
<name type="personal"><namePart>Albert Y.Zomaya</namePart>
<role><roleTerm type="text">editor</roleTerm>
</role>
</name>
<name type="personal"><namePart>Fikret Ercal</namePart>
<role><roleTerm type="text">editor</roleTerm>
</role>
</name>
<name type="personal"><namePart>Stephan Olariu</namePart>
<role><roleTerm type="text">editor</roleTerm>
</role>
</name>
<genre type="Journal">journal</genre>
<originInfo><dateIssued encoding="w3cdtf">200101</dateIssued>
</originInfo>
<identifier type="ISSN">0167-739X</identifier>
<identifier type="PII">S0167-739X(00)X0032-5</identifier>
<part><date>200101</date>
<detail type="issue"><title>Workshop on Bio-inspired Solutions to Parallel Computing problems, San Juan, Puerto Rico</title>
</detail>
<detail type="volume"><number>17</number>
<caption>vol.</caption>
</detail>
<detail type="issue"><number>4</number>
<caption>no.</caption>
</detail>
<extent unit="issue pages"><start>335</start>
<end>500</end>
</extent>
<extent unit="pages"><start>477</start>
<end>488</end>
</extent>
</part>
</relatedItem>
<identifier type="istex">EB2CF7CFB3D01E1F69401F13C1B44AA2457F459D</identifier>
<identifier type="DOI">10.1016/S0167-739X(99)00134-X</identifier>
<identifier type="PII">S0167-739X(99)00134-X</identifier>
<recordInfo><recordContentSource>ELSEVIER</recordContentSource>
</recordInfo>
</mods>
</metadata>
<serie></serie>
</istex>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/TelematiV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000233 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000233 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Ticri/CIDE |area= TelematiV1 |flux= Istex |étape= Corpus |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. | ![]() |