胡 書， 張 莉， 彭文敏 （內(nèi)江師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，四川 內(nèi)江 641112）

粒子群算法 （Particle Swarm Optimization，PSO）是由Kennedy和Eberhart[1]等人于1995年提出的一種新的進(jìn)化計算算法，它來源于鳥類或魚類覓食過程中遷徙和群集的模擬，是群智能的代表性方法之一。在PSO中，每一個粒子的位置代表問題的一個潛在解，在迭代過程中，每一個粒子跟隨代表最優(yōu)解的個體在解空間中進(jìn)行搜索，粒子群算法簡單容易實現(xiàn)，而且具有比普通遺傳算法更高的效率，特別是在連續(xù)函數(shù)的優(yōu)化方面，PSO算法表現(xiàn)出非常強的適應(yīng)性，被廣泛研究和采用。

PSO算法發(fā)展迅速并取得了可觀的研究成果，并且很多學(xué)者把粒子群算法用于解決離散問題，如張長勝[2]等人用自適應(yīng)離散粒子群算法解決TSP問題，程序[3]等人用粒子群算法解決多模式項目再調(diào)度問題，這些改進(jìn)的算法在一定程度上避免了粒子的早熟現(xiàn)象，使粒子盡可能在全局范圍內(nèi)搜索。

針對大多數(shù)文章未能將離散粒子群算法的內(nèi)容描述清楚，本文在文獻(xiàn)[4]的基礎(chǔ)上對離散粒子群算法的位置和速度的初始化、位置的更新公式進(jìn)行重新定義，并且保留慣性權(quán)值對速度的影響，把粒子的解儲存為數(shù)組形式，增加群體相似度和排斥算子來讓粒子跳出局部最優(yōu)。

配送問題是如何合理優(yōu)化配送資源，以最低的成本、最快的速度完成配送任務(wù)，也是任何一個現(xiàn)代物流企業(yè)的核心目標(biāo)之一，優(yōu)化配送方案不僅可以降低商品的流通費用，提高企業(yè)的利潤源泉，而且對工作效率也會產(chǎn)生很大的促進(jìn)作用，于是在此設(shè)計了用離散粒子群算法解決配送問題的算法步驟，并用matlab7.0編程仿真，仿真結(jié)果表明改進(jìn)的離散粒子群算法能夠找到更好的解，并且收斂速度快，在一定程度上避免了陷入局部最優(yōu)。

1 改進(jìn)的離散粒子群算法

1.1 粒子群算法原理

粒子群算法中的每個粒子代表一個解，每個粒子都有一個由優(yōu)化函數(shù)決定的適應(yīng)度，以評價該粒子當(dāng)前位置的優(yōu)劣。同時，每個粒子都有一個速度來決定它移動的方向和距離，然后粒子們追隨當(dāng)前的最優(yōu)粒子在解空間中進(jìn)行搜索，粒子群算法初始化為一群隨機粒子 （隨機解），然后通過如下迭代公式迭代找到最優(yōu)解：

其中w為加權(quán)系數(shù)，表示歷史速度對當(dāng)前速度的影響，c1,c2是學(xué)習(xí)因子，分別表示粒子受群體認(rèn)識和個體認(rèn)識的影響程度，rand1（），rand2（）是0～1區(qū)間上的隨機數(shù)，表示群體認(rèn)識或個體認(rèn)識對粒子的影響具有隨機性。在每一次迭代中，粒子通過跟蹤兩個 “極值”來更新自己，一個是粒子本身所找到的最優(yōu)解，即個體極值；另一個極值是整個種群目前找到的最優(yōu)解，即全局極值。

1.2 改進(jìn)的離散粒子群算法

在鐘一文[4]等人提出的離散粒子群優(yōu)化算法的基礎(chǔ)上，對離散對粒子的位置和速度的初始化、位置的更新公式進(jìn)行重新定義，并且保留了慣性權(quán)值的作用，最后定義群體相似度來讓粒子跳出局部最優(yōu)，部分定義如下。

1.2.1 初始化粒子的位置和速度

粒子的位置X用一個由點組成的表來表示，它是一個N維向量，在X中，第i維數(shù)據(jù)表示第i次訪問地點xi，位置X表示為：X=（x1,x2,…,xN），其中N為地點數(shù)，按照數(shù)組X依次訪問每個地點，最終形成一個回路的TSP問題。

在粒子的初始位置形成的基礎(chǔ)上，以一定的概率取初始位置上的部分點作為粒子的初始速度，即對第i維上的點xi，隨機產(chǎn)生一個0～1之間的數(shù)，如果這個數(shù)小于預(yù)先給定的常數(shù)c，則將此xi保留為速度vi，否則速度vi值為0，每一維速度vi表示為

速度V表示為：V=（v1,v2,…,vN），其中N為地點數(shù)。

1.2.2 位置與速度的加法

位置與速度相加，使粒子到達(dá)一個新的狀態(tài)，即得到新的位置，對第i維上的位置xi和速度vi，如果速度vi為0或者與xi相同，則不改變位置X的第i維上的數(shù)，否則將速度vi插入到位置X的第i維上，而X的第i維及其以后的數(shù)依次向后移動一個單位，并且原位置X上與vi相同的那一維的數(shù)值為空，于是得到新的位置，即

1.2.3 排斥算子

