段焰輝，周鑫，高詩(shī)婕茜，林錦星，張懷寶，王光學(xué),*

1. 中山大學(xué) 系統(tǒng)科學(xué)與工程學(xué)院，廣州 510006

2. 中山大學(xué) 智能工程學(xué)院，廣州 510006

3. 中山大學(xué) 航空航天學(xué)院，廣州 510006

計(jì)算流體力學(xué)(Computational Fluid Dynamic，CFD)在航空、航天、航海、能源等領(lǐng)域都發(fā)揮著重要作用。隨著求解問(wèn)題難度的增加和求解精度要求的提高，CFD的計(jì)算量急劇增加，計(jì)算周期隨之延長(zhǎng)。并行計(jì)算能夠有效地縮短計(jì)算周期，其原理是將計(jì)算網(wǎng)格分組并分配給高性能計(jì)算機(jī)的各個(gè)進(jìn)程，進(jìn)程之間通過(guò)傳遞網(wǎng)格面上的流場(chǎng)信息實(shí)現(xiàn)信息交互。分配給各個(gè)進(jìn)程的網(wǎng)格量均勻性以及通信相關(guān)的面網(wǎng)格量均勻性是影響并行計(jì)算效率的關(guān)鍵，負(fù)載平衡是解決網(wǎng)格量和通信相關(guān)面網(wǎng)格的分配問(wèn)題。中國(guó)已啟動(dòng)國(guó)家數(shù)值風(fēng)洞工程[1]以發(fā)展完全自主知識(shí)產(chǎn)權(quán)的計(jì)算流體力學(xué)軟件，該軟件為不同類型網(wǎng)格塊的數(shù)據(jù)交換設(shè)計(jì)了通用的通信模型及粗粒度MPI/OpenMP(Message Passing Interface/Open Multi-Processing)混合并行模型，因此適用于任意網(wǎng)格類型，且具有良好的擴(kuò)展性和并行效率[2]。網(wǎng)格負(fù)載平衡問(wèn)題是影響CFD并行計(jì)算的另一重要因素，因此也是國(guó)家數(shù)值風(fēng)洞工程的重要研究?jī)?nèi)容。

用于計(jì)算流體力學(xué)的負(fù)載平衡方法大致可分為兩類：幾何剖分法和圖剖分法[3]。幾何剖分方法包括Berger和Bokhari提出的遞歸坐標(biāo)對(duì)分法(RCB)[4]，以解決自適應(yīng)網(wǎng)格優(yōu)化策略為目的；還包括RCB的推廣，如遞歸慣性對(duì)分法(RIB)[5]和空間填充曲線法[6]等。圖剖分法[7]一般用權(quán)重圖表示計(jì)算和通信，包括多層譜對(duì)分方法(MSB)[8]、多層剖分方法[9]、超圖剖分法[10]以及多約束多目標(biāo)剖分方法[11]。其中圖剖分算法發(fā)展迅速，已形成多種應(yīng)用軟件，如ParMETIS[12]和Zoltan[13]。對(duì)于多塊結(jié)構(gòu)網(wǎng)格，劉宏康等將圖剖分用于結(jié)構(gòu)重疊網(wǎng)格的負(fù)載平衡[14]；李桂波和楊國(guó)偉采用遺傳算法對(duì)多塊結(jié)構(gòu)網(wǎng)格的分配進(jìn)行研究，但其目標(biāo)函數(shù)僅考慮計(jì)算時(shí)間，僅按通信時(shí)間選擇結(jié)果[15]；唐波以通信時(shí)間為指標(biāo)、計(jì)算時(shí)間為約束構(gòu)造目標(biāo)函數(shù)，采用遺傳算法對(duì)網(wǎng)格分配進(jìn)行研究[16]。綜上，對(duì)于負(fù)載平衡問(wèn)題多采用優(yōu)化思想求解，但所用優(yōu)化算法均有局限，如貪婪算法[17-18]效率較高且能在優(yōu)化過(guò)程中剖分大塊網(wǎng)格，但不考慮通信時(shí)間的平衡；遺傳算法能通過(guò)設(shè)計(jì)目標(biāo)函數(shù)的方式同時(shí)考慮計(jì)算時(shí)間和通信時(shí)間的平衡，但其結(jié)果依賴于目標(biāo)函數(shù)的構(gòu)造，而且遺傳算法本身不能對(duì)網(wǎng)格進(jìn)行剖分。

