CirrusPGA : a framework enabling automated cloud-based parallel genetic algorithms

Abstract

Problems deemed impractical to be solved using usual traditional algorithmic methods are abundant in real-world scenarios. These problems form a subset of the computational complexity class NP. A search and optimisation technique known as the Genetic Algorithm (GA) is one of many approaches that may be used in an attempt to nd a close approximate solution to one of these complex problems by drawing popular concepts from the eld of biology. Employing the Darwinist theory of evolution through natural selection, the Genetic Algorithm maintains a population-based environment in which solutions competitively evolve to better themselves. The distribution of this algorithm, exploiting methods of parallel computation, is known as the Parallel Genetic Algorithm (PGA). This nal year project presents the design and implementation of a framework and tool which facilitates the execution of the island model of Parallel Genetic Algorithms (PGAs), to solve a user-de ned problem, by enabling the deployment of a reusable environment to the domain of cloud computing. The deployment of the environment as well as the algorithm's design and problem de nition are made accessible through the use of a graphical user interface with the additional ability to customise several parameters. The framework also provides an additional functionality which may lead to continued study of the behaviour of island populations on the cloud. This is done by exposing details of the multiple populations' evolutionary progress at various stages throughout the problem-solving process. The Travelling Salesman Problem (TSP) was used as an example problem to evaluate the utilisation of the framework resulting in convergence to a close to, if not, optimum solution. Through this experimentation, it was seen that this project served as a good starting point with regards to the robustness, the autonomy and the problem-solving ability of such a framework.