【Matlab學習筆記】遺傳演算法

02-22

遺傳演算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。遺傳演算法也是計算機科學人工智慧領域中用於解決最優化的一種搜索啟發式演算法，是進化演算法的一種。這種啟發式通常用來生成有用的解決方案來優化和搜索問題。

下面在Matlab中使用遺傳演算法解決最優路線規劃問題。

假定一架飛機從A點出發，依次飛過40個點，視察該40個點是否發生火災，然後返回A點。已知A點和39個巡邏點的經緯度，求規劃一個最短巡邏路線。

已知A點的經緯度是：E70，N40.

其他40個點的經緯度為：

代碼如下：

%%遺傳演算法，計算N個城市之間的巡查最佳線路
load(tuihuo.mat);
A1 = [70,40];
B =[A1;A;A1] ; %初始基地的位置與全部過路點形成一個環線
d = zeros(42); %初始化距離d的矩陣
B = B.*pi/180;
for i = 1:41
for j = i+1:42
d(i,j) = 6370*acos(cos(B(i,1)-B(j,1))*cos(B(i,2))*cos(B(j,2))+sin(B(i,2))*sin(B(j,2)));
%d(i,j) = ((B(i,1)-B(j,1))^2 + (B(i,2) - B(j,2))^2)^0.5

end
end
d = d + d;
w = 50; g = 100; %遺傳50個族群，一共100代
rand(state,sum(clock));%初始化隨機過程
for k = 1:w
c = randperm(40);%產生40的隨機序列
c1 = [1,c+1,42];
for t = 1:42 %該層循環是修改層
flag = 0; %修改層退出的標誌

for m = 1:40
for n = m+2:41
if d(c1(m),c1(n))+d(c1(m+1),c1(n+1)) < d(c1(m),c1(m+1))+d(c1(n),c1(n+1))
c1(m+1:n) = c1(n:-1:m+1); flag = 1;%修改這個族群
end
end
end
if flag == 0
J(k,c1) = 1:42; %記錄較好的族群然後退出當前循環
break;

end
end
end
J(:,1) = 0;J = J/42;
for k = 1:g %該層循環進行遺傳演算法操作
A = J; %交配產生的子代B的初始染色體,A為全部族群
c = randperm(w);%產生交叉染色體配對
for i = 1:2:w
F = 2+floor(40*rand(1));
temp = A(c(i),[F:42]); %交叉操作

A(c(i),[F:42]) = A(c(i+1),[F:42]); %選擇的單數族c（i）與雙數族c（i+1)雜交
A(c(i+1),F:42) = temp;
end
by = [];
while ~length(by)
by = find(rand(1,w)<0.1);
end
C = A(by,:); %產生變異的初始染色體
for j = 1:length(by)
bw = sort(2+floor(40*rand(1,3))); %產生變異的3個地址

C(j,:) = C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:42]); %交換位置
end
G = [J;A;C] ;%混合父子兩代
[SG,ind1] = sort(G,2);
num = size(G,1);long = zeros(1,num);
for j = 1:num
for i = 1:41
long(j) = long(j)+d(ind1(j,i),ind1(j,i+1)); %計算每條路徑的長度
end
end

[slong,ind2] = sort(long);
J = G(ind2(1:w),:)
end
path = ind1(ind2(1),:);flong = slong(1);
xx = B(path,1);yy = B(path,2);
plot(xx,yy,.-);

得到結果如下：