何文靜

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004）

并行分布式遺傳算法的研究

何文靜

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004）

傳統(tǒng)遺傳算法在面對(duì)一些搜索空間巨大的復(fù)雜問題時(shí)，其表現(xiàn)往往難以令人滿意。作者針對(duì)傳統(tǒng)遺傳算法解決高維多峰值問題時(shí)可能會(huì)出現(xiàn)的困難進(jìn)行了分析，然后根據(jù)困難出現(xiàn)的原因，基于 PVM 設(shè)計(jì)了并行分布式遺傳算法，并對(duì)適應(yīng)度評(píng)估、交叉、變異算子做了一些改進(jìn)，旨在加強(qiáng)算法的全局搜索能力，提高算法的收斂速度。為了驗(yàn)證算法多項(xiàng)措施的有效性，對(duì)一多峰函數(shù)在高維條件下進(jìn)行多方面的測(cè)試，實(shí)驗(yàn)結(jié)果表明這幾項(xiàng)措施是有效的。

并行；分布式；多峰；遺傳算法

1 引言

并行計(jì)算理論的研究始于20世紀(jì)70年代，經(jīng)過40多年的發(fā)展，其技術(shù)日趨成熟。在生活中有大量的實(shí)際應(yīng)用，比如天氣預(yù)報(bào)、地震數(shù)據(jù)處理、飛行器數(shù)值模擬等等，這些領(lǐng)域的事務(wù)處理往往需要幾十萬億甚至幾百萬億次的浮點(diǎn)運(yùn)算，并行計(jì)算[1]是適合這類事務(wù)處理的一種技術(shù)。近年來云計(jì)算的興起，使得分布式計(jì)算技術(shù)也逐漸趨于成熟，并得到了廣泛的應(yīng)用，它把網(wǎng)絡(luò)上分散于各處的計(jì)算機(jī)資源匯聚起來完成各種大規(guī)模的計(jì)算和數(shù)據(jù)處理任務(wù)。

遺傳算法(genetic algorithm,GA)基于達(dá)爾文自然選擇定律以及孟德爾遺傳理論，它模擬自然生物遺傳和選擇的過程將適應(yīng)度相對(duì)高的個(gè)體保留，適應(yīng)度相對(duì)低的個(gè)體逐漸淘汰，循環(huán)重復(fù)這一過程，直到滿足停止條件，因此它是一種迭代搜索算法。遺傳算法的全局搜索比較容易實(shí)現(xiàn)與加強(qiáng)，目前在許多領(lǐng)域有廣泛的應(yīng)用，比如建筑的結(jié)構(gòu)性優(yōu)化、化工領(lǐng)域的資源分配、計(jì)算機(jī)自動(dòng)控制等等。但在高維、超高維多模態(tài)問題中，傳統(tǒng)遺傳算法仍會(huì)表現(xiàn)出一些不足，全局搜索能力不足，易限于局部極優(yōu)，收斂速度以及精度有待提高。

文章針對(duì)傳統(tǒng)遺傳算法用于高維、超高維多模態(tài)問題時(shí)存在的不足，提出了基于PVM的并行分布式遺傳算法(PVMIMGA)。PVM-IMGA算法基于PVM平臺(tái)，采用了一種比較好的適應(yīng)度評(píng)估方法，并對(duì)交叉算子、變異算子做了一些改進(jìn)，使其具有自適應(yīng)加速特性。為了驗(yàn)證改進(jìn)工作的有效性，文章最后對(duì)一高維多峰值函數(shù)進(jìn)行了實(shí)驗(yàn)測(cè)試，實(shí)驗(yàn)結(jié)果表明 PVM-IMGA算法克服了傳統(tǒng)遺傳算法易限于局部極優(yōu)的問題，全局搜索能力、收斂能力都有了比較明顯的提高。

2 問題分析

高維、超高維問題的一個(gè)特點(diǎn)是其搜索空間巨大，要在巨大的范圍內(nèi)搜索到合適精度的目標(biāo)可行解，耗時(shí)往往較長(zhǎng)，有時(shí)甚至無法找到。多個(gè)極值是多峰值問題的特點(diǎn)，多峰值問題較一般的單一峰值問題，尋優(yōu)難度要更大，算法易陷于局部極值，對(duì)遺傳算法的全局搜索能力會(huì)有更高的要求。

