配送中心選址的自適應Levy分布混合變異魚群算法

費 騰 張立毅 孫云山

(天津商業大學信息工程學院 天津 300134) (天津大學電子信息工程學院 天津 300072)

配送中心選址的自適應Levy分布混合變異魚群算法

費 騰 張立毅*孫云山

(天津商業大學信息工程學院 天津 300134) (天津大學電子信息工程學院 天津 300072)

在建立配送中心選址模型的基礎上，提出一種解決配送中心選址的自適應Levy分布混合變異人工魚群算法。該算法將公告板的歷史最優魚個體代替當前魚群中最差魚個體，形成中間魚群。在中間魚群中，對歷史最優魚個體進行混沌變異，其他魚個體進行Levy變異。Levy變異的引入，對于算法跳出局部最優解起到更好的引導作用，保持了魚群的多樣性。混沌變異的引入，增強了算法局部搜索的能力，保證了算法后期的收斂速度。通過算例仿真表明，Levy分布混合變異人工魚群算法比基本魚群算法更能有效解決配送中心選址問題，尋找到更低的費用成本。

人工魚群算法 Levy分布 混沌 變異 配送中心選址

0 引 言

配送中心的選址作為物流系統的極其重要組成部分，居于重要的樞紐地位，其規劃的好壞直接關系到整個物流系統規劃的成敗[1-2]。在物流系統分析與設計時，物流配送中心選址常需要得到模型化、數量化的支持[3]。物流配送中心選址模型主要分為單一配送中心選址模型及多配送中心選址模型兩種。單一配送中心模型求解方法主要包括重心法，交叉中值法，因素分析法及層次分析法等。多配送中心選址模型的求解方法主要包括混合0-1規劃法、CFLP法、P中值法等。近些年由于智能算法的飛速發展，且配送中心選址問題屬于離散的組合優化問題, 具有NP性質，學者們開始將智能算法運用到物流配送中心選址中。2008年，劉倩[4]用模擬退火算法的迭代得到了配送中心選址模型的最優解，通過實例驗證了模擬退火算法對于物流系統的優化具有一定的實用價值。2010年，郝棟梁等[5]在建立配送中心選址數學模型的基礎上，利用遺傳算法求解配送中心選址問題，并通過具體算例進行驗證。同年，許婷等[6]將 GIS 和蟻群算法結合，在解決最短路徑問題上得到了較好的效果，并基于該最短路徑構建了選址運輸費用模型，使選址運輸費用分析更接近實際運輸環境。2013年，瞿斌等[7]依照更具有現實意義的“加工廠—配送中心—用戶”的模式建立物流配送中心連續型選址模型，并針對較大規模的選址問題提出改進粒子群求解算法。近些年來，不斷有學者對于配送中心選址問題的解決提出大量的改進算法，但基本都局限于上述提及的粒子群算法、退火算法、遺傳算法及蟻群算法的改進上，而極少有魚群算法及其改進算法應用于配送中心選址問題上。

本文是在建立配送中心選址模型的基礎上，提出了一種解決配送中心選址的自適應Levy分布混合變異人工魚群算法。該算法將公告板記錄的歷史最優魚個體代替當前魚群中最差魚個體，形成中間魚群。在中間魚群中，對歷史最優魚個體進行混沌變異，其他魚個體進行Levy變異。由于Levy分布具有厚尾特性，使得Levy變異擾動作用更將強烈，對于算法跳出局部最優解起到更好的引導作用，保持了魚群的多樣性。混沌變異的引入，增強了算法局部搜索的能力，保證了算法后期的收斂速度。通過算例仿真表明，Levy分布混合變異人工魚群算法比基本魚群算法更能有效解決配送中心選址問題，尋找到更低的費用成本。

1 配送中心選址問題

配送中心選址模型所要解決的問題是已知有n個需求點的前提下，要在其中設定m個配送中心，使得選定的配送中心與其配送范圍內的需求點之間的運輸費用最小。

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