混合優(yōu)化策略能結(jié)合不同優(yōu)化算法的優(yōu)勢(shì)，并在一定程度上克服不同算法的缺點(diǎn)?；旌蟽?yōu)化策略已有較多研究與應(yīng)用[19-20]，其中兩步優(yōu)化策略構(gòu)造的混合優(yōu)化方法[21]充分結(jié)合兩步優(yōu)化方法的優(yōu)點(diǎn)，獲得了高效的優(yōu)化算法。本文將貪婪算法和遺傳算法相結(jié)合，構(gòu)造兩步優(yōu)化算法：第1步優(yōu)化采用傳統(tǒng)的貪婪算法完成對(duì)大塊網(wǎng)格的剖分和以進(jìn)程計(jì)算時(shí)間為指標(biāo)的網(wǎng)格塊分配；第2步采用遺傳算法，目標(biāo)函數(shù)兼顧進(jìn)程計(jì)算時(shí)間和通信時(shí)間，在第1步優(yōu)化結(jié)果的基礎(chǔ)上對(duì)網(wǎng)格塊在進(jìn)程上的分配開(kāi)展二次優(yōu)化。兩步優(yōu)化策略克服了遺傳算法無(wú)法對(duì)大塊網(wǎng)格剖分以及貪婪算法不能考慮通信時(shí)間的缺陷。

本文首先介紹了負(fù)載平衡算法，包括兩步優(yōu)化策略、用于計(jì)算時(shí)間和通信時(shí)間的模型構(gòu)建方法和遺傳算法，然后采用3個(gè)算例對(duì)提出的兩步優(yōu)化策略進(jìn)行驗(yàn)證，最后根據(jù)驗(yàn)證結(jié)果對(duì)兩步優(yōu)化策略的優(yōu)缺點(diǎn)進(jìn)行總結(jié)。

1 算法介紹

1.1 數(shù)學(xué)模型及求解思路

結(jié)構(gòu)化網(wǎng)格的負(fù)載平衡主要處理兩個(gè)方面問(wèn)題：網(wǎng)格塊在進(jìn)程上的分配問(wèn)題和大網(wǎng)格塊的切割問(wèn)題。在貪婪算法的分配過(guò)程中實(shí)現(xiàn)對(duì)結(jié)構(gòu)化網(wǎng)格負(fù)載平衡中的網(wǎng)格塊切割問(wèn)題，因非本文重點(diǎn)，不予贅述，相關(guān)方法可參考文獻(xiàn)[16]。對(duì)于網(wǎng)格塊在進(jìn)程上的分配問(wèn)題，用如下假設(shè)進(jìn)行處理：設(shè)負(fù)載平衡問(wèn)題的進(jìn)程個(gè)數(shù)為Np、網(wǎng)格塊個(gè)數(shù)為Nb，滿足Nb≥Np。以M表示某種分配方式，第i個(gè)進(jìn)程處理結(jié)構(gòu)網(wǎng)格計(jì)算問(wèn)題的總用時(shí)可表示為

(1)

(2)

負(fù)載平衡問(wèn)題的目標(biāo)函數(shù)即是所有進(jìn)程的最大總用時(shí)：

(3)

求解結(jié)構(gòu)化網(wǎng)格的負(fù)載平衡問(wèn)題即是最小化式(3)的最優(yōu)化問(wèn)題：

minf(M)

(4)

該優(yōu)化問(wèn)題的設(shè)計(jì)變量是網(wǎng)格塊在進(jìn)程上的分配方式，是一種組合優(yōu)化問(wèn)題。

傳統(tǒng)求解結(jié)構(gòu)化網(wǎng)格負(fù)載平衡問(wèn)題的方法是貪婪算法，這種方法在優(yōu)化過(guò)程中僅考慮網(wǎng)格單元的數(shù)量，沒(méi)有考慮通訊相關(guān)的面網(wǎng)格數(shù)量，因此所得結(jié)果在大部分情況下都不是最優(yōu)解。在貪婪算法的基礎(chǔ)上，再引入用于組合優(yōu)化的遺傳算法，通過(guò)合理組織兩步優(yōu)化策略以克服傳統(tǒng)算法未考慮通信時(shí)間的缺陷。具體而言，優(yōu)化策略可分為兩步：

1) 采用貪婪算法對(duì)初始結(jié)構(gòu)化網(wǎng)格開(kāi)展初步負(fù)載平衡優(yōu)化。主要完成兩方面的內(nèi)容：對(duì)大塊網(wǎng)格的分割和以計(jì)算時(shí)間為指標(biāo)的網(wǎng)格塊分配。

