肖 樂，吳相林,張雪萍

（1.華中科技大學(xué) 控制系，湖北 武漢 430074; 2.河南工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，河南 鄭州 450001）

自適應(yīng)混沌粒子群優(yōu)化的糧食應(yīng)急點選址研究

肖 樂1,2，吳相林1,張雪萍2

（1.華中科技大學(xué) 控制系，湖北 武漢 430074; 2.河南工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，河南 鄭州 450001）

針對糧食應(yīng)急點選址，將“運輸時間最小”和“應(yīng)急開始最早”作為目標，建立了相應(yīng)的優(yōu)化模型.利用基于粒子群的K-Medoids聚類算法進行求解，為了避免過早地陷入局部最優(yōu)，提出了自適應(yīng)混沌粒子群優(yōu)化算法.該算法利用粒子與已知全局最優(yōu)粒子的歐式距離來判斷粒子群當前狀態(tài)，并將其作為確定混沌擾動范圍的啟發(fā)信息，可以有效地提高最優(yōu)解的精度.試驗表明該算法優(yōu)于傳統(tǒng)的演化算法，較好地解決了糧食應(yīng)急點選址問題.

糧食應(yīng)急點；選址；聚類；自適應(yīng)混沌粒子群算法；距離啟發(fā)信息

0 引言

突發(fā)事件下的糧食供給保障直接關(guān)系到人民生活安全和社會穩(wěn)定.近年來，國家和各省市均出臺了“糧食應(yīng)急預(yù)案”，對緊急情況下的糧食供給和流通提出了較高的要求.應(yīng)急糧食與與其他應(yīng)急物資相比有其特殊性，由于數(shù)量和體積較大，本身也易發(fā)生霉變、蟲災(zāi)和鼠害，必須建立臨時的糧食應(yīng)急點進行儲藏和保管.糧食應(yīng)急點主要從其他國有儲備糧庫接收并儲存足夠的糧食，為其周圍地區(qū)進行救援.糧食應(yīng)急點的選址和建設(shè)一般是在省級區(qū)域進行，不同于在一個城市中的多應(yīng)急服務(wù)設(shè)施點的選址問題[1].糧食應(yīng)急點選址問題的研究對促進事發(fā)區(qū)域穩(wěn)定，提高政府應(yīng)急響應(yīng)能力等有著十分重要的意義.

粒子群優(yōu)化(PSO)算法是由Kennedy等[2-3]提出的一種進化算法，它源于對鳥類捕食過程中遷徙、聚集行為的模擬.因為PSO算法參數(shù)簡單、容易實現(xiàn)、可并行處理、魯棒性好、能以較大的概率收斂到全局最優(yōu)解，所以粒子群優(yōu)化算法得到了廣泛關(guān)注.與所有的演化算法類似，由于加入了正反饋，粒子群優(yōu)化算法也存在早熟收斂現(xiàn)象，在較復(fù)雜的高維、多峰搜索問題中表現(xiàn)得尤為明顯.筆者在處理糧食應(yīng)急點選址這一實際問題中，通過對基本粒子群算法改進，提出了一種自適應(yīng)混沌粒子群算法，在解決上述問題中得到了較好地應(yīng)用.

2 糧食應(yīng)急點選址數(shù)學(xué)模型

假設(shè)某一地區(qū)發(fā)生自然災(zāi)害或突發(fā)事件，亟需大量的糧食供應(yīng)，現(xiàn)根據(jù)需求在事發(fā)區(qū)域中建設(shè)d1,d2,…dk個糧食應(yīng)急點，已知每個應(yīng)急點的到各個救援目標的障礙約束下運輸時間和每個糧食應(yīng)急點的最早應(yīng)急時間.要求在一定的區(qū)域X和在一定時間T內(nèi)，滿足該區(qū)域人口應(yīng)急需求的前提下，求得最佳的d1,d2,…dk位置，使得應(yīng)急方案的總運輸時間最小和最大應(yīng)急開始時間最早.

基于上述分析，糧食應(yīng)急點選址問題本質(zhì)是在諸多約束條件下的一個多目標優(yōu)化問題.該問題建立在以下條件之上：

