1 Travelling Salesman Problem using Genetic Algorithms

Submitted To:- Presented By:-

Dr. Meenakshi Sood, Sunaina Stan
Er. Shano Solanki, Associate CSE 2020 Modular
Professors NITTTR, Batch
Chandigarh Roll No. 201409
 Contents
2

 Introduction of Travelling Salesman Problem

 The Genetic Algorithm
 Search space
 Basic Algorithm
 Initial Population
 Fitness Function
 Selection
 Crossover
 Mutation
 TSP using Genetic Algorithms
 Result
 Conclusion and Future scope
 References
 General Introduction to GAs
3

 Genetic algorithms (GAs) are a technique to solve problems which

need optimization.

 GAs are a subclass of Evolutionary Computing and are random

search algorithms.

 GAs are based on Darwin’s theory of evolution.

 History of GAs:
• Evolutionary computing evolved in the 1960s.
• GAs were created by John Holland in the mid-1970s.
 Genetic Algorithm
4

 Developed: USA in the early 1970’s by Prof. John Holland

 Typically applied to:
 discrete optimization
 Attributed features:
 not too fast
 good heuristic for combinatorial problems
 Special Features:
 Traditionally emphasizes combining information from good parents (crossover)
 many variants, e.g., reproduction models, operators
 Based on Theory of Evolution by Natural Selection.
 Incorporate the Evolutionary mechanism of Survival of the fittest.
 Biological Background (1) – The Cell
 Every cell is a complex of many small “factories”
 working together.
 The center of this all is the cell nucleus.
 The nucleus contains the genetic information.

5
Biological Background (2) – Chromosomes
 Genetic information is stored in the chromosomes.

 Each chromosome is build of DNA.

 Chromosomes in humans form pairs.

 There are 23 pairs.

 The chromosome is divided in parts: genes.

 Genes code for properties.

 The posibilities of the genes for one property is called: allele.

6
 Every gene has an unique position on the chromosome: locus.
 Biological Background (3) – Genetics
7

 The entire combination of genes is called genotype.

 A genotype develops into a phenotype.
 Alleles can be either dominant or recessive.
 Dominant alleles will always express from the genotype to the
fenotype.
 Recessive alleles can survive in the population for many generations
without being expressed.
 The Travelling Salesman Problem
8

 The travelling salesman problem (TSP) is the most well-known combinatorial

optimization problem.
 TSP is used to find a routing of a salesman who starts from a home location, visits a
prescribed set of cities and returns to the original location in such a way that the
total distance travelled is minimized and each city is visited exactly once .
 This problem is known to be NP-hard, and cannot be solved exactly in polynomial
time.
 It is a minimization problem.
 The numbers of fields where TSP can be used very effectively are military and
traffic.
 Some typical applications of TSP include vehicle routing, computer wiring, cutting
wallpaper and job sequencing.
 Will genetic algorithms work for TSP ?
9

 Optimization is the process of finding a better solution to a

problem.
 A genetic algorithm generates a population of competing
candidate solutions and then causes them to evolve through
the process of natural selection – poor solutions tend to die
out, while better solutions survive and reproduce. By repeating
this process over and over again, the genetic algorithm breeds
an optimal solution.
 Another approach is to use genetic algorithm to solve TSP
because of its robustness and flexibility.
 The Basic Algorithm
10

 Fix initial population of P chromosomes

 Randomly generate P strings in the solution space
 Evaluate the fitness of each chromosome
 Repeat:
 Select two fittest strings(parents) to reproduce
 Apply crossover with high probability to produce offspring
 Apply mutation to parent or offspring with low probability
 Observe the fitness of each new string
 Replace weakest strings of the population with the offspring
 until
 fixed number of iterations completed, OR
 average/best fitness above a threshold, OR
 average/best fitness value unchanged for a fixed number of consecutive iterations
 Flowchart of GA
11

• All individuals in population

evaluated by fitness function.
• Individuals allowed to
reproduce (selection),
crossover, mutate.

Flowchart of GA
 Genetic Algorithm (3) – Basic Algorithm
12

Outline of the basic algorithm

0 START : Create random population of n chromosomes

1 FITNESS : Evaluate fitness f(x) of each chromosome in the population
2 NEW POPULATION
1 REPRODUCTION/SELECTION : Based on f(x)
2 CROSS OVER : Cross-over chromosomes
3 MUTATION : Mutate chromosomes

3 REPLACE : Replace old with new population: the new generation

4 TEST : Test problem criterium
5 LOOP : Continue step 1 – 4 untill criterium is satisfied
13
 Genetic Algorithm- Search space
14

 Most often one is looking for the best

