旅行商問題的兩種算法.pdf

1、旅行商(TSP)問題是組合優(yōu)化中最典型的NP-Hard問題之一，并且應(yīng)用廣泛，如電路版印刷設(shè)計(jì)、交通調(diào)度等。目前關(guān)于該問題的啟發(fā)式算法主要分為兩類：環(huán)路構(gòu)造算法和環(huán)路改進(jìn)算法。 隨著現(xiàn)代科技的發(fā)展，旅行商問題的研究規(guī)模與難度越來越大，單一的算法已經(jīng)不能很好地解決問題。本文在參考大量關(guān)于啟發(fā)式算法論文的基礎(chǔ)上，給出了二種有效地改善啟發(fā)式算法解質(zhì)量的算法，并闡述了它們的基本思想以及操作步驟，并用程序?qū)崿F(xiàn)，最后指出了兩個(gè)算法的優(yōu)缺點(diǎn)和

2、今后的研究方向。 算法1 是在研究最近鄰算法、貪心算法、蟻群算法的基礎(chǔ)上，分析環(huán)路構(gòu)造算法優(yōu)缺點(diǎn)和適用用范圍。針對(duì)環(huán)路改造算法針容易陷入局部最優(yōu)等缺陷，提出了先優(yōu)化距陣再進(jìn)行計(jì)算的思路，可在提高解質(zhì)量的同時(shí)降低各類環(huán)路構(gòu)造算法的時(shí)間復(fù)雜度。 利用該思路設(shè)計(jì)的驗(yàn)證算法，可徹解20個(gè)城市以內(nèi)的旅行商問題，驗(yàn)證算法雖然增加了歸零的矩陣等處理步驟，但計(jì)算用時(shí)更短，極大提高了程序效率。測(cè)試結(jié)果證明，歸零矩陣可以有效改善原始矩陣數(shù)據(jù)

3、的排序關(guān)系，使得最優(yōu)解的矩陣數(shù)值變小，有效改善矩陣陷阱，歸零矩陣啟發(fā)集規(guī)模得以減少。 算法2 是在討論環(huán)路改進(jìn)算法中局部搜索、LK、LKH 等算法的基礎(chǔ)上，分析局部最優(yōu)解與全局最優(yōu)解之間關(guān)系，對(duì)局部最優(yōu)解進(jìn)行了分類。設(shè)計(jì)一種可加入更多種局部最優(yōu)類型的算法：二點(diǎn)組合算法。對(duì)該算法程序進(jìn)行了多角度測(cè)試，結(jié)果表明這個(gè)算法解決中小規(guī)模的旅行商問題是實(shí)用的。 本文從新的視角重新分析啟發(fā)式算法的基本原理和數(shù)學(xué)基礎(chǔ)，通過分析、研究環(huán)路