基于錯(cuò)位突變策略的改進(jìn)人工蜂群算法

《基于錯(cuò)位突變策略的改進(jìn)人工蜂群算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、基于錯(cuò)位突變策略的改進(jìn)人工蜂群算法蔣成1，汪繼文2，邱劍鋒1（1.安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院；2.安徽大學(xué)計(jì)算智能與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室,安徽合肥230601）摘要：人工蜂群算法是一種模擬蜜蜂覓食行為的群智能優(yōu)化算法，具有較好的全局搜索能力，但收斂速度較慢且容易陷入局部最優(yōu).針對(duì)其不足之處,提出了一種基于錯(cuò)位突變策略的人工蜂群算法（DMABC）.該算法在搜索蜜源的時(shí)候運(yùn)用錯(cuò)位突變策略增強(qiáng)種群多樣性，并使用排序選擇機(jī)制和新的比較機(jī)制防止過(guò)早收斂.通過(guò)對(duì)幾個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的實(shí)驗(yàn)表明，改進(jìn)算法具有更快的收斂速度，優(yōu)化精度更高.

2、.jyqkli[6]將人工蜂群算法應(yīng)用于旅行商問(wèn)題中.Ozturk[7]等使用了人工蜂群算法解決無(wú)線傳感器網(wǎng)絡(luò)的動(dòng)態(tài)部署問(wèn)題.胡中華等[8]實(shí)現(xiàn)了將人工蜂群算法應(yīng)用于機(jī)器人路徑規(guī)劃問(wèn)題.肖永豪等[9]提出了一種基于蜂群算法的圖像邊緣檢測(cè)方法.然而隨著對(duì)人工蜂群算法研究的深入，人們發(fā)現(xiàn)該算法同樣存在著缺點(diǎn)：算法收斂速度較慢，且容易陷入局部最優(yōu).針對(duì)這些缺點(diǎn)，國(guó)內(nèi)外的學(xué)者們相繼提出了改進(jìn)的人工蜂群算法.丁海軍等[10]基于Boltzmann選擇機(jī)制提出了一種改進(jìn)的人工蜂群算法用來(lái)優(yōu)化多變量函數(shù).暴勵(lì)等[11]結(jié)合差分進(jìn)化算法提出

3、了一種新的雙種群差分蜂群算法.Lee等[12]在人工蜂群算法中引入群體多樣性的機(jī)制，根據(jù)群體多樣性的門(mén)檻值選擇采用不同的搜索公式.Alam等[13]提出了一種基于指數(shù)分布的自適應(yīng)變異步長(zhǎng)機(jī)制的人工蜂群算法，動(dòng)態(tài)控制搜索過(guò)程中的探索和開(kāi)發(fā)能力.在人工蜂群算法中，全局搜索和局部開(kāi)采的平衡是決定算法性能好壞的關(guān)鍵.本文在基本人工蜂群算法的基礎(chǔ)上，借鑒差分進(jìn)化算法的突變算子，提出了一種新型的錯(cuò)位突變策略，應(yīng)用于蜜蜂的搜索過(guò)程中，以提高種群的多樣性.同時(shí)，還用排序選擇機(jī)制代替了原來(lái)的輪盤(pán)賭選擇機(jī)制來(lái)防止算法的過(guò)早收斂.為了測(cè)試改進(jìn)算法

4、的性能，本文用了幾個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)來(lái)做實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法的性能優(yōu)于基本人工蜂群算法.2基本人工蜂群算法Karaboga提出的基本人工蜂群算法將蜜蜂分為三類(lèi)：引領(lǐng)蜂、跟隨蜂和觀察蜂.蜂群在一個(gè)D維的空間中尋找蜜源，這里的D是在算法開(kāi)始時(shí)人為設(shè)定的，在函數(shù)優(yōu)化問(wèn)題中D就等于目標(biāo)函數(shù)的變量數(shù).一個(gè)蜜源對(duì)應(yīng)目標(biāo)函數(shù)的一個(gè)可行解.在算法中，蜜源用它在D維空間的位置向量表示.例如，第i個(gè)蜜源用i表示，i=(xi1,xi2,…,xiD)，向量中每個(gè)分量的取值范圍由目標(biāo)函數(shù)的解空間決定.尋找最優(yōu)蜜源，在本文中也就是尋找一組能讓目標(biāo)函

