The Internet belongs to everyone. Let’s keep it that way.

Protect Net Neutrality

Present Remotely

Send the link below via email or IM

• 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

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

dna-prezi-template

null
by

Syed Ahamed

on 27 March 2014

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

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
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,

“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
routing models etc.

Presented by,

Sumithra Pandiaraj
Yamini Papudesi
Shubhalakshmi Shetty
Hariharan Jayaraman

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