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

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

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

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

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