（四川大學(xué) 計算機學(xué)院， 成都 610064）

摘 要：

將引入粒子群優(yōu)化算法來解決帶隨機權(quán)值、服從獨立均勻概率分布的極小化極大（1-中心）平面選址問題，對其進行實驗?zāi)M并得出了樂觀的結(jié)果。

關(guān)鍵詞：隨機權(quán)值； 選址問題； 1-中心; 粒子群優(yōu)化算法

中圖分類號：TP301.6文獻標(biāo)志碼：A

文章編號：1001-3695(2009)04-1308-03

Random weighted location problem with particle swarm optimization algorithm

ZENG Hua-hua， TANG Ning-jiu， DENG Min-hui， LING Yan-xia

(College of Computer， Sichuan University， Chengdu 610064， China)

Abstract:

This paper introduced PSO algorithm to solve weighted minimax (1-center) location problem in the plane when the weights were not given but rather drawn from independent uniform distributions Implemented experimental simulations. and achieved optimistic results.

Key words：random weighted; location problem; 1-center; particle swarm optimization(PSO)

選址是最重要的長期決策之一，選址的好壞直接影響到服務(wù)方式、服務(wù)質(zhì)量、服務(wù)效率、服務(wù)成本等，從而影響到利潤和市場競爭力，甚至決定了企業(yè)的命運。好的選址會給人民的生活帶來便利，降低成本，擴大利潤和市場份額，提高服務(wù)效率和競爭力；差的選址往往會帶來很大的不便和損失，甚至是災(zāi)難。所以，選址問題的研究有著重大的經(jīng)濟、社會和軍事意義。

粒子群優(yōu)化(PSO) 算法是近年發(fā)展起來的一種新的進化算法，其思想來源于人工生命和演化計算理論，屬于進化算法的一種。它從隨機解出發(fā)，通過迭代尋找最優(yōu)解，并通過適應(yīng)度來評價解的品質(zhì)。PSO通過粒子追隨自己找到的最好解和整個群的最好解來完成優(yōu)化，它通過追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu)。該算法簡單易實現(xiàn)， 可調(diào)參數(shù)少且效率高，因而得到廣泛研究和應(yīng)用。經(jīng)過研究發(fā)現(xiàn)，粒子群算法可極好地適用于對帶隨機權(quán)值的平面選址問題的處理。

1 平面選址及粒子群優(yōu)化原理

1.1 平面選址

1909年，Weber研究了在平面上確定一個倉庫的位置使得倉庫與多個顧客之間的總距離最小的問題(Weber問題)，標(biāo)志著選址理論研究的開始。1964年，Hakimi[1]提出了網(wǎng)絡(luò)上的P-中值問題與P-中心問題，這篇具有里程碑意義的論文大大激發(fā)了選址問題的理論研究。

本文將考慮的是服從概率分布的極小化極大（1-中心）平面選址問題。在平面內(nèi)分布若干需求點，其權(quán)值均不確定，且假設(shè)每個權(quán)值都在一個區(qū)間內(nèi)服從均勻分布。均勻分布更易于分析并可以作為其他分布的一個近似值。

1-中心選址問題主要應(yīng)用于緊急事件機構(gòu)的選址，如消防機構(gòu)、醫(yī)院、疫情檢查站等。1857年，Sylvester首先對平面內(nèi)無權(quán)值實例的1-中心問題進行了研究；而Elzinga和Hearn在1972年首次提出了有效解決方案。此類緊急事件機構(gòu)選址的目標(biāo)是：使其到所有需求點的最大距離最小化，因為作者總是希望能對最遠的需求點提供盡可能好的服務(wù)。帶權(quán)值的1-中心問題在1982年由Hearn和Vijay解決。然而在這些模型中，權(quán)值都被假定為確定而非隨機的。

1996年，F(xiàn)rank首次引入了帶隨機權(quán)值網(wǎng)絡(luò)選址問題，即1-中值和1-中心問題。1-中值問題的目標(biāo)是找到某點使帶權(quán)值的總距離大于等于某個預(yù)定值的概率最小化；1-中心問題的目標(biāo)則是找到某點使設(shè)施到需求點的最大權(quán)值距離大于等于某個預(yù)定值的概率最小化。

