【正文】 中心位置方向前進(jìn)一步，達(dá)到狀態(tài) Xi(t+1)： xij(t+1)=xij(t)+rand()?Step?(xcj(t)xij(t))/|| Xc(t) Xi(t)|| (j=1,2,…, D) 結(jié)束。 Step5 在感知范圍內(nèi)隨機(jī)移動(dòng)一步，達(dá)到狀態(tài) Xi(t+1)： xij(t+1)=xij(t)+rand()?Step (j=1,2,…, D)結(jié)束。 (1)覓食行為 覓食行為是魚(yú)循著食物多的 方向游動(dòng)的一種行為。人工魚(yú)整個(gè)尋優(yōu)過(guò)程中充分利用自身信息和環(huán)境信息來(lái)調(diào)整自身的搜索方向，從而最終搜索達(dá)到食物濃度最高的地方，即全局極植。算法的進(jìn)行就是人工魚(yú)個(gè)體的自適應(yīng)活動(dòng)過(guò)程，整個(gè)過(guò)程包括覓食、聚群以及追尾三種行為，最優(yōu)解將在該過(guò)程中突現(xiàn)出來(lái)。 (4)隨機(jī)行為：魚(yú)在水 中悠閑的自由游動(dòng)，基本上是隨機(jī)的，其實(shí)它們也是為了更大范圍的尋覓食物或同伴。這是生物的一種最基本的行為，是通過(guò)感知水中的食物量或濃度來(lái)選擇趨向的。 人工魚(yú)群算法原理 人工魚(yú)群算法是一種基于動(dòng)物行為的自治體尋優(yōu)模式。229。 1 , 2 , ,nnnij ijki j kni k iimkiknijk kii =1nijk kijzkmin= , j = 1, 2, , n。 k=1,2,… ,m） 。 用 M 表示決策變量的定義域， G 表示問(wèn)題的可行域， g 表示目標(biāo)函數(shù)， x*為滿足條件的可行解，故該問(wèn)題解的數(shù)學(xué)模型如下： g(x*)=min{g(x*)|x*?G} G={x*|x*?M and h(x*)? 0} 車(chē)輛調(diào)度問(wèn)題的數(shù)學(xué)模型 將一般車(chē)輛的優(yōu)化調(diào)度問(wèn)題 （ VRP） 進(jìn)行如下描述：從某個(gè)物流配送中心（設(shè)其編號(hào)為 0）使用 m 輛貨車(chē)向 n 個(gè)貨物需要點(diǎn)配送貨物（編號(hào)依次為 1,2， … ， n）為第 i 個(gè)客戶的貨物需求量，其中這些貨車(chē)具有相同的載重量 qmax，配送中心和各需求點(diǎn)的位置事先已經(jīng)確定 ， dij（ i=0, 1, 2, ? ,n； j=0,1,2,…， n）為點(diǎn) i 和點(diǎn)j 之間的運(yùn)輸距離，要求配送的車(chē)輛均從配送中心出發(fā)，完成 貨物運(yùn)送任務(wù)后返回配送中心。 所以本文將蜂群和魚(yú)群的特點(diǎn)結(jié)合起來(lái)，開(kāi)始使用 蜂 群算法 能夠全局搜索解 ，然后使用 魚(yú) 群個(gè)體的 聚群、追尾等群體行為進(jìn)行搜索 ，使得全局最優(yōu)值能夠突現(xiàn)出來(lái)，達(dá)到快速收斂的目的。 我國(guó)李曉磊博士于 2021 年提出的一種人工智能算法即人工魚(yú)群算法 [89]，該算法具有 快速的收斂能力 ，能夠較好地 克服局部極值，并且算法對(duì)參數(shù)選擇以及初值不敏感，對(duì)搜索空間也就有一定的自適應(yīng)能力，是一種高效、并行、自適應(yīng)的全局搜索算法，特別適合于解決組合優(yōu)化領(lǐng)域的問(wèn)題，所以應(yīng)用該算法來(lái)求解車(chē)輛調(diào)度問(wèn)題是個(gè)不錯(cuò)的選擇。而且合理的運(yùn)送路線可以減少物流配送的運(yùn)輸費(fèi)用，從而使得 零售商的利潤(rùn)最大化。每次迭代過(guò)程中將最好的解都放在公告欄上，迭代完成以后那么公告欄上的解即為整個(gè)搜索過(guò)程中得到的最優(yōu)解。本論文中主要討論的是人工蜂群算法和人工魚(yú)群算法，并將這兩種進(jìn)行融合得到新的混合人工智能算法以解決 VRP 問(wèn)題。 因此，配送中心作業(yè)的重點(diǎn)就是如何將車(chē)輛有效的使用，并決定最經(jīng)濟(jì)的行駛路線，使商品能在最短的時(shí)間內(nèi)送到各個(gè) 客戶 手中 。 8 致謝 ............................................. 錯(cuò)誤 !未定義書(shū)簽。 參考文獻(xiàn) ........................................... 錯(cuò)誤 !未定義書(shū)簽。 實(shí)際上上述物流配送問(wèn)題就是車(chē)輛路線問(wèn)題（ VRP， Vehicle Routing Problem），它是組合領(lǐng)域中非常著名的 NP 難題，近二十年來(lái)， VRP 都是一個(gè)非?；钴S的研究領(lǐng)域。 人工魚(yú)群算法在 VRP 問(wèn)題上傳統(tǒng)的處理方法存在一定的缺陷，本論文將會(huì)給予一定的修正。 混 合人工智能算法能夠克服人工魚(yú)群算法的早熟現(xiàn)象和人工蜂群算法的收斂度不高等缺點(diǎn)，在同樣的條件下混合人工智能算法獲得的解一般情況下比人工魚(yú)群算法和人工蜂群算法要更好。 上述物流配送問(wèn)題實(shí)際上就是車(chē)輛路線問(wèn)題（ VRP， Vehicle Routing Problem），它是組合領(lǐng)域中非常著名的 NP 難題，近二十年來(lái)， VRP 都是一個(gè)非常活躍的研究領(lǐng)域 [3]。 但是人工魚(yú)群算法也有自身的缺點(diǎn)，在計(jì)算早期表現(xiàn)的收斂速度較快，能夠迅速靠近最佳求解點(diǎn)，但是后期計(jì)算過(guò)程中該算法的收斂速度會(huì)降低很多，而且求解精度較低 [10]。 本文以 VRP 為基礎(chǔ)，通過(guò)建立該問(wèn)題的數(shù)學(xué)模型，設(shè)計(jì)具有良好的近似解和較高收斂速度的混合人工智能算法。該問(wèn)題的目標(biāo)是：在滿足車(chē)輛載重量約束和各需求點(diǎn)需求量的約束的情況下，盡量使用較少的車(chē)輛且使得車(chē)輛的運(yùn)輸距離最短。yki=1 表示車(chē)輛 k 經(jīng)過(guò)需求點(diǎn) i，其他情況則yki=0（ i=1,2,… ,n。 k = 1, 2, mi n k mdxg y qyyxyx= = =====?=== = =邋 ?229。LLLLLL 6 3 主要 人工智能 群算法研究 本章主要研究 人工魚(yú)群算法 和人工蜂群 算法 的基本原理、數(shù)學(xué)模型、算法實(shí)現(xiàn)等內(nèi)容 。 動(dòng)物自治體通常指自主機(jī)器人或動(dòng)物模擬實(shí)體，它主要是用來(lái)展示動(dòng)物在復(fù)雜多變的環(huán)境里面能夠自主的產(chǎn)生自適應(yīng)的智能行為的一種方式。 (2)聚群行為：指魚(yú)在游動(dòng)過(guò)程中趨于聚集在一起來(lái)尋覓食物（集體覓食）、躲避敵害的行為。隨機(jī)行為實(shí)際上是覓食行為的一種缺省。其中覓食行為是人工魚(yú)根據(jù)當(dāng)前自身的適應(yīng)值隨機(jī)游動(dòng)的行為，是一種個(gè)體極值尋優(yōu)過(guò)程，屬于自學(xué)習(xí)的 過(guò)程；而聚群和追尾行為則是人工魚(yú)與周?chē)h(huán)境交互過(guò)程。 人工魚(yú)群的數(shù)學(xué)模型 假設(shè)在一個(gè) D 維的目標(biāo)搜索空間中，有 N 條組成一個(gè)群體的人工魚(yú)，其中第 i 條人工魚(yú)： 位置向量 Xi=(xi1, xi2,…, xiD)， 位置的食物濃度 (目標(biāo)函數(shù)適 應(yīng)值 ) Yi=f(Xi)， 兩條人工魚(yú) Xi 與 Xj之間的距離表示為 ||XjXi||， ?表示擁擠度因子，代表某個(gè)位置附近的擁擠程度，以避免與臨近伙伴過(guò)于擁擠， Visual 表示人工魚(yú)的感知范圍，人工魚(yú)每次移動(dòng)都要觀測(cè)感知范圍內(nèi)的其它魚(yú)的運(yùn)動(dòng)情況及其適應(yīng)值，從而決定自己的運(yùn)動(dòng)方向。狀態(tài)為 Xi(t)的第 i 條人工魚(yú)的覓食行為計(jì)算過(guò)程為： Step1 置 k=1。其中 rand()是 [0,1]內(nèi)的隨機(jī)數(shù)。 Step4 執(zhí)行覓食行為。 Step4 執(zhí)行覓食行為。常用的方法有兩種： ① （進(jìn)步即可原則）先進(jìn)行追尾行為，如果沒(méi)有進(jìn)步則進(jìn)行聚群行為，如果依然沒(méi)有進(jìn)步則進(jìn)行覓食行為。對(duì)于此種方法，同樣的迭代步數(shù)下，尋優(yōu)效果會(huì)好一些，但計(jì)算量也會(huì)加大。 Step3 (行為選擇 )各個(gè)人工魚(yú)分別模擬追尾行為和聚群行為，通過(guò)比較適應(yīng)值選擇最佳行為來(lái)執(zhí)行，缺省行為為覓食行為。人工蜂群算法是模仿蜜蜂行為從而提出的一種優(yōu)化方法，是集群智能思想的一個(gè)具體應(yīng)用，它的主要特點(diǎn)是不需要了解問(wèn)題的特殊信息，只需要對(duì)問(wèn)題進(jìn)行優(yōu)劣的比 較，通過(guò)各人工蜂個(gè)體的局部尋優(yōu)行為，最終在群體中使全局 最優(yōu)值 突現(xiàn)出來(lái)，有著較快的收斂速度。但為了算法的簡(jiǎn)單分 10 析起見(jiàn) ，算法中僅僅將食物源的 “質(zhì)量 ”作為衡量的標(biāo)準(zhǔn)。 （ 3） 算法過(guò)程及數(shù)學(xué)模型 首先， ABC 算法生成含有 SN 個(gè)解（食物源）的初始種群。引領(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小。 跟隨蜂根據(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小。 12 4 人工魚(yú)群算法在 VRP 問(wèn)題上的改進(jìn) 人工魚(yú)群算法在 VRP 問(wèn)題上的傳統(tǒng)方法沒(méi)有考慮 VRP 問(wèn)題最優(yōu)解的結(jié)構(gòu)型問(wèn)題 ，僅僅只是單純的對(duì)解的結(jié)構(gòu)進(jìn)行離散化，所以在程序?qū)崿F(xiàn)的過(guò)程中并沒(méi)有表現(xiàn)人工魚(yú)群算法的優(yōu)勢(shì)，反而使得在求解的過(guò)程中對(duì)某些問(wèn)題的復(fù)雜處理造成求解時(shí)間過(guò)長(zhǎng)，使得我們一般錯(cuò)誤的認(rèn)為人工魚(yú)群算法不適合解決 VRP 問(wèn)題。 例如數(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 個(gè)種群（由于本文中的變量是基于 C 語(yǔ)言中的二維數(shù)組結(jié)構(gòu)存儲(chǔ)的，所以數(shù)組的下標(biāo)是從 0 開(kāi)始的）依次需要經(jīng)過(guò)的站點(diǎn)為 3 2 4 1 5 ⑵ 第 1 個(gè)種群依次需要經(jīng)過(guò)的站點(diǎn)為 1 4 3 2 5 ⑶ 第 2 個(gè)種群依次需要經(jīng)過(guò)的站點(diǎn)為 2 5 1 4 3 ⑷ 第 3 個(gè)種群依次需要經(jīng)過(guò)的站點(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ì)造成種群 13 個(gè)數(shù)的浪費(fèi)或者種群過(guò)于擁擠。第 1 個(gè)種群依次需要經(jīng)過(guò)的站點(diǎn)為 1 4 3 2 5，則通過(guò)上述的計(jì)算可得該貨車(chē)需要經(jīng)過(guò)的路徑為 0 1 4 0 3 2 0 5 0（ 0 表示貨物的倉(cāng)庫(kù)，貨車(chē)必須要從倉(cāng)庫(kù)出發(fā)，并且最終回到倉(cāng)庫(kù)） 。 （ 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ù)的距離。最后將所有位置比較后的值相加就是兩條魚(yú)之間的距離 d（ x[m],x[n]分別表示第 m 條和第 n 條人工魚(yú)）的取值。采用上述的距離計(jì)算方法簡(jiǎn)單易行，它是以方案的總體視角來(lái)考慮問(wèn)題的，比較兩個(gè)種群，計(jì)算它們的相似程度，取值越大就說(shuō)明這兩個(gè)種群相似程度越小，當(dāng)它大于所給的 visual 時(shí)，就認(rèn)為這兩個(gè)種群都是對(duì)方看不見(jiàn)的。如果強(qiáng)硬的設(shè)置出步長(zhǎng)并讓人工魚(yú)按照步長(zhǎng)行動(dòng)，會(huì)造成變量取值的混亂，反而對(duì)求解不是有利的。 在尋找 y 的過(guò)程中，主要采取的是首先將 x 內(nèi)任意（ Client_Numbervisual）個(gè)數(shù)保持不變賦給 y，然后將剩下的 visual 個(gè)數(shù)隨機(jī)的存放在 y 的空位置處，得到新的位置 y。這個(gè)過(guò)程中的重點(diǎn)是如何計(jì)算該中心狀態(tài)。但是使用上面的方法可能使得中心位置不符合變量定義原則，因此需要對(duì)它進(jìn)行修復(fù)， center[Client_Number]可能出現(xiàn)的問(wèn)題為：某個(gè)站點(diǎn)出 現(xiàn)在很多位置；某個(gè)站點(diǎn)沒(méi)有出現(xiàn)在任何位置。該行為的具體步驟如下：先進(jìn)行追尾行為，如果沒(méi)有進(jìn)步則進(jìn)行聚群行 為，如果依然沒(méi)有進(jìn)步則進(jìn)行覓食行為。 例如a[5]={1,2,3,4,5},b[5]={2,3,4,5,1},a 與 b 之間 傳統(tǒng)的距離為 5。 計(jì)算 a 與 b 之間基于相似片段的距離的 主要方法如下： Step1 初始化 count=0（記錄人工魚(yú)距離的長(zhǎng)度）， i=0（數(shù)組 a 的 起始位置） ,j=0； Step2 將 a[i]與 b 中的每個(gè)數(shù)進(jìn)行對(duì)比，當(dāng) a[i]==b[j]的時(shí)候， i++， j++； Step3 直到 a[i]!=b[j]的時(shí)候，或者 j 等于 D 的時(shí)候 count++； Step4 如果 i!=D，則轉(zhuǎn)到 Step2，否則 count++，結(jié)束 。 基于相似片段距離的 人工魚(yú)覓食行為具體方法如下： Step1 首先定義三種改變?nèi)斯~(yú)位置的方法，第一種交換任意兩個(gè)數(shù)之間的位置；第二種任意選擇一個(gè)數(shù)，當(dāng)這個(gè)數(shù)不是數(shù)組中第一個(gè)數(shù)時(shí)將其與它前面一個(gè)數(shù)交換位置 ，否則繼續(xù)選擇一個(gè)數(shù)；第三種任意選擇兩個(gè)數(shù)，將其中一個(gè)數(shù)插到另一個(gè)數(shù)的前面； Step2 隨機(jī)生成一個(gè)小于等于 5 的正整數(shù)數(shù)，當(dāng)這個(gè)等于 1,2,3 的時(shí)候，則分 17 別進(jìn)行第一種、第二種或者第三種方法來(lái)改變?nèi)斯~(yú)的位置，當(dāng)?shù)扔?4 或 5 時(shí)，則不進(jìn)行任何操作； Step3 將步驟 Step2 進(jìn)行 visual 次操作，當(dāng)?shù)玫叫碌娜斯~(yú)的位置優(yōu)于以前的位置時(shí)，則將人工魚(yú)向食物濃度更高的位置前進(jìn)一步； Step4 如果進(jìn)行 try_namber 次尋找的時(shí)候人工魚(yú)任然沒(méi)有找到食物濃度更好的位置，那么該人工魚(yú)最后進(jìn)行一次嘗試，不管該位置是否更優(yōu) 該人工魚(yú)都向其前進(jìn)一步。 以 19 個(gè)客戶的配送為題驗(yàn)證結(jié)果，設(shè)定中心位于坐標(biāo)（ 0,0）處，這 19 個(gè)客戶的位置分布 及需求量見(jiàn)表 41。 表 42 人工魚(yú)群算法參數(shù) 人工魚(yú)的數(shù)