MAT之ACA：利用ACA解決TSP優化最佳路徑問題

?

目錄

輸出結果

實現代碼

---

?

?

輸出結果

?

?

實現代碼

load citys_data.mat n = size(citys,1); D = zeros(n,n); for i = 1:nfor j = 1:nif i ~= j D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2));else D(i,j) = 1e-4; endend endm = 50; alpha = 1; beta = 5; rho = 0.1; Q = 1; Eta = 1./D; Tau = ones(n,n); Table = zeros(m,n); iter = 1; iter_max = 200; Route_best = zeros(iter_max,n); Length_best = zeros(iter_max,1); Length_ave = zeros(iter_max,1); while iter <= iter_max start = zeros(m,1);for i = 1:mtemp = randperm(n); start(i) = temp(1);endTable(:,1) = start; citys_index = 1:n; for i = 1:mfor j = 2:n tabu = Table(i,1:(j - 1)); allow_index = ~ismember(citys_index,tabu); allow = citys_index(allow_index); P = allow;for k = 1:length(allow) P(k) = Tau(tabu(end),allow(k))^alpha * Eta(tabu(end),allow(k))^beta;endP = P/sum(P); Pc = cumsum(P); target_index = find(Pc >= rand); target = allow(target_index(1)); Table(i,j) = target; endendLength = zeros(m,1); for i = 1:mRoute = Table(i,:); for j = 1:(n - 1) Length(i) = Length(i) + D(Route(j),Route(j + 1));endLength(i) = Length(i) + D(Route(n),Route(1));endif iter == 1[min_Length,min_index] = min(Length);Length_best(iter) = min_Length; Length_ave(iter) = mean(Length);Route_best(iter,:) = Table(min_index,:);else[min_Length,min_index] = min(Length);Length_best(iter) = min(Length_best(iter - 1),min_Length);Length_ave(iter) = mean(Length);if Length_best(iter) == min_LengthRoute_best(iter,:) = Table(min_index,:);elseRoute_best(iter,:) = Route_best((iter-1),:);endendDelta_Tau = zeros(n,n);for i = 1:mfor j = 1:(n - 1)Delta_Tau(Table(i,j),Table(i,j+1)) = Delta_Tau(Table(i,j),Table(i,j+1)) + Q/Length(i);endDelta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);endTau = (1-rho) * Tau + Delta_Tau;iter = iter + 1;Table = zeros(m,n); end[Shortest_Length,index] = min(Length_best); Shortest_Route = Route_best(index,:); disp(['最短距離:' num2str(Shortest_Length)]); disp(['最短路徑:' num2str([Shortest_Route Shortest_Route(1)])]);subplot(1,2,1); plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...[citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-'); grid on for i = 1:size(citys,1)text(citys(i,1),citys(i,2),[' ' num2str(i)]); end text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),' 起點'); text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),' 終點'); xlabel('城市位置橫坐標') ylabel('城市位置縱坐標') title(['ACA：利用ACA算法解決TSP優化路徑(最短距離:' num2str(Shortest_Length) ')—Jason niu']) subplot(1,2,2); plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r:') legend('最短距離','平均距離') xlabel('迭代次數') ylabel('距離') title('ACA：各代最短距離與平均距離對比—Jason niu')

?

相關文章
ACA：利用ACA解決TSP優化最佳路徑問題
?

?

總結

以上是生活随笔為你收集整理的MAT之ACA：利用ACA解决TSP优化最佳路径问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。