Artificial Intelligence / Evolutionary Algorithms (1)

The Traveling salesman problem is described as follows: given a list of cities and their pairwise distances, find the shortest possible tour that visits each city exactly once. Design and implement a genetic algorithm to solve this problem.

MATLAB CODE

   1: function travelsp

   2: clear all; close all; clc;

   3: %Traveling Salesman Problem

   4: %Pablo Rivas Perea

   5: %800-40-4524

   6:  

   7: num_cit=inputdlg('Please type the number of cities','Step 1',1,{'8'});

   8: if ~isempty(cell2mat(num_cit))

   9:     num_cit=str2num(cell2mat(num_cit));

  10:     button = questdlg('How do you preffer to generate the distance matrix between cities?','Please confirm','Randomly','Manually','Randomly');

  11:     if strcmp(button,'Randomly')

  12:         points=rand(num_cit,2)*100;

  13:         dismat=zeros(num_cit);

  14:         for r=1:num_cit

  15:             for c=1:num_cit

  16:                 if c>r 

  17:                     d=sum((points(r,:)-points(c,:)).^2).^0.5;

  18:                     dismat(r,c)=d; dismat(c,r)=d;

  19:                 end

  20:             end 

  21:         end        

  22:     else

  23:         %do manual

  24:     end

  25:     %imagesc(dismat);

  26:     %initial parameters

  27:     solsnum=256;     %number of total solutions

  28:     numbits=size(dec2bin(num_cit-1),2); %minimum number of bits to represent the cities

  29:     elitism=1;      %best ranked solutions to keep

  30:     evolvesols=8;   %best ranked solutions to evolve, has to be EVEN

  31:     mincrossover=round(numbits*0.7); %round(rand*numbits);   %minimum start for crossover

  32:     maxmutations=round(numbits*0.5); %round(rand*numbits);   %maximum amount of mutations

  33:     maxiwnch=50;   %maximum iterations with no change on fitness (when to stop)

  34:     hfig = figure('Name','CS5314 - Genetic Algorithm Evolution','Numbertitle','off');

  35:     tic

  36:     %generate initial random solutions

  37:     sols={};

  38:     for n=1:solsnum

  39:         sols(1:num_cit,n)=randombinsol(num_cit,numbits);

  40:     end

  41:     fitsols=0; it=1;

  42:     %first iteration begins

  43:     contcrit=1;

  44:     while contcrit        

  45:         for n=1:solsnum

  46:             fitsols(n)=evalfitness(bin2dec(cell2mat(sols(:,n))),dismat);

  47:         end

  48:         [rsols,lowfit]=ranksols(sols,fitsols);   %ranking for posterior selection

  49:         history(it)=lowfit;

  50:         contcrit=evalstopcrit(history,maxiwnch);

  51:         path=(bin2dec(rsols(:,1))+1);

  52:         if contcrit<0

  53:             toc

  54:             fprintf('Solution found at iteration %d\n',it);

  55:             fprintf('Solution Fitness is: %f\nBest path is\n',lowfit); path

  56:             fprintf('\nPress enter to display the binary string\nBest path is\n');

  57:             pause;  rsols(:,1)

  58:             break;

  59:         end

  60:  

  61:         figure(hfig);

  62:         pts = points([path(:,1); path(1)],:);

  63:         plot(pts(:,1),pts(:,2),'.-','Color',[1 0 0]);

  64:         title(sprintf('Lowest fitness (Distance) = %1.4f, Generation = %d',lowfit,it));

  65:  

  66:         nsols=rsols(:,1:elitism);       %elitism parameter, keeps the best ranked

  67:         %offspring generation.  First evolve the best ranked

  68:         nsols(:,(elitism+1):(elitism+evolvesols))=fevolvesol(rsols, evolvesols, mincrossover, maxmutations, num_cit);

  69:         %then generate new random solutions

  70:         for n=(1+elitism+evolvesols):solsnum

  71:             nsols(1:num_cit,n)=randombinsol(num_cit,numbits);

  72:         end        

  73:         %first iteration complete, start to iterate all until fitness is

  74:         %reached  

  75:         sols=nsols;

  76:         it=it+1;

  77:     end

  78: end

  79: end

  80:  

  81: function rsol=randombinsol(ncities,nbits)

  82:     dsol=ones(ncities,1).*ncities;

  83:     n=0;

  84:     while n<ncities

  85:         cand=round(rand*(ncities-1));

  86:         if ~any(dsol==cand)

  87:             n=n+1;

  88:             dsol(n,1)=cand;

  89:         end

  90:     end

  91:     rsol=cellstr(dec2bin(dsol,nbits));

  92: end

  93:  

  94: function totdist=evalfitness(propsol,dismat)

  95:     totdist=0;

  96:     for n=1:(size(propsol,1)-1)

  97:         totdist=totdist+dismat(propsol(n)+1,propsol(n+1)+1);

  98:     end

  99:     totdist=totdist+dismat(propsol(n+1)+1,propsol(1)+1);

 100: end

 101:  

 102: function [rsols,lowfit]=ranksols(sols,fsols)

 103:     [rsols, ix]=sort(fsols,2);

 104:     lowfit=rsols(1);

 105:     rsols={};

 106:     for n=1:size(sols,2)

 107:         rsols(1:size(sols,1),n)=sols(1:size(sols,1),ix(n));        

 108:     end    

 109: end

 110:  

 111: function cont=evalstopcrit(history,maxiwnch)

 112:     cont=1;

 113:     if history(size(history,2))==0  %YES! Solution found

 114:         cont=0;

 115:     elseif size(history,2)>=maxiwnch

 116:         startpoint=size(history,2)-maxiwnch+1;

 117:         endpoint=size(history,2);

 118:         thist=history(startpoint:endpoint)-history(endpoint); %subtract the last best fitness from all

 119:         tthist=sum(thist);  %if the sum is zero means that there is no improvement

 120:         if tthist==0

 121:             cont=-1;

 122:         end

 123:     end

 124: end

 125:  

 126: function evosol=fevolvesol(rsols, total, mco, mmu, num_cit)

 127:     t1evosol={}; t2evosol={}; evosol={};

 128:     for n=1:2:total

 129:         t1evosol=rsols(:,n);

 130:         t2evosol=rsols(:,n+1);

 131:         crossol=bincrossover(t1evosol, t2evosol, mco);

 132:         mutsol=binmutation(crossol, mmu, num_cit);

 133:         evosol(1:size(mutsol,1),n)=mutsol(:,1);        

 134:         evosol(1:size(mutsol,1),n+1)=mutsol(:,2);

 135:     end

 136: end

 137: function crossol=bincrossover(sol1,sol2,minco)

 138:     %randomly selecting the point of crossover based on the minimum

 139:     pcross=round(rand*(size(sol1,1)-minco)+minco);

 140:     solt=sol1;

 141:     sol1(1:size(sol1,1)-pcross)=sol1(pcross+1:size(sol1,1));

 142:     sol1((size(sol1,1)-pcross+1):size(sol1,1))=solt(1:pcross);

 143:     solt=sol2;

 144:     sol2(1:size(sol2,1)-pcross)=sol2(pcross+1:size(sol2,1));

 145:     sol2((size(sol2,1)-pcross+1):size(sol2,1))=solt(1:pcross);    

 146:     crossol(1:size(sol1,1),1:2)=[sol1,sol2];

 147: end

 148:  

 149: function mutsol=binmutation(solpair,maxmu, num_cit)

 150:     m1=round(rand*maxmu);   %how many mutations to the first pair? Top=maxmu

 151:     for n=1:m1

 152:         pos=round(rand*(size(solpair,1)-1))+1;    %where to perform the mutation?

 153:         old=solpair(pos,1);

 154:         new=bincompl(old); %mutation call

 155:         if bin2dec(new)>=num_cit

 156:             new=old;    %if the complement exceedes the valid number for a city, don't change it

 157:         end

 158:         idx=strfind(solpair(:,1),cell2mat(new));

 159:         for k=1:size(solpair,1)

 160:             if cell2mat(idx(k))==1

 161:                 solpair(k,1)=old;

 162:                 break 

 163:             end

 164:         end

 165:         solpair(pos,1)=new;

 166:     end

 167:     if (maxmu-m1)~=0

 168:         for n=1:(maxmu-m1)

 169:             pos=round(rand*(size(solpair,1)-1))+1;    %where to perform the mutation?

 170:             old=solpair(pos,2);

 171:             new=bincompl(old); %mutation call

 172:             if bin2dec(new)>=num_cit

 173:                 new=old;    %if the complement exceedes the valid number for a city, don't change it

 174:             end

 175:             idx=strfind(solpair(:,2),cell2mat(new));

 176:             for k=1:size(solpair,1)

 177:                 if cell2mat(idx(k))==1

 178:                     solpair(k,2)=old;

 179:                     break 

 180:                 end

 181:             end

 182:             solpair(pos,2)=new;

 183:         end

 184:     end

 185:     mutsol=solpair;

 186: end

 187:  

 188: function bcomp=bincompl(binstring)

 189:     x=cell2mat(binstring);

 190:     y={};

 191:     for n=1:size(x,2)

 192:         y=strcat(y,{[num2str(xor(str2double(x(n)),1))]});

 193:     end

 194:     bcomp=y;

 195: end