并行蟻群算法的研究.pdf

1、蟻群算法是近年來一種新興的群智能算法，在解決大規(guī)模組合優(yōu)化問題中取得很好的效果，具有廣闊的發(fā)展前景。然而，現(xiàn)有蟻群算法的內(nèi)在機制存在不足，限制了其性能的充分發(fā)揮。因此，提高蟻群算法性能，具有很強的理論和現(xiàn)實意義。本文介紹了人工蟻群算法(ACO)的基本思想和模型，列出了人工蟻群算法搜索時間較長，收斂速度慢的缺點，詳述了并行蟻群算法(PAC)，在PAC中，針對各個子機對固定模式進行重復(fù)搜索的缺點，提出基于模式學(xué)習(xí)的并行蟻群算法(MPAC)，

2、設(shè)定標(biāo)準(zhǔn)對固定模式進行學(xué)習(xí)，并傳遞給其他處理器，減少計算復(fù)雜度，分別應(yīng)用MPAC、PAC和ACO針對bier52、kroA100、kroE100、bier127、ch150、kroE150六個TSP測試問題在matlab平臺上仿真顯示MPAC運算精度與PAC相近，優(yōu)于ACO。MPAC在大部分問題中收斂次數(shù)低于PAC和ACO，MPAC有效的記錄下了最優(yōu)模式，加快了收斂速度，模式學(xué)習(xí)同時降低計算問題的計算復(fù)雜度，減少搜索時間，因此，MPAC

3、優(yōu)于PAC和ACO。
　　蟻群初始階段等概率的選擇路徑，存在收斂速度較慢的問題，針對這一缺點，提出基于模式學(xué)習(xí)的并行混沌蟻群算法(CMPAC)。利用混沌運動的遍歷性，進行混沌初始化，每個混沌量對應(yīng)于一條路徑，產(chǎn)生大量的路徑，從中選擇比較優(yōu)的路徑，使這些路徑留下信息素（與路徑長度的和成反比例）。各路徑的信息素就不同，以此引導(dǎo)螞蟻進行選擇路徑，從而大大加快了收斂速度。引入混沌初始化，加快了收斂速度，但是混沌初始化會導(dǎo)致算法更易陷入早熟

4、狀態(tài)，即陷入局部最優(yōu)解，為了改進算法，加入了混沌擾動，在更新信息素時，加入一個混沌量來干擾信息素的更新，以使其跳出局部極值區(qū)間，同樣應(yīng)用CMPAC針對6個TSP測試問題仿真和MPAC、PAC比較發(fā)現(xiàn)， CMPAC運用在berlin52、kroA100、kroE100、ch150、kroE150最優(yōu)解最小，證明其混沌干擾因子在大部分TSP問題中，一定程度上跳出了局部最優(yōu)解，最優(yōu)解的精度高于MPAC和PAC，在berlin52、kroA10