基于蟻群算法的負載優化方法研究

于堯，趙忠文，郭皇皇

（裝備學院復雜電子系統仿真實驗室，北京101416）

為了充分挖掘并行仿真潛力，實現負載優化是提升并行仿真效率的關鍵問題。一般解決方式分為動態負載平衡和靜態負載平衡兩種算法，動態負載平衡[1-8]是一種通用的平衡方法，但這種方法本身存在通信開銷較大的問題，因此在特定的應用領域，靜態負載平衡設計一般比動態均衡算法更有效。在靜態負載平衡技術中，文獻[9]提出規則分塊算法和不規則分塊算法相結合的方法，從圖論的角度討論了靜態負載平衡問題，文獻[10-16]提出了基于蟻群算法的調度策略，提高了并行計算性能；文獻[17]提出基于最大-最小蟻群算法的模糊分類設計方法，實現了精確性與解釋性的折衷。但相關文獻對于仿真中存在的通信負載平衡問題研究相對較少，因此本文針對并行仿真通信負載的優化問題進行研究。

由于模型間的復雜交互，使通信負載和計算負載的測試及優化變得繁瑣及困難，本文將狀態通信問題轉化為模型間的交互作用，將模型的計算負載轉化為模型復雜度問題，通過蟻群算法將交互頻繁的仿真模型聚合到相同的處理器上，以減少處理器間模型消息傳遞的通信開銷，采用遺傳算法快速搜索優勢，以此彌補蟻群算法初期信息素匱乏導致算法收斂速度慢的缺陷。充分發揮多核處理器優勢，還需滿足不同處理器總模型復雜度均衡，從交互作用及模型復雜度兩個方面實現負載優化。

1　負載優化問題的簡化

仿真模型如何映射到多核處理器將會對仿真效率有很大的影響，由于同一個處理器上模型的通信開銷將遠小于不同處理器的通信開銷，因此應當將交互頻繁的仿真模型指派到同一個處理器上，以減少通信負載，為充分發揮多核處理器計算能力，每個處理器應根據自身處理能力以及模型的計算量進行適度映射。

由于模型間的狀態通信以及模型計算量在整個動態仿真中是變化的而且難以準確測量或描述，因此可將該問題簡化，將模型的通信問題轉化為模型交互作用問題，將模型的計算負載轉化為模型復雜度問題。模型的交互作用體現在傳遞消息上，傳遞消息的越頻繁，交互作用就越大，兩個模型間的通信越就緊密，因此將交互作用頻繁的模型聚合在同一個處理器上，將會減少通信開銷，模型的交互作用可根據模型的交互結構進行靜態分析計算。模型復雜度反映的是模型的計算量，模型設計的越復雜，可以認為模型的計算量越大，模型復雜度可采用群決策法進行分析計算，然后根據層次分析法可計算出各模型復雜程度的權重，該權重值即作為模型復雜度。但實際中模型的計算量不僅和模型的復雜度有關，還與模型在仿真中執行的頻率有關，因此可通過交互作用進行補償，即交互作用越大計算量越大。最后將交互作用頻繁的模型聚合在一起，映射到同一個處理器上以減少通信開銷，為充分發揮多核處理器性能，應保證每個處理器聚合后的模型復雜度相差較小。

1.1　交互作用的計算

靜態分析方法是圍繞仿真任務進行靜態分析的一種方法，所謂靜態指的是仿真運行前進行的處理器映射，在運行的過程中不作調整，直到運行結束為止。通過仿真任務在處理器上的合理映射，以達到仿真系統的綜合性能最優。

為了讓交互頻繁的模型映射到相同的處理器，我們可將模塊間的交互作用轉化為關系距離的概念，交互作用越大，兩者的關系距離則越小，按照關系距離對模型進行聚合，交互作用轉化為距離公式如式（2）所示，其中dijnew表示關系距離。

1.2　模型復雜度的計算

群決策也稱為多人決策，它是將不同知識結構及不同經驗的決策者集中在一起，彌補個人知識及經驗的不足的科學決策方法。在一個群決策過程中，大多要求各個決策者給出因素的評價分值或是比較的結果等。對于模型的復雜度的確定可根據模型的相互觸發關系、模型的內部設計結構、以及模型程序設計結構進行比較分析，形成決策者對各模型復雜程度的判斷矩陣。其模型復雜度比較的評語集應如表1所示。

表1　模型i對模型j復雜度的評語集