1）在一定區(qū)域范圍內(nèi)進行糧食應(yīng)急點選址；

2)%考慮到區(qū)域內(nèi)既有的和突發(fā)事件下新增的各種障礙物對選址的影響，糧食應(yīng)急點只能選擇在適宜建設(shè)的地址上；

3)%每個出救目標只接受一個應(yīng)急糧庫的救援；

4)%方案中的各糧食應(yīng)急點的最大最早應(yīng)急時間必須滿足應(yīng)急要求；

5)%方案中各應(yīng)急點到其所服務(wù)的救援目標最長時間必須滿足應(yīng)急要求；

6)%在應(yīng)急要求下，不考慮應(yīng)急點的建設(shè)成本和運輸成本.

考慮糧食應(yīng)急特點，在針對上述兩個目標建立優(yōu)化模型時，需要引入相應(yīng)影響因子.

2.1 總運輸時間最小和最大應(yīng)急開始時間最早

問題要求找到X的一個劃分Pk={D1,D2,…,Dk}，使其目標函數(shù)值最小.建立目標模型如下：

式中：di表示第i個的應(yīng)急點，di∈Di，C(p,di)為在一個劃分區(qū)域中應(yīng)急點到救援目標障礙條件下的時間開銷. ti為第i個糧食應(yīng)急點所能提供的最早應(yīng)急時間.T1為應(yīng)急活動允許應(yīng)急點到其救援目標的最長時間，T2為整體應(yīng)急響應(yīng)開始的最晚時間.

2.2 待救援目標緊急響應(yīng)程度

在公共突發(fā)事件或自然災(zāi)害中，待救援目標所需救援的緊急程度和受影響人口的數(shù)量不盡相同.在糧食應(yīng)急選址時需要考慮每個救援目標的響應(yīng)緊急程度，從而使糧食應(yīng)急點選址兼顧及時性與公平性.這里引入一個緊急因子λj(j=1,2,…,n)表示救援目標pj的應(yīng)急緊急程度，λj越大表示救援目標pj越重要，該值可由專家給出.則式（1）變?yōu)椋?/p>

用式（5）來求得上述問題的多目標最優(yōu)解.

式中：ω1、ω2是控制因子，不同的值代表對不同目標的關(guān)注程度，應(yīng)用時視糧食應(yīng)急實際情況而定.

式（4）可以看作聚類問題，解決此類問題較典型的方法有K-Mediods算法、K-Means算法和CLARANS算法.CLARANS算法較多用于大數(shù)據(jù)量的情況下. K-Means算法選取類中對象的平均值作為中心，有時中心可能剛好落在障礙上，在實際應(yīng)急中是不允許的.而K-Mediods算法選擇類中的一個對象作為中心點，這樣保證類中心不會落在障礙上.利用帶障礙約束的K-Mediods聚類算法提高實用性.但K-Mediods聚類算法具有對初始值的隨機選取敏感，很容易陷入局部極值等缺點，粒子群算法在處理聚類問題上有一定的優(yōu)勢.為了解決基本粒子群算法過早收斂問題，將基本粒子群算法與混沌系統(tǒng)相結(jié)合，利用混沌系統(tǒng)的偽隨機性及遍歷性對粒子加以擾動，以提高全局收斂的概率和速度.

3 混沌粒子群優(yōu)化算法

混沌粒子群算法是在基本粒子群算法中加入了混沌初始化和混沌擾動環(huán)節(jié)來實現(xiàn)的.下面首先給出基本粒子群算法介紹.

3.1 基本粒子群算法

PSO算法采用“群體進化”的概念，利用單個粒子的適應(yīng)度值大小來評價該粒子的優(yōu)劣.每個粒子對應(yīng)問題的一個可能解，具有位置和速度.粒子位置對應(yīng)的目標函數(shù)的值就是該粒子的適應(yīng)度.算法先隨機生成一組初始粒子，然后對每個粒子迭代，最后得到一個解.每次迭代中，粒子更新通過跟蹤個體極值位置pbest(即粒子本身經(jīng)歷過的最優(yōu)解)和全局極值gbest(即全題粒子群經(jīng)歷過的最優(yōu)解)實現(xiàn).