(1) 配送中心的供應量總可以滿足需求點的需求，并由其配送范圍內的需求量決定；

(2) 一個需求點有且僅有一個配送中心配送；

(3) 只考慮一級運輸情況，即只考慮從配送中心到需求點的費用，不考慮從工廠到配送中心的費用。

故建立如下模型[8]：

(1)

式(1)為目標函數，其目標為從選擇的配送中心到其配送范圍的需求點的運輸費用最小。其中，Z表示運輸費用，m表示配送中心的個數，n表示需求點的個數，Dk表示需求點的需求量，djk表示配送中心j到需求點k的距離。yjk是0-1變量，當yjk取值為1時，表示需求點k由配送中心j配送。

(2)

式(2)確保每個需求點僅有一個配送中心配送。J表示配送中心集合，{j|j=1,2,…,m}，K表示需求點集合，{k|k=1,2,…,n}。

(3)

式(3)表示選擇配送的個數為P。zj為0-1變量，當zj取值為1時，選擇j為配送中心。P表示選擇配送中心的個數：

yjk≤zjj∈Jk∈K

(4)

式(4)確保每個需求點必然有與之對應的配送中心。

yjk∈{0,1}j∈Jk∈K

(5)

zj∈{0,1}j∈J

(6)

式(5)、式(6)為yjk及zj的定義式。

2 自適應Levy分布混合變異魚群算法

2.1 人工魚群算法AFSA

基本魚群算法數學模型如下：

用X=(x1,x2,…,xn)來描述各個人工魚的位置，用Y=f(x)來描述當前人工魚所在位置的食物濃度，其中xi為尋優變量，Y為尋優的目標。δ表示擁擠度因子；step表示人工魚移動的步長；Trynumber表示人工魚每次覓食最大的試探次數。

人工魚的當前位置為xi，在視野允許范圍內隨機選擇下一個位置xj，假設在處理極小值問題中Yi>Yj，則向xj方向前進一步，否則重新隨機選擇xj，再次判斷是否滿足前進條件[9]。若反復次數達到嘗試次數Try_number時，隨機游動一步。

(7)

式中，rand()為(0,1)的隨機數。

(2) 聚群行為

人工魚當前位置為xi，其食物濃度為Yi，在其視野允許的范圍內的伙伴數量為nf，若Yc/nf>δYi，表示伙伴中心位置Xc的食物濃度較高，且周圍處在不擁擠狀態，則人工魚向中心位置Xc前進一步，否則執行覓食行為[10]。

(8)

(3) 追尾行為

人工魚的當前位置為xi，其食物濃度為Yi，在其視野允許范圍內能夠尋找到的食物濃度最高時的人工魚位置為xmax，若Ymax/nf>δYi，表示處于xmax位置的人工魚具有較高的食物濃度，且周圍不擁擠，可以向xmax位置前進一步，否則執行覓食行為。

(9)

2.2 自適應Levy分布混合變異魚群算法ALMM-AFSA

自適應Levy分布混合變異人工魚群算法主要用于克服在基本魚群算法后期，大部分人工魚個體容易聚集在局部最優附近而非在全局最優附近聚集，或者人工魚個體漫無目的的隨意游走，使得整個基本魚群算法全局搜索受限，陷入局部最優，嚴重影響到算法的搜索精度、收斂速度及穩定性等方面[11]。自適應Levy分布混合變異人工魚群算法改進的核心思想是當基本人工魚群算法在非全局最優嚴重聚集時，用公告板上的記錄的歷史最優魚個體替代當前狀態下的最差魚個體，形成中間魚群。對中間魚群中的歷史最優魚個體采取混沌變異，其他魚個體采取Levy變異。采取混沌變異的作用是使得改進算法在跳出局部最優的束縛的同時增強局部搜索的能力。對其他魚個體采取Levy變異的作用是增加人工魚的多樣性，提高全局搜索的能力，引導人工魚向歷史最優魚的方向移動，從而使基本魚群算法在搜索精度、收斂速度及穩定性等方面的能力得到增強。

