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

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

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

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