Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start 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.

DeleteCancel

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.

No, thanks

dna-prezi-template

null
by

Syed Ahamed

on 27 March 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of dna-prezi-template

Traveling Salesman Problem(TSP) using Genetic Algorithm
“Traveling salesman is a busy man.
So many places to go, so little time”
GA Approach
PROBLEM

:

You've got a number of cities to visit

GIVEN

:

Distances between cities

CONSTRAINTS

:

Visit every place exactly once
Return to where you started

OPTIMAL SOLUTION:

Work out the shortest route


HOW?

GENETIC ALGORITHM

GENETIC ALGORITHM


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
principle

GA Overview

Developed: USA in the 1970s
Typically applied to: Discrete optimization
Attributed features: Good heuristic for
combinatorial problems


GA OPERATORS
Chromosomes

Representation (Encoding) of solution




GA Pseudo-Code
Choose initial population

Evaluate the fitness of each individual in the population

Repeat

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>
Example
Parent 1: F A B E C G D
EXAMPLE CASE
Optimal solution for different number of cities
randomly placed
EXPERIMENTAL RESULT
REFERENCES
http://www-public.it-sudparis.eu/~gibson/Teaching/CSC4504/ReadingMaterial/Braun91.pdf
CONCLUSIONS
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”
Special features:

- Emphasizes combining information from
good parents (crossover)
- Many variants eg. reproduction models,
operators
Crossover

Selects genes from parent chromosomes and
generates new offspring Crossover point is chosen
randomly


Mutation

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
Parameters:
- the way the problem is encoded - which crossover and mutation methods are used
FUTURE WORK

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.

Presented by,

Sumithra Pandiaraj
Yamini Papudesi
Shubhalakshmi Shetty
Hariharan Jayaraman

http://thesai.org/Downloads/Volume2No1/Paper%204-A%20Genetic%20Algorithm%20for%20Solving%20Travelling%20Salesman%20Problem.pdf
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.


ECE 602
Population Size
Mutation %
Group Size
Maximum Generations
# Nearby cities
Nearby city odds %
Random Seed
City list
Parameters:
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
Crossover Problem
Replace repeated city with nearest city
http://www.theprojectspot.com/tutorial-post/pplying a-genetic-algorithm-to-the-travelling-salesman-problem/5
Applying Genatic Algorithm for Travelling Salesman Problem
Full transcript