3 優(yōu)化目標(biāo)

在多峰值問題中，一般是尋找單類型的所有極值，即在有限定義域、可接受的時(shí)間范圍內(nèi)要么尋找所有極大值，要么是極小值。本文實(shí)驗(yàn)測(cè)試所用的多峰函數(shù)尋找的是極小值。

4 設(shè)計(jì)方案

4.1 適應(yīng)度評(píng)估

多峰值問題中，各極值點(diǎn)的函數(shù)值往往大小不一。在傳統(tǒng)遺傳算法中，適應(yīng)度的評(píng)估與位置點(diǎn)對(duì)應(yīng)的函數(shù)值通常有比較大的關(guān)系，如果是尋找極大值，那么函數(shù)值大的，適應(yīng)度值可能就比較大，而函數(shù)值小的，適應(yīng)度值相對(duì)就小。這類評(píng)估方法有一定的局限性，比如當(dāng)尋優(yōu)目標(biāo)是尋找極小值時(shí)，有些位置點(diǎn)的函數(shù)值較另一位置點(diǎn)的要大，但是它距離所在局部區(qū)域的極小值點(diǎn)卻可能更近，因此以函數(shù)值作為參考標(biāo)準(zhǔn)的適應(yīng)度評(píng)估方案顯然不合適。文獻(xiàn)[2]提出了一種基于梯度算子與聚類算子的適應(yīng)度評(píng)估方法，這種適應(yīng)度評(píng)估方法能夠有效區(qū)分峰、谷、坡以及平原，但是它的峰、谷、坡以及平原位置點(diǎn)之間適應(yīng)度值差距較大，坡點(diǎn)與谷、峰之間的接近程度難以體現(xiàn)，同時(shí)不利于本文的交叉變異策略，因此對(duì)它做一些改進(jìn)：

由于是高維問題，因此采用浮點(diǎn)數(shù)編碼。 表示的是位置點(diǎn)的偏導(dǎo)數(shù)，有而是用于放大臨近極值點(diǎn)位置間差異的因子，那么的值介于0與1之間，由計(jì)算式我們知道，越是臨近極值點(diǎn)，那么偏導(dǎo)數(shù)的值越是接近于0，則有反之如果是平原位置，那么的值為0，其余位置均是2，而峰、谷對(duì)應(yīng)的適應(yīng)度值是3，坡位置點(diǎn)的適應(yīng)度介于2與3之間，平原位置點(diǎn)的適應(yīng)度是 1。所以主要用于識(shí)別位置點(diǎn)是否處在平原。則表示m維目標(biāo)問題的總適應(yīng)度值。

4.2 交叉算子

在遺傳算法中，交叉率體現(xiàn)著個(gè)體間、個(gè)體內(nèi)基因交叉重組的幾率?；虻慕徊嬷亟M是算法實(shí)現(xiàn)全局搜索的重要方式，因此交叉算子的設(shè)計(jì)非常重要。文獻(xiàn)[3]中提出了一種比較好的自適應(yīng)的交叉算子，能夠保證種群穩(wěn)步提升，但它的選擇保留策略需要不少的計(jì)算量，對(duì)于串行單機(jī)執(zhí)行的遺傳算法來講，算法的搜索效率會(huì)受到一定影響。本文汲取它的一些思想并做了一些改進(jìn)：個(gè)體間執(zhí)行基因重組的時(shí)候，如果父親的某個(gè)基因位點(diǎn)相比母親的對(duì)應(yīng)基因位點(diǎn)的值差異方向與該位置的偏導(dǎo)數(shù)符號(hào)相一致的話，那么該基因位點(diǎn)可以執(zhí)行交叉重組。比如父親的某個(gè)基因位置點(diǎn)的偏導(dǎo)數(shù)為正，而母親的基因值相比父親的要大，那么可以執(zhí)行，反之不執(zhí)行。執(zhí)行該段基因的交叉重組之后，如果個(gè)體得到改良，則替換相應(yīng)父母，繼續(xù)對(duì)下一段基因做相同嘗試。如果沒有得到改進(jìn)，采用兩種策略：一種是還原該基因段，還原之后對(duì)下一段基因做相同嘗試；另一種是保留這次的基因重組，繼續(xù)對(duì)下一段基因做類似嘗試，當(dāng)父母?jìng)€(gè)體全部完成基因的重組之后，得到的子代個(gè)體如果比父母要好，則做相應(yīng)替換，否則不替換。這兩種策略在種群進(jìn)化過程中交替執(zhí)行。

