遺傳算法和蟻群算法的比較

1、精選優(yōu)質文檔-傾情為你奉上全局優(yōu)化報告遺傳算法和蟻群算法的比較姓 名：鄭 玄 玄學 號：班 級：碩 20411 遺傳算法1.1 遺傳算法的發(fā)展歷史遺傳算法是一種模擬自然選擇和遺傳機制的尋優(yōu)方法。20世紀60年代初期，Holland教授開始認識到生物的自然遺傳現(xiàn)象與人工自適應系統(tǒng)行為的相似性。他認為不僅要研究自適應系統(tǒng)自身，也要研究與之相關的環(huán)境。因此，他提出在研究和設計人工自適應系統(tǒng)時，可以借鑒生物自然遺傳的基本原理，模仿生物自然遺傳的基本方法。1967年，他的學生Bagley在博士論文中首次提出了“遺傳算法”一詞。到70年代初，Holland教授提出了“模式定理”，一般認為是遺傳算法的基本定

2、理，從而奠定了遺傳算法的基本理論。1975年，Holland出版了著名的自然系統(tǒng)和人工系統(tǒng)的自適應性，這是第一本系統(tǒng)論述遺傳算法的專著。因此，也有人把1975年作為遺傳算法的誕生年。1985年，在美國召開了第一屆兩年一次的遺傳算法國際會議，并且成立了國際遺傳算法協(xié)會。1989年，Holland的學生Goldberg出版了搜索、優(yōu)化和機器學習中的遺傳算法，總結了遺傳算法研究的主要成果，對遺傳算法作了全面而系統(tǒng)的論述。一般認為，這個時期的遺傳算法從古典時期發(fā)展了現(xiàn)代階段，這本書則奠定了現(xiàn)代遺傳算法的基礎。遺傳算法是建立在達爾文的生物進化論和孟德爾的遺傳學說基礎上的算法。在進化論中，每一個物種在不斷

3、發(fā)展的過程中都是越來越適應環(huán)境，物種每個個體的基本特征被后代所繼承，但后代又不完全同于父代，這些新的變化，若適應環(huán)境，則被保留下來；否則，就將被淘汰。在遺傳學中認為，遺傳是作為一種指令遺傳碼封裝在每個細胞中，并以基因的形式包含在染色體中，每個基因有特殊的位置并控制某個特殊的性質。每個基因產(chǎn)生的個體對環(huán)境有一定的適應性。基因雜交和基因突變可能產(chǎn)生對環(huán)境適應性強的后代，通過優(yōu)勝劣汰的自然選擇，適應值高的基因結構就保存下來。遺傳算法就是模仿了生物的遺傳、進化原理，并引用了隨機統(tǒng)計原理而形成的。在求解過程中，遺傳算法從一個初始變量群體開始，一代一代地尋找問題的最優(yōu)解，直到滿足收斂判據(jù)或預先假定的迭代次

4、數(shù)為止。遺傳算法的應用研究比理論研究更為豐富，已滲透到許多學科，并且?guī)缀踉谒械目茖W和工程問題中都具有應用前景。一些典型的應用領域如下：（1）復雜的非線性最優(yōu)化問題。對具體多個局部極值的非線性最優(yōu)化問題，傳統(tǒng)的優(yōu)化方法一般難于找到全局最優(yōu)解；而遺傳算法可以克服這一缺點，找到全局最優(yōu)解。（2）復雜的組合優(yōu)化或整數(shù)規(guī)劃問題。大多數(shù)組合優(yōu)化或整數(shù)規(guī)劃問題屬于NP難問題，很難找到有效的求解方法；而遺傳算法即特別適合解決這一類問題，能夠在可以接受的計算時間內求得滿意的近似最優(yōu)解，如著名的旅行商問題、裝箱問題等都可以用遺傳算法得到滿意的解。（3）工程應用方面。工程方法的應用是遺傳算法的一個主要應用領域，如

5、管道優(yōu)化設計、通風網(wǎng)絡的優(yōu)化設計、飛機外型設計、超大規(guī)模集成電路的布線等。（4）計算機科學。遺傳算法廣泛應用于計算機科學的研究，如用于圖像處理和自動識別、文檔自動處理、VLSI設計等。（5）生物學。遺傳算法起源于對生物和自然現(xiàn)象的模擬，現(xiàn)在又反過來用于生物領域的研究，如利用遺傳算法進行生物信息學的研究等。（6）社會科學。遺傳算法在社會科學的許多領域也有廣泛應用，如人類行為規(guī)范進化過程的模擬、人口遷移模型的建立等（7）經(jīng)濟領域。經(jīng)濟學領域也用到遺傳算法。例如，國民經(jīng)濟預測模型、市場預測模型和期貨貿易模型等。遺傳算法與神經(jīng)網(wǎng)絡相結合正成功地被應用于從時間序列分析來進行財政預算等。1.2 遺傳算法的

