一種群體智能融合算法及其在應(yīng)急設(shè)施選址的應(yīng)用＊

許 駿，許曉東

（華中科技大學(xué)公共管理學(xué)院，湖北 武漢 430074)

一種群體智能融合算法及其在應(yīng)急設(shè)施選址的應(yīng)用＊

許 駿，許曉東

（華中科技大學(xué)公共管理學(xué)院，湖北 武漢 430074)

針對(duì)粒子群優(yōu)化算法早熟及細(xì)菌覓食算法收斂慢的問題，提出了將量子粒子群優(yōu)化與細(xì)菌覓食算法融合的一種群體智能融合算法。該算法將細(xì)菌覓食、量子計(jì)算理論及粒子群優(yōu)化的優(yōu)點(diǎn)進(jìn)行融合，以細(xì)菌覓食算法為主體，將量子進(jìn)化算法及粒子群優(yōu)化算法嵌入其中，從而極大地提高了算法的性能。通過對(duì)三個(gè)標(biāo)準(zhǔn)函數(shù)求解和驗(yàn)證，結(jié)果表明該算法提高了收斂精度及速度。最后用該算法求解公共衛(wèi)生應(yīng)急服務(wù)設(shè)施點(diǎn)選址問題，取得了較好的效果，說明了該算法的有效性。

群體智能算法；量子粒子群優(yōu)化；細(xì)菌覓食算法；應(yīng)急選址

1 引言

群體智能算法［1，2］是一門新興的優(yōu)化計(jì)算方法，自20世紀(jì)80年代出現(xiàn)以來，引起了多個(gè)學(xué)科領(lǐng)域研究人員的關(guān)注，已經(jīng)成為優(yōu)化技術(shù)領(lǐng)域的一個(gè)研究熱點(diǎn)。這類算法的主要應(yīng)用對(duì)象是優(yōu)化問題中的難解問題，也就是優(yōu)化理論中的NP-hard問題。

群體智能算法本質(zhì)上是一種概率搜索，不需要問題的梯度信息，并具有如下特點(diǎn)：（1)群體中的個(gè)體代表問題空間中的一個(gè)解，能感知周圍的局部信息且遵循的規(guī)則非常簡單，群體智能易于實(shí)現(xiàn)；（2)個(gè)體在解的空間是分布式的，不存在直接的中心控制，這樣即使有個(gè)別個(gè)體出現(xiàn)故障，也不會(huì)影響群體對(duì)問題的求解，具有較強(qiáng)的魯棒性。同時(shí)，個(gè)體之間可以相互作用從而表現(xiàn)出群體的高度智能。群體智能算法的出現(xiàn)，使得原來一些復(fù)雜而且難以用常規(guī)優(yōu)化算法進(jìn)行處理的問題得到了解決，在工程實(shí)際中得到了廣泛應(yīng)用。常用的群體智能算法有遺傳算法、粒子群算法、細(xì)菌覓食算法、蟻群算法等。

群體智能算法的理論研究主要是研究算法特性，改進(jìn)其不足，提高其性能，主要包括兩個(gè)方面：一是從群體智能算法的自身特性加以研究，改進(jìn)其性能；二是將群體智能算法之間或者與其它算法融合，產(chǎn)生性能更佳的融合智能算法。本文提出了將量子粒子群優(yōu)化與細(xì)菌覓食融合的算法，該算法結(jié)合了粒子群優(yōu)化和細(xì)菌覓食算法的特點(diǎn)，并利用有關(guān)量子計(jì)算的理論基礎(chǔ)使之適用于離散空間。然后，通過標(biāo)準(zhǔn)函數(shù)進(jìn)行驗(yàn)證，進(jìn)而應(yīng)用于求解應(yīng)急服務(wù)設(shè)施點(diǎn)選址問題。

2 量子粒子群與細(xì)菌覓食的融合算法

2.1 量子粒子群與細(xì)菌覓食的融合策略

粒子群優(yōu)化PSO（Particle Swarm Optimization)算法首先由 Kennedy J和 Eberhart R C［3］提出，由于其簡潔性和快速性，一經(jīng)提出便引起許多研究者的關(guān)注，主要?dú)w結(jié)為算法本身改進(jìn)［4，5］、算法拓?fù)浣Y(jié)構(gòu)改進(jìn)［6，7］、算法參數(shù)的改進(jìn)［8］、混合粒子群算法［9］等方面的研究和改進(jìn)。這些研究使PSO成為一種有競爭力的群體智能優(yōu)化技術(shù)，并廣泛應(yīng)用于連續(xù)空間的尋優(yōu)問題。

