蟻群優(yōu)化算法的搜索偏離性研究.pdf

1、蟻群優(yōu)化算法的搜索偏離性研究(申請揚州大學工學碩士學位論文)培養(yǎng)單位：揚州大學專業(yè)名稱：計算機軟件與理論研究方向：數(shù)據(jù)挖掘研究生：陳伯倫指導老師：陳岐教授201205摘要蟻群算法是一種求解復雜問題的元啟發(fā)式算法，它是意大利學者MDorigo，VManiezzo等人于20世紀90年代初，受到自然界中螞蟻在覓食過程中所表現(xiàn)出來的路徑尋找模式的啟發(fā)率先提出的。從MDorigo首先設(shè)計出了螞蟻系統(tǒng)(AntSystem，AS)開始，許多國內(nèi)外學者

2、對這類算法進行了不斷的改進，到目前為止已近形成了一套成熟的框架，由于蟻群算法所表現(xiàn)出全局性、穩(wěn)健性等優(yōu)點，蟻群算法的成功不僅表現(xiàn)在處理各種組合優(yōu)化問題上，而且也體現(xiàn)在處理優(yōu)化題時所取得的極佳的性能。它已廣泛的應用在各行各業(yè)，并且取德了非常不錯的成果。由于蟻群算法到目前為止主要成功大多是在實驗層次上，雖然它的性能在不斷的提高，但是在理論上還未像演化算法、遺傳算法、模擬退火等算法那樣具有嚴格的理論基礎(chǔ)。對蟻群算法理論方面的研究，目前主要集中

3、在它的收斂性證明、欺騙性問題、時間復雜度估計等方面。雖然初步取得了一些理論成果，但還存在著一些非常重要的問題亟待解決，如搜索偏離性的問題。蟻群算法在求解一些問題的過程中存在著兩種搜索偏離：一種是正搜索偏離，一種是負搜索偏離。產(chǎn)生這種情況的主要原因是源于算法本身或者問題本身的性質(zhì)。我們期望的情況是蟻群趨向于正搜索偏離，它可以引導螞蟻的搜索向著最優(yōu)解方向前進。但是，在許多情況下蟻群會產(chǎn)生負搜索偏離，它會使我們在求解問題的時候最終不能收斂到全

4、局最優(yōu)解。如果不能夠?qū)@種偏離進行估計和避免，我們在用蟻群算法求解～些優(yōu)化問題時，我們卻不能意識到自己所得到的解可能不是一個最優(yōu)解，這在許多實際應用中是十分有害的。本文中主要對蟻群算法的搜索偏離性進行了全面的研究，提出了反饋性偏離的概念，提出了一種衡量偏離大小的標準。我們提出了一種改進的蟻群算法用來避免搜索偏離。為了糾正搜索偏離所產(chǎn)生的負作用，加強解群體的多樣性，我們提出了三種改進的螞蟻路徑選擇策略，以增加解的多樣性，使改進的算法能夠有

5、效的避免搜索偏離。最后我們還將蟻群算法應用在了社團檢測上。本文的研究工作和主要研究成果有：(1)在已經(jīng)發(fā)現(xiàn)的蟻群優(yōu)化算法的兩種搜索偏離(即表征性偏離、構(gòu)建性偏離)之外，我們提出了第三種偏離，即反饋性偏離。我們給出了反饋性偏離的定義，并且舉側(cè)說明了反饋性偏離的存在。我們針對這三種偏離提出了一種衡量偏離大小的的統(tǒng)一的評價標準，并對該評價標準進行了測試，用實驗證明我們的評價標準的合理性和有效性。(2)提出了一種BA—ACO(Bias—Avoi

6、dingACO)算法來避免蟻群算法產(chǎn)生的搜索偏離。我們分別對傳統(tǒng)的蟻群算法和BA_ACO算法在不同問題上的收斂性進行了理論證明，實驗結(jié)果也充分說明了我們改進的蟻群算法可以避免搜索偏離，最終收斂于全局最優(yōu)解。(3)為了糾正搜索偏離所產(chǎn)生的負作用，加強解群體的多樣性，我們提出了三種改進的螞蟻路徑選擇策略，以增加解的多樣性，使改進的算法能夠有效的避免搜索偏離。我們以胛一digital問題為例，用實驗來驗證三種選擇策略的有效性。實驗結(jié)果表明我們