基于多頭絨泡菌的交通網(wǎng)絡(luò)設(shè)計(jì)算法的研究.pdf

1、交通網(wǎng)絡(luò)在人們的日常生活中發(fā)揮著重要的作用。近幾年，隨著城市的擴(kuò)張，越來(lái)越多的人涌入城市，城市內(nèi)部的交通需求越來(lái)越大。另外，隨著居民收入的升高，城市之間的社會(huì)活動(dòng)日漸頻繁。隨著城市人口與私家車(chē)的迅速增加，城市交通遇到了前所未有的困難與挑戰(zhàn)。交通擁堵現(xiàn)象日益嚴(yán)重，不僅造成了資源的浪費(fèi)，同時(shí)對(duì)環(huán)境產(chǎn)生了嚴(yán)重的污染。在交通系統(tǒng)中，道路的設(shè)計(jì)、建設(shè)和使用，對(duì)用戶行為有著重要的影響。合理的交通系統(tǒng)能夠在一定程度上減輕道路擁堵現(xiàn)象。因此，如何設(shè)計(jì)高

2、效，費(fèi)用低，容錯(cuò)率高的網(wǎng)絡(luò)成為擺在我們面前的一個(gè)亟待解決的問(wèn)題。
　　根據(jù)最近的研究發(fā)現(xiàn)，一種名為多頭絨泡菌（Physarum polycephalum）的單細(xì)胞生物在網(wǎng)絡(luò)設(shè)計(jì)、分析與優(yōu)化方面展現(xiàn)出了驚人的智能特性。在生物實(shí)驗(yàn)中，它所設(shè)計(jì)出的連接各食物源的覓食管道網(wǎng)絡(luò)在成本、效率和容錯(cuò)性等方面都堪比實(shí)際的東京鐵路網(wǎng)絡(luò)。因此，本文提出了基于智能仿生對(duì)象-多頭絨泡菌的網(wǎng)絡(luò)優(yōu)化機(jī)理，構(gòu)提出了構(gòu)建交通網(wǎng)絡(luò)的模型。
　　本文首先對(duì)多頭

3、絨泡菌路徑尋優(yōu)模型進(jìn)行了拓展，提出了有向網(wǎng)絡(luò)中的多頭絨泡菌路徑尋優(yōu)模型?；诖四Ｐ?，結(jié)合用戶的需求情況，建立了路網(wǎng)設(shè)計(jì)模型，并且將其應(yīng)用到Mexio路網(wǎng)，中國(guó)高速路網(wǎng)以及供應(yīng)鏈網(wǎng)絡(luò)的設(shè)計(jì)當(dāng)中。最后，通過(guò)具體的參數(shù)指標(biāo)對(duì)構(gòu)建的網(wǎng)絡(luò)進(jìn)行了評(píng)估。具體來(lái)說(shuō)，本文的工作可以分為以下幾個(gè)部分:
　　(1)將多頭絨泡菌路徑尋優(yōu)模型擴(kuò)展到有向網(wǎng)絡(luò)中針對(duì)原有模型僅僅適用于無(wú)向網(wǎng)絡(luò)的缺陷，我們對(duì)其進(jìn)行了拓展。通過(guò)修改基爾霍夫定律，嵌入檢查程序（一旦發(fā)

4、現(xiàn)邊的方向信息與對(duì)應(yīng)的節(jié)點(diǎn)壓力信息不符時(shí)，我們將這條邊的流量修改為0），我們建立了多頭絨泡菌解決有向網(wǎng)絡(luò)路徑尋優(yōu)的模型。同時(shí)，我們證明了該模型的收斂性，并且與Dijkstra算法進(jìn)行了對(duì)比。
　　(2)基于多頭絨泡菌的最短路徑樹(shù)算法基于有向網(wǎng)絡(luò)中的多頭絨泡菌模型，我們進(jìn)一步進(jìn)行了改進(jìn)。我們將最短路徑樹(shù)中的根節(jié)點(diǎn)當(dāng)作起點(diǎn)，其他的節(jié)點(diǎn)當(dāng)作終點(diǎn)，利用多頭絨泡菌算法解決了最短路徑樹(shù)問(wèn)題。通過(guò)在網(wǎng)絡(luò)上的測(cè)試，多頭絨泡菌模型得到的結(jié)果有效。<

5、br>　　(3)在動(dòng)態(tài)網(wǎng)路中，基于多頭絨泡菌的最短路徑樹(shù)模型在實(shí)際中，網(wǎng)絡(luò)的權(quán)重會(huì)隨著時(shí)間而發(fā)生變化，因此，在這種情況下，如何重建最短路徑樹(shù)成為一個(gè)值得研究的問(wèn)題。針對(duì)傳統(tǒng)算法的缺陷，我們從權(quán)重增加、權(quán)重減少以及權(quán)重混合變化三個(gè)方面研究了多頭絨泡菌算法的自適應(yīng)性。我們通過(guò)在不同的網(wǎng)絡(luò)上測(cè)試之后并且與其他算法相比較，實(shí)驗(yàn)結(jié)果表明我們提出的算法準(zhǔn)確有效。
　　(4)基于多頭絨泡菌的路網(wǎng)設(shè)計(jì)模型多頭絨泡菌在覓食的過(guò)程中，既要消耗能量，又

6、會(huì)從周?chē)沫h(huán)境中攝取能量，因此，它在不斷調(diào)整自身的網(wǎng)絡(luò)結(jié)構(gòu)使之達(dá)到最優(yōu)。利用該機(jī)制，我們基于初始的O-D需求，我們通過(guò)多頭絨泡菌算法迭代一次，記錄此時(shí)的流量矩陣，再利用多頭絨泡菌模型進(jìn)行優(yōu)化。我們成功的將該模型應(yīng)用到Mexico路網(wǎng)以及中國(guó)高速路網(wǎng)，通過(guò)過(guò)濾流量閾值的方式構(gòu)建了不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。另外，我們通過(guò)相關(guān)的參數(shù)分析了這些網(wǎng)絡(luò)的優(yōu)劣。
　　(5)將多頭絨泡菌應(yīng)用到供應(yīng)鏈網(wǎng)絡(luò)設(shè)計(jì)在供應(yīng)鏈網(wǎng)絡(luò)中，網(wǎng)絡(luò)中邊的花費(fèi)會(huì)隨著流量的大小