(1)Levy分布

按比例分配是在實際生活中經常碰到的問題，它的數學意義就是應用比把一個數量按照一定的比例來進行分配，在教學中可以結合實際創設合適的情境，通過一些生產、生活中的實例來呈現教學內容，既能吸引學生，激發學生的學習興趣，又能讓學生體驗按比例分配的數學意義，體會數學來源于生活而又服務于生活的辯證思想。

在19世紀30年代Levy[12]提出Levy分布，式(10)為其概率密度函數。

(10)

其中，α，γ為Levy分布的兩個特征參數。0<α≤2，γ>0。α用來控制分布圖形的銳度，γ用來控制分布的尺度單位。當α=2時，Levy分布等同于高斯分布，當α=1時，Levy分布等同于柯西分布[13]。對于一般的α取值，通過Levy分布的概率密度函數分析起來比較困難，所以利用數值模擬算法來產生Levy分布隨機數[14]。

假設產生兩個獨立同分布的隨機變量x、y，其標準差分別為σx、σy。σx和σy取決于參數α，且相互影響。因此，令σy=1，則σx只受參數α的影響。如下產生變量v：

(11)

變量w通過如下非線性變換用以服從Levy分布：

(12)

為了獲得尺度單位因子γ不為1的Levy分布，做如下線性變換：

(13)

其中，σx、K(α)以及C(α)的值可以通過文獻[15]查表得到。根據上述步驟得到的分布能夠快速準確地收斂于Levy分布。

(2) 傳統變異

(14)

(15)

(16)

(17)

其中，j=1,2,…,m，N(0,1)用于產生個體的高斯分布隨機數，Nj(0,1)用于產生每個分量的新的高斯分布隨機數。文獻[16]給出了參數τ和τ′的定義，即：

(18)

(19)

(3)Levy變異

在傳統變異中，式(16)中δj(t)選取不同分布的隨機數時，會產生不同的變異算子。

當δj(t)為Levy分布隨機數時，式(16)演變為Levy變異算子，即：

(20)

其中，Lj(t)為服從Levy分布的隨機數。

(4) 混沌變異

與Levy分布類似，當δj(t)為混沌隨機序列產生的隨機數時，式(16)演變為混沌變異算子，即：

(21)

其中，Hj(t)為在[-2,2]區間按照混沌規律變化的序列產生的隨機數[17]。混沌序列一般采用一維Logistic映射：

Zk+1=μZk[1-Zk]Zk∈[0,1]

(22)

式中，μ為控制參數，取值為[3.56,4]；當μ=4、0≤Zk(0)≤1時，Logistics映射完全處于混沌狀態[18]，歷遍性最強。Hj(t)為通過Zk放大平移后得到。

3 求解流程

步驟1 進行魚群初始化。設置人工魚群的規模、初始位置設置、視野、步長、擁擠度、試探次數、最大迭代次數、Levy變異的特征參數及混沌變異的控制參數等，產生初始魚群。讀取需求點的坐標，計算各個需求點之間的距離。設置選擇的配送中心的個數。

步驟2 進行公告板初始化。計算各個初始人工魚個體當前的狀態值，利用公告板將最優的費用值記錄下來，進行公告板初始化。

步驟3 進行魚群行為選擇。各個人工魚分別進行追尾行為和聚群行為，評價兩種行為后的值，選擇值較小的行為作為實際執行的行為，缺省行為是覓食行為[19]。

步驟4 進行公告板更新。一次迭代以后，若魚群中的最優魚的費用值大于公告板所記錄的費用值，進行公告板的更新替代。

步驟5 判斷是否變異。如果公告板上記錄的最優費用值在連續多次迭代執行后仍沒有改變，且連續的次數達到未改變次數的最大時，執行步驟6；否則執行步驟7。

