張亞龍 肖銀寶

摘要：在電子商務(wù)蓬勃發(fā)展的大環(huán)境下，物流行業(yè)已經(jīng)成為推動(dòng)我國(guó)經(jīng)濟(jì)發(fā)展的重要力量，人們對(duì)物流配送的要求也越來(lái)越高，如何科學(xué)合理地規(guī)劃配送車(chē)輛的路線，實(shí)現(xiàn)高效率、低成本是當(dāng)前學(xué)者們研究的重點(diǎn)。物流配送遍及生產(chǎn)生活的方方面面，面對(duì)日益復(fù)雜的道路環(huán)境，隨著信息化水平的提升，這使得用智能計(jì)算推動(dòng)物流配送模式革新有著重要意義。本文通過(guò)科學(xué)合理的方法對(duì)復(fù)雜的車(chē)輛路徑問(wèn)題（VRP）的衍生問(wèn)題，即帶時(shí)間窗的車(chē)輛路徑問(wèn)題和同時(shí)取送貨的車(chē)輛路徑問(wèn)題（VRPSPDTW）進(jìn)行求解，主要通過(guò)對(duì)現(xiàn)有的鯨魚(yú)優(yōu)化算法進(jìn)行研究，針對(duì)鯨魚(yú)算法求解問(wèn)題后期種群多樣性缺失的問(wèn)題，引入新的收斂因子、自適應(yīng)權(quán)重和Metropolis準(zhǔn)則對(duì)其進(jìn)行補(bǔ)足，將其應(yīng)用至實(shí)際問(wèn)題中，驗(yàn)證其可行性。

關(guān)鍵詞：智能計(jì)算；路徑規(guī)劃；鯨魚(yú)算法；VRP

1概述

隨著電子商務(wù)行業(yè)的強(qiáng)勁發(fā)展，物流行業(yè)逐漸成為推動(dòng)我國(guó)經(jīng)濟(jì)發(fā)展的主要力量，物流配送的車(chē)輛路徑問(wèn)題，越來(lái)越得到有關(guān)學(xué)者的重視，車(chē)輛路徑作為經(jīng)典的組合優(yōu)化問(wèn)題一直是研究的熱點(diǎn)與難點(diǎn)。隨著信息技術(shù)的快速發(fā)展，計(jì)算機(jī)算力大幅提升，使得啟發(fā)式算法求解車(chē)輛路徑及其衍生問(wèn)題更加科學(xué)合理。本文主要從車(chē)輛路徑問(wèn)題的發(fā)展現(xiàn)狀，傳統(tǒng)鯨魚(yú)優(yōu)化算法方案的優(yōu)缺點(diǎn)，對(duì)其進(jìn)行改進(jìn)，來(lái)提高其運(yùn)行效率。

2研究方案

WOA算法是一種群智能優(yōu)化算法，靈感來(lái)自海洋中座頭鯨獨(dú)有的氣泡網(wǎng)捕食方式。座頭鯨發(fā)現(xiàn)獵物后，通過(guò)制作氣泡網(wǎng)的方式，以形似螺旋的路徑進(jìn)行捕食，其具體行為包括包圍捕食、螺旋更新位置及搜索獵物。鯨魚(yú)種群捕食過(guò)程中，通過(guò)最佳個(gè)體的位置來(lái)進(jìn)行位置更新，最終收斂域最優(yōu)目標(biāo)值附件，但經(jīng)典的鯨魚(yú)優(yōu)化算法存在有收斂性慢，算法后期迭代缺乏種群多樣性，易陷入局部最優(yōu)。本文在基本的鯨魚(yú)優(yōu)化算法上加以改進(jìn)，通過(guò)采用新的收縮因子方法，較好地調(diào)節(jié)了全局和局部的搜索能力。引入自適應(yīng)權(quán)重策略很好地保持了種群的多樣性，使算法的收斂性和搜索性提升。引入Metropolis準(zhǔn)則，通過(guò)以一定的概率接受較差的點(diǎn)來(lái)提升全局尋優(yōu)能力，避免了算法陷入局部最優(yōu)解。

