核中心驅(qū)動混合蛙跳算法及其應(yīng)用

劉立群，顧任遠(yuǎn)

甘肅農(nóng)業(yè)大學(xué) 信息科學(xué)技術(shù)學(xué)院，蘭州730070

容量限制車輛路徑問題（capacity-limited vehicle routing problem，CVRP）是車輛路徑問題（vehicle routing problem，VRP）中最常用的一種。CVRP 是典型的非確定性多項(xiàng)式（non-deterministic polynomial，NP）難解問題，現(xiàn)有技術(shù)大多采用啟發(fā)式算法求解，但均存在算法運(yùn)行時間長、易于陷入早熟收斂現(xiàn)象的缺陷。在CVRP 中，所有客戶的服務(wù)類型相同，同為送貨或同為收貨，所有車輛載重量一樣，每個客戶的需求量均不大于車輛載重量，車輛都從配送中心出發(fā)最終也返回到配送中心。

混合蛙跳算法（shuffled frog leaping algorithm,SFLA）是一種新的基于全局搜索和局部更新的啟發(fā)式合作搜索算法，它模仿了青蛙在受限環(huán)境中的覓食機(jī)制。該算法具有參數(shù)少，全局尋優(yōu)能力強(qiáng)和較快的收斂性等優(yōu)點(diǎn)，在組合優(yōu)化問題等方面獲得了較好的效果。但是SFLA 在尋優(yōu)更新中，存在差異更新隨機(jī)性，導(dǎo)致SFLA 在進(jìn)化后期易出現(xiàn)收斂速度慢、精度低等問題。目前，已有諸多學(xué)者對SFLA 的尋優(yōu)策略進(jìn)行改進(jìn)，性能得到了較好的改善。文獻(xiàn)[9]把具有極強(qiáng)局部搜索能力的冪律極值動力學(xué)優(yōu)化結(jié)合如SFLA，提出基于實(shí)數(shù)編碼模式的混合蛙跳算法求解容量約束車輛路徑問題。文獻(xiàn)[10]將改進(jìn)后的SFLA 采用實(shí)數(shù)編碼方式，融入自適應(yīng)差分?jǐn)_動機(jī)制及混沌局部搜索策略到局部搜索過程用于求解帶有容量約束的車輛路徑問題。文獻(xiàn)[11]針對帶容量約束的車輛路徑問題，提出了一種帶分裂機(jī)制的帝國競爭算法進(jìn)行求解。文獻(xiàn)[12]提出了一種量子行為粒子群優(yōu)化算法和探索啟發(fā)式局部搜索算法來求解容量約束的車輛路徑模型。文獻(xiàn)[13]將容量約束的車輛路徑問題擴(kuò)展到更廣泛的度量空間。文獻(xiàn)[14]定義了離散的蝙蝠位置、速度、頻率以及更新規(guī)則，用于解決帶容量約束問題的車輛路徑問題。文獻(xiàn)[15]提出一種離散布谷鳥算法求解帶容量約束的車輛路徑問題。文獻(xiàn)[16]對粒子群與改進(jìn)蟻群算法進(jìn)行融合改進(jìn)，并應(yīng)用于三維路徑規(guī)劃（autonomous underwater vehicle，AUV）問題中。文獻(xiàn)[17]利用深度學(xué)習(xí)的棧式自編碼模型對高光譜影像進(jìn)行光譜特征提取，通過混合蛙跳算法對目標(biāo)函數(shù)進(jìn)行優(yōu)化從而實(shí)現(xiàn)對最佳端元組合的搜索。文獻(xiàn)[18]提出了一種混合蛙跳算法和禁忌搜索（shuffled frog leaping algorithm along with the tabu search，SFLA-TS）的算法。文獻(xiàn)[19]引入變鄰域搜索算法提升蛙跳算法的局部搜索能力，引入針對關(guān)鍵工廠的全解空間禁忌搜索，擴(kuò)大了算法解空間。文獻(xiàn)[20]設(shè)計(jì)求解多約束車輛路徑模型的改進(jìn)混合蛙跳算法，改進(jìn)聚類算法并結(jié)合鄰近矩陣構(gòu)造初始青蛙種群，設(shè)計(jì)自內(nèi)而外的交流演化模式，定義遠(yuǎn)離矩陣，對青蛙進(jìn)行引導(dǎo)性鄰域搜索。文獻(xiàn)[21]提出了采用單種群蛙跳優(yōu)化的卷積神經(jīng)網(wǎng)絡(luò)算法對眼底多種病變進(jìn)行檢測。

