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

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

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

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

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

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

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

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

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

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

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

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

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

13、碼方案，即用二進(jìn)制數(shù)構(gòu)成的符號(hào)串來(lái)表示一個(gè)個(gè)體，用下面的encoding函數(shù)來(lái)實(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來(lái)確定表示各決策變量的二進(jìn)制串的長(zhǎng)度bits，然后隨機(jī)產(chǎn)生一個(gè)種群大小為popsize的

14、初始種群bit_gen。編碼后的實(shí)際搜索精度為scale_dec=(max_var-min_var)/(2bits-1)，該精度會(huì)在解碼時(shí)用到。1.4.2解碼解碼后的個(gè)體構(gòu)成的種群bin_gen必須經(jīng)過(guò)解碼，以轉(zhuǎn)換成原問(wèn)題空間的決策變量構(gòu)成的種群var_gen，方能計(jì)算相應(yīng)的適應(yīng)值。我們用下面的代碼實(shí)現(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)./(2

15、.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ù)的關(guān)鍵在于先由二進(jìn)制數(shù)求得對(duì)應(yīng)的十進(jìn)制數(shù)D，并根據(jù)下式求得實(shí)際決

16、策變量值X：1.4.3選擇選擇過(guò)程是利用解碼后求得的各個(gè)適應(yīng)值大小，淘汰一些較差個(gè)體而選出一些比較優(yōu)良的個(gè)體，以進(jìn)行下一步的交叉和變異操作。選擇算子的程序如下：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_var=var_gen(ind

17、ex1);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_popsize,1)*r)+1;evo

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

19、C在兩兩配對(duì)的個(gè)體編碼串cpairs中隨機(jī)設(shè)置一個(gè)交叉點(diǎn)cpoints，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分基因，從而形成兩個(gè)新的個(gè)體。交叉算子的程序如下：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,bits);cpoints=cpairs.*

20、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變異對(duì)于二進(jìn)制的基因串而言，變異操作就是按照變異概率pm隨機(jī)選擇變異點(diǎn)mpoints，在變異點(diǎn)處將其位取反即可。變異算子的實(shí)現(xiàn)過(guò)程如下：function new_gen=mutation(old_gen,pm)mpoints=find(rand(size(old_gen)pm);new_gen=old_gen;new_gen(mpoints)=1-old

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

22、值為7.8681，落在函數(shù)的一個(gè)局部極值處。但是搜索并沒(méi)有在此處停滯，很快就躍到了另一個(gè)更大的極值點(diǎn)7.8538附近。搜索繼續(xù)，經(jīng)過(guò)幾次跳躍，我們發(fā)現(xiàn)在7.85附近搜索多次后，連續(xù)幾次得到的最優(yōu)個(gè)體的適應(yīng)值變化很小，可以認(rèn)為找到全局最大值。全局最大值點(diǎn)為7.8567，最大值為24.8554。下列程序?yàn)橹骱瘮?shù)。%Exampleclear;clc;close;popsize=40;%種群的個(gè)體個(gè)數(shù)scale_var=0.0001;%搜索精度pc=0.85;%交叉概率pm=0.05;%變異概率min_var=0;%函數(shù)定義域下界max_var=9;%函數(shù)定義域上界bin_gen,bits=encod

