基于中心定位的蟻群算法及其在交通選路中的應(yīng)用.pdf

1、需求工程——對復(fù)雜系統(tǒng)的軟件工程的基礎(chǔ)研究是科技部于2007年批準(zhǔn)的國家重點基礎(chǔ)研究項目(即973項目)。該項目選取城市交通領(lǐng)域的問題作為問題研究的載體，而城市交通選路問題又是其中一個重要研究內(nèi)容。應(yīng)用蟻群算法解決該問題是本文研究的主要內(nèi)容。 蟻群算法是一種新生算法，從產(chǎn)生伊始就用于解決旅行商(TSP)問題。該算法具有結(jié)構(gòu)簡單、易于實現(xiàn)、正反饋性和本質(zhì)的并行性等優(yōu)點。本文將基本蟻群算法加以改進(jìn)，有效發(fā)揮了蟻群算法的特性，為交通選

2、路問題的解決提供了一種方案。 本文首先介紹了課題的研究背景和意義，闡述了城市交通選路問題的研究現(xiàn)狀，詳細(xì)介紹了基本蟻群算法，并在此基礎(chǔ)上提出了一種改進(jìn)算法：基于中心定位的蟻群算法，并在相同的實驗環(huán)境下分別用兩種算法進(jìn)行仿真實驗，結(jié)果驗證了改進(jìn)算法尋找最優(yōu)解的速度明顯比原基本算法快，且更接近于理論上的最優(yōu)值，最后將基于中心定位的蟻群算法應(yīng)用于交通選路問題中。具體內(nèi)容如下： (1)介紹了基本蟻群算法的基本原理，以旅行商問題為

3、背景建立數(shù)學(xué)模型，總結(jié)了算法的具體步驟，從時間復(fù)雜度和空間復(fù)雜度兩方面分析了算法的復(fù)雜度，論證了算法的收斂性。 (2)在基本蟻群算法的基礎(chǔ)上對其進(jìn)行改進(jìn)，提出基于中心定位的蟻群算法，以旅行商問題為背景建立了新的數(shù)學(xué)模型，同樣總結(jié)了改進(jìn)算法的具體實現(xiàn)步驟，分析了改進(jìn)算法的復(fù)雜度，并論證了其收斂性。 (3)利用TSPLIB網(wǎng)站上公布的TSP數(shù)據(jù)，對基本蟻群算法和基于中心定位的蟻群算法在相同的實驗條件下進(jìn)行仿真實驗，并對實驗結(jié)