胡文皓， 陳曙東， 辛欣

(1. 中國科學(xué)院大學(xué) 電子電氣與通信工程學(xué)院, 北京 100049；2. 中國科學(xué)院 微電子研究所, 北京 100029；3. 中國物聯(lián)網(wǎng)研究發(fā)展中心, 江蘇 無錫 214135)

?

求解物流配送問題的混合粒子群算法

胡文皓1,3， 陳曙東2,3， 辛欣1,3

(1. 中國科學(xué)院大學(xué) 電子電氣與通信工程學(xué)院, 北京 100049；2. 中國科學(xué)院 微電子研究所, 北京 100029；3. 中國物聯(lián)網(wǎng)研究發(fā)展中心, 江蘇 無錫 214135)

摘要：為了加快粒子群算法(PSO)在解決限定車輛配送問題時的收斂速度和減少時間花費，采取先驗判斷粒子個體最優(yōu)位置與全局最優(yōu)位置的距離決定粒子的更新方式，提出一種混合策略，設(shè)計魚群-粒子群算法(AFSA-PSO)，并通過對函數(shù)極值的求解進行驗證.實驗結(jié)果表明：該方法能夠得到正確解，并具有收斂快、尋優(yōu)佳的特點.

關(guān)鍵詞：粒子群算法; 魚群算法; 混合算法; 物流配送問題

物流配送問題屬于復(fù)雜的求解最優(yōu)方案的問題,在實際問題中求解最優(yōu)解存在難度.因此，出現(xiàn)了通過種群中個體的協(xié)作能力尋找最優(yōu)解的方法[1].以粒子群算法(PSO)為代表的群智能[2]是基于此思想而產(chǎn)生的.粒子群算法是群智能理論中應(yīng)用廣泛的一類，它是個體學(xué)習(xí)迭代產(chǎn)生更佳解的算法.粒子群算法解決配送問題的研究主要體現(xiàn)在粒子編碼方式和改進解的精度上[3-6].粒子群算法為得到更精確解而增大了迭代次數(shù)，導(dǎo)致收斂速度慢、時間花費多等問題.為縮小迭代次數(shù)、加快解的收斂速度，本文設(shè)計了一種求解物流配送問題的混合粒子群算法.

1問題模型

車輛路徑問題是物流配送的關(guān)鍵，引入不同因素可以推導(dǎo)出不同的數(shù)學(xué)模型.文中采用有能力約束的車輛路徑問題[6].假定配送中心編號為0；用戶編號依次為1,2,…,n；第i個用戶的需求量為gi；可供使用的車輛數(shù)量為K；每輛車的容量為q；ci,j表示從點i到點j的單位費用.則有

又

(1)

(2)

(3)

式(1)為成本函數(shù)；式(2)為全部車的容量限制；式(3)限定了一個用戶僅能由一輛車完成.由于車容量的限制，采用判罰值修正成本函數(shù).其中，R=(1+t)/4(t為當(dāng)前迭代次數(shù)).式(1)可轉(zhuǎn)化為

(4)

采用自然數(shù)對配送路徑進行編碼，對粒子維數(shù)值進行遞增排序，得到相應(yīng)用戶序列.此外，每輛車必須從中心出發(fā)再回到中心.

2混合粒子群算法

2.1粒子群算法

粒子群算法是個體尋優(yōu)算法，粒子本身有感知能力.每次迭代后得到一個候選解，粒子維數(shù)代表解方案，在組合優(yōu)化問題上應(yīng)用廣泛，如求路徑規(guī)劃問題[7]、股票預(yù)測[8]、工程數(shù)學(xué)應(yīng)用問題[9-11].

粒子x的函數(shù)值f(x)稱為個體適應(yīng)度值pbest，一次迭代后，得到新位置xnew.若f(xnew)比f(x)更佳，則該粒子的個體最優(yōu)位置pbest,X為xnew，pbest為f(xnew)；否則，pbest,X為x，pbest為f(x)；種群中最優(yōu)位置gbest,X是全部個體適應(yīng)度值最佳的粒子xbest，全局適應(yīng)值gbest為f(xbest).粒子更新位置為

(5)

(6)

式(5)，(6)中:r1，r2均為(0,1)的隨機數(shù)；c1，c2為學(xué)習(xí)因子.

2.2魚群算法原理

魚群算法(AFSA)是個體尋優(yōu)算法，具有易實現(xiàn)、適用性強等優(yōu)點.如粒子群算法一樣，AFSA是連續(xù)型算法，對于離散型問題需對解編碼.AFSA算法有以下4個關(guān)鍵步驟.

