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

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

基于PBIL算法的物流中心選址問(wèn)題研究

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

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

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

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

1 引 言

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

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

2 PBIL算法簡(jiǎn)述

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

2.1 PBIL算法基本原理

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

基于二進(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隨機(jī)產(chǎn)生N個(gè)個(gè)體；

檢驗(yàn)并計(jì)算每個(gè)個(gè)體的適應(yīng)度值；

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

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

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

k++；｝

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

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

2.2 PBIL算法與遺傳算法

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

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

3 PBIL算法求解物流中心選址問(wèn)題

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

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

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

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

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

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

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

表1 需求點(diǎn)坐標(biāo)和運(yùn)輸成本

（1）確定物流中心選址問(wèn)題的編碼方案。

100表示成二進(jìn)制為1100100，50表示成二進(jìn)制為110010，則共需要13個(gè)基因位。將染色體表示成一個(gè)基因序列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隨機(jī)產(chǎn)生N個(gè)個(gè)體，判斷每一個(gè)個(gè)體是否滿足公式（2）的約束條件，若不滿足，則將此個(gè)體丟棄，再隨機(jī)產(chǎn)生一個(gè)新的個(gè)體。

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

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

［4］ 胡琨元，朱云龍，汪定偉.自適應(yīng)PBIL算法求解合同優(yōu)化匹配問(wèn)題［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

·微機(jī)應(yīng)用·