This project is about an application used by the Traveling Salesman, given a finite number of cities(I have chosen cities from 1 to a finite number) along with the distance of travel (distance between two cities is randomly chosen) between each pair of them, The aim is to find the shortest distance between the cities and returning to the starting point.In the Traveling Salesman Problem, the goal is to find the shortest distance between N different cities. The path that the salesman takes is called a tour. A genetic algorithm can be used to find a solution is much less time. Although it might not find the best solution, it can find a near perfect solution for a 100 city tour in less than a minute.
There are a couple of basic steps to solving the traveling salesman problem using a GA. First, create a group of many random tours in what is called a population. This algorithm uses a greedy initial population that gives preference to linking cities that are close to each other.Second, pick 2 of the better (shorter) tours parents in the population and combine them to make 2 new child tours. Hopefully, these children tour will be better than either parent.A small percentage of the time, the child tours are mutated. This is done to prevent all tours in the population from looking identical.The new child tours are inserted into the population replacing two of the longer tours. The size of the population remains the same. New children tours are repeatedly created until the desired goal is reached. The two complex issues with using a Genetic Algorithm to solve the Traveling Salesman Problem are the encoding of the tour and the crossover algorithm that is used to combine the two parent tours to make the child tours.
Now we will have a look at the internal working of genetic algorithm. At first we will make a chromosome of cities. Each gene inside a chromosome will represent a city via which a person can travel to reach the destination along with its latitude and longitude. You can choose the no of chromosomes based on the tests conducted to reach the final result. It will be ideal to have a population size of 100. No of iterations also should be defined based on the accuracy of results. Ideal no of iterations can be 100. As number of iterations increase, time taken to calculate the result will be more. Now the core component is objective function which calculate the distance between the cities and sum up get the final result. Objective function to calculate the distance is given below
Radius in Kilometer = 6371;
Latitude Total = (Latitude 2 - Latitude 1) in Radiance
Longitude Total = (Longitude 2 - Longitude 1) in radiance
a = Math.sin(Latitude Total/2) * Math.sin(Latitude Total/2) + Math.sin(Longitude Total/2) * Math.sin(Longitude Total/2) * Math.cos(latitude 1 in Radiance) * Math.cos(latitude 2 in Radiance);
c = 2 * Math.tan ( Math.sqrt (a), Math.sqrt (1-a) );
d = Radius in Kilometer * c;
We are using JGAP to implement genetic algorithm in this project.