2) 采用遺傳算法對(duì)第1步的優(yōu)化結(jié)果進(jìn)行二次優(yōu)化。將組合優(yōu)化的遺傳操作、引入第1步優(yōu)化結(jié)果的種群初始化方法、綜合進(jìn)程計(jì)算時(shí)間和通信時(shí)間的目標(biāo)函數(shù)計(jì)算方法相結(jié)合，形成適用于結(jié)構(gòu)網(wǎng)格負(fù)載平衡的遺傳算法。

1.2 計(jì)算時(shí)間和通信時(shí)間的建模方法

采用統(tǒng)計(jì)學(xué)的回歸思想建立時(shí)間計(jì)算模型，需要重點(diǎn)解決三方面的問(wèn)題：如何生成樣本、如何建模和如何對(duì)模型進(jìn)行驗(yàn)證。選擇恰當(dāng)?shù)挠?jì)算網(wǎng)格，通過(guò)逐漸增加網(wǎng)格量獲取計(jì)算時(shí)間隨網(wǎng)格單元數(shù)量以及通信時(shí)間隨通訊相關(guān)面網(wǎng)格數(shù)量的樣本，同時(shí)要充分考慮計(jì)算平臺(tái)硬件和操作系統(tǒng)的影響；建模需要根據(jù)樣本的分布規(guī)律合理選擇適當(dāng)?shù)哪Ｐ?；模型?yàn)證通過(guò)與真實(shí)的模型計(jì)算時(shí)間對(duì)比以檢驗(yàn)?zāi)Ｐ偷臏?zhǔn)確度。

1.2.1 樣本生成與預(yù)處理

CFD并行計(jì)算的計(jì)算時(shí)間和通信時(shí)間都會(huì)受計(jì)算平臺(tái)硬件和操作系統(tǒng)的擾動(dòng)影響。若影響為小量，則通過(guò)統(tǒng)計(jì)平均消除擾動(dòng)；若為大量，則作為奇異點(diǎn)處理。通過(guò)對(duì)多個(gè)具有相同硬件配置節(jié)點(diǎn)的計(jì)算結(jié)果對(duì)進(jìn)程數(shù)求平均的方式，消除硬件和系統(tǒng)誤差；采用先以CFD軟件計(jì)算多步再對(duì)步數(shù)求平均的方式，消除操作系統(tǒng)和計(jì)算軟件自身的影響；重復(fù)采樣多次，對(duì)采樣次數(shù)做平均以進(jìn)一步消除硬件、操作系統(tǒng)和計(jì)算軟件的影響。

j=1,2,…,Nsamp

(5)

式中：Nsamp為每次采樣時(shí)樣本的數(shù)量。另需要注意的是，式(5)的計(jì)算方式假定每個(gè)塊的計(jì)算量是相同的，但實(shí)際情況是物理邊界會(huì)造成計(jì)算量的微小偏差，因?yàn)橛糜谟?jì)算物理邊界的網(wǎng)格量相對(duì)于整體網(wǎng)格量很小，因此可以忽略物理邊界造成的計(jì)算量偏差。

j=1,2,…,Nsamp

(6)

圖1 采樣網(wǎng)格及邊界條件設(shè)置示意圖Fig.1 Schematic diagram of sampling grid and boundary conditions

圖2給出了10次采樣的結(jié)果。計(jì)算時(shí)間的結(jié)果顯示出雙線性特點(diǎn)，經(jīng)過(guò)后期多次測(cè)試，數(shù)據(jù)都呈現(xiàn)了相同的趨勢(shì)。推測(cè)應(yīng)與計(jì)算平臺(tái)有關(guān)，但具體原因分析不在研究范疇內(nèi)，且所有計(jì)算均使用相同計(jì)算平臺(tái)，只要建立相應(yīng)的模型就不會(huì)影響后期模型的計(jì)算精度。通信時(shí)間的結(jié)果整體呈線性分布，但部分樣本點(diǎn)存在較大偏差，屬于奇異點(diǎn)。假設(shè)多次采樣的數(shù)據(jù)服從正態(tài)分布，采用正態(tài)分布數(shù)理統(tǒng)計(jì)的方法對(duì)采樣結(jié)果進(jìn)行統(tǒng)計(jì)分析。采用1.96σ的置信區(qū)間，其中σ為標(biāo)準(zhǔn)差，利用在置信區(qū)間內(nèi)樣本點(diǎn)的平均值替換奇異點(diǎn)[22]。處理后的數(shù)據(jù)點(diǎn)如圖3所示。

圖2 10組采樣數(shù)據(jù)Fig.2 Ten sets of sampled data

圖3 處理奇異點(diǎn)后的采樣數(shù)據(jù)Fig.3 Sampled data without singularities

