課程設(shè)計(jì)---蜂群算法及其應(yīng)用

1、<p><b>　　蜂群算法及其應(yīng)用</b></p><p><b>　　研究背景。</b></p><p>　　伴隨著當(dāng)今社會(huì)、經(jīng)濟(jì)、文化和科技日新月異的發(fā)展，現(xiàn)實(shí)生活中面臨著許多復(fù)雜的非線性大系統(tǒng)和快速反應(yīng)性系統(tǒng)，這使得我們傳統(tǒng)的優(yōu)化方法逐漸陷入困境。于是，人們開始尋找更快、更好的方法去解決這些復(fù)雜問題。在自然界中，那些不起眼的群居

2、低智能的生物表現(xiàn)出來的令人嘆為觀止的復(fù)雜的群體智慧給予我們啟迪，如：蟻群、鳥群、蜜蜂群、魚群等。在群居生物中，單個(gè)個(gè)體的智能是簡(jiǎn)單的，但若干個(gè)個(gè)體組成的群體卻表現(xiàn)出遠(yuǎn)遠(yuǎn)超出個(gè)體相加的智慧。在群體中，個(gè)體間相互合作、相互協(xié)調(diào)的自組織能力能夠完成非常復(fù)雜的任務(wù)。這種現(xiàn)象引起眾多學(xué)者的關(guān)注，人們開始研究現(xiàn)象背后存在的機(jī)理，并用計(jì)算機(jī)仿真其中可循的規(guī)律，用以解決傳統(tǒng)優(yōu)化方法難以解決的復(fù)雜問題。其中，較為典型且廣泛應(yīng)用的群體智能算法有：蟻群算法、

3、微粒群算法以及蜂群算法等。</p><p>　　二十世紀(jì)初期以來，在優(yōu)化領(lǐng)域中，傳統(tǒng)的方法，如：線性規(guī)劃、非線性規(guī)劃、對(duì)策論、多目標(biāo)規(guī)劃、決策論排隊(duì)論、隨機(jī)規(guī)劃、庫(kù)存論等，不僅在理論上的研究有很大的發(fā)展，而且在軍事、經(jīng)濟(jì)、城市建設(shè)規(guī)劃、工廠生產(chǎn)規(guī)劃、最優(yōu)設(shè)計(jì)等各個(gè)方面的應(yīng)用取得顯著成就。但伴隨著社會(huì)、經(jīng)濟(jì)和科學(xué)技術(shù)的飛速發(fā)展，在生產(chǎn)生活中出現(xiàn)的許多復(fù)雜的非線性系統(tǒng)和快速反應(yīng)系統(tǒng)等不斷的呈現(xiàn)在我們面前，使得傳統(tǒng)的優(yōu)

4、化方法遇到了空前的挑戰(zhàn)。</p><p>　　群體智能是指由大量數(shù)目的智能個(gè)體組成的具有智能的群體，這個(gè)群體體現(xiàn)出來的智能絕對(duì)不是個(gè)體智能的簡(jiǎn)單相加，而是超過這個(gè)和的智能現(xiàn)象。在進(jìn)行目標(biāo)搜索時(shí)，單個(gè)個(gè)體雖然也能夠?qū)ふ业侥繕?biāo)，但往往只是局限于局部，并不是全局最好的結(jié)果。個(gè)體在空間中隨機(jī)搜尋，在沒有得到整個(gè)群體的信息反饋時(shí)，它的搜索是隨機(jī)的、低智能的、無規(guī)律的。只有群體問的個(gè)體相互合作、相互協(xié)調(diào)，進(jìn)行信息共享時(shí)，才能

5、表現(xiàn)出來在全局中針對(duì)目標(biāo)的尋優(yōu)特征。作為智能個(gè)體，就其大小和功能來說，又是相對(duì)的，要根據(jù)所要解決的具體問題而定。另外，群體智能中的個(gè)體，在整個(gè)群體尋優(yōu)過程中也并不能時(shí)刻保證都具有尋優(yōu)的特征，其智能尋優(yōu)方式的實(shí)現(xiàn)足通過整個(gè)智能群體的優(yōu)化特征而體現(xiàn)出來的。</p><p>　　人工蜂群算法作為典型的群體智能算法，是基于種群尋優(yōu)的啟發(fā)式搜索算法，充分發(fā)揮群體中個(gè)體問的信息傳遞，在蜂巢周圍尋找到路徑最短，食物最豐富的食物

6、源。由于整個(gè)覓食過程與旅行商問題的相似性，該算法適合用來解決旅行商的最短路徑問題，并取得較好的結(jié)果。</p><p>　　蜂群算法(BCO，Bee Colony Optimization)是受到自然界的蜜蜂行為啟發(fā)而提出的一種新穎的元啟發(fā)式優(yōu)化算法。根據(jù)所受啟發(fā)的生物機(jī)理的不同，蜂群算法可分為兩大類：</p><p>　　基于蜜蜂繁殖機(jī)理的蜂群算法(BCO on propagating)。

7、</p><p>　　基于蜜蜂采蜜機(jī)理的蜂群算法(BC0 on gathering)。</p><p>　　兩種思想各有其獨(dú)特的實(shí)現(xiàn)原理和發(fā)展軌跡。</p><p>　　對(duì)于基于繁殖的蜂群算法。Abbass發(fā)展出一種蜜蜂繁殖優(yōu)化模型(BMO，Bee Mating Optimization)。 Bozorg Haddad和A．Afshar共同將其發(fā)展并應(yīng)用基于離散變量

