基于蟻群算法的負(fù)載優(yōu)化方法研究

于堯，趙忠文，郭皇皇

（裝備學(xué)院復(fù)雜電子系統(tǒng)仿真實(shí)驗(yàn)室，北京101416）

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

由于模型間的復(fù)雜交互，使通信負(fù)載和計(jì)算負(fù)載的測(cè)試及優(yōu)化變得繁瑣及困難，本文將狀態(tài)通信問(wèn)題轉(zhuǎn)化為模型間的交互作用，將模型的計(jì)算負(fù)載轉(zhuǎn)化為模型復(fù)雜度問(wèn)題，通過(guò)蟻群算法將交互頻繁的仿真模型聚合到相同的處理器上，以減少處理器間模型消息傳遞的通信開(kāi)銷(xiāo)，采用遺傳算法快速搜索優(yōu)勢(shì)，以此彌補(bǔ)蟻群算法初期信息素匱乏導(dǎo)致算法收斂速度慢的缺陷。充分發(fā)揮多核處理器優(yōu)勢(shì)，還需滿(mǎn)足不同處理器總模型復(fù)雜度均衡，從交互作用及模型復(fù)雜度兩個(gè)方面實(shí)現(xiàn)負(fù)載優(yōu)化。

1　負(fù)載優(yōu)化問(wèn)題的簡(jiǎn)化

仿真模型如何映射到多核處理器將會(huì)對(duì)仿真效率有很大的影響，由于同一個(gè)處理器上模型的通信開(kāi)銷(xiāo)將遠(yuǎn)小于不同處理器的通信開(kāi)銷(xiāo)，因此應(yīng)當(dāng)將交互頻繁的仿真模型指派到同一個(gè)處理器上，以減少通信負(fù)載，為充分發(fā)揮多核處理器計(jì)算能力，每個(gè)處理器應(yīng)根據(jù)自身處理能力以及模型的計(jì)算量進(jìn)行適度映射。

由于模型間的狀態(tài)通信以及模型計(jì)算量在整個(gè)動(dòng)態(tài)仿真中是變化的而且難以準(zhǔn)確測(cè)量或描述，因此可將該問(wèn)題簡(jiǎn)化，將模型的通信問(wèn)題轉(zhuǎn)化為模型交互作用問(wèn)題，將模型的計(jì)算負(fù)載轉(zhuǎn)化為模型復(fù)雜度問(wèn)題。模型的交互作用體現(xiàn)在傳遞消息上，傳遞消息的越頻繁，交互作用就越大，兩個(gè)模型間的通信越就緊密，因此將交互作用頻繁的模型聚合在同一個(gè)處理器上，將會(huì)減少通信開(kāi)銷(xiāo)，模型的交互作用可根據(jù)模型的交互結(jié)構(gòu)進(jìn)行靜態(tài)分析計(jì)算。模型復(fù)雜度反映的是模型的計(jì)算量，模型設(shè)計(jì)的越復(fù)雜，可以認(rèn)為模型的計(jì)算量越大，模型復(fù)雜度可采用群決策法進(jìn)行分析計(jì)算，然后根據(jù)層次分析法可計(jì)算出各模型復(fù)雜程度的權(quán)重，該權(quán)重值即作為模型復(fù)雜度。但實(shí)際中模型的計(jì)算量不僅和模型的復(fù)雜度有關(guān)，還與模型在仿真中執(zhí)行的頻率有關(guān)，因此可通過(guò)交互作用進(jìn)行補(bǔ)償，即交互作用越大計(jì)算量越大。最后將交互作用頻繁的模型聚合在一起，映射到同一個(gè)處理器上以減少通信開(kāi)銷(xiāo)，為充分發(fā)揮多核處理器性能，應(yīng)保證每個(gè)處理器聚合后的模型復(fù)雜度相差較小。

1.1　交互作用的計(jì)算

靜態(tài)分析方法是圍繞仿真任務(wù)進(jìn)行靜態(tài)分析的一種方法，所謂靜態(tài)指的是仿真運(yùn)行前進(jìn)行的處理器映射，在運(yùn)行的過(guò)程中不作調(diào)整，直到運(yùn)行結(jié)束為止。通過(guò)仿真任務(wù)在處理器上的合理映射，以達(dá)到仿真系統(tǒng)的綜合性能最優(yōu)。

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

1.2　模型復(fù)雜度的計(jì)算