3傳統(tǒng)鯨魚(yú)優(yōu)化算法的實(shí)現(xiàn)

車(chē)輛路徑問(wèn)題及其衍生問(wèn)題一直是NPHard問(wèn)題，其約束條件繁雜，在對(duì)其目標(biāo)問(wèn)題建模后，根據(jù)鯨魚(yú)優(yōu)化算法包括三種更新個(gè)體位置的方式，分別是氣泡攻擊、搜索捕食、包圍獵物，對(duì)問(wèn)題進(jìn)行求解。

當(dāng)鯨魚(yú)在包圍捕獲獵物時(shí)，首先要確定獵物位置，但是獵物在搜索空間中的位置往往是不確定的。鯨魚(yú)優(yōu)化算法將獵物位置或者接近目標(biāo)獵物的位置作為當(dāng)前最優(yōu)候選解，其他鯨魚(yú)個(gè)體通過(guò)最優(yōu)候選解來(lái)更新自身所在的位置。

鯨魚(yú)優(yōu)化算法個(gè)體更新位置方式如下：

設(shè)p為［0，1］之間的隨機(jī)數(shù)，p是捕食機(jī)制概率，則：

若p0.5，則鯨魚(yú)個(gè)體采用氣泡攻擊方式以螺旋式形式進(jìn)行個(gè)體位置更新，即當(dāng)前鯨魚(yú)個(gè)體以螺旋式的方式向當(dāng)前最佳鯨魚(yú)個(gè)體靠近。

氣泡攻擊方式下的鯨魚(yú)個(gè)體位置更新公式為：

Xi（t+1）=X（t）+Deblcos（2πl(wèi)）（1）

D=X（t）－Xi（t）（2）

其中，Xi（t+1）表示下一代第i只鯨魚(yú)的位置，X（t）表示當(dāng)前時(shí)刻全局最優(yōu)向量，即當(dāng)前最優(yōu)鯨魚(yú)個(gè)體位置，b為常數(shù)，定義了對(duì)數(shù)螺旋的形狀；l為［－1，1］的隨機(jī)數(shù)。D=X（t）－Xi（t）表示為第i只鯨魚(yú)個(gè)體的位置到當(dāng)前最優(yōu)鯨魚(yú)個(gè)體位置的距離。

若p<0.5且A1，則鯨魚(yú)個(gè)體采用搜索捕食方式進(jìn)行個(gè)體位置更新，即鯨魚(yú)個(gè)體可能不向最佳鯨魚(yú)個(gè)體靠近，而是隨機(jī)選擇一只鯨魚(yú)個(gè)體靠近。

搜索捕食方式下得鯨魚(yú)個(gè)體位置更新公式為：

Xi（t+1）=Xrand（t）－A×D（3）

D=C×Xrand（t）－Xi（t）（4）

其中，假設(shè)在d維空間中，Xrand（t）表示為當(dāng)前鯨魚(yú)種群中隨機(jī)一只鯨魚(yú)個(gè)體的位置，D=C×Xrand（t）－Xi（t）表示為當(dāng)前種群中第i只鯨魚(yú)個(gè)體的位置到當(dāng)前種群中隨機(jī)一只鯨魚(yú)位置的距離，A=2a×r1－a，C=2×r2，其中，r1，r2為［0，1］之間的隨機(jī)數(shù)。

若p<0.5且A<1，則鯨魚(yú)個(gè)體采用包圍獵物的方式進(jìn)行個(gè)體位置更新。

包圍獵物方式下得鯨魚(yú)個(gè)體位置更新公式為：

Xi（t+1）=X（t）－A×D（5）

D=C×X（t）－Xi（t）（6）

其中，D=C×X（t）－Xi（t）表示當(dāng)前種群中第i只鯨魚(yú)個(gè)體的位置到當(dāng)前最優(yōu)鯨魚(yú)個(gè)體位置距離，A=2a×r1－a，C=2×r2，其中，r1，r2為［0，1］之間的隨機(jī)數(shù)。

