并行蟻群算法的研究.pdf

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

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

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

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