Scribd
Upload
61 views7 pages

Faculty of Egineering and Technology: Lecture - 34 Soft Computing

The document discusses using a genetic algorithm to solve the traveling salesman problem. It describes the genetic algorithm approach which involves initializing a population of routes, calculating fitness based on route length, selecting best routes, and using crossover and mutation over multiple iterations to find an optimal solution. Key steps are outlined for implementing a genetic algorithm to solve the traveling salesman problem.

Uploaded by

Prabhat kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
61 views7 pages

Faculty of Egineering and Technology: Lecture - 34 Soft Computing

The document discusses using a genetic algorithm to solve the traveling salesman problem. It describes the genetic algorithm approach which involves initializing a population of routes, calculating fitness based on route length, selecting best routes, and using crossover and mutation over multiple iterations to find an optimal solution. Key steps are outlined for implementing a genetic algorithm to solve the traveling salesman problem.

Uploaded by

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

FACULTY OF EGINEERING AND TECHNOLOGY

Soft Computing
LECTURE -34
Umesh Kumar Gera
Assistant Professor
Computer Science & Engineering
OUTLINE

Traveling Salesman Problem using Genetic Algorithm

Approach

Algorithm of TSP

Steps of TSP using GA

Multiple Choice Question

References
TRAVELING SALESMAN PROBLEM USING GENETIC ALGORITHM

Traveling Salesman Problem Using Genetic Algorithm

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. Standard genetic

algorithms are divided into five phases which are:

1. Creating initial population.

2. Calculating fitness.

3. Selecting the best genes.

4. Crossing over.

5. Mutating to introduce variations.


TRAVELING SALESMAN PROBLEM USING GENETIC ALGORITHM

Traveling Salesman Problem Using Genetic Algorithm

Approach:

In the following implementation, cities are taken as genes, string generated using these characters is called a chromosome,

while a fitness score which is equal to the path length of all the cities mentioned, is used to target a population.

Fitness Score is defined as the length of the path described by the gene. Lesser the path length fitter is the gene. The fittest of

all the genes in the gene pool survive the population test and move to the next iteration. The number of iterations depends

upon the value of a cooling variable. The value of the cooling variable keeps on decreasing with each iteration and reaches a

threshold after a certain number of iterations.


TRAVELING SALESMAN PROBLEM USING GENETIC ALGORITHM

Steps of TSP using GA

1. Initialize the population randomly.

2. Determine the fitness of the chromosome.

3. Until done repeat:

1. Select parents.

2. Perform crossover and mutation.

3. Calculate the fitness of the new population.

4. Append it to the gene pool.


MULTIPLE CHOICE QUESTION

1. Which of the following is false in the case of a 4. The travelling salesman problem can be solved using
spanning tree of a graph G? _________
a) It is tree that spans G a) A spanning tree
b) It is a subgraph of the G b) A minimum spanning tree
c) It includes every vertex of the G c) Bellman – Ford algorithm
d) It can be either cyclic or acyclic d) DFS traversal
View Answer
2. Every graph has only one minimum spanning tree. 5. Consider the graph M with 3 vertices. Its adjacency matrix is
a) True shown below. Which of the following is true?
b) False a) Graph M has no minimum spanning tree
b) Graph M has a unique minimum spanning trees of cost 2
3. Consider a complete graph G with 4 vertices. The c) Graph M has 3 distinct minimum spanning trees, each of cost 2
graph G has ____ spanning trees. d) Graph M has 3 spanning trees of different costs
a) 15
b) 8
c) 16
d) 13
REFERENCES

https://www.javatpoint.com/artificial-neural-network-hopfield-network

https://www.geeksforgeeks.org/traveling-salesman-problem-using-genetic-algorithm/

You might also like