Browse DORAS
Browse Theses
Latest Additions
Creative Commons License
Except where otherwise noted, content on this site is licensed for use under a:

Evolutionary computation applied to combinatorial optimisation problems

Mitchell, George G. (2007) Evolutionary computation applied to combinatorial optimisation problems. PhD thesis, Dublin City University.

Full text available as:

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


This 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. We evaluate 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 is made in two forms: firstly a handcrafted approach compares GAs without repair against those using GeneRepair. A second automated approach is then presented. This meta-genetic algorithm examines 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 have identified the optimal configuration settings for solving selected TSP problems. These results show that GeneRepair when used consistently generates very good TSP solutions for 50, 70 and 100 city problems. GeneRepair assists in finding TSP solutions in an extremely efficient manner, in both time and number of evaluations required.

Item Type:Thesis (PhD)
Date of Award:November 2007
Supervisor(s):McMullin, Barry
Subjects:Computer Science > Artificial intelligence
Computer Science > Algorithms
DCU Faculties and Centres:DCU Faculties and Schools > Faculty of Engineering and Computing > School of Electronic Engineering
Use License:This item is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 3.0 License. View License
ID Code:93
Deposited On:13 Dec 2007 by DORAS Administrator. Last Modified 30 Jan 2009 14:28

Download statistics

Archive Staff Only: edit this record