Travelling Salesman Problem Using Genetic Algorithms

Travelling Salesman Problem Using Genetic Algorithms

Problem Definition

-The traveling salesman problem consists of a salesman and a

set of cities. 

-The salesman has to visit each one of the cities

starting from a certain one (e.g. the hometown) and returning

to the same city. 

-The challenge of the problem is that the

traveling salesman wants to minimize the total length of the

trip

Method Used

• We have a set of cities (points) in 2d plane. 

Each city has  

road to each city.

 We need to find loop-path that will be in 

each city only one time and path length is minimal.

• The genetic algorithm is sequence of following operations

that repeated in generations loop:

1) Generate random population and finding path length.

2) find probabilities for selection.  f(x)= 1/d

3) prepare to crossover according probabilities.  pi=1/di / Σ 1/di

4) crossover, parents replaced with children.

5) mutations.(Swap,Flip,Random)

Similarly

 Internet Search Technique

• Searching using Links
• Application Starts from Set of Documents
• Indexing Web Bages
• Storing Information into DB

Genetic Algorithm vs Traditional/Classical Algorithm

Genetic Algorithm vs Traditional/Classical Algorithm

A genetic algorithm differs from a classical,Traditional  derivative-based, optimization algorithm in two ways:

• GA genetic algorithm generates a population of points in each iteration
• CA classical algorithm generates a single point at each iteration.

• GA genetic algorithm selects the next population by  Probability computation using random number generators.
• CA  classical algorithm selects the next point by deterministic computation.

Compared to traditional artificial intelligence, a genetic algorithm provides many advantages.

• GA works with  coding of Parameters set.
• CA  works themselves.

• GA is more robust and is susceptible to the presence of noise.
• CA is Less robust

• GA  genetic algorithm can provide better and more significant results while searching large multi-modal state spaces, large state spaces or n-dimensional surfaces.
• CA  provide better and less significant results while searching large multi-modal state spaces, large state spaces or n-dimensional surfaces.

Applications 

• robotics
• automotive design
•  optimized telecommunications routing
• engineering design 
• computer-aided molecular design

Genetic Algorithm Steps

A genetic algorithm makes uses of techniques inspired from evolutionary biology such as

• Selection(Reproduction),
• Mutation, 
• Inheritance 
• Cross Over(recombination)  to solve a problem. 

The most commonly employed method in genetic algorithms 

1.  create a group of individuals randomly from a given population.
2. The formed individuals are evaluated with the help of the evaluation function provided by the programmer.
3. Individuals are then provided with a score which indirectly highlights the fitness to the given situation. 
4. The best two individuals are then used to create one or more offspring, after which random mutations are done on the offspring. 
5. Depending on the needs of the application, the procedure continues until an acceptable solution is derived or until a certain number of generations have passed.

Operators in Genetic Algorithm

Operators in Genetic Algorithm

Encoding

1. Binary {0,1}
2. Octa {0-7}
3. Hexa {0-15}

Selection

1. Roulette Wheel
2. Random Selection
3. Rank Selection
4. Tournament Selection
5. Boltzmann Selection
6. Stochastic Selection

Crossover

1. Single Point
2. Two  Point
3. Multi Point
4. Uniform 
5. ThreeParent
6. Ordered 
7. Shuffled
8. Partially Matched 

Mutation

1. Flipping
2. Interchanging
3. Reversing

Genetic Alogrithm

Genetic Algorithm

Definition:-

• A genetic algorithm is a heuristic search method used in artificial intelligence and computing. 
• It is used for finding optimized solutions to search problems based on the theory of natural selection and evolutionary biology.
•  Genetic algorithms are excellent for searching through large and complex data sets.
•  They are  capable of finding reasonable solutions to complex issues.
• Genetic algorithm maximizes  fitness-function among the population  with fittest individuals.

Natural Selection

• Select the  fittest individuals from a population.
• Produce offspring which inherit the characteristics of the Parents and added to the next generation
•  If parents have better fitness, their offspring will be better than parents and have a better chance at surviving
• This process keeps on iterating and at the end, a generation with the fittest individuals will be found.

This notion can be applied for a search problem. We consider a set of solutions for a problem and select the set of best ones out of them.

5 Phases

1. Initial population
2. Fitness function
3. Selection
4. Crossover
5. Mutation

Mutation

Initial population

The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve.

An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).

In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used (string of 1s and 0s). We say that we encode the genes in a chromosome.

Fitness Function

The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

Selection

The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.

Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.

Crossover

Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

For example, consider the crossover point to be 3 as shown below.

Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

Exchanging genes among parents

The new offspring are added to the population.

New offspring

Mutation

In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.

Mutation: Before and After

Mutation occurs to maintain diversity within the population and prevent premature convergence.

Termination

The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then it is said that the genetic algorithm has provided a set of solutions to our problem.

Comments

The population has a fixed size. As new generations are formed, individuals with least fitness die, providing space for new offspring.

The sequence of phases is repeated to produce individuals in each new generation which are better than the previous generation.