1977年，Wesolowsky引入平面內(nèi)帶隨機權(quán)值的選址問題。更多隨機權(quán)值模型請參考文獻[2]。

1.2 粒子群優(yōu)化算法

1995 年Eberhart等人提出了一種新的算法，即粒子群優(yōu)化(PSO) 算法。這種算法以其實現(xiàn)容易、精度高、收斂快等優(yōu)點引起了學(xué)術(shù)界的重視，并且在解決實際問題中展示了其優(yōu)越性。Reynolds在對鳥群飛行的研究發(fā)現(xiàn)，鳥僅是追蹤它有限數(shù)量的鄰居，但最終的整體結(jié)果是整個鳥群好像在一個中心的控制之下，即復(fù)雜的全局行為是由簡單規(guī)則的相互作用引起的。PSO 即源于對鳥群捕食行為的研究， 一群鳥在隨機區(qū)域內(nèi)搜尋食物，若此區(qū)域里只有一塊食物，那么找到食物的最簡單最有效的策略就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO 算法就是從這種思想中得到啟示而產(chǎn)生的，并用于解決優(yōu)化問題。

如上所述，PSO模擬鳥群的捕食行為。PSO中，每個優(yōu)化問題的解都是搜索空間中的一只鳥，本文稱之為粒子。所有的實例都有一個由被優(yōu)化的函數(shù)決定的適應(yīng)值，每個粒子還有一個速度決定它們飛翔的方向和距離；然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索PSO 初始化為一群隨機粒子(隨機解)；最后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己。第一個就是粒子本身所找到的最優(yōu)解，這個解稱為個體極值pbest；另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值gbest。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。

在找到這兩個最優(yōu)值時，粒子根據(jù)式(1)(2)來更新自己的速度和新的位置。粒子i 的信息可以用D維向量表示， 位置表示為Xi=(xi1，xi2，…，xid)T，速度為Vi=(vi1，vi2，…，vid)T，其他向量類似。則速度和位置更新方程為

vk+1id=vkid+c1randk1(pbestkid-xkid)+c2randk2(gbestkd-xkid)(1)

xk+1id=xkid+vk+1id(2)

式（1）是粒子i 在第k 次迭代中第d 維的速度。c1、c2是學(xué)習(xí)因子，分別調(diào)節(jié)向全局最好粒子和個體最好粒子方向飛行的最大步長。若太小，則粒子可能遠離目標(biāo)區(qū)域，若太大則會導(dǎo)致突然向目標(biāo)區(qū)域飛去，或飛過目標(biāo)區(qū)域。合適的c1、c2可以加快收斂且不易陷入局部最優(yōu)，通常令c1=c2= 2。rand1，2是[ 0 ，1 ] 間的隨機數(shù)。xkid是粒子i 在第k 次迭代中第d 維的當(dāng)前位置。pbestid是粒子i 在第d 維的個體極值點的位置(即坐標(biāo)) ；gbestd是整個種群在第d 維的全局極值點的位置。為防止粒子遠離搜索空間，粒子的每一維速度vd都會在[-vd max，+vd max]中。vd max太大，粒子將飛離最好解，太小則會陷入局部最優(yōu)。

這里只簡要介紹平面選址和粒子群優(yōu)化算法的相關(guān)原理及背景，更加詳細的定量描述將在下部分?jǐn)⑹觥?/p>

2 問題描述及算法設(shè)計

2.1 問題描述

設(shè)wi為需求點i ( i=1，2， … ，n)發(fā)出的服務(wù)需求信息。進一步假設(shè)wi為獨立均勻的隨機變量，且wi∈[ai，bi]。本文用di(X)表示需求點i 到點X=(x，y)的歐幾里德距離?，F(xiàn)在本文的目標(biāo)就是找到工廠的一個最佳距離，使此工廠到需求點的最大權(quán)值距離超過閾值T 的概率最小。設(shè)工廠和所有需求點間最大的權(quán)值距離為MAX，因為筆者假設(shè)權(quán)值是隨機變量，所以MAX將服從某一概率分布，設(shè)其為均勻分布。那么，給定隨機變量最大權(quán)值距離MAX一個區(qū)域MAX，有

