In 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 sys- tematic 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 comprehen-sive 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 com-modity computing environment, without losing significant fitness comparatively to the correspondent sequential pan- mictic implementation of the same algorithm?. Moreover,
a new speedup index, the expected root speedup, is also proposed. A diversity of topology types and characteris- tics 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 topol- ogy 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.

EB00000002916K

Available