隨機權值平面選址的粒子群優化算法

（四川大學 計算機學院， 成都 610064）

摘 要：

將引入粒子群優化算法來解決帶隨機權值、服從獨立均勻概率分布的極小化極大（1-中心）平面選址問題，對其進行實驗模擬并得出了樂觀的結果。

關鍵詞：隨機權值； 選址問題； 1-中心; 粒子群優化算法

中圖分類號：TP301.6文獻標志碼：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)

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

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

1 平面選址及粒子群優化原理

1.1 平面選址

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

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

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

1996年，Frank首次引入了帶隨機權值網絡選址問題，即1-中值和1-中心問題。1-中值問題的目標是找到某點使帶權值的總距離大于等于某個預定值的概率最小化；1-中心問題的目標則是找到某點使設施到需求點的最大權值距離大于等于某個預定值的概率最小化。

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

1.2 粒子群優化算法

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

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

在找到這兩個最優值時，粒子根據式(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是學習因子，分別調節向全局最好粒子和個體最好粒子方向飛行的最大步長。若太小，則粒子可能遠離目標區域，若太大則會導致突然向目標區域飛去，或飛過目標區域。合適的c1、c2可以加快收斂且不易陷入局部最優，通常令c1=c2= 2。rand1，2是[ 0 ，1 ] 間的隨機數。xkid是粒子i 在第k 次迭代中第d 維的當前位置。pbestid是粒子i 在第d 維的個體極值點的位置(即坐標) ；gbestd是整個種群在第d 維的全局極值點的位置。為防止粒子遠離搜索空間，粒子的每一維速度vd都會在[-vd max，+vd max]中。vd max太大，粒子將飛離最好解，太小則會陷入局部最優。

這里只簡要介紹平面選址和粒子群優化算法的相關原理及背景，更加詳細的定量描述將在下部分敘述。

2 問題描述及算法設計

2.1 問題描述

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

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

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

由于wi為[ai，bi]內的均勻隨機變量，則

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)

現在本文的目標就是最大化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，那么平面內所有點都為式(3)的解，且最佳值為0。

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

2.2 算法設計

1)初始化

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

2） 評價每一個粒子

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

3）粒子的更新

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

4）檢驗是否符合結束條件

如果當前的迭代次數達到了預先設定的最大次數(或達到最小錯誤要求)，則停止迭代，輸出最優解；否則轉到2)。

2.2.1 相關數據結構

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

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

private point bestposition;// 粒子所經過的最佳位置

private double fitness;// 粒子的適應度

public double bestfitness;//該粒子所得到的最佳適應度

}

2.2.2 PParticle算法

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

gbestfitness/*全局變量，記錄種群最佳適應度 */

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

a)粒子群初始化;

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

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

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

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

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

3 實驗分析

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



表3 實驗數據對照

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

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

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

其中：R為當前迭代次數；Rmax為最大迭代次數。取wmin=0.4，wmax=0.9。

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

4 結束語

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

參考文獻:

[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]楊維，李歧強. 粒子群優化算法綜述[J]. 中國工程科學， 2004，6(5):87-94.

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