當(dāng)鯨魚(yú)算法訪問(wèn)完所有的客戶，第一次迭代完成，每條鯨魚(yú)均找到了對(duì)應(yīng)的行駛路徑，相當(dāng)于車(chē)輛完成了一次運(yùn)行，在達(dá)到最大迭代次數(shù)時(shí)，選取所有迭代次數(shù)中整體適應(yīng)度值最小的鯨魚(yú)所選的路徑，作為全局最優(yōu)路徑，總路徑最短的鯨魚(yú)為全局最優(yōu)解。

傳統(tǒng)鯨魚(yú)算法解決車(chē)輛路徑問(wèn)題時(shí)會(huì)有兩個(gè)缺點(diǎn)：（1）根據(jù)鯨魚(yú)優(yōu)化算法三個(gè)位置更新公式，不難看出，位置更新是通過(guò)最優(yōu)個(gè)體的位置變動(dòng)來(lái)更新此時(shí)鯨魚(yú)個(gè)體的位置，會(huì)造成種群多樣性的丟失，對(duì)于大規(guī)模問(wèn)題算法初期，解的搜索具有盲目性。（2）經(jīng)典鯨魚(yú)優(yōu)化算法缺少擾動(dòng)機(jī)制，存在算法后期收斂速度慢，易陷入局部最優(yōu)等缺陷。

4對(duì)傳統(tǒng)鯨魚(yú)算法的改進(jìn)

鯨魚(yú)優(yōu)化算法是元啟發(fā)式群智能優(yōu)化算法，雖然有良好的啟發(fā)性，但存在著求解精度低、收斂速度慢、易陷入局部最優(yōu)解的情況。針對(duì)以上幾個(gè)缺陷做出以下改進(jìn)：

（1）通過(guò)采用新的收縮因子方法，較好地調(diào)節(jié)了全局和局部的搜索能力。

（2）引入自適應(yīng)權(quán)重策略很好地保持了種群的多樣性，使算法的收斂性和搜索性提升。

（3）引入Metropolis準(zhǔn)則，通過(guò)以一定的概率接受較差的點(diǎn)來(lái)提升全局尋優(yōu)能力，避免了算法陷入局部最優(yōu)解。

4.1采用新的收縮因子

傳統(tǒng)的鯨魚(yú)優(yōu)化算法的收縮因子為線性收縮因子，a的值從2到0線性下降，其收斂速度較慢，導(dǎo)致搜索時(shí)間較長(zhǎng)，降低了算法的效率，傳統(tǒng)的搜索因子公式為：

a=2－2tItermax（7）

本文通過(guò)采用非線性收縮因子的方法，較好地調(diào)節(jié)了算法的全局和局部搜索能力，新的收縮因子公式如下：

a=2－2sinμtItermaxπ+φ（8）

其中Itermax是最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)，μ、φ是表達(dá)式的相關(guān)系數(shù)，為使收斂因子a滿足從2至0遞減，選取μ=1/2，φ=0；用新的收斂因子公式計(jì)算系數(shù)向量A，設(shè)r1，r2為［0，1］之間的隨機(jī)數(shù)，則A=2a×r1－a，系數(shù)向量C=2×r2。

4.2引入自適應(yīng)權(quán)重

通過(guò)鯨魚(yú)算法的所搜機(jī)制可知，位置更新是通過(guò)最優(yōu)個(gè)體的位置變動(dòng)來(lái)更新此時(shí)鯨魚(yú)個(gè)體的位置，會(huì)造成種群多樣性的丟失，對(duì)于大規(guī)模問(wèn)題算法初期，解的搜索具有盲目性。自適應(yīng)權(quán)重ω的公式如下：

ω=1－etItermax－1/e－1（9）

其中Itermax是最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)。通過(guò)采用自適應(yīng)權(quán)重策略很好地保持了種群的多樣性，使算法的收斂性和搜索性提升。

4.3引入Metropolis準(zhǔn)則

1953年，Metropolis提出重要性采樣方法，即以概率來(lái)接受新?tīng)顟B(tài)，而不是使用完全確定的規(guī)則，稱為Metropolis準(zhǔn)則。