P(MAX≥T)=P(maxi=1，2，…，n{widi(X)}≥T)=

1-Πni=1P(wi≤T/di(X))(3)

由于wi為[ai，bi]內(nèi)的均勻隨機變量，則

P(wi≤T/di(X))=（T-di(X)ai）/di(X)ai＜T＜di(X)bi

(di(X)(bi-ai))

1T≥di(X)bi

0T≤di(X)ai(4)

現(xiàn)在本文的目標(biāo)就是最大化F(X)：

F(X)=Πni=1P(wi≤T/di(X))(5)

對于某些i，有aidi(X)≥T，那么P(wi≤T/di(X))=0，且F(X)=0，下列引理有效。這里只給出引理，對所有引理的證明詳見的文獻[3]。

引理1如果minx{max1≤i≤n{aibi(X)}}≥T，那么平面內(nèi)所有點都為式(3)的解，且最佳值為0。

引理2minx{max1≤i≤n{bidi(X)}}≤T，此問題為極小化極大問題，式(3)有最佳解1。

2.2 算法設(shè)計

1)初始化

初始化搜索點的位置及其速度。通常是在允許的范圍內(nèi)隨機產(chǎn)生，每個粒子的pbest 坐標(biāo)設(shè)置為其當(dāng)前位置，且計算出其相應(yīng)的個體極值(即個體極值點的適應(yīng)度值)；全局極值(即全局極值點的適應(yīng)度值) 就是個體極值中最好的，記錄該最好值的粒子序號，并將gbest設(shè)置為該最好粒子的當(dāng)前位置。

2） 評價每一個粒子

計算粒子的適應(yīng)度值，如果好于該粒子當(dāng)前的個體極值，則將pbest設(shè)置為該粒子的位置，且更新個體極值。如果所有粒子的個體極值中最好的好于當(dāng)前的全局極值，則將gbest設(shè)置為該粒子的位置，記錄該粒子的序號，且更新全局極值。

3）粒子的更新

對每一個粒子的速度和位置進行更新。

4）檢驗是否符合結(jié)束條件

如果當(dāng)前的迭代次數(shù)達到了預(yù)先設(shè)定的最大次數(shù)(或達到最小錯誤要求)，則停止迭代，輸出最優(yōu)解；否則轉(zhuǎn)到2)。

2.2.1 相關(guān)數(shù)據(jù)結(jié)構(gòu)

public class particle {private point position;/*粒子當(dāng)前所在的位置，在本問題中即為平面坐標(biāo)點*/

private particlevelocity velocity; /*粒子當(dāng)前的速度，包括水平方向和垂直方向*/

private point bestposition;// 粒子所經(jīng)過的最佳位置

private double fitness;// 粒子的適應(yīng)度

public double bestfitness;//該粒子所得到的最佳適應(yīng)度

}

2.2.2 PParticle算法

輸入： 需求點集合，閾值T

gbestfitness/*全局變量，記錄種群最佳適應(yīng)度 */

gbestpostion/*全局變量，記錄當(dāng)前整個種群得到的最佳位置*/

a)粒子群初始化;

b)對粒子群中的每個粒子P執(zhí)行c);

c)更新P的位置，如果得到新位置的適應(yīng)度f 高于P的最好適應(yīng)度， 則p. bestfitness=f；

d)用f與種群最佳適應(yīng)度gbestfitness 比較，如果f大于種群最佳適應(yīng)度，gbestfitness=f；

e)返回b)直到停止條件滿足(停止條件可以是進化時間或者進化代數(shù)等)。

其中c)中計算適應(yīng)度是根據(jù)輸入的閾值T，通過適應(yīng)度計算函數(shù)(式(3))得到粒子的適應(yīng)度。

3 實驗分析

本文采用單元格內(nèi)隨機產(chǎn)生的點，簡單起見，僅用10個點(為作比較，10點均取自Berman[3])，其坐標(biāo)如表1所示； Berman[3]結(jié)果與本文得出的結(jié)果分別如表2、3所示。



