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

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

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