4.3 變異算子

遺傳算法中，變異運(yùn)算一般用于產(chǎn)生與父母性狀差異小的個(gè)體，是算法執(zhí)行局部搜索的主要方式。文獻(xiàn)[3]提出的自適應(yīng)變異算子同樣存在計(jì)算量較多的問題，它的保留策略由于是更優(yōu)則保留，否則還原，算法可能會(huì)無法進(jìn)入某些區(qū)域進(jìn)行搜索。為了適應(yīng)PVM-IMGA算法的適應(yīng)度評(píng)估方法，對(duì)變異算子進(jìn)行如下設(shè)計(jì)：

4.4 優(yōu)化輔助策略

在遺傳算法中，初始種群的特征也是影響算法搜索效率的一個(gè)因素。在多峰值問題中，許多極值點(diǎn)往往是分布在不同的空間區(qū)域，所以一般來講，應(yīng)該讓初始種群中的個(gè)體盡量分散，這樣更有利于算法將個(gè)體收斂到它附近的極值。

種群規(guī)模過大或者過小，都不利于算法的執(zhí)行。當(dāng)算法將個(gè)體收斂到指定精度后，我們可以遷徙該個(gè)體，并將一些距離該個(gè)體一定歐氏距離之外個(gè)體補(bǔ)充到進(jìn)化的種群中，保持種群的多樣性，避免算法陷于局部極優(yōu)區(qū)域。

如果目標(biāo)問題具有約束處理?xiàng)l件，那么問題的尋優(yōu)難度會(huì)增大。文獻(xiàn)[3]中提出了一種比較好的約束處理方法，為了更好的利用偽可行解的進(jìn)化信息，PVM-IMGA算法也采用類似的約束處理策略。

4.5 并行分布式計(jì)算方案

PVM-IMGA算法基于消息傳遞類并行軟件開發(fā)環(huán)境PVM[4],采用的是Master-Slave模式（MPMD），這種模式的程序是由運(yùn)行于一臺(tái)PVM主機(jī)上的Master PVM程序和運(yùn)行于若干計(jì)算節(jié)點(diǎn)的Slave PVM程序組成的。Master主機(jī)負(fù)責(zé)計(jì)算任務(wù)的管理調(diào)度以及數(shù)據(jù)收集分配，Slave計(jì)算節(jié)點(diǎn)負(fù)責(zé)算法的計(jì)算搜索任務(wù)。

網(wǎng)絡(luò)上的數(shù)據(jù)通信開銷是比較大的，因此應(yīng)盡量減少網(wǎng)絡(luò)通信，縮短算法運(yùn)行時(shí)間。為了做到這一點(diǎn)，堅(jiān)持本地化數(shù)據(jù)處理，即從主機(jī)下發(fā)給計(jì)算節(jié)點(diǎn)Slave的是搜索空間的范圍，計(jì)算節(jié)點(diǎn)再根據(jù)規(guī)則本地化生成個(gè)體對(duì)象，每個(gè)計(jì)算節(jié)點(diǎn)完成搜索任務(wù)后，反饋回主機(jī)的也是決策變量的值，主機(jī)再根據(jù)決策變量得出相關(guān)信息。

PVM-IMGA算法的一個(gè)完整的執(zhí)行過程是這樣的：Master主機(jī)將待處理的大數(shù)據(jù)劃分為很多數(shù)據(jù)塊，在算法中，我們按照一定規(guī)則劃分決策變量的范圍，使搜索空間成為細(xì)塊。主機(jī)將一個(gè)個(gè)的數(shù)據(jù)塊下發(fā)到網(wǎng)絡(luò)上的可用計(jì)算節(jié)點(diǎn)，然后等待節(jié)點(diǎn)返回搜索結(jié)果，收集完成后繼續(xù)分配未處理的數(shù)據(jù)塊，直到所有數(shù)據(jù)塊完成分配和搜索計(jì)算，匯總所有的計(jì)算結(jié)果作為最終結(jié)果。

