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

何文靜

（廣西大學計算機與電子信息學院，廣西 南寧 530004）

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

何文靜

（廣西大學計算機與電子信息學院，廣西 南寧 530004）

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

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

1 引言

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

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

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

2 問題分析

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

3 優(yōu)化目標

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

4 設計方案

4.1 適應度評估

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

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

4.2 交叉算子

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

4.3 變異算子

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

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

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

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

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

4.5 并行分布式計算方案

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

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

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

5 算法流程

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

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

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

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

（4）基因的交叉重組、變異：每一個計算節(jié)點獨立完成各自的搜索任務。當算法達到迭代停止條件時，將搜索到的有用信息傳回Master主機。

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

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

6 實驗測試

Keane’s Bump 函數(shù)

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

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

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

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

表1 50維條件下的測試對比

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

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

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

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

[3] 黃春.改進遺傳算法的函數(shù)優(yōu)化及應用[D].南寧:廣西大學, 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].計算機科學,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－），女，廣西大學計算機與電子信息學院碩士生，研究方向為并行分布式計算和優(yōu)化算法。