求解最小費(fèi)用流問(wèn)題的蟻群算法matlab程序

1、以下是解放軍信息工程大學(xué)一個(gè)老師編的 matlab 程序，請(qǐng)尊重原作者勞動(dòng)，引用時(shí)請(qǐng)注明 出處。我經(jīng)過(guò)修改增加了注釋?zhuān)呀?jīng)運(yùn)行過(guò)，無(wú)誤，functionR_best,L_best,L_ave,Shortest_Route,Shortest_Length=ACATSP(C,NC_max,m,Alpha,Beta,Rho ,Q)% 主要符號(hào)說(shuō)明% C n個(gè)城市的坐標(biāo)，n X2的矩陣% NC_max 最大迭代次數(shù)% m 螞蟻個(gè)數(shù)% Alpha 表征信息素重要程度的參數(shù)% Beta 表征啟發(fā)式因子重要程度的參數(shù)% Rho 信息素蒸發(fā)系數(shù)% Q 信息素增加強(qiáng)度系數(shù)% R_best 各代最佳路線(xiàn)% L_b

2、est 各代最佳路線(xiàn)的長(zhǎng)度 %=%第一步：變量初始化n=size(C,1);%n 表示問(wèn)題的規(guī)模(城市個(gè)數(shù))D=zeros(n,n);%D 表示完全圖的賦權(quán)鄰接矩陣for i=1:nfor j=1:nif i=jD(i,j)=(C(i,1)-C(j,1)A2+(C(i,2)-C(j,2)A2)P5;elseD(i,j)=eps; %i=j時(shí)不計(jì)算，應(yīng)該為 0，但后面的啟發(fā)因子要取倒數(shù)，用eps (浮點(diǎn)相對(duì)精度)表示endD(j,i)=D(i,j); % 對(duì)稱(chēng)矩陣endendEta=1./D; %Eta 為啟發(fā)因子，這里設(shè)為距離的倒數(shù)Tau=ones(n,n); %Tau 為信息素矩陣Tabu=

3、zeros(m,n); %存儲(chǔ)并記錄路徑的生成NC=1;% 迭代計(jì)數(shù)器，記錄迭代次數(shù)R_best=zeros(NC_max,n);% 各代最佳路線(xiàn)L_best=inf.*ones(NC_max,1); % 各代最佳路線(xiàn)的長(zhǎng)度L_ave=zeros(NC_max,1);% 各代路線(xiàn)的平均長(zhǎng)度while NC<=NC_max % 停止條件之一：達(dá)到最大迭代次數(shù)，停止%第二步：將m只螞蟻放到n個(gè)城市上Randpos=; % 隨即存取 for i=1:(ceil(m/n)Randpos=Randpos,randperm(n);endTabu(:,1)=(Randpos(1,1:m)' %

4、 此句不太理解？% 第三步： m 只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游 for j=2:n % 所在城市不計(jì)算for i=1:m visited=Tabu(i,1:(j-1); % 記錄已訪(fǎng)問(wèn)的城市，避免重復(fù)訪(fǎng)問(wèn) J=zeros(1,(n-j+1); % 待訪(fǎng)問(wèn)的城市P=J; % 待訪(fǎng)問(wèn)城市的選擇概率分布Jc=1;for k=1:nif length(find(visited=k)=0 % 開(kāi)始時(shí)置 0J(Jc)=k;Jc=Jc+1; % 訪(fǎng)問(wèn)的城市個(gè)數(shù)自加 1 end end%下面計(jì)算待選城市的概率分布for k=1:length(J)P(k)=(Tau(visited(e nd)

5、,J(k)AAIpha)*(Eta(visited(e nd),J(k)ABeta); endP=P/(sum(P);%按概率原則選取下一個(gè)城市Pcum=cumsum(P); %cumsum ，元素累加即求和 SeIect=find(Pcum>=rand); % 若計(jì)算的概率大于原來(lái)的就選擇這條路線(xiàn) to_visit=J(SeIect(1);Tabu(i,j)=to_visit;endendif NC>=2Tabu(1,:)=R_best(NC-1,:);end%第四步：記錄本次迭代最佳路線(xiàn)L=zeros(m,1); % 開(kāi)始距離為 0，m*1 的列向量 for i=1:mR=Ta

6、bu(i,:);for j=1:(n-1)L(i)=L(i)+D(R(j),R(j+1);% 原距離加上第j個(gè)城市到第j+1個(gè)城市的距離endL(i)=L(i)+D(R(1),R(n);% 一輪下來(lái)后走過(guò)的距離endL_best(NC)=min(L); % 最佳距離取最小 pos=find(L=L_best(NC);R_best(NC,:)=Tabu(pos(1),:); % 此輪迭代后的最佳路線(xiàn) L_ave(NC)=mean(L); % 此輪迭代后的平均距離 NC=NC+1 % 迭代繼續(xù)%第五步：更新信息素Delta_Tau=zeros(n,n); % 開(kāi)始時(shí)信息素為 n*n 的 0 矩陣f

7、or i=1:mfor j=1:(n-1) Delta_Tau(Tabu(i,j),Tabu(i,j+1)=Delta_Tau(Tabu(i,j),Tabu(i,j+1)+Q/L(i);%此次循環(huán)在路徑(i, j)上的信息素增量endDelta_Tau(Tabu(i,n),Tabu(i,1)=Delta_Tau(Tabu(i,n),Tabu(i,1)+Q/L(i); %此次循環(huán)在整個(gè)路徑上的信息素增量 endTau=(1-Rho).*Tau+Delta_Tau; % 考慮信息素?fù)]發(fā)，更新后的信息素 %第六步：禁忌表清零Tabu=zeros(m,n);% 直到最大迭代次數(shù)end%第七步：輸出結(jié)果

8、Pos=find(L_best=min(L_best); % 找到最佳路徑(非 0 為真) Shortest_Route=R_best(Pos(1),:) % 最大迭代次數(shù)后最佳路徑 Shortest_Length=L_best(Pos(1) % 最大迭代次數(shù)后最短距離 subplot(1,2,1)% 繪制第一個(gè)子圖形DrawRoute(C,Shortest_Route) % 畫(huà)路線(xiàn)圖的子函數(shù) subplot(1,2,2)% 繪制第二個(gè)子圖形plot(L_best) hold on % 保持圖形 plot(L_ave,'r') title(' 平均距離和最短距離 ')%標(biāo)題function DrawRoute(C,R)%= % DrawRoute.m% 畫(huà)路線(xiàn)圖的子函數(shù)% C Coordinate節(jié)點(diǎn)坐標(biāo)，由一個(gè) NX2的矩陣存儲(chǔ)% R Route 路線(xiàn)%=N=length(R); scatter(C(:,1),C(:,2);hold on plot(C(R(1),1),C(R(N),1),C(R(1),2),C(R(N),2)