分布式并行蟻群算法的設(shè)計(jì)與分析.pdf

1、對(duì)于類似TSP的NP難規(guī)劃問(wèn)題，以及一些模型復(fù)雜、解空間巨大的復(fù)雜大系統(tǒng)動(dòng)態(tài)優(yōu)化問(wèn)題，智能優(yōu)化算法成為最有希望的、有時(shí)甚至是唯一可用的求解手段。然而智能優(yōu)化算法一直由于需要大量計(jì)算和存儲(chǔ)資源，在一些動(dòng)態(tài)優(yōu)化和大規(guī)模優(yōu)化等應(yīng)用場(chǎng)合受到很大限制。計(jì)算技術(shù)發(fā)展至今，單個(gè)處理機(jī)的計(jì)算能力逐漸到達(dá)瓶頸，采用基于網(wǎng)絡(luò)連接的分布式并行計(jì)算系統(tǒng)求解復(fù)雜大系統(tǒng)動(dòng)態(tài)優(yōu)化問(wèn)題成為當(dāng)今的研究熱點(diǎn)。 本論文深入研究并行計(jì)算理論，并在此基礎(chǔ)上設(shè)計(jì)出適應(yīng)大規(guī)

2、模復(fù)雜優(yōu)化問(wèn)題的分布式并行AC0算法。 具體的研究成果有以下幾點(diǎn)： (1)基于LogP模型設(shè)計(jì)了一個(gè)分布式并行計(jì)算環(huán)境的串行仿真系統(tǒng)。該仿真系統(tǒng)采用LogP模型抽象并屏蔽了計(jì)算與通信設(shè)備中與并行算法性能瓶頸無(wú)關(guān)的具體底層細(xì)節(jié)，同時(shí)還運(yùn)用計(jì)算獨(dú)立于網(wǎng)絡(luò)通信平臺(tái)的思想設(shè)計(jì)體系結(jié)構(gòu)，不僅可以方便地實(shí)現(xiàn)各種并行算法，還可以在不同物理設(shè)備和網(wǎng)絡(luò)平臺(tái)上測(cè)試分析并行算法的可移植性、擴(kuò)展性等性能。 (2)提出了一種求解復(fù)雜多階段

3、決策問(wèn)題的分布式并行ACO算法的設(shè)計(jì)方法。通過(guò)將大規(guī)模復(fù)雜系統(tǒng)動(dòng)態(tài)優(yōu)化問(wèn)題轉(zhuǎn)換為復(fù)雜多階段決策問(wèn)題，可一致地將其解空間映射為ACO算法的層狀解構(gòu)造圖。再將層次解構(gòu)造圖按層數(shù)均勻分配給各個(gè)計(jì)算節(jié)點(diǎn)，使全局解構(gòu)造圖分布存儲(chǔ)于各個(gè)計(jì)算節(jié)點(diǎn)上。運(yùn)用移動(dòng)Agent技術(shù)實(shí)現(xiàn)螞蟻在各個(gè)計(jì)算節(jié)點(diǎn)間的遷移以完成在整個(gè)解構(gòu)造圖上的路徑搜索，并將最終搜索到的路徑及相應(yīng)的信息素廣播給各個(gè)汁算節(jié)點(diǎn)以更新其本地的解構(gòu)造圖信息素。該并行設(shè)計(jì)方法將螞蟻每步的解構(gòu)造塊評(píng)

4、價(jià)和更新解構(gòu)造圖信息素的計(jì)算都分配到各個(gè)計(jì)算節(jié)點(diǎn)來(lái)實(shí)現(xiàn)，比現(xiàn)有的并行ACO算法更好地解決了計(jì)算需求分配的均衡性和全局解構(gòu)造圖信息素的更新等問(wèn)題。 (3)提出了一種分析并行智能優(yōu)化算法的pesM模型。通過(guò)將智能優(yōu)化算法抽象概括為生成候選解、評(píng)價(jià)候選解和學(xué)習(xí)解空間知識(shí)三個(gè)主要步驟，提出以生成一個(gè)候選解的計(jì)算時(shí)間p，評(píng)價(jià)一個(gè)候選解的計(jì)算時(shí)間P，學(xué)習(xí)一次解空間知識(shí)的計(jì)算時(shí)間s以及生成的候選解總數(shù)M等四個(gè)參數(shù)組成的pesM并行智能優(yōu)化算法