基于PBIL算法的物流中心選址問題研究

王曉波，付珊珊，吉 玲，楊 亞，張海霞

（河海大學物聯(lián)網(wǎng)工程學院，常州213022）

基于PBIL算法的物流中心選址問題研究

王曉波，付珊珊，吉 玲，楊 亞，張海霞

（河海大學物聯(lián)網(wǎng)工程學院，常州213022）

介紹了基于種群競爭式學習的PBIL算法的基本原理和實現(xiàn)方法。比較了PBIL算法和遺傳算法求解過程的異同點。分析了PBIL算法在物流中心選址問題中的應用，并且通過實例驗證了算法的可行性和有效性，證明了PBIL算法比遺傳算法具有更高的搜索效率。

PBIL算法；進化計算；遺傳算法；物流中心選址

1 引 言

隨著世界經濟的快速發(fā)展和現(xiàn)代科學技術的進步，物流行業(yè)作為國民經濟的一個新興部門，正在全球范圍內迅速發(fā)展。物流業(yè)的發(fā)展給社會生產、人們生活甚至政府職能等帶來了巨大影響，因此物流業(yè)被喻為經濟發(fā)展的“加速器”。

在物流系統(tǒng)的運作中，配送中心的選址方式往往決定著物流的配送距離和配送模式，進而影響著物流系統(tǒng)的運作效率。因此，研究物流中心選址具有重要的理論意義和現(xiàn)實應用意義。一般來說，物流中心選址模型是非凸和非光滑的帶有復雜約束的非線性規(guī)劃模型，屬于NP-hard問題。

2 PBIL算法簡述

PBIL算法是美國卡內基梅龍大學Baluja.S.提出的進化學習算法［1］，是遺傳算法和增強式學習算法的結合，它將進化視為學習過程，用學習所獲得的知識-概率模型來指導后代的產生。這種概率是整個進化過程的信息累積，同遺傳算法相比，用它來指導產生的后代將更優(yōu)生，因而在許多問題中能獲得更快的收斂速度和理想的計算結果［2］。目前PBIL算法已應用到許多實際問題中，如TSP問題、最小碼覆蓋問題［3］、合同匹配問題［4］。

2.1 PBIL算法基本原理

PBIL算法的特點是用概率向量來約束染色體中每一個基因位的取值，因此它適合用于二進制編碼求解問題。若一個染色體的編碼有n個基因位，則概率向量為P｛p1，p2，...，pn｝，0≤pi≤1，i=1，2，...，n，當pi=0.5時，第i個基因位取0或1的機會相等。

基于二進制編碼的PBIL算法處理流程如下：

（1）初始化操作。確定種群的規(guī)模N、學習因子r、變異因子rm、變異概率pm、最大迭代次數(shù)MG、概率向量P=｛0.5，0.5，...，0.5｝。

（2）k=0；k為迭代次數(shù)。

（3）while（k＜MG）

｛根據(jù)概率向量P隨機產生N個個體；

檢驗并計算每個個體的適應度值；

選出當前種群的最優(yōu)個體Vmax；

根據(jù)最優(yōu)個體Vmax更新概率向量P；

根據(jù)變異概率pm對向量P進行變異操作；

k++；｝

（4）輸出MG中適應度值最優(yōu)的個體。

（5）PBIL算法主要經過個體生成、概率向量更新和概率變異三個操作，反復執(zhí)行逐漸朝全局最優(yōu)解逼近，達到最大迭代次數(shù)時，各基因位上的學習概率值大小分別接近1或0。

2.2 PBIL算法與遺傳算法

在傳統(tǒng)的遺傳算法中，用種群表示優(yōu)化問題的一組候選解，種群中的每個個體都有相應的適應值，然后進行選擇、交叉和變異等操作，反復進行，對問題進行求解。而在PBIL算法中，沒有交叉、變異等操作，取而代之的是概率模型的學習和采樣。PBIL算法采用統(tǒng)計學習手段從群體宏觀的角度建立一個描述解分布的概率模型，然后對概率模型隨機采樣產生新的種群，如此反復進行，實現(xiàn)種群進化，直到滿足終止條件。

從兩個算法的進化原理可看出：遺傳算法的交叉、變異操作能產生更好的個體，也能產生更壞的個體，進化較為緩慢；PBIL算法通過修改概率模型參數(shù)使新的個體更優(yōu)，能快速準確地收斂到最優(yōu)解。

3 PBIL算法求解物流中心選址問題

3.1 物流中心選址問題數(shù)學模型

物流中心選址問題描述：某城市有n個需求點，需建立一個物流中心，物流中心到每個需求點的單位距離運輸成本分別為c1、c2...cn，到每個需求點的距離為d1、d2...dn，每天需向每個需求點配送一次貨物。現(xiàn)要選擇一個物流中心，使得配送成本最低。本模型將城市簡化成L乘W的長方形區(qū)域塊，物流中心和需求點的坐標均為正整數(shù)。

