蟻群算法及群體智能的應(yīng)用研究.pdf

1、自然界里螞蟻、蜜蜂等，雖然他們個(gè)體的智能并不高，卻表現(xiàn)出很高的群體智能。群體智能起源于科學(xué)家對(duì)群居性昆蟲(chóng)的觀(guān)察和研究。群體智能是指任何啟發(fā)于群居性昆蟲(chóng)群體和其它動(dòng)物群體的集體行為而設(shè)計(jì)的算法和分布式問(wèn)題解決裝置。群體智能以其簡(jiǎn)單性、靈活性、分布性、健壯性在組合優(yōu)化問(wèn)題、知識(shí)發(fā)現(xiàn)、通信網(wǎng)絡(luò)、機(jī)器人等研究領(lǐng)域顯示出巨大的潛力和優(yōu)勢(shì)，并推動(dòng)復(fù)雜科學(xué)的發(fā)展。 蟻群算法是一種新型仿生類(lèi)進(jìn)化算法，是繼模擬退火、遺傳算法、禁忌搜索等之后的又一

2、啟發(fā)式智能優(yōu)化算法。螞蟻有能力在沒(méi)有任何提示下找到從巢穴到食物源的最短路徑，并且能隨環(huán)境的變化，適應(yīng)性地搜索新的路徑，產(chǎn)生新的選擇。根本原因是螞蟻在尋找食物時(shí)，能在其走過(guò)的路上釋放一種特殊的分泌物一信息素，隨著時(shí)間的推移該物質(zhì)會(huì)逐漸揮發(fā)，后來(lái)的螞蟻選擇該路徑的概率與當(dāng)時(shí)這條路徑上信息素的強(qiáng)度成正比。當(dāng)一條路徑上通過(guò)的螞蟻越來(lái)越多時(shí)，其留下的信息素也越來(lái)越多，后來(lái)螞蟻選擇該路徑的概率也越高，從而更增加了該路徑上的信息素強(qiáng)度。而強(qiáng)度大的信息

3、素會(huì)吸引更多的螞蟻，從而形成一種正反饋機(jī)制。通過(guò)這種正反饋機(jī)制，螞蟻?zhàn)罱K可以發(fā)現(xiàn)最短路徑。蟻群算法由意大利學(xué)者M(jìn)．Dorigo等人首先提出，并成功地應(yīng)用于求解TSP、二次分配、圖著色、車(chē)輛調(diào)度、集成電路設(shè)計(jì)及通信網(wǎng)絡(luò)負(fù)載等問(wèn)題。蟻群算法從提出到現(xiàn)在，短短十余年的時(shí)間，以其在離散型組合優(yōu)化問(wèn)題中的突出表現(xiàn)，吸引了人們的極大關(guān)注。 論文研究了群體智能的多個(gè)模型，研究的目的，一方面是探索和驗(yàn)證群體智能在解決分布式問(wèn)題方面的特性，另一方

4、面是拓寬群體智能的應(yīng)用領(lǐng)域。文章的研究工作主要包括以下幾個(gè)方面： (1)蟻群算法的研究。提出一種求解TSP問(wèn)題的分段交換蟻群算法。分段交換蟻群算法把小窗口、隨機(jī)分段優(yōu)化求解、模擬退火充分交換的思想引入蟻群算法，把蟻群算法和模擬退火算法融合。該算法在蟻群算法陷入局部最優(yōu)解的情況下，能改進(jìn)其局部最優(yōu)解，并可減少迭代次數(shù)。 (2)蟻群算法應(yīng)用于0-1背包問(wèn)題的研究。0-1背包問(wèn)題是典型的NP完全問(wèn)題，且蟻群算法已成功地解決了許

5、多組合優(yōu)化的難題。因此，文章介紹一種基于蟻群算法求解0-1背包問(wèn)題的算法，并對(duì)此算法進(jìn)行優(yōu)化，提出一種求解0-1背包問(wèn)題的快速蟻群算法。當(dāng)物品數(shù)較大時(shí)，也取得了較好的求解質(zhì)量。 (3)蟻群算法應(yīng)用于圓排列問(wèn)題的研究。本章提出一種求解圓排列問(wèn)題的快速蟻群算法。優(yōu)化后的該算法，大大減少了蟻群算法的搜索時(shí)間，有效改善了蟻群算法易于過(guò)早地收斂于非最優(yōu)解的缺陷。 (4)改進(jìn)蟻群算法及兩類(lèi)應(yīng)用模型的研究。論文通過(guò)改變概率的計(jì)算時(shí)機(jī)，

6、按“概率之和為u的輪盤(pán)賭”方式選擇下一個(gè)元素，基于模擬退火的分段交換優(yōu)化當(dāng)前最優(yōu)解，對(duì)基本的蟻群算法進(jìn)行改進(jìn)，提出一種改進(jìn)的蟻群算法。文章還對(duì)蟻群算法解決組合優(yōu)化問(wèn)題進(jìn)行總結(jié)，提出了蟻群算法的兩類(lèi)應(yīng)用模型。 (5)基于群體智能求解N后問(wèn)題的研究。文章提出一種求解N后問(wèn)題的螞蟻模型算法，它受啟發(fā)于群體智能的螞蟻算法和多Agent系統(tǒng)，又吸收了回溯算法的優(yōu)點(diǎn)。該算法是一種隨機(jī)搜索算法，從根本上改變了回溯算法的系統(tǒng)地搜索機(jī)制，避免了大