%% -----------------------------------------------------------------
% TSP
% Input Parameters:
% poposize population szie
% GenMax maximum number of generation
% Pc crossover rate
% Pm mutation rate
% CityNum the number of city
%% input parameters
popsize = 40;
GenMax = 500;
Pc = 0.8;
Pm = 0.1;
CityNum = 20;
for ii=1:2:40
%% initial distance and coordinate
[dislist, Clist] = tsp(CityNum);
figure(ii)
%% random initial population
population = zeros(popsize, CityNum);
for i = 1 : popsize
population(i,:) = randperm(CityNum);
end
[~, cumulativeProbs] = calPopValue(population,dislist);
genNum = 1;
genMeanValue = zeros(genNum,1);
genMaxValue = zeros(genNum,1);
bestpath = zeros(popsize,CityNum);
newPop = zeros(popsize,CityNum);
while genNum < GenMax+1
for j = 1:2:popsize
SelChromos = select(cumulativeProbs);
CrossChros = cross(population, SelChromos,Pc);
newPop(j,:) = mut(CrossChros(1,:),Pm);
newPop(j+1,:) = mut(CrossChros(2,:), Pm);
end
population = newPop;
[PopValue, cumulativeProbs] = calPopValue(population,dislist);
[fmax, nmax] = max(PopValue);
genMeanValue(genNum) = 1/mean(PopValue);
genMaxValue(genNum) = 1/fmax;
bestChromo = population(nmax,:);
bestpath(genNum,:) = bestChromo;
drawTSP(Clist,bestChromo,genMaxValue(genNum),genNum,0);
genNum = genNum+1;
end
[bestValue,index] = min(genMaxValue);
drawTSP(Clist,bestpath(index,:),bestValue,index,1);
figure(ii+1)
% figure(2);
plot(genMaxValue,'r');
hold on;
plot(genMeanValue,'b');
grid;
title('搜索过程');
legend('最优解', '平均解');
fprintf('遗传算法得到的最短距离: %.2f\n', bestValue);
fprintf('遗传算法得到的最短路线');
disp(bestpath(index,:));
end
%% calculate the fitness of all chromosomes
function [chromoValues, cumulativeProbs] = calPopValue(population,dislist)
inpopsize = size(population,1);
chromoValues = zeros(inpopsize,1);
% calculate the fitness of each chromosome
for i = 1:inpopsize
chromoValues(i) = CalDist(dislist,population(i, :));
end
% the smaller the distance,the higher the probability of selection,so...
chromoValues = 1./chromoValues';
fsum = 0;
for i = 1:inpopsize
fsum = fsum + chromoValues(i)^15;
end
probs = zeros(inpopsize, 1);
for i = 1: inpopsize
probs(i) = chromoValues(i)^15 / fsum;
end
cumulativeProbs = zeros(inpopsize,1);
cumulativeProbs(1) = probs(1);
for i = 2 : inpopsize
cumulativeProbs(i) = cumulativeProbs(i - 1) + probs(i);
end
cumulativeProbs = cumulativeProbs';
end
%% select
function selectedChromoNums = select(cumulatedPro)
selectedChromoNums = zeros(2,1);
for i = 1 : 2
r = rand;
prand = cumulatedPro - r;
j = 1;
while prand(j) < 0
j = j + 1;
end
selectedChromoNums(i) = j;
if i == 2 && j == selectedChromoNums(i - 1)
r = rand;
prand = cumulatedPro - r;
j = 1;
while prand(j) < 0
j = j + 1;
end
end
end
end
%% cross
function CrossChros = cross(population,selChromoNums,crossProb)
length = size(population,2);
crossProbc = crossMuteOrNot(crossProb);
CrossChros(1,:) = population(selChromoNums(1),:);
CrossChros(2,:) = population(selChromoNums(2),:);
if crossProbc == 1
c1 = round(rand*(length-2))+1;
c2 = round(rand*(length-2))+1;
chb1 = min(c1,c2);
chb2 = max(c1,c2);
middle = CrossChros(1,chb1+1:chb2);
CrossChros(1,chb1+1:chb2)= CrossChros(2,chb1+1:chb2);
CrossChros(2,chb1+1:chb2)= middle;
for i = 1 : chb1
while find(CrossChros(1,chb1+1:chb2) == CrossChros(1,i))
location = find(CrossChros(1,chb1+1: chb2) == CrossChros(1,i));
y = CrossChros(2,chb1+location);
CrossChros(1,i) = y;
end
while find(CrossChros(2,chb1+1:chb2) == CrossChros(2,i))
location = find(CrossChros(2,chb1+1:chb2) == CrossChros(2,i));
y = CrossChros(1,chb1+location);
CrossChros(2,i) = y;
end
end
for i = chb2+1:length
while find(CrossChros(1,1:chb2) == CrossChros(1,i))
location = logical(CrossChros(1,1:chb2) == CrossChros(1,i));
y = CrossChros(2,location);
CrossChros(1,i) = y;
end
while find(CrossChros(2,1:chb2) == CrossChros(2,i))
location = logical(CrossChros(2,1:chb2) == CrossChros(2,i));
y = CrossChros(1,location);
CrossChros(2, i) = y;
end
end
end
end
%% mutation
function snnew = mut(chromo,muteProb)
length = size(chromo,2);
snnew = chromo;
muteProbm = crossMuteOrNot(muteProb);
if muteProbm == 1
c1 = round(rand*(length-2))+1;
c2 = round(rand*(length-2))+1;
chb1 = min(c1,c2);
chb2 = max(c1,c2);
x = chromo(chb1+1:chb2);
snnew(chb1+1:chb2) = fliplr(x);
end
end
%%
function crossProbc = crossMuteOrNot(crossMuteProb)
test(1:100) = 0;
l = round(100*crossMuteProb);
test(1:l) = 1;
n = round(rand*99)+1;
crossProbc = test(n);
end
%% calculate the fitness of each chromosome
% chromo------a chromosome,or a path
function chromoValue = CalDist(dislist,chromo)
DistanV = 0;
n = size(chromo,2);
for i = 1:(n - 1)
DistanV = DistanV+dislist(chromo(i),chromo(i+1));
end
DistanV = DistanV+dislist(chromo(n),chromo(1));
chromoValue = DistanV;
end
%% show
function drawTSP(Clist,route,genValue,genNum,isBestGen)
CityNum = size(Clist,1);
for i = 1:CityNum-1
plot([Clist(route(i),1),Clist(route(i+1),1)], [Clist(route(i),2),...
Clist(route(i+1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k',...
'MarkerFaceColor','g');
text(Clist(route(i),1),Clist(route(i),2),[' ', int2str(route(i))]);
text(Clist(route(i+1),1),Clist(route(i+1),2), [' ',...
int2str(route(i+1))]);
hold on;
end
plot([Clist(route(CityNum),1),Clist(route(1),1)],[Clist(route(CityNum),...
2),Clist(route(1),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k',...
'MarkerFaceColor','g');
title([num2str(CityNum),'城市TSP']);
if isBestGen == 0 && CityNum ~= 10
text(5, 5, ['第 ',int2str(genNum),' 代',' 最短距离为 ',...
num2str(genValue)]);
else
text(5, 5, ['最终搜索结果：最短距离 ',num2str(genValue),...
'， 在第 ',num2str(genNum),' 代达到']);
end
if CityNum == 10
if isBestGen == 0
text(0, 0, ['第 ',int2str(genNum),' 代',' 最短距离为 ',...
num2str(genValue)]);
else
text(0, 0, ['最终搜索结果：最短距离 ',num2str(genValue),...
'， 在第 ', num2str(genNum),' 代达到']);
end
end
hold off;
pause(0.005);
end
%%
function [Dis, City] = tsp(n)
Dis=zeros(n,n);
CityXY = [5.294 1.558;4.268 3.622;4.719 2.774;4.185 2.230;0.915 3.861;...
4.771 6.041;1.524 2.871;3.447 2.111;3.718 3.665;2.649 2.556;...
4.399 1.194;4.660 2.949;1.232 6.440;5.036 0.244;2.710 3.140;...
1.072 3.454;5.855 6.203;0.194 1.862;1.762 2.693;2.682 6.097];
for i = 1 : 20
for j = 1 : 20
Dis(i,j) = ((CityXY(i,1)-CityXY(j,1))^2+(CityXY(i,2)-CityXY(j,2))^2)^0.5;
end
end
City = CityXY;
end
评论0
最新资源