核中心驅動混合蛙跳算法及其應用

劉立群，顧任遠

甘肅農業大學 信息科學技術學院，蘭州730070

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

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

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

1 基礎概念

1.1 車輛路徑問題的數學描述

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

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

1.2 核中心驅動混合蛙跳算法

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

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

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

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

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

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

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

（3）若這個位置仍不夠好，則丟棄該青蛙個體位置，使用式（4）隨機產生不重復的青蛙個體分量。

改進后的NCSFLA 算法收斂性能明顯優于原始SFLA。

算法效率分析如下：SFLA的時間復雜度是(×××)，空間復雜度是(××)；NCSFLA的時間復雜度是(×××)，空間復雜度是(××)。可以看出，改進后的NCSFLA 算法與原始SFLA算法的時間復雜度和空間復雜度相同，其運算復雜度及運算成本與原始SFLA 相當。NCSFLA 實現時需要按照約定的概念進行電子軌道劃分族群，并利用約定的概念進行族群內三種策略的改進，搜索策略中利用電子軌道中心、原子核中心為慣性指導，并且在進化更新時丟棄了跳躍步長的搜索范圍限制條件，較易實現。

2 核中心驅動混合蛙跳算法的容量限制車輛路徑優化算法

2.1 核中心驅動混合蛙跳算法的容量限制車輛路徑優化問題

核中心驅動混合蛙跳算法的容量限制車輛路徑優化問題可以看作單目標最小值優化問題，其數學描述可簡化為式（5），其中目標函數是所有車輛路徑總長。

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

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

2.2 核中心驅動混合蛙跳算法的容量限制車輛路徑優化算法流程

核中心驅動混合蛙跳算法的容量限制車輛路徑優化算法

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

2.3 算法流程圖

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

2.4 算法效率分析

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

3 實驗

3.1 核中心驅動混合蛙跳算法性能測試實驗

實驗采用20 個測試函數分別對本文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)進行優化性能測試實驗。各測試函數表達式、搜索范圍和理論極小值如表1 所示。最終測試結果采用獨立運行30 次后的平均值。

表1 測試函數Table 1 Benchmark functions

實驗參數設置如下：青蛙群體規模=200，族群數=20，族群內青蛙個數=10，青蛙個體維數=30，=10，=200。

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

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

圖2 改進的容量限制車輛路徑優化算法流程Fig.2 Flow chart of improved capacity-limited vehicle routing problem

圖3 f1進化曲線Fig.3 Evolution curves of f1

圖4 f2進化曲線Fig.4 Evolution curves of f2

圖5 f3進化曲線Fig.5 Evolution curves of f3

圖6 f4進化曲線Fig.6 Evolution curves of f4

圖7 f5進化曲線Fig.7 Evolution curves of f5

圖8 f6進化曲線Fig.8 Evolution curves of f6

圖9 f7進化曲線Fig.9 Evolution curves of f7

圖10 f8進化曲線Fig.10 Evolution curves of f8

圖11 f9進化曲線Fig.11 Evolution curves of f9

圖12 f10進化曲線Fig.12 Evolution curves of f10

圖13 f11進化曲線Fig.13 Evolution curves of f11

圖14 f12進化曲線Fig.14 Evolution curves of f12

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

3.2 核中心驅動混合蛙跳算法的容量限制車輛路徑優化算法性能測試實驗

圖15 f13進化曲線Fig.15 Evolution curves of f13

圖16 f14進化曲線Fig.16 Evolution curves of f14

圖17 f15進化曲線Fig.17 Evolution curves of f15

圖18 f16進化曲線Fig.18 Evolution curves of f16

圖19 f17進化曲線Fig.19 Evolution curves of f17

圖20 f18進化曲線Fig.20 Evolution curves of f18

圖21 f19進化曲線Fig.21 Evolution curves of f19

圖22 f20進化曲線Fig.22 Evolution curves of f20

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

實驗參數設置如下：青蛙群體規模=200，族群數=20，族群內青蛙個數=10，青蛙個體維數=8，=10，=30 。客戶結點個數=100，即青蛙個體維數=100，其中1～100 代表每個唯一的客戶號，0 代表配送中心的編號。按照車輛數=2，=4分別進行測試，每輛車的車容量q=200。=2 時，各算法進化曲線如圖23 所示，各算法車輛路徑優化比較如表3 所示。=4 時，各算法進化曲線如圖24所示，各算法車輛路徑優化比較如表4 所示。

表3 各算法K=2 Solomon算例數據車輛路徑優化比較Table 3 Comparison of vehicle routing optimization algorithms for Solomon example data while K=2

表4 各算法K=4 Solomon 算例數據車輛路徑優化比較Table 4 Comparison of vehicle routing optimization algorithms for Solomon example data while K=4

圖23 各算法K=2 Solomon 算例數據進化曲線Fig.23 Evolution curves of each algorithm for Solomon example data while K=2

圖24 各算法K=4 Solomon 算例數據進化曲線Fig.24 Evolution curves of each algorithm for Solomon example data while K=4

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

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

4 結束語

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