5 算法流程

PVM-IMGA算法的執(zhí)行流程如下：

（1）參數(shù)設(shè)置：包括并行分布式環(huán)境的建立，數(shù)據(jù)塊劃分?jǐn)?shù)目，計(jì)算節(jié)點(diǎn)上種群的規(guī)模，算法迭代停止條件等等。

（2）任務(wù)分配：Master主機(jī)給Slave計(jì)算節(jié)點(diǎn)下發(fā)搜索空間數(shù)據(jù)以及其他信息，比如算法迭代次數(shù)、小生境半徑等等。

（3）計(jì)算節(jié)點(diǎn)環(huán)境初始化：計(jì)算節(jié)點(diǎn)根據(jù)從主機(jī)發(fā)送來的參數(shù)信息，初始化進(jìn)化種群。

（4）基因的交叉重組、變異：每一個(gè)計(jì)算節(jié)點(diǎn)獨(dú)立完成各自的搜索任務(wù)。當(dāng)算法達(dá)到迭代停止條件時(shí)，將搜索到的有用信息傳回Master主機(jī)。

（5）數(shù)據(jù)的收集以及任務(wù)再分配：Master主機(jī)負(fù)責(zé)從計(jì)算節(jié)點(diǎn)收集信息，如果仍有數(shù)據(jù)搜索任務(wù)未分配，則將任務(wù)下發(fā)給該可用計(jì)算節(jié)點(diǎn)，然后等待其他節(jié)點(diǎn)的數(shù)據(jù)。

（6）判斷：如果主機(jī)之上仍有未分配的搜索任務(wù)或者計(jì)算節(jié)點(diǎn)上有未傳回的信息，那么重復(fù)第 5步驟，否則停止整個(gè)算法的運(yùn)行，匯總所有搜索到的有用信息。

6 實(shí)驗(yàn)測(cè)試

Keane’s Bump 函數(shù)

這是一個(gè)國際上廣泛用于測(cè)試算法穩(wěn)定性、收斂性能的多峰值函數(shù)，在超高維的條件下，它具有超非線性、超多峰的特征，函數(shù)維度越高，搜索難度越大。

圖1 Keane’s Bump 函數(shù)的最小值與維度的關(guān)系

圖2 不同維度下PVM-IMGA與IMGA的平均搜索時(shí)間

為了檢驗(yàn)論文提出的并行分布計(jì)算方式的有效性，筆者將論文改進(jìn)后的遺傳算法分別在 PVM并行環(huán)境以及單機(jī)環(huán)境對(duì)Keane’s Bump 函數(shù)進(jìn)行實(shí)驗(yàn)測(cè)試20次，然后求它們的平均時(shí)間。兩種算法的實(shí)驗(yàn)條件相同，例如相同的種群規(guī)模、迭代次數(shù)等等。圖2是在不同維度下，使用PVM-IMGA算法以及單機(jī)環(huán)境下的IMGA算法的平均搜索時(shí)間變化趨勢(shì)圖。從圖我們可以看到，在較低維度的條件下，單機(jī)環(huán)境下的IMGA算法的搜索時(shí)間要比并行環(huán)境下的PVM-IMGA算法的執(zhí)行時(shí)間要短，但是當(dāng)維度逐漸增高之后，它們的搜索時(shí)間的差距有了一些變化，當(dāng)維度高到一定程度時(shí)，PVM-IMGA算法的執(zhí)行效率要比單機(jī)環(huán)境的IMGA算法要高。另外，當(dāng)維度達(dá)到一定高度后，IMGA算法無法在指定的迭代次數(shù)內(nèi)找到所有極值，當(dāng)增加種群規(guī)模以及迭代次數(shù)時(shí)，其搜索結(jié)果會(huì)有一點(diǎn)變化，但是仍然是無法達(dá)到多峰值問題的尋優(yōu)要求。之所以出現(xiàn)這樣的結(jié)果，究其原因，當(dāng)維度比較低，問題的搜索空間不是很大時(shí)，IMGA具有較好的求解能力，可以比較快速的找到可行解，PVM-IMGA算法雖然也具有求解能力，但是因?yàn)榫W(wǎng)絡(luò)傳輸需要比較長(zhǎng)的時(shí)間，所以PVM-IMGA算法的耗時(shí)比IMGA算法要長(zhǎng)。但是當(dāng)維度較高，搜索空間比較巨大時(shí)，IMGA算法的局限性就暴露出來了。而PVM-IMGA算法因?yàn)槟軐⑺阉骺臻g分塊細(xì)化，并交由不同的計(jì)算節(jié)點(diǎn)來執(zhí)行，執(zhí)行效率開始變得更高。當(dāng)問題維度增大到一定程度時(shí)，筆者可以通過調(diào)整數(shù)據(jù)塊大小以及增加計(jì)算節(jié)點(diǎn)來提高算法的搜索效率。

