Transcript Dark Blue with Orange

Genetic Algorithms and TSP
Thomas Jefferson Computer Research Project
by Karl Leswing
Genetic Algorithms



Effective in Optimization Problems
Classified as a global search heuristic
Inspired by Evolutionary Biology




Inheritance
Mutation
Selection
Crossover
Traveling Salesman

Given a number of
cities and the costs of
traveling from any city
to any other city, what
is the cheapest roundtrip rout that visits each
city exactly once and
then returns to the
starting city.
Traveling Salesman Continued



O(N!)
Dynamic Programming down to O((n^2)*2^n)
Find Near Optimal Solutions
Current Work
Current Work Continued


Double Point Crossover
Roulette Selection


Single Point Mutation


Unique Fitness Algorithm
Mutation Rate Variable
Effectiveness

Solve 50 City TSP in less than one minute
Extensions

Selections




Matrix Encoding
Mutations



Double Point
Cycle
3 Dimension


Tournament
Elitism
Open GL
Weighted Paths