【文章內(nèi)容簡介】 應(yīng)值并進(jìn)行比較大小，取最優(yōu)的人工魚狀態(tài)及其值賦給公告板。Step3 (行為選擇)各個人工魚分別模擬追尾行為和聚群行為，通過比較適應(yīng)值選擇最佳行為來執(zhí)行，缺省行為為覓食行為。Step4 (更新公告板)每條人工 魚對自身的適應(yīng)值和公告板的值進(jìn)行比較，如優(yōu)于公告板的值則取代之，否則公告板的值不變。Step5：(終止條件判斷)當(dāng)公告板上的最優(yōu)解達(dá)到了滿意的誤差界內(nèi)時，算法結(jié)束，輸出最優(yōu)解，否則轉(zhuǎn)step3。 人工蜂群算法及其模型 自然界中的蜂群總是能很快的找到優(yōu)良的蜜源或花粉，通過這些發(fā)現(xiàn)，2005年，Karaboga等提出了人工蜂群算法。人工蜂群算法是模仿蜜蜂行為從而提出的一種優(yōu)化方法，是集群智能思想的一個具體應(yīng)用，它的主要特點是不需要了解問題的特殊信息，只需要對問題進(jìn)行優(yōu)劣的比較，通過各人工蜂個體的局部尋優(yōu)行為，最終在群體中使全局最優(yōu)值突現(xiàn)出來，有著較快的收斂速度。 人工蜂群算法原理及數(shù)學(xué)模型在ABC算法中有3個重要的基本部分：食物源、人工蜂群、算法過程。（1） 食物源。不同的食物源代表了各種可能的解，且食物源的值由多種因素決定， 比如蜜源和蜂巢的距離、能量的大小和集中程度以及采取該食物的容易程度等，所以每個食物源都包含了一系列的可優(yōu)化參數(shù)。但為了算法的簡單分析起見，算法中僅僅將食物源的“質(zhì)量”作為衡量的標(biāo)準(zhǔn)。（2） 人工蜂群。人工蜂群包含三種蜜蜂：引領(lǐng)蜂、跟隨蜂以及偵察蜂。引領(lǐng)蜂先出去尋找食物源；跟隨蜂在舞蹈區(qū)等待引領(lǐng)蜂帶回食物源的相關(guān)信息，并且根據(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ù)都是隨機選取的，Rij是一個在1和1之間的隨機數(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ù)都是隨機選取的，Rij是一個在1和1之間的隨機數(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)度值；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≠iStep6 如果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 + 1Step12 cycle cycle + 1Step13 如果 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。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)，使用獨特的人工魚視域以及人工魚覓食行為，使得人工魚在VRP問題上更快的向最優(yōu)解靠近。 人工魚群算法的傳統(tǒng)處理方法 初始化種群每個種群的狀態(tài)描述運用一個二維數(shù)組x[Food_Number][Client_Number]，F(xiàn)ood_Number表示種群的個數(shù)（人工魚或者跟隨蜂的個數(shù)），Client_Number表示需要運送站點的個數(shù)，x[i][j]表示第i條人工魚（跟隨蜂）第j個需要送貨的站點（為了方便研究，我們令站點的取值分別為1～Client_Number的正整數(shù)），例如1表示1號站點，2表示2號站點…Client_Number表示Client_Number號站點。這樣就確定了貨車依次需要進(jìn)過的站點，再根據(jù)貨車的載重量就可以確定車輛的配送路徑。例如數(shù)組x[Food_Number][Client_Number]（設(shè)Food_Number=4，Client_Number=5）為：3 2 4 1 51 4 3 2 52 5 1 4 31 3 5 4 2該數(shù)組表示的含義為：⑴第0個種群（由于本文中的變量是基于C語言中的二維數(shù)組結(jié)構(gòu)存儲的，所以數(shù)組的下標(biāo)是從0開始的）依次需要經(jīng)過的站點為3 2 4 1 5⑵第1個種群依次需要經(jīng)過的站點為1 4 3 2 5⑶第2個種群依次需要經(jīng)過的站點為2 5 1 4 3⑷第3個種群依次需要經(jīng)過的站點為1 3 5 4 2根據(jù)上面對變量意義的描述可以看出，對于x[Food_Number][Client_Number]數(shù)組有如下2個特點：從橫向看，每個數(shù)的取值都是在1～Client_Number的正整數(shù)，并且互不相同；從全局看，每一行的數(shù)不能與其他行的數(shù)完全一樣，至少有兩個數(shù)是不同的，這是因為不同的種群不能產(chǎn)生同樣的解，否則就會造成種群個數(shù)的浪費或者種群過于擁擠。通過上述的特點，本文對每個種群的初始化采用如下策略：（1）隨機的生成一組1～Client_Number這Client_Number個正整數(shù)的排列，將該排列賦給種群；（2）確保每個種群的值是不同，否則從新生成新的排列。生成的種群的解并不是貨車的路徑，僅僅是貨車需要依次經(jīng)過的站點，因為在設(shè)計貨車的路徑是我們還需要考慮貨車的載重量這個參數(shù)。例如，假設(shè)貨車的載重量為1，weight[Client_Number]={,}為1～Client_Number號站點依次需要貨物的重量。第1個種群依次需要經(jīng)過的站點為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è)定，但是一定要保證充分大），加入計算中是為了使得所求食物濃度盡量小時，首先考慮滿足車輛要求的條件。（2）實際距離的計算，則需要知道distance[Client_Number+1][Client_Number+1]的值，distance[i][j]表示的是從站點i到站點j的距離，當(dāng)i或j為0時，則表示到貨物的倉庫的距離。 人工魚行為的設(shè)計（1）感知能力設(shè)計人工魚的感知能力是它感知其他伙伴的狀態(tài)和周圍環(huán)境的保證，它的感知能力設(shè)計為有限的（在visual范圍內(nèi)，只有和魚的距離不大于visual時才能被感知），符合現(xiàn)實中的魚的實際情況，也從一定程度上降低了人工魚行為的復(fù)雜度。這樣我們就必須解決兩條人工魚之間的距離d，對于距離問題的計算，傳統(tǒng)的方法采取計算兩個變量取值的相似程度的做法。對于任意的兩個變量數(shù)組，將數(shù)組中每個存儲位置的值進(jìn)行比較，如果兩者不相等，則取值為1，否則取值為0。最后將所有位置比較后的值相加就是兩條魚之間的距離d（x[m],x[n]分別表示第m條和第n條人工魚）的取值。用數(shù)學(xué)語言描述如下： 1 x[m][j] ≠ x[n][j]= 0 x[m][j] = x[n][j] 其中C表示Client_Number，j表示人工魚的第j個參數(shù)。從變量意義的描述中可以看出，變量中存儲的每個數(shù)值都不具有數(shù)值的真正含義，僅僅表示一個符號而已。因此用平常的歐氏距離明顯是不合適的，因為那樣得出的距離是毫無意義的，而