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

何文靜

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

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

何文靜

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

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

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

1 引言

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

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

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

2 問題分析

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

3 優化目標

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

4 設計方案

4.1 適應度評估

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

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

4.2 交叉算子

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

4.3 變異算子

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

4.4 優化輔助策略

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

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

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

4.5 并行分布式計算方案

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

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

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

5 算法流程

PVM-IMGA算法的執行流程如下：

（1）參數設置：包括并行分布式環境的建立，數據塊劃分數目，計算節點上種群的規模，算法迭代停止條件等等。

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

（3）計算節點環境初始化：計算節點根據從主機發送來的參數信息，初始化進化種群。

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

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

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

6 實驗測試

Keane’s Bump 函數

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

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

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

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

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

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

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

[1] Kai Hwang.云計算與分布式系統:從并行處理到物聯網[M].北京:機械工業出版社,2013.

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

[3] 黃春.改進遺傳算法的函數優化及應用[D].南寧:廣西大學, 2015.

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

[5] 林志毅,王玲玲.求解高維函數優化問題的混合蜂群算法[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－），女，廣西大學計算機與電子信息學院碩士生，研究方向為并行分布式計算和優化算法。