8、的水庫(kù)優(yōu)化問題中。隨后，Bozorg Haddad等將同一理論在三種數(shù)學(xué)問題的測(cè)試平臺(tái)上進(jìn)行了應(yīng)用。</p><p>　　蜜蜂的采蜜行為是一種典型的群體智慧行為。Yang發(fā)展出一種虛擬蜜蜂理論(VBA，virtual bee algorithm)來解決數(shù)值優(yōu)化問題。VBA中，一群虛擬蜜蜂初始時(shí)隨機(jī)分布在解空間中：這個(gè)蜜蜂根據(jù)判決函數(shù)計(jì)算的適應(yīng)度來尋找附近的花蜜源。理論中，解的優(yōu)化程度可以用蜜蜂之間交流的劇烈程度來

9、衡量。對(duì)于多變量數(shù)值優(yōu)化問題，Karaboga根據(jù)蜜蜂采集行為設(shè)計(jì)了虛擬蜜蜂種群模型(ABC，artificial bee colony algorithm)，并和Basturk一起將ABC模型與GA進(jìn)行了性能上的比較，并進(jìn)一步與其他比較著名的元啟發(fā)式理論如：差分進(jìn)化(DE)，粒子群(PSO)在非約束數(shù)值優(yōu)化問題上進(jìn)行了仿真比較。進(jìn)而ABC理論被擴(kuò)展應(yīng)用到解決約束(CO，constraint optimization)問題，并在13種比

10、較著名的約束優(yōu)化問題上與DE，PSO進(jìn)行了比較。目前，ABC模型的研究主要集中在人工神經(jīng)網(wǎng)絡(luò)的訓(xùn)練上。</p><p>　　2、蜂群算法的理論基礎(chǔ)</p><p>　　Seely最早提出一種蜂群的群居行為為模型。模型中，群體中的各個(gè)角色蜜蜂，只是完成簡(jiǎn)單的、低智商的任務(wù)；但群體中的個(gè)體通過舞蹈、氣味等信息交互方式使整個(gè)群體協(xié)同能夠完成較為復(fù)雜的任務(wù)，如建筑蜂巢、繁衍后代和覓食等。</

11、p><p>　　Karaboga D在2005年將蜂群算法應(yīng)用到函數(shù)值優(yōu)化問題上，并提出系統(tǒng)的ABC(Artificial Bee Colony Algorithm)算法，取得很好的效果。</p><p>　　在人工蜂群算法中，食物源的位置表示待優(yōu)化問題的一個(gè)可行解，食物源的豐富程度代表解的質(zhì)量，即適應(yīng)度。在模型中，我們通常設(shè)：引領(lǐng)蜂的數(shù)量=跟隨蜂的數(shù)量=群體中解的數(shù)量。算法中，初始化生成M個(gè)

12、解，對(duì)于每個(gè)解都是一個(gè)D維向量。而后，蜜蜂開始對(duì)全部的食物源進(jìn)行循環(huán)搜索，最大循環(huán)次數(shù)為MCN。其中，引領(lǐng)蜂會(huì)先對(duì)全局進(jìn)行搜索，并比較搜索前后食物源的豐富程度，蜜蜂會(huì)選擇食物源較為豐富的目標(biāo)。當(dāng)所有的引領(lǐng)蜂完成搜索后，他們會(huì)回到信息交流區(qū)(舞蹈區(qū))把自己掌握的關(guān)于食物源的信息與其他蜜蜂進(jìn)行信息共享。跟隨蜂則會(huì)根據(jù)引領(lǐng)蜂提供的信息按照一定的概率選擇引領(lǐng)蜂進(jìn)行跟隨。越豐富的食物源被選擇的概率越大。然后，跟隨蜂會(huì)和引領(lǐng)蜂一樣進(jìn)行鄰域搜索，并選

13、擇較好的解。</p><p>　　人工蜂群算法中，蜜蜂的采蜜行為和函數(shù)優(yōu)化問題的對(duì)應(yīng)關(guān)系如表2．1所示：</p><p>　　表2．1 蜂群覓食行為與函數(shù)優(yōu)化的對(duì)應(yīng)關(guān)系</p><p>　　Table 2．1 The relationship of Bee Colony foraging behavior and function optimization</

14、p><p>　　初始化時(shí)，隨機(jī)生成Ns個(gè)可行解并計(jì)算函數(shù)值，將函數(shù)值從優(yōu)到劣排名，前50％作為蜜源位置即引領(lǐng)蜂，后50％為跟隨蜂。隨機(jī)產(chǎn)生可行解的公式如下：</p><p><b>　　(2．1)</b></p><p>　　其中j∈{1，2，?，Q}為Q維解向量的某個(gè)分量。</p><p>　　蜜蜂記錄自己到目前為止的最優(yōu)

15、值，并在當(dāng)前蜜源附近展開鄰域搜索，產(chǎn)生一個(gè)新位置替代前一位置的公式為：</p><p><b>　　(2．2)</b></p><p>　　其中j∈{1，2，?，Q}，k∈(1，2，?，sn)，k為隨機(jī)生成且k≠i， 為[一1，1]之間的隨機(jī)數(shù)。</p><p>　　蜜蜂采蜜時(shí)采用貪婪原則，將記憶中的最優(yōu)解和鄰域搜索到的解做比較，當(dāng)搜索解優(yōu)于記