群決策也稱(chēng)為多人決策，它是將不同知識(shí)結(jié)構(gòu)及不同經(jīng)驗(yàn)的決策者集中在一起，彌補(bǔ)個(gè)人知識(shí)及經(jīng)驗(yàn)的不足的科學(xué)決策方法。在一個(gè)群決策過(guò)程中，大多要求各個(gè)決策者給出因素的評(píng)價(jià)分值或是比較的結(jié)果等。對(duì)于模型的復(fù)雜度的確定可根據(jù)模型的相互觸發(fā)關(guān)系、模型的內(nèi)部設(shè)計(jì)結(jié)構(gòu)、以及模型程序設(shè)計(jì)結(jié)構(gòu)進(jìn)行比較分析，形成決策者對(duì)各模型復(fù)雜程度的判斷矩陣。其模型復(fù)雜度比較的評(píng)語(yǔ)集應(yīng)如表1所示。

表1　模型i對(duì)模型j復(fù)雜度的評(píng)語(yǔ)集

2　基于改進(jìn)蟻群算法的處理器映射

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

2.1　改進(jìn)的蟻群算法設(shè)計(jì)

1）遺傳算法編碼對(duì)模型的關(guān)聯(lián)距離進(jìn)行二進(jìn)制編碼，生成距離矩陣D，起始點(diǎn)到目標(biāo)結(jié)束點(diǎn)的路徑序列作為一條染色體的編碼，每個(gè)染色體都代表了一個(gè)完整模型交互作用距離的路徑。

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

3）選擇操作采用輪盤(pán)賭選擇方法，從舊群體按概率選擇到新群體當(dāng)中。

4）交叉操作兩條染色體隨機(jī)選擇一個(gè)公共點(diǎn)作為交叉點(diǎn)，從起始點(diǎn)到交叉點(diǎn)的節(jié)點(diǎn)順序保持不變，將交叉點(diǎn)與目標(biāo)節(jié)點(diǎn)間的順序相互交換。

5）變異操作一條染色體中任選兩個(gè)點(diǎn)進(jìn)行位置互換。

6）遺傳算法結(jié)束在遺傳算法的迭代過(guò)程中同時(shí)統(tǒng)計(jì)進(jìn)化率，公式為

設(shè)遺傳算法迭代次數(shù)為N，若連續(xù)三次進(jìn)化率都小于最小進(jìn)化率時(shí)，則停止遺傳算法迭代過(guò)程，進(jìn)入蟻群算法。

7）遺傳算法對(duì)蟻群算法信息素的修正選擇遺傳算法結(jié)果的適應(yīng)值最高的前10%條路徑V，作為蟻群算法的初始路徑，由于遺傳算法沒(méi)有信息素值，所以定義τF=k?F（g）為遺傳算法產(chǎn)生的信息素值，k為常數(shù)，當(dāng)有多條路徑經(jīng)過(guò)仿真模型位置時(shí)，τa需要進(jìn)行疊加。因此，蟻群算法的信息素初值為τs=τa+τF，τa為常數(shù)。

8）目標(biāo)點(diǎn)轉(zhuǎn)移概率采用輪盤(pán)賭原理的路徑選擇策略，見(jiàn)式（6），式（6）中的為t時(shí)刻螞蟻k從模型i轉(zhuǎn)移到模型j的概率。其中ηij（t）為啟發(fā)函數(shù)，表示螞蟻從模型i轉(zhuǎn)移到模型j的期望程度；allowk（k=1，2，…，m）為螞蟻k待訪(fǎng)問(wèn)模型的集合；α為信息素重要程度因子，簡(jiǎn)稱(chēng)信息素因子，其值越大，表明信息素強(qiáng)度影響越大；β為啟發(fā)函數(shù)重要程度因子，簡(jiǎn)稱(chēng)啟發(fā)函數(shù)因子，其值越大，表明啟發(fā)函數(shù)影響越大。

9）信息度更新規(guī)則螞蟻在行走的同時(shí)，信息素的強(qiáng)度也在揮發(fā)而逐漸消失。式（7）中的ρ（0<ρ<1）表示信息素的揮發(fā)程度，信息素濃度為

其中式（8）中的Q為信息素常數(shù)，表示螞蟻循環(huán)一次所釋放的信息素總量；Lk為第k只螞蟻經(jīng)過(guò)路徑的總長(zhǎng)度，并記錄最短路徑時(shí)模型的連接順序。

2.2　模型聚類(lèi)與處理器的映射