1.2.2 線性回歸建模

鑒于樣本數(shù)據(jù)都呈現(xiàn)線性分布，采用線性回歸的思路建立線性模型。對(duì)于體網(wǎng)格和計(jì)算時(shí)間模型分別建立單線性模型和雙線性模型，并對(duì)結(jié)果進(jìn)行對(duì)比。單線性模型的結(jié)果如式(7)所示，模型與真值的對(duì)比如圖4所示。

圖4 單線性模型與樣本點(diǎn)對(duì)比Fig.4 Comparison between single linear model and sample points

T(xv)=4.342 2×10-6xv-3.518 2×10-2

(7)

式中：T為計(jì)算時(shí)間；xv為體網(wǎng)格單元數(shù)量。

雙線性模型的結(jié)果如式(8)所示，模型與真值的對(duì)比如圖5所示。

(8)

由圖4可知，單線性模型主要擬合了第2段數(shù)據(jù)，所以最大誤差出現(xiàn)在第1段數(shù)據(jù)的末端，對(duì)第1段數(shù)據(jù)的擬合程度很差。圖5雙線性模型的擬合精度明顯提高，最大誤差位置僅出現(xiàn)在整個(gè)數(shù)據(jù)的前端。表1給出了兩種模型的誤差對(duì)比，雙線性模型的均方誤差和最大誤差均優(yōu)于單線性模型，因此選擇雙線性模型。

表1 單線性模型和雙線性模型的精度對(duì)比Table 1 Accuracy comparison between single linear model and double linear model

圖5 雙線性模型與樣本點(diǎn)對(duì)比Fig.5 Comparison between double linear model and sample points

同理建立通信時(shí)間的線性模型，如式(9)所示，均方誤差為1.373 5×10-12，最大誤差為1.366 0×10-6。模型結(jié)果與樣本的比較如圖6所示。

圖6 通信時(shí)間的模型與樣本點(diǎn)對(duì)比Fig.6 Communication time comparison between model and sample points

C(xs)=4.485 7×10-9xs-4.875 3×10-7

(9)

式中：C為通信時(shí)間；xs為面網(wǎng)格單元數(shù)量。

1.2.3 模型驗(yàn)證

采用阻力預(yù)測(cè)會(huì)議的標(biāo)模DPW2的網(wǎng)格[23]，該網(wǎng)格共有141塊，網(wǎng)格量約1千萬(wàn)，如圖7所示。在天河二號(hào)上，采用40個(gè)進(jìn)程計(jì)算100步，通過(guò)設(shè)置并行節(jié)點(diǎn)的使用保證計(jì)算節(jié)點(diǎn)與模型建立時(shí)的節(jié)點(diǎn)相同。使用計(jì)算模型式(2)、式(8)和式(9)分別計(jì)算各個(gè)進(jìn)程上的總時(shí)間、計(jì)算時(shí)間和通信時(shí)間，并和準(zhǔn)確時(shí)間對(duì)比。

圖7 DPW2網(wǎng)格塊Fig.7 Grid block of DPW2

相對(duì)誤差如表2所示。從平均誤差看，進(jìn)程計(jì)算時(shí)間的準(zhǔn)確率高于通信時(shí)間，但總體上兩者都保持在10%附近；從最小誤差、最大誤差和標(biāo)準(zhǔn)差能夠看到各個(gè)進(jìn)程的誤差分布情況，各個(gè)進(jìn)程計(jì)算時(shí)間和總時(shí)間誤差的最大、最小值相差不大，標(biāo)準(zhǔn)差也較小，所以整體分布比較均勻；通信時(shí)間誤差分布的最大、最小值相差較大，標(biāo)準(zhǔn)差也大，所以分布的差異性較大。計(jì)算時(shí)間和總時(shí)間相近的原因是通信時(shí)間的數(shù)值很小，對(duì)總時(shí)間的影響較?。煌ㄐ艜r(shí)間的差異推測(cè)和計(jì)算平臺(tái)的性能相關(guān)，應(yīng)與采樣時(shí)通信時(shí)間存在奇異點(diǎn)的原因一致，具體的誤差分布如圖8所示，較大誤差的進(jìn)程數(shù)較少，但存在誤差值很大的進(jìn)程，類似于奇異點(diǎn)?？傮w而言，建立的計(jì)算時(shí)間和通信時(shí)間計(jì)算模型是可信的，進(jìn)一步由兩個(gè)時(shí)間結(jié)合得到的進(jìn)程總時(shí)間模型也是可信的，可用于遺傳算法的目標(biāo)函數(shù)計(jì)算。

