改進(jìn)的離散粒子群算法在配送問(wèn)題中的應(yīng)用

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

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

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

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

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

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

1.1 粒子群算法原理

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

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

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

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

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

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

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

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

1.2.2 位置與速度的加法

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

1.2.3 排斥算子

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

1.2.4 定義粒子的群體相似度

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

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

1.2.5 離散粒子群算法

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

2 配送問(wèn)題描述

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

約束條件為：

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

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

3 離散粒子群算法流程

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

4 實(shí)驗(yàn)仿真及結(jié)果分析

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

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

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

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

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

[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] 張長(zhǎng)勝，孫吉貴，歐陽(yáng)丹彤.一種自適應(yīng)離散粒子群算法及其應(yīng)用研究[J].電子學(xué)報(bào)，2009(2):299-304.

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

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

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

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