其中，k為迭代次數(shù)，ω為權(quán)系數(shù)，c1、c2為加速因子，r1、r2為［0，1］的隨機(jī)數(shù)。

在式（1)所描述的粒子速度進(jìn)化方程中，第一項(xiàng)是粒子先前的速度，第二項(xiàng)代表“認(rèn)知”部分，但僅考慮了粒子自身的“經(jīng)驗(yàn)”，第三項(xiàng)則代表了“社會(huì)”部分，即粒子間的社會(huì)信息共享。這樣粒子在相互作用下，有能力到達(dá)新的搜索空間。不過，雖然它的收斂速度較快，但對(duì)于復(fù)雜問題，容易陷入局部最優(yōu)點(diǎn)［10］。

細(xì)菌覓食算法BFA（Bacterial Foraging Algorithm)是由Passino K M［11］于2002年提出來的一種仿生隨機(jī)搜索算法，通過模擬人類腸道中大腸桿菌的覓食行為，在搜索過程中通過營養(yǎng)分布函數(shù)來判斷搜索算法的優(yōu)劣。該算法因具有群體智能算法并行搜索、易跳出局部極值等優(yōu)點(diǎn)，成為生物啟發(fā)式計(jì)算研究領(lǐng)域的又一熱點(diǎn)。

在BFA中，優(yōu)化問題的解對(duì)應(yīng)于搜索空間中的細(xì)菌的狀態(tài)，即優(yōu)化函數(shù)的適應(yīng)度值。BFA包括趨化、復(fù)制和驅(qū)散三個(gè)步驟［12］，其主要步驟為趨化行為。細(xì)菌的趨化性操作可表示如下：

其中，θi（j，k，l)表示細(xì)菌i在第j次趨化操作、第k次復(fù)制操作和第l次驅(qū)散操作時(shí)的位置，c（i)表示趨化步長，φ（j)表示旋轉(zhuǎn)后選擇的一個(gè)隨機(jī)前進(jìn)方向。

由于BFA在趨化中采用任意方向進(jìn)行翻轉(zhuǎn)，沒有利用歷史信息，導(dǎo)致收斂速度較慢。2008年Dasgupta S和 Das S等人［13，14］對(duì)趨化操作分析后指出：當(dāng)適應(yīng)度函數(shù)形狀較為平坦時(shí)，趨化在接近優(yōu)化值時(shí)會(huì)產(chǎn)生振蕩，文獻(xiàn)［13，14］建議對(duì)趨化步長給以約束。本文利用PSO中個(gè)體極值和全局極值信息來確定細(xì)菌前進(jìn)的方向，從而確定趨化的最佳方向，表達(dá)為：其中r1i、r2i分別為粒子歷史最優(yōu)和全局最優(yōu)權(quán)系數(shù)，通過與當(dāng)前粒子適應(yīng)度值比較而確定其值，表達(dá)為：

趨化步長對(duì)收斂性能影響較大，步長越大算法收斂越快，但易跳過最優(yōu)值，而較小步長則增加了搜索時(shí)間。本文根據(jù)迭代次數(shù)自適應(yīng)地改變步長，即開始使用大的步長，接近最優(yōu)值時(shí)采用小步長，即：

其中，itermax是最大迭代次數(shù)，k是當(dāng)前迭代次數(shù)。改進(jìn)后趨化操作的進(jìn)化方程為：

但是，上述對(duì)算法的改進(jìn)策略僅適用于連續(xù)解空間。為了適應(yīng)于離散空間，本文利用量子計(jì)算理論基礎(chǔ)，采用量子比特方式來表示每個(gè)細(xì)菌位置的狀態(tài)。一個(gè)具有n個(gè)量子比特位的系統(tǒng)可以描述為［15］：

量子比特位的狀態(tài)改變可由進(jìn)化方程（2)通過量子旋轉(zhuǎn)門計(jì)算得到［15］，即狀態(tài)更新方程為：