本文提出一種核中心驅(qū)動混合蛙跳算法（shuffled frog leaping algorithm driven by nuclear center，NCSFLA），對容量限制車輛路徑優(yōu)化問題進(jìn)行研究，提出一種核中心驅(qū)動混合蛙跳算法的容量限制車輛路徑優(yōu)化算法（shuffled frog leaping algorithm driven by nuclear center for capacity-limited vehicle routing problem，NCSFLA-CVRP），以提高容量限制車輛路徑的優(yōu)化性能。

1 基礎(chǔ)概念

1.1 車輛路徑問題的數(shù)學(xué)描述

單目標(biāo)最優(yōu)化問題一般分為最大值優(yōu)化問題和最小值優(yōu)化問題。本文采用容量限制車輛路徑問題作為研究的對象，該問題屬于單目標(biāo)最小值優(yōu)化問題，其定義及描述如式（1）所示。

式中，(,)代表所有車輛的總路徑長度，c代表客戶和客戶之間的運(yùn)輸距離，q代表客戶的運(yùn)輸需求，q代表車輛的載荷容量，是客戶的總數(shù)量，其中,=1,2,…,代表客戶編號，=0 和=0 代表配送中心的編號，是車輛的總數(shù)量，其中=1,2,…,代表車輛編號，{x=1}代表車輛從客戶到客戶之間的有直接相連的路徑，否則{x=0}，y和y分別代表客戶和客戶的需求由車輛滿足。式（1.1）表示以配送中心0 開始編號的所有車輛的最小總路徑長度，是待求解的目標(biāo)函數(shù)。式（1.2）～（1.5）表示約束條件。式（1.2）～（1.3）表示車輛到達(dá)客戶或客戶后，又從該客戶出發(fā)。式（1.4）表示每條配送線路上總客戶需求量≤該配送線路上車輛的運(yùn)載能力。式（1.5）表示每個客戶僅和一輛車相關(guān)聯(lián)，配送中心0 編號可以與輛車關(guān)聯(lián)。

1.2 核中心驅(qū)動混合蛙跳算法

本文引入量子力學(xué)理論，以及玻爾原子模型理論，將SFLA 算法中的青蛙個體跳躍進(jìn)化行為定義為量子力學(xué)行為，對原始混合蛙跳算法進(jìn)行改進(jìn)，提出一種核中心驅(qū)動混合蛙跳算法（NCSFLA）。

（電子軌道）將初始化的青蛙群體空間定義為量子空間，量子空間中有一個原子模型，多個青蛙可以看作這個原子模型中的多個電子以及一個由全局最優(yōu)個體代表的原子核。青蛙的族群定義為多個電子軌道。則量子空間表示為：

其中，量子空間中具有=×個青蛙初始個體，為族群個數(shù)，為族群內(nèi)青蛙個數(shù)，青蛙個體分量()的維數(shù)記為。設(shè)各族群迭代局部進(jìn)化次數(shù)為，全局進(jìn)化次數(shù)為。

（個體躍遷步長）族群中個體躍遷步長定義為電子軌道中心與當(dāng)前族群中最差個體的差值，記為_=()-()，()代表族群中最差個體。

（個體驅(qū)動步長）族群中個體驅(qū)動步長定義為原子核中心與當(dāng)前族群中最差個體的差值，記為_=()-()，()代表族群中最差個體。

本文利用電子軌道中心驅(qū)動策略和原子核中心驅(qū)動策略對混合蛙跳算法中的一次局部進(jìn)化進(jìn)行改進(jìn)，提出一種核中心驅(qū)動混合蛙跳算法。算法進(jìn)化原理如圖1 所示。

圖1 核中心驅(qū)動混合蛙跳算法原理Fig.1 Principle of shuffled frog leaping algorithm driven by nuclear center

（3）若這個位置仍不夠好，則丟棄該青蛙個體位置，使用式（4）隨機(jī)產(chǎn)生不重復(fù)的青蛙個體分量。

改進(jìn)后的NCSFLA 算法收斂性能明顯優(yōu)于原始SFLA。