16、憶中的最優(yōu)解時(shí)，替換記憶解；反之，保持不變。在所有的引領(lǐng)蜂完成鄰域搜索后，引領(lǐng)蜂跳擺尾舞與跟隨蜂共享蜜源信息。跟隨蜂根據(jù)蜜源信息以一定概率選擇引領(lǐng)蜂，收益度大的引領(lǐng)蜂吸引跟隨蜂的概率大于收益度小的引領(lǐng)蜂。同樣，跟隨蜂在采蜜源附近鄰域搜索，采用貪婪準(zhǔn)則，比較跟隨蜂搜索解與原引領(lǐng)蜂的解，當(dāng)搜索解優(yōu)于原引領(lǐng)蜂的解時(shí)，替換原引領(lǐng)蜂的解，完成角色互換；反之，保持不變。</p><p>　　ABC算法中，跟隨蜂選擇引領(lǐng)蜂的概

17、率公式為：</p><p><b>　　(2. 3)</b></p><p>　　按照如下公式計(jì)算適應(yīng)值：</p><p>　　根據(jù)f是否大于零， (2. 4)</p><p>　　式(2．3)中， 為第f個(gè)解的適應(yīng)值，對(duì)應(yīng)食物源的豐富程度。食物源越豐富,被跟隨蜂選擇的概率越大。為防止算法

18、陷入局部最優(yōu)，算法1imit次迭代沒有改進(jìn)，放棄該解，由偵察蜂產(chǎn)生一個(gè)新的位置代替。</p><p>　　人工蜂群算法的算法流程：</p><p>　　ABC算法的流程為：</p><p><b>　　1：初始化種群；</b></p><p>　　2：cycle=l：</p><p><b&

19、gt;　　3：repeat：</b></p><p>　　4:雇傭蜂根據(jù)公式（2.2）在解的鄰域內(nèi)產(chǎn)生新解（食物源位置），其中，k是i鄰域內(nèi)的一個(gè)值，是[一1，1]之間的隨機(jī)數(shù)；</p><p>　　5:應(yīng)用貪婪原則選擇在 和 之問做出選擇；</p><p>　　6：根據(jù)公式(2．3)(2．4)計(jì)算轉(zhuǎn)移概率 ；</p><p>　

20、　7：根據(jù)轉(zhuǎn)移概率，跟隨蜂選擇引領(lǐng)蜂進(jìn)行跟隨，并根據(jù)公式(2．2)產(chǎn)生一個(gè)新解；</p><p>　　8：跟隨蜂應(yīng)用貪婪原則選擇在和 之問做出選擇；</p><p>　　9：放棄一個(gè)解，角色轉(zhuǎn)變成偵查蜂，并根據(jù)公式(2．1)產(chǎn)生一個(gè)新解；</p><p><b>　　10：記錄最好解；</b></p><p>　　11：

21、cycle=cycle+1；</p><p>　　12：達(dá)到最大循環(huán)數(shù)，最Pcycle=mcn。，</p><p>　　從上述算法中我們不難看出，ABC算法的核心由三個(gè)部分構(gòu)成：</p><p>　　1．引領(lǐng)蜂：進(jìn)行鄰域搜索；</p><p>　　2．跟隨蜂：對(duì)目標(biāo)進(jìn)行“開采”；</p><p>　　3．偵察蜂：對(duì)目標(biāo)

22、進(jìn)行“探索”。</p><p>　　3、蜂群算法解決函數(shù)優(yōu)化問題</p><p>　　3.1函數(shù)優(yōu)化問題的描述</p><p>　　目標(biāo)優(yōu)化問題可以描述為： </p><p>　　Max f(x ) (3.1.1) x∈S </p><p>　　或：Min f( x)

23、 (3.1.2) x∈S </p><p>　　這里S→ 稱為搜索空間，f(x)：S→ 稱為目標(biāo)函數(shù)。 (3.1.1)式描述的優(yōu)化問題稱為極大化問題,(3.1.2)式描述的稱為極小化問題。 當(dāng)把f(x)看成是一序列的函數(shù)時(shí)上述的問題就轉(zhuǎn)變?yōu)槎嗄繕?biāo)優(yōu)化問題。 </p><p>　　對(duì)很多實(shí)際問題進(jìn)行數(shù)學(xué)建模后?？蓪⑵涑橄鬄橐粋€(gè)數(shù)值函數(shù)的優(yōu)化問題。由于問題種類的繁多、影響因素的復(fù)雜。這些

24、數(shù)學(xué)函數(shù)會(huì)呈現(xiàn)出不同的數(shù)學(xué)特征，比如連續(xù)的、離散的、凸的、凹的、單峰值的、多峰值的函數(shù)等等，經(jīng)常遇到的函數(shù)還有這些不同數(shù)學(xué)特征的組合。除了在函數(shù)是連續(xù)、可求導(dǎo)、低階的簡(jiǎn)單情況下可解折地求出其最優(yōu)解外。大部分情況需要通過數(shù)值計(jì)算方法來進(jìn)行近似優(yōu)化計(jì)算，盡管人們對(duì)這個(gè)問題研究了很多年。但至今仍無一種既能處理各種不同的復(fù)雜函數(shù)、又具有良好求解結(jié)果的數(shù)值計(jì)算方法。特別是當(dāng)問題的規(guī)模比較大時(shí)，優(yōu)化計(jì)算時(shí)的搜索空間急 劇擴(kuò)大，人們認(rèn)識(shí)到要嚴(yán)格地求出

