一種基于MapReduce模型的并行化TSP算法研究.pdf

1、TSP問題（Traveling Salesman Problem），即旅行商問題，是數(shù)學領域里面組合優(yōu)化問題中被廣泛研究的著名問題之一。TSP問題在學術研究和實際生產需求中十分重要，同時在物理學、生物學和計算機科學等領域有著廣泛的應用。TSP問題是NP-完全問題中很有挑戰(zhàn)性的一個問題。目前對于TSP問題的研究多是在單一物理機上使用順序執(zhí)行的啟發(fā)式算法求得近似解，也有少量研究初步在Hadoop平臺上基于MapReduce模型實現(xiàn)了一些諸如

2、遺傳算法和蟻群算法等新型啟發(fā)式算法，但都仍然存在不能保證算法的質量、運行不穩(wěn)定等問題。本論文探索通過并行MapReduce模型高效解決TSP問題。
　　根據(jù)以上存在的問題，本文提出基于MapReduce模型的并行化迭代K-OPT算法：首先，本文提出一種基于MapReduce模型并行化求解最小生成樹算法，并用于構造TSP初始化路徑；該算法充分應用MapReduce模型中可以很容易對數(shù)據(jù)進行排序的特點對圖中的所有邊的權重進行排序，結合

3、并行化的克魯斯卡爾算法求得最小生成樹；再將其作為Christofides算法輸入求得一條可以用于迭代求解TSP問題算法的初始化路徑，其中Christofides算法是目前TSP問題中最好的近似算法之一，其近似比為1.5-opt。其次，以初始路徑為基礎，提出一種基于MapReduce模型并行化的K-OPT算法，算法利用MapReduce模型可以充分并行化運算的特點，將map函數(shù)用于路徑的分發(fā)和圖的讀取，reduce函數(shù)用于問題的求解，從集

4、群中多節(jié)點求得的不同迭代解中篩選出最優(yōu)解，將其作為下一次迭代的輸入。然后，通過對節(jié)點數(shù)規(guī)模較小的完全圖進行基于MapReduce模型所有路徑的窮舉和對一些TSPLIB中的實例進行基于MapReduce模型的大規(guī)模隨機路徑生成以及并行化去冗余操作，然后進行一定的統(tǒng)計和特征分析，本文首次提出了截斷廣義Beta分布Truncated Generalized Beta distribution(TGB)作為TSP問題中最優(yōu)路徑的概率密度函數(shù)，并