1、機(jī)器學(xué)習(xí)作業(yè)（2013）第1頁共5頁機(jī)器學(xué)習(xí)作業(yè)（2013）題請以100個城市的旅行商冋題為例，與出使用20只人工螞蟻進(jìn)行旅次第四次目行商問題求解的基本步驟。數(shù)作業(yè)姓周璐學(xué)號53070711班7班名級正文Q:請以100個城市的旅行商問題為例，寫出使用20只人工螞蟻進(jìn)行旅行商問題求解的基本步驟。A:核心公式:W -匚亦麗刊亦卩Tat + 1) = (I - p) r,*垃(0 V(i,j)if arc (i, j) is used by ant k場）=0otherwise.是信息素濃度因子；是可見度因子，通常取為城市間距離的倒數(shù)；:-和用來控制信轉(zhuǎn)移概率敘）息素和可見度的相對重要性；Nk為螞蟻

2、k的可訪問城市集合 ；Q為常量。數(shù)據(jù)結(jié)構(gòu)：-信息素矩陣（ 100 X 100階，記錄信息素濃度）- 可見度矩陣（100X 100階，通常取為距離（i, j）的倒數(shù)）- 禁忌表Tabu （20 X 100階，記錄螞蟻k走過的城市）初始化：-20螞蟻隨機(jī)分布到100個城市環(huán)游：,上-仃）_丁曲）FT如一if i r V*-按照第一個核心公式計算-螞蟻依次選擇路徑直到返回出發(fā)點更新信息素濃度-按照第二個核心公式計算t+1時刻的信息素濃度停止條件-全部螞蟻選擇了同一條路線-算法運行到最大迭代次數(shù)旅行商問題代碼思路大體如下：/*/初始化蟻群 /*/m=20;/蟻群中螞蟻的數(shù)量，當(dāng)m接近或等于城市個數(shù) n

3、時，本算法可以在最少的迭代次數(shù)內(nèi)找到最優(yōu)解n=20;/表示TSP問題的規(guī)模，亦即城市的數(shù)量，這里為100D100100=;/表示城市完全地圖的賦權(quán)鄰接矩陣，記錄城市之間的距離Nc_max=200;/最大循環(huán)次數(shù)，即算法迭代的次數(shù)，亦即螞蟻出動的撥數(shù)（每撥螞蟻的數(shù)量都是20）alpha=1;/螞蟻在運動過程中所積累信息（即信息素）在螞蟻選擇路徑時的相對重要程度，alpha過大時，算法迭代到一定代數(shù)后將出現(xiàn)停滯現(xiàn)象beta=5;/啟發(fā)式因子在螞蟻選擇路徑時的相對重要程度rho=0.5;（0<rho<1）表示路徑上信息素的衰減系數(shù)（亦稱揮發(fā)系數(shù)、蒸發(fā)系數(shù)），1-rho表示信息素的持久性系

4、數(shù)Q=100;/螞蟻釋放的信息素量，對本算法的性能影響不大*第3頁共5頁機(jī)器學(xué)習(xí)作業(yè)（2013）第#頁共5頁機(jī)器學(xué)習(xí)作業(yè)（2013）/變量初始化*eta=1/D;phero mone=ones(n,n); /tabu_list=zeros( m,n);/啟發(fā)式因子，這里設(shè)為城市之間距離的倒數(shù)信息素矩陣，這里假設(shè)任何兩個城市之間路徑上的初始信 息素都為1禁忌表，記錄螞蟻已經(jīng)走過的城市，螞蟻在本次循環(huán)中不能再經(jīng)過這些城市。當(dāng)本次循環(huán)結(jié)束后，禁忌表被用來計 算螞蟻當(dāng)前所建立的解決方案，即經(jīng)過的路徑和路徑的長 度Nc=0; routh_best=zeros(Nc_max ,n); / len gth_

5、best=on es(Nc_max,1); / len gth_average=on es(Nc_max,1);/循環(huán)次數(shù)計數(shù)器各次循環(huán)的最短路徑各次循環(huán)最短路徑的長度各次循環(huán)所有路徑的平均長度第#頁共5頁機(jī)器學(xué)習(xí)作業(yè)（2013）第#頁共5頁機(jī)器學(xué)習(xí)作業(yè)（2013）這里i從0取到19,1:m表示隨著i 的增大而講tabu_list從隨機(jī)位置1初始化到位置 m將螞蟻放在城市上 之后的禁忌表，第i行表示第i只螞 蟻，第i行第一列元素表示第i只螞 蟻所在的初始城市while Nc<Nc_max/ 將m只螞蟻放在n個城市上ran d_positi on=;for (i=1;i<ceil(

6、m/n );i+)ran d_positi on=ran d_positi on,ran dperm (n); endtabu_list(i,0)=(ran d_positi on (1:m);/*/m只螞蟻按概率函數(shù)選擇下一座城市，在本次循環(huán)中完成各自的周游/*/for j=2 to nfor i=1 to mcity_visited=tabu_list(i,1:(j-1);city_rema in ed=zeros(1,( n-j+1); / probability=city_rema in ed; cr=1;for k=1 to n已訪問的城市。1:（j-1）表示從1到j(luò)-1待訪問的城市

7、/待訪問城市的訪問概率/for數(shù)是經(jīng)過此 for 循環(huán)后 city_remanied=1 3 5循環(huán)用于求待訪問的城市。比如如果城市個5,而已訪問的城市 city_visited=2 4,第4頁共5頁機(jī)器學(xué)習(xí)作業(yè)（2013）if len gth(fi nd(city_visited=k)=0 city_rema in ed(cr)=k;cr=cr+1;endend/*/for循環(huán)計算待訪問城市的訪問概率分布，此概率和兩個參數(shù)有關(guān)，一是螞蟻當(dāng)前所在城 市（即city_visited（end）和待訪問城市（即city_remained（k）路徑上的信息素,這兩者之間的啟發(fā)因子即距離的倒數(shù) /*/f

8、or k=1 to len gth(city_remai ned)probability(k)=(phero mon e(city_visited(e nd),city_rema in ed(k)Aalpa*(eta(city_visited(e nd),city_remai ned(k)Abeta;/即作業(yè)第一頁提到的核心公式endprobability=probability/sum(probability);/按概率選取下一個要訪問的城pcum=cumsum(probability); select=fi nd(pcum>=ran d);to_visit=city_remai ne

9、d(select(1); tabuist(i,j)=to_visit;endendif Nc>0tabuist(1,:)=routh_best(Nc,:);end/ 記錄本次循環(huán)的最佳路線total_le ngth=zeros(m,1);將上一代的最優(yōu)路徑（最優(yōu)解）保留下來, 保證上一代中的最適應(yīng)個體的信息不會丟失m只螞蟻在本次循環(huán)中分別所走過的路徑長度第#頁共5頁機(jī)器學(xué)習(xí)作業(yè)(2013)for i=1:mr=tabu_list(i,:);/取出第i只螞蟻在本次循環(huán)中所走的路徑for j=1:( n-1)total_length(i)=total_length(i)+D(r(j),r(j

10、+1);第 i 只螞蟻本次循環(huán)中從起點城市到終點城市所走過的路徑長度endtotal_le ngth(i)=total_le ngth(i)+D(r(1),r( n);/endlen gth_best(Nc+1)=min( total_le ngth);positi on=fin d(total_le ngth=le ngth_best(Nc+1); /routh_best(Nc+1,:)=tabuist(positio n(1),:); /len gth_average(Nc+1)=mea n( total_le ngth);/最終得到第i只螞蟻在本次 循環(huán)中所走過的路徑長度/把m只螞蟻在本

11、次循環(huán)中所 走路徑長度的最小值作為本次 循環(huán)中最短路徑的長度找到最短路徑的位置，即最 短路徑是第幾只螞蟻或哪幾 只螞蟻走出來的把第一個走出最短路徑的螞 蟻在本次循環(huán)中所走的路徑作 為本次循環(huán)中的最優(yōu)路徑計算本次循環(huán)中m只螞蟻所走路徑的平均長度Nc=Nc+1/ 更新信息素delta_phero mon e=zeros (n,n);for i=1:mfor j=1:( n-1)delta_phero mon e(tabu_list(i,j),tabu_list(i,j+1)=delta_phero mon e(ta bu_list(i,j),tabui_l ist(i,j+1)+Q/total_l

12、e ngth(i);/total_length(i)為第i只螞蟻在本次循環(huán)中所走過的路徑長度(蟻周系統(tǒng)區(qū)別于蟻密系統(tǒng)和蟻量系統(tǒng)的地方)enddelta_phero mon e(tabu_list(i, n),tabu_list(i,1)=delta_phero mon e(tabu_list(i, n),tabu_list(i,1)+Q/total_le ngth(i)；/整個循環(huán)過程，即作業(yè)第一頁的核心公式三end/ 至此把m只螞蟻在本次循環(huán)中在所有路徑上釋放的信息素已經(jīng)累加上去pherom on e=(1-rho)*pherom on e+delta_pheromo ne;本次循環(huán)后所有路

13、徑上的信息素*/禁忌表清零，準(zhǔn)備下一次循環(huán)，螞蟻在下一次循環(huán)中又可以自由地進(jìn)行選擇*第5頁共5頁機(jī)器學(xué)習(xí)作業(yè)(2013)tabu_list=zeros( m,n); end第#頁共5頁機(jī)器學(xué)習(xí)作業(yè)（2013）/*/輸出結(jié)果，繪制圖形，這部分若以經(jīng)過改動的初始化方式為準(zhǔn)，則不能繪出圖形，但是可 以將圖的路徑節(jié)點按順序輸出。/*/positi on=fin d(le ngth_best=min (le ngth_best);shortest_path=routh_best(positi on( 1),:)shortest_le ngth=le ngth_best(positi on (1)/繪制最

14、短路徑figure(1)set(gcf,'Name','Ant Colony OptimizationFigure of shortest_path','Color','r')N=le ngth(shortest_path);scatter(C(:,1),C(:,2),50,'filled');hold onplot(C(shortest_path(1),1),C(shortest_path(N),1),C(shortest_path(1),2),C(sho rtest_path(N),2)set(gca,'

15、;Color','g')hold onfor i=2:N plot(C(shortest_path(i-1),1),C(shortest_path(i),1),C(shortest_path(i-1),2),C(shortest_path(i),2)hold onend/繪制每次循環(huán)最短路徑長度和平均路徑長度figure(2)set(gcf,'Name','A ntColo nyOptimizati onFigure oflen gth_bestandlen gth_average','Color','r')plot(le ngth_best,'r')set(gca,'Color','g') hold onplot(le ngth_