假設(shè)第i個(gè)細(xì)菌的位置向量Xi＝ ｛xi1，…，xin｝，位置向量的更新由其存儲(chǔ)在量子比特q中的β值確定，即：

2.2 量子粒子群優(yōu)化與細(xì)菌覓食融合算法的實(shí)現(xiàn)

細(xì)菌位置代表一個(gè)解，解的優(yōu)劣由系統(tǒng)適應(yīng)度函數(shù)來確定。融合算法搜索最優(yōu)解的步驟如下：

Step 1 初始化參數(shù)設(shè)置。其中，n為搜索空間維數(shù)；S為細(xì)菌種群數(shù)；Nc為趨化循環(huán)次數(shù)；Nre為復(fù)制循環(huán)次數(shù)；Ned為遷移循環(huán)次數(shù)；Ped為遷移概率；θmin、θmax為最小、最大旋轉(zhuǎn)角；、為1/。

Step 2遷移循環(huán)：l＝l＋1。

Step 3復(fù)制循環(huán)：k＝k＋1。

Step 4趨化循環(huán)：j＝j(luò)＋1。

Step 4.1選取細(xì)菌i，計(jì)算細(xì)菌i所在位置的適應(yīng)度值：J（i，j，k，l)，并保存該值到Jlast；

Step 4.2由公式（2)計(jì)算細(xì)菌i每一位的旋轉(zhuǎn)值；

Step 4.3由公式（3)和公式（4)計(jì)算細(xì)菌i的新位置，并計(jì)算新位置的適應(yīng)度值J（i，j，k，l)；

Step 4.4更新細(xì)菌i的局部最優(yōu)值和種群全局最優(yōu)值。

Step 5循環(huán)Step 4，直到趨化循環(huán)完畢。

Step 6復(fù)制：將適應(yīng)度值差的細(xì)菌淘汰一半。為保證個(gè)體總數(shù)一致性，再對(duì)剩余的細(xì)菌進(jìn)行復(fù)制。

Step 7重復(fù)Step 3，直至復(fù)制循環(huán)完畢。

Step 8遷移：以一定的概率Ped選取部分細(xì)菌，將其驅(qū)散到其它位置，剩余細(xì)菌的位置保持不變。

Step 9重復(fù)Step 2，直至遷移循環(huán)完畢。

Step 10結(jié)束。

2.3 算法性能測試

目前常用求解測試函數(shù)的最優(yōu)值的問題來檢驗(yàn)智能優(yōu)化算法，這些測試函數(shù)有單峰，也有多峰的，函數(shù)解的分布是連續(xù)變化的。本文使用下列三個(gè)標(biāo)準(zhǔn)函數(shù)來驗(yàn)證群體融合智能算法的精度及收斂性能。

上述三個(gè)標(biāo)準(zhǔn)函數(shù)的維數(shù)為N。其中，Sphere函數(shù)具有單峰，最小值f（0)＝0，該函數(shù)的特點(diǎn)是曲面平滑，梯度信息總是能指向全局最優(yōu)；Rosenbrock函數(shù)也是一個(gè)單峰函數(shù)，曲面光滑，但梯度信息經(jīng)常誤導(dǎo)算法的搜索方向，算法較難搜索到全局最優(yōu)解，全局最小值f（1)＝1；而Rastrigin函數(shù)具有多峰，有許多局部最小值，很難找到全局最優(yōu)解，優(yōu)化算法易陷入局部最優(yōu)點(diǎn)，全局最小值f（0)＝0。

（1)算法參數(shù)分析。

本文提出算法中沒有太多需要調(diào)節(jié)的參數(shù)，因此只對(duì)最大、最小旋轉(zhuǎn)角、種群規(guī)模等參數(shù)進(jìn)行分析。趨化操作及復(fù)制操作影響可參考文獻(xiàn)［13］，最大迭代次數(shù)分析由下文給出。

種群規(guī)模表示算法中同時(shí)進(jìn)行搜索的細(xì)菌數(shù)目，決定了目標(biāo)函數(shù)達(dá)到收斂值需要進(jìn)行評(píng)價(jià)的最少次數(shù)。一般而言，種群規(guī)模大有利于在狀態(tài)空間內(nèi)更充分搜索，同時(shí)可減少迭代次數(shù)，但是評(píng)價(jià)次數(shù)也相應(yīng)增加。圖1是使用Rastrigin函數(shù)在不同種群規(guī)模下迭代1 000次時(shí)，計(jì)算機(jī)所用的時(shí)間及收斂值。從圖1中可以看出，種群規(guī)模選擇在20～40可取得較為合理的結(jié)果。

