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

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

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

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

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

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

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

PBIL算法；進(jìn)化計算；遺傳算法；物流中心選址

1 引 言

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

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

2 PBIL算法簡述

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

2.1 PBIL算法基本原理

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

基于二進(jìn)制編碼的PBIL算法處理流程如下：

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

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

（3）while（k＜MG）

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

檢驗并計算每個個體的適應(yīng)度值；

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

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

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

k++；｝

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

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

2.2 PBIL算法與遺傳算法

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

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

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

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

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

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

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

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

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

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

表1 需求點坐標(biāo)和運輸成本

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

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

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

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

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

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

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

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

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

3.3 實驗結(jié)果分析

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

表2 遺傳算法程序運行結(jié)果

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

表3 PBIL算法程序運行結(jié)果

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

4 結(jié)束語

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

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

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

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

［4］ 胡琨元，朱云龍，汪定偉.自適應(yīng)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

·微機應(yīng)用·