表2 單個(gè)進(jìn)程的模型計(jì)算結(jié)果與真實(shí)結(jié)果誤差對(duì)比

圖8 通信時(shí)間誤差分布Fig.8 Communication time error distribution

1.3 第1步優(yōu)化：貪婪算法

貪婪算法是求解結(jié)構(gòu)網(wǎng)格負(fù)載平衡問(wèn)題的常用算法，只給出該方法的思路，算法細(xì)節(jié)可參考文獻(xiàn)[16]。貪婪算法的基本思想是“優(yōu)先匹配優(yōu)值資源”，具體到結(jié)構(gòu)化網(wǎng)格的負(fù)載平衡就是選擇大網(wǎng)格塊匹配計(jì)算能力強(qiáng)的進(jìn)程。使用計(jì)算平臺(tái)各個(gè)進(jìn)程的計(jì)算能力相同，通常用總網(wǎng)格量與進(jìn)程數(shù)量的比值作為進(jìn)程計(jì)算能力的度量。至此，可給出貪婪算法的大致求解步驟：

1) 計(jì)算進(jìn)程的初始計(jì)算能力，即總網(wǎng)格量與進(jìn)程數(shù)量的比值。

2) 從未分配網(wǎng)格塊中選擇網(wǎng)格量最大的網(wǎng)格塊，從未分配進(jìn)程中選擇計(jì)算能力最優(yōu)的進(jìn)程，判定兩者是否匹配(網(wǎng)格量和計(jì)算能力數(shù)值上近似相等)。

3) 匹配則將網(wǎng)格塊分配給相應(yīng)進(jìn)程，并將該進(jìn)程的計(jì)算能力標(biāo)定為0。

4) 不匹配則分兩種情況處理：第1種，所選網(wǎng)絡(luò)塊網(wǎng)格量大于進(jìn)程計(jì)算能力，則對(duì)網(wǎng)格塊進(jìn)行分割，分出匹配該進(jìn)程計(jì)算能力的網(wǎng)格塊按步驟3)處理，剩余網(wǎng)格塊作為未分配網(wǎng)格塊；第2種，所選網(wǎng)格塊網(wǎng)格量小于進(jìn)程計(jì)算能力，則把網(wǎng)格塊分配給進(jìn)程，同時(shí)使用進(jìn)程的計(jì)算能力減去網(wǎng)格塊網(wǎng)格量的差作為進(jìn)程新的計(jì)算能力。

5) 判斷是否所有進(jìn)程的計(jì)算能力都為0,是則計(jì)算完成，否則轉(zhuǎn)步驟2)。

1.4 第2步優(yōu)化：遺傳算法

采用與文獻(xiàn)[15]中一致的遺傳算法，但在處理細(xì)節(jié)上略有不同。用于結(jié)構(gòu)網(wǎng)格負(fù)載平衡的遺傳算法處理的是將網(wǎng)格塊在各個(gè)進(jìn)程上分配的問(wèn)題，本質(zhì)上是一個(gè)組合優(yōu)化問(wèn)題。遺傳算法需要針對(duì)結(jié)構(gòu)網(wǎng)格分配的特點(diǎn)，解決編碼、交叉、變異和種群初始化的問(wèn)題。以10個(gè)網(wǎng)格塊分配到4個(gè)進(jìn)程上的問(wèn)題為例，對(duì)上述方法依次展開(kāi)介紹。

1.4.1 編 碼

采用兩段編碼。第1段是所有網(wǎng)格塊序號(hào)按某個(gè)順序的排列，第2段是分配到各個(gè)進(jìn)程的網(wǎng)格塊的總數(shù)。如圖9所示，其中第1個(gè)進(jìn)程分配1塊網(wǎng)格，網(wǎng)格編號(hào)為7；第2個(gè)進(jìn)程分配2塊網(wǎng)格，網(wǎng)格編號(hào)為8和1；第3個(gè)進(jìn)程分配5塊網(wǎng)格，網(wǎng)格編號(hào)為10、3、5、4和9；第4個(gè)進(jìn)程分配2塊網(wǎng)格，網(wǎng)格編號(hào)為2和6。采用這種兩段編碼方式需要滿足如下約束條件：第1段編碼中的網(wǎng)格序號(hào)不允許有重復(fù)；第2段編碼中的數(shù)字之和等于總的網(wǎng)格塊數(shù)，也即第1段編碼的長(zhǎng)度。

圖9 遺傳算法編碼示意圖Fig.9 Schematic diagram of genetic algorithm coding

1.4.2 交叉操作

