Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Do you really want to delete this prezi?
Neither you, nor the coeditors you shared it with will be able to recover it again.
Make your likes visible on Facebook?
Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.
Transcript of dna-prezi-template
“Traveling salesman is a busy man.
So many places to go, so little time”
You've got a number of cities to visit
Distances between cities
Visit every place exactly once
Return to where you started
Work out the shortest route
A search technique used in computing to find approximate solutions to optimization and search problems.
- Global search heuristics
- Uses crossover and mutation operators using the
Developed: USA in the 1970s
Typically applied to: Discrete optimization
Attributed features: Good heuristic for
Representation (Encoding) of solution
Choose initial population
Evaluate the fitness of each individual in the population
Select best-ranking individuals to reproduce
Breed new generation through cross over and mutation (Genetic Operation) and give birth to offspring
Evaluate the individual fitness of the offspring
Replace worst ranked part of population with offspring
Until <terminating conditions>
Parent 1: F A B E C G D
Optimal solution for different number of cities
Performs a number of iterations, then the process is terminated and the best optimal tour is chosen.
For 23 cities, minimum distance is 1798.7
Good solutions for various problem sizes; depends on:
For a good solution,
a trade-off must be made between run-time and the solution quality
“Survival of the fittest”
- Emphasizes combining information from
good parents (crossover)
- Many variants eg. reproduction models,
Selects genes from parent chromosomes and
generates new offspring Crossover point is chosen
Operation makes random, but small, changes to an encoded solution
- all solutions into a local optimum
- extends the search space of the algorithm
Number of cities = 23
- the way the problem is encoded - which crossover and mutation methods are used
A number of genetic algorithm techniques have been analyzed and
surveyed for solving TSP
The research work can be extended for different hybrid selection,
crossover and mutation operators
Applications of GA include for advanced network models like
logistic network, task scheduling models, vehicle navigation
routing models etc.
On Solving Traveling Salesman Problems by Genetic Algorithms by Heinrich Braun
A Genetic Algorithm for solving Travelling Salesman Problem by Adewole Philip, Akinwale Adio
Taofiki and Otunbanowo Kehinde
To account that tour "A B C D E F G" is the same as "G F E D C B A",
We can store the links in both directions for each tour.
# Nearby cities
Nearby city odds %
initial number of random tours
percentage that each child after crossover will undergo mutation
percent chance the initial population will link to a nearby city
seed for the random number generator. Fixed - duplicate previous results
import city lists from XML files
each generation, no. of tours randomly chosen from the population
no. of cities close by which greedy GA uses to link cities
the no. of crossovers run before the algorithm is terminated
Replace repeated city with nearest city
Applying Genatic Algorithm for Travelling Salesman Problem