MSc Math Defence: Analyzing the effectiveness of different parameter optimization techniques for complex genetic algorithms

CANDIDATE:  THOMAS KIELSTRA

ABSTRACT:

This thesis attempts to determine whether a modified version of the genetic algorithm developed by Ashlocket al. (2014) could be used to create graphs that are hard to colour for graph colouring algorithms, specifically the random sort (RS) method. In order to determine whether or not this is possible, an optimal parameter setting for the genetic algorithm must be obtained. The appropriate population size, iteration number and mutation number was determined using a uniform chromosomal regulatory sequence. This thesis then analysed the edit commands of the chromosomal regulatory sequence to determine general characteristics that could be used to optimize the chromosomal regulatory sequence. Modified versions of particle swarm optimization and differential evolution were also used to try to optimize the chromosomal regulatory sequence. This thesis shows that even though the edit commands do have some general characteristics, it is ineffective to use these characteristics to optimize the genetic algorithm. Both particle swarm optimization and differential evolution are effective at optimizing the genetic algorithm given appropriate conditions. The genetic algorithm appears to be effective at finding hard to colour graphs for the RS method. This genetic algorithm could be used to create graphs for other graph colouring algorithms. This thesis suggests modifications that could be made to the genetic algorithm based on some the edit commands’ general characteristics.