【正文】 的收斂能力 ，能夠較好地 克服局部極值，并且算法對參數(shù)選擇以及初值不敏感，對搜索空間也就有一定的自適應(yīng)能力，是一種高效、并行、自適應(yīng)的全局搜索算法，特別適合于解決組合優(yōu)化領(lǐng)域的問題，所以應(yīng)用該算法來求解車輛調(diào)度問題是個不錯的選擇。 但是人工魚群算法也有自身的缺點(diǎn)，在計算早期表現(xiàn)的收斂速度較快，能夠迅速靠近最佳求解點(diǎn)，但是后期計算過程中該算法的收斂速度會降低很多，而且求解精度較低 [10]。 人工蜂群算法是 2021年由土耳其學(xué)者 KaraBoga[11]提出的模擬蜜蜂群體尋找優(yōu)質(zhì)蜜源的一種動物仿真的智能算法，是群體智能思想的應(yīng)用。它的主要 特點(diǎn)是不需要了解問題的特殊信息，只需要對問題進(jìn)行優(yōu)劣的比較，通過各人工蜂個體的局部尋優(yōu)行為，最終在群體中使全局最優(yōu)值突現(xiàn)出來， 能避免解的早熟現(xiàn)象 ， 但是人工蜂群算法 收斂速度不快 。 所以本文將蜂群和魚群的特點(diǎn)結(jié)合起來，開始使用 蜂 群算法 能夠全局搜索解 ，然后使用 魚 群個體的 聚群、追尾等群體行為進(jìn)行搜索 ，使得全局最優(yōu)值能夠突現(xiàn)出來，達(dá)到快速收斂的目的。 本文以 VRP 為基礎(chǔ)，通過建立該問題的數(shù)學(xué)模型，設(shè)計具有良好的近似解和較高收斂速度的混合人工智能算法。為了研究方便起見，本文假設(shè)不存在某客戶的需求量超過一個貨車載重量的 情況，并且所有車輛的載重量相同，同時不考慮時間窗約束，僅僅將車輛的最短行駛距離作為目標(biāo)函數(shù)。 4 2 車輛優(yōu)化調(diào)度問題的描述 組合優(yōu)化問題的描述 為了滿足一般性，對求解最小化問題進(jìn)行描述，其數(shù)學(xué)模型如下所示： min g(x) . h(x)? 0 x?M 上述公式中， x 為決策變量， g(x)為需要求解的最小化目標(biāo)函數(shù)， h(x)為約束函數(shù)即需要滿足的條件， M 為有限個點(diǎn)的組合集合。 用 M 表示決策變量的定義域， G 表示問題的可行域， g 表示目標(biāo)函數(shù)， x*為滿足條件的可行解，故該問題解的數(shù)學(xué)模型如下： g(x*)=min{g(x*)|x*?G} G={x*|x*?M and h(x*)? 0} 車輛調(diào)度問題的數(shù)學(xué)模型 將一般車輛的優(yōu)化調(diào)度問題 （ VRP） 進(jìn)行如下描述：從某個物流配送中心（設(shè)其編號為 0）使用 m 輛貨車向 n 個貨物需要點(diǎn)配送貨物（編號依次為 1,2， … ， n）為第 i 個客戶的貨物需求量，其中這些貨車具有相同的載重量 qmax，配送中心和各需求點(diǎn)的位置事先已經(jīng)確定 ， dij（ i=0, 1, 2, ? ,n； j=0,1,2,…， n）為點(diǎn) i 和點(diǎn)j 之間的運(yùn)輸距離，要求配送的車輛均從配送中心出發(fā)，完成 貨物運(yùn)送任務(wù)后返回配送中心。該問題的目標(biāo)是：在滿足車輛載重量約束和各需求點(diǎn)需求量的約束的情況下，盡量使用較少的車輛且使得車輛的運(yùn)輸距離最短。 VRP 的解 必須滿足 以 下條件： （ 1） 每個需求點(diǎn)的需求量均小于或等于配送貨車的載重量； （ 2） 客戶的需求必須得到滿足，且每個需求點(diǎn)只能由一輛貨車一次運(yùn)送完成 ； （ 3） 運(yùn)送完后，貨車必須要回到配送中心 。 若客戶 i 的需求由車輛 k 完成，則 yij 的 值為 1，否則則為 0； 若車輛 k 從貨物需求點(diǎn) i 行駛到需求點(diǎn) j，則 xijk 的值為 1，否則則為 0. VRP 的數(shù)學(xué)模型如下： 5 xijk=1 表示車輛 k 從貨物需求 點(diǎn) i 行駛到需求點(diǎn) j， 其他情況則 xijk=0（ i or j=1,2,… ,n。 k=1,2,… ,m） 。yki=1 表示車輛 k 經(jīng)過需求點(diǎn) i，其他情況則yki=0（ i=1,2,… ,n。 k=1,2,… ,m）。 0 0 0m a x110, 1 , 2 , ,1 , 1 , 2 , , 1 , 2 , , 。 1 , 2 , ,nnnij ijki j kni k iimkiknijk kii =1nijk kijzkmin= , j = 1, 2, , n。 k = 1, 2, mi n k mdxg y qyyxyx= = =====?=== = =邋 ?229。229。229。229。LLLLLL 6 3 主要 人工智能 群算法研究 本章主要研究 人工魚群算法 和人工蜂群 算法 的基本原理、數(shù)學(xué)模型、算法實(shí)現(xiàn)等內(nèi)容 。 人工魚群算法原理及其模型 人工魚群算法由李曉磊等人采用自下而上的尋優(yōu)模式在 2021 年提出。該 算法模仿自然界魚群覓食行為，主要以魚的覓食、聚群和追尾行為構(gòu)造個體的底層行為；通過魚群中各個體的局部尋優(yōu)，達(dá)到全局最優(yōu)值在群體中突現(xiàn)出來的目的。 人工魚群算法原理 人工魚群算法是一種基于動物行為的自治體尋優(yōu)模式。 動物自治體通常指自主機(jī)器人或動物模擬實(shí)體，它主要是用來展示動物在復(fù)雜多變的環(huán)境里面能夠自主的產(chǎn)生自適應(yīng)的智能行為的一種方式。魚類生活習(xí)性具有以下幾種典型行為： (1)覓食行為：指魚通過味覺、視覺來判斷食物的位置和濃度，從而接近食物的行為。一般情況下，魚在水中隨機(jī)的自由游動，當(dāng)發(fā)現(xiàn)食物時 ，則會向著食物逐漸增多的方向快速游去。這是生物的一種最基本的行為，是通過感知水中的食物量或濃度來選擇趨向的。 (2)聚群行為：指魚在游動過程中趨于聚集在一起來尋覓食物（集體覓食）、躲避敵害的行為。這是魚類較常見的一種現(xiàn)象，魚聚群時所遵守的規(guī)則有三條： ① 分隔規(guī)則：盡量避免與臨近伙伴過于擁擠： ② 對準(zhǔn)規(guī)則：盡量與臨近伙伴的平均方向一致； ③ 內(nèi)聚規(guī)則：盡量向臨近伙伴的中心移動。 (3)追尾行為：當(dāng)某一條魚或幾條魚發(fā)現(xiàn)食物時，它們附近的魚會尾隨其后快速游過來，進(jìn)而導(dǎo)致更遠(yuǎn)處的魚也尾隨過來。 (4)隨機(jī)行為：魚在水 中悠閑的自由游動，基本上是隨機(jī)的，其實(shí)它們也是為了更大范圍的尋覓食物或同伴。隨機(jī)行為實(shí)際上是覓食行為的一種缺省。 每條人工魚通過對環(huán)境的感知，在每次移動中經(jīng)過嘗試后，執(zhí)行其中的一種行為。人工魚群算法就是利用這幾種典型行為從構(gòu)造單條魚底層行為做起，通過魚群中各個體的局部尋優(yōu)達(dá)到全局最優(yōu)值在群體中突現(xiàn)出來的目的。算法的進(jìn)行就是人工魚個體的自適應(yīng)活動過程，整個過程包括覓食、聚群以及追尾三種行為，最優(yōu)解將在該過程中突現(xiàn)出來。其中覓食行為是人工魚根據(jù)當(dāng)前自身的適應(yīng)值隨機(jī)游動的行為，是一種個體極值尋優(yōu)過程，屬于自學(xué)習(xí)的 過程；而聚群和追尾行為則是人工魚與周圍環(huán)境交互過程。這兩種過程是在保證不與伙伴過于擁擠，且 7 與臨近伙伴的平均移動方向一致的情況下向群體極值 (中心 )移動。由此可見，人工魚群算法也是一類基于群體智能的優(yōu)化方法。人工魚整個尋優(yōu)過程中充分利用自身信息和環(huán)境信息來調(diào)整自身的搜索方向，從而最終搜索達(dá)到食物濃度最高的地方，即全局極植。 人工魚群的數(shù)學(xué)模型 假設(shè)在一個 D 維的目標(biāo)搜索空間中，有 N 條組成一個群體的人工魚，其中第 i 條人工魚： 位置向量 Xi=(xi1, xi2,…, xiD)， 位置的食物濃度 (目標(biāo)函數(shù)適 應(yīng)值 ) Yi=f(Xi)， 兩條人工魚 Xi 與 Xj之間的距離表示為 ||XjXi||， ?表示擁擠度因子，代表某個位置附近的擁擠程度，以避免與臨近伙伴過于擁擠， Visual 表示人工魚的感知范圍，人工魚每次移動都要觀測感知范圍內(nèi)的其它魚的運(yùn)動情況及其適應(yīng)值，從而決定自己的運(yùn)動方向。 Step 表示人工魚每次移動的最大步長，為了防止運(yùn)動速度過快而錯過最優(yōu)解，步長不能設(shè)置的過大，當(dāng)然，太小的步長也不利于算法的收斂。 Try_number 表示人工魚在覓食過程中最大的試探次數(shù)。 (1)覓食行為 覓食行為是魚循著食物多的 方向游動的一種行為。狀態(tài)為 Xi(t)的第 i 條人工魚的覓食行為計算過程為： Step1 置 k=1。 Step2 在其感知范圍內(nèi)隨機(jī)選擇一個狀態(tài) Xv(t)： xvj(t)=xij(t)+rand()?Visual (j=1,2,…, D) Step3 若 Yv(t)?Yi(t)，則向該方向前進(jìn)一步，達(dá)到狀態(tài) Xi(t+1)： xij(t+1)=xij(t)+rand()?Step?(xvj(t)xij(t))/|| Xv(t) Xi(t)|| (j=1,2,…, D) 結(jié)束。 Step4 若 k=Try_number，則轉(zhuǎn) Step5；否則，置 k=k+1，轉(zhuǎn) Step2。 Step5 在感知范圍內(nèi)隨機(jī)移動一步，達(dá)到狀態(tài) Xi(t+1)： xij(t+1)=xij(t)+rand()?Step (j=1,2,…, D)結(jié)束。其中 rand()是 [0,1]內(nèi)的隨機(jī)數(shù)。 (2)聚群行為 聚群行為是每條魚在游動過程中盡量向臨近伙伴的中心移動并避免過分擁擠。狀態(tài)為 Xi(t)的第 i 條人工魚的聚群行為計算過程為： Step1 計算以自身位置為 中心其感知范圍內(nèi)的人工魚形成集合 Si： Si={Xj(t)||| Xj(t) Xi(t)||?Visual,j?i} 8 并計算 Si 中人工魚數(shù)目 Nf=|Si|。 Step2 若 Nf ?0，則計算該集合的中心位置 Xc(t)： Xc(t)=?(Xj(t)|j=1,2,…, Nf, Xj(t)?Si)/Nf Step3 若 Yc(t)?Yi(t)且 Nf ?Yc(t)???Yi(t) (??1)，（表明該中心位置狀態(tài)較優(yōu)并且不太擁擠）則向該中心位置方向前進(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é)束。 Step4 執(zhí)行覓食行為。 (3)追尾行為 追尾行為是魚向臨近的最活躍者追捉的行為。狀態(tài)為 Xi(t)的第 i 條人工魚的追尾行為計算過程為： Step1 計算以自身位置為中心其感知范圍內(nèi)的人工魚形成集合 Si： Si={Xj(t)||| Xj(t) Xi(t)||?Visual,j?i} 計算 Si 中人工魚數(shù)目 Nf=|Si|。 Step2 若 Nf ?0，則計算感知范圍內(nèi)的所有伙伴中適 應(yīng)值為最小的伙伴位置Xm(t)： Ym(t)=min{Yj(t)|Xj(t)?Si} Step3 若 Ym(t)?Yi(t)且 Nf ?Ym(t)???Yi(t) (??1)，（表明該位置狀態(tài)較優(yōu)并且不太擁擠）則向該位置方向前進(jìn)一步，達(dá)到狀態(tài) Xi(t+1)： xij(t+1)=xij(t)+rand()?Step?(xmj(t)xij(t))/|| Xm(t) Xi(t)|| (j=1,2,…, D) 結(jié)束。 Step4 執(zhí)行覓食行為。 (4)設(shè)立公告板 在人工魚群算法中，設(shè)置一個公告板，用以記錄當(dāng) 前搜索到的最優(yōu)人工魚狀態(tài)及對應(yīng)的適應(yīng)值，各條人工魚在每次行動后，將自身當(dāng)前狀態(tài)的適應(yīng)值與公告板進(jìn)行比較，如果優(yōu)于公告板，則用自身狀態(tài)及其適應(yīng)值取代公告板中的相應(yīng)值，以使公告板能夠記錄搜索到的最優(yōu)狀態(tài)及該狀態(tài)的適應(yīng)值。即算法結(jié)束時，最終公告板的值就是系統(tǒng)的最優(yōu)解。 (5)行為選擇（移動策略） 根據(jù)所要解決的問題性質(zhì)，對人工魚當(dāng)前所處的環(huán)境進(jìn)行評價，從上述各行為中選取一種合適的行為。常用的方法有兩種： ① （進(jìn)步即可原則）先進(jìn)行追尾行為，如果沒有進(jìn)步則進(jìn)行聚群行為，如果依然沒有進(jìn)步則進(jìn)行覓食行為。也就是選擇較優(yōu)行 為前進(jìn)，即任選一種行為，只要能向優(yōu)的方向前進(jìn)即可。 9 ② （進(jìn)步最快原則）試探執(zhí)行各種行為，選擇各行為中使得向最優(yōu)方向前進(jìn)最快的行為，即模擬執(zhí)行聚群、追尾等行為，然后選擇行動后狀態(tài)較優(yōu)的動作來實(shí)際執(zhí)行，缺省的行為方式為覓食行為。也就是選擇各行為中使得人工魚的下一個狀態(tài)最優(yōu)的行為，如果沒有能使下一狀態(tài)優(yōu)于當(dāng)前狀態(tài)的行為，則采取隨機(jī)行為。對于此種方法，同樣的迭代步數(shù)下，尋優(yōu)效果會好一些，但計算量也會加大。 人工魚群算法通過這些行為的選擇形成了一種高效的尋優(yōu)策略，最終，人工魚集結(jié)在幾個局部極值的周圍，且值較優(yōu)的極值區(qū) 域周圍一般能集結(jié)較多人工魚。 人工魚群 算法 人工魚群 算法的具體計算步驟為： Step1 (初始化 )確定人工魚群規(guī)模 N，在變量可行域內(nèi)隨機(jī)生成 N 個人工魚，設(shè)定人工魚的可視域 Visual，人工魚的移動步長 Step，擁擠度因子 ?，嘗試次數(shù)Try_number。 Step2 (設(shè)置公告板 )計算初始魚群各個人工魚的適應(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)， 2021年， Karaboga 等提出了人工