6、基本原理遺傳算法是一種基于自然選擇和群體遺傳機制的搜索算法，它模擬了自然選擇和自然遺傳過程中的繁殖、雜交和突變現(xiàn)象。在利用遺傳算法求解問題時，問題的每個可能的解都被編碼成一個“染色體”，即個體，若干個個體構成了群體（所有可能解）。在遺傳算法開始時，總是隨機地產(chǎn)生一些個體（即初始解）。根據(jù)預定的目標函數(shù)對每個個體進行評估，給出了一個適應度值?；诖诉m應度值，選擇個體用來復制下一代。選擇操作體現(xiàn)了“適者生存”的原理，“好”的個體被選擇用來復制，而“壞”的個體則被淘汰。然后選擇出來的個體經(jīng)過交叉和變異算子進行再結合生成新的一代。這一群新個體由于繼承了上一代的一些優(yōu)良性狀，因而在性能上要優(yōu)于上一代，這

7、樣逐步朝著更優(yōu)解的方向進化。因此，遺傳算法可以看成是一個由可行解組成的群體逐步進化的過程。圖給出了簡單遺傳算法的基本過程。下面介紹遺傳算法的編碼及基本遺傳操作過程。1.2.1 編碼利用遺傳算法求解問題時，首先要確定問題的目標函數(shù)和變量，然后對變量進行編碼。這樣做主要是因為在遺傳算法中，問題的解是用數(shù)字串來表示的，而且遺傳算子也是直接對串進行操作的。編碼方式可以分為二進制編碼和實數(shù)編碼。若用二進制數(shù)表示個體，則將二進制數(shù)轉化為十進制數(shù)的解碼公式可以為其中，為某個個體的第段，每段段長都為，每個都是0或者1，和是第段分量的定義域的兩個端點。1.2.2 遺傳操作遺傳操作是模擬生物基因的操作，它的任務就

8、是根據(jù)個體的適應度對其施加一定的操作，從而實現(xiàn)優(yōu)勝劣汰的進化過程。從優(yōu)化搜索的角度看，遺傳操作可以使問題的解逐代的優(yōu)化，逼近最優(yōu)解。遺傳操作包括以下三個基本遺傳算子：選擇、交叉、變異。選擇和交叉基本上完成了遺傳算法的大部分搜索功能，變異增加了遺傳算法找到最接近最優(yōu)解的能力。1. 選擇選擇是指從群體中選擇優(yōu)良的個體并淘汰劣質個體的操作。它建立在適應度評估的基礎上。適應度越大的個體，被選擇的可能性就越大，它的“子孫”在下一代的個數(shù)就越多。選擇出來的個體被放入配對庫中。目前常用的選擇方法有輪賭盤方法（也稱適應度比例法）、最佳個體保留法、期望值法、排序選擇法、競爭法、線性標準化方法等。2. 交叉交叉是

9、指把兩個父代個體的部分結構加以替換重組而生成新個體的操作，交叉的目的是為了能夠在下一代產(chǎn)生新的個體。通過交叉操作，遺傳算法的搜索能力得以飛躍性的提高。交叉是遺傳算法獲得新優(yōu)良個體的最重要的手段。交叉操作是按照一定的交叉概率在配對庫中隨機地選取兩個個體進行的。交叉的位置也是隨機確定的。交叉概率的值一般取得很大，為0.60.9。3. 變異變異就是以很小的變異概率隨機地改變群體中個體的某些基因的值。變異操作的基本過程是：產(chǎn)生一個之間的隨機數(shù)，如果，則進行變異操作。變異操作本身是一種局部隨機搜索，與選擇、交叉算子結合在一起，能夠避免由于選擇和交叉算子而引起的某些信息的永久性丟失，保證了遺傳算法的有效性

10、，使遺傳算法具有局部的隨機搜索能力，同時使得遺傳算法能夠保持群體的多樣性，以防止出現(xiàn)未成熟收斂。變異操作是一種防止算法早熟的措施。在變異操作中，變異概率不能取值太大，如果，遺傳算法就退化為隨機搜索，而遺傳算法的一些重要的數(shù)學特性和搜索能力也就不復存在了。1.3 基本步驟遺傳算法的基本步驟如下：1）在一定編碼方案下，隨機產(chǎn)生一個初始種群；2）用相應的解碼方法，將編碼后的個體轉換成問題空間的決策變量，并求得個體的適應值；3）按照個體適應值的大小，從種群中選出適應值較大的一些個體構成交配池；4）由交叉和變異這兩個遺傳算子對交配池中的個體進行操作，并形成新一代的種群；5）反復執(zhí)行步驟24，直至滿足收斂

