TSP的結(jié)構(gòu)特征挖掘與啟發(fā)式算法設(shè)計.pdf

1、旅行商問題TSP(traveling salesman problem)是經(jīng)典的NP-難解組合優(yōu)化問題之一，在交通、網(wǎng)絡(luò)、電路設(shè)計等方面有著廣泛的應用背景。根據(jù)計算復雜性理論可知：對于NP-難解問題，除非P=NP，否則不存在多項式時間內(nèi)得到最優(yōu)解的精確算法。因此對于大規(guī)模的實例，求解它的高效啟發(fā)式算法設(shè)計一直是計算機科學研究的熱點。骨架、脂肪等作為描述TSP結(jié)構(gòu)特征的工具，對啟發(fā)式算法設(shè)計有著重要的意義，已經(jīng)成為目前研究TSP問題的主要

2、研究領(lǐng)域。 本文首先對TSP問題的研究現(xiàn)狀進行了介紹和分析，指出在TSP結(jié)構(gòu)特征工具的研究上的不足之處。通過構(gòu)造偏移實例的技巧，分析了TSP問題的脂肪計算復雜性，并首次給出了獲取TSP的脂肪是NP-難解的理論證明，即在P≠NP的假設(shè)下，不存在算法可以在多項式時間內(nèi)獲得完整脂肪。在此基礎(chǔ)上，通過分析TSP問題局部最優(yōu)解與脂肪的關(guān)系，給出了求解TSP問題新的元啟發(fā)式算法——動態(tài)候選集搜索算法。利用該算法，本文改進了目前求解TSP問題

3、最好的算法之一的LKH。 然后，本文在分析局部最優(yōu)解與全局最優(yōu)解關(guān)系的基礎(chǔ)上，提出一種新的描述TSP結(jié)構(gòu)特征工具——擾邊。通過假設(shè)可以構(gòu)造多項式時間內(nèi)的算法求得擾邊，進而引出可以在多項式時間內(nèi)求的TSP問題的最優(yōu)解，用反證法給出了求解擾邊是NP-難的理論證明。通過試驗分析，發(fā)現(xiàn)通過對局部最優(yōu)解之間的相互操作，可以求得有效模擬擾邊的“近似擾邊”。并在此基礎(chǔ)上，提出了基于近似擾邊的元啟發(fā)式算法框架MAFBOAD(Meta-Heuri