25、其最優(yōu)解不太現(xiàn)實(shí)。所以需要研究出一種能夠在可接受的時(shí)間和可接受的精度范圍內(nèi)求出數(shù)值函數(shù)近似最優(yōu)解的方法或通用算法。蜂群算法提供了求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，函數(shù)優(yōu)化正是其最成熟的應(yīng)用域。也是對(duì)蜂群算法進(jìn)行性能評(píng)價(jià)的常用算倒。在對(duì)各種復(fù)雜形式的測(cè)試函數(shù)的計(jì)算中。由于蜂群算法直接以目標(biāo)函數(shù)值作為搜索信息。同時(shí)使用多個(gè)搜索點(diǎn)進(jìn)行索，且這種概率搜索始終遍及整個(gè)解空間，都能找到幾乎全局最優(yōu)解。對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，在其

26、他優(yōu)化方法較難</p><p>　　實(shí)踐表明，遺傳算法求解函數(shù)優(yōu)化問題的計(jì)算教率比較高、適用范圍相當(dāng)廣。與傳統(tǒng)的優(yōu)化方法相比．遺傳算法具有如下特點(diǎn)：具有簡(jiǎn)單通用、魯捧性強(qiáng)、適 于并行處理以及高效、實(shí)用等顯著優(yōu)點(diǎn)。</p><p>　　3.2 解決問題的步驟</p><p><b>　　(1) 編碼</b></p><p>

27、;　　在遺傳算法的運(yùn)行過程中，它不對(duì)所求問題的實(shí)際決策變量直接進(jìn)行操作，而是對(duì)表示可行解的個(gè)體編碼施加選擇、交叉和變異等遺傳操作。將一個(gè)問題的可行解從其可行解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就稱為編碼。典型的遺傳算法都采用二進(jìn)制的編碼方式，在本文中我們也采用這種與自然界中的實(shí)際情況相對(duì)應(yīng)的編碼方式。但是在多個(gè)變量的情況下，傳統(tǒng)的整體編碼是用一個(gè)一維數(shù)組來按順序存放所有的基因。這樣的編碼方式明顯地存在著問題：隨著自變量維數(shù)的

28、增加或求解精度要求的提高，整個(gè)位串的長(zhǎng)度會(huì)迅速地增加，這樣，整個(gè)位串的長(zhǎng)度將變得難以忍受，不方便操作；此外，一旦位串過長(zhǎng),將不可避免地導(dǎo)致重復(fù)操作，而且由于位串過長(zhǎng)，還會(huì)降低雜交和變異操作的結(jié)果，致使算法易陷于局部最優(yōu)或增加運(yùn)行時(shí)間。</p><p>　　為了解決這些問題，我們采用一種改進(jìn)的二進(jìn)制編碼方式——獨(dú)立編碼方式。它將每個(gè)變量都相互獨(dú)立開來，采用多維的數(shù)組來表示多維的變量，用獨(dú)立編碼方式就表示為：<

29、/p><p>　　x1=0110110100 ，x2=1101001011</p><p>　　chrom[n][0]= 0110110100 x1</p><p>　　chrom[n][1]= 1101001011 x2</p><p>　　實(shí)驗(yàn)表明，獨(dú)立編碼較整體編碼具有良好的收斂性，能使函數(shù)較好地逼近于極值。

30、原因主要在于當(dāng)雜交和變異概率不變時(shí)，原始的整體編碼由于精度要求，導(dǎo)致位串過長(zhǎng)，而其中相當(dāng)大的一部分位串只表示小數(shù)點(diǎn)后的數(shù)值，所以若雜交和變異算子作用在這一部分上，則對(duì)數(shù)值的改變不大。而獨(dú)立編碼由于大大縮短了位串長(zhǎng)度，所以使得雜交和變異算子有很大可能作用到代表小數(shù)點(diǎn)以前的數(shù)值位串上，致使自變量的數(shù)值有較大改變。這就能使算法有效地跳出局部最優(yōu)解陷阱，更好地接近全局最優(yōu)解。</p><p><b>　　(2)

31、 選擇與交叉</b></p><p>　　蜂后以一定的速率穿梭于空間中的不同區(qū)域，并在各個(gè)區(qū)域內(nèi)隨機(jī)地與碰到的雄蜂進(jìn)行交配。在婚飛的開始，給蜂后賦予一定量的能量，在能量消耗到零或某一限度時(shí)或在受精囊裝滿時(shí)返回蜂巢。</p><p>　　雄蜂提供給后代一半的基因，因此保證雄蜂的高適應(yīng)度也有利于產(chǎn)生適應(yīng)度較高的幼蜂。為此，我們使用一個(gè)模擬的退火算法來對(duì)雄蜂進(jìn)行選擇。按照退火算法的原

32、理，令當(dāng)前的雄蜂為D0，隨機(jī)產(chǎn)生下一個(gè)用于交配的雄蜂為 D1，如果f (D1) ≥f (D0) 則D1被接受為當(dāng)前雄蜂(f(D)表示雄蜂 D 的適應(yīng)度) ，準(zhǔn)備與蜂后交配。否則 D1僅以概率:</p><p><b>　　(3.2.1)</b></p><p>　　被接受。S（t）表示蜂后在 t 時(shí)刻的速率，隨著時(shí)間的推移，S（t）的值會(huì)越來越小，則接受不良個(gè)體的概率

33、也就越來越小，所以總能保持雄蜂的高適應(yīng)度。</p><p>　　雄蜂與蜂后交配的隨機(jī)率用下式表示：</p><p><b>　　(3.2.2)</b></p><p>　　此處，prob（Q ，D）是將 D的精子加入到蜂后Q的受精囊的概率，也就是指交配成功的概率；⊿f（t）是 D 的適應(yīng)度 f（D）與Q 的適應(yīng)度 f（Q）的絕對(duì)差值；S（t）表

