[發明專利]基于遺傳算法的流體機械并行仿真程序進程映射方法

有效

• 申請號: 201811063464.1
• 申請日: 2018-09-12
• 公開（公告）號: CN109241633B
• 公開（公告）日: 2021-03-23
• 發明（設計）人: 張興軍;安偉華;魏恒義;趙俊芳;張強龍;董小社;李靖波;伍衛國;鄒年俊;何峰
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F30/27
• 分類號: G06F30/27;G06F30/28;G06N3/12;G06F113/08;G06F119/14;G06F119/08
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 徐文權

1.基于遺傳算法的流體機械并行仿真程序進程映射方法，其特征在于，包括以下步驟：

步驟1，在流體機械并行仿真程序中，不同進程之間使用消息傳遞接口MPI進行通信；收集流體機械并行仿真程序各個MPI進程間的通信親和度信息，并記錄到日志文件中；

步驟2，從步驟1得到的日志文件中整理各個MPI進程間的通信親和度，建立一個進程通信模式矩陣G∈R^n×n，n表示流體機械并行仿真程序中MPI進程個數，其中的元素gi,gj，i∈n,j∈n表示進程i和進程j的通信親和度；

步驟3，通過Pingpong測試對用戶申請到的計算單元間的通信帶寬和通信延遲數據進行收集，對收集到的數據進行正規化整合，得到不同計算單元間的通信距離；Pingpong是測試任意兩個計算單元之間進行發送Ping并接收消息Pong來回所需時間的程序；

步驟4，定義流體機械并行仿真程序的通信開銷模型Z；如公式（ 1 ） 所示，G為步驟2提到的進程通信模式矩陣，H為步驟3提到的計算單元通信距離矩陣，π為MPI進程和計算單元間的一對一映射，g(i,j)為進程i和進程j的通信親和度，h(π(i),π(j))表示進程i和進程j所在計算單元之間的通信距離，通過計算得到流體機械并行仿真程序在進程映射π下的通信總開銷Z；

步驟5，將步驟2得到的進程通信模式矩陣G和步驟3得到的計算單元通信距離矩陣H整理到一個文件中，使用混合并行遺傳算法根據該文件中的數據求解最優的進程映射策略；將流體機械并行仿真程序的進程映射方案定義為個體，利用迭代的方式對種群中的個體進行選擇、交叉、變異、模擬退火操作，生成使得通信開銷Z最小的進程映射方案；

步驟6，根據步驟5中得到的進程映射策略，靜態綁定MPI進程到指定計算節點，重新運行流體機械并行仿真程序；

步驟5具體包括以下步驟：

1)編碼；對混合并行遺傳算法中的個體采用實數編碼，定義一個長度為n的實數編碼序列TP，對應于流體機械并行仿真程序的MPI進程數目；序列TP中，進程號所在的位置表示該進程所對應的計算單元；TP(k)＝p_i表示將流體機械并行仿真程序中的進程p_i，i∈n，映射到計算單元k上，其中k為計算單元的編號，p_i表示進程編號，k∈[0,n-1]，p_i∈[0，n-1]；在混合并行遺傳算法中，一個個體表示一種進程編號序列，對應一種進程映射方案；實數編碼表示流體機械模擬程序中進程號和計算單元的映射關系；

2)建立適應度函數；選擇步驟4提到的公式(1)作為適應度函數；適應度函數越小的個體表示其對應的進程映射策略通信開銷越小，在混合并行遺傳算法運行結束時，適應度函數最小的個體就是要求的最優個體，對應使得通信開銷最小的進程映射方案；

3)初始化；在混合并行遺傳算法中將0號進程稱為主進程，其他進程稱為從進程；用戶在算法運行前，在配置文件中設置遺傳算法的配置參數，包括種群規模、最大進化代數、交叉概率、選擇概率、變異概率和模擬退火算法的初始溫度T₀和終止溫度T_s；算法初始時主進程讀入配置文件，并將其中的配置參數通過MPI依次發送給其它從進程；從進程在接收到配置參數后，獨立地在本進程內產生初始種群；

4)在從進程中生成多個線程；各從進程調用OpenMP編譯指導語句生成多個線程，這些線程并行執行5)～9)，在主線程中保留當前種群中適應度函數最小的個體；OpenMP是一個針對共享內存架構的多線程編程標準，是基于顯示編譯指導語句的多線程程序編程接口；

5)選擇操作；采用精英保留和輪盤賭選擇兩種方法進行選擇操作；精英選擇是指在算法執行過程中，每一次迭代時，當前種群中的最優個體不參與遺傳及模擬退火操作，而是用它來替換本次迭代結束后種群中適應度最大的個體；輪盤賭選擇能保證當前種群中適應度函數值小的個體有更大的概率被遺傳到下一代；

6)交叉操作；在種群中隨機選擇兩個個體S1和S2進行交叉操作：隨機選擇一個交叉點r，r∈(0,n-1)，n為個體的長度，對應于流體機械并行仿真程序的MPI進程個數；以此交叉點r將S1和S2分別劃分為兩部分：前一部分長度為r，后一部分長度為n-r；將S1的后部分基因與S2的后部分基因進行交換，然后重新調整，保證兩個個體中的基因沒有重復出現，得到兩個新的個體S1’和S2’，將它們放到種群中；

7)變異操作；在種群中隨機選擇一個個體S，在S的序列中隨機選擇兩個位置的基因，將它們的位置進行交換，得到一個新的個體S’，將它放到種群中；

8)模擬退火操作；根據3)中的初始溫度T₀和終止溫度T_s，在每次迭代的最后一步，根據公式(2)計算當前的溫度T_i，其中k表示總的迭代步數，i表示當前迭代代數；

T_i＝0.6×(1+cos(i×π÷k))×(T₀-T_s)+T_s (2)

模擬退火的主要實現方式為：對于當前迭代產生的種群中的個體，依次計算它們的適應度函數值并進行比較；具體流程為，記最小的適應度函數值為Z_best，對于新的個體，其適應度函數值為Z_new，根據公式(3)計算適應度函數變化量Δ，當Δ0時，令Z_best＝Z_new，接受該個體，并將其加入到種群中；當Δ0時，以概率p接受該個體，p的計算方式如公式(4)所示；

Δ＝Z_new-Z_best (3)

p＝exp(Δ/T_i) (4)

9)各個進程執行優秀個體遷移操作；在主進程中設置一個優秀個體接收緩沖區，每隔一定的進化代數d，各個從進程就調用MPI的發送函數，向主進程的優秀個體接收緩沖區發送當前種群中的最優個體；主進程在接收到各個從進程發送的最優個體后，根據它們的適應度函數值進行排序，將適應度函數值最小的個體以廣播的方式發送給各個從進程；從進程接收到主進程發送的最優個體后，用最優個體替換掉當前種群中的適應度函數值最大的個體；

10)判斷混合并行遺傳算法是否結束；判斷當前進化代數i，當i等于3)中設置的最大進化代數時，算法結束，由主進程輸出求解得到的最優個體，即最優的進程號序列，否則轉到4)繼續執行。