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

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

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

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

4、局最優(yōu)解。如果不能夠?qū)@種偏離進(jìn)行估計(jì)和避免，我們?cè)谟孟伻核惴ㄇ蠼狻﹥?yōu)化問(wèn)題時(shí)，我們卻不能意識(shí)到自己所得到的解可能不是一個(gè)最優(yōu)解，這在許多實(shí)際應(yīng)用中是十分有害的。本文中主要對(duì)蟻群算法的搜索偏離性進(jìn)行了全面的研究，提出了反饋性偏離的概念，提出了一種衡量偏離大小的標(biāo)準(zhǔn)。我們提出了一種改進(jìn)的蟻群算法用來(lái)避免搜索偏離。為了糾正搜索偏離所產(chǎn)生的負(fù)作用，加強(qiáng)解群體的多樣性，我們提出了三種改進(jìn)的螞蟻路徑選擇策略，以增加解的多樣性，使改進(jìn)的算法能夠有

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

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