改進人工電場算法在選址問題中的應用研究 *

鄭宏宇，唐竟超，姚光磊，熊菊霞

（廣西民族大學 數學與物理學院，廣西 南寧 530006）

0 引言

隨著新經濟和電商平臺的日益發達，物流行業的競爭也越來越激烈?，F代物流配送是指商品從倉庫到需求點的實體運輸過程中，按照現實需求，將裝卸、運輸、流通和加工等功能有機地結合以滿足需求點要求的過程。在將商品從制造地運輸到需求地的過程中，需要建立一個中心服務站點來集中配送商品。建立中心服務站點的主要目的是將商品有效、快捷地送達需求地點，這就是物流配送中心。物流配送中心在整條物流系統中具有著承上啟下的重要功能，是供給點和需求點之間相互聯系的關鍵紐帶。因此，如何科學、合理地選定建設配送中心的地點是整條物流系統分析中的核心內容，同時也是物流配送體系合理運營的基礎前提。在大規模連鎖經營下，物流配送中心即連鎖公司建立的物資供應管理中心，按照公司總店的安排及各分公司的需求，由配送中心向各分公司統一調配物資，利用物流配送中心大規模生產和高效率的配送方式減少公司的運營成本，以便獲取最高的收益。［1］由于配送中心的選址工作是一項龐大的工程，且往往受到原料配送、運輸條件等諸多因素的影響，其合理的選擇既可以節省建設和維護成本，也能保證物流系統高效運作。物流配送中心規模巨大，其建設與發展不但關系到周邊地區，而且關系一個城市的經濟發展建設以及所在地區的生態環境，［2］因而配送中心的選址設計和優化方案具有重要的研究意義。

選址問題（Location problem，LP）［3］是運籌學中經典的問題之一，一般描述為在一個具有若干供應點及若干需求點的區域內，將一定數量的需求點設置為配送中心的優化過程。［4］1964 年，Hakimi 首先提出了網絡上的P-中位問題（也稱P-中值問題）與P-中心問題，自此，選址理論的研究開始活躍起來。選址問題包括P-中位問題、P-中心問題和覆蓋問題三個基本問題以及多種擴展問題。多配送中心選址問題（Multi-distribution center location problem，MDLP）屬于P-中位選址問題，且涉及的變量及約束條件較多，屬于典型的NPhard 問題［5］，以至于一些傳統的方法難以解決該問題。但隨著智能優化算法的興起和多種新型啟發式仿生算法在近些年被相繼提出，多配送中心選址問題成為學者們的研究熱點，很多國內外專家和學者都應用智能優化算法尋找選址問題的最優解。Nong［6］采用網絡分析法（ANP）和優劣解距離法相結合的方法，提出了一種支持配送中心選址的集成多準則決策分析模型（Multicriteria decision making model，MCDM）。Arsalan 等人［7］基于leader-follower 模型，提出了一個雙層非線性規劃領域中的枚舉分支切割方法，并通過實驗表明了算法的有效性。Thuy 等人［8］提出了一種基于球形模糊層次分析法和組合妥協解的混合MCDM 模型，并證明了該模型的有效性。劉培德等人［9］提出了一種基于二維語言相似度的聚類分析算法，并利用該算法構建了綜合物流配送中心選址問題的多屬性群體決策求解框架。Li 等人［10］通過Q 學習步長和遺傳算子，給出了動態步長布谷鳥算法用于求解選址問題，并通過實驗證明了該算法的性能優勢。

本文從實際科學工程優化問題出發，基于Anita等人提出的人工電場算法（Artificial electric field algorithm，AEFA），針對多配送中心選址模型，提出一種改進人工電場算法（Improved artificial electric field algorithm，IAEFA）并進行了理論分析。通過仿真實驗，驗證了改進人工電場算法的良好性能。

1 待解問題和算法描述

1.1 多配送中心選址問題

多配送中心選址問題（MDLP）指的是在某個區域內，已知有n個需求點，要從中選擇m(m＜n) 個作為配送中心向其余的需求點運輸貨物，在滿足所有需求點貨物需求的前提下，最小化配送中心與其配送范圍內需求點之間的運輸費用。［11］

為了方便多配送中心選址模型的建立，進行如下假設：

（1） 物流配送中心的供應量總能夠滿足需求點的需求量，并由其配送范圍內的總需求量決定；

（2） 確保每個需求點有且僅有一個為其運輸貨物的配送中心；

（3） 該選址模型只考慮從配送中心到需求點的費用；

