基于復雜網(wǎng)絡(luò)的旅行商問題的智能求解算法研究.pdf

1、TSP(TravelingSalesmanProblem)問題是組合優(yōu)化領(lǐng)域中典型問題之一,包含了組合優(yōu)化問題的大部分特征。在許多領(lǐng)域都有廣泛的應(yīng)用,如工業(yè)、農(nóng)業(yè)、國防、建筑、商業(yè),交通運輸業(yè)等。因此,對于TSP問題的有效解決必將帶動社會多個行業(yè)的發(fā)展,具有廣泛的實用價值。另外,它經(jīng)常被用來評價各種啟發(fā)式優(yōu)化算法的優(yōu)劣。因此,研究TSP問題也具有重要的理論價值。
　　隨著計算機的發(fā)展,研究者對TSP問題的求解提出了很多智能算法。其

2、中比較經(jīng)典的有遺傳算法、蟻群算法、粒子群算法等,這些算法基本上都是根據(jù)生物界的一些規(guī)律演化而來的。與傳統(tǒng)算法不同的是:本文考慮將復雜網(wǎng)絡(luò)的思想引入到組合優(yōu)化問題中,利用復雜網(wǎng)絡(luò)的一些特征思想來求解TSP問題。
　　復雜網(wǎng)絡(luò)是現(xiàn)在科學研究中的一個新興的熱點話題。復雜網(wǎng)絡(luò)與現(xiàn)實社會有著很多密不可分的聯(lián)系,在現(xiàn)實社會中存在著許多復雜網(wǎng)絡(luò)模型,例如:社會關(guān)系網(wǎng),物種捕食關(guān)系網(wǎng),通信網(wǎng)等。如何通過對復雜網(wǎng)絡(luò)模型的研究,將其應(yīng)用到其他的領(lǐng)域來

3、解決社會中的一些現(xiàn)實問題,是科學家和研究學者非常關(guān)心的一個問題。大量學者的研究發(fā)現(xiàn),大多數(shù)復雜網(wǎng)絡(luò)都具有一些相同的特性,如較短的網(wǎng)絡(luò)平均路徑、較大的網(wǎng)絡(luò)聚類系數(shù)、節(jié)點度的冪率分布等。網(wǎng)絡(luò)模型結(jié)構(gòu)和特性的研究對處理現(xiàn)實網(wǎng)絡(luò)中存在的問題具有一定的指導作用。
　　本文重點討論了如何在復雜網(wǎng)絡(luò)知識背景下解決TSP問題。首先,本文介紹了TSP問題的基本思想。其次,分析了求解TSP問題的傳統(tǒng)智能算法的具體求解思路,給出了遺傳算法、蟻群算法和粒

4、子群算法的具體算法描述,并對這幾種算法分別進行了仿真實驗,對實驗結(jié)果進行了合理的分析。再次,詳細的闡述了復雜網(wǎng)絡(luò)及其建模的概念,給出了復雜網(wǎng)絡(luò)的主要統(tǒng)計特征,主要包括度分布、聚類系數(shù)和平均路徑長度。文中還給出了小世界網(wǎng)絡(luò)和無標度網(wǎng)絡(luò)的詳細建模算法,并對WS(WattsStrogatz)、NW(NewmanWatts)和BA(BarabsiAlbert)三種網(wǎng)絡(luò)模型分別進行了仿真實驗。最后,設(shè)計了利用復雜網(wǎng)絡(luò)思想求解TSP問題的具體算法,