表1 50維條件下的測(cè)試對(duì)比

為進(jìn)一步驗(yàn)證PVM-IMGA算法的穩(wěn)定性以及收斂能力，筆者對(duì)算法能收斂到的最小極值進(jìn)行統(tǒng)計(jì)，并與文獻(xiàn)[5]的DE、ABC、HABC算法，文獻(xiàn)[3]的IMBF-GA算法進(jìn)行比較。從表1的 4項(xiàng)實(shí)驗(yàn)數(shù)據(jù)可見，在收斂能力和穩(wěn)定性方面，PVM-IMGA算法皆優(yōu)于DE、ABC、HABC、IMBF-GA算法,說明PVM-IMGA算法在高維條件下，對(duì)多峰函數(shù)具有較好的收斂能力，文章針對(duì)多模態(tài)問題，對(duì)傳統(tǒng)遺傳算法進(jìn)行的多項(xiàng)修改是有效的。

文獻(xiàn)[3]中提到IMBF-GA算法在一定維度下，搜索到所有極值的概率是比較高的，但是當(dāng)維度增加時(shí)，成功率會(huì)下降。對(duì)于本文的 PVM-IMGA算法，如果去除并行分布式計(jì)算形式，僅使用單機(jī)運(yùn)行，其運(yùn)行效果與IMBF-GA算法大致類似，增大種群規(guī)模以及迭代搜索次數(shù)盡管能在一定程度上提高成功率，但是當(dāng)函數(shù)維度達(dá)到一定程度后，算法執(zhí)行效率、收斂效果仍然難以讓人滿意。并行分布式計(jì)算方式是解決超大規(guī)模計(jì)算的有效手段，這也是當(dāng)今云計(jì)算與分布式系統(tǒng)流行的一個(gè)重要原因。

[1] Kai Hwang.云計(jì)算與分布式系統(tǒng):從并行處理到物聯(lián)網(wǎng)[M].北京:機(jī)械工業(yè)出版社,2013.

[2] 劉洪杰,王秀峰.峰搜索的自適應(yīng)遺傳算法[J].控制理論與應(yīng)用,2004,4(21): 303-310.

[3] 黃春.改進(jìn)遺傳算法的函數(shù)優(yōu)化及應(yīng)用[D].南寧:廣西大學(xué), 2015.

[4] Adam.Parallel Virtual Machine:A Users' Guide and Tutorial for Networked Parallel Computing[M].The MIT Press,1994.

[5] 林志毅,王玲玲.求解高維函數(shù)優(yōu)化問題的混合蜂群算法[J].計(jì)算機(jī)科學(xué),2013,3(40): 279-281.

The research of parallel and distributed genetic algorithm

In the face of complex problems with a large number of search spaces, traditional genetic algorithm’s performance is often difficult to satisfactory. The author analyzes those possible difficulties for solving high-dimensional multimodal problems by traditional genetic algorithm. Then according to the cause that difficulties occur, we design parallel and distributed genetic algorithm based on PVM, and make some improvements to the evaluation method of fitness, the crossover and mutation operator. These improvements aim at strengthening the global search ability and improving the rate of convergence of the algorithm. In order to verify the measures’ effectiveness of the algorithm, we take a test to a multi-modal functions in many aspects under the condition of high dimension. The experimental results show that the several measures are effective.

Parallel; distributed; multi-modal; GA

TP302

A

1008-1151(2016)07-0013-03

2016-06-11

何文靜（1987－），女，廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院碩士生，研究方向?yàn)椴⑿蟹植际接?jì)算和優(yōu)化算法。