[發(fā)明專利]一種基于Spark的并行化遺傳算法

在審

• 申請?zhí)枺?/td>: 201711338226.2
• 申請日: 2017-12-14
• 公開（公告）號: CN108197708A
• 公開（公告）日: 2018-06-22
• 發(fā)明（設(shè)計）人: 戚榮志;李水艷;曾濤;安紀存
• 申請（專利權(quán)）人: 河海大學(xué)
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06N3/00
• 代理公司: 南京蘇高專利商標事務(wù)所(普通合伙) 32204
• 代理人: 柏尚春

本發(fā)明公開了一種基于Spark的并行化遺傳算法，包括適應(yīng)度值計算并行化和遺傳操作并行化，從初始種群創(chuàng)建Spark的RDD，將RDD劃分為多個分區(qū)分布到集群的多個節(jié)點中，每個分區(qū)對應(yīng)一個子種群，各個子種群在各自的節(jié)點上進行適應(yīng)度值的計算，并將計算結(jié)果收回到Spark的主節(jié)點上；將帶有適應(yīng)度值的種群劃分為多個子種群，并作為RDD的多個分區(qū)再次分布到集群的多個節(jié)點中，各個子種群在各自的節(jié)點上進行獨立進化，在進化滿足終止條件時收集RDD不同分區(qū)中的最好的個體，將結(jié)果返回到Spark的主節(jié)點上。本發(fā)明利用Spark的基于內(nèi)存的計算模型，從適應(yīng)度值計算和遺傳操作兩方面將遺傳算法并行化，提高了遺傳算法的性能。

技術(shù)領(lǐng)域

本發(fā)明涉及一種并行化遺傳算法，尤其是一種基于Spark的并行化遺傳算法。

背景技術(shù)

遺傳算法是一種模擬自然界生物進化過程與機制的元啟發(fā)式搜索技術(shù)，被廣泛應(yīng)用于求解復(fù)雜的優(yōu)化問題。通常，窮盡搜索完整的輸入空間是不可行的，遺傳算法可以用來通過搜索較小的輸入空間，在合理的時間里求出好的問題解。傳統(tǒng)遺傳算法通過順序執(zhí)行選擇、交叉、變異等遺傳操作，尋找問題的最優(yōu)解。傳統(tǒng)遺傳算法用于求解復(fù)雜的優(yōu)化問題時，通常需要較長的計算時間。

為了解決遺傳算法帶來的計算性能問題，本發(fā)明提供一種基于Spark的并行化遺傳算法。Spark是一種快速、通用的并行計算框架，它的核心是一種彈性分布式數(shù)據(jù)集RDD。Spark通過對RDD進行并行切片，然后分發(fā)到集群中的多個節(jié)點上完成相應(yīng)的變換操作，最后由行動操作觸發(fā)所有的運算。Spark的這種運算方式非常適合并行化遺傳算法的實現(xiàn)。

發(fā)明內(nèi)容

發(fā)明目的：針對上述現(xiàn)有技術(shù)存在的缺陷，本發(fā)明旨在提供一種基于Spark的并行化遺傳算法。

技術(shù)方案：一種基于Spark的并行化遺傳算法，包括如下步驟：

(1)適應(yīng)度值計算并行化：隨機生成初始種群，從初始種群創(chuàng)建Spark的RDD，并將RDD劃分為多個分區(qū)分布到集群的多個節(jié)點中，每個分區(qū)對應(yīng)一個子種群，各個子種群在各自的節(jié)點上進行適應(yīng)度值的計算，并將計算結(jié)果收回到Spark的主節(jié)點上；

(2)遺傳操作并行化：將帶有適應(yīng)度值的種群劃分為多個子種群，并作為RDD的多個分區(qū)再次分布到集群的多個節(jié)點中，各個子種群在各自的節(jié)點上進行獨立進化，在進化滿足終止條件時收集RDD不同分區(qū)中的最好的個體，并將結(jié)果返回到Spark的主節(jié)點上。

進一步的，步驟(1)具體包括如下子步驟：

(1.1)隨機生成初始種群，隨機生成的初始種群通過Spark的parallelize函數(shù)轉(zhuǎn)換為種群RDD，并將種群RDD劃分為多個分區(qū)分布到集群的多個節(jié)點中，RDD包含的分區(qū)的數(shù)量，以及每個分區(qū)包含的個體的數(shù)量，由Spark自動分配；

(1.2)通過Spark的mapPartitions(assessFitness())函數(shù)將種群RDD轉(zhuǎn)換為適應(yīng)度值RDD，該RDD包含鍵值對<key,value>，其中key是一個個體，

value是該個體的適應(yīng)度值，函數(shù)assessFitness()用于計算個體的適應(yīng)度值，它被分布到集群中不同的節(jié)點上并行計算；

(1.3)Spark的collect函數(shù)觸發(fā)Spark的運算流程，完成步驟(1.2)中的所述轉(zhuǎn)換，并將這些鍵值對收回到主節(jié)點上。

進一步的，步驟(2)具體包括如下子步驟：

(2.1)將帶有適應(yīng)度值的種群再次通過Spark的parallelize函數(shù)變換為種群RDD；