34、示蜂后在t 時(shí)刻的速率。</p><p>　　表面上看來這個(gè)函數(shù)有些類似退火算法，當(dāng)蜂后在剛開始婚飛因而速率很大時(shí)或是雄蜂的適應(yīng)度和蜂后的一樣高時(shí)，交配的概率很大。隨著時(shí)間的推移，蜂后的速率和能量以下面的方式衰減：</p><p>　　S(t+1)=α*S(t) (3.2.3) E(t+1)=E(t) －r (3.2.4)</p>

35、<p>　　此處，α 是一個(gè)因子，α∈[0 ，1] ；r 是每次轉(zhuǎn)移后能量的消耗量。</p><p><b>　?。?）變異和災(zāi)變</b></p><p>　　自然界中的變異率是進(jìn)化的動(dòng)力，只有通過變異率才能使后代產(chǎn)生前代沒有的特性，為進(jìn)化提供條件。同時(shí)變異率設(shè)置得是否合適對(duì)于算法的表現(xiàn)也有很大的影響。如果變異率太小則某位的有效基因可能經(jīng)過好多代的進(jìn)化都不

36、會(huì)出現(xiàn)，算法容易陷入局部解中；如果變異率設(shè)得太大則經(jīng)常變異容易丟失一些有效基因，反而倒喪失了啟發(fā)性而變得更像隨機(jī)搜索。一般情況下，變異率設(shè)在 0.0001 ～0.1就比較合適了。</p><p>　　在自然界中，有時(shí)會(huì)因?yàn)榄h(huán)境的突然性的巨大變化而使物種發(fā)生很大的改變，這時(shí)原有的基因平衡被打破，創(chuàng)造出完全不同的染色體，生物的性狀發(fā)生很大的變化。將這種思想應(yīng)用于我們的蜂群算法中，有利于進(jìn)化跳出局部極值點(diǎn)，快速、準(zhǔn)確地

37、搜索出全局最優(yōu)解。但是，災(zāi)變率的選擇也不是任意的，它應(yīng)該根據(jù)具體的情況而合理地設(shè)定。多次實(shí)驗(yàn)的結(jié)果表明：選擇災(zāi)變率的標(biāo)準(zhǔn)是要在整個(gè)的進(jìn)化過程中保證發(fā)生1 到2 次的災(zāi)變。否則，若災(zāi)變率設(shè)得太小，可能整個(gè)進(jìn)化完成后都沒有發(fā)生一次災(zāi)變，也就喪失了設(shè)置災(zāi)變率的意義；若災(zāi)變率太大，則多次的反復(fù)災(zāi)變就很容易丟失經(jīng)過多代進(jìn)化積累起來的有利基因組合。</p><p>　　3.3 核心參數(shù)的設(shè)置</p><p

38、>　　改進(jìn)后的ABC算法中需設(shè)定的參數(shù)有三個(gè)：種群數(shù)SN，搜索代數(shù)MCN，limit 。（1）Rosenbrock 函數(shù)</p><p>　?。? ）Griew函數(shù)</p><p>　?。? ）Schaffer函數(shù)</p><p>　　二維Rosenbrok函數(shù)f1(X) 是一個(gè)非凸函數(shù)，它在（1 ，1）處達(dá)到極小值；f2(X) 是由Griewangk提出的。

39、它的全局極小是xi=0 ，i=1 ，2 ，…。其局部極小點(diǎn)是xi ≈ ±k* π*,i=1,2, …，n，k=0 ，1 ，2 ，…。</p><p>　　函數(shù)f1(X) ，算法參數(shù)設(shè)置為：種群規(guī)模SN=100；終止代數(shù)MCN=300limit=100 ，T0=100。</p><p>　　函數(shù)f2(X) ，算法參數(shù)設(shè)置為：種群規(guī)模SN=50；終止代數(shù)MCN=500limit=50

40、 ，T0=100。</p><p>　　函數(shù)f3(X) ，算法參數(shù)設(shè)置為：種群規(guī)模SN=30；終止代數(shù)MCN=60；limit=10 ，T0=100。</p><p><b>　　3.4 核心代碼</b></p><p><b>　　clear all</b></p><p><b>　　

41、close all</b></p><p><b>　　clc</b></p><p>　　%/* Control Parameters of ABC algorithm*/</p><p>　　NP=20; %/* The number of colony size (employed bees+onlooker bees)*/&

42、lt;/p><p>　　FoodNumber=NP/2; %/*The number of food sources equals the half of the colony size*/</p><p>　　limit=100; %/*A food source which could not be improved through "limit" trials is

43、abandoned by its employed bee*/</p><p>　　maxCycle=2500; %/*The number of cycles for foraging {a stopping criteria}</p><p>　　%/* Problem specific variables*/</p><p>　　objfun='Sph

44、ere'; %cost function to be optimized</p><p>　　D=100; %/*The number of parameters of the problem to be optimized*/</p><p>　　ub=ones(1,D)*100; %/*lower bounds of the parameters. */</p>