最大、最小旋轉(zhuǎn)角選用文獻(xiàn)［15］推薦值0.05π和0.001π，圖2顯示的是種群分別為10和30的情況下迭代1 000次不同最大、最小旋轉(zhuǎn)角的組合對(duì)收斂性能影響的結(jié)果。從圖2中可知，最大、最小旋轉(zhuǎn)角分別選用0.05π和0.01π最佳。

（2)算法性能分析。

Figure 1 Influence of population size on the performance of algorithm圖1 種群數(shù)量對(duì)算法性能的影響

Figure 2 Influence of maximum ＆minimum rotation angle combination on the performance of algorithm圖2 最大、最小旋轉(zhuǎn)角組合對(duì)算法性能的影響

為了驗(yàn)證本文提出的群體智能融合算法的收斂精度及收斂時(shí)間，本文采用前述三個(gè)經(jīng)典標(biāo)準(zhǔn)函數(shù)進(jìn)行驗(yàn)證，并同時(shí)與其它算法進(jìn)行比較。使用的參數(shù)為：遷移概率Ped＝0.25，最大、最小旋轉(zhuǎn)角分別取0.05π和0.01π，細(xì)菌種群數(shù)S＝20、復(fù)制次數(shù)Nre＝4、遷移次數(shù)Ned＝5，趨化次數(shù)Nc則隨函數(shù)復(fù)雜程度不同而變化。

首先，用 GA-BFO［16］、PSO-BFO［17］及本文算法分別對(duì)標(biāo)準(zhǔn)函數(shù)求解，每個(gè)函數(shù)獨(dú)立執(zhí)行50次，計(jì)算均值及方差，收斂精度結(jié)果見表1，收斂速度結(jié)果見表2。

表1列出了不同算法對(duì)標(biāo)準(zhǔn)函數(shù)收斂到0.001或運(yùn)行到規(guī)定的最大迭代次數(shù)時(shí)的情況（表中的黑體標(biāo)記為不同算法收斂的最好值，方差為0的沒有標(biāo)明)。從表1中可以看出，對(duì)于Sphere函數(shù)，維數(shù)為15時(shí)表中所選算法都能很快地收斂?？傮w來說，本文提出的融合算法收斂精度較其他算法高，特別當(dāng)函數(shù)的維數(shù)比較大時(shí)。表2展示了函數(shù)收斂到規(guī)定閾值0.000 1時(shí)，算法獨(dú)立運(yùn)行50次的迭代次數(shù)的均值與方差。從表2可以看出，對(duì)于Sphere函數(shù)，所有算法都能收斂，但對(duì)于Rosenbrock、Rastrigin兩個(gè)函數(shù)，在高維時(shí)，只有本文提出的算法能夠收斂，其它算法由于早熟而不能收斂到規(guī)定值（算法迭代的最高次數(shù)不高于1010)。

3 本文提出的算法求解公共衛(wèi)生應(yīng)急服務(wù)設(shè)施點(diǎn)選址問題

3.1 建模

直接面對(duì)居民“最后一公里”的應(yīng)急服務(wù)設(shè)施點(diǎn)的選址對(duì)保障應(yīng)急資源在短時(shí)間內(nèi)高效地提供給受威脅地區(qū)每個(gè)居民是至關(guān)重要的，其選擇影響到衛(wèi)生應(yīng)急中應(yīng)急資源供應(yīng)最大最優(yōu)，影響著整個(gè)系統(tǒng)的快速反應(yīng)能力。對(duì)于分布寬廣的“最后一公里”的應(yīng)急服務(wù)設(shè)施點(diǎn)的選址，必須確保覆蓋到所有災(zāi)區(qū)中每一戶家庭，同時(shí)，為防止意外，每個(gè)行政區(qū)內(nèi)至少要設(shè)置兩個(gè)應(yīng)急服務(wù)設(shè)施點(diǎn)。顯然，設(shè)施點(diǎn)的數(shù)量與其容量及服務(wù)的人數(shù)有關(guān)，每個(gè)設(shè)施點(diǎn)需要的資源需要統(tǒng)籌規(guī)劃，以確保在規(guī)定時(shí)間內(nèi)完成任務(wù)。本文中假設(shè)每個(gè)設(shè)施點(diǎn)的資源已確定，即容量已知，服務(wù)對(duì)象到相應(yīng)設(shè)施點(diǎn)的距離不超過設(shè)置的最遠(yuǎn)距離，在上述條件下確定應(yīng)急服務(wù)設(shè)施點(diǎn)的數(shù)量。

