基于粒子群算法的无容量限制设施寻位问题研究

基于粒子群算法的无容量限制设施寻位问题研究

房屋检测问题是一种广泛使用的联合优化问题，主要包括以下三种类型：限制房屋检测、限制房屋检测和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问题中,并且通过以上数值试验说明了算法的可行性与有效性.