問題定義：
巡回旅行商問題
給定一組n個城市和倆倆之間的直達距離，尋找一條閉合的旅程，使得每個城市剛好經過一次且總的旅行距離最短。
TSP問題也稱為貨郎擔問題，是一個古老的問題。最早可以追溯到1759年Euler提出的騎士旅行的問題。1948年，由美國蘭德公司推動，TSP成為近代組合優化領域的典型難題。
TSP是一個具有廣泛的應用背景和重要理論價值的組合優化問題。近年來，有很多解決該問題的較為有效的算法不斷被推出，例如Hopfield神經網絡方法，模拟退火方法以及遺傳算法方法等。
TSP搜尋空間随着城市數n的增加而增大,所有的旅程路線組合數為(n-1)!/2。在如此龐大的搜尋空間中尋求最優解，對于正常方法和現有的計算工具而言，存在着諸多計算困難。借助遺傳算法的搜尋能力解決TSP問題，是很自然的想法。
基本遺傳算法可定義為一個8元組：
- (SGA)=(C，E，P0，M，Φ，Г，Ψ，Τ)
- C ——個體的編碼方法，SGA使用固定長度二進制符号串編碼方法；
- E ——個體的适應度評價函數；
- P0——初始群體；
- M ——群體大小，一般取20—100；
- Ф——選擇算子，SGA使用比例算子；
- Г——交叉算子，SGA使用單點交叉算子；
- Ψ——變異算子，SGA使用基本位變異算子；
- Т——算法終止條件，一般終止進化代數為100—500；
問題的表示
- 對于一個實際的待優化問題，首先需要将其表示為适合于遺傳算法操作的形式。用遺傳算法解決TSP，一個旅程很自然的表示為n個城市的排列，但基于二進制編碼的交叉和變異操作不能适用。
- 路徑表示是表示旅程對應的基因編碼的最自然，最簡單的表示方法。它在編碼，解碼，存儲過程中相對容易了解和實作。例如：旅程(5-1-7-8-9-4-6-2-3)可以直接表示為(5 1 7 8 9 4 6 2 3)。
産生初始種群
- 一是完全随機産生，它适合于對問題的解無任何先驗知識的情況。随機性較強，因而也較公正。
- 二是某些先驗知識可轉變為必須滿足的一組要求，然後在滿足這些要求的解中在随機地選取樣本。這樣選擇初始種群可使遺傳算法更快的達到最優解。種群有一定的目标性和代表性，但取例不如完全随機的廣泛，而且先驗知識是否可靠也是一個問題。
适應度函數
- 遺傳算法在進化搜尋中基本不利用外部資訊,僅以适應度函數為依據,利用種群中每個個體的适應度值來進行搜尋。TSP的目标是路徑總長度為最短，路徑總長度的倒數就可以為TSP的适應度函數：
選擇
一般地說，選擇将使适應度較大(優良)個體有較大的存在機會，而适應度較小(低劣)的個體繼續存在的機會也較小。簡單遺傳算法采用賭輪選擇機制，令Σfi表示群體的适應度值之總和，fi表示種群中第i個染色體的适應度值，它産生後代的能力正好為其适應度值所占份額fi／Σfi。
交叉
基于路徑表示的編碼方法，要求一個個體的染色體編碼中不允許有重複的基因碼，也就是說要滿足任意一個城市必須而且隻能通路一次的限制。基本遺傳算法的交叉操作生成的個體一般不能滿足這一限制條件。
部分比對交叉操作要求随機選取兩個交叉點，以便确定一個比對段，根據兩個父個體中兩個交叉點之間的中間段給出的映射關系生成兩個子個體。
變異
遺傳算法解決TSP 問題基于二進值編碼的變異操作不能适用，不能夠由簡單的變量的翻轉來實作
在TSP問題中個體的編碼是一批城市的序列，随機的在這個序列抽取兩個城市，然後交換他們的位置。這樣就實作了個體編碼的變異，算法如下：
- 産生兩個0到1之間的随機實數；
- 将這兩個随機實數轉化為0到n(城市數)-1之間的随機整數；
- 将這兩個随機整數指代的城市進行交換；
流程圖
代碼
主函數代碼：
clear;
clc;
tStart= tic;% 算法計時器
%%%%%%%%%%%%自定義參數%%%%%%%%%%%%%
[cityNum,cities]= Read('dsj1000.tsp');
cities= cities';
%cityNum=100;
maxGEN = 1000;
popSize = 100; % 遺傳算法種群大小
crossoverProbabilty = 0.9; %交叉機率
mutationProbabilty = 0.1; %變異機率
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
gbest = Inf;
%随機生成城市位置
%cities=rand(2,cityNum)*100;%100是最遠距離
%計算上述生成的城市距離
distances = calculateDistance(cities);
%生成種群，每個個體代表一個路徑
pop = zeros(popSize, cityNum);
for i=1:popSize
pop(i,:) = randperm(cityNum);
end
offspring = zeros(popSize,cityNum);
%儲存每代的最小路勁便于畫圖
minPathes = zeros(maxGEN,1);
%GA算法
for gen=1:maxGEN
% 計算适應度的值，即路徑總距離
[fval, sumDistance, minPath, maxPath] = fitness(distances, pop);
% 輪盤賭選擇
tournamentSize=4; %設定大小
for k=1:popSize
% 選擇父代進行交叉
tourPopDistances=zeros( tournamentSize,1);
for i=1:tournamentSize
randomRow = randi(popSize);
tourPopDistances(i,1) = sumDistance(randomRow,1);
end
% 選擇最好的，即距離最小的
parent1 = min(tourPopDistances);
[parent1X,parent1Y] = find(sumDistance==parent1,1, 'first');
parent1Path = pop(parent1X(1,1),:);
for i=1:tournamentSize
randomRow = randi(popSize);
tourPopDistances(i,1) = sumDistance(randomRow,1);
end
parent2 = min(tourPopDistances);
[parent2X,parent2Y] = find(sumDistance==parent2,1, 'first');
parent2Path = pop(parent2X(1,1),:);
subPath = crossover(parent1Path, parent2Path, crossoverProbabilty);%交叉
subPath = mutate(subPath, mutationProbabilty);%變異
offspring(k,:) = subPath(1,:);
minPathes(gen,1) = minPath;
end
fprintf('代數:%d 最短路徑:%.2fKM \n', gen,minPath);
% 更新
pop= offspring;
% 畫出目前狀态下的最短路徑
ifminPath< gbest
gbest= minPath;
paint(cities,pop,gbest,sumDistance,gen);
end
end
figure
plot(minPathes,'MarkerFaceColor','red','LineWidth',1);
title('收斂曲線圖(每一代的最短路徑)');
set(gca,'ytick',500:100:5000);
ylabel('路徑長度');
xlabel('疊代次數');
gridon
tEnd= toc(tStart);
fprintf('時間:%d 分 %f 秒.\n',floor(tEnd/60),rem(tEnd,60));
function[distances]= calculateDistance(city)
%計算距離
[~,col]= size(city);
distances= zeros(col);
fori=1:col
forj=1:col
distances(i,j)= distances(i,j)+ sqrt((city(1,i)-city(1,j))^2+ (city(2,i)-city(2,j))^2 );
end
end
end
function[childPath]= crossover(parent1Path,parent2Path,prob)
%交叉
random= rand();
ifprob>= random
[l,length]= size(parent1Path);
childPath= zeros(l,length);
setSize= floor(length/2)-1;
offset= randi(setSize);
fori=offset:setSize+offset-1
childPath(1,i)= parent1Path(1,i);
end
iterator= i+1;
j= iterator;
whileany(childPath== 0)
ifj> length
j= 1;
end
ifiterator> length
iterator= 1;
end
if~any(childPath== parent2Path(1,j))
childPath(1,iterator)= parent2Path(1,j);
iterator= iterator+ 1;
end
j= j+ 1;
end
else
childPath= parent1Path;
end
end
function[fitnessvar,sumDistances,minPath,maxPath]= fitness(distances,pop)
%計算整個種群的适應度值
[popSize,col]= size(pop);
sumDistances= zeros(popSize,1);
fitnessvar= zeros(popSize,1);
fori=1:popSize
forj=1:col-1
sumDistances(i)= sumDistances(i)+ distances(pop(i,j),pop(i,j+1));
end
end
minPath= min(sumDistances);
maxPath= max(sumDistances);
fori=1:length(sumDistances)
fitnessvar(i,1)=(maxPath- sumDistances(i,1)+0.000001)/ (maxPath-minPath+0.00000001);
end
end
function[mutatedPath]= mutate(path,prob)
%對指定的路徑利用指定的機率進行更新
random= rand();
ifrandom<= prob
[l,length]= size(path);
index1= randi(length);
index2= randi(length);
%交換
temp= path(l,index1);
path(l,index1)= path(l,index2);
path(l,index2)=temp;
end
mutatedPath= path;
end
function[output_args]= paint(cities,pop,minPath, totalDistances, gen)
gNumber=gen;
[~,length]= size(cities);
xDots= cities(1,:);
yDots= cities(2,:);
%figure(1);
title('GA TSP');
plot(xDots,yDots,'p','MarkerSize',14,'MarkerFaceColor','blue');
xlabel('經度');
ylabel('緯度');
axisequal
holdon
[minPathX,~]= find(totalDistances==minPath,1,'first');
bestPopPath= pop(minPathX,:);
bestX= zeros(1,length);
bestY= zeros(1,length);
forj=1:length
bestX(1,j)= cities(1,bestPopPath(1,j));
bestY(1,j)= cities(2,bestPopPath(1,j));
end
title('GA TSP');
plot(bestX(1,:),bestY(1,:),'red','LineWidth',1.25);
legend('城市','路徑');
axisequal
gridon
%text(5,0,sprintf('疊代次數: %d 總路徑長度: %.2f',gNumber, minPath),'FontSize',10);
drawnow
holdoff
end
function[n_citys,city_position]= Read(filename)
fid= fopen(filename,'rt');
location=[];
A= [12];
tline= fgetl(fid);
whileischar(tline)
if(strcmp(tline,'NODE_COORD_SECTION'))
while~isempty(A)
A=fscanf(fid,'%f',[3,1]);
ifisempty(A)
break;
end
location=[location;A(2:3)'];
end
end
tline = fgetl(fid);
if strcmp(tline,'EOF')
break;
end
end
[m,n]=size(location);
n_citys= m;
city_position=location;
fclose(fid);
end
結果
測試資料：
初始态：
終态：
收斂曲線：
可以看到，當城市數量适中時，疊代500次最短路徑長度有收斂的趨勢。
當城市數目較多時
疊代500次，仍然不收斂，可能的問題是陷入了局部最優解。
總結與觀點
難點是交叉算法的設計，由于TSP問題和一般的NP問題不一樣，每個個體的每個次元具有唯一性，是以在交叉的時候要注意不能有重複的值。本次實驗采用的是部分比對交叉，先從第一個父代選出一個偏移量，從偏移量後的部分點加入到子代，接下來從第二個父代選擇第一代沒有選擇的部分點移到子代中。
當城市數量較多時，大于50個城市，疊代多次，GA仍然不收斂，可能的問題是陷入了局部最優解，是以對GA算法進行改進怡跳出局部最優解，可以采用類似于PSO或者蟻群算法的思想。
資料集下載下傳
https://github.com/xyjigsaw/Dataset
轉載自：
https://www.omegaxyz.com/2019/01/21/matlab-tsp-all/
作者：OmegaXYZ
https://www.omegaxyz.com