Distributed computation frameworks for solving optimisation problems

Abstract

Evolutionary algorithms are extremely efficacious at finding near-optimal solutions for NP-Complete problems. However, complex combinatorial problems often demand high processing power which most of the time is unavailable to the ordinary public. A Genetic Algorithm (GA) is a well-known stochastic-based search and optimisation technique that attempts to find a solution through automated trial-and-improvement. By simulating the process of natural selection, chromosomes compete against each other in a continuously evolving population to arrive at an approximately optimum solution for the problem. By executing genetic algorithms onto several loosely-coupled machines, a parallel solution (PGA) can be employed to significantly reduce the time necessary for obtaining a near-optimal solution. With the utilisation of the EASEA framework connected in a Beowulf-style cluster much like in a school or office, serial and parallel genetic algorithms were applied to the combinatorial optimisation packing problem, known as the knapsack problem. Results generated from this study determined that while time was dramatically decreased when using a parallel genetic algorithm, solution quality did not degrade when comparing it to a serial genetic algorithm with the same number of evaluations.