23、ing(min_var,max_var,scale_var,popsize);%隨機(jī)產(chǎn)生初始群體old_gen=bin_gen;t=0;T=40;Max_f=;Best_var=;while(tT) 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_gen,pc); munew_gen=mutation(conew_gen,pm

24、); 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(全局最大值點(diǎn)為： num2str(best_var) )figureezplot(fun,min_var,max_var);xlabel(x)ylabel(f(x)title(f(x)=x+10sin(5x)+7cos(4x)figureplot(Best_var,g+,lin

25、ewidth,5);xlabel(遺傳代數(shù))ylabel(最佳個(gè)體解碼值)title(最佳個(gè)體的變化情況)figureplot(Max_f,c*,linewidth,5);xlabel(遺傳代數(shù))ylabel(最佳適應(yīng)值)title(最佳適應(yīng)值的變化情況)定義的函數(shù)為：function f=fun(x)f=x+10*sin(5*x)+7*cos(4*x);2 蟻群算法2.1 蟻群算法起源及發(fā)展蟻群算法是一種源于大自然生物世界的仿生類算法，作為通用型隨機(jī)優(yōu)化方法，它吸收了昆蟲(chóng)王國(guó)中螞蟻的行為特性，通過(guò)其內(nèi)在的搜索機(jī)制，在一系列困難的組合優(yōu)化問(wèn)題求解中取得了成效。由于在模擬仿真中使用的是人工螞蟻概

26、念，因此，有時(shí)也稱為螞蟻系統(tǒng)。螞蟻是一種古老的社會(huì)性昆蟲(chóng)，種類成千上萬(wàn)，分布遍及世界各地，其共同特征是群居生活，每一種群都有著嚴(yán)格的社會(huì)結(jié)構(gòu)，不同螞蟻有著不同的分工。因此，雖然螞蟻個(gè)體的結(jié)構(gòu)和行為都比較簡(jiǎn)單，但是由這些簡(jiǎn)單個(gè)體組成的群體，即“蟻群”系統(tǒng)卻高度復(fù)雜，所能完成的任務(wù)復(fù)雜程度遠(yuǎn)遠(yuǎn)超出每個(gè)個(gè)體的能力。除了“蟻群”系統(tǒng)具有高度的分工協(xié)作之外，螞蟻個(gè)體之間還存在著一種信息傳遞機(jī)制，這也是使得系統(tǒng)能夠高效有序運(yùn)轉(zhuǎn)的重要原因。據(jù)昆蟲(chóng)學(xué)家的觀察和研究發(fā)現(xiàn)，生物世界中的螞蟻有能力在沒(méi)有任何可見(jiàn)提示下找出其巢穴至食物源的最短路徑，并能隨環(huán)境的變化而變化，適應(yīng)性地搜索新的路徑，產(chǎn)生新的選擇。作為昆蟲(chóng)的

27、螞蟻在尋找食物源時(shí)，能在其走過(guò)的路徑上釋放一種螞蟻特有的分泌物信息素，使得一定范圍內(nèi)的其他螞蟻能夠察覺(jué)到并由此影響它們以后的行為。當(dāng)一些路徑上通過(guò)的螞蟻越來(lái)越多時(shí)，其留下的信息素軌跡也越來(lái)越多，以致信息素強(qiáng)度增大（隨時(shí)間的推移會(huì)逐漸減弱），后來(lái)螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強(qiáng)度，這種選擇過(guò)程被稱為螞蟻的自催化行為。受到蟻群系統(tǒng)信息共享機(jī)制的啟發(fā)，意大利學(xué)者Dorigo于1992年在他的博士論文中首次系統(tǒng)提出了蟻群算法，并成功地將該方法應(yīng)用于其解旅行商問(wèn)題和二次分配問(wèn)題（QAP）中，引起了大家的廣泛關(guān)注。之后，蟻群算法很快陸續(xù)滲透到其他問(wèn)題領(lǐng)域中，如工件排序問(wèn)題、圖著色問(wèn)

28、題、車輛調(diào)度問(wèn)題、大規(guī)模集成電路設(shè)計(jì)、通信網(wǎng)絡(luò)中的負(fù)載平衡問(wèn)題等，蟻群算法越來(lái)越引起人們的重視。2.2 蟻群算法的原理用于優(yōu)化領(lǐng)域的蟻群算法吸收了生物界中蟻群群體行為特征，其原理在于（1）感知小范圍區(qū)域內(nèi)狀況，并判斷出是否有食物或其他同伴的信息素軌跡；（2）釋放自己的信息素；（3）所遺留的信息素?cái)?shù)量會(huì)隨時(shí)間而逐步減少。由于自然界中的螞蟻基本沒(méi)有視覺(jué)，既不知向何處去尋找和獲取食物，也不知發(fā)現(xiàn)食物后如何返回自己的巢穴，因此，它們僅僅依賴于同類散發(fā)在周圍環(huán)境中的信息素來(lái)決定自己何去何從。有趣的是，盡管沒(méi)有任何先驗(yàn)知識(shí)，但螞蟻們還是有能力找到從巢穴到食物源的最佳路徑，甚至在該路線設(shè)置障礙物之后，它們?nèi)?/p>

