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

Approaching TSP; A comparison & Implementation of multiple heuristics

Presentation by Abdul Mannan
by

Abdul Mannan Akhtar

on 20 March 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Approaching TSP; A comparison & Implementation of multiple heuristics

Approaching TSP
A comparison & implementation of multiple heuristics
Abdul Mannan Akhtar
Haris Mahmood
Abdul Hadi Syed
Rushan Qaisrani

?
What is TSP
SEECS ACM Student Chapter ...
SACM ?
Analysis & Comparison
Q
&
A
?
One does not simply walk from city to city!
T
S
P
ravelling
alesman
roblem
shortest path
cover cities
no repetition
Properties
NP hard
Applications
Simulated annealing
Tabu Search
Ant Algorithm
Linear programming
Genetic Algorithm
Hill climbing
Nearest neighbor search
Nearest Neighbor
Abdul Hadi Syed
Strategy
Starting Temperature
Simulated Annealing
Rushan Qaisrani
Biology 101
Genetic Algorithm
Haris Mahmood
“Solution to a problem solved by Genetic Algorithms is

evolved"
Chromosomes
Genes
Mutation
Crossover
Implementation
of GA
on

TSP
Annealing
Temperature Parameter
Explore parameter space.
Restrict exploration
minimization procedure
At high temperature
At lower temperature
Simulated
Annealing
The Cooling Schedule
Temperature Decrement
Iterations at each temperature
Final Temperature
Algorithm
one of the algorithm
Pioneer
TSP
Explanation
Algorithm & Example
Abdul Mannan Akhtar
Heuristic
Comparison
GA
Comparison
29
48
70
101
Cities
c = the change in the evaluation function
t = the current temperature
r = a random number between 0 and 1
P = exp(-c/t) > r
Acceptance Criteria
Exact Algorithm
NP hard
infinite iterations
Heuristics
Full transcript