算法效率分析如下：SFLA的時間復(fù)雜度是(×××)，空間復(fù)雜度是(××)；NCSFLA的時間復(fù)雜度是(×××)，空間復(fù)雜度是(××)?？梢钥闯觯倪M(jìn)后的NCSFLA 算法與原始SFLA算法的時間復(fù)雜度和空間復(fù)雜度相同，其運(yùn)算復(fù)雜度及運(yùn)算成本與原始SFLA 相當(dāng)。NCSFLA 實(shí)現(xiàn)時需要按照約定的概念進(jìn)行電子軌道劃分族群，并利用約定的概念進(jìn)行族群內(nèi)三種策略的改進(jìn)，搜索策略中利用電子軌道中心、原子核中心為慣性指導(dǎo)，并且在進(jìn)化更新時丟棄了跳躍步長的搜索范圍限制條件，較易實(shí)現(xiàn)。

2 核中心驅(qū)動混合蛙跳算法的容量限制車輛路徑優(yōu)化算法

2.1 核中心驅(qū)動混合蛙跳算法的容量限制車輛路徑優(yōu)化問題

核中心驅(qū)動混合蛙跳算法的容量限制車輛路徑優(yōu)化問題可以看作單目標(biāo)最小值優(yōu)化問題，其數(shù)學(xué)描述可簡化為式（5），其中目標(biāo)函數(shù)是所有車輛路徑總長。

假設(shè)青蛙個體分量()的維數(shù)為，=1,2,…,,=1,2,…,，則一個青蛙個體分量()代表路徑優(yōu)化編碼里的每一個客戶號，即一個青蛙個體是由位客戶組成的，要求每個客戶號是唯一的。安排車輛的方案主要依據(jù)客戶編號排列次序及車輛最大裝載量安排車輛，依次類推直到客戶全部安排完畢為止。將客戶的編碼順序解碼為每個車輛的車輛路徑序列。

式（5.1）表示以配送中心0 開始編號的輛車總路徑長度之和的最小值，這是單目標(biāo)極小值最優(yōu)化問題的目標(biāo)函數(shù)。式（5.2）表示個客戶的運(yùn)輸需求≤第輛車的載荷容量。因?yàn)?1,2,…,代表每個唯一的客戶號，=0 代表配送中心的編號,第(=1,2,…,)輛車對應(yīng)的那條路徑總是從配送中心(=0)出發(fā)，再回到配送中心(=0)，所以式（5.2）涵蓋了車輛到達(dá)客戶或客戶+1 后，又從該客戶出發(fā)的約束條件，從而式（1.2）～（1.3）約束條件在此省略。式（5.3）表示每個客戶僅和一輛車相關(guān)聯(lián)，配送中心0 編號可以與輛車關(guān)聯(lián)。

2.2 核中心驅(qū)動混合蛙跳算法的容量限制車輛路徑優(yōu)化算法流程

核中心驅(qū)動混合蛙跳算法的容量限制車輛路徑優(yōu)化算法

4.判斷局部進(jìn)化次數(shù)是否達(dá)到，若未達(dá)到，轉(zhuǎn)至3；否則，判斷青蛙族群全局進(jìn)化次數(shù)是否達(dá)到或()是否達(dá)到收斂精度。若未達(dá)到，轉(zhuǎn)至2；否則，算法停止，輸出(())及優(yōu)化路徑序列。

2.3 算法流程圖

核中心驅(qū)動混合蛙跳算法的容量限制車輛路徑優(yōu)化算法流程如圖2 所示。

2.4 算法效率分析

NCSFLA-CVRP 的時間復(fù)雜度是(×××××)，空間復(fù)雜度是(×××+)。NCSFLACVRP 時間復(fù)雜度和空間復(fù)雜度會隨著、和的變化而變化，視車輛路徑數(shù)據(jù)規(guī)模而定。

3 實(shí)驗(yàn)

3.1 核中心驅(qū)動混合蛙跳算法性能測試實(shí)驗(yàn)

實(shí)驗(yàn)采用20 個測試函數(shù)分別對本文NCSFLA、帶記憶功能的混合蛙跳算法（shuffled frog leaping algorithm with memory，MSFLA）、基于全局共享因子的混合蛙跳算法（shuffled frog leaping algorithm based on global sharing factor，GSFLA）、SFLA、和聲搜索算法（harmony search algorithm，HSA）、人工蜂群算法（artificial bee colony algorithm，ABCA)進(jìn)行優(yōu)化性能測試實(shí)驗(yàn)。各測試函數(shù)表達(dá)式、搜索范圍和理論極小值如表1 所示。最終測試結(jié)果采用獨(dú)立運(yùn)行30 次后的平均值。

表1 測試函數(shù)Table 1 Benchmark functions