45、<p>　　lb=ones(1,D)*(-100);%/*upper bound of the parameters.*/</p><p>　　runtime=1;%/*Algorithm can be run many times in order to see its robustness*/</p><p>　　%Foods [FoodNumber][D]; /*Foods

46、 is the population of food sources. Each row of Foods matrix is a vector holding D parameters to be optimized. The number of rows of Foods matrix equals to the FoodNumber*/</p><p>　　%ObjVal[FoodNumber]; /*f

47、 is a vector holding objective function values associated with food sources */</p><p>　　%Fitness[FoodNumber]; /*fitness is a vector holding fitness (quality) values associated with food sources*/</p>

48、<p>　　%trial[FoodNumber]; /*trial is a vector holding trial numbers through which solutions can not be improved*/</p><p>　　%prob[FoodNumber]; /*prob is a vector holding probabilities of food sources (so

49、lutions) to be chosen*/</p><p>　　%solution [D]; /*New solution (neighbour) produced by v_{ij}=x_{ij}+\phi_{ij}*(x_{kj}-x_{ij}) j is a randomly chosen parameter and k is a randomlu chosen solution different f

50、rom i*/</p><p>　　%ObjValSol; /*Objective function value of new solution*/</p><p>　　%FitnessSol; /*Fitness value of new solution*/</p><p>　　%neighbour, param2change; /*param2change c

51、orrresponds to j, neighbour corresponds to k in equation v_{ij}=x_{ij}+\phi_{ij}*(x_{kj}-x_{ij})*/</p><p>　　%GlobalMin; /*Optimum solution obtained by ABC algorithm*/</p><p>　　%GlobalParams[D];

52、/*Parameters of the optimum solution*/</p><p>　　%GlobalMins[runtime]; /*GlobalMins holds the GlobalMin of each run in multiple runs*/</p><p>　　GlobalMins=zeros(1,runtime);</p><p>　　

53、for r=1:runtime</p><p>　　% /*All food sources are initialized */</p><p>　　%/*Variables are initialized in the range [lb,ub]. If each parameter has different range, use arrays lb[j], ub[j] instea

54、d of lb and ub */</p><p>　　Range = repmat((ub-lb),[FoodNumber 1]);</p><p>　　Lower = repmat(lb, [FoodNumber 1]);</p><p>　　Foods = rand(FoodNumber,D) .* Range + Lower;</p><

55、p>　　ObjVal=feval(objfun,Foods);</p><p>　　Fitness=calculateFitness(ObjVal);</p><p>　　%reset trial counters</p><p>　　trial=zeros(1,FoodNumber);</p><p>　　%/*The best fo

56、od source is memorized*/</p><p>　　BestInd=find(ObjVal==min(ObjVal));</p><p>　　BestInd=BestInd(end);</p><p>　　GlobalMin=ObjVal(BestInd);</p><p>　　GlobalParams=Foods(Best

57、Ind,:);</p><p><b>　　iter=1;</b></p><p>　　while ((iter <= maxCycle)),</p><p>　　%%%%%%%%% EMPLOYED BEE PHASE %%%%%%%%%%%%%%%%%%%%%%%%</p><p>　　for i=1:(Foo

58、dNumber)</p><p>　　%/*The parameter to be changed is determined randomly*/</p><p>　　Param2Change=fix(rand*D)+1;</p><p>　　%/*A randomly chosen solution is used in producing a mutant s

59、olution of the solution i*/</p><p>　　neighbour=fix(rand*(FoodNumber))+</p><p>　　%/*Randomly selected solution must be different from the solution i*/ </p><p>　　while(neighbou

60、r==i)</p><p>　　neighbour=fix(rand*(FoodNumber))+1;</p><p><b>　　end</b></p><p>　　sol=Foods(i,:);</p><p>　　% /*v_{ij}=x_{ij}+\phi_{ij}*(x_{kj}-x_{ij}) */<

61、/p><p>　　sol(Param2Change)=Foods(i,Param2Change)+(Foods(i,Param2Change)-Foods(neighbour,Param2Change))*(rand-0.5)*</p><p>　　% /*if generated parameter value is out of boundaries, it is shifted ont

62、o the boundaries*/</p><p>　　ind=find(sol<lb);</p><p>　　sol(ind)=lb(ind);</p><p>　　ind=find(sol>ub);</p><p>　　sol(ind)=ub(ind);</p><p>　　%evaluate new

63、 solution</p><p>　　ObjValSol=feval(objfun,sol);</p><p>　　FitnessSol=calculateFitness(ObjValSol)</p><p>　　% /*a greedy selection is applied between the current solution i and its mut

64、ant*/</p><p>　　if (FitnessSol>Fitness(i)) %/*If the mutant solution is better than the current solution i, replace the solution with the mutant and reset the trial counter of solution i*/</p><p

65、>　　Foods(i,:)=sol;</p><p>　　Fitness(i)=FitnessSol;</p><p>　　ObjVal(i)=ObjValSol;</p><p>　　trial(i)=0;</p><p><b>　　else</b></p><p>　　trial(i)

66、=trial(i)+1; %/*if the solution i can not be improved, increase its trial counter*/</p><p><b>　　end</b></p><p><b>　　end;</b></p><p>　　%%%%%%%%%%%%%%%%%%%%%%%

67、% CalculateProbabilities %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%</p><p>　　%/* A food source is chosen with the probability which is proportioal to its quality*/</p><p>　　%/*Diffe

68、rent schemes can be used to calculate the probability values*/</p><p>　　%/*For example prob(i)=fitness(i)/sum(fitness)*/</p><p>　　%/*or in a way used in the metot below prob(i)=a*fitness(i)/max(

69、fitness)+b*/</p><p>　　%/*probability values are calculated by using fitness values and normalized by dividing maximum fitness value*/</p><p>　　prob=(0.9.*Fitness./max(Fitness))+0.1;</p>&

