基于Spark平臺的混沌蟻群優(yōu)化算法研究與實現(xiàn).pdf

1、分類號TP301學(xué)校代碼10129UDC004學(xué)號2013210003基于Spark平臺的混沌蟻群優(yōu)化算法研究與實現(xiàn)ResearchImplementationofChaoticAntColonyOptimizationBasedonSparkPlatfm申請人：謝鵬飛學(xué)生類別：學(xué)術(shù)型碩士學(xué)科門類：工學(xué)學(xué)科專業(yè)：計算機應(yīng)用技術(shù)研究方向：智能計算與數(shù)據(jù)挖掘指導(dǎo)教師：付學(xué)良教授論文提交日期：二〇一六年六月摘要組合優(yōu)化問題是指從組合問題的可行

2、解中求出最優(yōu)解，但是目前利用傳統(tǒng)方式解決組合優(yōu)化問題需要極大的存儲空間和極長的運行時間，而在當今大數(shù)據(jù)時代，各行業(yè)每年產(chǎn)生的數(shù)據(jù)量都呈指數(shù)增長，Spark作為一種新型的并行計算模型應(yīng)運而生，因此利用Spark并行計算模型解決“組合爆炸”問題是一種很可行的方案。在解決組合優(yōu)化問題時，人們傾向于選擇元啟發(fā)式算法，例如蟻群算法就是受螞蟻覓食行為的啟發(fā)而提出的一種元啟發(fā)式算法，它具有魯棒性、分布式運行、易于和其它算法相融合等優(yōu)點。目前該算法已經(jīng)

3、廣泛應(yīng)用于組合優(yōu)化領(lǐng)域，并且取得了較好的成果，但它也存在易陷入局部最優(yōu)解和收斂速度慢等問題。論文根據(jù)蟻群構(gòu)建可行解過程的內(nèi)在并行性及云計算平臺分布式計算的特點，提出一種基于Spark的混沌蟻群優(yōu)化算法，進而展開了以下幾方面的研究：1針對基本蟻群算法在處理大規(guī)模旅行商問題時易陷入局部最優(yōu)解及收斂速度慢等問題，論文提出當螞蟻選擇路徑時采用輪盤賭策略從候選城市中隨機選擇下一個城市，從而擴大蟻群搜索空間；然后引用混沌理論動態(tài)地調(diào)整信息素揮發(fā)系數(shù)

4、，避免算法陷入局部最優(yōu)解；再使用遺傳變異算子對每一次迭代的路徑結(jié)果進行變異操作，以期望得到路徑最優(yōu)解；最后將改進的蟻群算法使用MapReduce并行計算模型編程實現(xiàn)，并將其部署在Hadoop平臺中運行，以大幅提高蟻群算法的運行速度。2論文在對Spark平臺充分研究的基礎(chǔ)上，又將改進的蟻群算法使用Spark并行計算模型編程實現(xiàn)。首先把蟻群封裝為彈性分布式數(shù)據(jù)集RDD，并將其初始化為大小規(guī)模均等的多個小種群；再使用Spark提供的廣播機制在

5、集群節(jié)點中共享信息素矩陣，并充分利用Spark基于內(nèi)存計算的特點實現(xiàn)蟻群并行地構(gòu)建可行解，從而更快地處理大規(guī)模組合優(yōu)化問題。3通過實驗證明：對于特定規(guī)模大小的蟻群，增加集群節(jié)點數(shù)量并不能持續(xù)地提升蟻群算法的運行速度；論文選用TSPLIB庫中不同的旅行商實例驗證改進蟻群算法的性能。結(jié)果表明：隨著蟻群規(guī)模的增大，基于MapReduce的混沌蟻群優(yōu)化算法比基本蟻群算法的運行時間大幅縮短，而基于Spark的混沌蟻群優(yōu)化算法比前兩者算法的運行速度