29、然能很快重新找到新的最佳路線。這里，用一個(gè)形象化的圖來(lái)說(shuō)明蟻群算法的路徑搜索原理和機(jī)制。(a) (b) (c)注：（a）是初始的距離圖，d表示距離；（b）在t=0時(shí)刻，在各路徑上沒(méi)有信息素的遺留，螞蟻以等概率選擇路徑；（c）在t=1時(shí)刻，比較短的邊上信息素的遺留比較多。因此，這樣的邊容易被螞蟻選擇。在圖（a）中，假設(shè)F是食物源，E是蟻穴。螞蟻的目的是把食物帶回蟻穴。顯然，較短的路徑比較長(zhǎng)的路徑有優(yōu)勢(shì)。假設(shè)在t=0時(shí)刻，這里有150只螞蟻在點(diǎn)C（另有150只螞蟻在點(diǎn)A）。并且在這一時(shí)刻任何一段路徑都沒(méi)有信息素的遺留。這樣，每只螞蟻都以相同的概率隨機(jī)地選擇它們的路徑。所以，從點(diǎn)C和A出發(fā)點(diǎn)螞蟻，按

30、概率都將各有75只走向D，另外75只走向B（圖（b）。當(dāng)t=1時(shí)，又有150只螞蟻從F走向C，此時(shí)在C到D的路徑上遺留了先前從C經(jīng)D到A的75只螞蟻所遺留的信息素，而在C到B的路徑上則遺留了先前從C經(jīng)B到A的75只螞蟻以及從A經(jīng)B到C的75只螞蟻所遺留的信息素。螞蟻在選擇路徑的時(shí)候依據(jù)各路徑所遺留信息素的濃度來(lái)進(jìn)行選擇，因此，按概率將有100只螞蟻朝點(diǎn)B走，有50只螞蟻朝點(diǎn)D走。由E點(diǎn)到A點(diǎn)也是相同的情況（圖（c）。這一過(guò)程反復(fù)進(jìn)行，最終所有點(diǎn)螞蟻都將選擇到這條最短路徑，即CBA這條邊。螞蟻有能力在沒(méi)有任何提示下找到從其巢穴到食物源的最短路徑，并且能隨環(huán)境的變化而變化，適應(yīng)性地搜索新的路徑，產(chǎn)

31、生新的選擇。其根本原因是螞蟻在尋找食物源時(shí)，能在其走過(guò)的路上釋放信息素，隨著時(shí)間的推移該物質(zhì)會(huì)逐漸揮發(fā)，后來(lái)的螞蟻選擇該路徑的概率與當(dāng)時(shí)這條路徑上該物質(zhì)的強(qiáng)度成正比，當(dāng)一定路徑上通過(guò)的螞蟻越來(lái)越多時(shí)，其留下的信息素軌跡也越來(lái)越多，后來(lái)螞蟻選擇該路徑的概率也越高，從而更增加了該路徑的信息素強(qiáng)度。而強(qiáng)度大的信息素會(huì)吸引更多的螞蟻，從而形成一種正反饋機(jī)制。通過(guò)這種正反饋機(jī)制，螞蟻?zhàn)罱K可以發(fā)現(xiàn)最短路徑。特別地，當(dāng)螞蟻巢穴與食物源之間出現(xiàn)障礙物時(shí)，螞蟻不僅可以繞過(guò)障礙物，而且通過(guò)蟻群信息素軌跡在不同路徑上的變化，經(jīng)過(guò)一段時(shí)間的正反饋，最終收斂到最短路徑上。2.3 基本蟻群算法數(shù)學(xué)模型為了便于理解，現(xiàn)用求

