Open AccessParallel Genetic Algorithms with Dynamic Topology using Cluster Computing
Author(s) -
Nihat Adar,
Gültekin Kuvat
Publication year - 2016
Publication title -
advances in electrical and computer engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.254
H-Index - 23
eISSN - 1844-7600
pISSN - 1582-7445
DOI - 10.4316/aece.2016.03011
Subject(s) - computer science , cluster (spacecraft) , topology (electrical circuits) , computer cluster , genetic algorithm , algorithm , parallel computing , distributed computing , theoretical computer science , mathematics , computer network , machine learning , combinatorics
A parallel genetic algorithm (PGA) conducts a distributed meta-heuristic search by employing genetic algorithms on more than one subpopulation simultaneously. PGAs migrate a number of individuals between subpopulations over generations. The layout that facilitates the interactions of the subpopulations is called the topology. Static migration topologies have been widely incorporated into PGAs. In this article, a PGA with a dynamic migration topology (D-PGA) is proposed. D-PGA generates a new migration topology in every epoch based on the average fitness values of the subpopulations. The D-PGA has been tested against ring and fully connected migration topologies in a Beowulf Cluster. The D-PGA has outperformed the ring migration topology with comparable communication cost and has provided competitive or better results than a fully connected migration topology with significantly lower communication cost. PGA convergence behaviors have been analyzed in terms of the diversities within and between subpopulations. Conventional diversity can be considered as the diversity within a subpopulation. A new concept of permeability has been introduced to measure the diversity between subpopulations. It is shown that the success of the proposed D-PGA can be attributed to maintaining a high level of permeability while preserving diversity within subpopulations