為了避免粒子在搜索過程中出現(xiàn)早熟現(xiàn)象，于是引入排斥算子增加粒子的多樣性，當(dāng)粒子的群體相似度大于某一給定的閥值c時，表明粒子群在靠攏，為了避免早熟，于是啟用排斥算子 （閥值c越大，表明粒子靠得越攏才啟用排斥算子），即以一定的概率隨機產(chǎn)生一個新的速度，并將速度作用在當(dāng)前位置上得到新的位置。這里可用初始化粒子速度的方法產(chǎn)生新的速度，用位置與速度的加法來更新位置。

1.2.4 定義粒子的群體相似度

由于粒子在尋找最優(yōu)解的過程中是以群體合作為前提的，因此以整個群體的相似度判斷粒子是否陷入局部最優(yōu)。首先求出任意兩個粒子Xi和Xj的相似度Si,j[4]，然后把整個粒子群中任意兩個粒子Xi和Xj的相似度Si,j的平均值作為粒子的群體相似度d，即

其中M表示粒子數(shù)，d的值仍在0～1之間。

1.2.5 離散粒子群算法

離散粒子群算法保留了慣性項的作用，在這里慣性權(quán)值w取常數(shù)，并且在定義常數(shù)與速度的乘法時引入了隨機項，于是把c1×rand1（）和c2×rand2（）合并為常數(shù)c1和c2，于是離散粒子群算法定義為

2 配送問題描述

貨物的配送是由中心倉庫運到子庫，再由子庫的車輛運到多個零售點 （需求點）。從中心倉庫到子庫的配送安排可以按運籌學(xué)中的一般運輸問題解決，配送中心要向整個區(qū)域內(nèi)的各個地點送貨，而且客戶的數(shù)量、頻率和方向具有不確定性。配送問題的數(shù)學(xué)模型為[5]：

約束條件為：

式中，m——配送中心擁有的車輛臺數(shù)，Wk——車輛的載重量，n——客戶需求點數(shù)，Ri——需求點的需貨量，Lk——每輛車每日最大運行距離，di,j（i=1,2,…,n-1;j=1,2,…,n;i＜j,i=0表示配送中心）——配送中心到各需求點的距離及需求點之間的距離。

約束條件 （1）表示每輛車輛所運送的貨物量不超出其載重量；約束條件 （4）表示若客戶點i由車輛k送貨，則車輛k送完該點的貨后必到達(dá)另一個點j；約束條件 （5）表示每條線路距離不大于車輛的最大運行距離為Lk；約束條件 （6）表示需求點i由車輛k送貨時，Yi,k=1；否則Yi,k=0；約束條件 （7）表示第k輛車從點i到點j時，Xi,j,k=1；否則Xi,j,k=0。

3 離散粒子群算法流程

配送問題屬于多約束TSP問題，而離散粒子群算法可用于解決TSP問題，并且運算速度快，能夠找到比一般算法更好的解，于是設(shè)計了用離散粒子群算法解決配送問題的算法流程。

4 實驗仿真及結(jié)果分析

根據(jù)參考文獻(xiàn)[5]，利用K-means聚類方法，將配送問題中的路徑分為兩類，于是轉(zhuǎn)化為了TSP問題，并且配送中心坐標(biāo)為 （0.4291,0.2354 ）。其余客戶的坐標(biāo)如下表所示。

利用改進(jìn)的離散粒子群算法對以上數(shù)據(jù)進(jìn)行仿真，其中慣性權(quán)值w取0.4，系數(shù)c1取0.2，c2取0.3，閥值c取0.4，在matlab7.0環(huán)境下，用10個粒子，迭代100次，仿真結(jié)果如下圖：

與其它算法的結(jié)果進(jìn)行比較，表明本算法能夠找到更好的解，并且運算速度很快，不到兩秒便可計算出這兩個回路，結(jié)果如下表：

5 結(jié)束語

本文在參考文獻(xiàn)[4]的前提下對粒子群算法進(jìn)行重新定義和部分修改，得出改進(jìn)的離散粒子群算法，并且在配送問題中，以最低的成本、最快的速度完成配送任務(wù)是任何一個現(xiàn)代物流企業(yè)的核心目標(biāo)之一，因此很有必要對配送問題進(jìn)行優(yōu)化。于是設(shè)計了用改進(jìn)的離散粒子群算法解決配送問題的算法流程，并用matlab7.0對它進(jìn)行仿真，結(jié)果表明離散粒子群算法比其他算法找到的解更好，并且運算速度快。

[1] Keedny J,Eberhart R C.Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks.Perth,Australia:IEEE Press,1995:1942-1948.

[2] 張長勝，孫吉貴，歐陽丹彤.一種自適應(yīng)離散粒子群算法及其應(yīng)用研究[J].電子學(xué)報，2009(2):299-304.

[3] 程序，吳澄.粒子群優(yōu)化算法求解多模式項目再調(diào)度問題[J].計算機集成制造系統(tǒng)，2009,15(1):97-101.

[4] 鐘一文，楊建剛，寧正元.求解TSP問題的離散粒子群優(yōu)化算法[J].系統(tǒng)工程理論與實踐，2006(6):88-94.

[5] 王曉博，李一軍.面向電子商務(wù)的協(xié)同配送路線優(yōu)化研究[J].計算機工程與應(yīng)用，2007,43(8):184-186,196.

[6] 田謙益，何田中.粒子群算法在PERT網(wǎng)絡(luò)優(yōu)化問題中的應(yīng)用[J].計算機工程與科學(xué)，2008,30(9):58-59,72.