Please use this identifier to cite or link to this item:
Title: Distributed computation frameworks for solving optimisation problems
Authors: Galea, Etienne
Keywords: Evolutionary programming (Computer science)
Computer algorithms
Genetic algorithms
NP-complete problems
Issue Date: 2017
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.
Description: B.SC.IT(HONS)
Appears in Collections:Dissertations - FacICT - 2017

Files in This Item:
File Description SizeFormat 
  Restricted Access
2.8 MBAdobe PDFView/Open Request a copy

Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.