32、解平面上個(gè)城市的TSP問(wèn)題為例來(lái)說(shuō)明基本蟻群算法模型。假設(shè)將只螞蟻隨機(jī)放在個(gè)城市上，表示城市和城市之間的距離， 表示時(shí)刻城市和城市連線上的信息量，即路徑的信息量。初始時(shí)刻，各條路徑上信息量相等，設(shè)（為一個(gè)正常數(shù)），螞蟻在運(yùn)動(dòng)過(guò)程中根據(jù)各條路徑的信息量決定其轉(zhuǎn)移方向。這里用禁忌表來(lái)記錄螞蟻當(dāng)前所走過(guò)的城市，集合隨著蟻群進(jìn)化過(guò)程做動(dòng)態(tài)調(diào)整。表示時(shí)刻螞蟻由城市轉(zhuǎn)移到城市的狀態(tài)轉(zhuǎn)移概率 （2-1）其中，表示螞蟻下一步允許選擇的城市集合，則，為信息啟發(fā)因子，為期望啟發(fā)因子，為啟發(fā)函數(shù)，對(duì)于某個(gè)確定的TSP問(wèn)題，是一個(gè)常數(shù)。其表達(dá)式如下：其中，表示城市和城市之間的距離，且其中，和分別是城市和城市的坐標(biāo)。為

33、了避免路徑上信息素的無(wú)限累計(jì)，導(dǎo)致某路徑上殘留的信息素過(guò)多而淹沒(méi)啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咭粋€(gè)循環(huán)結(jié)束后，要對(duì)路徑上的信息素進(jìn)行更新處理。由此，在時(shí)刻，路徑上的信息量可按如下規(guī)則調(diào)整 （2-2） （2-3）其中，是信息素?fù)]發(fā)系數(shù)，則是信息素殘留因子，且。表示本次循環(huán)中路徑上信息素增量，初始時(shí)刻信息素的增量為0，即。為第只螞蟻在本次循環(huán)中留在路徑上的信息素。這里，根據(jù)信息素不同的更新策略，即的不同求法將蟻群算法模型分為以下三種：Ant-Cycle模型、Ant-Auantity模型和Ant-Density模型（1）Ant-Cycle模型 （2-4）（2）Ant-Quantity模型 （2-5

34、）（3）Ant-Density模型 （2-6）以上各式中，均表示信息素強(qiáng)度，是一個(gè)常數(shù)。在這三個(gè)模型中，Ant-Quantity模型和Ant-Density模型是當(dāng)螞蟻?zhàn)咄暌徊胶蟾缕渌呗窂缴系男畔⑺?，是局部信息素更新。而Ant-Cycle模型則是螞蟻完成一個(gè)循環(huán)后更新所有路徑上的信息素，利用的是整體信息素更新。我們通常采用Ant-Cycle模型作為螞蟻算法的基本模型。2.4 基本蟻群算法實(shí)現(xiàn)過(guò)程以Ant-Cycle模型為例來(lái)說(shuō)明基本蟻群算法的具體實(shí)現(xiàn)步驟：Step1（初始化）設(shè)定算法迭代次數(shù)，設(shè)置最大循環(huán)次數(shù)，設(shè)置路徑初始時(shí)刻的信息量（為常數(shù)），信息素，且初始時(shí)路徑上的信息素增量為0，即。

35、Step2算法的迭代過(guò)程While(NCNCmax)for i=1:n-1（確保遍歷所有的城市） for k=1:m（對(duì)m只螞蟻進(jìn)行循環(huán)） for j=1:n（對(duì)n個(gè)城市進(jìn)行循環(huán)） 螞蟻k根據(jù)公式（2-1）選擇轉(zhuǎn)移到的下一個(gè)城市j，并將城市j置入螞蟻k的禁忌表tabuk中 end（結(jié)束對(duì)城市的循環(huán)） end（結(jié)束對(duì)螞蟻的循環(huán)） end（結(jié)束對(duì)i的循環(huán)）計(jì)算所有螞蟻求得的路徑長(zhǎng)度，根據(jù)公式（2-2）、（2-3）和（2-4）更新路徑（i,j）上的信息素； NC=NC+1endStep3結(jié)束算法，輸出結(jié)果。2.5 用于連續(xù)函數(shù)優(yōu)化的蟻群算法2.5.1 一元連續(xù)函數(shù)優(yōu)化對(duì)于任何一個(gè)連續(xù)函數(shù)優(yōu)化問(wèn)題，都

