Title
A hardware implementation of a traveling salesman problem using genetic algorithm with migration
Date of Award
2013
Document Type
Thesis
Degree Name
Master of Science in Engineering (MSE)
Department
Electrical and Computer Engineering
Committee Chair
B. Earl Wells
Committee Member
Fat D. Ho
Committee Member
S. M. Yoo
Subject(s)
Traveling salesman problem., Combinatorial optimization.
Abstract
In this thesis, a genetic algorithm is employed to solve the Traveling Salesman Problem by utilizing reconfigurable hardware's speed, regular structure, and ability to quickly modify design elements to overcome unacceptable delays found in software optimizations. These delays are a result of the genetic algorithm's complexity. This thesis expands upon previous hardware implementations, adapting them to today's reconfigurable hardware. Exploiting the fine grain parallelization capabilities of hardware in specific areas of the algorithm is shown to provide decreased execution time. Allowing multiple simultaneously running genetic algorithms to communicate with each other's subpopulation through a migration operator exploits the hardware's coarse grain parallelization capabilities resulting in more accurate solutions. These parallelization techniques, however, add to resource costs and their tradeoffs and benefits are evaluated to determine the feasibility of these parallelization techniques.
Recommended Citation
Mintz, Jessica, "A hardware implementation of a traveling salesman problem using genetic algorithm with migration" (2013). Theses. 34.
https://louis.uah.edu/uah-theses/34