Repository logo
 
Publication

On asynchronous parallelization of order-based GA over grid-enabled heterogenous commodity hardware

dc.contributor.authorValente de Oliveira, JOSÉ
dc.contributor.authorBaltazar, Sérgio
dc.contributor.authorDaniel, Helder
dc.date.accessioned2019-11-20T15:07:15Z
dc.date.available2019-11-20T15:07:15Z
dc.date.issued2017-11
dc.description.abstractIn real-world applications, the runtime of genetic algorithms (GAs) can be computationally demanding, an issue that can be mitigated using parallelization. The study evaluates the parallelization of order-based GAs using the island model in an asynchronous heterogeneous computing environment. The island model allows for a considerable number of migration topologies. The study offers a systematic review of the studies on migration topologies and observes that no study is available yet on the performance of these migration topologies over asynchronous heterogeneous environments. Based on a statistical analysis of a comprehensive set of experiments, using real-world TSPLIB instances, the study researches the question: What is the fastest island model topology for order-based genetic algorithm, in an asynchronous distributed heterogeneous grid-enabled commodity computing environment, without losing significant fitness comparatively to the correspondent sequential panmictic implementation of the same algorithm?. Moreover, a new speedup index, the expected root speedup, is also proposed. A diversity of topology types and characteristics are considered: the single node, star, ring, cartwheel, rooted ordered tree, rooted full binary tree, coordinated tree-ring, and feedforward fully connected layered type. Different number of nodes are also considered. While some of the types of topologies are well known, the coordinated tree-ring topology is a novelty. These types of topologies allow us to assess three notable cases: (i) no migration (isolated island), (ii) migration toward the coordinator only, and (iii) migration flows to, and from, the coordinator.
dc.description.sponsorshipFCT-The Portuguese Board of Science and Technology [UID/MULTI/00631/2013 - CEOT]
dc.description.versioninfo:eu-repo/semantics/publishedVersion
dc.identifier.doi10.1007/s00500-016-2190-2
dc.identifier.issn1432-7643
dc.identifier.issn1433-7479
dc.identifier.urihttp://hdl.handle.net/10400.1/12949
dc.language.isoeng
dc.peerreviewedyes
dc.publisherSpringer
dc.subjectTraveling Salesman Problem
dc.subjectGenetic Algorithms
dc.subjectIsland Model
dc.subjectEvolutionary
dc.subjectCluster
dc.subjectImplementation
dc.titleOn asynchronous parallelization of order-based GA over grid-enabled heterogenous commodity hardware
dc.typejournal article
dspace.entity.typePublication
oaire.awardURIinfo:eu-repo/grantAgreement/FCT/5876/UID%2FMulti%2F00631%2F2013/PT
oaire.citation.endPage6368
oaire.citation.issue21
oaire.citation.startPage6351
oaire.citation.titleSoft Computing
oaire.citation.volume21
oaire.fundingStream5876
person.familyNameLUÍS VALENTE DE OLIVEIRA
person.familyNameBaltazar
person.familyNameDaniel
person.givenNameJOSÉ
person.givenNameSérgio
person.givenNameHelder
person.identifier.ciencia-id1F12-C1D3-7717
person.identifier.orcid0000-0001-5337-5699
person.identifier.orcid0000-0003-1270-0234
person.identifier.orcid0000-0002-4477-736X
project.funder.identifierhttp://doi.org/10.13039/501100001871
project.funder.nameFundação para a Ciência e a Tecnologia
rcaap.rightsrestrictedAccess
rcaap.typearticle
relation.isAuthorOfPublicationbb726e73-690c-4a33-822e-c47bdac3035b
relation.isAuthorOfPublication69408591-a742-4ac8-a18d-69c7bb050d5d
relation.isAuthorOfPublication414fdea2-ad8b-4ee8-8816-094a9802593a
relation.isAuthorOfPublication.latestForDiscoverybb726e73-690c-4a33-822e-c47bdac3035b
relation.isProjectOfPublication093114eb-daa5-4e3d-98ce-bebbf4dde4b8
relation.isProjectOfPublication.latestForDiscovery093114eb-daa5-4e3d-98ce-bebbf4dde4b8

Files

Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
On asynchronous parallelization - 12949.pdf
Size:
1.81 MB
Format:
Adobe Portable Document Format