表3 實驗數(shù)據(jù)對照

data of PParticle

TP(MAX≤T)xy

1.000.725 6490.498 5010.476 238

0.950.478 2360.519 5500.491 279

0.900.293 7380.532 7140.512 975

0.850.163 9260.530 2880.537 126

0.800.064 9620.524 0570.546 050

0.750.021 3910.510 9460.534 696

實驗中，將學(xué)習(xí)因子取c1=c2=2.5。w為慣性因子，w較大時算法具有較強的全局搜索能力， w 較小時則算法傾向于局部搜索。慣性權(quán)值線性遞減算法將慣性因子線性地減少，其變化公式為

w=wmax-R(wmax-wmin)/Rmax(6)

其中：R為當(dāng)前迭代次數(shù)；Rmax為最大迭代次數(shù)。取wmin=0.4，wmax=0.9。

為了分析對比，將實驗數(shù)據(jù)保留6位精度(Berman[3]中只保留5位)。由表2和3可以看出，當(dāng)T=1.0時，得出的結(jié)果明顯好于Berman[3]，當(dāng)T=0.95和0.85時，結(jié)果略差。其他情況下結(jié)果相同。更多的實驗數(shù)據(jù)顯示，此算法在性能上與Berman[3]的算法相當(dāng)，但是此算法無須考慮需求點集合是否為凸集的復(fù)雜情況，且簡單易實現(xiàn)、通用性好。

4 結(jié)束語

經(jīng)上面的分析，對本文討論的隨機權(quán)值的平面選址問題而言，粒子群優(yōu)化算法具有較為理想的尋優(yōu)能力，在實際操作中是行之有效的。粒子群優(yōu)化算法不僅簡單易實現(xiàn)，而且具有很好的收斂特性和得出較優(yōu)解的能力。本文只涉及了粒子服從均勻分布的情況，而對于服從其他概率分布的情形還有待于進一步的研究。這為解決平面問題提供了一種新的求解思路和手段。

參考文獻:

[1]HAKIMI S L. Optimum locations of switching centers and absolute Centers and medians of a graph[J]. Operations Research， 1964，12(3):450-459.

[2]BERMAN O， KRASS D. Facility location with stochastic demands and congestion[M].Berlin:Springer， 2001.

[3]BERMAN O， WANG Jia-min， DREZNER Z， et al. A probabilistic minimax location problem on the plane[J]. Annals of Operations Research， 2003，122(1-4):59-70.

[4]PELEGRLN B， FERNONDEZ J， TOTH B. The 1-center problem in the plane with independent random weights[J]. Computers and Operations Research， 2006，35（3）：737-749.

[5]FUKUYAMA Y. Fundamentals of particle swarm techniques[M]//LEE K Y， ELSHARKAWI M A. Modern heuristic optimization techniques with applications to power systems.[S.l.]:IEEE Power Engineering Society， 2002.

[6]BERGH F. An analysis of particle swarm optimizers[D]. Pretoria: Department of Computer Science， University of Pretoria， 2002.

[7]SHI Yu-hui， EBERHART R C. Fuzzy adaptive particle swarm optimization[C]//Proc of Congress on Evolutionary Computation. 2001:101-106.

[8]BERMAN O， DREZNER Z， WANG J， et al. The minimax and maximin location problems on a network with uniform distributed weights[J]. IIE Transactions， 2003，35(11):1017-1025.

[9]PELEGRIN B. A general approach to the 1-center problem[J]. Ca-hiers du CERO， 1986，28:293-301.

[10]楊豐梅，華國偉，鄧猛，等. 選址問題研究的若干進展[J]. 運籌與管理， 2005，14(6):1-6.

[11]楊維，李歧強. 粒子群優(yōu)化算法綜述[J]. 中國工程科學(xué)， 2004，6(5):87-94.

[12]張選平，杜玉平，秦國強，等. 一種動態(tài)改變慣性權(quán)的自適應(yīng)粒子群算法[J].西安交通大學(xué)學(xué)報， 2005，39(10):1039-1042.