[發明專利]粒子群算法在多機上并行執行的方法

無效

• 申請號: 201010148490.1
• 申請日: 2010-04-16
• 公開（公告）號: CN101819651A
• 公開（公告）日: 2010-09-01
• 發明（設計）人: 陳天洲;袁輝;施青松;胡威;蔣冠軍;李敬賢
• 申請（專利權）人: 浙江大學
• 主分類號: G06N3/00
• 分類號: G06N3/00;G06F9/38;G06F9/50
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 林懷禹

1.一種粒子群算法在多機上并行執行的方法，包括初始化步驟，評價和調整步驟，判斷終止條件步驟，結束并輸出步驟；其特征在于：所述的評價和調整步驟為通過MPI+OpenMP并行編程實現并行計算的部分；其具體步驟如下：

1)發現粒子群算法中的可并行部分：

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

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

由一個計算機擔當主機的角色，執行粒子群算法中串行部分，并向多臺從機中分發任務，當全部從機任務完成后，主機對全部從機的任務進行收集和整理，并繼續開展下一步的工作；

3)MPI多機并行編程實現并行粒子群算法：

安裝MPICH2的Win32A32版本。每臺計算機的安裝相同，之后，通過MPICH與MSVC++6.0整合，通過C++語言和MPI庫函數進行多核程序設計，實現主機和從機的任務分配，達到并行計算的效果；

4)基于局域網的并行計算：

通過VLAN或者子網掩碼技術設置局域網，并關閉所有計算機的防火墻，每一臺計算機劃定共享資源區域方便其他機器進行訪問，在主機和從機通過局域網絡進行通訊；

5)動態調配參與工作的計算機的數量：

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

6)動態調配實現負載平衡：

并行計算的加速比往往會因為一臺計算速度慢的從機而下降，在任務分配的時，首先將部分任務平均分配給每一臺從機，當發現某臺從機計算完成任務后，再給它分配額外的任務，直到任務全部完成，這種多能多勞的分配模式可以減少計算速度慢的計算機所帶來的損失；

7)OpenMP進一步加速：

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