Genetic algorithms for the traveling salesman problem using edge assembly crossovers

The central issue in creating new genetic algorithms is the algorithm's crossover method. My focus is on a particular crossover known as the Edge Assembly Crossover, or EAX, by Nagata and Kobayashi. The basics of a what make up a genetic algorithm is reviewed. The traveling salesman problem is defined. The EAX as an algorithm within an algorithm is explained. The crossover's implementation is original and is listed. The use of the graphic user interface, TSP View, used to run algorithms is explained as well as the extensions to the interface that were implemented for this study. The results of running a genetic algorithm using the EAX against traveling salesman problems, with a focus on ATT532, is discussed and compared to runs using other optimization algorithms. The question of why EAX works is addressed with conjectures for a possible future research path.

Name thesis:degree_name

Master of Science (MS)

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

University of Nevada, Las Vegas

Year

2003

Author dc:creator

• Seppala, Dwain Alan

Contributors dc:contributor

• Wolfgang Bein

Statement dc:rights

• IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Language dc:language

English

Identifier

https://oasis.library.unlv.edu/rtds/1542

OAI identifier oai:identifier

oai:oasis.library.unlv.edu:rtds-2541