蟻群優(yōu)化算法的理論研究及其應(yīng)用.pdf

1、蟻群優(yōu)化算法(ant colony optimization，ACO)是基于螞蟻群體覓食過程中沿最短路徑行進(jìn)的生物學(xué)行為發(fā)展起來的一類群智能優(yōu)化方法。該算法在解決傳統(tǒng)優(yōu)化方法難以奏效的具有NP-hard特性的組合優(yōu)化問題中取得了令人鼓舞的效果，因而受到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。目前，蟻群優(yōu)化算法已成為計(jì)算智能方法中的一個(gè)重要分支，并在很多國(guó)際會(huì)議上作為專題加以討論，成為蓬勃發(fā)展的熱點(diǎn)研究課題。 蟻群優(yōu)化算法的理論研究相對(duì)滯后，特

2、別是算法的參數(shù)選擇和收斂性證明方面還有許多問題有待進(jìn)一步研究。網(wǎng)絡(luò)路由問題的很多特征，如信息的分布式特性、動(dòng)態(tài)性和異步性等與蟻群算法的特征匹配得很好，因此利用蟻群優(yōu)化算法解決網(wǎng)絡(luò)路由問題一直倍受關(guān)注。此外，將蟻群優(yōu)化算法與其它仿生優(yōu)化方法進(jìn)行巧妙的融合、互補(bǔ)長(zhǎng)短是近年來蟻群優(yōu)化算法的另一個(gè)熱點(diǎn)研究方向。 本文致力于以上問題的研究，主要研究?jī)?nèi)容及創(chuàng)新點(diǎn)包括以下幾方面： 1、在將組合優(yōu)化極小化問題映射為全連通圖的基礎(chǔ)上，對(duì)蟻

3、群優(yōu)化算法的參數(shù)設(shè)置進(jìn)行了研究。證明了信息素增量△τ是介于最大偽可行解s<,max>和最小偽可行解S<,min>之間的量，即g(s<,max>)≤△τ≤g(s<,min>)，為信息素初值的選取提供了理論依據(jù)；進(jìn)一步緊縮了信息素?fù)]發(fā)系數(shù)p的取值范圍，由p(0，1)變?yōu)閜(0，1-t<,0><平方根e<,min>/e<,max>>)，其中e<,min>和e<,max>分別表示構(gòu)造圖中的最小和最大權(quán)值，％表示算法的有效迭代次數(shù)；最后給出了最大

4、迭代次數(shù)Iter<,max>的估算公式。 2、在收斂性證明方面：證明了當(dāng)螞蟻數(shù)目和迭代次數(shù)的乘積趨于無窮時(shí)算法將以概率1找到全局最優(yōu)解的結(jié)論；對(duì)使算法以概率P<'*>(m,t)找到全局最優(yōu)解所需m·t的上界進(jìn)行了研究；對(duì)在假設(shè)算法找到最優(yōu)解的情況下，通過信息素更新使最優(yōu)解“凸現(xiàn)”出來的時(shí)刻進(jìn)行了討論；最后證明了在已經(jīng)找到最優(yōu)解的情況下，任意螞蟻構(gòu)造最優(yōu)解的概率下界為完全隨機(jī)算法構(gòu)造任意解的概率P。 3、提出了歸一化蟻群優(yōu)

5、化算法框架ACO-UF，并在ACO-UF下實(shí)現(xiàn)了MMAS算法，以TSP為例對(duì)其參數(shù)設(shè)置進(jìn)行了研究。ACO-UF在標(biāo)準(zhǔn)ACO的基礎(chǔ)上作了兩點(diǎn)改進(jìn)，即問題的歸一化預(yù)處理和信息素初值的統(tǒng)一設(shè)定，克服了標(biāo)準(zhǔn)ACO受同形問題的困擾和信息素初值選取經(jīng)驗(yàn)性強(qiáng)的不足。 4、提出了一種基于蟻群優(yōu)化的分布式QoS多播路由算法DMRACO，并結(jié)合多播路由問題的特點(diǎn)對(duì)算法進(jìn)行了改進(jìn)。DMRACO可方便的避免循環(huán)回路的產(chǎn)生，引起的額外負(fù)載較小，具有合理的

6、鏈路建立時(shí)間。通過仿真實(shí)驗(yàn)討論了網(wǎng)絡(luò)規(guī)模、多播規(guī)模和時(shí)延限制對(duì)DMRACO性能的影響，并與BSMA算法和KMB算法進(jìn)行了比較，驗(yàn)證了該方法的有效性。 5、提出了一種將ACO與BP算法相融合共同完成反傳神經(jīng)網(wǎng)絡(luò)訓(xùn)練的方法，ACO-BP算法。該算法首先采用ACO對(duì)網(wǎng)絡(luò)權(quán)值進(jìn)行整體尋優(yōu)，克服BP算法容易陷入局部最優(yōu)的不足；再以找到的較優(yōu)的權(quán)值為初值，采用BP算法做進(jìn)一步的尋優(yōu)，克服單一ACO訓(xùn)練網(wǎng)絡(luò)時(shí)間較長(zhǎng)、精度不高的缺點(diǎn)。以函數(shù)逼近