【文章內(nèi)容簡介】 算法。人工蜂群算法是模仿蜜蜂行為從而提出的一種優(yōu)化方法，是集群智能思想的一個具體應(yīng)用，它的主要特點(diǎn)是不需要了解問題的特殊信息，只需要對問題進(jìn)行優(yōu)劣的比較，通過各人工蜂個體的局部尋優(yōu)行為，最終在群體中使全局 最優(yōu)值 突現(xiàn)出來，有著較快的收斂速度。 人工蜂群算法 原理及數(shù)學(xué)模型 在 ABC 算法中有 3 個重要的基本部分：食物源、人工蜂群、算法過程。 （ 1） 食物源。不同的食物源代表了各種可能的解，且食物源的值由多種因素決定， 比如蜜源和蜂巢的距離、能量的大小和集中程度以及采取該食物的容易程度等，所以每個食物源都包含了一系列的可優(yōu)化參數(shù)。但為了算法的簡單分 10 析起見，算法中僅僅將食物源的 “質(zhì)量 ”作為衡量的標(biāo)準(zhǔn)。 （ 2） 人工蜂群。人工蜂群包含三種蜜蜂：引領(lǐng)蜂、跟隨蜂以及偵察蜂。引領(lǐng)蜂先出去尋找食物源；跟隨蜂在舞蹈區(qū)等待引領(lǐng)蜂帶回食物源的相關(guān)信息，并且根據(jù)信息選擇食物源；偵查蜂則完全隨機(jī)的尋找新 的食物源，如果某個食物源被引領(lǐng)蜂和跟隨蜂丟棄，那么和這個食物源對應(yīng)的引領(lǐng)蜂就變成了偵查蜂。 （ 3） 算法過程及數(shù)學(xué)模型 首先， ABC 算法生成含有 SN 個解（食物源）的初始種群。每個解 xi(i=1,2,… ,D)是一個 D 維的向量。然后，蜜蜂對所有的食物源進(jìn)行循環(huán)搜索，循環(huán)次數(shù)為 MCN。 ① 引領(lǐng)蜂先對對應(yīng)的食物源（解）進(jìn)行一次領(lǐng)域搜索，并選擇花蜜數(shù)量多也就是適應(yīng)度較高的食物源（解）。引領(lǐng)蜂按照以下表達(dá)式進(jìn)行領(lǐng)域搜索： vij = xij + Rij(xij xkj) （ k ≠ i） k?{1,2,...,SN} , j?{1,2,...,D}， 這兩個數(shù)都是隨機(jī)選取的， Rij 是一個在 1 和 1 之間的隨機(jī)數(shù)，這個步長可以適當(dāng)?shù)臏p小。 ② 所有的引領(lǐng)蜂完成搜索之后，在舞蹈區(qū)把食物源的信息傳達(dá)給跟隨蜂，跟隨蜂根據(jù)得到的信息按照概率選擇食物源。在花蜜越多的食物源，被選 擇的概率越大。 跟隨蜂按照概率值 pi 選擇食物源，根據(jù)以下表達(dá)式計算： Pi = fi / ?j=0SNfj fi 是第 i 個解的適應(yīng)度值 ③ 隨后，跟隨蜂也進(jìn)行一次領(lǐng)域搜索，并選擇較好的解。 跟隨蜂根據(jù)以下表達(dá)式進(jìn)行領(lǐng)域搜索： vij = xij + Rij(xij xkj) （ k ≠ i） k?{1,2,...,SN} , j?{1,2,...,D}， 這兩個數(shù)都是隨機(jī)選取的， Rij 是一個在 1 和 1 之間的隨機(jī)數(shù)，這個步長可以適當(dāng)?shù)臏p小。 ④ 如果某個解經(jīng)過 limit 次循環(huán)后沒有得到改善，那么這個節(jié)就要被丟棄。假定被丟掉的解是 xi，那么就由偵查蜂按照以下表達(dá)式產(chǎn)生一個新的解來代替 xi： xij = xjmin + rand(0,1)(xjmax xjmin) 人工蜂群算法步驟 人工 蜂群算法的具體計算步驟為： 設(shè)定 3 個參數(shù)：食物源的個數(shù) =引領(lǐng)蜂的個數(shù) =跟隨 蜂 的個數(shù)（ SN）、領(lǐng)域搜索次數(shù) limit、最大循環(huán)次數(shù) MCN。算法步驟如下： Step1 產(chǎn)生初始解集 xij， i?{1,2,...,SN}， j?{1,2,...,D}； Step2 計算各個解 xij 的適應(yīng)度值； 11 Step3 置 cycle=1（外循環(huán)）； Step4 置 s=1（內(nèi)循環(huán)）； Step5 引領(lǐng)蜂根據(jù)如下公式做領(lǐng)域搜索產(chǎn)生新解 vij ，并計算其適應(yīng)度值： vij = xij + Rij(xij xkj) k?{1,2,...,SN} 且 k≠i Step6 如果 vij 的適應(yīng)度值大于 xij，則 xij=vij，否則 xij 不變； Step7 計算 xij 的適應(yīng)度，并根據(jù)如下公式計算概率值 Pi： Pi = fi / ?j=0SNfj Step8 跟隨蜂根據(jù) Pi 選擇食物源（解），并進(jìn)行領(lǐng)域搜索產(chǎn)生新解 vij，計算其適應(yīng)度； Step9 同步驟 6； Step10 記錄 到目前為止最好的解； Step11 s = s + 1 Step12 cycle cycle + 1 Step13 如果 s limit ， 則轉(zhuǎn)步驟 5； Step14 經(jīng)過 limit 次循環(huán)后，判斷是否有要丟棄的解，如果存在，則偵查蜂根據(jù)如下公式產(chǎn)生一個新解 xij 代替： xij = xjmin + rand(0,1)(xjmax xjmin) Step15 如果 cycle MCN （最大循環(huán)次數(shù)），則轉(zhuǎn)步驟 Step4。 12 4 人工魚群算法在 VRP 問題上的改進(jìn) 人工魚群 算法在 VRP 問題上的傳統(tǒng)方法沒有考慮 VRP 問題最優(yōu)解的結(jié)構(gòu)型問題，僅僅只是單純的對解的結(jié)構(gòu)進(jìn)行離散化，所以在程序?qū)崿F(xiàn)的過程中并沒有表現(xiàn)人工魚群算法的優(yōu)勢，反而使得在求解的過程中對某些問題的復(fù)雜處理造成求解時間過長，使得我們一般錯誤的認(rèn)為人工魚群算法不適合解決 VRP 問題。由于上述一些原因，本論文對傳統(tǒng)的方法加以改進(jìn)，使用獨(dú)特的人工魚視域以及人工魚覓食行為，使得人工魚在 VRP 問題上更快的向最優(yōu)解靠近。 人工魚群算法的傳統(tǒng)處理方法 初始化種群 每個種群的狀態(tài)描述運(yùn)用一個二維數(shù)組 x[Food_Number][Client_Number]，F(xiàn)ood_Number 表示種群的個數(shù)（人工魚或者跟隨蜂的個數(shù)）， Client_Number 表示需要運(yùn)送站點(diǎn)的個數(shù)， x[i][j]表示第 i 條人工魚（跟隨蜂）第 j 個需要送貨的站點(diǎn)（為了方便研究，我們令站點(diǎn)的取值分別為 1～ Client_Number 的正整數(shù)），例如1 表示 1 號站點(diǎn)， 2 表示 2 號站點(diǎn) … Client_Number 表示 Client_Number 號站點(diǎn)。這樣就確定了貨車依次需要進(jìn)過的站點(diǎn)，再根據(jù)貨車的載重量就可以確定車輛的配送路徑。 例如數(shù)組 x[Food_Number][Client_Number] （設(shè) Food_Number=4 ，Client_Number=5）為： 3 2 4 1 5 1 4 3 2 5 2 5 1 4 3 1 3 5 4 2 該數(shù)組表示的含義為： ⑴ 第 0 個種群（由于本文中的變量是基于 C 語言中的二維數(shù)組結(jié)構(gòu)存儲的，所以數(shù)組的下標(biāo)是從 0 開始的）依次需要經(jīng)過的站點(diǎn)為 3 2 4 1 5 ⑵ 第 1 個種群依次需要經(jīng)過的站點(diǎn)為 1 4 3 2 5 ⑶ 第 2 個種群依次需要經(jīng)過的站點(diǎn)為 2 5 1 4 3 ⑷ 第 3 個種群依次需要經(jīng)過的站點(diǎn)為 1 3 5 4 2 根據(jù)上面對變量意義的描述可以看出，對于 x[Food_Number][Client_Number]數(shù)組有如下 2 個特點(diǎn)：從橫向看，每個數(shù)的取值都是在 1～ Client_Number 的正整數(shù)，并且互不相同；從全 局看，每一行的數(shù)不能與其他行的數(shù)完全一樣，至少有兩個數(shù)是不同的，這是因?yàn)椴煌姆N群不能產(chǎn)生同樣的解，否則就會造成種群 13 個數(shù)的浪費(fèi)或者種群過于擁擠。 通過上述的特點(diǎn)，本文對每個種群的初始化采用如下策略： （ 1） 隨機(jī)的生成一組 1～ Client_Number 這 Client_Number 個正整數(shù)的排列，將該排列賦給種群； （ 2） 確保每個種群的值是不同，否則從新生成新的排列。 生成的種群的解并不是貨車的路徑，僅僅是貨車需要依次經(jīng)過的站點(diǎn)，因?yàn)樵谠O(shè)計貨車的路徑是我們還需要考慮貨車的載重量這個參數(shù)。例如，假設(shè)貨車的載重量為 1， weight[Client_Number]={,}為 1～ Client_Number 號站點(diǎn)依次需要貨物的重量。第 1 個種群依次需要經(jīng)過的站點(diǎn)為 1 4 3 2 5，則通過上述的計算可得該貨車需要經(jīng)過的路徑為 0 1 4 0 3 2 0 5 0（ 0 表示貨物的倉庫，貨車必須要從倉庫出發(fā)，并且最終回到倉庫） 。 食物濃度的計算 食物濃度是指模型中的目標(biāo)函數(shù)值，用來衡量種群當(dāng)前狀態(tài)的優(yōu)劣程度。每個種群每次迭代后所在狀態(tài)的食物濃度計算就是 VRP 問題的目 標(biāo)函數(shù)值的計算問題，它是判斷狀態(tài)優(yōu)劣的標(biāo)準(zhǔn)。該食物濃度的計算如 VRP 模型由兩部分組成為： （ 1） 判斷未達(dá)到滿載率要求的車輛數(shù)目是否超過規(guī)定的車輛數(shù)目，如果超過則將之乘以一個很大的權(quán)數(shù) 100000（該可以根據(jù)實(shí)際情況設(shè)定，但是一定要保證充分大），加入計算中是為了使得所求食物濃度盡量小時，首先考慮滿足車輛要求的條件。 （ 2） 實(shí)際距離的計算，則需要知道distance[Client_Number+1][Client_Number+1]的值， distance[i][j]表示的是從站點(diǎn) i到站點(diǎn) j 的距離，當(dāng) i 或 j 為 0 時 ，則表示到貨物的倉庫的距離。 人工魚行為的設(shè)計 （ 1） 感知能力設(shè)計 人工魚的感知能力是它感知其他伙伴的狀態(tài)和周圍環(huán)境的保證，它的感知能力設(shè)計為有限的（在 visual 范圍內(nèi)，只有和魚的距離不大于 visual 時才能被感知），符合現(xiàn)實(shí)中的魚的實(shí)際情況，也從一定程度上降低了人工魚行為的復(fù)雜度。這樣我們就必須解決兩條人工魚之間的距離 d，對于距離問題的計算，傳統(tǒng)的方法采取計算兩個變量取值的相似程度的做法。 對于任意的兩個變量數(shù)組，將數(shù)組中每個存儲位置的值進(jìn)行比較，如果兩者不相等，則取值為 1，否則取值為 0。最 后將所有位置比較后的值相加就是兩條魚之間的距離 d（ x[m],x[n]分別表示第 m 條和第 n 條人工魚）的取值。用數(shù)學(xué)語 14 言描述如下： 1 x[m][j] ≠ x[n][j] ej = 0 x[m][j] = x[n][j] ???Cjeojd 其中 C 表示 Client_Number， j 表示人工魚的第 j 個參數(shù)。從變量意義的描述中可以看出，變量中存儲的每個數(shù)值都不具有數(shù)值的真正含義，僅僅表示一個符號而已。因此用平常的歐氏距離明顯是不合適的，因?yàn)槟菢拥贸龅木嚯x是毫無意義的，而且對不能真正體現(xiàn)人工魚視覺的意義。采用上述的距離計算方法簡單易行，它是以方案的總體視角來考慮問題的，比較兩個種群，計算它們的相似程度，取值越大就說明這兩個種群相似程度越小，當(dāng)它大于所給的 visual 時，就認(rèn)為這兩個種群都是對方看不見的。對于兩個種群的距離運(yùn)算中，最壞的情況是兩種種群里面的 值完全是不同的，這是他們之間的距離就是 2*Client_Number。 （ 2） 覓食行為 從 VRP 問題可以看出，每個變量都是一種可行的解決方案，它的解集空間是不連續(xù)的，而是很多離散的點(diǎn)，并且變量中每個分量的取值都不具有數(shù)值含義。所以步長的設(shè)計對于該問題的意義就不大。如果強(qiáng)硬的設(shè)置出步長并讓人工魚按照步長行動，會造成變量取值的混亂，反而對求解不是有利的。 基于上面的考慮，對于每個種群的行動采取讓人工魚直接跳向更優(yōu)狀態(tài)的策略，這樣會使問題變得更加簡單易行，而且收效也很好。執(zhí)行覓食行為的過程可以描述為：首先，對于任 意的一條人工魚，設(shè)其現(xiàn)在的狀態(tài)為 x，在其視野范圍內(nèi)任意找到一點(diǎn) y，采用如下方法： ① 保證 y 在 x 的視野范圍內(nèi)。使得兩條人工魚之間的距離 dvisual ② 保證 y 的任意性，并符合變量的定義規(guī)則。 在尋找 y 的過程中，主要采取的是首先將 x 內(nèi)任意（ Client_Numbervisual）個數(shù)保持不變賦給 y，然后將剩下的 visual 個數(shù)隨機(jī)的存放在 y 的空位置處，得到新的位置 y。 得到 y 后就進(jìn)一步判斷 該點(diǎn)的食物濃度是否更優(yōu)，如果是則跳向它。如果并沒有在視野內(nèi)找到更好的狀態(tài)則繼續(xù)掃描，這樣尋優(yōu)會持續(xù) try_number 次；如果經(jīng)過 try_number 后還沒有找到一個更優(yōu)的狀態(tài)，就采取隨機(jī)行為。 （ 3） 聚群行為 聚群行為實(shí)現(xiàn)過程是首先找到視野范圍內(nèi)的其他人工魚，將它們的狀態(tài)存在 15 friendflag[index][i]（其中 index 表示這條人工的編號， i 表示第 i 條人工，這個數(shù)組存儲的值為 bool 型， true 表示在該魚的視野范圍內(nèi)， false 則表示不在其的視野范圍內(nèi)）中，然后計算出這些人工魚的中心位置，在判斷 這一中心是否優(yōu)于人工魚的當(dāng)前的狀態(tài)，如果比當(dāng)前的狀態(tài)優(yōu)而且周圍并不擁擠，該人工魚就跳向中心，否則就保持原來的狀態(tài)不變。這個過程中的重點(diǎn)是如何計算該中心狀態(tài)。 中心狀態(tài)根據(jù) x[Food_Number][Client_Number]矩陣得出，設(shè)中心點(diǎn)的坐標(biāo)為center[Client_Number]={0}(初始化 )，對于矩陣的計算是 :首先標(biāo)記出人工魚 index的視野范圍內(nèi)的人工魚，將 friendflag[index][Food_Number]內(nèi)的在范圍內(nèi)的人工魚標(biāo)號為 true。計算這個魚群中第 1 個經(jīng)過站點(diǎn)的標(biāo) 號（ a[x[j][1]]++，其中 j 表示在該魚群中第 j 條人工魚， a[x[j][1]]表示存儲第一次經(jīng)過某個標(biāo)號的次數(shù)），通過 a[x