元启发式算法（共7篇）
元启发式算法 篇1
0 引 言
广义最小生成树问题广泛应用于远程通信、能源分布、农业灌溉等领域。给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边权的总和为最小,称为最小生成树问题(MST)。广义最小生成树问题(GMST)是最小生成树问题的推广,它是将这个无向图的顶点分为k个簇,在每个簇中找一个点作为这个簇的代表,共找到k个点,然后在这k个点组成的新的子图中,寻找它的最小生成树问题。GMST最先由Myung等[1]于1995年提出,并且证明它是NP-难的,而且给出了求解这个问题的分支定界法;Feremans等[2]对于GMST的8个整数规划模型进行了理论上的比较;Feremans等[3]提出了几类有效不等式以及分支切割法来解决GMST;Duin等[4]把GMST转化为斯坦纳树(Steiner Tree)问题,并利用一些专门的算法来解决。近年来,Pop等[5]提出了GMST的一种新的整数规划模型。
对于GMST,当规模比较大时,得到最优解比较困难,所以对于大规模GMST经常用元启发式算法进行解决。Feremans[6]首先提出用禁忌搜索算法来求解GMST;Pop[7]提出模拟退火算法来解决GMST;Hu等[8]提出了改进的变邻域搜索算法来解决GMST,并与其他的元启发式算法进行了比较;Golden等[9]提出了一种局部搜索算法和遗传算法来解GMST。最近,Wang等[10]提出了一种改进的禁忌搜索算法来解决GMST,并表示他的算法比文献[9]中的遗传算法有效。本文基于遗传算法和模拟退火算法的优点,提出了单亲遗传模拟退火算法,并且通过在2种邻域进行搜索改进禁忌搜索算法,并与文献[10]中给出的最优值比较,证明我们算法的有效性。
1 问题描述
考虑无向图G=(V,E),V={v1,v2,…,vn},将点集V中的顶点分为k个簇(即k个集合),分别为V1,V2,…,Vk(k≤n)。
E={{vi,vj}|vi∈Vp,vj∈Vq,p,q=1,…,k,且p≠q},为不同簇之间点的连接边集。C={cij},cij为边{vi,vj}的权。在每个簇中找一个点作为这个簇的代表,共找到k个点,然后在这k个点组成的新的子图中,寻找其最小生成树。最小生成树边权的和记为fm,则GMST就是要找满足fm最小的k个点。图1即为k=5,n=13的GMST。
2 算 法
针对广义最小生成树问题模型,本文设计了2种改进的元启发式算法:单亲遗传模拟退火算法和改进的禁忌搜索法。
2.1单亲遗传模拟退火算法
单亲遗传算法(partheno-genetic algorithm,PGA)是对传统遗传算法(GA)的一种改进算法,它取消了传统遗传算法的交叉算子,采取单亲繁殖方式。跟传统遗传算法相比,单亲遗传算法操作简单。而模拟退火(simulated annealing,SA)是一种强大的随机搜索算法,它不依赖于起始点,能在复杂的情况下产生高质量的解。己有研究证明,模拟退火算法在选择合适的退温函数后,能够以概率1收敛到最优解。所以综合了PGA和SA的优点,本文提出了单亲遗传模拟退火算法(PGASA),它的基本操作包括编码、初始种群的产生、个体的适应度评价、个体的选择、基因重组、模拟退火等。
2.1.1 初始种群的产生及编码
针对广义最小生成树问题的特点,本文用如下方式来构造个体,即S=[vi1,vi2,…,vik]。式中:vi1∈V1,vi2∈V2,…,vik∈Vk。初始种群中的个体随机产生,即S中的每一位vic都由Vc中的随机一个点产生,c=1,…,k,这样就能保证种群中的个体都是可行解。种群规模记为Ps。
2.1.2 评价个体适应度
本文直接以个体S的目标函数值作为它的适应度值,而个体S的目标函数值就是S中k个点组成的子图的最小生成树,通过Prim算法来求图的最小生成树。
2.1.3 自适应选择
在算法迭代的初始阶段:对于基因重组,考虑到重组操作会破坏优秀个体的结构,故不好的个体以较高的概率被选择进行重组操作,好的个体则以较低的概率进行重组操作;对于模拟退火,为了保证算法的全局收敛,每个个体都以较高的概率进行模拟退火操作。在算法迭代进行到一定阶段时:对于基因重组,考虑到算法会陷入局部最优,应该加大基因重组的作用,故不好的个体依旧以较高的概率进行重组,好的个体也以比较高的概率进行重组;对于模拟退火操作,为了提高算法效率,好的个体以较高的概率进行模拟退火操作,不好的个体则以较低的概率进行操作。于是本文设计了自适应选择法,针对个体的优劣情况,随着迭代的进行,根据一定的概率,自适应地选择个体进行操作,如下式:
式中:p1为接近于1的数;p2=exp((f-favg)/t)为关于t的递增函数,当然也与f的大小有关;p3=exp(t/(favg-f))为关于t的递减函数,本文t均指迭代数;f为个体的适应度;favg为当前种群中个体的平均适应度。这里对当前种群中的最优个体采取保存策略,即如果f=fmin,则该个体不进行重组,直接进行模拟退火;fmin为种群中个体的最小适应度。
2.1.4 基因重组
操作如下:从当前解S中随机选择2个点vi,vj从S中删除,再从vi,vj所在的簇Vi,Vj中随机选择2个不同的点加入S。
2.1.5 模拟退火
对基因重组后的个体S进行模拟退火操作如下:
1) 设定局部搜索步数。本文设定局部搜索步数与选择的簇有关,即局部搜索步数等于选择的簇中点的个数减1。
2) 邻域内局部搜索。在当前个体S的邻域中进行局部搜索,产生新个体S′。下面来解释如何进行局部搜索:对于S,随机选择一个点vl从S中删除,并将vl放入H中(H为加入过的点的集合),然后再从vl点所在的簇Vl中随机选择一个与H中不同的点加入S,这样就产生了一个新个体S′。
3) 判断新个体是否被接受。记Δf(S,S′)=f(S′)-f(S),如果Δf(S,S′)≤0,则令S=S′,否则产生一个(0,1)范围内的随机数r,如果exp(-Δf(S,S′)/T)>r,则令S=S′,T为当前的温度。这里为了实施最优保存策略,种群中的最优个体在进行局部搜索后,只有Δf(S,S′)≤0时,才令S=S′。
4) 初始温度的确定。如果初始温度设置过大,温度下降就会变慢,计算量也增加,影响算法效率。对于初始温度的选取,本文令T0=100。
5) 温度下降方式。T(t+1)=T0/(1+t)。
2.1.6 混合算法的操作步骤
综合以上各点,混合算法的操作步骤描述如下。
步骤1。初始化。采用实数编码,随机产生初始种群P,并评价个体的适应度,种群规模为Ps;计算初始温度T0,并令T=T0;令t=1。
步骤2。基因重组。对于种群P,利用式(1)选择算子①选出个体进行基因重组操作,生成新种群P′。
步骤3。模拟退火。对于种群P′,利用式(2)选择算子②选出个体进行模拟退火操作,生成新种群P″。对于要进行模拟退火操作的每一个个体,先令H=Ø,然后执行如下操作:
1) 对S进行局部搜索,随机选择S中的一个点vl,将其删除,并将vl加入H中。
2) 添加一个Vl中的不同点v′l,这样得到S′,然后再将v′l加入H中。如果Δf(S,S′)≤0,则令S=S′;否则产生一个(0,1)范围内的随机数r,如果满足exp(-Δf(S,S′)/T)>r,则令S=S′。
3) 如果H=Vl,跳到步骤4,否则返回步骤2继续局部搜索。
步骤4。种群更新。重新评价种群P″中个体的适应度,令P=P″。
步骤5。温度下降。令T=T0/(1+t),t=t+1。
步骤6。终止规则。产生一个(0,0.1)范围内的随机数rand,如果T<rand或连续迭代50次而最好解没有改进的时候,算法终止,输出当前种群中适应度最小的个体,即为近似最优解;否则返回步骤2继续迭代。
2.2改进的禁忌搜索算法
禁忌搜索(tabu search,TS)算法是局部邻域搜索算法的推广,该思想最早由Glover[11]提出,是一种全局逐步寻优算法。禁忌搜索算法是对人类智力过程的一种模拟,即人们对已搜索的地方不会立即去搜索,而去对其它地方进行搜索。所谓禁忌就是禁止重复前面的工作,它回避了局部邻域搜索陷入局部最优的主要不足,通过使用一个禁忌表来记录下已经达到过的局部最优点,在下一次搜索中,就利用禁忌表中的信息不再搜索或有选择地搜索这些点,以此来跳出局部最优,并通过特赦准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化。
目前,禁忌搜索算法在组合优化、生产调度、机器学习等领域得到了广泛且成功的应用,近年来又在函数全局优化方面得到较多的研究。在本文改进的禁忌搜索算法中,通过在当前迭代点的2种邻域进行搜索来避免陷入局部最优。下面来详细描述本文的改进禁忌搜索算法
2.2.1 初始解的构造
从每一个簇中随机选一个点,共选择k个点构成初始解。即S=[vi1,vi2,…,vik],其中vi1∈V1,vi2∈V2,…,vik∈Vk。
2.2.2 评价函数
直接以每个解的目标函数值作为它的评价函数值。对于每个解,用Prim算法来求最小生成树,得到的值f(S)即为这个解的评价函数值。
2.2.3 邻域搜索
用到2个邻域结构,即N1(S)和N2(S)。N1(S)为从S中随机选择一个点vp从S中删除,并从vp所在的簇Vp中选择一个不同的点v′p加入S中,这样的v′p共有|Vp|-1个。N2(S)为从S随机选择2个点vp和vq从S中删除,并从vp和vq所在的簇Vp和Vq中选择2个点v′p和v′q加入S中,且v′p≠vp,v′q≠vq,这样的v′p和v′q的组合共有(|Vp|-1)×(|Vq|-1)个。
2.2.4 禁忌表
禁忌表是禁忌搜索算法的一个重要特征,它主要由禁忌对象和禁忌长度组成.禁忌的对象是那些引起解变化的因素,禁忌长度为禁忌对象的受禁时间,在算法中以迭代长度来表示.禁忌对象的选取:我们对当前解S每进行一次邻域搜索时,都要在1个簇或者2个簇中进行局部搜索。那么在进行完这次邻域搜索后,就将这1个簇或2个簇放入禁忌表中。对于N1(S)的情况,禁忌表记为T1,对于N2(S)的情况,禁忌表记为T2。禁忌长度的确定:对于在禁忌表中的簇,我们在一定的迭代次数内不对这些簇进行局部搜索,这个迭代次数就称为禁忌长度。对于禁忌表T1,它的禁忌长度记为L1;对于T2,它的禁忌长度记为L2。
如果禁忌对象达到禁忌长度,则取消对它的禁忌。禁忌长度的确定非常重要,如果过长,则会造成过早陷入局部最优,并且占用机器内存,但如果过短,则会造成搜索的循环。
2.2.5 特赦规则
在禁忌搜索算法的迭代过程中,会出现某一禁忌对象被解禁后当前最优值将下降的情况。在这样的情况下,为了达到全局最优,会让一些禁忌对象重新可选。这种方法称为特赦,相应的规则称为特赦规则。本文算法的特赦规则为基于评价值的规则,即如果某个禁忌对象被解禁后,在该对象内进行局部搜索,能使得当前最小评价值降低,则将该禁忌对象从禁忌表中删除。
2.2.6 终止规则
本文给定一个最大迭代次数R,当算法达到最大迭代次数R或者连续迭代50次而最好解没有改进的时候,则算法终止。
2.2.7 算法步骤
步骤1。初始化。随机产生初始可行解S=[vi1,vi2,…,vik],并用Prim算法求其评价函数值,令t=1,T1=Ø,T2=Ø。
步骤2。N1(S)内局部搜索。从S中随机选择一个点vp。
1) 如果Vp∈T1,判断是否满足特赦规则,如果不满足,则跳到步骤3。
2) 否则将vp从S中删除,并从簇Vp中选择另外一个点v′p加入S中,得到新的解S′,求其评价函数值f(S′),判断如果f(S′)<f(S),则令S=S′;执行以上操作,直到满足Vp中的所有点均加入过S为止;令t=t+1,并将Vp加入禁忌表T1中;禁忌表长度为L1;如果禁忌对象达到禁忌长度,则取消对它的禁忌,将该禁忌对象从禁忌表中删除。
步骤3。从N1(S)跳到N2(S)。判断如果t>t1,则执行步骤4,否则跳到步骤6。
步骤4。N2(S)内局部搜索。从S随机选择2个点vp和vq从S中删除,并从vp和vq所在的簇Vp和Vq中选择2个点v′p和v′q加入S中,得到新的解S′,求其评价函数值f(S′),判断如果f(S′)<f(S),则令S=S′;执行以上操作,直到满足Vp×Vq中的所有两个点的组合均加入过S为止;令t=t+1,并将Vp,Vq加入禁忌表T2中;禁忌表长度为L2;如果禁忌对象达到禁忌长度,则取消对它的禁忌。
步骤5。从N2(S)跳到N1(S)。判断如果t>t2,则执行步骤6,否则跳到步骤4。
步骤6。终止规则。如果t>R或连续50次迭代当前最好解没有改进,则算法终止,输出当前最优解即为近似最优解;否则返回步骤2继续迭代。
3 数值实验
为了验证本文2种改进元启发式算法的有效性,将本文算法应用于新TSPLIB上的若干个实例,这些实例数据可以从http://neumann.hec.ca/chairedistributique/data/gmstp上下载。这些实例是通过对TSPLIB上的例子经过处理得到的,以便于适合本文的广义最小生成树问题。
下面介绍2种处理方法,这2种方法均由Fischetti等[12]于1997年提出。
1) 中心划分法(center clustering procedure)。
它先在n个点中找出互相之间尽可能远的k个点作为k个簇的中心点,然后在剩下的n-k个点中,把每一个点都被分配到离它最近的那个中心点,最后再就把n个点划分成了k个簇.这里k=round(n/5)。
2) 网格划分法(grid clustering procedure)。
这种方法一般适用于n个点的地理坐标(xi,yi),i=1,…,n都知道的情况,找出这n个点坐标中的xmin,ymin,xmax,ymax,那么由(xmin,ymin),(xmin,ymax),(xmax,ymin),(xmax,ymax)这4个点构成的矩形就可以把那n个点全包围起来.我们将这个矩形平均划分成g×g个网格,每个网格都满足高为(ymax-ymin)/g,宽为(xmax-xmin)/g,这里g为满足cluster(g)≥n/μ的最小整数,cluster(g)表示g×g个网格中的非空网格的个数.本文μ可取值为7,10,等等。
参数设置。单亲遗传模拟退火算法中:初始温度T0=100,种群规模Ps设为10,选择概率p1设为0.95。改进禁忌搜索算法中:中心划分法,禁忌表长度为L1=20,L2=30;网格划分法,禁忌表长度为L1=10,L2=15;迭代次数t1=80,t2=50,R=500。
表1为本文2种算法与Wang[10]中TS方法关于新TSPLIB上5个实例的数值实验结果。其中网格划分法为μ=10的情况第3列为最好值,最好值是指PGASA、TS、Wang[10]三者对同一个例子所得到的最好值(即3种方法求解同一实例所得函数值中的最小值)。由表1可见,PGASA每次都能得到最好值,TS算法的平均偏差是0.02%,Wang[10]的平均偏差是0.88%,显然本文的PGASA和TS比Wang[10]有效,且PGASA算法最有效。
4 结束语
本文提出了2种改进的元启发式算法来解决广义最小生成树问题,并且以新TSPLIB上的实例作为数据进行了数值实验,将本文提出的算法PGASA,TS与Wang[10]比较,实验结果表明本文提出的2种算法都比Wang[10]的有效,在解的质量方面,单亲遗传模拟退火算法表现要更好一些。
参考文献
[1]Myung Y S,Lee C H,Tcha D W.On the general-ized minimum spanning tree problem[J].Net-works,1995,26(4):231-241.
[2] Feremans C, Labbe M, Laporte G. A comparative analysis of several formulations for the generalized minimum spanning tree problem[J]. Networks, 2002,39(1):29-34.
[3]Feremans C,Labbe M,Laporte G.The generalizedminimum spanning tree problem:Polyhedral analy-sis and branch-and-cut algorithm[J].Networks,2004,43(2):71-86.
[4] Duin C W, Volgenant A, Voss S. Solving group Steiner problems as Steiner problems[J]. European Journal of Operational Research, 2004,154(1):323-329.
[5]Pop P C,Kern W,Still G.A new relaxation meth-od for the generalized minimum spanning tree prob-lem[J].European Journal of Operational Research,2006,170(3):900-908.
[6]Feremans C.Generalized spanning tree and exten-sions[D].Belgium:Universite′Libre de Bruxelles,2001.
[7] Pop P C. The generalized minimum spanning tree problem[D]. Netherlands: University of Twente, 2002.
[8]Hu B,Leitner M,Raidl G R.Computing general-ized minimum spanning trees with variable neigh-borhood search[C]∥Proceedings of the 18th Mini-Euro Conference on Variable Neighborhood Search,2005.
[9] Golden B L, Raghavan S, Stanojevic D. Heuristic search for the generalized minimum spanning tree problem[J]. Informs Journal on Computing, 2005(17):290-304.
[10]Wang Z,Che C H,Lim A.Tabu search for gener-alized minimum spanning tree problem[C]∥Ber-lin,Heidelberg,Yang Q,Webb G eds.PRICAI2006,LNAI,Vol.4099.Springer-Verlag,2006:918-922.
[11] Glover F. Future paths for integer programming and links to artificial intelligence[J]. Computers and Operations Reseach, 1986,13(5):533-549.
[12]Fischetti M,Salazar J,Gonzalez J,et al.A branch-and-cut algorithm for the symmetric generalized trave-ling salesman problem[J].Operations Research,1997,45(3):378-394.
启发式库存-路径问题求解算法 篇2
集成化物流管理ILM(integrated logistics management)是一种近年来才发展起来的新的物流战略管理模式,其主张将所有的物流活动整合在一起视为一个完整的系统,并在理想的客户服务水平下追求总成本最低[1]。
库存-路径问题IRP(inventory routing problem)是在如何联合优化配送和库存这两个往往被独立考虑的物流环节的现实需求推动下成为崭新的研究领域,是企业节能增效的重要途径。库存路径问题是对一系列已知需求量的客户,组织适当的行车线路进行服务,在不违反任何约束条件下,优化路线使得总成本达到最小。有效地解决该问题可以提高车辆的利用率,降低配送成本,提高配送时间的准确率,从而提高物流服务水平。由于库存路径问题是典型的NP难题,使用传统的优化方法很难得到问题的最优解或满意解,因此构造高质量的启发式算法成为研究该问题的主要发展方向[2]。
国外IRP研究最早出现在20世纪70年代。2000年以前的IRP文献主要研究单周期、一对多、单品种、确定需求情况,通常给定车辆数或不限,决策方式则集中在确定固定的配送频率,目标只考虑客户库存成本(一般不考虑中心库存成本)。求解时,采用“分区—路径” 分解问题或者沿用EOQ(Economic Order Quantity)思路占绝大多数,寻找合适的求解方法一直是研究热点、重点和难点。2000年以来,在继续构建高效率求解方法的同时,IRP本身的研究得到了深入,随机需求IRP、三层级IRP、取送结合IRP受到更多研究的重视[3]。
SPERANZA等运用实例证明了建立混合整数规划模型较建立纯整数规划模型的优越性[4]。
CHIEN等也讨论了单周期的IRP,他们所研究的配送系统包括一个有固定供应能力的中心仓库和多个有确定需求的客户,供方可以不满足部分客户的需求,但必须对未被满足的需求支付惩罚费用,建立了一个混合整数规划模型,采用基于拉格朗日松弛的求解过程来获得理想的上界[5]。
DROR等则研究了多周期IRP,侧重于如何将长时段(如每年)的多周期问题简化为短时段(如每天)的单周期问题。通过引入惩罚因子和激励因子来反映相邻周期决策的相互影响,并且建立了相应的混合整数规划模型[6]。
BLANCHINI等在建立随机动态规划模型时将单品种、多对多的物流系统看成是一个网络[7]。
国内IRP研究文献出现在2001年以后,但论文数不多,研究工作尚处于起步阶段。
奚飞等人通过综合考虑零售商订货周期与供应商订货周期之间的大小关系,最终寻求一种最优的IR策略,从而使整个供应链的成本最小[8]。
武秀焕等人将随机IRP描述为一个马尔可夫过程MDP(Markovian decision process),根据客户数量将问题分解成N个子问题进行MDP描述,接着对状态转移矩阵进行模拟,并对每一个MDP子问题进行求解,然后运用非线性背包问题的求解方法得到IRP的初始策略来构成直接配送路线,并在此基础上构造了一种基于搜索算法的启发式算法对初始策略进行优化,得到最终的优化解[9]。
沈飞等人将IRP问题分成两个子问题:一个能够使库存储存费用最小的线性规划和在基于模拟退火理论下生成并评估可选择性组合路线的分路线排除约束函数(the route perturbation routine)。一旦确定运货车的路线,混合整数规划(MIP)就转化为相对容易解决的线性规划,这样便能在给定的路线组合中寻找到解决库存问题的最优方案[10]。
目前国内对IRP的研究都是假设产品为单一品种。本文考虑多品种、多供应商对多客户的IRP问题,使用启发式算法选择最优的可选择的组合线路,逐步生成满意解。
1模型的建立
1.1模型假设
(1) 所有产品都能在1天内送到,即不考虑配送时间。
(2) 运输成本以整车为单位计算。通常运输成本包括:过路费、油费、人工工资、各种损耗。对于确定的运输线路和运输工具,则过路费、人工工资、其他损耗可以估算出来,油费与运输距离、货车自重、载货量成正比。
(3) 只考虑产品重量,忽略产品体积,是否易燃易爆等因素对运输费用的影响。
(4) 不考虑产品装卸费用和库存成本。
(5) 货车可以有多种类型,每种货车的自重、最大载货量、固定费用不同。
(6) 只考虑点对点运输,即货车到达目的地之后,必须将所有产品全部卸下。货车数量不受限制。
(7) 任意2节点之间存在直达线路。节点之间直达线路长度为最短,比经过任何节点中转都要短。
(8) 货车必须在当天返回出发点。即货车运输路线形成汉密尔顿圈。
1.2模型的建立
设有n个节点ai,m种产品Bj,节点之间直达距离为Dij,节点产品库存为Sij,节点产品需求为Eij。
设运输费用为:
其中,F为固定费用(与货车类型有关),d为运输距离,Z为货车自重,w为载货量,u为费用系数(需事先估计)。
每辆货车的运输路线形成汉密尔顿圈,设运输路线经过k个节点,则该运输线路可表示为:L(a1,a2,…,ak,a1)。
1.3目标函数
令恰好满足所有节点产品需求的货车运输路线集合为Q={L},相应的总运输费用为:
P=∑c(Li) Li∈Q (2)
则系统目标函数为求总运输费用最低的集合Q′,即:
P(Q′)=min{P(Q)} (3)
约定:
di,t=时间段t内配件i的需求量,i=1,2,…,m;
t=1,2,…,T;
K0=仓库和装配车间的距离;
K1=仓库和最近供应商间的距离;
K2=装配车间和供应商间的距离;
K=K0+1/2K1+1/2K2;
Ci,j=供应商i与j之间的行车距离,i和j=0,1,…,m+1;
hi=配件i的库存存储成本i=1,2,…,m;
Ii=配件i的初始库存量i=1,2,…,m;
C=货车的装运量;
L=线路的最大长度。
设:
qi,t=时间段t内在供应商i处的装运量;
si,t=时间段t内在配件i的库存水平。
于是有:
s.t
qi,t≥yi,t ∀i,∀t (5)
pi,t≤qi,t ∀i,∀t (6)
si,t+1=si,t+pi,t-di,t ∀i,∀t (10)
si,0=Ii ∀i∈{1,2,…,m} (11)
si,t≥0 ∀i,∀t (12)
yi,k,t,pi,k,t∈{0,1} ∀i,j∈{0,1,…,m+1},∀k,∀t (13)
因此,目标函数(4)包括的成本项目有访问供应商的成本之和,库存存储成本,出行设置成本。而约束条件式(5)至式(7)将变量yi,t与装运数量联系起来,约束函数(9)限定了每条线路都小于或等于最长线路L,约束条件式(10)为库存平衡等式,约束函数式(14)对一辆货车能够装运的载运量进行了限定。
2启发式求解算法
Q′为汉密尔顿运输路线集合,根据贪婪法则,总能找到当前单位运输成本最低的汉密尔顿运输路线,则有算法如下:
(1) 系统初始化。
(2) 根据需求计划及库存,找出所有可能的点对点运输线段。
(3) 找出使运输线段连接成汉密尔顿圈的所有组合。
(4) 对于p种货车,分别计算汉密尔顿运输线路及其成本。
(5) 找出运输成本最低的汉密尔顿运输线路,记录该线路。
(6) 根据该线路选择具体的运输方案,并在运输源节点的库存中减去已计划运输的产品,及在目标节点的需求中减去已计划运输的产品。
重复(2)—(6),直到没有任何可能的点对点运输线段。得到的配送方案集合即为最优运输方案。
3算例分析
为验证算法的可行性与有效性,编制程序验证本文所提出的模型与算法。
算例来源于模拟现实生活。基本数据为9个节点,9种货物,货车自重1500千克,最大载货量4000千克,固定费用200元,费用系数为4500,节点之间平均间距为153.3千米,每个节点存有多种产品,平均每个节点存有4.89种产品,节点平均库存量为4137.4千克。节点的产品需求数随机产生,多次运行算例结果如表1所示。
由表1可以看出:单位产品运输成本平均为0.06883元/千克,货车平均载货量为2416.99千克,平均货车运输效率为60.425%,空驶率平均为14.785%。而我国物流运输车辆的空驶率达37%[11]。
为验证算法的可行性与有效性,本文将应用所提出的模型与算法所得出的计算结果与其他启发式算法进行比较。
若利用集合覆盖型等式,由于该等式限制了路线的长度,能够最优解决的IRP 的最大容量是6 个供应商和7 个时间段。最优总成本是1354.70 元(存货成本=97.80 元,运输成本=1256.90 元)。
若利用本文所提出的启发式算法程序解决相同的问题,总的成本是1370.43元(存货成本=118.2 元,运输成本=1252.23元)。最优解和利用启发式解法得到的解的直接数值间隙是1.15%。同时即使供应商的数量大于100 和多个时间段的问题时也是有效的。因此本文提出的模型与算法不仅具有可行性而且在所求解问题的规模上具有先进性。
通过对比可知,本文提出的启发式多产品库存路径算法大大降低了货车的空驶率,有效地提高了货车运输效率,从而降低了运输成本。
4结语
(1) 本文重点介绍了库存路径问题的启发式算法研究,分析了关于库存路径问题的模型建立和解决过程。
(2) 探讨了以贪婪法为基础的启发式算法,采用的策略是每次选取平均运输成本最低的汉密尔顿运输路线。
(3) 模型仿真结果表明,本文提出的启发式多产品库存路径求解算法生成的物流运输方案高效,成本低廉,有广泛的应用前景。
参考文献
[1]Kenderdine D J,Larson P D.Quality and Lo-gistics:A Framework forStrategic Integration[J].International Journal of Physical DistributionandMaterials Management,1988,18(7):5-10.
[2]陈雪瑛.基于启发式算法的库存路径优化问题研究[D],北京交通大学,2008.
[3]傅成红,符卓.库存路径问题及其最新进展[J].计算机应用,2010(2):453-457.
[4]Speranza M G,Ukovich W.MinimizingTransportation and InventoryCosts for Several Products on A Single Link[J].Operations Re-search,1994,42(5):879-894.
[5]Chien W,Balakrishnan A,Wong R.An Integrated Inventory Alloca-tion and Vehicle Routing Problem[J].Transportation Science,1989,23(2):67-76.
[6]Dror M,Ball M.Inventory Routing:Reduction From an Annual to AShort-period Problem[J].Naval Research Logistics,1987,34(6):891-905.
[7]Blanchini F,Queyranne M,Rinaldi F,et al.A Feedback Strategy forPeriodic Network Flows[J].Networks,1996,27(1):25-34.
[8]奚飞,周永务.基于固定分割的库存路径问题最优策略[J].系统工程与电子技术,2009(10):2389-2993.
[9]武秀焕,李延晖.马氏过程的随机库存路径问题模型与算法[J].工业工程与管理,2009(1):66-70.
[10]沈飞,管小俊,于雅岑,等.基于模拟退火理论求解库存路径问题的模型与算法研究[J].物流技术,2009,(2):74-76.
动态拓扑网络最短路径启发式算法 篇3
关键词：最短路径,A*算法,二叉堆,动态拓扑
0 引 言
随着GPS(global position system)的应用领域越来越广,船舶、车辆等交通系统在利用知道自己位置的前提下进行通信显得方便易行。如果把每个实体看成是一个节点,实体间的可达通信看成是一条边,则两点间通信问题就转化为求解图的最短路径问题。
在求最短路径的方法中,目前国内外一致公认较好的算法是Dijkstra算法,然而Dijkstra采用遍历搜索,得到的是所有目标节点的最短路径,属一对多问题,不能有效解决两点间的点对点通信问题,为此,研究人员提出几十种不同的优化算法,效果较好的算法有TQQ (graph growth with two queues) ,DKA(the Dijkstra’s algorithm implemented with approximate buckets) ,DKD ( the Dijkstra’s algorithm implemented with double buckets)[1,2],可是这些算法都是针对静态网络拓扑结构的,不能有效解决动态网络的实时性要求高、规模庞大、移动节点的处理能力和系统的存储资源有限等问题。
而A*启发式[1]算法能适应网络的变拓扑特性,它采用路径规划思想,每次探寻到离目标节点更近的目标节点。选用恰当的启发函数便可使搜索范围限制在一个期望的区域,快速找到一个最优解。为此,本文提出ASPA(A* heuristic shortest path algorithm)算法,使搜索范围局限在一个椭圆曲线范围内。实验数据表明,该算法可以减少扩展的节点数目,节约计算时间,提高运算效率。
1 A*优化算法
1.1 A*算法简介
A*算法是目前广为流行的路径规划启发式算法[1],与Dijkstra算法不同之处在于它优先考虑最有希望的节点(具有最小估价函数的节点),使用了启发式信息来减少搜索空间,提高效率。定义节点的启发式估价函数为f(x) = g (x) + h(x),f (x)是假设是从起始节点S 出发,经过节点X到达目标节点T的最小代价值估计值。估价函数f (x) 由以下两部分所组成:一部分是从起始节点S 到达节点x的最小代价,记为g (x);另—部分是从节点x 到目标节点的最小代价,记为h(x)。实际过程中我们使用f (x) =LSX+dis(X,x)+ h(x),式中LSX是从原点S到当前节点X的实际最小费用,dis(X,x)是从当前节点X到扩展节点x的直线长度,h(x)是扩展节点x到目标节点T的路径长度,dis(X,x)+h(x)是启发式函数。
1.2 启发函数上限值
文献[3]利用最小角度求启发函数初始值,然而对于动态的网络拓扑结构,这种方法获得初始值是非常困难的。本文以船舶导航系统为例,设定启发函数的初值为2a,原理如下:如图1所示,节点S要和D通信,假设S知道t0时刻T的位置在(XT ,YT),其平均移动速度为v,则在t1时刻,节点T应该在以(XT ,YT)为圆心,以r=v(t1 -t0)为半径的圆内。这里设r=(2a-2c)/2=a-c,根据ITU-RM建议标准[4],速度最快的船舶通信报告周期为2s,那么上限值2a≈dis(X,T)+2r= dis(X,T)+4v,其中,dis(X,T)是X和T的直线距离;v是船舶的航行速度,即扩展节点的航行速度,取单个节点速度的平均值;加号“+”是考虑最坏时的情况,即v背离S的方向,这样从起点开始,每次扩展一个节点,每个扩展节点根据节点速度和离目标节点的距离来动态调整上限值,这样可以使搜索以限制在椭圆曲线范围内的方式不断逼近目标节点。该方法适用所有移动通信网络求启发函数初始值,具有一般性。
1.3 优化算法简要描述
有了启发函数的初始值,对每个向前搜索的扩展节点x如图1所示,判断以下二种情况:
1) dis(X,x)+h(x)≤2a,x点在椭圆曲线范围以内,如果x点是所有椭圆曲线范围节点中最小者,选定x加入到永久标记节点,LSx=LSX+LXx,当前节点扩展到x节点。剩余满足条件的所有节点,标记为临时标记节点,加入到二叉堆序列,反过来讲,二叉堆里面元素也都是临时标记节点。
2) dis(X,x)+h(x)>2a,丢弃x,说明目标不可达。由于节点的离开、故障、睡眠等原因,X没有可达邻居节点,这时向源节点S报告不可达信息,避免无效的通信探询开销。
2 ASPA算法实现
2.1 数据结构设计
(1) 网络结点数据结构 (Node_Inf)
NodeID:节点编号;Latitude:结点纬度;Longitude:结点经度;AdjacentNum:邻居节点个数;*AdjacentIndex:邻居节点索引指针。
(2) 邻居节点索引表(AdjacentIndex)
NodeID:索引节点;A rcID:索引弧段。
(3) 弧数据结构 (Arc_Inf)
A rcID:弧段编号;FirstNode:弧的起点编号;EndNode:弧的终点编号;ArcLength:弧的长度。
(4) 最短路径结点数据结构(ShortNode)
HeapID:此结点在堆中的编号;*PreNode:最短路径中此结点的前一结点;ShortestLen:源点到此结点的最短路径长度。
用这个特殊的网络数组来存储节点数据,数组类似于邻接矩阵的压缩存储方式,其内容则具有邻接多重表的特点,即一条边以两顶点表示。AdjacentIndex则相当于一个记录了顶点出度的索引表,通过它可以很容易地得到此顶点的出度和与它相连的第一条弧段在弧段数组中的位置,这样就可以在顶点已编号的情况下以最快速度搜索出与任意节点相连的边。建立Arc_Inf和AdjacentIndex两个表以及对Arc_Inf的排序其时间复杂度共为O(2n+lg(n))。
2.2 ASPA算法实现
堆排序(heap sort)的基本操作有:
· ModiyHeap (S):首先将集合S调整成完全二叉树,并设定其根结点具有最小关键字。
· InsertHeap (x,S):将元素x插入集合S,并调用ModiyHeap将其调整成完全二叉树。
· SelectHeap (S):选取具有最小关键字的元素,并调用ModiyHeap将其调整成完全二叉树。
算法的步骤如下:
1) Initialize 操作:首先搜索与源结点SourceNode 相邻的结点Adjacent [AdjacentNum],然后初始化Arc_Inf中所有邻结点的权值ArcLength[i],计算启发函数初始值2a。
2) Initialize源节点长度:计算dis(S,i)+ h(i),不大于2a转3),大于2a的转5)。
3) 选取最短距离结点操作:SelectHeap,使得ShortestLen[i]= min{dis(S,i)+ h(i), i∈Adjacent [AdjacentNum] },ShortestLen[i]加入ShortNode表,设置链接指针PreNode=Node ID[i]
4) 计算源点到当前节点最短长度:选取当前节点NodeID[i]的扩展邻节点NodeID[j],ShortestLen[j]= min{ dis(S,j)+dis(j,T)},dis(S,j)+dis(j,T)≤2a,j∈Adjacent[i]。计算ShortestLen[j]= ShortestLen[i]+dis(S,j)+dis(j,T),ShortestLen[j] 加入到ShortNode, 当前节点转移到j节点,PreNode=NodeID[j]。
5) 扩展节点约束:如果NodeID[j]邻节点dis(X,x)+h(x)>2a,则SelectHeap,从临时标记节点开始新一轮搜索,SelectHeap遍历完毕转7),否则转6)。
6) 重复步骤2),直至Node [j]=DesNode。
7) 结束。
3 算法仿真和分析
3.1 算法仿真
以网络仿真软件NS-2(Network Simulator)作为仿真平台。由源节点发出的探测包到达目的节点后返回,从返回的数据包可检测到到达目的节点的准确度及往返花费的时间,也可以分析数据包转发路径,得到临时标记节点的扩展数目。平面算法指的是类似GPRS等以平面图为基础拓扑的其它算法,表1统计数据表明,扩展节点数可以减少到改进前的54%,程序运行的时间大约为改进前的71 %。
3.2 算法复杂度分析
Dijkstra算法采用广度优先的搜索策略,在访问了网络中所有的节点后,最终生成从源点到其余各点的最短路径树。算法的运行时间为O(N2)。如果Dijkstra算法搜索范围可以看成是以X为圆心的圆的面积S=4πr2,r=dis(S,T),那么启发式椭圆曲线搜索范围可看成椭圆面积S =πab≈πr2/4,圆和椭圆面积之比大约4∶1, 即二者扩展节点数目相差4倍左右。从仿真实验扩展节点数目的减少量上来看,可以说明这一点。
4 结束语
本文在分析迪杰斯特拉(Dijkstra)演变算法的基础上,提出了基于椭圆曲线的启发式搜索算法,该算法适用于变拓扑结构的网络间求最短路径问题,具有一般性。从应用于船舶无线自组网络通信系统的实际情况看,该算法表现出良好的性能。关于速度与距离的配合及对椭圆参数的影响,有待今后进一步探索。
参考文献
[1]Soltani A R,Tawfik H,Goulermas J Y,FernandoT.Path planning inconstruction sites:performance evaluation of the Dijkstra,A*,andGA search algorithms[J].Advanced Engineering Informatics,2002,16(4):291-303.
[2]Fu L,Sun D,Rilett LR.Heuristic shortest path algorithms for transpor-tation applications[J].Computers&Operations Research,2006,11(33):3324-3343.
[3]汤晓,李贻斌,王彦堂,张娟.基于Mapinfo的最短路径混合搜索算法[J].山东理工大学学报:自然科学版,2006,20(3):81-84.
元启发式算法 篇4
在物流中心的各项活动中,分拣是最为重要的一项活动, 其成本约是整个中心运营成本的50% ~ 65%[1],分拣的效率不仅关系到整个运营的成本还直接影响到客户服务水平。而订单分批通过将多个订单合成一个批次或更大的订单以提升拣选设备的利用率并减少工作量,使得分拣过程得以更有效的实施。随着订单数目的增加,可行批次的数量以及决策变量的数量呈指数增长,许多基于最优化算法的研究都具有比较大的局限性,所以采用启发式算法解决订单分批问题得到了广泛的共识。早期的研究主要凭借以往的经验对订单分批过程进行优化。例如对客户订单按照某种事先确定好的优先级进行分批,先到先服务( First Come First Serve,FCFS) 准则是其中最常用的一种。Elsayed[2]在1981年提出种子算法的概念,该算法对每个批次选定一个种子订单,余下的订单将按照某种配对原则添加到批次中。Ho和Tseng[3,4]等对种子的选取规则以及订单配对原则的选取进行了深入的研究。李诗珍对种子算法以及节约算法进行了初步的探讨[5,6]。Elsayed和Unal[7]在节约算法的基础上提出了一种有效的算法用于求解订单分批问题,通过比较每两个客户订单合并后的路程节约量进行分批,从节约量最大的订单对开始,余下的订单对按照节约量非增的顺序被分配到下一批次中,每次分配订单的时候都重新计算节约量。
综上所述,订单分批问题的求解方法是国内外研究的重点,一些经典的启发式方法如先到先服务,种子算法,节约算法在实际中得到了广泛的应用,这些算法的特点是直观易行并且计算快速,常用来求得问题的初始解或作为检验新算法有效性的基准。本文提出一种降批次启发式方法,并与经典的算法进行比较。
2问题描述和模型建立
订单拣选可以说是物流中心最耗费时间的作业,根据以往的经验,减少拣选所花费的时间能够有效节约人力成本。 同时,拣选时间是交付提前期的重要组成部分,减少拣选作业时间能减少客户订货周期从而提升客户服务水平。
当客户订单到达,为了完成客户订单所指定的物品的拣选,拣货人员需要花费的时间也被称作订单处理时间,其中行走时间对整个订单处理时间的影响最大。假设拣货人员在拣货过程中采用匀速行走,减少行走时间可以等效为减少总的拣选路程。
订单分批是这样一个过程: 待拣选的物品被安排到每一次往返于仓库的行走过程中,每次往返拣选一方面受限于拣选设备的容量,另一方面也取决于订单所包含品项占用的空间大小。客户订单尽量被安排到一次拣选路程中直到拣选设备的容量被用尽为止,这些需要在一次往返路程中完成的订单为一个批次。许多文献中拣选设备容量有不同的意义,即可以指订单的数目也可以是物品的数目,本文指的是物品的数目。综上,订单分批问题可以描述如下:
对于给定的拣选设备容量以及路径策略,如何将客户订单以及所要求的有固定储位的待拣选物品分批在一次往返拣选中完成从而使得所行走的路程最短?
本文采用Gademann和van de Velde[8]提出的订单分批模型,该模型具有简洁直观的特点非常适合用来进行订单分批问题的探讨,该模型明确考虑到每个可行的批次,设订单集合O有n个订单需要拣取,每个订单中含有一定数量的物品,并设B为可行的批次集合,可以建立如下数学优化模型:
目标函数:
约束条件:
式中
O———客户订单的集合,O={1,2,…,n};
C———拣货车的容量;
B———所有可行批次的集合;
cj———第j个订单中所有品项的数量;
di———拣取第i批次订单中的所有物品所行走的总的路径值;
xi———二进制决策变量,如果第i个批次被选中则xi= 1, 否则xi= 0;
ai= { ai1,ai2,…,ain} 表示第i批订单的订单组成,aij= 1表示第j个订单在第i个批次中。
该模型要求每批次订单在一次往返拣选路径中完成,以使得所有批次总的拣选路程最短。约束条件( 2) 保证了每批订单所包含的品项数不超过拣货设备的容量,约束条件( 3) 和( 4) 则保证了每个订单必须且只能被分配一次。
3路径策略下的计算方法
上述优化模型的目标是最小化拣选路径,对于启发式算法的评估依赖于相应的路径策略,由于具体选择哪种路径策略并不会对评价分批结果的好坏产生影响,本文的算法采用S型路径策略。在实际应用中,S型路径策略是最为常见的,采用S型路径策略计算拣选路程不仅直观而且易于实现。本节讨论一种S型路径的计算方法,该方法灵活易于扩展,而且最为重要的是不影响我们对订单分批问题的讨论。一个典型的单区型无交叉走道的货架摆放如图1所示:
则捡货人员在拣选过程中通过的路程可近似计算如下:
其中:
LENGTH_OF_RACK:货架(走道)的长度;
WIDTH:货架的宽度;
CONER:拣货人员到达通道尽头的转角距离;
Nl:人员通过的走道数目;
Nc: 拣选设备转过拐角的数目;
Nw: 拣选设备通过货架两侧的次数即通过货架宽度的次数;
Last: 拣选设备通过的最远的通道数。
λ 的取值取决于需要穿过的通道的数目,当需要穿过的通道数目为奇数时,拣货人员需要多穿越一次。值得注意的是,当拣货员通过的最远通道数为一即只有第一个通道有货物需要拣选时,最好拣选方法是返回策略即拣完最后一个货物就返回,本文在此进行了简化,认为此时拣货员需要通过整个通道再返回,即:
D = LENGTH_OF_RACK + CORNER。图2表示当Nl = 2, last = 3时路程的计算情况,蓝色的方块表示拐角被计算一次, 红色的方块表示货架宽度被计算一次,粉色的区域表示走道被通过。
4启发式分批算法
4. 1根据优先级规则进行分批
通常拣货员在进行拣选作业之前会对订单进行简单的分类,比如按照时间顺序,品项数目多少的顺序等,然后对这些订单按照某种规则制定拣选的优先级,先到先服务( FCFS) 是最常用的一种基于优先规则的分批算法,FCFS按照订单到达的顺序对订单进行分批。
4. 2种子算法
种子算法自从1981年被Elsayed提出,种子含有“最初” 的意思,即种子订单是每个批次的初始订单。种子算法是一种连续生成订单批次的方法,因此,初始批次的选取对后面的分批有很大影响,种子算法进行分批主要有两个过程: 一是种子订单的选取; 二是根据订单的相似度进行配对。使用种子算法进行订单分批,首先对初始批次选择一个种子订单,然后按照配对原则从剩余订单中选出一些订单加入该批次,加入时要考虑拣选设备的容量,如果当前批次无法容纳更多的订单,则考虑一个新的批次直到所有订单都在某个批次内。
4. 3节约算法
种子算法忽略了与具体目标函数的联系,使得算法性能具有某种不确定性,节约算法通过计算每两个订单合并后路径的节约量来匹配订单,所有订单间的路径节约量被存放在一个被称为节约矩阵的矩阵里,其行和列均代表订单的编号, 索引为( i,j) 的元素表示第i个订单与第j个订单合并产生的节约量。节约算法的思想来自于Clark和Wright对车辆调度问题的研究,每次将订单安排进某个批次就对节约矩阵进行更新,使得批次中的订单与剩余订单重新计算节约量,这样剩余订单更可能选择那些能获得最大节约量的批次加入。
4. 4降批次启发式算法
本节根据订单分批问题的特点提出一种降批次算法用于求解分批问题。在分批问题中,订单的分批数量是影响优化结果的一个关键性的指标,分批数量越少则结果可能越好,每个批次在一次拣选路径中完成,则越少的批次意味着越少的拣选次数,拣选的总路程也相应更少。受拣选设备容量的限制,理论的最小批次数为订单集合的物品总数与拣选设备容量的比值,一般要在理想情况下才能取到这个值。降批次算法正是出于上述考虑提出的,该算法的过程如下所述: 首先将一系列订单进行排序,排序将订单按品项数从大到小排列。然后依次将订单放入每个批次中,第i个订单放入第i个批次,批次的数量等于订单的数量,然后依次对最高的批次进行降批即逐步减少批次数量,将高批次数中的订单放入任意低批次中并检查是否满足约束条件,如果不满足则将其作为一个独立的批次,重复上述过程直到无法再进行降批次操作算法停止。
降批次算法不同于前面几种方法,无论FCFS还是种子算法或是节约算法均是采用连续产生批次的方法,降批次算法采用一种逆向的思路,先将订单分成批次,然后对批次的内容进行调整,相当于每个订单都是一个种子,从而减少了选择种子的过程。
5启发式方法求解性能比较
考察上述启发式方法在不同订单集合下的优化性能,通过设置不同的订单数量测试算法的适应性,对FCFS算法、种子算法、节约算法和降批次算法进行了比较,其中种子算法选用最小通道数目的选择策略和随机的匹配策略,节约算法按照节约矩阵选择种子订单对,然后根据随机原则将为分配订单加入到已有批次中。表1显示了在订单数目分别为10、15、 20、25、30、35时各算法平均最小批次数量以及平均路径改善率的情况,这里每个订单品项数均随机产生且均匀分布在[10,30]区间上,拣选设备容量为40,仓储布局为传统的单区型仓库拥有6条纵向走道240个储位,采用S型路径策略和随机存储策略,表中的值为10次试验所取平均值。算法路径改善率随订单数目变化情况图4所示。由图4可看出在随机产生订单的情况下不同的算法得到的结果的优异程度,节约算法的路径改善率是四种算法中最大的,降批次算法则具有几种算法中最少的分批数量。种子算法则显得中规中矩, FCFS的结果最糟糕。然而并不能据此得出某个算法比另一个更好的结论。
表2显示了在同等条件下拣选设备容量为60时的情况。 算法路径改善率随订单数目变化情况如图3所示。
表中节约算法的批次数量最大,但是仍然获得了很好的路径改善率,可见批次数量少并非是路径改善率高的必要条件,种子算法在这种情形下的表现最好。当拣选设备容量为60而订单品项数均匀分布于[10,50]区间上,其结果如表3所示。算法路径改善率随订单数目变化情况如图4所示。
可见,算法的性能受拣选设备容量以及订单品项分布情况共同的影响,当品项数分布接近拣选设备容量上限时,节约算法和降批次算法具有更好的性能,当品项分布远小于容量的限制,FCFS和种子算法则较以往有更好的表现。综合来看,在两种情况下节约算法和降批次算法都提供了更好的分批结果,尤其是节约算法,这与以往的研究结果一致。降批次算法在一些拣选设备有限的情形则可能有更好的表现。
6结论
本文分析了订单分批问题及其求解思路,然后介绍了三种启发式分批算法,并在此基础上提出了一种旨在减少批次数量启发式算法—降批次算法,最后对上述四种算法进行了比较,发现在最小化路径模型的分批问题中节约算法和降批次算法具有比较好的性能。启发式方法还受到订单品项分布和拣选设备容量限制共同的影响,采用不同的启发式算法的性能具有差异性。
摘要：订单分拣是物流中心最为关键的环节,其成本占到整个物流中心成本的50%以上。文中通过制定合理的订单分批策略以改善人工拣选系统中拣选作业的工作效率,在以往研究的基础上提出了降批次启发式算法,算法考虑到拣选过程中批次数量对于结果的影响。并且利用matlab仿真软件进行仿真实验,与经典的启发式算法进行了比较,实验结果显示降批次算法有较经典的启发式算法更好的求解结果。
元启发式算法 篇5
关键词：Memetic算法,配电网重构,重要性
引言
配电网系统中包含着少量联络开关以及大量的开断开关。通过关闭联络开关,打开相对应的支路开断开关,使配电网系统在结构上发生变化。配电网重构就是科学地利用这种变化使得配电网在满足辐射状和各负荷点不失电的情况下,平衡负荷、降低网损、提高供电可靠性及改善电压质量。
配电网重构是一个大规模、非线性的优化问题,对于该问题的研究已经有了许多成果。主要有:数学优化算法、启发式算法、人工智能算法、混合式算法。其中数学优化法和人工智能算法求解过程耗费的时间较多,而且可能不收敛或者陷入局部最优的缺陷。启发式算法和混合式算法在求解速度上明显加快,寻求的解基本满足工程上要求,但不一定寻到最优解。文章引用了一种文化基因算法(memetic algorithm),利用改进编码方式编码的遗传算法进行全局寻优,同时利用启发式原则的局部寻优方法,大大提高了求解速度和求解质量,比传统的智能算法和启发式算法更加优越。IEEE33和IEEE69算例表明将Memetic算法应用到配电网经济性求解中,具有很好的寻优速率。
1 配电网重构的数学模型
配电网重构的目标函数有很多,文章仅考虑重构后使全网的有功功率损耗最小。数学表达式为:
式中:n为配电网总支路数,b为支路编号,rb为支路b的电阻值,Pb和Qb分别为支路b末节点注入的有功功率和无功功率,Ub为支路b注入功率节点的电压,Kb表示支路b的开断状态,当Kb=1时,支路b闭合,当Kb=0时,支路b断开。
配电网重构还需满足下列必要的约束条件:
(1)网络辐射状约束,重构完成后网络呈辐射状且各负荷节点不失电。
(2)电压约束:
(3)容量约束:
式中:Sb为支路b的功率,Sbmax为支路b传输功率的上限。
2 以支路交换为基础的局部寻优
文化基因算法对个体进行局部寻优,可以尽快淘汰掉适应值低的个体,从后使得寻优速率大大加快。但是局部寻优算法的效率和可靠性决定着文化基因算法求解速度和质量,因此高效的局部寻优算法直接影响文化基因算法的效率。传统的文化基因算法个体局部搜索一般采取模拟退火法,但是其应用于配电网时,若其领域选择较大则局部寻优所费的时间较长,整个算法的时间大量延长,若其领域选取较小,则容易寻不到局部最优,使算法陷入局部最优。现代智能电网要求进行实时在线的配电网重构,使得以更快的效率寻求最优解成为研究算法的核心要求。文章采用的以支路交换法为基础的局部寻优可以迅速找到局部最优解,同时在Memetic框架下可以最大化保留系统的多样性,找到全局最优。相对于传统的文化基因算法所采用模拟退火法进行局部寻优,文章利用以支路交换法为基础的局部寻优对整个算法性能提高巨大。
对于含有若干环的配电网系统,利用支路交换法可以快速定位合理的交换支路使系统网损大量减少,因此可以用该方法进行局部寻优,求解得到最优解的效率很高。
如图一个简单的配电网环路,在开关一侧的负荷向对侧转移,则两侧的网损增量分别为:
上述两式均把电压U觶i的标幺值视为1,节点注入功率可视为注入电流。两式之和就是转移该负荷给该环带来的增量,其值若为负值,则该负荷的转移对减少网损有利。
对于含有多个环的配电网,在其呈辐射状的情况下,对断开支路两侧的负荷转移产生的网损进行计算,寻求局部最优。具体做法为:选择一个断开支路,选择一侧的负荷向另一侧转移,计算网损增量并记录下来,接着计算另一侧负荷转移后产生的网损增量并记录下来。依次计算剩余断开支路处的负荷转移所产生的增量,对得到的所有增量进行大小顺序的排列,选择网损增量为负且最小的支路与该负荷转移形成的支路交换,然后在此基础上在进行两次这样的减少网损的操作,重复多次上述操作,系统的网损单调下降,因为个环之间会有相互的影响,为保证整个系统不陷入全局最优,文章对每个初始染色体用该方法局部寻优时,每次只进行两次这样的操作,这样既可以较大的趋于局部最优,又避免陷入局部最优解。
3 Memetic算法步骤
文章采用的是遗传算法进行全局寻优和运用启发式支路交换法局部寻优的文化基因算法。由上文的规则,染色体只编码支路类别不为0的支路。同时为了减少不可行出现的概率,采用有文献提出的编码方式,利用单点交叉和单点变异,并适当提高交叉率与变异率。初始种群的形成则是在配电网每个环内选择断开一个支路,然后将其改造为可行解。
该算法的流程图如图2所示。
文章算法的步骤:(1)读入系统数据,形成全为可行解的初始化种群。(2)对初始化种群中的个体运用文章的局部寻优方法进行局部寻优,得到在某领域拥有足够专业知识的精通者族群。(3)对得到的新的族群进行交叉和变异,并对不可行解进行改造。(4)重复2,3操作,直至达到最大迭代次数,输出最优解。
4 算例分析
文章以IEEE33节点和IEEE33节点配电网算例系统为例,该系统取基准容量为100k VA,基准电压为10k V。
文章采用改进的编码方式,支路1-2不参与编码,染色体长度为36,设置初始种群为20,最大进化代数为50,交叉概率为0.8,变异概率为0.05。利用文章方法对该33节点系统连续寻优发现,98%在35之内代就可以找到最优解,与文献[1]相比文章在速度上和求解质量上均有很大的优势。表1列出了文献[1]的方法与文章方法分别进行重构计算后的结果,显然文章得到的结果更优。
5 结束语
文章引进的Memetic算法的框架,用改进了编码方式的遗传算法进行全局寻优,特别是根据配电网的特点,以支路交换为基础的局部寻优作为个体寻优,使得算法无论在全局搜索能力和求解速度与质量方面相对于其余智能算法都有了极大的提高,在求解过程中,保持了遗传过程中父辈的优良基因,进一步提高了收敛速度。
参考文献
[1]李晓明,黄彦浩,尹项根.基于改良策略的配电网重构遗传算法[J].中国电机工程学报,2004,24(2):49-54.
[2]张栋,张刘春,傅正财.配电网络重构的快速支路交换算法[J].电网技术,2005,29(9):82-85.
[3]刘曼丹.文化基因算法在多约束背包问题中的应用[J].计算技术与自动化,2007,26(4):61-67.
[4]何禹清,彭建春,文明,等.配电网重构的最小可行分析对象及其快速算法[J].中国电机工程学报,2010,30(31):50-54.
[5]麻秀范,张粒子,孔令宇.基于家族优生学的配网重构[J].中国电机工程学报,2004,24(10):97-102.
[6]陈根军,李继洗,唐国庆.基于Tabu搜索的配电网络配电网重构算法[J].中国电机工程学报,2002,22(10):28-33.
[7]郝文波,于继来.基于负荷受电路径电气剖分信息的配电网重构算法[J].中国电机工程学报,2008,28(19):42-48.
[8]刘自发,葛少云,余贻鑫.一种混合只能算法在配电网重构中的应用[J].中国电机工程学报,2005,25(15):73-77.
[9]王艳松,陈国明,张加肚,等.基于小生境遗传算法的配电网开关优化配置[J].电工技术学报,2006,21(5):82-86.
[10]葛少云,刘自发,余贻鑫.基于改进禁忌搜索的配电网重构[J].电网技术,2004,28(23):22-26.
元启发式算法 篇6
齿轮类零件是机械加工中的主要零件,齿轮生产正逐步从大批量连续生产向多品种、小批量生产转型。一个制造型企业的竞争能力基本上取决于产品制造过程中的调度能力。从上个世纪末到现在,学者们在不断追寻调度问题解决方案的过程中发明了很多实用的算法,启发式算法就是为了解决复杂调度问题而发明的一种新思路和新方法,其中比较经典的算法如遗传算法、蚁群算法、粒子群优化算法等对求解车间调度问题起到了很大的推动作用。本文应用启发式算法理论对齿轮生产车间的调度问题进行研究。
1齿轮生产调度问题描述
设需要加工零件的数量为n,加工机床的数量为m,每个加工零件包含多道固定顺序的加工工序,每道工序可以在不同的机器上进行加工,在不同的机器上工序的加工时间也不同。调度的任务是安排最合适的机床完成每道工序的加工,计划每台机床上各工序的最佳加工顺序以及开工时间,使生产中需要达到的交货期、库存数量、生产延迟等性能指标达到最优。
2算法的求解步骤
齿轮生产车间寻找最小化制造期的调度Fm‖Cmax问题,可以看成是否能够得到使一个零件的加工工序贯穿整个系统的排列。实际上,需要加工的零件在队列中等待忙碌机器的时候越过另一项工作先进行加工是可能的,机器不一定要按照先到先加工的规则进行加工,这样在不同机器上各零件的加工顺序可能发生变化。改变相邻两台机器间各等待加工工作的加工顺序有时能得到更短的制造期。
对有m台机器的流水车间给出一个排列调度j1,j2,…,jn,在机器i上工作的jk完成时间为:
Ci,jk=max(Ci-1,jk,Ci,jk-1)+pi,jki=1,2,3,…,m;k=1,2,3,…,n。
其中:Ci-1,jk为在机器i-1上工作jk的完成时间;Ci,jk-1为在机器i上第k-1项工作的完成时间;pi,jk为工作jk在机器i上的加工时间。
给定排列调度下的制造期可由有向图的关键路径计算得到,给定序列的有向图构造如图1所示。
对每道在机器i上进行的工序jk,存在一个节点(i,jk),其权重等于jk在机器i上的加工时间。节点 (i,jk)有弧连接到节点(i+1,jk)和(i,jk-1),与机器m相关的节点只有一条弧,这和对应工作jn的节点相同。节点(m,jn)没有出弧(见图1)。从(1,j1)到(m,jn)的最大权重路径的总权重对应于排列调度j1,j2,…,jn的制造期。
3应用实例
结合理论研究,本文设计开发了齿轮生产车间的调度系统,下面以某齿轮加工车间的实际需求为背景,验证该系统的可用性和有效性。
齿轮生产车间的生产线类型属于流水线,其基本的工艺流程为:齿轮毛坯预处理→热处理→齿轮端面加工→齿形加工→热处理→表面处理。现有3个订单生产任务,3种齿轮的型号不一样。通过数据管理模块将新工件添加到系统中,如图2所示。该模块的主要工作是对工件信息进行管理,包括新建、修改和删除等。工件信息包含工件编号、工件名称、开始加工时间、交货期、数量、状态、优先级等。
在对调度问题建模完成后,点击“调度执行”按钮,操作者可根据自己的要求相应地进行参数设置,在确认各项参数后,点“确定”就可以进行调度计算。经验证,运行结果符合实际生产情况,可用来指导实际生产。
4结束语
启发式算法在调度问题中的应用可以很好地解决复杂的调度优化问题。随着研究的不断深入,调度模型和调度算法与生产实践的结合必定会更加紧密,调度系统必定向着集成化、动态化、高效化、实用化和智能化的方向发展。
参考文献
[1]何霆,刘飞,马玉林.车间生产调度问题研究[J].机械工程学报,2000,25(5):14-18.
[2]黄友锐.智能优化算法及其应用[M].北京:国防工业出版社,2008.
[3]孙志峻,朱剑英.具有柔性加工路径的作业车间智能优化调度[J].机械科学与技术,2001,20(6):931-935.
元启发式算法 篇7
关键词：BP神经网络,短时交通流量,CS算法
1 概述
随着城市人口不断增加,我国城市道路的建设进度难以跟上车辆数目的增长速度,从而使得交通拥堵问题日益严重,因此在现有道路条件下,如何对交通的进行高效的管理与调度以提升道路的通行能力,从而最大限度地缓解交通拥堵问题成为了一个十分重要的研究课题。而ITS(Intelligent Transport System,智能交通系统)[1]是目前最有效的解决办法之一。ITS把网络技术、信息技术、控制技术等先进的现代化技术运用到交通管理中,从而构建了一个覆盖全城的、全方位的、准确、实时、高效的智能系统。其中的交通流量预测是ITS的一项重要功能。这是因为ITS是根据未来的交通流量来制定相应的交通管理策略。因此,预测的准确性直接关系到交通管理测率的有效性。而短时交通流量预测为流量预测的重要组成部分。
经过多年的研究,人们在短时交通流量预测方面取得了丰硕的成果,提出许多的预测算法[2]。根据算法的理论依据,这些预测算法可以分成基于确定理论的预测算法与基于混沌理论的预测算法。常用的基于确定理论的预测算法有:Kalman滤波法、时间序列法、线性回归法等。这些算法都假设交通流量的变化是一个线性过程,但是在实际生活中,交通流量的变化是一个非线性时变的过程,因此这些基于确定理论的预测算法的预测准确度并不理想,其所得到的预测结果与实际情况相差会比较大,从而影响了交通管理策略的制定与调整。而常用的基于混沌理论的预测算法有:基于神经网络的预测法、基于遗传算法的预测法、基于向量机的预测法等。这些算法能够对非线性环境进行预测,从而能取得较高的预测精度。而该类算法的工作流程通常分为三个步骤:相空间的重构、预测算法的选择和参数优化、预测模型的生成。对训练序列进行相空间重构的目的是为了发掘训练序列背后所隐藏的内在规律。而预测算法是用来对从训练数据中提取预测模型,从而用于对未来进行预测。由于基于BP神经网络的短时交通流量预测算法能够实现自我学习并且具备预测可行度高等优点,因此本文选择该算法作为预测算法。但是,BP神经网络的阀值与初始连接权值直接影响该算法的预测可信度,如果参数设置不合理,该算法的收敛速度不仅会变慢而且所得到的预测模型也可能只是局部最优。针对这个问题,蚁群算法、遗传算法、退火算法等分别被用于BP神经网路的参数优化。但是,参数经过优化后的BPBP神经网络预测可行度还有有待提升。
而智能启发算法CS算法通过利用鸟类的飞行搜索原理,使得群体内的信息交流增多,从而实现了较快的收敛速度,这为参数优化问题提供了新的研究思路。在本文中,为了提高预测的可行度与精度,提出了基于CS(Cuckoo Search)算法与BP(Back Propagation)神经网络相结合的启发式算法(简称CS-BP算法)来进行短时交通流量的预测。
2 相关理论介绍
2.1 相空间重构
Packard等人在二十世纪九十年代第一次对相空间重构进行了定义[3]。而进行重构的目的是为了从某一非线性系统的实测的时间序列中发掘其在相空间中的几何特性,以便能够对更高维的相空间中吸引子进行重构。在本文中,短时交通流量的一维实测
2.2 基于BP神经网络的交通流量预测算法
其中,γ与vj分别为该层的阀值和从隐层到输出层的连接权值。
在基于BP神经网络[4]的预测算法中,连接权值与阀值是随机产生的,从而会造成收敛速度以及预测结果都不是很理想,因此,采用CS算法对连接权值与阀值进行优化,从而提升BP神经网络的收敛速度与预测可行度。
2.3 CS算法
为了解决CS算法收敛速度慢等缺点,利用高斯扰动来加快收敛速度,实现方法为:第t代中的第i个鸟巢的位置x(t)i进行绕到扰动,从而实现对x(t)i的更进一步的搜索。
从公式(6)可以看出,通过β与ε 的使用,使得鸟巢的位置变化更灵活,从而实现了算法的快速收敛。
3 基于启发式算法的短时交通流量预测的实现
上一节分别对本文所提算法用到的相关理论进行了介绍,本节将综合利用上述理论来实现本文所提算法。算法的实现步骤为:用m与τ对训练序列进行相空间重构,那么重构后的序列被用作神经网络的训练序列;1)首先通过对交通流量进行测量得到短时流量训练序列,然后分别用关联维算法与互信息法来确定维数m与时延τ ,最后利
3)首先x(0)b保持不变,而其它鸟巢的位置利用公式(5)进行变化,接着计算变化了的位置所对应的预测精度,然后把本次所得到的预测 精度与相 应的上代 预测精度 相比较 ,最后把精 度高的鸟 巢位置保 留下来 ,从而生成 了一组新 的鸟巢位 置
4)首先随机生成一组r ,接着把r与Pa进行比较,kt中的鸟巢位置被发现概率小的将被保留,其它的经随机地改变,从而得到一组新的 位置 ,然后计算 新位置所 对应的预 测精度 ,最后把精 度高的位 置保留下 来 ,从而成了 一组新的 鸟巢位置
6)首先跳出pt中预测精度最高的鸟巢xtb,接着判断该预测精度是否能够达到要求,如果达到,把xtb作为神经网络的参数设置,调到(7),否则的话,跳到(3);()
7)首先xtb所对应阀值与初始权值送入神经网络,然后神经网络开始用训练序列进行训练,从而得到预测模型,最后用预测模型进行预测。
4仿真分析
对某市的某一道路交通流量进行连续10天的观测,时间从8:00到12:00,每隔5分钟记录一次,总共得到480个观测值,组成的序列为X ={x1,x2,?,x480}。480个观测值中的前380个被用作训练序列用于生成预测模型,剩下的100个观测值被用于进行预测模型准确性的验证。图1给出所得到的测量值。
为了验证本文所提算法(简称CS-BP)的性能,将对基于PSO的BP神经网络的预测算法(简称PSO-BP)和基于GA的BP神经网络的预测算法(简称GA-BP)与CS-BP三者的预测误差进行分析。
GA-BP的参数为:变异与交叉概率分别为0.12,0.73,种群规则与最大进化次数分别为30和300。PSO-BP的参数为:
三种预测算法根据X的前380个数据来生成预测模型,并使用预测模型来预测后100个数据,图2给出了三种算法预测的结果。
从图5中可以看出,与GA-BP,PSO-BP相比,CS-BP的预测值与实测值相差最小,从而说明,CS-BP所产生的预测模型的可靠性。
5 小结