改進(jìn)的蟻群算法按照總交互作用最大，其意義是兩兩模型間的交互作用也將越大，從而得到各模型連接的一個(gè)封閉的關(guān)聯(lián)環(huán)，關(guān)聯(lián)環(huán)上每個(gè)點(diǎn)代表了一個(gè)仿真模型，每個(gè)邊代表仿真模型間的關(guān)聯(lián)距離，整個(gè)關(guān)聯(lián)環(huán)點(diǎn)的順序體現(xiàn)了在總關(guān)聯(lián)距離最小時(shí)，仿真模型的連接順序，如圖1（a）所示。

如果僅考慮通信的切換開(kāi)銷(xiāo)最小，將所有的模型映射到同一個(gè)處理器上，顯然通信的切換開(kāi)銷(xiāo)將是最小的，但是多核處理器的性能顯然沒(méi)有發(fā)揮出來(lái)，因此還需要先將關(guān)聯(lián)環(huán)進(jìn)行適當(dāng)?shù)膭澐?，將交互頻繁的模型聚類(lèi)，然后將每段的模型映射到相應(yīng)的處理器上，從而充分發(fā)揮多核處理器的并行計(jì)算優(yōu)勢(shì)。

圖1　蟻群算法的關(guān)聯(lián)環(huán)示意圖

1）關(guān)聯(lián)環(huán)切割

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

2）處理器的映射

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

然后根據(jù)式（10）檢驗(yàn)每個(gè)處理器的計(jì)算負(fù)載是否平衡，其中α為允許的誤差范圍，其中i為處理器標(biāo)號(hào)，其取值范圍為1，2…m。

3　實(shí)驗(yàn)驗(yàn)證及分析

實(shí)驗(yàn)算例采用的是某個(gè)導(dǎo)彈突防仿真，對(duì)敵方分布的5個(gè)目標(biāo)群分別使用128/256/314/512/640枚導(dǎo)彈進(jìn)行目標(biāo)群轟炸，每個(gè)目標(biāo)群含有一套雷達(dá)干擾設(shè)備，導(dǎo)彈分配到5個(gè)目標(biāo)群數(shù)量比為26:26:26:25:25，采用上述方法將仿真模型映射到多核處理器進(jìn)行并行仿真。

1）模型間交互作用及模型復(fù)雜度

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

表2　模型間的交互作用

2）蟻群算法的聚類(lèi)

按照式（2）將交互作用轉(zhuǎn)化為關(guān)系距離，按照式（4）-（8）的蟻群算法將模型進(jìn)行排序，然后根據(jù)關(guān)聯(lián)距離的大小將模型聚類(lèi)，停止切分的的關(guān)聯(lián)距離閾值設(shè)置為R1-R5的模型間交互作用的最小值。利用MATLAB實(shí)現(xiàn)改進(jìn)的蟻群算法的模型聚類(lèi)的過(guò)程，其實(shí)驗(yàn)參數(shù)設(shè)定如表3所示。

表3　實(shí)驗(yàn)參數(shù)設(shè)定

MATLAB的仿真結(jié)果如圖2所示，其中1-5分別代表D1-D5的移動(dòng)模型，6-8、9-11、12-14、15-17、18-20分別代表R1-R5的3個(gè)模型。比較傳統(tǒng)蟻群算法和改進(jìn)的蟻群算法，5次實(shí)驗(yàn)的平均運(yùn)行時(shí)間分別由20.40 s提高到11.88 s，驗(yàn)證了算法改進(jìn)的有效性。

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

3）處理器的映射

以128個(gè)導(dǎo)彈的處理器分配為例，根據(jù)每個(gè)處理器的模型復(fù)雜度平衡原則將模型映射到處理器上。映射到四核和八核處理器上，結(jié)果如表4和表5所示。

表4　四核處理器的模型映射關(guān)系

表5　八核處理器的模型映射關(guān)系

4）仿真實(shí)驗(yàn)驗(yàn)

基于ROSS仿真引擎對(duì)上述模型進(jìn)行實(shí)現(xiàn)，將模型分別映射到處理器為四、八核的處理器上進(jìn)行運(yùn)行，并與串行仿真進(jìn)行比較，比較結(jié)果如圖3所示，經(jīng)比較發(fā)現(xiàn)并行仿真中，四核處理器仿真效率比串行提高63.0%，八核處理器仿真效率比串行提高73.6%，均能夠較好的發(fā)揮并行仿真的能力，說(shuō)明了該方法能夠通過(guò)模型合理映射到處理器上實(shí)現(xiàn)負(fù)載的優(yōu)化，能夠比較充分發(fā)揮多核處理器的性能，驗(yàn)證了該方法的有效性。

圖3　并行仿真與串行仿真的效率對(duì)比

4　結(jié)束語(yǔ)

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