實(shí)驗(yàn)參數(shù)設(shè)置如下：青蛙群體規(guī)模=200，族群數(shù)=20，族群內(nèi)青蛙個數(shù)=10，青蛙個體維數(shù)=30，=10，=200。

六個算法對應(yīng)的20 個測試函數(shù)收斂精度和速度比較如表2 所示，進(jìn)化曲線如圖3～圖22 所示。從進(jìn)化曲線可以看出，NCSFLA 算法進(jìn)化收斂速度以及精度明顯高于其他五種算法，尤其和是兩個復(fù)合函數(shù)的情況下，本文算法也適用。表2 也顯示了本文算法在單峰和多峰值函數(shù)的收斂精度上表現(xiàn)良好。

表2 收斂精度和速度比較Table 2 Comparison of convergence precision and convergence speed

圖2 改進(jìn)的容量限制車輛路徑優(yōu)化算法流程Fig.2 Flow chart of improved capacity-limited vehicle routing problem

圖3 f1進(jìn)化曲線Fig.3 Evolution curves of f1

圖4 f2進(jìn)化曲線Fig.4 Evolution curves of f2

圖5 f3進(jìn)化曲線Fig.5 Evolution curves of f3

圖6 f4進(jìn)化曲線Fig.6 Evolution curves of f4

圖7 f5進(jìn)化曲線Fig.7 Evolution curves of f5

圖8 f6進(jìn)化曲線Fig.8 Evolution curves of f6

圖9 f7進(jìn)化曲線Fig.9 Evolution curves of f7

圖10 f8進(jìn)化曲線Fig.10 Evolution curves of f8

圖11 f9進(jìn)化曲線Fig.11 Evolution curves of f9

圖12 f10進(jìn)化曲線Fig.12 Evolution curves of f10

圖13 f11進(jìn)化曲線Fig.13 Evolution curves of f11

圖14 f12進(jìn)化曲線Fig.14 Evolution curves of f12

結(jié)果顯示，針對20 個測試函數(shù)，本文提出的NCSFLA 算法相對于MSFLA、GSFLA、SFLA、HSA、ABCA 五種算法，具有收斂速度快、收斂精度高的特點(diǎn)，克服了原始SFLA 的缺陷。

3.2 核中心驅(qū)動混合蛙跳算法的容量限制車輛路徑優(yōu)化算法性能測試實(shí)驗(yàn)

圖15 f13進(jìn)化曲線Fig.15 Evolution curves of f13

圖16 f14進(jìn)化曲線Fig.16 Evolution curves of f14

圖17 f15進(jìn)化曲線Fig.17 Evolution curves of f15

圖18 f16進(jìn)化曲線Fig.18 Evolution curves of f16

圖19 f17進(jìn)化曲線Fig.19 Evolution curves of f17

圖20 f18進(jìn)化曲線Fig.20 Evolution curves of f18

圖21 f19進(jìn)化曲線Fig.21 Evolution curves of f19

圖22 f20進(jìn)化曲線Fig.22 Evolution curves of f20

依據(jù)本文提出的NCSFLA-CVRP 算法解決容量限制車輛路徑問題的思路，對上述其中三個算法MSFLA、GSFLA、SFLA進(jìn)行修改，分別得到帶記憶功能混合蛙跳算法的容量限制車輛路徑優(yōu)化算法（shuffled frog leaping algorithm with memory for capacity-limited vehicle routing problem，MSFLA-CVRP），基于全局共享因子混合蛙跳算法的容量限制車輛路徑優(yōu)化算法（shuffled frog leaping algorithm based on global sharing factor for capacity-limited vehicle routing problem，GSFLA-CVRP），基本混合蛙跳算法的容量限制車輛路徑優(yōu)化算法（shuffled frog leaping algorithm for capacity-limited vehicle routing problem，SFLACVRP）。實(shí)驗(yàn)采用這四種算法，采用Solomon算例（http://web.cba.neu.edu/～msolomon/problems.htm）標(biāo)準(zhǔn)測試數(shù)據(jù)中RC101 數(shù)據(jù)集對容量限制車輛路徑問題進(jìn)行優(yōu)化性能測試實(shí)驗(yàn)。選取RC101數(shù)據(jù)集作為測試集。