Table 1 Mean and variance of the objective function after different algorithm running independently（N＝50)表1 不同算法獨(dú)立運(yùn)行后目標(biāo)函數(shù)的均值及方差（N＝50次)

Table 2 Comparison of iteration number to the convergence of different algorithm running to the provisions threshold（N＝50)表2 收斂到規(guī)定閾值0.000 1時(shí)不同算法運(yùn)行的迭代次數(shù)比較（N＝50次)

選址問題本身是一個(gè)非常經(jīng)典的問題，有成熟的解決模型，然而應(yīng)急服務(wù)設(shè)施點(diǎn)選址問題與傳統(tǒng)選址問題具有不同的優(yōu)化約束與目標(biāo)，前者時(shí)效性可能非常重要，而后者則更加關(guān)注成本。選址問題已被證明是一類極難優(yōu)化的問題集，即NP-hard問題，至今未能有效精確求解［18］。已有的精確式算法都是指數(shù)級(jí)的，無法解決現(xiàn)實(shí)問題（中、大規(guī)模)。在實(shí)際應(yīng)用時(shí)，近似算法特別是智能優(yōu)化算法是求解NP-hard問題的有效方法之一［19］。本文通過對(duì)公共衛(wèi)生應(yīng)急服務(wù)設(shè)施點(diǎn)選址進(jìn)行了建模，并用本文提出的算法求解應(yīng)急服務(wù)設(shè)施點(diǎn)選址問題。

為了確定應(yīng)急服務(wù)設(shè)施點(diǎn)的數(shù)量及服務(wù)的范圍，本文首先對(duì)要服務(wù)的目標(biāo)區(qū)域離散化，即將目標(biāo)區(qū)域劃分成大小為一平方公里的網(wǎng)格。每個(gè)網(wǎng)格與所服務(wù)的人口聯(lián)系起來，可認(rèn)為是一個(gè)候選的應(yīng)急服務(wù)設(shè)施點(diǎn)。對(duì)給定的目標(biāo)區(qū)域，可以使用如下參數(shù)來描述與設(shè)施點(diǎn)有關(guān)的變量：

kem：事件發(fā)生地行政區(qū)的數(shù)目；

Gi：在行政區(qū)i內(nèi)所有網(wǎng)格的集合，i≤kem；

cl：網(wǎng)格l內(nèi)的應(yīng)急服務(wù)設(shè)施點(diǎn)容量；

pr：網(wǎng)格r內(nèi)的人口數(shù)量；

d（r，l)：網(wǎng)格r、l之間的距離；

dmax：服務(wù)對(duì)象到相應(yīng)的應(yīng)急服務(wù)設(shè)施點(diǎn)允許的最遠(yuǎn)距離。

決策變量設(shè)為：

yl：如果網(wǎng)格l內(nèi)設(shè)置了應(yīng)急服務(wù)設(shè)施點(diǎn)，則為1，否則為0；

xrl：如果網(wǎng)格l內(nèi)的應(yīng)急點(diǎn)為網(wǎng)格r內(nèi)的公民服務(wù)，則為1，否則為0。

則應(yīng)急服務(wù)設(shè)施點(diǎn)的選址可用如下數(shù)學(xué)模型來描述：

目標(biāo)函數(shù)在滿足需求的條件下，使應(yīng)急服務(wù)設(shè)施點(diǎn)的數(shù)目最小。其中，約束條件（5)保證在每個(gè)行政區(qū)內(nèi)至少要設(shè)置兩個(gè)應(yīng)急服務(wù)設(shè)施點(diǎn)，以防在意外災(zāi)難發(fā)生而必須關(guān)閉設(shè)施點(diǎn)時(shí)，另一個(gè)應(yīng)急設(shè)施點(diǎn)還能正常運(yùn)行；約束條件（6)限制了每個(gè)用戶到達(dá)應(yīng)急服務(wù)設(shè)施點(diǎn)的距離需小于最遠(yuǎn)行駛距離；約束條件（7)保證每戶都能得到服務(wù)；約束條件（8)則要求設(shè)施點(diǎn)所能提供的服務(wù)量不能大于其容量；約束條件（9)限定決策變量是0/1變量。約束條件

