并行蟻群算法及其應(yīng)用研究.pdf

1、蟻群優(yōu)化(ACO)算法是一種新型的元啟發(fā)式算法。蟻群優(yōu)化算法具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算機(jī)制、易于與其它方法結(jié)合等優(yōu)點(diǎn)，可以用于解決各種組合優(yōu)化問(wèn)題，并已經(jīng)成功解決了包括旅行商(TSP)問(wèn)題在內(nèi)的許多組合優(yōu)化問(wèn)題。 蟻群優(yōu)化算法具有天然的并行特性，適合并行計(jì)算。本文對(duì)并行蟻群優(yōu)化算法進(jìn)行了研究，主要工作包括：研究蟻群算法的并行化，研究并行蟻群算法的應(yīng)用，研究算法參數(shù)的最優(yōu)組合。本文采用MPICH在機(jī)群系統(tǒng)上對(duì)算法進(jìn)行仿真研

2、究，并選擇了適合機(jī)群系統(tǒng)以及蟻群優(yōu)化算法特點(diǎn)的并行策略。 針對(duì)大規(guī)?；鹆Ψ峙鋯?wèn)題(WTA)的特點(diǎn)，提出了一種求解該問(wèn)題的并行蟻群算法(ACS-WTA-MPI)。仿真實(shí)驗(yàn)結(jié)果表明，本文提出的算法的求解質(zhì)量比求解此問(wèn)題的對(duì)應(yīng)的串行ACS算法好，本文提出的并行算法的加速比和并行效率也比較理想，加速比最高達(dá)到3.851(處理機(jī)個(gè)數(shù)=4)，并行效率最高達(dá)到0.963。 本文對(duì)蟻群算法參數(shù)的選取進(jìn)行了研究，目的是確定出參數(shù)的最優(yōu)組合