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

余濤　劉澤檠

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

關(guān)鍵詞：Spark；RDD；并行遺傳算法；多目標優(yōu)化；大規(guī)模變量

中圖分類號：TP18

文獻標志碼：A

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

0.引言

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

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

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

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

2.基于Spark的并行遺傳算法設(shè)計及實現(xiàn)

2.1SPGA算法流程

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

2.2SPGA算法優(yōu)化設(shè)計

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

3.實驗與結(jié)果分析

3.1實驗環(huán)境和測試函數(shù)

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

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

3.2.2算法運行時間對比

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

4.結(jié)束語

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