步驟6 進行變異操作。人工魚群體中的最差費用個體被公告板上記錄的最優費用個體代替，形成一個父代中間種群。在中間魚群對歷史最優魚進行混沌變異，其他魚進行Levy變異。計算最優費用值與公告板比較，若優，表明變異成功，更新公告板，同時設置公告板未改變次數為0，執行步驟7；否則，重新變異，若達到最大變異次數時仍不成功就采用最后一次的變異，執行步驟7。

步驟7 記錄最小費用及各個配送點的配送范圍。

步驟8 判斷是否算法終止。判斷是否已達到最大迭代次數，若不滿足，執行步驟3，否則執行步驟9。

步驟9 算法終止，輸出最小費用值及配送方案。

4 算例仿真

假設有28個需求點，從其中選出6個作為配送中心。每個需求點的坐標及需求量如表1所示。設置人工魚個數為100，嘗試次數為100，人工魚的視野為100，擁擠度因子為0.618，人工魚移動的最大步長為9，Levy分布的特征參數α為0.8，尺度因子γ為2，混沌變異的控制參數為4，最大迭代次數為30。

表1 需求點坐標及需求量

表2為利用AFSA解決配送中心選址問題的10次運行結果，表3為利用ALMM-AFSA解決配送中心選址問題的10次運行結果。表4為AFSA選擇配送中心及配送的具體方案。表5為ALMM-AFSA選擇配送中心及配送的具體方案。表6為AFSA與ALMM-AFSA在配送中心選址分配問題上的性能對比表。

表2 采用AFSA所得實驗結果

表3 采用ALMM-AFSA所得實驗結果

表4 AFSA選址方案

表5 ALMM-AFSA選址方案

表6 性能對比表

圖1為AFSA選址方案圖，圖2為ALMM-AFSA尋址方案圖，圖3為AFSA與ALMM-AFSA尋優曲線對比圖。

圖1 AFSA尋址方案

圖2 ALMM-AFSA尋址方案

圖3 尋優曲線對比圖

算例仿真表明，在費用方面，AFSA的最小費用為6783，ALMM-AFSA的最小費用為6334，最小費用節省了6.65%。AFSA的平均費用為7068.5，ALMM-AFSA的平均費用為6458，平均費用節省8.64%。由此可以看出，ALMM-AFSA在求解配送中心選址問題中能夠尋找到更低的費用，提高費用利用率。在終結代數方面，AFSA的平均終結代數為21.2，ALMM-AFSA的平均收斂代數為9.1。由此可見，ALMM-AFSA具有更好的收斂速度。在標準差及差的平均值方面，AFSA的標準差及差的平均值為334.74和285.5，ALMM-AFSA的標準差及差的平均值為95.28和123.9。由此可見，ALMM-AFSA在解決配送中心選址問題上穩定性更好。

5 結 語

本文提出了一種新的解決配送中心選址的算法——自適應Levy分布混合變異人工魚群算法。該算法在基本魚群算法陷入局部最優時引入Levy變異和混沌變異，通過變異來增加魚群跳出局部最優的能力，增加魚群的多樣性，從而達到全局尋優的目的。通過實驗仿真表明，該算法相比于基本魚群算法更適合求解配送中心選址問題。但是，由于配送中心模型建立基本處在理想情況下，因此，對于更適合實際環境的配送中心模型的建立是今后進一步研究的方向。除此之外，由于對于魚群算法的改進研究仍處在初期階段，因此，對于改進魚群算法的研究是今后研究的另一個方向。

[1] 李云清.物流系統規劃[M].上海:同濟大學出版社,2004.

[2] 胡雙增,張明.物流系統工程[M].北京:清華大學出版社,2000.

[3] 秦固.基于蟻群優化的多物流配送中心選址算法[J].系統工程理論與實踐,2006(4):120-124.

[4] 劉倩.模擬退火算法在配送中心選址的應用[J].交通標準化,2008(8):147-149.

[5] 郝棟梁,汝宜紅,徐秀全.遺傳算法在配送中心選址的應用[J].物流技術,2010(7):75-77.