36、可以通過(guò)一定的變換而成為一個(gè)在0,1上的函數(shù)最小化問(wèn)題，其中。加上一個(gè)常數(shù)以使函數(shù)值大于0.對(duì)于端點(diǎn)值，可以通過(guò)直接與除去端點(diǎn)計(jì)算出的最小值比較的方法確定是否為最小，因此下面不考慮端點(diǎn)值。設(shè)問(wèn)題要求自變量精確到小數(shù)點(diǎn)后位，則自變量可以用個(gè)十進(jìn)制數(shù)來(lái)近似表示，就可以構(gòu)造如下個(gè)“城市”。這些城市分為層。其中首尾兩層分別僅含一個(gè)城市：一個(gè)為起始城市，一個(gè)為終止城市。中間層，從左往右分別表示自變量的十分位、百分位這些城市中，只有與層（）之間的各個(gè)城市有連接通路。記層中代表十進(jìn)制數(shù)的城市與層中代表十進(jìn)制數(shù)的城市之間的連接上殘留的信息量為。螞蟻在一次循環(huán)中的第步所在的城市用表示。設(shè)螞蟻總數(shù)為。首先用一個(gè)較

37、小的值初始化所有的。讓每只螞蟻的第一步為0，即令。然后，就為每一只螞蟻選擇路徑。若螞蟻當(dāng)前所在的城市為，根據(jù)如下公式選擇每只螞蟻下一步應(yīng)該到達(dá)的城市： （2-7）其中，是隨機(jī)數(shù)；是一個(gè)上的常數(shù)，用于確定偽隨機(jī)選擇的概率；表示用偽隨機(jī)選擇來(lái)確定下一步要走的城市，也就是根據(jù)下式選擇下一層中每一個(gè)城市的概率，然后按此概率用遺傳算法中的轉(zhuǎn)盤(pán)式選擇法確定要選擇的城市： （2-8）其中，表示從當(dāng)前城市轉(zhuǎn)移到下一層的城市的概率。由于本算法中僅允許螞蟻由上一層城市向下一層轉(zhuǎn)移，所以這個(gè)公式與普通蟻群算法的轉(zhuǎn)移概率計(jì)算公式有所不同。當(dāng)每只螞蟻按上面的公式到達(dá)了層時(shí)，都將轉(zhuǎn)移到層的唯一的城市0.螞蟻在城市上建立路

38、徑的過(guò)程中，要不斷地在經(jīng)過(guò)的路徑上按公式（2-9）減弱上面殘留的信息，這樣可以減少下一只螞蟻選擇同樣路徑的概率，除非經(jīng)過(guò)多次循環(huán)后已確定一條極優(yōu)的路徑。這個(gè)過(guò)程叫做殘留信息的局部更新。 （2-9）其中，為常數(shù)，表示路徑上殘留信息減弱的速度。當(dāng)所有螞蟻都按上面的步驟完成了一次循環(huán)。這時(shí)就對(duì)路徑上的信息進(jìn)行全局更新。首先對(duì)螞蟻選擇的路徑解碼，計(jì)算出螞蟻對(duì)應(yīng)的自變量值： （2-10）計(jì)算每只螞蟻對(duì)應(yīng)的函數(shù)值，并選擇出函數(shù)值最小的螞蟻： （2-11）對(duì)這只最優(yōu)螞蟻經(jīng)過(guò)的路徑按下式做全局更新： （2-12）其中，為上的常數(shù)。至此就完成了一個(gè)循環(huán)。反復(fù)進(jìn)行上面的步驟直到達(dá)到指定的循環(huán)次數(shù)或得到的解在一定循