（4） 配送中心與需求點之間的距離采用二維平面的歐式距離，不考慮地面高度差異和實際道路系統（如交通堵塞、車輛故障等）。

基于以上假設，建立如下模型：

約束條件為：

式（1）為目標函數；其中，Z表示總成本，即從選定的物流配送地點到該配送范圍內的每個需求點的總運費；m表示物流配送中心的數量，n表示需求點的數量，Dk表示需求點的需求量，djk表示物流配送中心j到需求點k的距離。yjk是0，1 變量，當yjk取值為1 時，表示需求點k由配送中心j配送。式（2）確保每個需求點僅由一個配送中心配送。J表示由配送中心組成的集合，K表示由需求點組成的集合。式（3）中，zj為0，1 變量，當zj取值為1 時，確定需求點j為配送中心；P表示選定的配送中心的個數。式（4）確保需求點的需求量只能被選為配送中心的點供應。式（5）、式（6）為yjk和zj的定義式。［12］

1.2 人工電場算法

人工電場算法（AEFA）［13］由Anita 等人于2019 年提出，主要模擬了帶電粒子在靜電場中的運動，并將其演化成隨機搜索最優解的過程。帶電粒子在搜索空間中受到靜電力的作用進行相互吸引或排斥運動，使得自身能在搜索空間中移動。為簡化帶電粒子的運動原理，在AEFA 算法中，僅考慮帶電粒子之間的吸引力，因此帶電粒子之間可以通過吸引力的作用進行相互運動，直到所有帶電粒子聚到一起。

在搜索空間中，每一個帶電粒子代表一個可行解，解的適應度由帶電粒子的電荷量決定，帶電粒子的電荷量越大，說明該帶電粒子所表示的可行解越接近最優解［14］。帶電粒子的運動原理如圖1所示。

圖1 帶電粒子受力示意圖

在圖1中，每一個圓圈代表一個帶電粒子，圓圈的大小表示電荷量的大小。帶電粒子Q1受到其他三個帶電粒子的吸引力，最終形成一個合力F和該方向上的加速度?？梢奞4的電荷量最大，它對Q1的吸引力最大，所以Q1所受合力的方向更接近Q4對Q1的吸引力方向。因此，AEFA算法在進行迭代的過程中，搜索空間中小電荷粒子會向大電荷粒子移動，使算法逐步收斂到最優解。［15］

AEFA算法的數學模型可以用式（7）、式（8）來描述：

其中，rand為[0，1]之間的任意常數；Vit+1表示在第t+ 1次迭代時第i個帶電粒子的速度；+1表示在第t+ 1次迭代時第i個帶電粒子的位置；表示在第t次迭代時第i個帶電粒子的加速度。

根據牛頓第二定律，當粒子受到電場力時，加速度的表達式為：

在第t次迭代時，帶電粒子的電場強度為：

帶電粒子在搜索空間中受到的合力為：

合力根據帶電粒子所受庫侖力計算而來，帶電粒子所受庫侖力模型如下：

式（12）中，Kt為庫倫常數；X表示第t次迭代中的最優個體；表示在第t次迭代時，帶電粒子i與帶電粒子j之間的距離；ε為很小的正數。式（13）為的定義式。式（14）中，K0= 500，α= 30；iter表示當前迭代次數；T表示最大迭代次數。庫倫常數的變化使得該算法在迭代前期進行全局搜索，找到最優解所在范圍；在迭代后期對最優解所在范圍進行局部搜索。Kt的迭代過程如圖2所示。

圖2 庫倫常數迭代曲線

算法在迭代過程中規定第一代種群中所有粒子的電荷量均相同（設為1），從第二代開始，電荷量的迭代公式如下：

其中，表示第i個帶電粒子在第t次迭代時的電荷量，為的歸一化處理結果；fi為第t次迭代中第i個粒子的適應度值；best (t ) 表示第t 次迭代中的最優適應度值，worst (t ) 表示第t 次迭代中的最差適應度值。

算法在每一次迭代時的位置均由貪婪策略決定：

式（17）表示下一代個體位置的選取方式。若更新后的個體適應度劣于上一代，則個體位置不發生改變；反之采用更新后的個體作為下一代。

由上述分析可知，AEFA 算法的基本實現步驟如下：

1）在搜索空間中初始化種群數量、種群位置和最大迭代次數；

2）初始化帶電粒子的速度(V= 0)、電荷量(Q=1) 和質量(m= 1)；

3）計算庫倫常數，更新全局最優值和最差值；

