File Exchange

image thumbnail

Travelling Salesman Problem - A Genetic Algorithm Approach

GUI which provides a genetic algorithm based solution for solving the NP Travelling Salesman Problem

15 Downloads

Updated 11 Dec 2015

View License

This Graphic User Interface (GUI) is intended to solve the famous NP-problem known as Travelling Salesman Problem (TSP) using a common Artificial Intelligence method: a Genetic Algorithm (GA).

Execute ‘main.m’ for running the main GUI program. As shown in the thumbnail, the program allows the user to configure every single parameter of the GA.

First of all, it is necessary to set the cities to travel on the map. The GUI offers three different options: a circled position, a random position or a custom one. If ‘circled’ or ‘random’ are selected, it is necessary to set the number of cities. In contrast, if ‘custom’ is selected, a new figure will rise up for introducing each city position with the mouse.

Once the city map is created, it is time to set the optimal parameters for solving the problem. Those parameters are the population size, the maximum number of generations, the mutation and crossover likelihoods, if elitism is wanted or not and the type of likelihood variation (i.e., whether it is necessary to vary the likelihood with a linear tendency or it is better to maintain the values as constants).

Finally, pressing the ‘run’ button, the algorithm will start. In this case, fitness is the inverse of the distance, because the algorithm is trying to find the shortest route (i.e., chromosome) that connects all the cities (i.e., minimizing the traveled distance). The GUI presents 4 different graphs: distance matrix (bottom left), best local route in the current generation (upper left), best local route found until the moment (upper right) and fitness monitoring (bottom right). In addition, the AG can be stopped at any time.

Cite As

Víctor Martínez-Cagigal (2019). Travelling Salesman Problem - A Genetic Algorithm Approach (https://www.mathworks.com/matlabcentral/fileexchange/54420-travelling-salesman-problem-a-genetic-algorithm-approach), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (7)

Yuning Guo

David Franco

How can I load a xy.mat data to the script? Nice job.

Excellent

Hi Maximilian,

You just need to plot the map before plotting the current generation chromosome and make a "hold on" in that graph. In "main.m", search the "Genetic Algorithm loop". Then, in "Plotting the best chromosome for each generation", just place your map, for example, using "imagesc(handles.run_graph,'yourmappath.png');" and "hold(handles.run_graph,'on')".

Looks Great thanks!
I have one question, I would like to adapt it for finding the shortest route and therefore would need to place a picture, in this case a map, in the background.
How can I manage that?

Thanks in advance!

ayman goba

thanks

Updates

1.0.0.0

Comments added in 'pop_selection' and 'main' functions.

1.0.0.0

Grammar error.

MATLAB Release Compatibility
Created with R2013a
Compatible with any release
Platform Compatibility
Windows macOS Linux