3.2 實(shí)現(xiàn)

為了求解公共衛(wèi)生應(yīng)急資源選址問題，必須先確定問題空間的編碼方式、粒子適應(yīng)度函數(shù)、種群的初始化等。

（1)問題的編碼方式。

當(dāng)采用本文提出的算法求解問題時(shí)，首先必須在目標(biāo)問題實(shí)際表示與種群個(gè)體之間建立聯(lián)系，即采用某種編碼方式將解空間映射到編碼空間。本文將應(yīng)急區(qū)域用網(wǎng)格進(jìn)行劃分，對(duì)網(wǎng)格進(jìn)行編號(hào)，然后采用二進(jìn)制編碼，碼的位數(shù)與網(wǎng)格的編號(hào)一一對(duì)應(yīng)。比如，現(xiàn)有編號(hào)為0、1、2、3、4、5的網(wǎng)格，則對(duì)應(yīng)的二進(jìn)制編碼為110010，位0對(duì)應(yīng)于0號(hào)網(wǎng)格，位1對(duì)應(yīng)于1號(hào)網(wǎng)格，依次類推。二進(jìn)制相應(yīng)位如果是“0”表示在此網(wǎng)格中沒有應(yīng)急服務(wù)設(shè)施點(diǎn)，是“1”則表示網(wǎng)格中設(shè)置有應(yīng)急服務(wù)設(shè)施點(diǎn)，上述例子中，1、4、5號(hào)網(wǎng)格中應(yīng)設(shè)置設(shè)施點(diǎn)。網(wǎng)格排列的值的變化構(gòu)成了問題的狀態(tài)空間，顯然，一個(gè)排列代表了一個(gè)解。

（2)確定適應(yīng)度函數(shù)。

適應(yīng)度函數(shù)是由問題的目標(biāo)函數(shù)變化而成的。對(duì)應(yīng)急服務(wù)設(shè)施點(diǎn)選址問題，還必須滿足約束條件。為此，適應(yīng)度函數(shù)包括三部分：第一部分與目標(biāo)函數(shù)有關(guān)，本文應(yīng)急服務(wù)設(shè)施點(diǎn)采用了二進(jìn)制編碼方式，因此，解的二進(jìn)制中“1”的個(gè)數(shù)即為設(shè)施點(diǎn)的數(shù)量，此部分設(shè)為fem1；對(duì)于不滿足約束條件（5)的行政區(qū)的數(shù)量設(shè)為fem2，這一部分必須加入到適應(yīng)度函數(shù)中，為第二部分；第三部分與服務(wù)對(duì)象有關(guān)，涉及到約束條件（6)～約束條件（8)。依據(jù)最近法則，確定可為每個(gè)服務(wù)對(duì)象提供服務(wù)的設(shè)施點(diǎn)，當(dāng)超過其容量時(shí)，到次近的設(shè)施點(diǎn)，直到無設(shè)施點(diǎn)可用或者到設(shè)施點(diǎn)的距離超過設(shè)定的最遠(yuǎn)距離為止。此時(shí)對(duì)剩余的服務(wù)對(duì)象進(jìn)行聚類統(tǒng)計(jì)，相互之間的距離小于最遠(yuǎn)距離的歸為一類，分類的數(shù)量即為fem3，則適應(yīng)度函數(shù)f＝fem1＋fem2＋fem3，在fem2、fem3都為零的情況下適應(yīng)度函數(shù)越小越優(yōu)。

（3)種群的初始化。

種群個(gè)體數(shù)量一般在20～40，與解空間的狀態(tài)有關(guān)，本文數(shù)量選為30。個(gè)體的初始位置采用貪婪算法選取，使之滿足所有約束條件。

3.3 算例