solution in a specific subset of solutions
(best?, exploration) 2.5

 This subset is called the search space (or 2

state space)
1.5

 Every point in the search space is a

possible solution
1

Therefore every point has a fitness

0.5


value, depending on the problem 0
0 100 200 300 400 500 600 700 800 900 1000

definition (higher is closer to best)

 GA’s are used to search the search
space for the best solution.
 Initial Population
15

 Population is the subset of solutions in the

current generation.
 It can also defined as set of chromosomes.
 An individual is characterized by a set of
parameters(variables) known as Genes.
Genes are joined into a string to form a
Chromosome(solution).
 Population size should be kept optimal.
 Two primary methods for Population
initialization are:-
 - Random initialization
 -Heuristic initialization
 Selection
16

 The idea of selection phase is to select the fittest individuals

and let them pass their genes to the next generation.

 Two pair of individuals(parents) are selected based on their

fitness scores. Individual with higher fitness have more chance
to be selected for reproduction.

 There are four popular methods for selection: Random,

Tournament and Roulette wheel.
 Selection
17

 (a) Random Selection Method:-This is the Tournament selection

simplest selection consists of randomly selecting method
individuals for reproduction with no regard to
the fitness function.
 (b) Tournament Selection Method:-
 - It selects k individuals with replacement from
a population of p ,applies the fitness function to
those individuals to select the one with best
fitness score, also known as fittest individual.
 - The fittest individuals from each tournament
round will be the parents responsible for
forming the next generation.
 Selection
18
18

 c) Roulette-Wheel Selection
Method:-
100 0
X1: 16.5%
 In this method , individuals X2:
X3:
20.2%
6.4%
75.2
have a fitness- X4: 6.4%
proportionate probability 36.7
X5:
X6:
25.3%
24.8%
of being selected. 49.5 43.1
 Fitness function
19

 The fitness function determines the fitness of an individual.

 It gives a fitness score to each individual
 The probability that an individual will be selected for reproduction is based
on its fitness score.
 The purpose of the fitness function is to decide if a chromosome is good
then how good it is ? In the travelling salesman problem the criteria for
good chromosome is its length.
 Fitness function calculation takes place during the creation of the
chromosomes.
 Fitness Function
20

 The fitness of each individual chromosome is determined as the reciprocal

of the route length, the shorter the route, the fitter the chromosome.
count
 fitness of chromosome = ∑ti
i=1

 where
 count = total number of cities
 ti = distance between two cities.
 Fitness Function
21

 Fitness function:
 f(x), x is a chromosome in the solution space
 f(x) may be:
 an well-defined objective function to be optimised
 e.g. TSP and knapsack
 a heuristic
 e.g. N-Queens
P X  xi  
f ( xi )

M
 Probability distribution for selection: j 1
f (x j )

 Fitness proportional selection

 Crossover
22

 Crossover plays a vital role in a genetic algorithm. For each pair of parents to
be mated, crossover point is chosen at random from within the genes.
 Offsprings are created by exchanging the genes of parents among
themselves until the crossover point is reached. The new offsprings are added
to population.
 Sometimes the offspring takes half of its genes from one parent and the other
half from the other parent.
 Crossover is important and without it, the offspring will be identical to its
parent.
 Crossover
23

 One Point Crossover

 In this one-point crossover, a random
crossover point is selected and the tails
of its two parents are swapped to get
new off-springs.
 Multi Point Crossover
 Multi point crossover is a
generalization of the one-point
crossover where in alternating
segments are swapped to get new off-
springs.
 Crossover operator for TSP
24

The crossover operator in its classical form cannot be

directly applied to the TSP. A simple exchange of parts
between two parents would produce illegal routes containing
duplicates and omissions – some cities would be visited twice
while some others would not be visited at all.

Parent 1: 1 6 5 3 2 8 4 9 7 Parent 2: 3 7 6 1 9 4 8 2 5

Child 1: 1 6 5 3 9 4 8 2 5 Chil d 2: 3 7 6 1 2 8 4 9 7
 Order Crossover
25

 It is used for permutation based crossovers with the

intention of transmitting information about relative
ordering to the off-springs.
 It works as follows −
 - Create two random crossover points in the
parent and copy the segment between them from the
first parent to the first offspring.
 -Now, starting from the second crossover point in
the second parent, copy the remaining unused
numbers from the second parent to the first child,
wrapping around the list.
 -Repeat for the second child with the parent’s
role reversed.
 Mutation
26

 Mutation is a genetic operator used to maintain genetic diversity from one

generation of a population of chromosomes to other.
 It alters one or more gene values in a chromosome from its initial state.
 The mutation operator flips a randomly selected gene in a chromosome.
 This makes the individuals explore in search of the optima by constantly