1) 追尾.個體魚i在其鄰域內(nèi)滿足有更好的位置best_j，且位置best_j的鄰域內(nèi)的個體魚數(shù)量滿足一定條件.則魚i向best_j前進一步；否則,群聚.

2) 群聚.個體魚i在其鄰域內(nèi)的個體魚數(shù)量滿足一定條件，并且該鄰域內(nèi)有一個中心位置，若位置更佳，則魚i向中心位置前進一步；否則,覓食.

3) 覓食.個體魚i鄰域內(nèi)隨機選擇位置new_i,若該位置更佳，則魚i向其前進一步;否則,位置不變.選擇一定次數(shù)后，都沒有更佳的位置，則隨機移動.

4) 隨機移動.在可行域內(nèi)，隨機生成新位置，個體魚向其前進一步.

2.3混合策略改進粒子群算法

魚群算法根據(jù)適應(yīng)值規(guī)定不同個體應(yīng)有各自的優(yōu)化方向，為粒子群算法改進提供了思路，即粒子應(yīng)針對性地依靠不同感知能力指導(dǎo)粒子位置更新.

粒子的不同感知能力決定了粒子的搜索范圍和粒子種群的收斂速度.粒子在大范圍內(nèi)搜索最優(yōu)位置，需依仗整體感知和自我感知，使粒子位置更新后足夠分散.而為實現(xiàn)收斂速度快，應(yīng)讓粒子向全局最優(yōu)位置靠攏，這就不能擴大整體感知和自我感知.因此，應(yīng)平衡粒子位置更新時所具備的3種感知能力.引入權(quán)重維持粒子的繼承能力，即

(7)

為加速粒子種群的收斂速度，每次迭代更新位置時，對粒子進行個體適應(yīng)值與全局適應(yīng)度差值檢測.如果接近，則“追尾”可以得到解，這些粒子的位置可信度高，為了維持粒子的搜索能力，采取信任3種感知能力的方式進行更新；如果臨近，則“群聚”即可，采取信任自我感知能力，粒子向著自己鄰近的粒子靠攏，即它們的個體最優(yōu)位置pbest,X是鄰近的粒子的pbest,X；其余情況，為加速收斂，這些粒子的位置和當(dāng)前個體最優(yōu)位置是不足夠可信的，則直接忽略，采取信任整體感知能力，向全局最優(yōu)位置gbest,X靠攏.由此，粒子會整體向當(dāng)前全局最優(yōu)位置靠攏，加速了收斂速度.新的混合算法記為AFSA-PSO.

3結(jié)果與分析

為驗證文章算法解決車輛路徑問題的可行性和有效性，在Windows7系統(tǒng)下，基于MatlabR2010b工具實現(xiàn)算法，通過求函數(shù)極值驗證搜索性能，并與其他文獻方法進行對比.

3.1尋優(yōu)性能的驗證

由線性遞減策略可得到標(biāo)準(zhǔn)粒子群算法(SPSO).模擬退火算法與粒子群算法的融合[12](SA-PSO)是混合策略研究的熱門.設(shè)粒子數(shù)量N=40；c1=c2=1.496 18；wstart=0.9；wend=0.4；最大迭代次數(shù)為1 000次；初始溫度為10 000 ℃；最低溫度為0.01 ℃；溫度遞減因子K=0.9；最大接受誤差為0.5.

(a) Ackley函數(shù)　　　　　(b) Sphere函數(shù)圖1　混合策略和SPSO求解函數(shù)極值Fig.1　Mixed strategy and SPSO for function extremum

混合策略和SPSO求解函數(shù)極值，如圖1所示.圖1中：n為迭代算法的次數(shù)；fx為函數(shù)極值.由圖1可知：SA-PSO算法收斂速度慢，搜索范圍廣；而AFSA-PSO算法收斂速度快，搜索范圍??；SPSO算法收斂速度比AFSA-PSO稍微慢，搜索過程穩(wěn)定.

3.2車輛路徑問題

配送路徑問題的數(shù)據(jù)來源于文獻[6].AFSA-PSO參數(shù)設(shè)置：粒子個數(shù)為60；迭代次數(shù)為150；粒子維數(shù)為9；最大速度限制100；權(quán)重始于0.9，終于0.4；學(xué)習(xí)因子c1=c2=1.496 18.隨機運行20次，結(jié)果如表1所示.表1中：HAPS為加入蛙跳算法的粒子群優(yōu)化算法.

表1　算法結(jié)果比較表

由表1可知：AFSA-PSO最小值為65，其余最小值為67.5，但AFSA-PSO的平均成本值不是最小.此外，文獻[5]采用輪盤選擇策略選擇粒子，加入退火算法解決車輛路徑問題，記為PSOSA，運行50次，二者最優(yōu)值相同，皆為67.5，但AFSA-PSO平均值為69.77，大于PSOSA的平均值68.11.