以武漢市為例，總?cè)丝?78萬人，有13個(gè)行政區(qū)，用一平方公里網(wǎng)格對(duì)區(qū)域作劃分，每個(gè)行政區(qū)網(wǎng)格數(shù)量在34～2 261，每個(gè)網(wǎng)格人口數(shù)量在321～20 711。模型的問題規(guī)模約束條件和0/1變量數(shù)量從最小1 225＊1 190到最大5 116 644＊5 114 382。

為了說明本算法性能，本文分別用LINGO 10、GA-BFO和本文算法求解，迭代次數(shù)1 000次，計(jì)算結(jié)果如表3所示。

Table 3 Calculating results of running time and facilities point number of different algorithm表3 不同算法的運(yùn)行時(shí)間及設(shè)施點(diǎn)數(shù)量計(jì)算結(jié)果

從表3中可以看出，當(dāng)應(yīng)急設(shè)施點(diǎn)容量為2 000人/h時(shí)，采用LINGO 10的運(yùn)算時(shí)間最短，但當(dāng)問題的規(guī)模變大，如設(shè)施點(diǎn)容量為500人/h時(shí)，則不能求解，而本文提出的算法僅用90分鐘就可以完成。因此，求解問題規(guī)模越大，本文提出的算法優(yōu)勢越明顯。

表4的結(jié)果顯示了當(dāng)應(yīng)急服務(wù)設(shè)施點(diǎn)容量不同時(shí)，限制的最遠(yuǎn)距離與應(yīng)急服務(wù)設(shè)施點(diǎn)數(shù)量之間的關(guān)系。圖3則顯示在設(shè)施點(diǎn)容量和最遠(yuǎn)距離一定時(shí)，實(shí)際旅行距離下到應(yīng)急設(shè)施點(diǎn)接受服務(wù)的居民數(shù)量分布的概率。

Table 4 Numbers of facility points needed in different capacity under different maximum distances表4 不同容量下不同最遠(yuǎn)距離所需設(shè)施點(diǎn)的數(shù)目

Figure 3 Relationship between the actual driving distance and the residents distribution proportion（parametric assumption：capacity＝1 500person/hour，maximum distance＝10km)圖3 實(shí)際行駛距離與居民分布比例的關(guān)系

4 結(jié)束語

本文基于細(xì)菌覓食算法、粒子群優(yōu)化及量子計(jì)算的特點(diǎn)提出的群體智能融合算法，是將粒子群優(yōu)化的思想融入細(xì)菌覓食算法中，充分利用了個(gè)體的信息，使收斂速度大大加快，解決了由于隨機(jī)的搜索方向?qū)е录?xì)菌覓食算法收斂時(shí)間增加的問題，從而極大地提高了算法的性能。同時(shí)，采用量子比特位來存儲(chǔ)細(xì)菌的狀態(tài)，從而使算法適用于離散空間。本文通過對(duì)三個(gè)標(biāo)準(zhǔn)函數(shù)在不同維數(shù)下的求解，驗(yàn)證該算法在收斂性能方面的提高。最后用該算法求解公共衛(wèi)生應(yīng)急選址的問題，得到了較好的效果，表明該算法是一種有效的方法。

［1］ Bonabeau E，Dorigo M，Theraulaz G.Swarm intelligence：From natural to artificial systems［M］.1st edition.New York：Oxford University Press，1999.

［2］ Bonabeau E，Dorigo M，Theraulaz G.Inspiration for optimization from social insect behaviour［J］.Nature，2002，406（6)：39-42.

［3］ Kennedy J，Eberhart R C.Particle swarm optimization［C］∥Proc of IEEE International Conference on Neural Networks，1995：1942-1948.

［4］ Clerc M，Kennedy J.The particle swarm-explosion，stability，and convergence in a multidimensional complex space［J］.IEEE Transactions on Evolutionary Computation，2002，6（1)：58-73.

［5］ Ratnaweera A，Halgamuge S，Watson H.Self-organizing hierarchical particle swarm optimizer with time-varying accelerating coefficients［J］.IEEE Transactions on Evolutionary Computation，2004，8（3)：240-255.

［6］ Hu X H，Eberhart R C.Multi-objective optimization using dynamic neighborhood particle swarm optimization［C］∥Proc of the Congress on Evolutionary Computation，2002：606-607.

［7］ Mendes R，Kennedy J，Neves J.The fully informed particle swarm：Simpler，maybe better［J］.IEEE Transactions on Evolutionary Computation，2004，8（3)：204-210.

