本文關鍵詞：一種基于MapReduce模型的并行化TSP算法研究

  更多相關文章： TSP MapReduce模型 并行化 廣義Beta分布

【摘要】：TSP問題(Traveling Salesman Problem),即旅行商問題,是數(shù)學領域里面組合優(yōu)化問題中被廣泛研究的著名問題之一。TSP問題在學術研究和實際生產需求中十分重要,同時在物理學、生物學和計算機科學等領域有著廣泛的應用。TSP問題是NP-完全問題中很有挑戰(zhàn)性的一個問題。目前對于TSP問題的研究多是在單一物理機上使用順序執(zhí)行的啟發(fā)式算法求得近似解,也有少量研究初步在Hadoop平臺上基于MapReduce模型實現(xiàn)了一些諸如遺傳算法和蟻群算法等新型啟發(fā)式算法,但都仍然存在不能保證算法的質量、運行不穩(wěn)定等問題。本論文探索通過并行MapReduce模型高效解決TSP問題。根據(jù)以上存在的問題,本文提出基于MapReduce模型的并行化迭代K-OPT算法:首先,本文提出一種基于MapReduce模型并行化求解最小生成樹算法,并用于構造TSP初始化路徑;該算法充分應用MapReduce模型中可以很容易對數(shù)據(jù)進行排序的特點對圖中的所有邊的權重進行排序,結合并行化的克魯斯卡爾算法求得最小生成樹;再將其作為Christofides算法輸入求得一條可以用于迭代求解TSP問題算法的初始化路徑,其中Christofides算法是目前TSP問題中最好的近似算法之一,其近似比為1.5-opt。其次,以初始路徑為基礎,提出一種基于MapReduce模型并行化的KOPT算法,算法利用MapReduce模型可以充分并行化運算的特點,將map函數(shù)用于路徑的分發(fā)和圖的讀取,reduce函數(shù)用于問題的求解,從集群中多節(jié)點求得的不同迭代解中篩選出最優(yōu)解,將其作為下一次迭代的輸入。然后,通過對節(jié)點數(shù)規(guī)模較小的完全圖進行基于MapReduce模型所有路徑的窮舉和對一些TSPLIB中的實例進行基于MapReduce模型的大規(guī)模隨機路徑生成以及并行化去冗余操作,然后進行一定的統(tǒng)計和特征分析,本文首次提出了截斷廣義Beta分布Truncated Generalized Beta distribution(TGB)作為TSP問題中最優(yōu)路徑的概率密度函數(shù),并以此證明了迭代KOPT算法的近似比,在不斷增加迭代次數(shù)的情況下,可獲得接近優(yōu)化的結果。最后,通過大量實例測試驗證了本文所提算法的性能。
【關鍵詞】：TSP MapReduce模型 并行化 廣義Beta分布
【學位授予單位】：電子科技大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：TP338.6
【目錄】：

• 摘要5-6
• ABSTRACT6-10
• 第一章 緒論10-15
• 1.1 背景及意義10-11
• 1.1.1 TSP問題背景10
• 1.1.2 研究TSP問題的意義10-11
• 1.2 研究現(xiàn)狀11-12
• 1.2.1 TSP問題的發(fā)展階段11-12
• 1.2.2 TSP問題的已有的研究成果12
• 1.3 研究內容12-13
• 1.4 組織結構13-14
• 1.5 本章小結14-15
• 第二章 TSP問題及MapReduce模型介紹15-24
• 2.1 TSP問題定義15-16
• 2.1.1 TSP問題的描述15
• 2.1.2 TSP問題的數(shù)學模型15-16
• 2.2 TSP問題已有解決方法概述16-21
• 2.2.1 TSP問題精確解決算法16-17
• 2.2.2 TSP問題近似算法17-21
• 2.3 Hadoop平臺及MapReduce模型簡介21-23
• 2.3.1 Hadoop平臺介紹21-22
• 2.3.2 MapReduce模型簡介22-23
• 2.4 本章小節(jié)23-24
• 第三章 基于MapReduce模型求解MST算法24-32
• 3.1 最小生成樹MST定義及基本算法24-26
• 3.1.1 最小生成樹MST定義24
• 3.1.2 求解MST基本算法24-26
• 3.2 基于MapReduce模型的MST算法26-31
• 3.2.1 算法概述26
• 3.2.2 算法設計及流程圖26-27
• 3.2.3 算法核心代碼及時間復雜度分析27-31
• 3.3 初始環(huán)路生成31
• 3.3.1 Christofides算法概述及初始環(huán)路的生成31
• 3.4 本章小結31-32
• 第四章 基于MapReduce模型實現(xiàn)K-OPT算法32-38
• 4.1 K-OPT算法及基本應用32-33
• 4.1.1 K-OPT算法概述32
• 4.1.2 K-OPT算法在LKH算法中的應用32-33
• 4.2 基于MapReduce模型實現(xiàn)K-OPT算法33-37
• 4.2.1 算法概述33
• 4.2.2 算法設計及流程圖33-35
• 4.2.3 算法核心代碼及時間復雜度分析35-37
• 4.3 本章小結37-38
• 第五章 TSP優(yōu)化路徑和模型統(tǒng)計分析38-59
• 5.1 完全圖的TSP隨機路徑38-42
• 5.1.1 完全圖的TSP隨機路徑算法概述38-41
• 5.1.2 基于MapReduce模型生成完全圖的TSP隨機路徑41-42
• 5.2 窮舉完全圖的所有TSP路徑42-46
• 5.3 TSP路徑模型的統(tǒng)計分析46-58
• 5.3.1 廣義Beta分布作為隨機TSP問題的概率密度函數(shù)48-49
• 5.3.2 TSPLIB實例服從廣義Beta分布的概率密度函數(shù)49-50
• 5.3.3 基于Christofides算法的截取廣義Beta概率分布（Truncated GeneralizedBeta Distribution）50-58
• 5.4 本章小結58-59
• 第六章 算法性能評估與測試59-73
• 6.1 實驗環(huán)境及配置59
• 6.1.1 實驗硬件環(huán)境59
• 6.1.2 實驗軟件環(huán)境59
• 6.2 實驗結果展示及分析59-72
• 6.2.1 基于MapReduce模型生成最小生成樹算法測試及分析60-64
• 6.2.2 基于MapReduce模型K-OPT算法測試及分析64-67
• 6.2.3 TSP優(yōu)化路徑特征的統(tǒng)計分析測試及分析67-72
• 6.3 本章小結72-73
• 第七章 總結與展望73-75
• 7.1 本文總結73-74
• 7.2 存在的問題與不足74
• 7.3 未來工作展望74-75
• 致謝75-76
• 參考文獻76-78
• 攻讀碩士期間取得的研究成果78-79

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前2條

1 夏衛(wèi)雷;王立松;;基于MapReduce的并行蟻群算法研究與實現(xiàn)[J];電子科技;2013年02期

2 張煜東;吳樂南;韋耿;;智能算法求解TSP問題的比較[J];計算機工程與應用;2009年11期

，

本文編號：665797