39、環(huán)次數(shù)后沒(méi)有改進(jìn)。文中提出的求解一元連續(xù)函數(shù)優(yōu)化問(wèn)題的蟻群算法具體描述如下：1）初始化；2）將所有螞蟻置于初始城市；3）對(duì)所有的到層城市執(zhí)行步驟4）8）；4）對(duì)每只螞蟻執(zhí)行步驟5）6）；5）根據(jù)公式（2-7）和（2-8）選擇螞蟻在第層應(yīng)該到達(dá)的城市；6）每只螞蟻選擇城市后都立即按公式（2-9）執(zhí)行局部更新規(guī)則；7）根據(jù)公式（2-10）（2-12）評(píng)選出最優(yōu)螞蟻并執(zhí)行全局更新規(guī)則；8）判斷是否滿足終止條件，滿足則輸出結(jié)果結(jié)束計(jì)算。2.5.2 多元連續(xù)函數(shù)優(yōu)化對(duì)于多元連續(xù)函數(shù)的優(yōu)化問(wèn)題，設(shè)自變量由個(gè)分量組成，并要求自變量的每一個(gè)分量都精確到小數(shù)點(diǎn)后位，則可構(gòu)造一副由層城市組成，且第層由1個(gè)標(biāo)號(hào)為0

40、的城市組成，其余層都由標(biāo)號(hào)為0到9的10個(gè)城市組成。第到層表示自變量的第個(gè)分量。其余層都是輔助層。解碼時(shí)，就對(duì)各分量對(duì)應(yīng)的層分別解碼。采用這種方法，每個(gè)自變量分量的最后一位與下一個(gè)分量的第一位之間都有輔助層隔開(kāi)，因此前面一個(gè)分量的末位就不會(huì)影響后面一個(gè)分量首位。除了這一點(diǎn)以外，其余部分都與一元連續(xù)函數(shù)的優(yōu)化方法相同，這里就不再詳細(xì)介紹了。2.5.3 應(yīng)用實(shí)例為了與遺傳算法作比較，下面取與1.5中一樣的函數(shù)為：。采用的參數(shù)如下：，運(yùn)行循環(huán)次數(shù)為：50.2.5.3.1算法具體代碼描述具體分成兩部分：調(diào)用函數(shù)部分和主函數(shù)部分。（一）調(diào)用函數(shù)部分轉(zhuǎn)移規(guī)則子函數(shù)%5) 根據(jù)公式(1)和(2)選擇螞蟻n在

41、第k層應(yīng)該到達(dá)的城市;Tau 任意兩個(gè)城市之間的信息素，三個(gè)維度，第一維表示第幾層，第二維表示Q0 是一個(gè)常數(shù)，主要是作為輪盤(pán)賭法的臨界點(diǎn)k: 代表目前進(jìn)展到第幾層（1d+2）a： 第k-1層的節(jié)點(diǎn)下標(biāo)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;%輪盤(pán)賭次數(shù)P=;Select=;if qQ0 b=find(Tau(k,a,:)=max(Tau(k,a,:); else P=Tau(k,a

42、,:)/sum(Tau(k,a,:); Select=Roulette(P,num); row,col,len=size(Tau); for i=1:len Ps(i)=(sum(Select=i)/num); end b=find(Ps=max(Ps);end輪盤(pán)賭法子函數(shù)%輪盤(pán)賭法程序%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之間的隨機(jī)整數(shù) while sumP r(i) su

43、mP = sumP + P(mod(j-1,m)+1); j = j+1; end Select(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 每一只螞蟻下一步到達(dá)的城市.第一維是第幾只螞蟻、第二位是目前是第幾步%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)

44、*Tau(k,j,i)+Rho*tao0;全局更新規(guī)則子函數(shù)%test7%7) 根據(jù)公式(4) (6) 評(píng)選出最優(yōu)螞蟻并執(zhí)行全局更新規(guī)則;%共有n只螞蟻%tau層與層之間的信息素d是小數(shù)點(diǎn)后精確到d位%X所有螞蟻的具體數(shù)值數(shù)組%idx最小的螞蟻編碼，也就是數(shù)組下標(biāo)%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=myfunc

45、tion(X(i); F=F f;endf_min=min(F);idx=find(F=f_min);var_min=X(idx(1);%螞蟻經(jīng)過(guò)路徑全局性更新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螞蟻的路徑矩陣，起始點(diǎn)是第一層的0，終點(diǎn)是第d+2層的0%Tau全部d+2層的信息素矩陣，代表每一層上每一節(jié)點(diǎn)的經(jīng)過(guò)概率% Rho信息素蒸發(fā)系數(shù)，取值01之間，推薦取值0.70.95% N蟻群