4結(jié)束語

粒子群算法的改進在于對粒子位置更新時3種能力的優(yōu)化.新算法提升了收斂速度、減少了時間花費，在面對車輛路徑問題時，可以快速地找到解.未來可以采用階段求解的方法，先更新粒子位置，然后計算適應(yīng)值與原來的差距判定更新位置方式，并且具體的方式使用漸進函數(shù)優(yōu)化，以達到搜索解過程穩(wěn)定、保證解精度的目標(biāo).

參考文獻：

[1]王文杰,葉世偉.人工智能原理與應(yīng)用[M].北京:人民郵電出版社,2004：3-4.

[2]HACKWOOD S,BENI G.Self-organization of sensors for swarm intelligence[C]∥International Conference on Robotics and Automation.Piscataway：IEEE Press,1992:819-829.

[3]吳斌.車輛路徑問題的粒子群算法研究與應(yīng)用[D].杭州:浙江工業(yè)大學(xué),2007：28-40.

[4]肖麗，包駿杰.一種改進粒子群算法在物流配送路徑問題中的應(yīng)用[J].湖南科技大學(xué)學(xué)報(自然科學(xué)版),2012,27(2):88-92.

[5]楊凌云.改進粒子群算法在車輛問題中的應(yīng)用研究[D].鄭州:河南大學(xué),2011：25-32.

[6]張思亮，葛宏偉.粒子群和蛙跳的混合算法求解車輛路勁問題[J].計算機工程與應(yīng)用,2011,47(21):246-248.

[7]章權(quán)，溫惠英，孫博.適于配送車輛導(dǎo)航路徑規(guī)劃的遍歷模型的改進型粒子群優(yōu)化算法[J].華南理工大學(xué)學(xué)報(自然科學(xué)版),2011,39(8):109-112.

[8]LU Jinna,BAI Yanping.Applications of GRNN based on particle swarm algorithm forecasting stock prices[C]∥International Conference on Information, Business and Education Technolog.Atlantis：Atlantis Press,2013:69-73.

[9]WANG Wei,GONG Shuiqing,LI Peilin,et al.Research on convex polyhedron collision detection[C]∥International Conference on Mechanical Engineering and Material Science.Atlantis：Atlantis Press,2012:479-483.

[10]周書敬，高延安，楊柳，等.改進的粒子群-模擬退火算法在桁架結(jié)構(gòu)優(yōu)化設(shè)計中的應(yīng)用[J].工業(yè)建筑,2012，27(163):37-41.

[11]孫祥云,邵輝，趙家宏.采用粒子群優(yōu)化算法在液壓挖掘機高效空中運動軌跡規(guī)劃方法[J].華僑大學(xué)學(xué)報(自然科學(xué)版)，2014,35(5):498-502.

[12]李麗，牛奔.粒子群優(yōu)化算法[M].北京:冶金工業(yè)出版社,2009：72-94.

(責(zé)任編輯： 錢筠 英文審校： 吳逢鐵)

Hybrid Particle Swarm Algorithm for the Logistics Distribution Problem

HU Wenhao1,3, CHEN Shudong2,3, XIN Xin1,3

(1. School of Electronic, Electrical and Communication Engineering，University of Chinese Academy of Sciences, Beijing 100049, China;2. Institute of Microelectronics, Chinese Academy of Sciences, Beijing 100029, China;3. China Research and Development Center for Internet of Things, Wuxi 214135, China)

Abstract：In order to speed up convergence and reduce the time, when using the particle swarm algorithm (PSO) to solve the limited vehicle distribution problem, we use the distance between the individual optimal position and the global optimal position to decide particle updating mode, and propose a hybrid improved strategy, then we design a new AFSA-PSO algorithm. Experimental results show that it can get correct solution and has the characteristics of fast convergence and good searching effect.

Keywords：particle swarm algorithm; artificial fish swarm algorithm; hybrid algorithm; logistics and distribution problem

中圖分類號：TP 18

文獻標(biāo)志碼：A

基金項目：農(nóng)村信息服務(wù)數(shù)據(jù)智能處理技術(shù)研究與應(yīng)用(2013BAD15B03)

通信作者：陳曙東(1977-)，女，教授，博士，主要從事大數(shù)據(jù)管理的研究.E-mail:chenshudong@ciotc.org.

收稿日期：2015-08-09

doi:10.11830/ISSN.1000-5013.2016.03.0295

文章編號：1000-5013(2016)03-0295-04