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

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

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

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