原理：
1.介紹：
摘自百度百科：遺傳算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。
2.名詞解析：
基因：用來表示個體的特徵，算法中簡化為城市的編號，例如1,2,3,10,9….
染色體：又叫做基因型個體，一定數量的個體組成種群（population）
（程序中我的初始設置是100，一般偶數對出現）
適應度：個體對環境的適應程度。程序中用該條染色體對應路線的距離作為適應度值。
自然選擇；採用輪盤賭的方式，適應度值越大那麼它在所佔的面積更大，越有可能被選擇後記錄下來。值越小則越有可能被淘汰。
簡單說來就是：好的個體被保留，壞的逐漸被淘汰，經過不斷的迭代逼近最好的結果。
(這裡另外有一個代溝的概念，子代的數量會變少)
交叉互換：基因的重組，把父代個體的部分結構加以替換重組，類似於生個小寶寶。
變異：對某些基因做變動,隨機互換路線中的兩個城市。
進化逆轉：隨機逆轉基因中的一段基因，如果距離更短該路線會被保留。
重新插入父代優秀個體到子代：因為子代會少一些，重新插入優秀個體保證下次迭代數目穩定。
3.算法流程：
1. 開始
2．建立種群（或者更新種群）
3．記錄上次迭代最優值、適應度值
4. 自然選擇
5. 交叉互換產生子代
6. 基因的變異
7. 進化逆轉
8. 重新插入優秀父代個體到子代
9. 動態路線展示（迭代次數未達到轉到第三步）
10. 結束
主函數：
----
%% GA遺傳算法用來解決TSP問題測試文件
clc;
clear %清屏清除工作區
close all;
%% 取得要處理的城市的坐標,作出初始圖
%position=load('景區經緯度.txt');
%這句可以讀入所需要處理的數據，以下採用的是隨機產生的坐標信息
t0=clock;
citys=[
1304 2312;
3639 1315;
4177 2244;
3712 1399;
3488 1535;
3326 1556;
3238 1229;
4196 1004;
4312 790;
4386 570;
3007 1970;
2562 1756;
2788 1491;
2381 1676;
1332 695;
3715 1678;
3918 2179;
4061 2370;
3780 2212;
3676 2578;
4029 2838;
4263 2931;
3429 1908;
3507 2367;
3394 2643;
3439 3201;
2935 3240;
3140 3550;
2545 2357;
2778 2826;
2370 2975
];
x = citys(:,1);
y = citys(:,2);
xlabel('經度'); %橫坐標
ylabel('緯度'); %縱坐標
title('TSP問題遺傳算法(GA)優化'); %圖片標題
grid on
%% 計算各個城市之間的距離
n = size(citys,1);
for i = 1:n
for j = 1:n
D(i,j) = sqrt((x(i)-x(j))^2 + (y(i)-y(j))^2); %距離公式
end
end
%% 算法的初始設置
POP_num = 100; %種群的數量
MAXiter = 300; %最大的迭代次數
pc = 0.8; %交叉概率
pm = 0.06; %變異概率
GAP = 0.9; %代溝(也就是選擇概率)
route_evo = zeros(MAXiter,n+1); %記錄每次迭代之後的最優路線進化
best_value = zeros(MAXiter,1);
Length_ave = zeros(MAXiter,1);
Route_long = zeros(POP_num,1);
%% 種群的初始化
global Chrom
Chrom = zeros(POP_num,n);
for i=1:POP_num
Chrom(i,:) = randperm(n); %隨機產生初始的種群
end
%% 記錄一個初始的隨機解後開始優化
%suijishu = unidrnd(n);
iter = 0;
times = 0;
while iter < MAXiter
for i = 1:POP_num
Route_long(i) = Routelength(D,Chrom(i,:)); %計算路線總長度
end
[route_best,best_index] = min(Route_long);
Length_ave(iter+1) = mean(Route_long); %每次迭代路線距離的平均值
best_value(iter+1) = route_best;
route_evo(iter+1,:) = [Chrom(best_index,:) Chrom(best_index,1)]; %記錄下這次的最優路線
Fit = 1./Route_long; %適應度值
%%選擇操作（個體的適應度值越大越有可能被選中）
select_num = max(floor(POP_num*GAP+0.6),2); %被選中的染色體數目
NEWChrom1 = Select(Fit,select_num);
%%交叉操作
NEWChrom2 = Cross(NEWChrom1, pc);
%%變異操作
NEWChrom2 = Mutate(NEWChrom2, pm);
%%進化逆轉操作
NEWChrom2 = Reverse(NEWChrom2, D);
%%重插入幾條優秀的父代基因到子代裡形成新種群
Chrom = Rein(Chrom, NEWChrom2,Route_long);
%%做一個動態的效果
if times >= 10
cla;
Route_all = route_evo(iter+1,:);
plot(citys(Route_all,1), citys(Route_all,2), 'bo-');
text(citys(Route_all(1),1),citys(Route_all(1),2),' 起點');
text(citys(Route_all(end-1),1),citys(Route_all(end-1),2),' 終點');
pause(0.1);
times = 0;
end
iter = iter + 1;
times = times + 1;
end
%% 命令窗口的結果顯示
Time_Cost=etime(clock,t0); %調用windows系統的時鐘進行時間差計算
disp(['環遊城市的最短距離:' num2str(best_value(end))]);
arrow = '%d ----> %d\n';
disp('最短路線如下所示：');
Route_print = route_evo(end,:);
for i=1:n
fprintf(arrow,Route_print(i),Route_print(i+1));
end
disp(['程序執行時間:' num2str(Time_Cost) '秒']);
%% 畫出最終結果圖
figure()
for i = 1 : n
scatter(x(i),y(i),'b'); %畫出散點圖
hold on
text(x(i)+1,y(i)+1,num2str(i)) %用text做好標記，
end
plot(citys(Route_print,1), citys(Route_print,2), 'bo-');
text(citys(Route_print(1),1),citys(Route_print(1),2),' 起點');
text(citys(Route_print(end-1),1),citys(Route_print(end-1),2),' 終點');
xlabel('經度'); %橫坐標
ylabel('緯度'); %縱坐標
title('最終結果圖'); %圖片標題
grid on
%% 畫出迭代過程曲線
figure()
subplot(1,2,1)
plot(best_value)
xlabel('迭代次數')
ylabel('最短距離收斂軌跡')
subplot(1,2,2)
plot(Length_ave)
xlabel('迭代次數')
ylabel('平均距離收斂軌跡')
%% 程序可以改進的地方還有很多，留個小疑問給大家
%如何再加一個跳出循環的條件：我的結果被保持了n次(具體數字根據迭代次數設置)提前跳出？
%我之前的視頻裡有答案，可以翻翻。當你會往程序裡加這個條件，那說明基本都弄懂了哦
----