Comparison of Crossover and Diversity-Maintaining Operators in Randomized Search Heuristics |
| | Abstract | In this project a comparison of crossover and diversity-maintaining operators in randomized search heuristics is performed on the Traveling Salesman Problem (TSP).
Through a literature study, an initial overview of the eld is provided. Basic original operators and more advanced operators are described. Theoretical results affecting the field are presented.
A framework for solving TSP solutions and testing TSP-solvers is implemented. Three operators are then selected, based on the literature study, implemented and thoroughly tested on problems from the TSP-Lib online library. An analysis of the results and findings from these tests, combined with the literature study is used to summarize the current state of the art of the field, and present some future design principles of algorithms in the field. It is found that the traditional pure genetic algorithms are not feasible in order to obtain good performance for solving TSPs. Hybrid algorithms focusing on combining the best properties of crossover with the properties of local search heuristics are the current state-of-the-art of 'genetic algorithms' and has shown the potential to improve solutions obtained by the state-of-the-art algorithms for solving TSPs.
Diversity maintaining mechanisms are found to be important, however the use of a simple injection strategy did not by itself provide an increase in fitness of the solutions obtained.
Four guidelines for future design of hybrid algorithms/crossover-operators in the field, is to have the crossover operator respect the principles of alleles transmission and respectfulnes, to use an e fficient local search heuristic, to use some diversity maintaining scheme and to use an operator capable of exploration. | | Type | Master's thesis [Academic thesis] | | Year | 2014 | | Publisher | Technical University of Denmark, Department of Applied Mathematics and Computer Science | | Address | Richard Petersens Plads, Building 324, DK-2800 Kgs. Lyngby, Denmark, compute@compute.dtu.dk | | Series | DTU Compute M.Sc.-2014 | | Note | DTU supervisor: Carsten Witt, cawi@dtu.dk, DTU Compute | | Electronic version(s) | [pdf] | | Publication link | http://www.compute.dtu.dk/English.aspx | | BibTeX data | [bibtex] | | IMM Group(s) | Computer Science & Engineering |
|