基于粒子群算法的無容量限制設施尋位問題研究

房屋檢測問題是一種廣泛使用的聯合優化問題，主要包括以下三種類型：限制房屋檢測、限制房屋檢測和k-中心件件。這里主要討論了無容量限制設施的檢測，也稱為簡單設施搜索問題，這是一門需要稱職的問題。這是一門需要共同努力的問題。它對數學、科學、物流、管理和其他學科都有重要意義。粒子群算法是近年來出現的一種基于對鳥群覓食行為模擬的仿生算法.最初,算法只用來處理連續優化問題,因其簡單有效的特點,PSO已經得到眾多學者的重視和研究,其應用也已擴展到了組合優化問題,并取得了很好的效果.將粒子群算法應用到求解無容量限制設施尋位問題中,試驗結果表明此方法可行有效.1建設設施方案UFL一般可描述為:給定兩個有限集合,設施集為I={1,2,…,m},即有m個位置可供設施選擇,每個位置所需建設費用為fi(i=1,2,…,m);客戶集為J={1,2,…,n},即有n個客戶需要服務,每個客戶的需求總量為di(i=1,2,…,n).由設施i∈I提供單位需求量給客戶j∈J時所需運輸費用為cij.每個設施所能提供的需求量不受限制,即無容量限制.求一建設設施方案(即在哪個位置建立設施?建立多少個設施?)使得總費用最小.下面給出這一問題的數學模型,本文采用文中所給的模型minΖ=m∑i=1fiyi+m∑i=1n∑j=1djcijxijs.t.m∑i=1xij=1?j=1,2,?,nxij≤yi?i=1,2,?,m；j=1,2,?,nxij,yi∈{0,1}?i=1,2,?,m；j=1,2,?,n(1)minZ=∑i=1mfiyi+∑i=1m∑j=1ndjcijxijs.t.∑i=1mxij=1?j=1,2,?,nxij≤yi?i=1,2,?,m；j=1,2,?,nxij,yi∈{0,1}?i=1,2,?,m；j=1,2,?,n(1)其中yi={1?在第i個位置建立設施0?否則xij={1?當第個i設施提供服務給第j個客戶0?否則在(1)中,總費用包括建設費用fi和服務費用cij,第一個約束條件說明每個客戶需求總量由一個設施即可滿足,第二個約束條件說明客戶只能從已經建立了設施的地方獲得需求.模型(1)在組合優化中有著廣泛應用.如城市消防站點的設置、計算機網絡設計、機床作業進度表問題等.目前,求解這一問題較好的算法有局部搜索算法和禁忌搜索算法.作者將利用粒子群算法求解此問題.下面給出無容量限制設施尋位問題的粒子群算法.2加速收斂及加速系數在PSO系統中,每個備選解被稱為一個“粒子”,多個粒子(種群)共存、合作尋優(近似鳥群覓食行為),每個粒子都對應有一個由適應函數(或目標函數)計算出的適應度值,粒子根據自身的適應度值在問題空間中向更好的位置“飛行”,搜索最優解.設搜索空間為D維,總粒子數為n,則每個粒子的信息可以用D維向量表示:第i個粒子的位置向量為Xi=(xi1,xi2,…,xiD)T,速度向量為Vi=(vi1,vi2,…,viD)T.另外,設第i個粒子目前所找到的最優位置為Pi=(pi1,pi2,…,piD)T,稱為個體最優位置.設整個種群目前找到的最優位置為G=(g1,g2,…,gD)T,稱為全局最優位置.則每個粒子的速度和位置按如下公式進行更新(“飛行”)vik(t+1)=w?vik(t)+c1r1[pik(t)-xik(t)]+c2r2[gk(t)-xik(t)](2)xik(t+1)=xik(t)+vik(t+1)(3)其中,vik(t)是粒子i在第t次迭代中第k維的速度;w是慣性權重,較大的w可加強PSO的全局搜索能力,而較小w的可加強局部搜索能力.試驗結果表明,w在[0.8,1.2]之間PSO有更快的收斂速度;c1,c2是加速系數,分別調節向全局最好粒子和個體最好粒子方向飛行的最大步長.若太小,則粒子可能偏離目標區域;若太大,則會導致粒子突然向目標區域“飛去”或飛離目標區域.合適的c1,c2可以加速收斂且不易陷入局部最優,通常令c1=c2=2;r1,r2是之間的隨機數;xik(t)是粒子i在第t次迭代中第k維的當前位置.粒子群初始位置和速度按下面公式隨機產生xik=xmin+(xmax-xmin)×r1,vik=vmin+(xmax-xmin)×r2(4)其中,xmin=-10,xmax=10,vmin=-4,vmin=4,然后按照公式(2)、(3)進行迭代.在應用PSO求解UFL問題時,關鍵在于如何構造設施位置的粒子表達式,下面利用粒子的位置向量來構造設施位置的粒子表達式:設所求UFL問題的規模為m.定義第i個粒子的位置向量為Xi=(xi1,xi2,…,xim)T,速度向量為Vi=(vi1,vi2,…,vim)T.設施位置的粒子表達式Yi=(y1,y2,…,ym)T的每個分量對應由位置向量分量的函數得到.函數關系如下yj=[|xij|mod2],j=1,2,?,m(5)由(5)式可知設施位置的粒子表達式為一個0-1列向量.故當yj=1時,可表示在第j個位置建設設施,否則,yj=0.記Zi=FT·Yi+c(T)為粒子i對應的適應函數,其中,F=(f1,f2,…,fm)T為設施的建設費用向量,c(T)為按照就近原則求得的總運輸費用.事實上,Zi是模型(1)中目標函數的向量表達式.粒子i的個體最優位置Pi=(pi1,pi2,…,pim)T由i對應的設施位置粒子表達式和適應度值決定,記粒子的個體最優適應度值為Zpbi.在粒子i的位置向量Xi和速度向量Vi按式(3)和式(2)進行更新時,其適應度值按下面規則進行迭代更新Ζpbi={Ζpbi(t+1)?若Ζpb1(t+1)≤Ζpb1(t)Ζpbi(t)?否則(6)迭代前,令Pi=Xi,Zpbi=Zi.迭代過程中,種群的全局最優位置G=(g1,g2,…,gm)T(所有個體最優位置中的最優)對應的全局最優適應度值記為Zgb=min{Zpbi},并按下面規則進行迭代更新Ζgb={Ζgb(t+1)?若Ζgb(t+1)≤Ζgb(t)Ζgb(t)?否則(7)當所有粒子的位置向量按式(3)得到一次更新后,相應地,每個粒子對應的設施位置向量和適應度值隨即得到.若此時的全局最優適應函數值沒有達到最小適應度誤差標準或迭代次數沒有達到最大迭代次數時,算法進入下一次迭代.由以上可得求解UFL問題的PSO算法可用偽代碼表示如下:隨機初始化粒子群中的每一個粒子(particle);For每個粒子(eachparticle)按式(5)計算出相應的設施位置粒子表達式;利用設施位置粒子表達式計算出適應度值;置粒子的初始位置向量和相應適應度值為個體最優位置Pi和個體最優適應度值Zpbi;選擇Pi和Zpbi中的最優為全局最優位置G和全局最優適應度值Zgb;EndDoFor每個粒子按(2)式更新粒子飛行速度Vi;按(3)式更新粒子位置Xi;按(5)式得出相應的設施位置粒子表達式Yi并計算出適應度值Zi;If粒子當前適應度值優于該粒子歷史最優適應度值Then更新歷史最優適應度值和位置(Pi)為該粒子當前適應度值和位置(Xi);If當前粒子群中全局最優適應度值優于群內歷史全局最優適應度值Then更新粒子群中歷史全局最優適應度值和位置(G)為當前群內全局最優適應度值和最優粒子得位置;EndWhile最大迭代次數沒有達到;3ufl問題的實現作者以運籌學實驗室中12個關于CFL問題的基準測試題為例來驗證本算法的性能(這里,不考慮每個設施的容量限制即可作為UFL的基準測試題).12個基準測試題的規模和最優解值如表1所示.用Matlab6.1編寫了UFL問題的粒子群算法程序.在P41.7G、256M、Win2000操作系統的計算機上運行.這里采用文對PSO參數的設置.粒子數:在每個基準測試題中,粒子數等于可供選擇的設施位置數;慣性權重w=0.73;加速系數c1=c2=2;迭代次數:100;在每個問題上,算法運行30次.運行結果如表2所示.平均相對誤差百分比為30∑Ι=1Fi-ΟΡΤΟΡΤ/30.式中,Fi表示求解同一基準測試題的OSP算法在第i(1≤i≤30)次運行時的求解結果.OPT表示基準測試題的最優解.4osp算法性能分析作者首次將OSP算法應用到求解UFL問題中,并且通過以上數值試驗說明了算法的可行性與有效性.