11、判據(jù)為止。使用遺傳算法需要決定的運行參數(shù)有：編碼串長度、種群大小、交叉和變異概率。編碼串長度優(yōu)優(yōu)化問題所要求的求解精度決定。種群大小表示種群中所含個體的數(shù)量，種群較小時，可提高遺傳算法的運算速度，但卻降低了群體的多樣性，可能找不到最優(yōu)解；種群較大時，又會增加計算量，使遺傳算法的運行效率降低。一般取種群數(shù)目為20100.交叉概率控制著交叉操作的頻率，由于交叉操作是遺傳算法中產(chǎn)生新個體的主要方法，所以交叉概率通常應取較大值；但若過大的話，又可能破壞群體的優(yōu)良模式。一般取0.40.99.變異概率也是影響新個體產(chǎn)生的一個因素，變異概率小，產(chǎn)生新個體少；變異概率太大，又會使遺傳算法變成隨機搜索。一般取變

12、異概率為0.00010.1.遺傳算法常采用的收斂判據(jù)有：規(guī)定遺傳代數(shù)：連續(xù)幾次得到的最優(yōu)個體的適應值沒有變化或變化很小等。1.4 用MATLAB實現(xiàn)遺傳算法MATLAB是Matwork公司的產(chǎn)品，是一個功能強大的數(shù)學軟件，其優(yōu)秀的數(shù)值計算能力使其在工業(yè)界和學術界的使用率都非常高。MATLAB還十分便于使用，它以直觀、簡潔并符合人們思維習慣的代碼給用戶提供了一個非常友好的開發(fā)環(huán)境。利用MATLAB處理矩陣運算的強大功能來編寫遺傳算法程序有著巨大的優(yōu)勢。1.4.1編碼遺傳算法不對優(yōu)化問題的實際決策變量進行操作，所以應用遺傳算法首要的問題是通過編碼將決策變量表示成串結構數(shù)據(jù)。本文中我們采用最常用的二