70、lt;p>　　%%%%%%%%%%%%%%%%%%%%%%%% ONLOOKER BEE PHASE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%</p><p><b>　　i=1;</b></p><p><b>　　t=0;</b></p><p>　　w

71、hile(t<FoodNumber)</p><p>　　if(rand<prob(i))</p><p><b>　　t=t+1;</b></p><p>　　%/*The parameter to be changed is determined randomly*/</p><p>　　Param2Ch

72、ange=fix(rand*D)+1;</p><p>　　%/*A randomly chosen solution is used in producing a mutant solution of the solution i*/</p><p>　　neighbour=fix(rand*(FoodNumber))+1; </p><p>　　%/*Rando

73、mly selected solution must be different from the solution i*/ </p><p>　　while(neighbour==i)</p><p>　　neighbour=fix(rand*(FoodNumber))+1;</p><p><b>　　end;</b></

74、p><p>　　sol=Foods(i,:);</p><p>　　% /*v_{ij}=x_{ij}+\phi_{ij}*(x_{kj}-x_{ij}) */</p><p>　　sol(Param2Change)=Foods(i,Param2Change)+(Foods(i,Param2Change)-Foods(neighbour,Param2Change))*

75、(rand-0.5)*2;</p><p>　　% /*if generated parameter value is out of boundaries, it is shifted onto the boundaries*/</p><p>　　ind=find(sol<lb);</p><p>　　sol(ind)=lb(ind);</p>

76、<p>　　ind=find(sol>ub);</p><p>　　sol(ind)=ub(ind);</p><p>　　%evaluate new solution</p><p>　　ObjValSol=feval(objfun,sol);</p><p>　　FitnessSol=calculateFitness(

77、ObjValSol);</p><p>　　% /*a greedy selection is applied between the current solution i and its mutant*/</p><p>　　if (FitnessSol>Fitness(i)) %/*If the mutant solution is better than the current

78、 solution i, replace the solution with the mutant and reset the trial counter of solution i*/</p><p>　　Foods(i,:)=sol;</p><p>　　Fitness(i)=FitnessSol;</p><p>　　ObjVal(i)=ObjValSol;&

79、lt;/p><p>　　trial(i)=0;</p><p><b>　　else</b></p><p>　　trial(i)=trial(i)+1; %/*if the solution i can not be improved, increase its trial counter*/</p><p><b&

80、gt;　　end;</b></p><p><b>　　end;</b></p><p><b>　　i=i+1;</b></p><p>　　if (i==(FoodNumber)+1) </p><p><b>　　i=1;</b></p><

81、;p><b>　　end; </b></p><p><b>　　end;</b></p><p>　　%/*The best food source is memorized*/</p><p>　　ind=find(ObjVal==min(ObjVal));</p><p>　　ind

82、=ind(end);</p><p>　　if (ObjVal(ind)<GlobalMin)</p><p>　　GlobalMin=ObjVal(ind);</p><p>　　GlobalParams=Foods(ind,:);</p><p><b>　　end; </b></p><p

