Metaheuristics and combinatorial optimization problems

Show full item record

Title: Metaheuristics and combinatorial optimization problems
Author: Skidmore, Gerald
Abstract: This thesis will use the traveling salesman problem (TSP) as a tool to help present and investigate several new techniques that improve the overall performance of genetic algorithms (GA). Improvements include a new parent selection algorithm, harem select, that outperforms all other parent selection algorithms tested, some by up to 600%. Other techniques investigated include population seeding, random restart, heuristic crossovers, and hybrid genetic algorithms, all of which posted improvements in the range of 1% up to 1100%. Also studied will be a new algorithm, GRASP, that is just starting to enjoy a lot of interest in the research community and will also been applied to the traveling salesman problem (TSP). Given very little time to run, relative to other popular metaheuristic algorithms, GRASP was able to come within 5% of optimal on several of the TSPLIB maps used for testing. Both the GA and the GRASP algorithms will be compared with commonly used metaheuristic algorithms such as simulated annealing (SA) and reactive tabu search (RTS) as well as a simple neighborhood search - greedy search.
Record URI: http://hdl.handle.net/1850/2319
Date: 2006

Files in this item

Files Size Format View
GSkidmoreThesis08-2006.pdf 595.8Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse