[發(fā)明專利]粒子群算法在多機(jī)上并行執(zhí)行的方法

無效

• 申請?zhí)枺?/td>: 201010148490.1
• 申請日: 2010-04-16
• 公開（公告）號: CN101819651A
• 公開（公告）日: 2010-09-01
• 發(fā)明（設(shè)計(jì)）人: 陳天洲;袁輝;施青松;胡威;蔣冠軍;李敬賢
• 申請（專利權(quán)）人: 浙江大學(xué)
• 主分類號: G06N3/00
• 分類號: G06N3/00;G06F9/38;G06F9/50
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 林懷禹

技術(shù)領(lǐng)域

本發(fā)明涉及并行計(jì)算的粒子群算法技術(shù)，尤其涉及一種粒子群算法在多機(jī)上并行執(zhí)行的方法。

背景技術(shù)

隨著社會的發(fā)展，人們需要處理的問題越來越復(fù)雜，如工業(yè)控制過程中經(jīng)常碰到的最優(yōu)化問題。這些問題既無法通過數(shù)學(xué)方法獲得最優(yōu)解，同時由于規(guī)模巨大，復(fù)雜程度以階乘地速度上升，窮舉的方法也是不可行的.受到大自然的啟發(fā)，人們從大自然的運(yùn)行規(guī)律中找到了許多解決實(shí)際問題的辦法，這些方法被稱為啟發(fā)式算法(heuristic?algorithm)。近年來，演化算法，蟻群算法，擬人擬物算法和粒子群算法等相繼興起，掀起了研究啟發(fā)式算法的高潮。由于這些算法簡單有效，而且具有某種智能，因而成為科學(xué)計(jì)算與人類之間的橋梁。

其中粒子群優(yōu)化(Particle?Swarm?Optimi-zation，PSO)算法是一種新興的全局優(yōu)化技術(shù)。PSO算法同遺傳算法類似，是一種基于迭代的優(yōu)化算法。系統(tǒng)初始化為一組隨機(jī)解，然后通過粒子在解空間中追隨最優(yōu)粒子來搜索最優(yōu)值。其保留了基于種群的、并行的全局搜索策略，采用“速度一位移”模型，操作簡單，易于實(shí)現(xiàn)，同時又有深刻的智能背景，既適合科學(xué)研究，又特別適于工程應(yīng)用。作為一種簡單、有效的隨機(jī)全局優(yōu)化算法，PSO算法是一種有著潛在競爭力的最優(yōu)化算法。

但是在優(yōu)化復(fù)雜問題，比如訓(xùn)練大規(guī)模神經(jīng)網(wǎng)絡(luò)時，隨著神經(jīng)元數(shù)目的增多，待優(yōu)化參數(shù)的數(shù)目也隨之增多，從而造成進(jìn)化計(jì)算的搜索空間急劇增大，在單個CPU上運(yùn)行通常需要很長的計(jì)算時間，運(yùn)算效率低，有時運(yùn)行時間甚至長達(dá)幾天，大大降低了粒子群算法的實(shí)際應(yīng)用價值。

并行計(jì)算通過協(xié)同若干處理器進(jìn)行并行工作，可以有效解決大規(guī)模計(jì)算時間過長的問題。隨著個人計(jì)算機(jī)的日益普及，我們的身邊就有大量的可利用的計(jì)算資源，多機(jī)并行計(jì)算可以充分利用這些資源來提高計(jì)算效率，有著很好的實(shí)用價值。

由于粒子群算法和并行計(jì)算的技術(shù)都比較成熟，本發(fā)明中認(rèn)真研究粒子群算法流程中，分析了粒子群算法并行化的可行性，然后劃分粒子群算法中可并行的部分，通過MPI+openMP多核編程實(shí)現(xiàn)并行粒子群算法。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種粒子群算法在多機(jī)上并行執(zhí)行的方法。

本發(fā)明解決其技術(shù)問題采用的技術(shù)方案如下：

包括初始化步驟，評價和調(diào)整步驟，判斷終止條件步驟，結(jié)束并輸出步驟；其特征在于：所述的評價和調(diào)整步驟為通過MPI+OpenMP并行編程實(shí)現(xiàn)并行計(jì)算的部分；其具體步驟如下：

1)發(fā)現(xiàn)粒子群算法中的可并行部分：

分析粒子群算法流成圖，找出粒子群算法中并行計(jì)算的部分；并行計(jì)算部分應(yīng)滿足以下兩條原則，第一條原則：并行計(jì)算部分中的任務(wù)前后互不依賴，第二條原則：每個并行計(jì)算部分中的任務(wù)運(yùn)行時間相同，粒子群算法中，只有評價和調(diào)整步驟滿足以上兩條原則，通過并行計(jì)算加速粒子的評價計(jì)算和調(diào)整，從而達(dá)到加速粒子群算法的目的；

2)主從模式作為并行粒子群算法的通訊模式：

由一個計(jì)算機(jī)擔(dān)當(dāng)主機(jī)的角色，執(zhí)行粒子群算法中串行部分，并向多臺從機(jī)中分發(fā)任務(wù)，當(dāng)全部從機(jī)任務(wù)完成后，主機(jī)對全部從機(jī)的任務(wù)進(jìn)行收集和整理，并繼續(xù)開展下一步的工作；

3)MPI多機(jī)并行編程實(shí)現(xiàn)并行粒子群算法：

安裝MPICH2的Win32A32版本。每臺計(jì)算機(jī)的安裝相同，之后，通過MPICH與MSVC++6.0整合，通過C++語言和MPI庫函數(shù)進(jìn)行多核程序設(shè)計(jì)，實(shí)現(xiàn)主機(jī)和從機(jī)的任務(wù)分配，達(dá)到并行計(jì)算的效果；

4)基于局域網(wǎng)的并行計(jì)算：

通過VLAN或者子網(wǎng)掩碼技術(shù)設(shè)置局域網(wǎng)，并關(guān)閉所有計(jì)算機(jī)的防火墻，每一臺計(jì)算機(jī)劃定共享資源區(qū)域方便其他機(jī)器進(jìn)行訪問，在主機(jī)和從機(jī)通過局域網(wǎng)絡(luò)進(jìn)行通訊；

5)動態(tài)調(diào)配參與工作的計(jì)算機(jī)的數(shù)量：

在并行計(jì)算的過程中，首先引入一臺從機(jī)，然而引入一臺額外從機(jī)觀察效果，若加速比提高則引入第二臺額外從機(jī)，若加速比下降則踢出此臺從機(jī)，依次類推；

6)動態(tài)調(diào)配實(shí)現(xiàn)負(fù)載平衡：

并行計(jì)算的加速比往往會因?yàn)橐慌_計(jì)算速度慢的從機(jī)而下降，在任務(wù)分配的時，首先將部分任務(wù)平均分配給每一臺從機(jī)，當(dāng)發(fā)現(xiàn)某臺從機(jī)計(jì)算完成任務(wù)后，再給它分配額外的任務(wù)，直到任務(wù)全部完成，這種多能多勞的分配模式可以減少計(jì)算速度慢的計(jì)算機(jī)所帶來的損失；

7)OpenMP進(jìn)一步加速：

MPI并行編程將任務(wù)分配到每臺從機(jī)上，目前，多核計(jì)算機(jī)已經(jīng)非常普遍，為了提高并行計(jì)算的速度，通過openMP多核編程將從機(jī)上的任務(wù)進(jìn)一步并行化，比如前后無關(guān)的循環(huán)，矩陣，然而將它們分配到每個CPU上。