實(shí)驗(yàn)參數(shù)設(shè)置如下：青蛙群體規(guī)模=200，族群數(shù)=20，族群內(nèi)青蛙個數(shù)=10，青蛙個體維數(shù)=8，=10，=30 ?？蛻艚Y(jié)點(diǎn)個數(shù)=100，即青蛙個體維數(shù)=100，其中1～100 代表每個唯一的客戶號，0 代表配送中心的編號。按照車輛數(shù)=2，=4分別進(jìn)行測試，每輛車的車容量q=200。=2 時，各算法進(jìn)化曲線如圖23 所示，各算法車輛路徑優(yōu)化比較如表3 所示。=4 時，各算法進(jìn)化曲線如圖24所示，各算法車輛路徑優(yōu)化比較如表4 所示。

表3 各算法K=2 Solomon算例數(shù)據(jù)車輛路徑優(yōu)化比較Table 3 Comparison of vehicle routing optimization algorithms for Solomon example data while K=2

表4 各算法K=4 Solomon 算例數(shù)據(jù)車輛路徑優(yōu)化比較Table 4 Comparison of vehicle routing optimization algorithms for Solomon example data while K=4

圖23 各算法K=2 Solomon 算例數(shù)據(jù)進(jìn)化曲線Fig.23 Evolution curves of each algorithm for Solomon example data while K=2

圖24 各算法K=4 Solomon 算例數(shù)據(jù)進(jìn)化曲線Fig.24 Evolution curves of each algorithm for Solomon example data while K=4

從以上測試結(jié)果可以看出，對標(biāo)準(zhǔn)測試數(shù)據(jù)RC101 數(shù)據(jù)集，NCSFLA-CVRP 算法在不同車輛數(shù)情況下均體現(xiàn)出較優(yōu)的最短路徑值。算法進(jìn)化曲線也顯示出在固定進(jìn)化次數(shù)條件下，NCSFLA-CVRP 算法具有較為平穩(wěn)的進(jìn)化曲線，使得它不易陷入早熟收斂。在多車輛測試中，隨著車輛數(shù)的增多，車輛優(yōu)化的路徑更加滿足客戶的實(shí)際需求。以上結(jié)果表明，NCSFLA-CVRP算法較MSFLA-CVRP、GSFLA-CVRP、SFLA-CVRP 三種算法具有更高的效率和可靠性，可以有效提高容量限制車輛路徑的優(yōu)化性能。

由于CVRP 問題屬于NP 難解問題，很難在多項(xiàng)式時間復(fù)雜度范圍內(nèi)求得最優(yōu)解。本文將提出的核中心驅(qū)動混合蛙跳算法應(yīng)用于解決該問題，提出NCSFLA-CVRP 算法，以青蛙個體分量代表路徑優(yōu)化編碼里的每一個唯一的客戶號，將客戶的編碼順序解碼為每個車輛的車輛路徑序列，并以配送中心0開始編號的輛車總路徑長度之和的最小值作為算法的適應(yīng)度目標(biāo)函數(shù)，在約束滿足的條件下將CVRP問題簡化為求解單目標(biāo)極小值最優(yōu)化問題。算例結(jié)果表明，本文提出的NCSFLA-CVRP 算法具有快速收斂的效果，提高了算法的執(zhí)行效率，取得了較優(yōu)的最短路徑值。同時，算法具有較高的魯棒性和可靠性，在多車輛條件下仍可滿足多客戶的實(shí)際需求。

4 結(jié)束語

本文引入量子力學(xué)理論以及玻爾原子模型理論，將SFLA 算法中的青蛙個體跳躍進(jìn)化行為定義為量子力學(xué)行為，對原始混合蛙跳算法進(jìn)行改進(jìn)，提出一種核中心驅(qū)動混合蛙跳算法。將該算法應(yīng)用于容量限制車輛路徑優(yōu)化問題，提出了一種核中心驅(qū)動混合蛙跳算法的容量限制車輛路徑優(yōu)化算法。實(shí)驗(yàn)結(jié)果顯示單峰值、多峰值函數(shù)以及復(fù)合函數(shù)等20 個測試函數(shù)，NCSFLA 算法相對于MSFLA、GSFLA、SFLA、HSA、ABCA 五種算法具有收斂速度快、精度高的特點(diǎn)，克服了原始SFLA 的缺陷。Solomon 算例標(biāo)準(zhǔn)測試數(shù)據(jù)實(shí)驗(yàn)結(jié)果表明NCSFLA-CVRP 算法較MSFLA-CVRP、GSFLA-CVRP、SFLA-CVRP 三種算法具有更高的效率和可靠性，有效提高了容量限制車輛路徑的優(yōu)化性能。