changing the gene values.
 The mutation probability is quite small in
 nature, and is kept low for GA’s, typically
 in the range between 0.001 and 0.01.
 Why crossover and mutation?
27

 Crossover
 Produces new solutions while ‘remembering’ the
characteristics of old solutions
 Partially preserves distribution of strings across schemas

 Mutation
 Randomly generates new solutions which cannot be
produced from existing population
 Avoids local optimum
  First, we need to decide how to represent a route of the salesman. The most
natural way of representing a route is the path representation. Each city is
given an alphabetic or numerical name, the route through the cities is
represented as a chromosome, and appropriate genetic operators are used to
create new routes.
 TSP can be modelled as an undirected weighted graph, such that cities are the
graph’s vertices, paths are the graph’s edges, and a path’s distance is the
edge’s length.
 The Euclidean distance d, between any two cities with coordinate (x1, y1) and
(x2, y2) is calculated by equation
 d=√(│X1-X2│)²+(│Y1-Y2│ ﴿²
 Suppose we have nine cities named from 1 to 8. In a chromosome, the order
of the integers represents the order in which the cities will be visited by the
salesman.
28
 Gentic Algorithm – Encoding method
29

No. of cities = 5
,so total number
of possible path

5! = 120
 Genetic Algorithm Calculating Distance
30
 A Simple Example
31

The Traveling Salesman Problem:

Find the least cost route through a set of n cities so
that each city is visited exactly once.

Find a tour of a given set of cities so that

 each city is visited only once
 the total distance traveled is minimized
 Representation
32

Representation is an ordered list of city

numbers known as an order-based GA.

1) Lucknow 3) Delhi 5) Bhopal 7) Mumbai

2) Shimla 4) Chandigarh 6) Patna 8) Jaipur
CityList1 (3 5 7 2 1 6 4 8)
CityList2 (2 5 7 6 8 1 3 4)
No. of possible Path 8! = 40,320
 Crossover
33

Crossover combines inversion and recombination:

* *
Parent1 (3 5 7 2 1 6 4 8)
Parent2 (2 5 7 6 8 1 3 4)
Child (2 5 7 2 1 6 3 4)
This operator is called the Order1 crossover. Ensure no
duplicate cities in the tour
 Mutation
34

Mutation involves reordering of the list:

* *
Before: (5 8 7 2 1 6 3 4)
After: (5 8 6 2 1 7 3 4)
 TSP Example: 30 Cities
35
 Solution i (Distance = 941)
36
 Solution j(Distance = 800)
37
 Best Solution (Distance = 420)
38
Benefits of Genetic Algorithms
39

 Concept is easy to understand

 Modular, separate from application
 Supports multi-objective optimization
 Good for “noisy” environments
 Always an answer; answer gets better with time
 Inherently parallel; easily distributed
 Area of application
40

 GAs can be used when:

 Non-analytical problems.
 Non-linear models.
 Uncertainty.
 Large state spaces.
 41

PRACTICAL EXAMPLE -
TSP
 TSP Description
42

 Problem Statement: Given a complete weighted

undirected graph, find the shortest Hamiltonian
cycle. (n nodes)
 The size of the solution space in (n-1)!/2
 Dynamic Programming gives us a solution in time
O(n22n)
 TSP is NP Complete
 Example : Selection
43

4 1
31% 14%

5% 3 49%
2
 Example : Crossover
44
 Example : Mutation
45
 Comparison of GA with Traditional Optimization
46
Techniques

 GA works with the coding of solution set and not with the solution
itself.

 GA uses population of solutions rather than a single solution for

searching.

 GA uses fitness function for evaluation rather the derivatives.

 GA uses probabilistic transition and not deterministic rules.

 Conclusion and future scope
47

• Combining the knowledge from heuristic methods and genetic algorithms is a

promising approach for solving the TSP.
• Genetic algorithms appear to find good solutions for the travelling salesman
problem, however it depends very much on the way the problem is encoded
and which crossover and mutation methods are used.
• The research work can be extended for different hybrid selection, crossover and
mutation operators.
• 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.
 References
48

 Neural Network Fuzzy Logic and Genetic Algorithms. –G.A. Vijayalakshmi

Pai.

 Artificial intelligence – Second Edition – Michael Negnevitsky

 Principals Of Soft Computing – S.N. Shivanandan.

 Travelling Salesman Problem Optimization Using Genetic Algorithm -

Sahib Singh Juneja, Pavi Saraswat , Kshitij Singh
 Online Resources
49

 [Link]

 [Link]

 [Link]
50