所有粒子根據(jù)下面公式來更新自己的速度和位置：

式中：vid表示第i個粒子在第d維上的速度；xid表示第i個粒子在第d維上的位置；ω，c1，c2表示群體的認知系數(shù)，ω一般介于于（0，1）之間的隨機數(shù)，c1，c2取（0，2）之間的隨機數(shù).用Pi=(pi1,pi2,…,piD)，i=1,2,…,n表示第i個粒子迄今為止搜索到的最好位置，也稱為個體極值pbest.用Pg=(pg1,pg2,…,pgD)表示整個粒子群迄今為止搜索到的最優(yōu)位置，也稱為全局極值gbest.

為防止粒子遠離搜索空間，粒子的每一維速度vid的值被限定在一個最大速度vdmax(vdmax＞0)內(nèi)，如果某一維更新后的速度超過用戶設(shè)定的vdmax，那么這一維的速度就被限定在vdmax，即若vid＞vdmax時，vid=vdmax或vid＜－vdmax時，vid=－vdmax.

3.2 混沌粒子群優(yōu)化算法

針對基本粒子群優(yōu)化算法的不足，利用混沌運動的遍歷性，產(chǎn)生大量初始群體，從中選擇較優(yōu)的初始群體，在迭代過程中，對當前粒子個體產(chǎn)生混沌擾動，以使解跳出局部極值區(qū)間.

Logistic映射是一個典型的混沌系統(tǒng)，迭代公式如下：

式中：μ為控制參量，當μ=4時，Logistic完全處于混沌狀態(tài).

設(shè)求解n維的優(yōu)化問題：

解上述優(yōu)化問題的混沌粒子群算法的程序框架為：

Step1：設(shè)定粒子數(shù)m，初始化混沌系統(tǒng).隨機產(chǎn)生一個n維、每個分量取0～1之間的數(shù)值，生成向量Z1= (z11,z12,…,z1n).根據(jù)式（8），得到m個Z1,Z2,…,Zn.將Zi的各個分量加載到優(yōu)化變量的取值范圍：

計算目標函數(shù)，初始化pbest和gbest，隨機產(chǎn)生m個速度.

Step2：根據(jù)當前位置和速度分別產(chǎn)生各個粒子新的位置.

Step3：隨機產(chǎn)生一個n維、每個分量數(shù)值在0～1之間的向量.

Step4：當?shù)螖?shù)k小于規(guī)定迭代次數(shù)，執(zhí)行Step5，否則輸出結(jié)果.

Step5：對于每一個粒子按照式（6），更新其速度，并限制速度的大小.

Step7：比較每個粒子新位置的適應(yīng)值.對各個粒子的適應(yīng)值和自身最優(yōu)值pbest進行比較，如果當前適應(yīng)值優(yōu)于pbest，則將pbest置為當前適應(yīng)值，對各個粒子的適應(yīng)值和種群最優(yōu)值gbest進行比較，如果當前適應(yīng)值優(yōu)于gbest，則將gbest置為粒子的當前適應(yīng)值，轉(zhuǎn)Step4.

該算法能夠?qū)玖Ｗ尤哼M行改進，但當具體問題的最優(yōu)解無法預(yù)知的情況下，擾動范圍不易確定，對算法效果有較大的影響.作者針對這一問題進行研究，提出一個利用粒子間距離，自適應(yīng)地改變擾動范圍的算法.

4 距離啟發(fā)信息

考慮到很多實際問題是一個多峰值問題，粒子群容易過早的進入收斂，落入局部最優(yōu).某個粒子與當前全局最優(yōu)粒子的距離可用式（14）的σ2表示.

式中：pij是當前第i個粒子的第j維數(shù)值，pgbestj當前全局最優(yōu)粒子的第j維數(shù)值，F(xiàn)為目標函數(shù)的表達式.與一般的距離公式不同，在式（14）中，既考慮了粒子與當前全局最優(yōu)粒子之間的距離，又考慮了兩者適應(yīng)度的差異.