[6] 許婷,盛明,婁彩榮.基于GIS和蟻群算法的物流配送中心選址研究[J].測繪科學,2010,35(6):206-208.

[7] 瞿斌,陸柳絲.種群規模自適應粒子群在配送中心連續型選址中的應用[J].運籌與管理,2013,22(3):102-108.

[8] 史峰,王輝,郁磊,等.Matlab智能算法30個案例分析[M].北京:北京航空航天大學出版社,2011.

[9] 吳姍姍,黃友銳.基于改進人工魚群算法的PID控制器參數優化[J].安徽理工大學學報:自然科學版,2013,33(2):23-26,55.

[10] 潘喆,吳一全.二維Ostu圖像分割的人工魚群算法[J].光學學報,2009,29(8):2115-2121.

[11] 張創業,莫愿斌,何登旭,等.混沌協同人工魚粒子群混合算法及其應用[J].計算工程與應用,2010,46(32):48-51,54.

[12] Levy P.Théorie de l’Addition des Variables Aléatoires[M].Paris:Gauthier-Villars,1937.

[13] 唐洪,邱天爽,李婷.非高斯alpha穩定分布環境中自適應濾波及研究進展[J].系統工程與電子技術,2005,27(8):1336-1341.

[14] Lee C Y,Yao X.Evolutionary programming using mutations based on the Levy probability distribution[J].IEEE Transactions on Evolutionary Computation,2004,8(1):1-13.

[15] Mantegna R N.Fast,accurate algorithm for numerical simulation of Levy stable stochastic processes[J].Physical Review E,1994,49(5):4677-4683.

[16] B?ck T,Schwefe H P.An overview of evolutionary algorithms for parameter optimization[J].Evolutionary Computation,1993,1(1):1-23.

[17] 駱晨鐘,邵惠鶴.采用混沌變異的進化算法[J].控制與決策,2000,15(5):557-560.

[18] 高尚.旅行商問題的混沌蟻群算法[J].系統工程理論與實踐,2005(9):100-104,125.

[19] 陳廣洲,汪家權,李傳軍,等.一種改進的人工魚群算法及其應用[J].系統工程,2009,27(12):105-110.

[20] 王東升.赤峰電網無功優化規劃方案研究[D].北京:華北電力大學,2008.

RESEARCH ON MIXED MUTATION ARTIFICIAL FISH SWARM ALGORITHM BASED ON ADAPTIVE LEVY DISTRIBUTION OF THE DISTRIBUTION CENTER LOCATION

Fei Teng Zhang Liyi*Sun Yunshan

(SchoolofInformationEngineering,TianjinUniversityofCommerce,Tianjin300134China) (SchoolofElectronicInformationEngineering,TianjinUniversity,Tianjin300072,China)

Based on the establishment of distribution center location model, the adaptive Levy distribution mixed mutation artificial fish swarm algorithm for solving distribution center location is proposed. In the improved algorithm, the worst individual of the current fish is replaced by the best individual fish of bulletin board toformat theintermediate fish swarm. In the middle swarm, the best individual fish is to carry out the chaotic variation, and the other fish individuals is to carry out Levy variation. The introduction of Levy mutation plays a better role in guiding the algorithm out of local optimal solution, and increases the diversity of fish.Besides,the introduction of chaos mutation enhances the local search ability of the algorithm and guarantees the convergence rate of the algorithm. The simulation results show that the adaptive Levy distribution mixed mutation artificial fish swarm algorithm are more effectively than artificial fish swarm algorithm to solve the distribution center location problem and find the lower cost.

Artificial fish swarm algorithm Levy distribution Chaos Mutation Distribution center location

2015-10-29。國家軟科學研究計劃項目(2014GXS4D089)；天津市高等學校科技發展基金計劃項目(20110709)；天津市科技特派員項目(15JCTPJC63000)；中國物流學會項目(2014CSLKT3-16)。費騰，實驗師，主研領域：智能計算。張立毅，教授。孫云山，副教授。

TP391.1

A

10.3969/j.issn.1000-386x.2017.01.046