2　基于改進蟻群算法的處理器映射

為了讓交互頻繁的模型映射到相同的處理器上，我們首先需要對模型進行排序，排序的原則就是保證兩兩模型間的交互作用盡可能大，即模型間總的交互作用最大。我們將模塊間的交互作用轉化為關聯距離的概念，交互作用越大，兩者的關聯距離則越小，從而將每個處理器交互作用最大問題轉化為關聯距離最短問題。對于這類問題概率搜索算法有其獨特的優勢，但也有其明顯的缺陷，因此本節首先利用遺傳算法全局搜索的優勢對蟻群算法的初始信息素值進行修正，解決了蟻群算法前期由于初始信息素過低而引起的全局搜索收斂慢的問題，再利用蟻群算法的反饋機制尋找模型排序的最優解。為了充分發揮多核處理器的并行能力，需要將閉合排序按照關聯距離的大小進行切割聚類，從而保證每個組的交互作用盡可能的大，同時需要根據每個模型復雜度及每個處理器的能力進行計算負載平衡，從而讓每個處理器能夠充分發揮其計算能力。

2.1　改進的蟻群算法設計

1）遺傳算法編碼對模型的關聯距離進行二進制編碼，生成距離矩陣D，起始點到目標結束點的路徑序列作為一條染色體的編碼，每個染色體都代表了一個完整模型交互作用距離的路徑。

2）適應度函數設定染色體g的適應度函數如式（4）所示，其中的Dkikj表示第i個模型到第j個模型的距離。

3）選擇操作采用輪盤賭選擇方法，從舊群體按概率選擇到新群體當中。

4）交叉操作兩條染色體隨機選擇一個公共點作為交叉點，從起始點到交叉點的節點順序保持不變，將交叉點與目標節點間的順序相互交換。

5）變異操作一條染色體中任選兩個點進行位置互換。

6）遺傳算法結束在遺傳算法的迭代過程中同時統計進化率，公式為

設遺傳算法迭代次數為N，若連續三次進化率都小于最小進化率時，則停止遺傳算法迭代過程，進入蟻群算法。

7）遺傳算法對蟻群算法信息素的修正選擇遺傳算法結果的適應值最高的前10%條路徑V，作為蟻群算法的初始路徑，由于遺傳算法沒有信息素值，所以定義τF=k?F（g）為遺傳算法產生的信息素值，k為常數，當有多條路徑經過仿真模型位置時，τa需要進行疊加。因此，蟻群算法的信息素初值為τs=τa+τF，τa為常數。

8）目標點轉移概率采用輪盤賭原理的路徑選擇策略，見式（6），式（6）中的為t時刻螞蟻k從模型i轉移到模型j的概率。其中ηij（t）為啟發函數，表示螞蟻從模型i轉移到模型j的期望程度；allowk（k=1，2，…，m）為螞蟻k待訪問模型的集合；α為信息素重要程度因子，簡稱信息素因子，其值越大，表明信息素強度影響越大；β為啟發函數重要程度因子，簡稱啟發函數因子，其值越大，表明啟發函數影響越大。

9）信息度更新規則螞蟻在行走的同時，信息素的強度也在揮發而逐漸消失。式（7）中的ρ（0<ρ<1）表示信息素的揮發程度，信息素濃度為

其中式（8）中的Q為信息素常數，表示螞蟻循環一次所釋放的信息素總量；Lk為第k只螞蟻經過路徑的總長度，并記錄最短路徑時模型的連接順序。

2.2　模型聚類與處理器的映射

改進的蟻群算法按照總交互作用最大，其意義是兩兩模型間的交互作用也將越大，從而得到各模型連接的一個封閉的關聯環，關聯環上每個點代表了一個仿真模型，每個邊代表仿真模型間的關聯距離，整個關聯環點的順序體現了在總關聯距離最小時，仿真模型的連接順序，如圖1（a）所示。

如果僅考慮通信的切換開銷最小，將所有的模型映射到同一個處理器上，顯然通信的切換開銷將是最小的，但是多核處理器的性能顯然沒有發揮出來，因此還需要先將關聯環進行適當的劃分，將交互頻繁的模型聚類，然后將每段的模型映射到相應的處理器上，從而充分發揮多核處理器的并行計算優勢。

圖1　蟻群算法的關聯環示意圖

1）關聯環切割