4）更新個體速度和位置；

5）若算法達到最大迭代次數，則輸出當前最優值；反之，算法跳回步驟3）。

2 人工電場算法解決MDLP 問題原理

人工電場算法的求解是以庫倫定律為依據的逐代搜索過程。在實際求解時，采用隨機數編碼策略，設定維度D等于需求點個數，根據所需配送中心的數量對個體進行排序并取前m個編號得到所需的配送中心位置。編碼和解碼過程如圖3 所示。

圖3 編碼及解碼策略

假設種群數量為N，維度為28，意味著共有28 個需求點。以選取6 個配送中心為例，由圖3 可知，從種群X=(X1，X2，…，XN) 中 任 意 選 取 個 體Xi，i∈{1，2，…，N}，Xi=（0.34，0.41，0.56，0.53，0.82，0.50，0.72，…，0.49）。對Xi進行排序，取前6 個的編號（11，13，24，5，19，7），該編號代表一個可行解，即選取編號為11，13，24，5，19，7 的需求點為配送中心。

3 改進人工電場算法

3.1 正余弦算法迭代機制

正余弦算法（Sine cosine algorithm，SCA）［16］利用正余弦函數的數學性質，通過添加自適應參數改變正余弦函數的振幅以實現算法的全局搜索和局部開發過程，最終尋得最優解。在SCA 算法中個體位置的更新公式如下［17］：

式（18）中，表示在第t+ 1 次迭代時第i個個體的位置；Ptbest表示第t次迭代時種群中的最優個體的位置；參數r1控制個體的搜索方向和步長在迭代時的影響程度；參數r2控制個體在迭代過程中的搜索距離；r3是一個隨機權重系數，決定最優個體位置對當前個體下一次迭代的影響程度；r4是控制算法進行正弦迭代或余弦迭代的轉換概率；式（19）中，a為常數（一般取2）；iter 表示當前迭代次數；T表示最大迭代次數；式（20）中，r2為(0，2π) 之間的任意常數；式（21）中，r3為(0，2) 之間的任意常數；式（22）中，r4為(0，1) 之間的任意常數。

為了更好地協調正余弦算法的全局搜索和局部開發過程，現對其進行改進。參數r1作為線性函數，不利于在算法迭代前期進行充分的全局搜索，這導致算法在后期的局部尋優能力變差。因此對參數r1進行如下調整：

與之前相比，改進后的r1使SCA 算法的全局搜索更加充分，并且利用余弦函數的數學特點，使得r1在固定的范圍內上下振蕩，更好地平衡了算法的全局搜索與局部開發過程。

3.2 反向學習策略

Haupt 等人［18］指出，初始種群的優劣會直接影響基于種群迭代的群智能優化算法整體的搜索速度和解的精度，多樣性好的初始種群有助于提高算法的優化性能［19］。然而，原始AEFA 算法在迭代前采用隨機方式初始化種群個體，這導致初始種群存在偶然性，從而在一定程度上影響了初代種群的引導效果，這會直接影響算法的收斂精度和速度。Tizhoosh 于2005 年提出的反向學習策略（Opposition - based learning，OBL）［20］，目前已被成功應用在蝗蟲優化算法（GOA）、遺傳算法（GA）、蟻群算法（ACO）和蝴蝶優化算法（BOA）等算法。反向學習策略中關于反向點的定義如下：［21］

假設在[lb，ub] 中存在數x，則x的反向點定義為x′=lb+ub-x。將反向點的定義擴展到D維空間，設p=(x1，x2，…，xD) 為D維空間中的一個點，其中xi∈[lbi，ubi]，i= 1，2，…，D，則其反向點

3.3 精英個體保留策略

在種群進行迭代更新時，為確保精英個體即適應度好的個體進入下一代循環，采用精英個體保留策略。［22］從第二次種群迭代開始，每次迭代結束后，均對新一代種群計算反向點。將新一代種群與其反向點進行種群合并操作，并計算適應度值，用適應度好的個體替換適應度差的個體，使得子代精英個體作為父代繼續迭代。這可以在一定程度上提高算法的收斂精度。

3.4 柯西擾動策略

柯西擾動策略［23］又稱柯西變異，源自柯西分布。一維柯西分布概率密度如下：

當a= 1 時，上式稱為標準柯西分布。圖4 為高斯分布與柯西分布的曲線對比圖。

圖4 兩種分布的概率密度曲線對比