假設(shè)前一狀態(tài)為X（n），系統(tǒng)受到一定擾動(dòng)，狀態(tài)變?yōu)閄（n+1），相應(yīng)地，系統(tǒng)能量由E（n）變?yōu)镋（n+1），定義系統(tǒng)由X（n）變?yōu)閄（n+1）的接收概率為P，則P的概率計(jì)算公式為：

P=1，E（n+1）<E（n）

exp（－En+1－E（n）T），x0（10）

當(dāng)狀態(tài)轉(zhuǎn)移之后，如果能量減小了，那么這種轉(zhuǎn)移就被接受了。如果能量增大了，就說(shuō)明系統(tǒng)偏離全局最優(yōu)位置更遠(yuǎn)了，此時(shí)算法不會(huì)立即將其拋棄，而是進(jìn)行概率判斷。首先在區(qū)間［0，1］產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)ε，如果ε<P，這種轉(zhuǎn)移將被接受，否則拒絕轉(zhuǎn)移，進(jìn)入下一步，如此循環(huán)。

其核心思想是當(dāng)能量增加時(shí)以一定概率接收，即陷入局部最優(yōu)時(shí)有一定概率能跳出局部最優(yōu)，其中以能量的變化量和T進(jìn)行決定概率P的大小，所以P這個(gè)值是動(dòng)態(tài)的。

經(jīng)典鯨魚(yú)優(yōu)化算法缺少擾動(dòng)機(jī)制，存在算法后期收斂速度慢、易陷入局部最優(yōu)等缺陷。在更新鯨魚(yú)種群中的鯨魚(yú)個(gè)體后，根據(jù)Metropolis準(zhǔn)則，以一定的概率接受劣質(zhì)個(gè)體。概率公式計(jì)算如下：

P1=e－fXit+1－fXi（t）/fXi（t）T（11）

其中，T為當(dāng)前迭代次數(shù)時(shí)的溫度，初始迭代溫度T0為100。fXi（t）為第i只鯨魚(yú)當(dāng)前迭代下的最優(yōu)路徑，fXi（t+1）是下一次迭代下第i只鯨魚(yú)的最優(yōu)路徑。每次迭代后的降溫公式為：T=αT，其中，α為降溫速率，設(shè)定為0.99。

4.4算法流程

下圖為改進(jìn)的鯨魚(yú)優(yōu)化算法流程圖，整個(gè)算法對(duì)問(wèn)題的求解過(guò)程分為以下步驟：

Step1初始化鯨魚(yú)算法的相關(guān)參數(shù)，包括種群規(guī)模N、當(dāng)前迭代次數(shù)t、最大迭代次數(shù)Itermax、初始溫度T0和降火速率系數(shù)α；

Step2構(gòu)建解空間，根據(jù)適應(yīng)度函數(shù)，計(jì)算鯨魚(yú)種群中的每個(gè)鯨魚(yú)個(gè)體的所在位置的適應(yīng)度值，確定初始種群中個(gè)體的最優(yōu)位置和種群全局最優(yōu)位置，初始個(gè)體適應(yīng)度值最小的對(duì)應(yīng)最優(yōu)位置，就是初始種群的全局最優(yōu)位置；

Step3采用非線性的方法計(jì)算收縮因子a，計(jì)算并更新鯨魚(yú)優(yōu)化算法系數(shù)向量A，C；

Step4引入自適應(yīng)權(quán)重ω，根據(jù)鯨魚(yú)個(gè)體更新公式、更新鯨魚(yú)種群中的所有鯨魚(yú)個(gè)體的位置，得到每只鯨魚(yú)的初始可行路徑；

Step5位置更新結(jié)束后，使用Metropolis準(zhǔn)則更新種群；

Step6對(duì)Metropolis準(zhǔn)則進(jìn)行降溫，T=αT；

Step7判斷是否達(dá)到種群最大迭代次數(shù)Itermax，如果達(dá)到最大迭代次數(shù)，輸出最優(yōu)鯨魚(yú)個(gè)體位置，得到最優(yōu)鯨魚(yú)個(gè)體的可行路徑，計(jì)算結(jié)束，否則轉(zhuǎn)到Step3，重復(fù)執(zhí)行Step3至Step6，達(dá)到最大迭代次數(shù)時(shí)，輸出求解結(jié)果。

