Travel Planner using Genetic Algorithm

    4 Votes

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.

Attachments:
Download this file (SalesManV1.zip)Travel Planner using Genetic Algorithm[Source Code]1660 Kb

Popular Videos

How to speak to people

How to speak so that people want to listen.

Got a tip or Question?
Let us know

Related Articles

Data Recovery and Undeletion using RecoverE2
PC CONTROLLED ROBOTIC CAR
Routino Router Algorithm
Data Leakage Detection
Scene Animation System Project
Data Structures and Algorithms Visualization Tool
Paint Program in C
Solving 0-1 Knapsack Problem using Genetic Algorithm
Software Watermarking Project
Android Gesture Recognition
Internet working between OSI and TCP/IP Network Managements with Security Features Requirements
Web Image Searching Engine Using SIFT Algorithm
Remote Wireless Sensor Networks for Water Quality Monitoring Requirements
Ranking Spatial Data by Quality Preferences
Scalable Learning Of Collective Behaviour
Computational Metaphor Extraction And Interpretation
Designing a domain independent Rules Engine For Business Intelligence
Graph Colouring Algorithm
Gesture Based Computing
Facial Expression Detection