式（15）中的ζ為設(shè)定的閾值，m為粒子總數(shù)，當sum數(shù)值過多時，則意味著大量粒子都在當前最優(yōu)值的周圍，有可能落入局部最優(yōu)，必須進行混沌擾動.作者提出了一種使用距離啟發(fā)信息來確定擾動范圍的方法，啟發(fā)信息如下：

將上述混沌粒子群算法中的第6步式（11）改為式（17），就可以達到混沌擾動范圍的自適應(yīng)變動.

5 基于改進的自適應(yīng)混沌粒子群算法選址

利用K-Medios方法結(jié)合改進后的混沌粒子群算法對式（5）進行求解.

5.1 改進的自適應(yīng)混沌粒子群算法描述

算法描述如下：

輸入：聚類個數(shù)k以及包含N個數(shù)據(jù)對象的樣本集.輸出：滿足式（5）最小的k個聚類.

處理流程：

Step1：初始化.設(shè)定最大進化代數(shù)MaxT和當前進化代數(shù)，并置t=1，在問題空間利用混沌初始化產(chǎn)生M個粒子，組成初始種群X(t).

Step2：使用改進后的混沌粒子群算法進行尋優(yōu).

Step3：對新一代粒子進行K-Mediods優(yōu)化.使用K-Mediods對新一代粒子劃分的類進行聚類分析，確定每個粒子劃分區(qū)域中的最佳中心點，并用其代替新粒子.

Step4：若達到最大代數(shù)或目標函數(shù)不再變化，則繼續(xù)執(zhí)行，否則轉(zhuǎn)Step2.

Step5：輸出最終的聚類結(jié)果.%%

新算法在產(chǎn)生下一代粒子時具有較大的遍歷性，所以不容易產(chǎn)生局部極小值，對新一代個體的KMediods算法優(yōu)化，更提高了收斂速度.由于不存在隨機尋優(yōu)的退化現(xiàn)象，因此后期收斂比較平穩(wěn)，很少有波動現(xiàn)象.

5.2 最優(yōu)解的判定

多目標優(yōu)化問題在大多數(shù)情況下，各個目標函數(shù)間可能是沖突的.這就導(dǎo)致多目標優(yōu)化問題不存在惟一的全局最優(yōu)解，使所有目標函數(shù)同時最優(yōu).但是，可以存在這樣的解：對一個或幾個目標函數(shù)不可能進一步優(yōu)化，而對其他目標函數(shù)不至于劣化，這樣的解稱之為非劣最優(yōu)解(Pareto optimal)，而將所有子目標函數(shù)最優(yōu)解組合成的解稱為多目標組合優(yōu)化問題的理想解.為此，對于每一個粒子所取得的較優(yōu)解與理想解的偏差τ作為算法的性能評價指標.在每一次迭代時所有粒子取得的解中對應(yīng)于最小偏差τ的糧食應(yīng)急點選址方案即為當前的最優(yōu)解.

在糧食應(yīng)急點選址中，僅需要考慮兩個優(yōu)化目標，粒子i所取得較優(yōu)解和理想解的的偏差τi如式(18)所示：

式中：ti1為粒子i選址方案中的最小總應(yīng)急運輸時間，ti2為方案中最小最遲應(yīng)急時間.t*1為理想最小總應(yīng)急運輸時間，為理想最小最遲應(yīng)急時間.

6 試驗與結(jié)果分析

圖1 兩種算法的貼近度收斂情況

圖2 使用ACPSO算法的求解結(jié)果

表1 應(yīng)急點建設(shè)時間d

對河南省區(qū)域內(nèi)的縣級以上城市數(shù)據(jù)集分別采用遺傳算法與改進的自適應(yīng)混沌粒子群算法（ACPSO）進行試驗和結(jié)果分析.考慮主要障礙物為黃河和淮河，聚類數(shù)目k=5，應(yīng)急點最早開始使用時間(數(shù)據(jù)為歸一化后的，縣級市取其所在地級市時間，不另給出)見表1，ω1=0.9,ω2=0.1,λ取救援目標的人數(shù)與總?cè)藬?shù)的比值.

