%
% This is the main script to finds a (near) optimal solution to the Traveling
% Salesman Problem (TSP), by setting up a Genetic Algorithm (GA) to search
% for the shortest route (least distance for the salesman to travel to each
% city exactly once and return to the starting city).
%
% Author: zhou lvwen Email: zhou.lv.wen@gmail.com
% Release Date: November 12, 2012
%
clear;clc;
load china; % geographic information
plotcities(province, border, city); % draw the map of China
numberofcities = length(city); % number of cities
% distance matrix: dis(i,j) is the distance between city i and j.
dis = distancematrix(city);
popSize = 100; % population size
max_generation = 1000; % number of generation
probmutation = 0.16; % probability of mutation
% Initialize random number generator with "seed".
rand('seed',103);
% Initialize the pop: start from random routes
pop = zeros(popSize,numberofcities);
for i=1:popSize
pop(i,:)=randperm(numberofcities);
end
for generation = 1:max_generation % generations loop
% evaluate: compute fitness(1/totaldistance) for each individuals in pop
popDist = totaldistance(pop,dis);
fitness = 1./popDist;
% find the best route & distance
[mindist, bestID] = min(popDist);
bestPop = pop(bestID, :); % best route
% update best route on figure:
if mod(generation,10)==0
plotroute(city, bestPop, mindist, generation)
end
% select (competition / roulette)
pop = select(pop, fitness, popSize,'competition');
% crossover
pop = crossover(pop);
% mutation
pop = mutation(pop, probmutation);
% save elitism(best path) and put it to next generation without changes
pop = [bestPop; pop];
end
% return the best route
[mindist, bestID]=min(popDist);
bestPop = pop(bestID, :);
% plot the final solution
plotroute(city, bestPop, mindist, generation);