Congratulations to George Mitchell

Congratulations to George Mitchell who successfully defended his thesis and will be awarded the degree of PhD.

The title of George's thesis is "Evolutionary Computation Applied to Combinatorial Optimisation Problems ".

He completed his PhD at the school of Electronic Engineering's Artificial Life research group while under the supervision of Professor Barry McMullin. The Artificial Life research group forms part of the Research Institute for Networks and Communications Engineering (RINCE), a national centre for excellence in Information and Communications Technology (ICT) based at Dublin City University.


Brief description of Project:
George's thesis addresses the issues associated with conventional genetic algorithms (GA) when applied to hard optimisation problems. In particular it examines the problem of selecting and implementing appropriate genetic operators in order to meet the validity constraints for constrained optimisation problems. The problem selected is the travelling salesman problem (TSP), a well known NP-hard problem.

Following a review of conventional genetic algorithms, this thesis advocates the use of a repair technique for genetic algorithms: GeneRepair. George evaluated the effectiveness of this operator against a wide range of benchmark problems and compare these results with conventional genetic algorithm approaches. A comparison between GeneRepair and the conventional GA approaches was made in two forms: firstly a handcrafted approach compared GAs without repair against those using GeneRepair. A second automated approach was then presented which utilises a meta-genetic algorithm to examine different configurations of operators and parameters. Through the use of a cost/benefit (Quality-Time Tradeoff) function, the user can balance the computational effort against the quality of the solution and thus allow the user to specify exactly what the cost benefit point should be for the search.

Results identified the optimal configuration settings for solving selected TSP problems. These results show that GeneRepair when used consistently generates very good TSP solutions in an extremely efficient manner, in both time and number of evaluations required.

There are many areas in which the finding of this work could be applied. The findings have definite applications in permutation based problems found in mathematics, engineering and computer science contexts. There are many other areas of high complexity ( e.g. Synthetic Biology) which at present are in the early stages of research. One factor which inhibits research in these areas is the cost of computation, this factor could be addressed through the use of the techniques discovered in the course of this work.