83、>　　%%%%%%%%%%%% SCOUT BEE PHASE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%</p><p>　　%/*determine the food sources whose trial counter exceeds the "limit" value. </p><p>　　%In

84、Basic ABC, only one scout is allowed to occur in each cycle*</p><p>　　ind=find(trial==max(trial));</p><p>　　ind=ind(end);</p><p>　　if (trial(ind)>limit)</p><p>　　Bas

85、(ind)=0;</p><p>　　sol=(ub-lb).*rand(1,D)+lb;</p><p>　　ObjValSol=feval(objfun,sol);</p><p>　　FitnessSol=calculateFitness(ObjValSol);</p><p>　　Foods(ind,:)=sol;</p>

86、<p>　　Fitness(ind)=FitnessSol;</p><p>　　ObjVal(ind)=ObjValSol;</p><p><b>　　End;</b></p><p>　　fprintf('er=%d ObjVal=%g\n',iter,GlobalMin);</p><p

87、>　　iter=iter+1;</p><p>　　end % End of ABC</p><p>　　GlobalMins(r)=GlobalMin;</p><p>　　end; %end of runs</p><p><b>　　save all</b></p><p>　　3.4

88、 實(shí)驗(yàn)結(jié)果和分析</p><p>　　(1)函數(shù)f1(X) ，50次連續(xù)運(yùn)算的結(jié)果為：平均最優(yōu)解1.42×10-14，成功率100%，隨機(jī)選取一次最優(yōu)個(gè)體的進(jìn)化過程如圖3.1所示。</p><p>　　圖3. 1 函數(shù)f1(x)最佳個(gè)體進(jìn)化過程</p><p>　　(2)函數(shù)f2(x), 50次連續(xù)運(yùn)算的結(jié)果為：平均最優(yōu)解1.42×10-14，

89、成功率100%，隨機(jī)選取一次最優(yōu)個(gè)體的進(jìn)化過程如圖3.2所示。</p><p>　　圖3.2 函數(shù)f2(x)最佳個(gè)體進(jìn)化過程</p><p>　　（3）函數(shù)f3(x), 50次連續(xù)運(yùn)算的結(jié)果為：平均最優(yōu)解1.42×10-14，成功率100%，隨機(jī)選取一次最優(yōu)個(gè)體的進(jìn)化過程如圖3.3所示。</p><p>　　圖3.3 函數(shù)f3(x)最佳個(gè)體進(jìn)化過程&l

90、t;/p><p>　　(4)結(jié)果分析：表1 是本文提出的BABC 算法與標(biāo)準(zhǔn)ABC算法、GA、PSO 算法各運(yùn)行50次的實(shí)驗(yàn)結(jié)果比較。GA和PSO 是文獻(xiàn)中的算法結(jié)果。從表1 可見，ABC算法在搜索空間中局部極值點(diǎn)少的情況下具有良好的尋優(yōu)能力。但是對(duì)于復(fù)雜函數(shù)來說，ABC算法和PSO 算法優(yōu)化結(jié)果并不理想，很容易陷入局部極值。而改進(jìn)后的BABC 算法對(duì)于測(cè)試函數(shù)，特別是對(duì)于復(fù)雜多峰函數(shù)的優(yōu)化結(jié)果明顯好于前面兩種方法。

91、這是因?yàn)锽ABC 算法中同時(shí)包含了確定性和隨機(jī)性搜索因素，在處理多維復(fù)雜函數(shù)時(shí)能表現(xiàn)出較強(qiáng)的優(yōu)化性能。</p><p>　　表1 BABC算法與標(biāo)準(zhǔn)ABC、GA以及PSO算法優(yōu)化結(jié)果比較</p><p><b>　　4、總結(jié)和展望</b></p><p>　　盡管人工蜂群算法在國(guó)內(nèi)外的研究還有待發(fā)展，但其已經(jīng)在解決復(fù)雜問題方面，特別是離散問

92、題方面表現(xiàn)出明顯的優(yōu)越性。已經(jīng)取得的成果表明該算法具有很大的發(fā)展空間。對(duì)于算法來況，在熟知其算法原理的前提下，更為重要的足為所要求解的問題建立一個(gè)數(shù)學(xué)模型，使算法對(duì)于問題的求解更加切實(shí)有效。在實(shí)際生產(chǎn)生活中，對(duì)于算法模型的收斂性和時(shí)間復(fù)雜度是值得我們深入研究和探討的問題。人工蜂群算法，作為全局隨機(jī)搜索算法，能夠以一定的概率避免陷入局部最優(yōu)。然而，針對(duì)復(fù)雜空間的全局搜索，無法避免地增加了時(shí)間復(fù)雜度，耗費(fèi)了大量時(shí)間。為了能夠更好、更快的找到

93、問題的最優(yōu)解，在算法進(jìn)行全局搜索的過程中，針對(duì)要解決的實(shí)際問題，加入局部搜索算法也是很好的思想。利用算法的全局性搜索防止陷入局部最優(yōu)，利用局部搜索來加快算法的收斂速度，降低時(shí)間復(fù)雜度，如何能更好的將二者完美的結(jié)合在一起，是值得我們進(jìn)一步研究的問題。另外，本文算法如果能和其他啟發(fā)式仿生算法結(jié)合，形成混合智能算法，也是值得研究的問題。</p><p>　　群體智能算法本質(zhì)上是一種模擬進(jìn)化算法，其產(chǎn)生、應(yīng)用和發(fā)展的過程

94、與進(jìn)化算法相輔相成，息息相關(guān)。在群體智能模型中，如果能將算法和搜索策略結(jié)合應(yīng)用，且群體中個(gè)體問存在信息交換，則在群智能算法中可以體現(xiàn)出進(jìn)化算法的優(yōu)越性：首先，在進(jìn)化算法的整個(gè)搜索過程中，不容易陷入局部最優(yōu)，即使在所定義的適應(yīng)函數(shù)是不連續(xù)的、非規(guī)則的或有噪聲的情況下，它們也能以很大的概率找到全局最優(yōu)解；其次，由于它固有的內(nèi)存并行性，非常適合并行計(jì)算；再次，進(jìn)化算法采用自然界的生物進(jìn)化機(jī)制表現(xiàn)出復(fù)雜的現(xiàn)緣，因此能夠迅速、穩(wěn)定的解決高難度的問

95、題。因此，它容易混合到已有的模型中，可擴(kuò)展性很好，又因?yàn)榫哂幸着c別的技術(shù)融合的特點(diǎn)，進(jìn)化算法已普遍應(yīng)用到優(yōu)化等相關(guān)領(lǐng)域。</p><p>　　本文主要講述人工蜂群算法，并利用此算法解決函數(shù)優(yōu)化問題，總結(jié)了解決函數(shù)優(yōu)化的框架，并驗(yàn)證。具有一定的推廣價(jià)值。</p><p>　　目前，關(guān)于群體智能的研究還處于一個(gè)開始階段，依然存在著很多的懸而術(shù)決的問題，但需要指出的是，人工蜂群算法和微粒群算法均

96、屬于概率算法，從數(shù)學(xué)上對(duì)其正確性和穩(wěn)定性的證明是比較困難的，而且算法在解決問題的過程中，整個(gè)系統(tǒng)的整體智能行為是通過低層次的個(gè)體與個(gè)體之問的信息交互來體現(xiàn)的。單個(gè)簡(jiǎn)單的個(gè)體組成的群體并不意味著也簡(jiǎn)單，設(shè)計(jì)者必須能夠?qū)⒏邔哟蔚膹?fù)雜行為(也就是系統(tǒng)所要完成的功能，例如背包問題、車間調(diào)度問題、旅行商等)映射到低層次(例如個(gè)體信息的交互)上面， 而這二者又是存在較大差別的。</p><p>　　本文存在管不足之處是蜂群中