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

在審

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

1.一種基于Spark的并行化遺傳算法，其特征在于，包括如下步驟：

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

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

2.根據權利要求1所述的一種基于Spark的并行化遺傳算法，其特征在于，步驟(1)具體包括如下子步驟：

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

(1.2)通過Spark的mapPartitions(assessFitness())函數將種群RDD轉換為適應度值RDD，該RDD包含鍵值對<key,value>，其中key是一個個體，value是該個體的適應度值，函數assessFitness()用于計算個體的適應度值，它被分布到集群中不同的節點上并行計算；

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

3.根據權利要求1所述的一種基于Spark的并行化遺傳算法，其特征在于，步驟(2)具體包括如下子步驟：

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

(2.2)通過Spark的mapPartitions(evolution())函數將種群RDD中的各個子種群分布到Spark集群的不同的工作節點上，并轉換為進化RDD，函數evolution()用于執行遺傳操作，被分布到集群中不同的節點上并行進化，所述遺傳操作包括選擇、交叉和變異；

(2.3)通過Spark的map(getBest())函數將進化RDD轉換為最優個體RDD，該RDD包含鍵值對<key,value>，其中key是一個鍵值對<individual,fitness>，value是發現解決方案時的進化代數；函數getBest()用于獲得每個子種群中的最好個體，被分布到集群中不同的節點上并行執行；

(2.4)Spark的collect函數觸發Spark的運算流程，將步驟(2.3)中每個子種群中的最好個體都收回到主節點上，找出其中最好的一個，作為最優結果輸出。

4.根據權利要求3所述的一種基于Spark的并行化遺傳算法，其特征在于，步驟(2.2)中所述遺傳操作具體為：選擇操作采用適應度值比例法；交叉操作采用多點隨機交叉；變異操作采用多點隨機變異。