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

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

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

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

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