[發明專利]基于個體?種群的智能優化算法在Spark上的通用并行化方法

在審

• 申請號: 201711072393.7
• 申請日: 2017-11-03
• 公開（公告）號: CN107766927A
• 公開（公告）日: 2018-03-06
• 發明（設計）人: 邢煥來;周芯宇;楊慧;李可;葉佳
• 申請（專利權）人: 西南交通大學
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 成都盈信專利代理事務所(普通合伙)51245
• 代理人: 崔建中

技術領域

本發明涉及分布式計算技術領域，特別是一種基于個體-種群的智能優化算法在Spark上的通用并行化方法。

背景技術

有一類智能優化算法是通過模仿自然界的生物行為或模擬物理現象而來，該類算法能在可接收的開銷下(包括時間和空間)給出待解決問題的一個較好質量的可行解。該類智能優化算法也稱為元啟發式算法，比較常用的有遺傳算法、粒子群算法、蟻群算法、人工蜂群算法等。相比于傳統的優化算法，該類算法理論上不是很完善，不能確保找到問題的最優解，但該類算法適應性廣，尋解開銷能控制在可接受的范圍內，大量應用在實際的工程領域中。該類智能優化算法有一個顯著且共通的特點，均有個體和種群的概念。種群是個體的集合，而個體代表了問題的一個解，通過個體的一些行為或是個體之間的相互協作，促使整個種群往更好的方向發展、演化，從而尋找到問題的更優解。

隨著問題的復雜度增大、規模增長，在單機環境下利用該類智能優化算法求解問題的運行耗時也會隨之增長。為了提高該類算法的執行效率，減少運行時間，滿足實際的應用需要，可以對算法本身進行改造以提高性能，但不同的算法其改造方式不同，即使是同一算法針對不同的問題也有各種各樣的變種，難度較大。另一種方法就是對算法進行并行化處理，使原本運行在單機上的算法分布到不同的計算機上同時運行，減少運行時間，提升效率。

隨著云計算、大數據的蓬勃發展，各種各樣的分布式計算框架被提出，Spark平臺就是其中之一，為并行化奠定了底層基礎。

發明內容

本發明的目的是提供一種基于個體-種群的智能優化算法在Spark上的通用并行化方法。

實現本發明目的的技術方案如下：

基于個體-種群的智能優化算法在Spark上的通用并行化方法，包括步驟：

(1)封裝個體的抽象基類BaseIndividual，封裝種群的抽象基類BasePopulation，封裝種群之間用于個體交換的中間數據格式類ExchangeData；

(2)設定所述智能優化算法的個體的實現類SomeIndividual，設定所述智能優化算法的種群的實現類SomePopulation；所述SomeIndividual繼承自BaseIndividual，SomePopulation繼承自BasePopulation；

(3)初始化M個種群，M≥2；初始化每個種群中N個個體，N≥100；初始化全局最優個體gbest，初始化最大迭代次數MAX_T，設當前迭代次數t＝1；

(4)初始化環境上下文SparkContext，調用SparkContext.broadcast()接口生成常量信息的廣播量，廣播到Spark平臺上的所有計算節點內；

(5)調用SparkContext.parallelize()接口將M個種群對象并行化，生成對應的種群分布式數據集PopulationRDD；

(6)調用PopulationRDD.map()接口執行并行計算；所述PopulationRDD.map()接口中，每個種群依次經過獨自進化、種群適應度評估后返回該種群中適應度最優的前K個個體，其中K≥2；

(7)調用PopulationRDD.collect()接口，收集每個種群返回的K個個體，從中找出當代最優個體cbest；若cbest的適應度優于gbest，則用cbest更新gbest；

(8)對每個種群返回的K個個體進行封裝，生成M個用于個體交換的中間數據，再對M個中間數據進行打亂混排，然后調用SparkContext.parallelize()接口對其進行并行化，生成對應的個體中間交換數據分布式數據集ExchangeRDD；

(9)調用PopulationRDD.zipPartitions()接口并傳入ExchangeRDD，進行種群之間的個體交換；

(10)t＝t+1，若t<MAX_T，轉到步驟(6)，否則退出循環，輸出gbest。

本發明的有益效果在于，針對基于個體-種群的智能優化算法，在Spark平臺上提出了一種通用型的并行化方法，使原本運行在單機上的算法分布到不同的計算機上同時運行，以減少運行時間，提升效率。

附圖說明

圖1是本發明的流程圖；

圖2是本發明具體實施例中的BaseIndividual類圖；

圖3是本發明具體實施例中的BasePopulation類圖；

圖4是本發明具體實施例中的ExchangeData類圖；