Transcript Genetic Algorithms

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
Ant Colony Optimization




Pheromone Trail
Evaporation Rate
Effective for dynamically changing graphs
Useful for network routing and urban
transportation systems
3 Dimensions


Attempted Open GL with Pipe
Attempted Jogl



Java Bindings for OpenGl
Given Up
Work on Comparison of global search hueristics
Extensions




Finish my ant colony
optimization (ACO)
Brute Force Automated
Test
Particle Swarm
Optimization (PSO)
Neural Networking