基于正反饋機制的仿生優(yōu)化算法研究.pdf

1、近年來，通過模擬自然生態(tài)系統(tǒng)，涌現(xiàn)出大量的智能仿生算法求解復(fù)雜優(yōu)化問題，如遺傳算法，粒子群算法，蟻群算法，人工免疫算法，螢火蟲算法等。這些智能生物系統(tǒng)有著相似的特點:單個個體行為簡單而且具有隨機性，但由這些個體組成的生物群體可以相互協(xié)作完成一系列復(fù)雜的任務(wù)。這些智能優(yōu)化算法，應(yīng)用范圍廣泛，尤其在工程設(shè)計、資源分配、生存計劃安排、交通運輸?shù)雀鱾€領(lǐng)域有著深入的應(yīng)用。根據(jù)最近的研究，一種叫作多頭絨泡菌(Physarum polycephalu

2、m)的單細胞多核生物體在路徑尋優(yōu)、網(wǎng)絡(luò)設(shè)計等方面展現(xiàn)出非常智能的特性。研究發(fā)現(xiàn)，分布于迷宮中的多頭絨泡菌，能夠在覓食過程中找到入口與出口之間的最短路徑;更厲害的是，多頭絨泡菌連接食物源構(gòu)造出來的管道網(wǎng)絡(luò)在效率、成本和容錯性能等方面都堪比真實的東京鐵路網(wǎng)。由此，多頭絨泡菌的這種智能特性已經(jīng)越來越受到學(xué)術(shù)界的重視。
　　目前，關(guān)于多頭絨泡菌的智能行為，已有眾多算法、模型用來分析、模擬其內(nèi)在優(yōu)化特性。本文，我們著重圍繞多頭絨泡菌路徑尋優(yōu)

3、模型(Physarum Solver)來展開工作。在多頭絨泡菌路徑尋優(yōu)模型中，首先假定管道內(nèi)液體的流動滿足泊肅葉定律，再利用導(dǎo)通性定量地衡量管道的粗細，繼而用演化方程模擬管道導(dǎo)通性與內(nèi)部流量之間的正反饋機制——導(dǎo)通性越大，則內(nèi)部流量越大;內(nèi)部流量越大，導(dǎo)通性也越大;反之則亦然——最后成功地解決了迷宮問題。多頭絨泡菌路徑尋優(yōu)模型在具有自適應(yīng)性（根據(jù)流量大小自動調(diào)整管道粗細）等優(yōu)點的同時，也存在以下的缺點:(1)在多頭絨泡菌路徑尋優(yōu)模型的內(nèi)

4、部迭代過程中，解關(guān)于壓力的基爾霍夫方程組的計算復(fù)雜度高，為O(n3);(2)傳統(tǒng)的多頭絨泡菌路徑尋優(yōu)模型只能處理無向圖，而在有向圖中無法施展用處;(3)多頭絨泡菌路徑尋優(yōu)模型需要網(wǎng)絡(luò)圖的全局結(jié)構(gòu)信息，這一強制性要求限制了它的應(yīng)用范圍;(4)多頭絨泡菌路徑尋優(yōu)模型利用基爾霍夫方程組來計算節(jié)點的壓力值，由此帶來了管道之間無法相互獨立計算的缺點，也意味著多頭絨泡菌路徑尋優(yōu)模型無法進行并行計算處理。為此，我們有必要對現(xiàn)有的多頭絨泡菌路徑尋優(yōu)模型

5、進行改進，從而能提出更有效、應(yīng)用范圍更廣的算法模型。
　　本文首先分析多頭絨泡菌路徑尋優(yōu)模型的內(nèi)在正反饋優(yōu)化機制，率先將該算法模型用于具有多源多匯的網(wǎng)絡(luò)圖中，探究其能否解決經(jīng)典運輸問題和推廣的運輸問題。然后，基于多頭絨泡菌的正反饋機制，提出一種全新的能量傳播模型，解決一系列實際優(yōu)化問題，包括運輸問題、迷宮問題、最短路徑樹問題、動態(tài)最短路徑樹問題和最大流問題。
　　本文的主要工作包括以下幾個方面:
　　(1)介紹多頭絨泡

6、菌路徑尋優(yōu)模型
　　介紹了多頭絨泡菌路徑迷宮實驗，分析并解釋其智能行為的核心機制:管道粗細與管道里流量之間的正反饋機制。又詳細介紹多頭絨泡菌路徑尋優(yōu)模型，最后介紹在有向圖下的多頭絨泡菌路徑尋優(yōu)模型。
　　(2)提出多頭絨泡菌解運輸問題算法
　　原始的多頭絨泡菌路徑尋優(yōu)模型并未考慮多源多匯情形下是如何優(yōu)化的。正對此問題，我們嘗試將正反饋優(yōu)化機制應(yīng)用到具有多源多匯的有向圖中，建立多源多匯多頭絨泡菌路徑尋優(yōu)模型-最后實驗結(jié)果

7、表明，該模型可以有效地解決平衡運輸問題、非平衡運輸問題和推廣的運輸問題。
　　(3)提出一種基于能量傳播的路徑選擇模型
　　傳統(tǒng)的多頭絨泡菌路徑尋優(yōu)模型無法依靠局部信息尋找最短路徑，且管道間無法并行處理。由流體力學(xué)中的泊肅葉定律、熱力學(xué)中的傅里葉定律和電力學(xué)的歐母定律得到啟發(fā)，我們首先提出一種一般性的能量傳播法則，引入的能量粒子能夠臨時地“存儲”在節(jié)點上，且具有液體、熱量、電流運動的特點。在新構(gòu)建的模型中，各條邊能量流的更新

8、僅僅需要鄰接節(jié)點的能量信息來獨立地計算。最后，引入多頭絨泡菌路徑尋優(yōu)模型的正反饋機制，建立了一種基于能量傳播的路徑選擇模型。該模型具有傳統(tǒng)多頭絨泡菌路徑尋優(yōu)模型不具備的特點-局部性和并行性。
　　(4)將提出的能量傳播模型應(yīng)用于解決一些優(yōu)化問題
　　最先提出的能量傳播模型僅用于解決迷宮問題。這里，我們擴展模型，將其應(yīng)用到多源多匯、單源單匯等不同情形下，進行優(yōu)化行為研究，實驗結(jié)果表明，該模型可以正確地解決運輸問題和最短路徑樹問

9、題。最后，我們將該模型應(yīng)用到動態(tài)無線傳感器網(wǎng)絡(luò)中，發(fā)現(xiàn)該模型能夠很好地進行通信路徑選擇，同時數(shù)值仿真結(jié)果也驗證了該模型能夠在動態(tài)網(wǎng)絡(luò)中解決最短路徑樹問題。
　　(5)能量傳播模型解最大流問題的初步方案
　　正反饋機制在優(yōu)化問題上的應(yīng)用方式還有很多種。在本文中提出了基于能量傳播模型解決最大流的初步方案:建立一條長度大于任意一條源匯節(jié)點間的可能路徑，利用正反饋機制，使得原先沿著虛擬邊的流量逐步收斂到原網(wǎng)絡(luò)中，直至各條邊上的流量不