Scribd
Upload
47 views19 pages

Travelling Salesman Problem Using Genetic Algorithm: Faculty

The document discusses using a genetic algorithm to solve the traveling salesman problem. It introduces the traveling salesman problem, describes the benefits and steps of the genetic algorithm, provides an example of how it would work applying the algorithm to a TSP, and concludes by discussing other potential applications of genetic algorithms.

Uploaded by

ASHISH JOSE 20BCE10286
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
47 views19 pages

Travelling Salesman Problem Using Genetic Algorithm: Faculty

The document discusses using a genetic algorithm to solve the traveling salesman problem. It introduces the traveling salesman problem, describes the benefits and steps of the genetic algorithm, provides an example of how it would work applying the algorithm to a TSP, and concludes by discussing other potential applications of genetic algorithms.

Uploaded by

ASHISH JOSE 20BCE10286
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 19

Travelling Salesman Problem

Using Genetic Algorithm

Faculty: Dr.Nidhi Mishra


Ashish Jose Rajarshi Mishra Vipul Anand
20BCE10286 20BCE10265 20BCE10296

Sheetal Nagliya Chinmay Agrawal


20BCE10258 20BCE10264
TABLE OF CONTENTS

01 Introduction
03
Working

Benefits Conclusion
02 04
01
Introduction
INTRODUCTIO
N
Genetic algorithms are heuristic search algorithms
inspired by the process that supports the
evolution of life. The algorithm is designed to
replicate the natural selection process to carry
generation, i.e. survival of the fittest of beings.
The algorithm can be implemented to find a
solution to the optimization problems of various
types. One such problem is the Traveling
Salesman Problem. The problem says that a
salesman is given a set of cities, he has to find
the shortest route to as to visit each city exactly
once and return to the starting city.
02
Benefits And
Algorithm
Benefits
1. Concept is easy to understand.
2. Modular, separate from application.
3. Supports multi-objective optimization
4. Always an answer; answer gets better with time.
5. Inherently parallel; easily distributed.
Algorithm
Steps of Algorithm
Step-1: Randomly Create the initial population of individual
string of the given TSP problem and create a matrix
representation of the cost of the path.
Step-2: Assign the fitness to each chromosome in the population
using fitness criteria measure.
F(x)= 1/x
Where, x represent the total cost of string.
Step-3: Create new off-spring population from two existing
chromosomes in the parent population by applying crossover
operator.
Step-4: Mutate the resultant off-springs if required.
Step-5: Repeat step-3 and step-4 until we get an optimal solution
to the problem.
Working
03
Working of Chromosomes

Initial Population Chromosome


(K Chromosomes)
The chromosomes crossover
and goes through mutation to
create k- offspring

K- initial Chromosomes K- offspring Chromosomes


Generation h- population

Intermediate Step

Generation h+1
TSP

D
B

A-B-D-C-A
Or
(1-2-4-3-1)

C
A
Chromosomes

Random Sequence Random Sequence


Numbers Numbers
(1→2 →7 →4 →5
0.23 2 0.23 2 →3 →6 →1)
0.65 3 0.34 7

0.49 4 0.49 4

0.58 5 0.58 5

0.75 6 0.65 3

0.34 7 0.75 6
Crossover for TSP

Parent 1 1 3 4 2 5 7 6

Parent 2
1 7 5 2 3 4 6

Offspring 1 1 2 3 4 6 7 5
Mutation for TSP

Parent 1 1 3 4 2 5 7 6

Offspring 1 1 7 5 2 3 4 6
Conclusion
04
Conclusion
Genetic algorithms are rich - rich in application across a large and
growing number of disciplines. The proposed approach can be
applied for various advanced network models like logistic
network, task scheduling models, vehicle navigation routing
models etc. The same approach can also be used for
allocation of frequencies in cells of cellular network.
Thanks!

You might also like