從圖4 可以看出，柯西分布逼近于0 的過程相對平穩，比高斯分布更慢，而且在原點附近的峰值也比高斯分布更小。綜上所述，柯西分布可以在計算中產生更強的擾動能力。將柯西變異引入目標位置的更新方式中，利用柯西分布產生的隨機數改變當前迭代的最優值，提高算法的全局搜索能力和脫離局部最優能力。［24］

式（25）中，cauchy (0，1) 為標準柯西分布?？挛鞣植茧S機變量生成函數為

3.5 算法結構

基于上述分析，本文設計的改進人工電場算法（IAEFA）流程如圖5 所示。算法步驟如下：

圖5 算法流程圖

1）初始化種群及各項參數，并計算種群反向點，擇優保存；

2）計算全局最優值（柯西擾動策略）和最差值；

3）在迭代前期使用改進的SCA 迭代機制，在迭代后期使用AEFA 迭代機制；

4）獲得新種群，計算反向點，使用精英個體保留策略擇優保存；

5）若算法達到最大迭代次數，則輸出最優解；反之，算法跳回步驟2）。

4 算例仿真和結果分析

假設在有28 個需求點的某一區域內，經決策需選取6 個需求點作為配送中心向其他需求點運輸貨物，表1 為每個需求點的位置及需求信息。進行算例仿真時設置人工電場算法的種群規模N= 50，最大迭代次數T= 30。使用軟件：MATLAB R2018a，運行環境為64 位Windows 11 操作系統，計算機硬件參數：處理器類型為AMD Ryzen 5 3500U。機帶RAM 為12.0 GB，64 位操作系統。

表1 需求點坐標及需求量

為保證實驗結果的有效性，針對該MDLP 問題，將AEFA 算法和IAEFA 算法獨立運行10 次，結果如表2～表3、圖6～圖7 所示。

圖6 選址方案對比

圖7 尋優曲線對比

表2 AEFA 和IAEFA 實驗結果對比

表3 選址方案及配送方案對比

由表2 可知，在10 次獨立實驗中，AEFA 算法的最小費用為6347.2，IAEFA 算法的最小費用為6020.9，與AEFA 相比，IAEFA 的最小費用節省了326.3。圖7的尋優曲線也表明，不論是最優值還是平均值，IAEFA 算法計算結果的都比AEFA 算法的結果更小，這說明了本文算法的改進方式具有一定的性能優勢。

將人工魚群算法（AFSA）、文獻［11］、人工電場算法（AEFA）和本文的改進算法（IAEFA）應用于上述MDLP 問題，四種算法的對比結果如表4 所示。

表4 性能對比

由表4 可以看出，在最優值方面，IAEFA 算法的計算結果是6020.9，比其他三種算法節約了313.1 以上；在平均值方面，IAEFA 算法的計算結果是6192.31，比其他三種算法節約了265.69 以上，說明IAEFA 算法具有更高的求解精度；在標準差方面，IAEFA 算法的結果是114.61，相比于其他三種算法具有一定的穩定性；在平均收斂代數方面，雖然IAEFA算法不是最快的，但仍然比AESA 算法和文獻［11］快了3 代以上。綜上所述，在解決多配送中心選址問題上，IAEFA 算法具有較高的搜索性能。

5 總結

本文針對多配送中心選址問題，提出了一種改進人工電場算法（IAEFA）。該算法在初始化種群時，利用反向學習策略，以提高初始種群規模的方式增加多樣性，從而使算法的第一代種群具有更好的引導效果；在計算全局最優值時，引入柯西擾動策略，改變每次迭代時最優個體的位置，避免了算法出現過早收斂的情況；在迭代過程中，引入正余弦迭代機制以平衡算法的全局搜索和局部開發過程；在每一次迭代結束后，引入反向學習策略和精英個體保留策略，不僅提高了種群的多樣性，還確保每次迭代后都是好的結果替換差的結果，大幅度提高了算法的收斂精度。通過仿真案例表明，相比于原始人工電場算法、人工魚群算法和文獻［11］中的ALMM-AFSA 算法，本文提出的IAEFA 算法在求解多配送中心選址問題時具有更好的性能。但是，由于多配送中心選址模型的建立基本處在理想情況下，因此，對于更符合真實環境，具備更高實際參考價值的選址模型是今后進一步的研究工作。除此之外，國內外對人工電場算法的改進研究仍處在初期階段，算法性能尚未被完全發掘，仍具有較大的提升空間，因此進一步開發人工電場算法的性能優勢，分析算法的性能特點是今后深入研究的另一重要方面。