遺傳算法的參數(shù)設(shè)置為：種群規(guī)模60，交叉概率0.8，變異概率0.05，迭代次數(shù)100代.粒子群參數(shù)設(shè)置：粒子個數(shù)60，最大迭代次數(shù)100，學(xué)習(xí)因子c1=c2=2, β=2，σ=0.001.

圖1是兩種算法的收斂曲線對比，由實驗結(jié)果可以看出，ACPSO的試驗結(jié)果具有較好的全局收斂性能，其收斂速度和收斂精度都較標準GA更好.圖2給出了使用ACPSO算法求解的最優(yōu)結(jié)果.

7 結(jié)束語

主要對一定區(qū)域下帶障礙約束的糧食應(yīng)急點選址進行了研究，結(jié)合糧食應(yīng)急的自身特點，建立了該問題的多目標優(yōu)化數(shù)學(xué)模型.針對傳統(tǒng)算法對初始值敏感和容易陷入局部極值的缺點，研究并提出了一種自適應(yīng)混沌粒子群算法.結(jié)果表明，該算法較好地解決了糧食應(yīng)急點選址問題.本算法使用了混沌系統(tǒng)對粒子群進行初始化和擾動，因此如何選取更佳的混沌系統(tǒng)使其更進一步優(yōu)化粒子群算法，是下一步進行研究的方向.

［1］ 何建敏,劉春林,曹杰,等.應(yīng)急管理與應(yīng)急系［M］.北京:科學(xué)出版社,2005:54-55.

［2］ Kennedy J,Eberhart R.Particle swarm optimization［C］//Proc of IEEE International Conference on Neural Networks,1995:1942-1948.

［3］ Clerc M,Kennedy J.The particle swarm-explosion,stability,and convergence in a multidimensional complex space［J］.IEEE Trans on Evolutionary Computation,2002,6(1):58-73.

［4］ Sun J,Feng B,Xu W B.Particle swans optimization with particles having quantum behavior［C］// IEEE Congresson EvolutionaryComputation, 2004:325-331.

［5］ 唐賢倫,莊陵,李銀國,等.基于粒子群優(yōu)化和模糊c均值聚類的入侵檢測［J］.計算機工程,2008,34 (4):13-15.

［6］ 田東平.基于Tent混沌序列的粒子群優(yōu)化算法［J］.計算機工程,2010,36(4):180-182.

RESEARCH ON SITE SELECTION OF GRAIN EMERGENCY SUPPLY LOCATION BASED ON SELF-ADAPTIVE CHAOS PARTICLE SWARM OPTIMIZATION

XIAO Le1,2,WU Xiang-lin1,ZHANG Xue-ping2
(1.Department.of Control Engineering,Huazhong University of Science and Technology,Wuhan 430074, China;2.School of Information Science and Engineering,Henan University of Technology,Zhengzhou 450001,China)

In order to solve the problem of site selection of grain emergency supply location,we established a corresponding optimization model to achieve the targets of the shortest transport time and the earliest emergency start time.We solved the model by use of a particle swarm-based k-medoids cluster algorithm,and we also put forward a self-adaptive chaos particle swarm optimization algorithm to avoid the solution from sinking to local optimum prematurely.The algorithm judged the current state of the particle swarm according to the Euclidean distance between particles and the known global optimum particle,and determined the chaos perturbation range by using the current state as the heuristic information so as to effectively improve accuracy of the optimal solution.The experiment showed that the algorithm was superior to the conventional evolutionary algorithm and could well solve the problem of site selection of grain emergency supply location.

grain emergency supply location;site selection;cluster;self-adaptive chaos particle swarm algorithm; distance heuristic information

TP311

A%%%%%%

1673-2383(2012)04-0077-05

http://www.cnki.net/kcms/detail/41.1378.N.20120829.1722.201204.77_018.html

網(wǎng)絡(luò)出版時間：2012-08-29 05:22:00 PM

2012-03-08

“十一五”國家科技支撐計劃重點項目(2008BADA8B03)；科技部科技型中小企業(yè)技術(shù)創(chuàng)新基金項目(10C26214102205)

肖樂(1972—)，男，河南開封人，副教授，博士研究生，研究方向為系統(tǒng)工程.