摘 要: 結(jié)合粒子群算法提出一個城市消防點選址問題的研究模型,。該算法利用局部尋優(yōu)能力對初始粒子進行優(yōu)化,,并利用粒子群優(yōu)化算法進行全局尋優(yōu),。
關(guān)鍵詞: 消防點;選址,;粒子群,;優(yōu)化
城市空間選址是城市規(guī)劃的重要內(nèi)容之一,,解決該問題最直接的方法是對所有的可能組合方案進行評價,找到最佳的方案,,這種方法可以稱為Brute-force搜索方法,,它能保證獲得最優(yōu)值。但是,,這種方法的計算量十分驚人,。當目標數(shù)目和搜索空間較大時,所涉及的組合可以有天文數(shù)字之巨,,大多情況下高性能的計算機也無法在可接受的時間內(nèi)完成計算任務,。
粒子群優(yōu)化算法PSO(Particle Swarm Optimization)是一類隨機全局搜索技術(shù),通過微粒個體對歷史信息(個體極值)和社會信息的共享(全局極值)發(fā)現(xiàn)復雜搜索空間中的最優(yōu)區(qū)域,。同遺傳算法類似,,粒子群優(yōu)化算法是一種基于群體的演化計算技術(shù)。系統(tǒng)初始化為一組隨機解,,通過迭代搜尋最優(yōu)值,。但是PSO并沒有遺傳算法的交叉以及變異操作,而是粒子(潛在的解)在解空間追隨最優(yōu)的粒子的過程,。目前,,已提出了多種PSO改進算法,并且已廣泛應用于函數(shù)優(yōu)化,、神經(jīng)網(wǎng)絡訓練,、模式分類、模糊系統(tǒng)控制以及其他的應用領域,。PSO最早是由Kennedy和Eberhart于1995年提出的,。受到人工生命的研究結(jié)果啟發(fā), PSO的基本概念源于對鳥群捕食行為的研究,。PSO中,,每個優(yōu)化問題的潛在解都是搜索空間中的1只“鳥”,稱之為“粒子”,。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應值,,每個粒子的速度決定它們飛翔的方向和距離,粒子們追隨當前的最優(yōu)粒子在解空間中搜索,。PSO初始化為一群隨機粒子(隨機解),,通過迭代找到最優(yōu)解。在每一次迭代中,,粒子通過跟蹤2個極值來更新自己,。第1個就是粒子本身所找到的最優(yōu)解,即為個體極值,;第2個極值是整個種群目前找到的最優(yōu)解[1-2],,這個極值是全局極值,。由于PSO概念簡單、容易實現(xiàn)并且沒有許多參數(shù)需要調(diào)整,,同時又有深刻的智能背景,,既適合科學計算、又適合工程應用,。短短幾年里,, PSO算法已經(jīng)獲得了很大的發(fā)展,目前已廣泛應用于函數(shù)優(yōu)化,、車間調(diào)度等問題,。
1 消防點選址
本文利用PSO算法的這些特點,提出了解決消防點選址的粒子群優(yōu)化算法,。城市消防點選址問題的研究,,有其特殊性:
(1)消防點地址的選擇與消防責任區(qū)的劃分;
(2)基于行車距離的計算,;
(3)責任區(qū)應該按照固定的邊界(如街道)進行,;
(4)各責任區(qū)內(nèi)針對消防主題具有不同的消防權(quán)重。
基于消防點選址至關(guān)重要的特點,,近幾十年科研人員對這一問題開展了工作,,建立了一系列的選址模型與算法。這些模型大致可歸納為2種方法:
(1)應用連續(xù)型模型選擇地點,;
(2)應用離散型模型選擇地點,。
第1種方法認為,消防站的地點可取直角坐標上的任意點,;第2種方法認為,,消防站的被選地點是有限的幾個場所,最合適的地點只能從中選出,。對于連續(xù)型模型主要是應用重心法進行求解,,對于離散型模型則主要是應用整數(shù)規(guī)劃法和逐次逼近法進行計算。本文提出了基于粒子群算法的城市消防點布局研究通用框架,,并以城市消防點規(guī)劃數(shù)據(jù)為例進行了研究對比分析,。
2 消防點選址模型及粒子群優(yōu)化算法的實現(xiàn)
2.1 模型分析與建立
一個簡化的城市如圖1所示,邊表示主要街道,,頂點表示大型交叉路口?,F(xiàn)計劃在某些路口安置消防點,只有與路口直接相連的街道才能安置,,在哪些路口安置消防點最好?
顯然在每個路口設置消防點即可以達到每個街道都覆蓋的目的,,但從經(jīng)濟角度考慮,,這是不必要的,。不難發(fā)現(xiàn),在v1,,v3,,v5或v2,v4,,v5各安置1個消防點就可以保證每個街道都有安全機構(gòu),,但是只在2個路口安置消防點是不可行的??梢钥闯?,這是一個研究圖的頂點與邊的關(guān)系問題,屬于圖的覆蓋問題,。即包括邊覆蓋和點覆蓋2種情況,,邊覆蓋是用邊覆蓋點;點覆蓋是用點控制邊,。而消防點安置問題屬于點情況,。
2.2 地理信息的處理
事實上,要使火災損失達到最小,,最重要的是消防隊接到火警后應能夠盡快到達火災現(xiàn)場[4],。因此,本文的研究采取以消防點平均消防行車距離最小為消防點的選址重要原則,,對地理信息的處理如圖2所示,。
2.3 算法的實現(xiàn)
利用本文提出的粒子群優(yōu)化算法對消防點的地址進行求解。該算法的優(yōu)化過程如圖3所示,。
本文較為全面,、深入地介紹了消防點選址方法、粒子群優(yōu)化算法以及兩者的結(jié)合應用,,在研究過程中,,主要做了以下的分析:
(1)全面分析消防點選址的基本理論、目標定位,、基本原則,、研究內(nèi)容以及所涉及到的相關(guān)因素等,系統(tǒng)提出消防點選址影響因素,。
(2)詳細介紹了粒子群優(yōu)化算法的理論基礎,,包括粒子群算法的基本實現(xiàn)技術(shù)以及其數(shù)學理論基礎。
(3)建立消防點選址模型,,在基本粒子群優(yōu)化算法的基礎上,,對其進行改進,分析了利用粒子群算法對該模型的求解過程,。
參考文獻
[1] 郜振華.粒子群優(yōu)化算法在配送中心連續(xù)性選址中的應用[J].計算機應用,,2008,,28(9):2401-2404.
[2] 柯晶,錢積新,,喬誼正.一種改進的粒子群優(yōu)化算法[J].電路與系統(tǒng)學報,,2003,8(5):87-91.
[3] 李志林,,歐宜貴.數(shù)學建模及典型案例分析[M].北京:化學工業(yè)出版社,,2007.
[4] 張艷霞,霍佳震.物流中心選址的模糊方法研究[J].物流技術(shù),,2002(8):20-21.