13、進制編碼方案，即用二進制數(shù)構成的符號串來表示一個個體，用下面的encoding函數(shù)來實現(xiàn)編碼并產(chǎn)生初始種群。function bin_gen,bits=encoding(min_var,max_var,scale_var,popsize)bits=ceil(log2(max_var-min_var)./scale_var);bin_gen=round(rand(popsize,sum(bits);end在上面的代碼中，首先根據(jù)各決策變量的下界（min_var）、上界（max_var）及其搜索精度scale_var來確定表示各決策變量的二進制串的長度bits，然后隨機產(chǎn)生一個種群大小為popsi

14、ze的初始種群bit_gen。編碼后的實際搜索精度為scale_dec=(max_var-min_var)/(2bits-1)，該精度會在解碼時用到。1.4.2解碼解碼后的個體構成的種群bin_gen必須經(jīng)過解碼，以轉換成原問題空間的決策變量構成的種群var_gen，方能計算相應的適應值。我們用下面的代碼實現(xiàn)。function var_gen,fitness=decoding(funname,bin_gen,bits,min_var,max_var)num_var=length(bits);popsize=size(bin_gen,1);scale_dec=(max_var-min_var).

15、/(2.bits-1);bits=cumsum(bits);bits=0 bits;for i=1:num_var bin_vari=bin_gen(:,bits(i)+1:bits(i+1); vari=sum(ones(popsize,1)*2.(size(bin_vari,2)-1:-1:0).*bin_vari,2).*scale_dec(i)+min_var(i);endvar_gen=var1,:;for i=1:popsize fitness(i)=eval(funname,'(var_gen(i,:)');endend解碼函數(shù)的關鍵在于先由二進制數(shù)求得對應的十進

16、制數(shù)D，并根據(jù)下式求得實際決策變量值X：1.4.3選擇選擇過程是利用解碼后求得的各個適應值大小，淘汰一些較差個體而選出一些比較優(yōu)良的個體，以進行下一步的交叉和變異操作。選擇算子的程序如下：function evo_gen,best_indiv,best_var,max_fitness=selection(old_gen,fitness,var_gen)popsize=length(fitness);max_fitness,index1=max(fitness);min_fitness,index2=min(fitness);best_indiv=old_gen(index1,:);best_v

17、ar=var_gen(index1);index=1:popsize;index(index1)=0;index(index2)=0;index=nonzeros(index);evo_gen=old_gen(index,:);evo_fitness=fitness(index);evo_popsize=length(index);ps=evo_fitness/sum(evo_fitness);pscum=transpose(cumsum(ps);r=rand(1,evo_popsize);selected=sum(pscum*ones(1,evo_popsize)<ones(evo_p

18、opsize,1)*r)+1;evo_gen=evo_gen(selected,:);end在該算子中，采用了最優(yōu)保存策略和比例選擇法相結合的思路，即首先找出當前群體中適應值最高和最低的個體，將最佳個體best_indiv保存并用其替換掉最差個體。為保證當前最佳個體不被交叉、變異操作所破壞，允許其不參與交叉和變異而直接進入下一代。然后將剩下的個體evo_gen按比例選擇法進行操作。所謂比例選擇法，也叫賭輪算法，是指個體被選中的概率與該個體的適應值大小成正比。將這兩種方法想結合的目的是：在遺傳操作中，不僅能不斷提高群體的平均適應值，而且能保證最佳個體的適應值不減小。1.4.4交叉下面采用單點交叉

19、的方法來實現(xiàn)交叉算子，即按選擇概率PC在兩兩配對的個體編碼串cpairs中隨機設置一個交叉點cpoints，然后在該點相互交換兩個配對個體的部分基因，從而形成兩個新的個體。交叉算子的程序如下：function new_gen=crossover(old_gen,pc)nouse,mating=sort(rand(size(old_gen,1),1);mat_gen=old_gen(mating,:);pairs=size(mat_gen,1)/2;bits=size(mat_gen,2);cpairs=rand(pairs,1)<pc;cpoints=randint(pairs,1,1,

20、bits);cpoints=cpairs.*cpoints;for i=1:pairs new_gen(2*i-1 2*i,:)=mat_gen(2*i-1 2*i,1:cpoints(i) mat_gen(2*i 2*i-1,cpoints(i)+1:bits);endend1.4.5變異對于二進制的基因串而言，變異操作就是按照變異概率pm隨機選擇變異點mpoints，在變異點處將其位取反即可。變異算子的實現(xiàn)過程如下：function new_gen=mutation(old_gen,pm)mpoints=find(rand(size(old_gen)<pm);new_gen=old_

21、gen;new_gen(mpoints)=1-old_gen(mpoints);1.5 應用實例上述程序已經(jīng)考慮了多參數(shù)編碼問題，可以用于搜索多變量函數(shù)的最優(yōu)解。為簡單起見，下面僅以一個單變量函數(shù)為例，來驗證所編遺傳算法程序的全局尋優(yōu)能力。設函數(shù)為：，函數(shù)特性如圖1所示。圖1 函數(shù)特性示意圖取種群大小popsize=40，搜索精度scale_var=0.0001，交叉概率pc=0.85，變異概率pm=0.05。圖2和圖3是某一次運算遺傳40代后最佳個體和最佳適應值的變化情況。圖2 最佳個體的變化情況圖3 最佳個體適應值的增長情況由于采用了最優(yōu)保存策略，所以在圖3中未看到最佳個體適應值減少的現(xiàn)象

22、。由圖2可見：在前三代種群中適應值最大的個體解碼后的值為7.8681，落在函數(shù)的一個局部極值處。但是搜索并沒有在此處停滯，很快就躍到了另一個更大的極值點7.8538附近。搜索繼續(xù)，經(jīng)過幾次跳躍，我們發(fā)現(xiàn)在7.85附近搜索多次后，連續(xù)幾次得到的最優(yōu)個體的適應值變化很小，可以認為找到全局最大值。全局最大值點為7.8567，最大值為24.8554。下列程序為主函數(shù)。%Exampleclear;clc;close;popsize=40;%種群的個體個數(shù)scale_var=0.0001;%搜索精度pc=0.85;%交叉概率pm=0.05;%變異概率min_var=0;%函數(shù)定義域下界max_var=9;

23、%函數(shù)定義域上界bin_gen,bits=encoding(min_var,max_var,scale_var,popsize);%隨機產(chǎn)生初始群體old_gen=bin_gen;t=0;T=40;Max_f=;Best_var=;while(t<T) var_gen,fitness=decoding('fun',old_gen,bits,min_var,max_var); evo_gen,best_indiv,best_var,max_fitness=selection(old_gen,fitness,var_gen); conew_gen=crossover(evo_

24、gen,pc); munew_gen=mutation(conew_gen,pm); new_gen=munew_gen;best_indiv;best_indiv; old_gen=new_gen; Best_var=Best_var,best_var; Max_f=Max_f,max_fitness; t=t+1;enddisp('最大值為：' num2str(max_fitness) )disp('全局最大值點為：' num2str(best_var) )figureezplot('fun',min_var,max_var);xlabel(

25、'x')ylabel('f(x)')title('f(x)=x+10sin(5x)+7cos(4x)')figureplot(Best_var,'g+','linewidth',5);xlabel('遺傳代數(shù)')ylabel('最佳個體解碼值')title('最佳個體的變化情況')figureplot(Max_f,'c*','linewidth',5);xlabel('遺傳代數(shù)')ylabel('最佳適應值

26、9;)title('最佳適應值的變化情況')定義的函數(shù)為：function f=fun(x)f=x+10*sin(5*x)+7*cos(4*x);2 蟻群算法2.1 蟻群算法起源及發(fā)展蟻群算法是一種源于大自然生物世界的仿生類算法，作為通用型隨機優(yōu)化方法，它吸收了昆蟲王國中螞蟻的行為特性，通過其內在的搜索機制，在一系列困難的組合優(yōu)化問題求解中取得了成效。由于在模擬仿真中使用的是人工螞蟻概念，因此，有時也稱為螞蟻系統(tǒng)。螞蟻是一種古老的社會性昆蟲，種類成千上萬，分布遍及世界各地，其共同特征是群居生活，每一種群都有著嚴格的社會結構，不同螞蟻有著不同的分工。因此，雖然螞蟻個體的結構和行為

27、都比較簡單，但是由這些簡單個體組成的群體，即“蟻群”系統(tǒng)卻高度復雜，所能完成的任務復雜程度遠遠超出每個個體的能力。除了“蟻群”系統(tǒng)具有高度的分工協(xié)作之外，螞蟻個體之間還存在著一種信息傳遞機制，這也是使得系統(tǒng)能夠高效有序運轉的重要原因。據(jù)昆蟲學家的觀察和研究發(fā)現(xiàn)，生物世界中的螞蟻有能力在沒有任何可見提示下找出其巢穴至食物源的最短路徑，并能隨環(huán)境的變化而變化，適應性地搜索新的路徑，產(chǎn)生新的選擇。作為昆蟲的螞蟻在尋找食物源時，能在其走過的路徑上釋放一種螞蟻特有的分泌物信息素，使得一定范圍內的其他螞蟻能夠察覺到并由此影響它們以后的行為。當一些路徑上通過的螞蟻越來越多時，其留下的信息素軌跡也越來越多，以

28、致信息素強度增大（隨時間的推移會逐漸減弱），后來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強度，這種選擇過程被稱為螞蟻的自催化行為。受到蟻群系統(tǒng)信息共享機制的啟發(fā)，意大利學者Dorigo于1992年在他的博士論文中首次系統(tǒng)提出了蟻群算法，并成功地將該方法應用于其解旅行商問題和二次分配問題（QAP）中，引起了大家的廣泛關注。之后，蟻群算法很快陸續(xù)滲透到其他問題領域中，如工件排序問題、圖著色問題、車輛調度問題、大規(guī)模集成電路設計、通信網(wǎng)絡中的負載平衡問題等，蟻群算法越來越引起人們的重視。2.2 蟻群算法的原理用于優(yōu)化領域的蟻群算法吸收了生物界中蟻群群體行為特征，其原理在于（1）感知小范

29、圍區(qū)域內狀況，并判斷出是否有食物或其他同伴的信息素軌跡；（2）釋放自己的信息素；（3）所遺留的信息素數(shù)量會隨時間而逐步減少。由于自然界中的螞蟻基本沒有視覺，既不知向何處去尋找和獲取食物，也不知發(fā)現(xiàn)食物后如何返回自己的巢穴，因此，它們僅僅依賴于同類散發(fā)在周圍環(huán)境中的信息素來決定自己何去何從。有趣的是，盡管沒有任何先驗知識，但螞蟻們還是有能力找到從巢穴到食物源的最佳路徑，甚至在該路線設置障礙物之后，它們仍然能很快重新找到新的最佳路線。這里，用一個形象化的圖來說明蟻群算法的路徑搜索原理和機制。(a) (b) (c)注：（a）是初始的距離圖，d表示距離；（b）在t=0時刻，在各路徑上沒有信息素的遺留，

30、螞蟻以等概率選擇路徑；（c）在t=1時刻，比較短的邊上信息素的遺留比較多。因此，這樣的邊容易被螞蟻選擇。在圖（a）中，假設F是食物源，E是蟻穴。螞蟻的目的是把食物帶回蟻穴。顯然，較短的路徑比較長的路徑有優(yōu)勢。假設在t=0時刻，這里有150只螞蟻在點C（另有150只螞蟻在點A）。并且在這一時刻任何一段路徑都沒有信息素的遺留。這樣，每只螞蟻都以相同的概率隨機地選擇它們的路徑。所以，從點C和A出發(fā)點螞蟻，按概率都將各有75只走向D，另外75只走向B（圖（b）。當t=1時，又有150只螞蟻從F走向C，此時在C到D的路徑上遺留了先前從C經(jīng)D到A的75只螞蟻所遺留的信息素，而在C到B的路徑上則遺留了先前從

31、C經(jīng)B到A的75只螞蟻以及從A經(jīng)B到C的75只螞蟻所遺留的信息素。螞蟻在選擇路徑的時候依據(jù)各路徑所遺留信息素的濃度來進行選擇，因此，按概率將有100只螞蟻朝點B走，有50只螞蟻朝點D走。由E點到A點也是相同的情況（圖（c）。這一過程反復進行，最終所有點螞蟻都將選擇到這條最短路徑，即CBA這條邊。螞蟻有能力在沒有任何提示下找到從其巢穴到食物源的最短路徑，并且能隨環(huán)境的變化而變化，適應性地搜索新的路徑，產(chǎn)生新的選擇。其根本原因是螞蟻在尋找食物源時，能在其走過的路上釋放信息素，隨著時間的推移該物質會逐漸揮發(fā)，后來的螞蟻選擇該路徑的概率與當時這條路徑上該物質的強度成正比，當一定路徑上通過的螞蟻越來越多

32、時，其留下的信息素軌跡也越來越多，后來螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強度。而強度大的信息素會吸引更多的螞蟻，從而形成一種正反饋機制。通過這種正反饋機制，螞蟻最終可以發(fā)現(xiàn)最短路徑。特別地，當螞蟻巢穴與食物源之間出現(xiàn)障礙物時，螞蟻不僅可以繞過障礙物，而且通過蟻群信息素軌跡在不同路徑上的變化，經(jīng)過一段時間的正反饋，最終收斂到最短路徑上。2.3 基本蟻群算法數(shù)學模型為了便于理解，現(xiàn)用求解平面上個城市的TSP問題為例來說明基本蟻群算法模型。假設將只螞蟻隨機放在個城市上，表示城市和城市之間的距離， 表示時刻城市和城市連線上的信息量，即路徑的信息量。初始時刻，各條路徑上信息量相等，設

33、（為一個正常數(shù)），螞蟻在運動過程中根據(jù)各條路徑的信息量決定其轉移方向。這里用禁忌表來記錄螞蟻當前所走過的城市，集合隨著蟻群進化過程做動態(tài)調整。表示時刻螞蟻由城市轉移到城市的狀態(tài)轉移概率 （2-1）其中，表示螞蟻下一步允許選擇的城市集合，則，為信息啟發(fā)因子，為期望啟發(fā)因子，為啟發(fā)函數(shù)，對于某個確定的TSP問題，是一個常數(shù)。其表達式如下：其中，表示城市和城市之間的距離，且其中，和分別是城市和城市的坐標。為了避免路徑上信息素的無限累計，導致某路徑上殘留的信息素過多而淹沒啟發(fā)信息，在每只螞蟻走完一步或者一個循環(huán)結束后，要對路徑上的信息素進行更新處理。由此，在時刻，路徑上的信息量可按如下規(guī)則調整 （2-

34、2） （2-3）其中，是信息素揮發(fā)系數(shù)，則是信息素殘留因子，且。表示本次循環(huán)中路徑上信息素增量，初始時刻信息素的增量為0，即。為第只螞蟻在本次循環(huán)中留在路徑上的信息素。這里，根據(jù)信息素不同的更新策略，即的不同求法將蟻群算法模型分為以下三種：Ant-Cycle模型、Ant-Auantity模型和Ant-Density模型（1）Ant-Cycle模型 （2-4）（2）Ant-Quantity模型 （2-5）（3）Ant-Density模型 （2-6）以上各式中，均表示信息素強度，是一個常數(shù)。在這三個模型中，Ant-Quantity模型和Ant-Density模型是當螞蟻走完一步后更新其所走路徑上的

35、信息素，是局部信息素更新。而Ant-Cycle模型則是螞蟻完成一個循環(huán)后更新所有路徑上的信息素，利用的是整體信息素更新。我們通常采用Ant-Cycle模型作為螞蟻算法的基本模型。2.4 基本蟻群算法實現(xiàn)過程以Ant-Cycle模型為例來說明基本蟻群算法的具體實現(xiàn)步驟：Step1（初始化）設定算法迭代次數(shù)，設置最大循環(huán)次數(shù)，設置路徑初始時刻的信息量（為常數(shù)），信息素，且初始時路徑上的信息素增量為0，即。Step2算法的迭代過程While(NC<NCmax)for i=1:n-1（確保遍歷所有的城市） for k=1:m（對m只螞蟻進行循環(huán)） for j=1:n（對n個城市進行循環(huán)） 螞蟻k

36、根據(jù)公式（2-1）選擇轉移到的下一個城市j，并將城市j置入螞蟻k的禁忌表tabuk中 end（結束對城市的循環(huán)） end（結束對螞蟻的循環(huán)） end（結束對i的循環(huán)）計算所有螞蟻求得的路徑長度，根據(jù)公式（2-2）、（2-3）和（2-4）更新路徑（i,j）上的信息素； NC=NC+1endStep3結束算法，輸出結果。2.5 用于連續(xù)函數(shù)優(yōu)化的蟻群算法2.5.1 一元連續(xù)函數(shù)優(yōu)化對于任何一個連續(xù)函數(shù)優(yōu)化問題，都可以通過一定的變換而成為一個在0,1上的函數(shù)最小化問題，其中。加上一個常數(shù)以使函數(shù)值大于0.對于端點值，可以通過直接與除去端點計算出的最小值比較的方法確定是否為最小，因此下面不考慮端點值。

37、設問題要求自變量精確到小數(shù)點后位，則自變量可以用個十進制數(shù)來近似表示，就可以構造如下個“城市”。這些城市分為層。其中首尾兩層分別僅含一個城市：一個為起始城市，一個為終止城市。中間層，從左往右分別表示自變量的十分位、百分位······這些城市中，只有與層（）之間的各個城市有連接通路。記層中代表十進制數(shù)的城市與層中代表十進制數(shù)的城市之間的連接上殘留的信息量為。螞蟻在一次循環(huán)中的第步所在的城市用表示。設螞蟻總數(shù)為。首先用一個較小的值初始化所有的。讓每只螞蟻的第一步為0，即令。然后，就為每一只螞蟻選擇路徑。若螞蟻當前所在的城市為，根據(jù)如下公式

38、選擇每只螞蟻下一步應該到達的城市： （2-7）其中，是隨機數(shù)；是一個上的常數(shù)，用于確定偽隨機選擇的概率；表示用偽隨機選擇來確定下一步要走的城市，也就是根據(jù)下式選擇下一層中每一個城市的概率，然后按此概率用遺傳算法中的轉盤式選擇法確定要選擇的城市： （2-8）其中，表示從當前城市轉移到下一層的城市的概率。由于本算法中僅允許螞蟻由上一層城市向下一層轉移，所以這個公式與普通蟻群算法的轉移概率計算公式有所不同。當每只螞蟻按上面的公式到達了層時，都將轉移到層的唯一的城市0.螞蟻在城市上建立路徑的過程中，要不斷地在經(jīng)過的路徑上按公式（2-9）減弱上面殘留的信息，這樣可以減少下一只螞蟻選擇同樣路徑的概率，除非

39、經(jīng)過多次循環(huán)后已確定一條極優(yōu)的路徑。這個過程叫做殘留信息的局部更新。 （2-9）其中，為常數(shù)，表示路徑上殘留信息減弱的速度。當所有螞蟻都按上面的步驟完成了一次循環(huán)。這時就對路徑上的信息進行全局更新。首先對螞蟻選擇的路徑解碼，計算出螞蟻對應的自變量值： （2-10）計算每只螞蟻對應的函數(shù)值，并選擇出函數(shù)值最小的螞蟻： （2-11）對這只最優(yōu)螞蟻經(jīng)過的路徑按下式做全局更新： （2-12）其中，為上的常數(shù)。至此就完成了一個循環(huán)。反復進行上面的步驟直到達到指定的循環(huán)次數(shù)或得到的解在一定循環(huán)次數(shù)后沒有改進。文中提出的求解一元連續(xù)函數(shù)優(yōu)化問題的蟻群算法具體描述如下：1）初始化；2）將所有螞蟻置于初始城市；

40、3）對所有的到層城市執(zhí)行步驟4）8）；4）對每只螞蟻執(zhí)行步驟5）6）；5）根據(jù)公式（2-7）和（2-8）選擇螞蟻在第層應該到達的城市；6）每只螞蟻選擇城市后都立即按公式（2-9）執(zhí)行局部更新規(guī)則；7）根據(jù)公式（2-10）（2-12）評選出最優(yōu)螞蟻并執(zhí)行全局更新規(guī)則；8）判斷是否滿足終止條件，滿足則輸出結果結束計算。2.5.2 多元連續(xù)函數(shù)優(yōu)化對于多元連續(xù)函數(shù)的優(yōu)化問題，設自變量由個分量組成，并要求自變量的每一個分量都精確到小數(shù)點后位，則可構造一副由層城市組成，且第層由1個標號為0的城市組成，其余層都由標號為0到9的10個城市組成。第到層表示自變量的第個分量。其余層都是輔助層。解碼時，就對各分量

41、對應的層分別解碼。采用這種方法，每個自變量分量的最后一位與下一個分量的第一位之間都有輔助層隔開，因此前面一個分量的末位就不會影響后面一個分量首位。除了這一點以外，其余部分都與一元連續(xù)函數(shù)的優(yōu)化方法相同，這里就不再詳細介紹了。2.5.3 應用實例為了與遺傳算法作比較，下面取與1.5中一樣的函數(shù)為：。采用的參數(shù)如下：，運行循環(huán)次數(shù)為：50.2.5.3.1算法具體代碼描述具體分成兩部分：調用函數(shù)部分和主函數(shù)部分。（一）調用函數(shù)部分轉移規(guī)則子函數(shù)%5) 根據(jù)公式(1)和(2)選擇螞蟻n在第k層應該到達的城市;Tau 任意兩個城市之間的信息素，三個維度，第一維表示第幾層，第二維表示Q0 是一個常數(shù)，主要

42、是作為輪盤賭法的臨界點k: 代表目前進展到第幾層（1d+2）a： 第k-1層的節(jié)點下標d： 代表小數(shù)位數(shù)T: 每只螞蟻的路徑矩陣n: 第n只螞蟻%function b=select_k_city(Tau,Q0,n,k,T)a=T(n,k-1)+1;%第n只螞蟻第k-1層的所在城市編碼（注意：城市編碼從110）q=rand;num=100;%輪盤賭次數(shù)P=;Select=;if q<Q0 b=find(Tau(k,a,:)=max(Tau(k,a,:); else P=Tau(k,a,:)/sum(Tau(k,a,:); Select=Roulette(P,num); row,col,le

43、n=size(Tau); for i=1:len Ps(i)=(sum(Select=i)/num); end b=find(Ps=max(Ps);end輪盤賭法子函數(shù)%輪盤賭法程序%function Select=Roulette(P,num)m = length(P);Select = zeros(1,num);r = rand(1,num);for i=1:num sumP = 0; j = ceil(m*rand); %產(chǎn)生1m之間的隨機整數(shù) while sumP < r(i) sumP = sumP + P(mod(j-1,m)+1); j = j+1; end Select(

44、i) = mod(j-2,m)+1;end局部更新規(guī)則子函數(shù)%6) 每只螞蟻選擇城市后都立即按公式(3) 執(zhí)行局部更新規(guī)則;需要輸入rou,tao0,T,Tau%k 第k層%Tau 兩層之間的信息素%Rho 比例%tao0 剩余信息素0.01%T 每一只螞蟻下一步到達的城市.第一維是第幾只螞蟻、第二位是目前是第幾步%n 第幾只螞蟻function Tau=update_tao(Tau,Rho,tao0,T,k,n)i=T(n,k)+1;j=T(n,k-1)+1;Tau(k,j,i)=(1-Rho)*Tau(k,j,i)+Rho*tao0;全局更新規(guī)則子函數(shù)%test7%7) 根據(jù)公式(4) (

45、6) 評選出最優(yōu)螞蟻并執(zhí)行全局更新規(guī)則;%共有n只螞蟻%tau層與層之間的信息素d是小數(shù)點后精確到d位%X所有螞蟻的具體數(shù)值數(shù)組%idx最小的螞蟻編碼，也就是數(shù)組下標%alpha是一常量%function Tau,f_min,var_min=update_all_tao(Tau,N,alpha,d,T)X=zeros(N,1);for j=1:N for i=2:d+1 X(j)=X(j)+T(j,i)*(10(1-i); endend%選擇出螞蟻的最小值F=;for i=1:N f=myfunction(X(i); F=F f;endf_min=min(F);idx=find(F=f_min

46、);var_min=X(idx(1);%螞蟻經(jīng)過路徑全局性更新for k=2:d+1 i=T(idx,k-1)+1; j=T(idx,k)+1; Tau(k,i,j)=(1-alpha)*Tau(k,i,j)+alpha*(1./f_min);end定義連續(xù)函數(shù)子函數(shù)function myvalue=myfunction(x)y=8*x+1;myvalue=-(y+10*sin(5*y)+7*cos(4*y)+30;（二）主函數(shù)部分主函數(shù)%test_lianxu_function%第一層和最后一層只有0%中間層都是0-9 len%T螞蟻的路徑矩陣，起始點是第一層的0，終點是第d+2層的0%Tau全部d+2層的信息素矩陣，代表每一層上每一節(jié)點的經(jīng)過概率% Rho信息素蒸發(fā)系數(shù)，取值01之間，推薦取值0.70.95% N蟻群規(guī)模len=10;tau=0.01;d=10;Tau=ones(d+2,len,len);Tau=Tau*tau;%所有螞蟻共用Rho=0.8;N=20;T=zeros(N,d+2