Author

Jessica Mintz

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.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.