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