關聯環的分割的過程實際是將交互頻繁的模型聚類的過程，根據關聯距離的大小進行切割的，其中關聯距離為無窮大的必須進行切割，這部分表示模型之間沒有任何交互作用，通常是模型是區域隔離的，例如某個地面雷達站只會定位其探測范圍內的飛機的位置，而距離其較遠未知的飛機與該雷達如果沒有任何交互，因此他們的關聯距離才會為無窮大，因此先進行切割。然后依次按照關聯距離的由大到小將關聯環進行切割，如圖1（b）所示，直到發生斷開邊的模型存在緊密的交互作用后停止切分（設置關聯距離小于某一閾值即停止），我們可認為剩余連接的模型都是交互頻繁的。

2）處理器的映射

切割后的n組模型需要再一次重組到m個處理器上，為了充分發揮處理器的計算能力，處理器的映射應該考慮計算負載平衡，其目的在于讓所有處理器盡量在相同的時間根據各自的處理能力完成各自相應的任務量。在此我們忽略并行仿真中每個處理器等待其他處理器的消息的時間，僅考慮處理器的效率因素，分配給處理器相應的任務量，即處理效率即比為任務量分配比，可按照式（9）計算每個處理器應分配的任務量，其中P代表處理器的計算能力，C代表聚合后的各段模型總復雜度，右下標數字代表處理器標號。

然后根據式（10）檢驗每個處理器的計算負載是否平衡，其中α為允許的誤差范圍，其中i為處理器標號，其取值范圍為1，2…m。

3　實驗驗證及分析

實驗算例采用的是某個導彈突防仿真，對敵方分布的5個目標群分別使用128/256/314/512/640枚導彈進行目標群轟炸，每個目標群含有一套雷達干擾設備，導彈分配到5個目標群數量比為26:26:26:25:25，采用上述方法將仿真模型映射到多核處理器進行并行仿真。

1）模型間交互作用及模型復雜度

將該仿真分成5個子任務，D1R1、D2R2、…、D5R5，其中D代表導彈，R代表雷達設備，導彈具有移動模型，雷達具有決策模型、干擾模型和移動模型，模型的t、p、s以及模型間的交互作用計算如表2所示，未說明模型間交互作用記為0；通過群決策法可得4個模型復雜度分別為0.53、0.11、0.08、0.29。

表2　模型間的交互作用

2）蟻群算法的聚類

按照式（2）將交互作用轉化為關系距離，按照式（4）-（8）的蟻群算法將模型進行排序，然后根據關聯距離的大小將模型聚類，停止切分的的關聯距離閾值設置為R1-R5的模型間交互作用的最小值。利用MATLAB實現改進的蟻群算法的模型聚類的過程，其實驗參數設定如表3所示。

表3　實驗參數設定

MATLAB的仿真結果如圖2所示，其中1-5分別代表D1-D5的移動模型，6-8、9-11、12-14、15-17、18-20分別代表R1-R5的3個模型。比較傳統蟻群算法和改進的蟻群算法，5次實驗的平均運行時間分別由20.40 s提高到11.88 s，驗證了算法改進的有效性。

圖2　模型交互作用的聚合圖

3）處理器的映射

以128個導彈的處理器分配為例，根據每個處理器的模型復雜度平衡原則將模型映射到處理器上。映射到四核和八核處理器上，結果如表4和表5所示。

表4　四核處理器的模型映射關系

表5　八核處理器的模型映射關系

4）仿真實驗驗

基于ROSS仿真引擎對上述模型進行實現，將模型分別映射到處理器為四、八核的處理器上進行運行，并與串行仿真進行比較，比較結果如圖3所示，經比較發現并行仿真中，四核處理器仿真效率比串行提高63.0%，八核處理器仿真效率比串行提高73.6%，均能夠較好的發揮并行仿真的能力，說明了該方法能夠通過模型合理映射到處理器上實現負載的優化，能夠比較充分發揮多核處理器的性能，驗證了該方法的有效性。

圖3　并行仿真與串行仿真的效率對比

4　結束語

本文將仿真模型通信負載及計算負載問題簡化為模型交互作用及模型復雜度問題，利用改進的蟻群算法將模型按照交互作用進行排序和聚類，并根據模型復雜度以及處理器的能力將模型映射到處理器上，該方法能夠減少仿真中的通信開銷，并能充分發揮仿真的并行程度，在導彈突防的仿真中得到了很好的效果，證明了該方法在并行仿真的負載優化的有效性。