交叉操作僅對(duì)第1段編碼操作，圖示不畫(huà)出第2段編碼。采用Goldberg[24]提出的部分匹配交叉方法，該方法能夠保證交叉后的編碼滿足不重復(fù)的約束條件。選擇兩個(gè)父代編碼如圖10所示，圖中三角形標(biāo)識(shí)的位置為隨機(jī)確定的兩個(gè)交叉位置5和7，交叉操作可分為3步進(jìn)行。

1) 交換兩個(gè)父代交叉位置之間的編碼，如圖11(a) 所示。根據(jù)交換的編碼確定映射關(guān)系，如圖11(b)所示。

2) 在子代1的剩余編碼中，保留不在父代1交叉位置之間的編碼，對(duì)子代2則保留不在父代2交叉位置之間的編碼，如圖11(c)所示。

3) 利用圖12的映射關(guān)系對(duì)剩余編碼進(jìn)行處理，如子代1第1個(gè)“*”可通過(guò)將父代相同位置的8換成3得到，由此得到最后的交叉結(jié)果，如圖11(d) 所示。

圖10 編碼交叉位置示意圖Fig.10 Schematic diagram of coding cross position

圖11 交叉操作Fig.11 Cross operation

在交叉操作中特別需要注意的是遞歸問(wèn)題，仍然以圖10為例，將交叉位置改為4和7，如圖12(a) 所示。按照上述3步操作得到圖12(b)所示結(jié)果，此時(shí)兩個(gè)子代都出現(xiàn)了重復(fù)編碼10(紅色部分)。這是因?yàn)樵谟媒徊嫖恢弥g的編碼建立的映射關(guān)系中存在遞歸關(guān)系10和5、10和2。

圖12 交叉操作遞歸問(wèn)題Fig.12 Recursion problem in cross operation

以圖12(a)中父代的第9個(gè)編碼2為例，將其通過(guò)映射換為10之后，需要檢查10是否在父代2的映射編碼之內(nèi)，如果有就再做一次映射，得到5，即是所求。綜上，對(duì)于遞歸問(wèn)題，需要做兩次或以上的映射，直至映射結(jié)果不存在遞歸關(guān)系。對(duì)圖12(a)按遞歸問(wèn)題處理得到的結(jié)果如圖12(c)所示，仍滿足編碼的約束條件。

1.4.3 變異操作

采用交換算子進(jìn)行變異操作，對(duì)兩段編碼分別進(jìn)行變異操作。以第1段編碼為例，假設(shè)父代編碼如圖13(a)所示，隨機(jī)選取的變異位置如圖13(a) 中三角形標(biāo)記所示。通過(guò)變異操作，可得子代如圖13(b)所示。第2段的變異操作與第1段相同，不再贅述。顯然，換位變異操作能夠保證編碼的第1段和第2段滿足約束條件。

圖13 變異操作Fig.13 Mutation operation

1.4.4 種群初始化

發(fā)展的遺傳算法作為二次優(yōu)化方法需要在第1步優(yōu)化的基礎(chǔ)上開(kāi)展優(yōu)化，同時(shí)還要考慮第2次優(yōu)化的設(shè)計(jì)空間，因此采用隨機(jī)初始化和第1步優(yōu)化結(jié)果混合的初始化種群。

對(duì)第1段和第2段編碼分別進(jìn)行隨機(jī)初始化。對(duì)于第1段編碼，對(duì)網(wǎng)格塊編號(hào)采用隨機(jī)不放回抽樣即可得到隨機(jī)編碼。對(duì)于第2段編碼，采用多次隨機(jī)拆分的思路：先將網(wǎng)格塊總數(shù)隨機(jī)拆分為兩個(gè)整數(shù)，選擇其中最大的再次拆分，此時(shí)共得到3個(gè)整數(shù)，再對(duì)其中最大數(shù)做隨機(jī)拆分，直到拆分得到的整數(shù)個(gè)數(shù)與負(fù)載平衡的進(jìn)程數(shù)相等。

隨機(jī)初始化能夠得到隨機(jī)種群，但無(wú)法利用第1步貪婪算法的優(yōu)化結(jié)果。將遺傳算法的初始種群分為兩部分，一部分使用隨機(jī)初始化種群，另一部分使用貪婪算法的結(jié)果。

2 算例驗(yàn)證

2.1 特殊結(jié)構(gòu)網(wǎng)格算例