數(shù)學模型表示如下：

約束條件0≤x≤w，0≤y≤l

其中：x、y為物流中心的橫坐標和縱坐標，xi、yi為需求點的坐標。

3.2 算法具體實現(xiàn)

這里給出一個物流中心選址問題的實例，城市規(guī)模為100乘50，6個需求點的坐標和單位距離運輸成本見表1。

表1 需求點坐標和運輸成本

（1）確定物流中心選址問題的編碼方案。

100表示成二進制為1100100，50表示成二進制為110010，則共需要13個基因位。將染色體表示成一個基因序列G=（g1，g2，...，g13）。

（2）初始化操作，設定參數(shù)值：種群規(guī)模N= 20，最大迭代次數(shù)MG=100，學習因子r=0.1，變異概率pm=0.2，概率向量P=｛0.5，0.5，...，0.5｝。

（3）根據(jù)P隨機產生N個個體，判斷每一個個體是否滿足公式（2）的約束條件，若不滿足，則將此個體丟棄，再隨機產生一個新的個體。

（4）計算適應度值。根據(jù)公式（1）計算出每一個個體的適應度值，并從中選擇一個最優(yōu)個體。

（5）選出的最優(yōu)個體按照以下公式更新概率向量P：其中：xi為最優(yōu)個體中第i個基因位上的值，r為學習因子。

（6）生成一個0到1之間的隨機數(shù)，如果該數(shù)小于變異概率pm，對概率向量進行變異操作，公式如下：

其中：rm為變異因子，通常取rm=0.1，rand是一個0到-1之間均勻分布的隨機數(shù)。

（7）按照更新后的概率向量P重復上述操作，直到達到最優(yōu)值或最大迭代次數(shù)為止。

3.3 實驗結果分析

針對上面給出的物流中心選址問題的實例，使用matlab編寫遺傳算法和PBIL算法程序。兩個程序分別運行5次，比較它們的結果，具體數(shù)據(jù)如表2和表3所示。

表2 遺傳算法程序運行結果

遺傳算法參數(shù)設定如下：種群規(guī)模為20，最大迭代次數(shù)為200，交叉概率為0.6，變異概率為0.1，選擇操作采用“輪盤賭法”。

表3 PBIL算法程序運行結果

從5次運行結果來看，遺傳算法找到最優(yōu)解的次數(shù)為2次，PBIL算法找到最優(yōu)解的次數(shù)為4次。而且PBIL算法得到的解均小于1000。從數(shù)據(jù)上來看，PBIL算法迭代100次所找到的解明顯優(yōu)于遺傳算法迭代200次的結果。

4 結束語

對于同一個問題，PBIL算法在迭代100次后能找到一個比較令人滿意的結果，而用遺傳算法則需要迭代200次以上才能找到這樣的解。所以在收斂速度上PBIL算法優(yōu)于遺傳算法。另外，由實驗結果可以看出，PBIL算法得到的最優(yōu)解比遺傳算法要好，說明其搜索效果更好。以上證明了用PBIL算法求解物流中心選址問題比用遺傳算法求解該問題更為快速和有效，算法應用是成功的。

［1］ SBaluja.Population-based Incremental Learning［R］.Technical Report，CMU-CS-94-163，CarnegieMellon University，1994.

［2］ 金炳堯，蔚承建，何振亞.一個用于優(yōu)化搜索的學習算法［J］.軟件學報，2001，12（3）：448-453.

［3］ 林大瀛，郝志峰，舒蕾.應用基因概率學習算法求解最小碼覆蓋問題［J］.華南理工大學學報（自然科學版），2003，31（6）：67-70.

［4］ 胡琨元，朱云龍，汪定偉.自適應PBIL算法求解合同優(yōu)化匹配問題［J］.系統(tǒng)工程，2004，22（12）：87-91.

Study on the Logistics Center Location Problem Based on PBIL Algorithm

WANG Xiao-bo，F(xiàn)U Shan-shan，JILing，YANG Ya，ZHANG Hai-xia
（College of Internet of Things Engineering，Hohai University，Changzhou 213022，China）

The principle and realization of PBIL（Population-based Increased Learning）algorithm are introduced in this paper.The differences between PBIL algorithm and genetic algorithm are compared in their process.The application of logistics center location problem based on PBIL algorithm is analyzed.The feasibility and validity of improved algorithm is proved.The experiments result shown that the searching efficiency and accuracy of PBIL algorithm are higher than that of genetic algorithm.

PBIL algorithm；Evolutionary computing；Genetic algorithm；Logistics Center Location

10.3969／j.issn.1002-2279.2014.02.018

TP301.6

A

1002-2279（2014）02-0058-02

王曉波（1989-），男，江蘇徐州人，碩士研究生，主方向：智能算法。

2014-01-09

·微機應用·