%% student dave tutorial on...
%% THE TRAVELING SANTA CLAUS! a "potentially" shortest path santa might
%% travel during christmas to most of the countries
close all
clear all
clc
%% load in the list of country longitude and latitudes
%country_long_lat.name --> country names
%country_long_lat.loc --> country longititude and latitude from google
%(N and E are postitive, S and W are negative.
load('country_lat_long.mat');
locs = country_lat_long.loc
names = country_lat_long.name
Nc = length(locs); %number of countries
%% measure AIR distance (spherical distance) between all country and make into big ole matrix!
dist_air = nan(Nc);
for i = 1:Nc
for j = 1:Nc
dist_air(i,j) = distance(locs(i,1),locs(i,2),locs(j,1),locs(j,2));
end
end
%save('dist_air.mat','dist_air')
load('dist_air.mat')
%% Genetic algorithm part!
% we need a random set of paths..like, i dunno, 100 paths! this is our
% first generation of paths..they are our primordial soup..if they are too
% local (i.e. to similar) and are not good...we'll have a hard time ever
% getting a good approximate solution :(.
N = 2000
popl = nan(N,Nc);
for v = 1:N
popl(v,:) = randperm(Nc); %makes random sequence through all the counties
end
%now loop through the generations testing them over and over
perf_top = [];
path_top = [];
KK = 1
for TT = 1:N
%well, how good are these routes!!? for each path sequence, see how long the total
%travel was (don't forget the distance to and from the north pole!)
tot_dist = [];
for f = 1:size(popl,1)
tot_dist(f) = dist_air(popl(f,end),popl(f,1)) + sum(diag(dist_air(popl(f,1:end-1)',popl(f,2:end)'))); %this is lil trick for getting the elements at the indices given by the 2 vectors
end
%now, we want to avoid local minimum as much as possible, and since we are simulating such
%a relatively small subset of the entire space, we don't wanna just take the overall best performers..
%it makes it easier for us to run down quickly to a local minimum
%but we also don't wanna search the entire space..it's WAYYYYY too big... so what we can do
%is just randomly make subsets within the simulated population and see
%who's best within those lil populations (even if they are bad relative to
%the whole population). this will help us stay spread out in the space of
%possible paths.
%let's use groups of 10 within the population of 1000 simulated, and since
%they are randonly generated, we can just grab them sequentially.
%get best route for plotting performance
[val_top idx_top] = min(tot_dist);
perf_top = [perf_top val_top(1)];
path_top(TT,:) = popl(idx_top(1),:);
k = 1;
T = 5;
top_routes = [];
rand_pop = randperm(size(popl,1));
rand_dist = tot_dist(rand_pop);
[val idx ] = min(reshape(rand_dist,T,N/T)); %get min distance for each randomized set
tmp_pop = reshape(rand_pop,T,N/T); %map onto the randomized population
top_routes = popl(diag(tmp_pop(idx,:))',:); %map onto the native population and take those best performers within each set
%for each top route, create T routes out of that one
nxt_gen_routes = [];
for G = 1:size(top_routes,1)
pt = [];
pt= ceil(rand(1,2)*Nc);
m = round(Nc/2);
for k = 1:T % Mutate the Best to get Three New Routes
sub_pop(k,:) = top_routes(G,:);
switch k
case 1 %switch a random segment
r = randperm(2);
sub_pop(k,[1:pt(r) pt(r)+1:end ]) = sub_pop(k,[ pt(r)+1:end 1:pt(r)]);
case 2 %flip the middle segment
sub_pop(k,pt(1):pt(2)) = fliplr( sub_pop(k,pt(1):pt(2)));
case 3 % point mutations
sub_pop(k,[pt(1) pt(2)]) = sub_pop(k,[pt(2) pt(1)]);
case 4 %shift
sub_pop(k,:) = circshift( sub_pop(k,:),[0 diff(pt)]);
otherwise %clone of last generation
end
end
nxt_gen_routes = [nxt_gen_routes; sub_pop];
end
popl = nxt_gen_routes;
TT
%pause(0.01)
end
save('GA_results.mat','perf_top', 'path_top')
%plot the results
KK = 1
for TT = 1:N
if (mod(TT,2) == 0)
figure(1);
subplot(211);plot(perf_top(1:TT),'.b');
axis([1 2000 0 18000 ])
xlabel('generation number')
ylabel('total distance traveled')
%subplot(212);plot(locs(path_top,1),locs(path_top,2),'.-r');
subplot(212);plot(locs(path_top(TT,:),1),locs(path_top(TT,:)',2),'o-r','markersize',5,'MarkerFaceColor','g');
set(gca,'Xtick',[],'Ytick',[])
title(['best dist = ',num2str(round(perf_top(TT))),' Generation = ',num2str(TT)])
xlabel('2-d projection of country locations')
eval(['print -djpeg GA_santa_path_',num2str(KK),'.jpeg'])
KK = KK + 1;
pause(0.1)
end
end