肖 樂，吳相林,張雪萍

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

考慮糧食應(yīng)急特點(diǎn)，在針對(duì)上述兩個(gè)目標(biāo)建立優(yōu)化模型時(shí)，需要引入相應(yīng)影響因子.

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

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

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

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

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

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

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

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

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

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

3.1 基本粒子群算法

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

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

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

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

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

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

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

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

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

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

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

計(jì)算目標(biāo)函數(shù)，初始化pbest和gbest，隨機(jī)產(chǎn)生m個(gè)速度.

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

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

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

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

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

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

4 距離啟發(fā)信息

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

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

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

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

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

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

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

算法描述如下：

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

處理流程：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)束語

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

［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］ 唐賢倫,莊陵,李銀國(guó),等.基于粒子群優(yōu)化和模糊c均值聚類的入侵檢測(cè)［J］.計(jì)算機(jī)工程,2008,34 (4):13-15.

［6］ 田東平.基于Tent混沌序列的粒子群優(yōu)化算法［J］.計(jì)算機(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ò)出版時(shí)間：2012-08-29 05:22:00 PM

2012-03-08

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

肖樂(1972—)，男，河南開封人，副教授，博士研究生，研究方向?yàn)橄到y(tǒng)工程.