5、數(shù)取得最小值的可行解.蜂群分成兩半，一半是引領(lǐng)蜂，一半是跟隨蜂.引領(lǐng)蜂和蜜源一一對(duì)應(yīng)，每個(gè)引領(lǐng)蜂的位置就是一個(gè)蜜源的位置.因此，在程序中，引領(lǐng)蜂的數(shù)目、跟隨蜂的數(shù)目和蜜源的數(shù)目都相等，設(shè)為SN,則種群的規(guī)模也就是2*SN.SN也是一個(gè)需要人工設(shè)定的參數(shù).整個(gè)算法是一個(gè)循環(huán)算法.每次循環(huán)的開(kāi)始，引領(lǐng)蜂會(huì)在各自對(duì)應(yīng)的蜜源周?chē)M(jìn)行搜索.搜索的公式如下：其中，?漬(i,j)是-1到1的隨機(jī)數(shù)，k是引領(lǐng)蜂隨機(jī)選擇的一個(gè)鄰近蜜源，作為擾動(dòng)項(xiàng)，增強(qiáng)全局搜索能力.引領(lǐng)蜂搜索的時(shí)候只改變位置向量的一個(gè)分量，這個(gè)要被改變的分量也是隨機(jī)選擇出來(lái)的

6、.通過(guò)(2)式得到一個(gè)新的蜜源位置后，引領(lǐng)蜂會(huì)對(duì)新蜜源進(jìn)行評(píng)估，計(jì)算出適應(yīng)度值與舊蜜源比較.適應(yīng)度的計(jì)算公式如下：fi是用第i個(gè)蜜源的位置向量作為可行解計(jì)算出來(lái)的目標(biāo)函數(shù)值.從(3)式可以看出，目標(biāo)函數(shù)值越小，該蜜源的適應(yīng)度值就越大.引領(lǐng)蜂經(jīng)過(guò)比較后，如果新蜜源的適應(yīng)度值大于舊蜜源，則更新蜜源的位置；反之，則保留舊蜜源.跟隨蜂則通過(guò)輪盤(pán)賭機(jī)制選擇蜜源進(jìn)行搜索.適應(yīng)度值越高的蜜源會(huì)有更大概率被跟隨蜂選中從而得到更新.跟隨蜂的搜索方程與引領(lǐng)蜂相同.輪盤(pán)賭的選擇概率使用下面的公式計(jì)算出來(lái)的：由于人工蜂群算法有陷入局部最優(yōu)的可能，因

7、此算法中設(shè)置了偵察蜂的操作來(lái)跳出局部最優(yōu).當(dāng)一個(gè)蜜源經(jīng)過(guò)很多次循環(huán)仍無(wú)法得到更新，那么該蜜源對(duì)應(yīng)的引領(lǐng)蜂就會(huì)轉(zhuǎn)化為偵察蜂，舍棄舊蜜源，在搜索空間內(nèi)隨機(jī)生成一個(gè)新的蜜源.偵察蜂的搜索公式如下：lj和uj分別是搜索空間的下界和上界，rand(0,1)是0到1的隨機(jī)值.偵察蜂操作的觸發(fā)條件是有蜜源的停滯次數(shù)達(dá)到了限定值，姑且將這個(gè)限定值設(shè)為limit.limit的值是需要人工設(shè)定的.大量的實(shí)驗(yàn)表明，limit的設(shè)定會(huì)影響到算法的效果，定值太小會(huì)減緩收斂速度，定值太大又起不到跳出局部最優(yōu)的效果.后來(lái)研究者們發(fā)現(xiàn)，將limit的值設(shè)為

8、SN*D可以得到不錯(cuò)的實(shí)驗(yàn)效果，因此本文中l(wèi)imit的值也是SN*D.除此之外，還有一個(gè)最大循環(huán)次數(shù)需要人工設(shè)定，這是算法的終止條件.3基于錯(cuò)位突變策略的人工蜂群算法基本人工蜂群算法在搜索蜜源的時(shí)候，由于其搜索方向是隨機(jī)的，因此具有較好的全局搜索能力.但正因?yàn)樗乃阉魍耆S機(jī)，沒(méi)有任何啟發(fā)