專門(mén)設(shè)計(jì)特殊結(jié)構(gòu)網(wǎng)格算例以說(shuō)明貪婪算法的問(wèn)題以及兩步優(yōu)化的必要性。該算例初始網(wǎng)格由10塊網(wǎng)格組成，網(wǎng)格塊的編號(hào)如圖14所示。大塊網(wǎng)格的網(wǎng)格量為50.0萬(wàn)，小塊網(wǎng)格的網(wǎng)格量為12.5萬(wàn)。將上述網(wǎng)格分配到4個(gè)進(jìn)程上。

圖14 算例1的初始網(wǎng)格及編號(hào)Fig.14 Initial grid and number of Case 1

第1步優(yōu)化采用貪婪算法，得到的結(jié)果如圖15 所示，4種顏色分別代表分到4個(gè)進(jìn)程的網(wǎng)格塊?？芍?、2兩塊分配合理，第3～10塊分配僅考慮計(jì)算量平衡，未考慮通信時(shí)間平衡。由式(2)計(jì)算的目標(biāo)函數(shù)值為2.141 77 s。

圖15 算例1的第1步優(yōu)化結(jié)果(貪婪算法)Fig.15 1st step optimization result of Case 1 (greedy algorithm)

第2步優(yōu)化采用遺傳算法，種群選取100個(gè)，交叉概率0.6，變異概率0.1，初始化種群中貪婪算法優(yōu)化結(jié)果占比10%，優(yōu)化100代，所得結(jié)果如圖16所示?？芍?，優(yōu)化結(jié)果是最優(yōu)的，此時(shí)的目標(biāo)函數(shù)值為2.141 65 s。雖然計(jì)算時(shí)間縮短很小，但是對(duì)于網(wǎng)格量大、迭代步數(shù)多、計(jì)算狀態(tài)復(fù)雜等計(jì)算量巨大的情況效果更為明顯。

另一方面，貪婪算法對(duì)網(wǎng)格塊的排列敏感。如把圖15中的網(wǎng)格塊編號(hào)改為如圖17所示，則分配結(jié)果與圖16相同，也可以得到最優(yōu)結(jié)果。但劃分網(wǎng)格時(shí)很難兼顧網(wǎng)格塊的排列順序，且當(dāng)網(wǎng)格塊數(shù)量巨大時(shí)，人工排列網(wǎng)格塊順序幾乎難以實(shí)現(xiàn)。所以對(duì)于計(jì)算量巨大的問(wèn)題，第2步基于遺傳算法的優(yōu)化是必要的。

圖16 算例1的第2步優(yōu)化結(jié)果(遺傳算法)Fig.16 2nd step optimization result of Case 1 (genetic algorithm)

圖17 改變網(wǎng)格塊排列順序的初始網(wǎng)格Fig.17 Initial grid changing grid blocks order

2.2 DPW2算例

DPW2的網(wǎng)格與1.2.3節(jié)的網(wǎng)格相同，分配到12個(gè)進(jìn)程上，網(wǎng)格如圖7所示。第1步優(yōu)化采用貪婪算法，得到的目標(biāo)函數(shù)值為3.598 49 s。第2步優(yōu)化采用遺傳算法，種群選取2 000個(gè)，交叉概率0.6，變異概率0.1，初始化種群中貪婪算法優(yōu)化結(jié)果占比10%，優(yōu)化200代。優(yōu)化結(jié)果為3.596 0 s。

第1步和第2步優(yōu)化結(jié)果的網(wǎng)格塊分配變化體現(xiàn)在第8、11和12個(gè)進(jìn)程上，具體的變化如表3 所示，3個(gè)進(jìn)程上分配的網(wǎng)格塊進(jìn)行了交叉調(diào)整，如表3中“*”標(biāo)示的網(wǎng)格塊編號(hào)。調(diào)整后各個(gè)進(jìn)程的計(jì)算時(shí)間如表4所示，計(jì)算時(shí)間最長(zhǎng)的進(jìn)程由進(jìn)程8變?yōu)檫M(jìn)程2，發(fā)生變化的主要原因來(lái)自進(jìn)程8計(jì)算時(shí)間的縮短。

表3 DPW2網(wǎng)格第1步和第2步優(yōu)化結(jié)果的網(wǎng)格塊分配對(duì)比

表4 DPW2網(wǎng)格第1步和第2步優(yōu)化結(jié)果的時(shí)間對(duì)比

DPW2的結(jié)果說(shuō)明即使經(jīng)過(guò)貪婪算法的優(yōu)化，網(wǎng)格塊的分配也不能保證計(jì)算時(shí)間指標(biāo)達(dá)到最優(yōu)，而遺傳算法能夠?qū)Φ?步優(yōu)化結(jié)果進(jìn)行有效改善。

2.3 DPW6算例

