基于SPark的并行遺傳算法研究

余濤　劉澤檠

摘要：當前Spark分布式編程框架由于內存計算得到了快速發展，相對于傳統MapReduce并行編程模型在迭代運算上有明顯優勢。針對串行遺傳算法處理大規模問題能力有限的現狀，提出了一種基于Spark平臺的粗粒度并行遺傳算法（sPGA）。該方法利用Spark框架并行實現了遺傳算法的選擇、交叉和變異操作，并對并行操作算子的性能進行了分析，優化了算法并行化實現方案，極大地提高了遺傳算法全局搜索效率。實驗結果表明，新的并行遺傳算法在收斂速度上有顯著的提高，能夠很好地提高優化效率。

關鍵詞：Spark；RDD；并行遺傳算法；多目標優化；大規模變量

中圖分類號：TP18

文獻標志碼：A

文章編號：1006-8228（2017）01-43-03

0.引言

遺傳算法是一種模擬生物進化的隨機學習方法，主要包括選擇、交叉和變異三種遺傳操作。面對大規模復雜優化問題時，遺傳算法的尋優時間長，所以有人提出了并行遺傳算法，主要將遺傳算法的天然并行性跟并行編程模型相結合，加快搜索優化過程。

近年來，機器學習領域的眾多專家做了許多加快并行遺傳算法尋優速度的研究和探索。郭肇祿在并行遺傳算法中提出了自適應遷移策略，降低了通信開銷。李建明等人實現了一種基于GPU的細粒度并行遺傳算法，抑制了種群的早熟，提高了搜索效率。Verma A等人則從數據處理規模的角度實現了MapReduce跟遺傳算法的結合。這些基于GPU或者MapReduce實現的并行遺傳算法，雖然取得了一定的進展，但是GPU可擴展能力欠佳，MapReduce的迭代速度較慢，這些缺陷都制約了并行遺傳算法對大規模復雜優化問題的快速求解。近期快速發展的Spark并行計算引擎能夠提供內存計算機制，被普遍認為是下一代大數據并行處理框架，但是基于Spark計算模型實現并行遺傳算法需要嘗試不同的Spark算子和參數來對比分析其性能。

本文深入分析了遺傳算法和Spark并行編程模型，實現了一種適合Spark框架的粗粒度并行遺傳算法。具體的工作有：①對Spark的部分算子和參數通過大量實驗進行對比分析，優化了算法性能。②結合遺傳算法跟Spark計算平臺實現了一種高性能的并行遺傳算法。實驗表明該算法能夠提高收斂效率，適合處理大規模的優化問題。

Spark是一個集流計算、數據查詢、機器學習和圖挖掘于一體的通用計算框架，具有可伸縮、內存計算和高可靠性等優點。彈性分布式數據集（RDD）是Spark的數據存儲的核心，在迭代計算時可以高效的共享數據，目標是為基于工作集的應用提供抽象。本質上RDD是一個元數據結構，提供了一種高度受限的內存模型，記錄著只讀的、分區記錄的集合，存儲著數據分區及其邏輯結構映射關系；在Spark編程模型中RDD被表示為對象，相應的API為RDD提供轉換（Transformations）和動作（Actions）兩種算子，其中Transformations算子執行后創建新的RDD，從而RDD之問形成相互依賴關系，如圖1所示。RDD的依賴分為窄依賴和寬依賴，其中窄依賴是子RDD的分區只依賴父RDD的某個分區，而寬依賴則指子RDD的每個分區依賴父RDD的多個分區；Action算子則真正觸發程序的執行，向應用程序返回結果或者向存儲系統導出數據。

2.基于Spark的并行遺傳算法設計及實現

2.1SPGA算法流程

本文將標準遺傳算法的并行性和RDD編程模型相結合，實現了一種粗粒度的并行遺傳算法。算法整體流程如圖2所示。首先是初始化種群，然后具體實現相應的并行遺傳算子，這里只是在Spark上并行實現了遺傳算子，并沒有做任何實質改進，所以從這個角度來看SPGA算法相對標準遺傳算法在求解精度上是沒有任何優勢的，但是SPGA算法會將整個種群劃分為若干個亞種群，而后在集群所擁有的處理器上獨立進行計算，這可以縮短運行時間，發揮并行算法速度優勢。遷移策略是并行遺傳算法跟串行遺傳算法的重要不同之處，這里在亞種群之間采用隨機遷移策略，能夠解決遺傳算法的局部最優問題。

