蟻群算法的應用研究.pdf

1、蟻群算法是一種新型仿生類優(yōu)化算法，是繼模擬退火、遺傳算法、禁忌搜索等之后的又一啟發(fā)式智能優(yōu)化算法。蟻群算法由意大利學者M.Dorigo等人首先提出，并成功地應用于求解一系列NP完全的組合優(yōu)化問題，如：旅行商問題、二次分配問題、車輛尋路問題和圖著色問題等等。蟻群算法從提出到現(xiàn)在，短短十余年的時間，以其在離散型組合優(yōu)化問題中的突出表現(xiàn)，吸引了人們的極大關(guān)注。 論文針對基本蟻群算法收斂速度較慢和算法容易出現(xiàn)停滯現(xiàn)象的缺點，對蟻群算法進

2、行研究，提出了兩種改進的蟻群優(yōu)化算法，并分別應用于TSP問題和多維0-1背包問題。論文的研究工作主要包括以下兩個方面： 1．改進的蟻群算法應用于TSP問題的研究。提出一種求解TSP問題的具有分段和變異特性的蟻群算法SMAS。該算法融合了分段的分而治之思想和遺傳算法中的變異，有利于保持群體多樣性的特性，是在采用輪盤賭方式的最大最小蟻群算法陷入局部最優(yōu)解的情況下，引入隨機分段和遺傳算法的變異操作來優(yōu)化當前最優(yōu)解，改善解的質(zhì)量，有效地

3、改善了蟻群算法易于過早地收斂于非最優(yōu)解的缺陷。 2．改進的蟻群算法應用于多維0-1背包問題的研究(MKPACA)。0-1背包問題是典型的NP完全問題，且蟻群算法已成功地解決了許多組合優(yōu)化的難題。因此，論文提出一種求解多維O．1背包問題的蟻群算法——MKPACA，當物品數(shù)較大時，也取得了較好的求解質(zhì)量。在MKPACA中，引入受益量密度的概念，改變概率計算的時機，并采用“輪盤賭”方式根據(jù)概率pj選擇下一個物資，這樣既兼顧了概率大小，