為進(jìn)一步檢驗(yàn)本文方法對(duì)大規(guī)模網(wǎng)格的處理能力，采用網(wǎng)格量接近1億的DPW6網(wǎng)格。該網(wǎng)格包含203個(gè)網(wǎng)格塊，共有近1億的網(wǎng)格單元，分配到60個(gè)進(jìn)程上，網(wǎng)格如圖18所示。第1步優(yōu)化采用貪婪算法，得到的目標(biāo)函數(shù)值為6.817 21 s。第2步優(yōu)化采用遺傳算法，種群選取8 000個(gè)，交叉概率0.6，變異概率0.1，初始化種群中貪婪算法優(yōu)化結(jié)果占比10%，優(yōu)化200代。優(yōu)化結(jié)果為6.817 3 s。

圖18 DPW6網(wǎng)格塊Fig.18 Grid block of DPW6

第1步和第2步優(yōu)化結(jié)果的網(wǎng)格塊分配變化體現(xiàn)在第30、33、36、37和42個(gè)進(jìn)程上，具體的變化如表5所示，5個(gè)進(jìn)程上分配的網(wǎng)格塊進(jìn)行了交叉調(diào)整，如表5中“*”標(biāo)示的網(wǎng)格編號(hào)所示。調(diào)整后各個(gè)進(jìn)程的計(jì)算時(shí)間如表6所示，計(jì)算時(shí)間最長(zhǎng)的進(jìn)程由進(jìn)程36變?yōu)檫M(jìn)程46，發(fā)生變化的主要原因來(lái)自進(jìn)程36計(jì)算時(shí)間和通信時(shí)間的縮短。

表5 DPW6網(wǎng)格第1步和第2步優(yōu)化結(jié)果的網(wǎng)格塊分配對(duì)比

表6 DPW6網(wǎng)格第1步和第2步優(yōu)化結(jié)果的時(shí)間對(duì)比

分析DPW6算例的結(jié)果，編碼長(zhǎng)度的增加極大地提高了尋優(yōu)難度，即使種群增加到8 000個(gè)，目標(biāo)函數(shù)才獲得0.000 1 s的收益，這是遺傳算法尋優(yōu)的不利之處，也是之后需要重點(diǎn)研究的方向之一。

3 結(jié) 論

1) 設(shè)計(jì)的進(jìn)程計(jì)算時(shí)間和通信時(shí)間的建模方法具有一定的通用性，可以擴(kuò)展到相關(guān)負(fù)載平衡問(wèn)題的研究上；建立的進(jìn)程計(jì)算時(shí)間模型和通信時(shí)間模型都具有較高的精度，滿足遺傳算法優(yōu)化設(shè)計(jì)的需要；通信時(shí)間受計(jì)算平臺(tái)的擾動(dòng)較大，所以計(jì)算精度略低于網(wǎng)格計(jì)算時(shí)間的模型。

2) 提出的兩步優(yōu)化策略能夠有效求解負(fù)載平衡問(wèn)題。第1步優(yōu)化采用貪婪算法，能夠完成大網(wǎng)格塊的剖分和以計(jì)算時(shí)間為依據(jù)的網(wǎng)格塊分配；第2步優(yōu)化采用遺傳算法，在第1步優(yōu)化基礎(chǔ)上，以建立的計(jì)算時(shí)間和通信時(shí)間計(jì)算模型計(jì)算目標(biāo)函數(shù)開(kāi)展二次優(yōu)化，能夠得到更優(yōu)的分配結(jié)果。

3) 第2步優(yōu)化結(jié)果顯示，單進(jìn)程單步的時(shí)間收益是較小的。對(duì)于計(jì)算量巨大的問(wèn)題，如網(wǎng)格量巨大、迭代步數(shù)冗長(zhǎng)和計(jì)算狀態(tài)很多的問(wèn)題，整體上能夠獲得較大的時(shí)間收益；對(duì)于計(jì)算量較小的問(wèn)題，可不開(kāi)展第2步優(yōu)化。

4) 本文屬于探索性研究，要提升本文兩步優(yōu)化策略的工程實(shí)用能力，還可從以下問(wèn)題尋求突破：網(wǎng)格塊數(shù)和進(jìn)程數(shù)增多造成編碼長(zhǎng)度的增加，從而導(dǎo)致設(shè)計(jì)空間急劇增大，最終造成遺傳算法尋優(yōu)困難的問(wèn)題；組合優(yōu)化遺傳算法交叉和變異操作的改進(jìn)問(wèn)題；非組合優(yōu)化遺傳算法的改進(jìn)措施在組合優(yōu)化遺傳算法上的適用性研究。