2.2SPGA算法優化設計

mapPartitions和map是RDD上的兩個并行操作算子，mapPartitions的功能是作用一個函數到RDD的每一個分片（partition）上，map則是對RDD的每個元素應用一個函數，兩者運算后都返回一個新的RDD。由于遺傳算法的適應度計算及變異過程是一種粗粒度操作，種群中的個體單獨計算互不干擾，所以很容易想到使用map算子。然而在考慮性能時我們發現，map算子需要為所有的個體都初始化一個測試函數，在大規模種群時產生了大量不必要的內存和計算開銷。為了避免這種冗余開銷，我們考慮使用mapPartitions算子代替map算子，因為mapPartitios算子是以RDD的partition作為處理函數的輸入，也就是把partition作為整體來處理，只需要在每個partition開始計算時初始化一個測試函數，節省了很多內存和計算資源，提高了算法的整體運算效率。

3.實驗與結果分析

3.1實驗環境和測試函數

本實驗使用7臺Dell服務器構建了—個Spark集群，分為1個主控節點和6個受控節點，集群的任務調度模式為standalone。硬件配置：服務器擁有8G內存，四核處理器。軟件配置：集群搭建使用spark-1.2.0-bin-hadoopl和Hadoop-1.2.1穩定版，Java選用JDKl.7.0_71（Linux版），操作系統選擇ubuntul2.04Server版。

首先初始化8個不同大小的種群，然后在相同條件下使用mapPartitions和map算子實現的SPGA算法在初始種群上優化求解ZDTl函數的Pareto最優前沿，并對運行時間進行對比分析。圖3評價了mapPartitions和map算子實現的SPGA算法性能，從中可以看出由mapPartitions算子編寫的算法對所有種群的運行時間都明顯優低于map算子，且隨著種群規模的增大，mapPartitions和map算子的運行時間都在增加，同時兩者的時間差距也越來越大，這是因為個體數目增多的同時partition的數目沒有變，所以mapPartitions算子沒有增加初始化資源的時間，只是因為種群變大增加了計算時間，實現的算法效率更高。由于mapPartitions算子的性能優異，所以最終選擇使用mapPartitions算子實現SPGA算法的變異和適應度。

3.2.2算法運行時間對比

本次實驗對比了串行遺傳算法、基于MapReduce的并行遺傳算法（MRPGA）和基于Spark的并行遺傳算法在不同種群規模下求解ZDTl多目標優化問題的運行時問。從圖4可以看出，在種群規模較小，個體數量小于o.2*10時，串行遺傳算法執行時間最短，其次是SPGA算法，運行時間最長的是MRPGA算法，這是因為Spark集群和MapReduce建立作業以及系統通信需要消耗一定的時問，而且MapReduce作業的初始化耗時大于Spark作業。當種群規模增大到中等規模時我們發現，SPGA算法用時最少，串行次之，MRPGA還是用時最多，在這個階段串行遺傳算法的運行時間上升最快并且超過了SPGA算法，這是因為相對于串行算法而言，并行算法會將增加的數據分散到各個節點并行計算，能夠大量節省了計算時間，同時MRPGA算法由于作業啟動和磁盤I/O耗時太多所以整體運行速度還是最。隨著種群增長達到大規模，其數量大于9*10⁵時，集群上并行程序的優勢就明顯大于串行程序，SPGA和MRPGA算法的耗時都小于串行遺傳算法，而且SPGA算法優于MRPGA算法，這是因為Spark框架是基于內存運算，不需要大量讀寫磁盤，所以SPGA算法運行更快。

4.結束語

在spark上實現了粗粒度并行遺傳算法，其收斂速度有很大優勢，但是由于該算法并沒有對標準遺傳算子進行改進，所以在求解精度上沒有明顯進步。在以后的工作中，我們將在spark平臺上重點改進標準遺傳算法的算子結構以提高求解精度；對spark的參數調優以及如何利用基于spark的并行遺傳算法解決實際問題也是我們未來研究的重點。