5分析總結(jié)

本課題主要是應(yīng)用鯨魚(yú)優(yōu)化算法，通過(guò)對(duì)其改進(jìn)以便更好加快算法的收斂速度和求解精度，以此來(lái)更好地滿足實(shí)際應(yīng)用對(duì)效率和準(zhǔn)確性的需求。

雖然創(chuàng)造性地從收縮因子方面及引入自適應(yīng)權(quán)重和Metropolis準(zhǔn)則來(lái)改進(jìn)鯨魚(yú)算法，但是僅從鯨魚(yú)種群多樣性和擾動(dòng)機(jī)制上考慮是不夠的，在未來(lái)的研究中還需要進(jìn)一步加深。

主要?jiǎng)?chuàng)新點(diǎn)：

（1）通過(guò)對(duì)傳統(tǒng)鯨魚(yú)算法的改進(jìn)，提高其搜索性能，增加其擾動(dòng)機(jī)制，并采用Metropolis準(zhǔn)則來(lái)增強(qiáng)其跳出局部最優(yōu)的能力。

（2）優(yōu)化參數(shù)的選擇，提高其收斂性，提高算法運(yùn)行效率，可更好地應(yīng)用于復(fù)雜問(wèn)題。

參考文獻(xiàn)：

［1］唐彥，張進(jìn)軍.基于改進(jìn)的鯨魚(yú)優(yōu)化算法的物流車(chē)輛配送路徑規(guī)劃［J］.隴東學(xué)院學(xué)報(bào)，2021，32（05）：610.

［2］龐燕，羅華麗，邢立寧，等.車(chē)輛路徑優(yōu)化問(wèn)題及求解方法研究綜述［J］.控制理論與應(yīng)用，2019（10）：15731584.

［3］楊博，李昌華，李智杰，等.改進(jìn)鯨魚(yú)算法及其在路徑規(guī)劃的應(yīng)用［J］.計(jì)算機(jī)測(cè)量與控制，2021，29（02）：187193+201.

［4］余賢星.一種改進(jìn)的多領(lǐng)導(dǎo)鯨魚(yú)優(yōu)化算法［J］.軟件工程，2022，25（11）：2834.

［5］楊柳，王潁超，侯漢坡.冷鏈低碳配送路徑優(yōu)化研究［J］.商業(yè)經(jīng)濟(jì)研究，2019（17）：104107.

［6］謝沖沖，李瑩.基于改進(jìn)算法的移動(dòng)機(jī)器人路徑規(guī)劃［J］.重慶大學(xué)學(xué)報(bào)，2021，44（12）：140148.

［7］陳榮，王雯陽(yáng)，卞東東.基于鯨魚(yú)算法的循環(huán)取貨路徑優(yōu)化研究［J］.物流科技，2021，44（10）：2832.

［8］崔東文.鯨魚(yú)優(yōu)化算法在水庫(kù)優(yōu)化調(diào)度中的應(yīng)用［J］.水利水電科技進(jìn)展，2017，37（03）：7276+94.

［9］高嘉，任亞明.基于模擬退火算法組合優(yōu)化問(wèn)題的求解［J］.企業(yè)科技與發(fā)展，2021（05）：6668.

［10］鄧紹強(qiáng)，郭宗建，李芳，等.基于Metropolis準(zhǔn)則的自適應(yīng)模擬退火粒子群優(yōu)化［J］.軟件導(dǎo)刊，2022，21（06）：8591.

項(xiàng)目：本文受到廣東高校重點(diǎn)領(lǐng)域?qū)ｍ?xiàng)新一代信息技術(shù)重點(diǎn)領(lǐng)域?qū)ｍ?xiàng)項(xiàng)目（2021ZDZX1019）的技術(shù)及經(jīng)費(fèi)支持

作者簡(jiǎn)介：張亞龍（1997—），男，漢族，河南洛陽(yáng)人，碩士研究生在讀，研究方向：智能優(yōu)化算法及應(yīng)用；肖銀寶（1973—），男，漢族，云南昆明人，碩士，助理研究員，研究方向：科技管理及信息化。