［8］ Eberhart R C，Yu S.Guest editorial special issue on particle swarm optimization［J］.IEEE Transactions on Evolutionary Computation，2004，8（3)：201-203.

［9］ Higashi N，Iba H.Particle swarm optimization with Gaussian mutation［C］∥ Proc of the Congress on Evolutionary Computation，2003：72-79.

［10］ Kennedy J，Mendes R.Neighborhood topologies in fully-informed and best-of-neighborhood particle swarms［J］.IEEE Transactions on Systems，Man，and Cybernetics，2006，36（4)：515-519.

［11］ Passino K M.Biomimicry of bacterial foraging for distributed optimization and control［J］.IEEE Control Systems Magazine，2002，22（3)：52-67.

［12］ Das S，Biswas A，Dasgupta S.Bacterial foraging optimization algorithm：Theoretical foundations，analysis，and applications［M］.Heidelberg：Springer-Verlag，2009：23-55.

［13］ Dasgupta S，Das S，Abraham A，et al.Adaptive computational chemotaxis in bacterial foraging algorithm［C］∥Proc of the 2nd International Conference on Complex，Intelligent and Software Intensive Systems，2008：64-71.

［14］ Das S，Dasgupta S，Biswas A，et al.On stability of the chemotactic dynamics in bacterial foraging［C］∥ Proc of International Conference on Soft Computing as Transdisciplinary Science and Technology，2008：245-251.

［15］ Han K H，Kim J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization［J］.IEEE Transactions on Evolutionary Computation，2002，6（6)：580-593.

［16］ Kim D H，Abraham A，Cho J H.A hybrid genetic algorithm and bacterial foraging approach for global optimization［J］.Information Sciences，2007，177（18)：3918-3937.

［17］ Biswas A，Dasgupta S，Das S，et al.Synergy of PSO and bacterial foraging optimization：A comparative study on numerical benchmarks［M］∥Innovations in Hybrid Intelligent Systems，2007：255-263.

［18］ Yang Feng-mei，Hua Guo-wei，Deng Meng，et al.Some advances of the researches on location problems［J］.Operations Research and Management Science，2005，14（6)：1-7.（in Chinese)

［19］ Edson L F S，Luiz A N L，Marcos A P.A decomposition heuristic for the maximal covering location problem［J］.Advances in Operations Research，2010，2010：1-12.

附中文參考文獻(xiàn)：

［18］ 楊豐梅，華國偉，鄧猛，等.選址問題研究的若干進(jìn)展［J］.運(yùn)籌與管理，2005，14（6)：1-7.

A fusion algorithm of swarm intelligence and its application in emergency services facility location

XU Jun，XU Xiao-dong
（School of Public Administration，Huazhong University of Science and Technology，Wuhan 430074，China)

In order to solve the problem of prematurity of swarm intelligence algorithm and slow speed of convergence of bacterial forging algorithm，an algorithm is proposed，which fuses quantum particle swarm together with bacteria foraging optimization.After considering the advantages of bacteria foraging optimization，quantum computing theory and particle swarm optimization，the proposed fusion algorithm takes the bacterial foraging algorithm as the main body and embedded quantum evolutionary algorithm and particle swarm optimization algorithm into it，thus improving the performance of the algorithm greatly.Through solving and validating the three criteria functions，the results show that the proposed fusion algorithm improves convergence precision and speed.Finally，the proposed algorithm is used to solve public health emergency service facility location problem and achieves good results，proving its effectiveness.

swarm intelligence algorithm；quantum particle swarm optimization；bacterial foraging algorithm；emergency service facilities point location

TP399；X43

A

10.3969/j.issn.1007-130X.2014.04.017

2012-10-08；

2013-03-05

通訊地址：430015湖北省武漢市江岸區(qū)江漢北路24號(hào)

Address：24Jianghan Rd North，Jiang’an District，Wuhan 430015，Hubei，P.R.China

1007-130X（2014)04-0667-07

許駿（1971-)，女，湖北隨州人，博士生，研究方向?yàn)楣舶踩A(yù)警與應(yīng)急管理。E-mail：xujun＠whcdc.org

XU Jun，born in 1971，PhD candidate，her research interests include public safety early warning，and emergency management.