萤火虫算法的仿生优化研究

萤火虫算法的仿生优化研究

1pfsp优化方法置换流场设定问题是很多实际流场生产计划的简化模型。它可以简化约10%的生产系统、组装线和信息服务，可以简化为pfsp模型。尽管PFSP的工艺约束比较简单,但业已证明3台以上机器的PFSP即为NP难题,至今尚没有一个具有多项式计算复杂性的全局优化算法。求解PFSP的方法主要有精确算法、启发式算法和智能算法等。精确算法(如枚举法、分支定界法、动态规划等)可求得该问题的精确解,但由于是NP难题,只适用于小规模问题的求解。启发式算法(如Palmer法、CDS法、NEH法等)可以快速建立问题的解,但通常构造复杂且解的质量不高。智能算法尤其是基于物理或仿生学机理的一类元启发式算法(如模拟退火算法、蚁群算法、粒子群算法等)能够在可行时间内以较大概率获得问题的满意解,成为求解各种生产调度问题的常用算法。对PFSP的调度优化可有效利用企业制造资源,提高生产效益,因此,学术界和工程界一直致力于研究和开发高效的优化技术,希望能快速找到PFSP的最优解或满意解。萤火虫算法(FireflyAlgorithm,FA)是一种新兴的仿生智能算法,是通过模拟自然界中萤火虫发光的生物学特性发展而来的一种基于群体智能的优化技术,具有模型简单、可调参数少、宜于并行处理、收敛速度快等特点。从目前文献来看,萤火虫算法多用于函数优化领域,生产调度领域的应用尚未见于国内文献中。本文分析了萤火虫算法的优化机理,在此基础上应用该算法来求解置换流水车间调度问题,通过仿真实例验证了算法的正确性和有效性,并对其在组合优化领域的优化性能进行评估。2机器上的工工信度问题置换流水车间调度问题研究n个工件在m台机器上的流水加工过程,约定每个工件在各机器上加工顺序相同而且每台机器加工的各工件顺序也相同,要求每个工件在每台机器上只加工一次,每台机器在某一时刻只能加工一个工件,已知各工件在各机器上所需的加工时间和准备时间,求使某项生产指标最优的调度方案。若调度目标为最大完工时间,则此类问题可用n/m/prmu/Cmax来表示,其中:n代表工件数;m代表机器数;prmu表明所有工件经过每一台机器的加工顺序一致;Cmax表示这批工件的最大完工时间。上述情形的PFSP数学描述如下:令tij表示工件i在机器j上的加工时间(假设各工件的准备时间已包含在各自加工时间内),C(ji,k)表示工件ji在机器k上的完工时间,π表示所有工件的一个排序,Γ为所有排序的集合;假设各工件按照机器1到m的顺序进行加工,则n个工件在m台机器上的完工时间可以通过(1)至(5)式计算。其中式(5)即为最大完工时间,式(6)表示最小化最大完工时间所对应的调度方案。3萤火虫算法的优化机制3.1设计机构设计自然界中多数种类的萤火虫都会发出短促、有节奏的荧光,尽管发光的真实原因仍在探讨当中,但一般认为,萤火虫成虫发光的生物学意义是利用物种特有的闪光信号来定位并吸引异性,借此完成求偶、交配及繁殖的使命,少数萤火虫利用闪光信号进行捕食。萤火虫算法就是模拟自然界中萤火虫的发光行为构造出的随机优化算法,但在算法中舍弃了萤火虫发光的某些生物学意义,只利用其发光特性来根据其搜索区域寻找伙伴,并向邻域结构内位置较优的萤火虫移动,从而实现位置进化。萤火虫算法通过模拟萤火虫的群体行为从而实现优化。萤火虫发出荧光的亮度取决于自身所在位置,所处位置越好(即目标值越佳)亮度越高,从而拥有的吸引度越大,可以吸引视线范围内亮度比其弱的萤火虫向其移动,亮度和吸引度随着萤火虫之间的距离的增加而减小,体现出荧光在空间传播时逐渐衰减的特性。在萤火虫算法中,用求解问题的目标函数值代表个体所处位置的优劣,将搜索和优化过程模拟成萤火虫个体的吸引和移动过程,将个体的优胜劣汰过程类比为用较好可行解取代较差可行解的迭代过程,最终实现优化目的。3.2荧光特征参数萤火虫算法包含亮度和吸引度两个要素,亮度体现了萤火虫所处位置的优劣并决定其移动方向,吸引度决定了萤火虫移动的距离,通过亮度和吸引度的不断更新,从而实现目标优化。从数学角度对萤火虫算法的优化机理进行如下定义。定义1萤火虫的相对荧光亮度为其中I0表示萤火虫的最大荧光亮度,即自身(r=0处)荧光亮度,目标函数值越优自身亮度越高;γ表示光强吸收系数,用以模拟荧光在空间传播逐渐衰减的特性,可设为常数;rij为萤火虫i和j之间的空间距离。定义2萤火虫的吸引度为其中β0为最大吸引度,即光源处(r=0处)的吸引度,可设为大于0的常数;γ、rij意义同上。定义3萤火虫i被亮度更高的萤火虫j吸引并向j移动时的位置更新为其中xi、xj为萤火虫i和j所处的空间位置;α为步长因子,是上的常数;rand为上服从均匀分布的随机因子;式中α(rand-1/2)为随机扰动,作用是为了避免在位置更新过程中过早陷入局部最优。算法寻优过程是:萤火虫群体随机散布在解空间,每只萤火虫因为所处位置不同发出的荧光亮度也不同,通过比较(根据式(7)),亮度高的萤火虫吸引亮度低的萤火虫向其移动,移动距离主要取决于吸引度的大小(根据式(8)),根据式(9)来调整更新后的位置。这样,通过多次移动后,所有个体都将被吸引到亮度最高的萤火虫附近,从而实现寻优。4基于萤火虫算法的换水调整4.1随机键编码方式由于标准萤火虫算法中萤火虫个体的位置为连续值矢量,算法无法实现工件排序的更新,因此应用萤火虫算法求解PFSP需要构造从个体位置到工件排序的恰当映射,采用合理的编码方式来映射调度问题的解。针对PFSP的特点,本文采用基于升序排列(RankedOrderValue,ROV)规则的随机键编码方式,将萤火虫个体的连续位置矢量Xi=[xi,1,xi,2,…,xi,n]转换为机器上各工件的加工顺序π=(j1,j2,…,jn),从而计算个体所对应的调度解的目标值。这样,既能够保证获得的调度解的可行性,又无需修改萤火虫算法的进化操作。4.2局部搜索的对象研究表明,基于邻域结构的搜索对于改善算法搜索能力有着重要作用,对于PFSP而言,局部搜索的对象就是工件的排序。本文采用基于互换操作的局部搜索,在每一轮迭代结束后,对于找到的最佳调度解进行两两互换操作,即从第一个加工工件开始,两两交换工件加工顺序,如果目标值得到改善,就将原先最佳调度解替换,同时更新所对应的位置矢量。4.3计算验证的设置综上所述,求解置换流水车间调度问题的萤火虫算法流程如下。Step1初始化算法基本参数;设置萤火虫数目m,最大吸引度β0,光强吸收系数γ,步长因子α,最大搜索次数MaxT或搜索精度ε;Step2随机初始化萤火虫的位置,按照4.1节编码方式转换为加工顺序,计算萤火虫的目标函数值作为各自最大萤光亮度I0;Step3计算萤火虫的相对亮度I和吸引度β(根据式(7)、式(8)),根据相对亮度决定萤火虫的移动方向;Step4根据式(9)更新萤火虫的空间位置;Step5按照4.2节策略对最佳萤火虫个体所对应的调度解进行局部搜索;Step6根据更新后萤火虫的位置,重新计算萤火虫的亮度;Step7当达到最大搜索次数或满足搜索精度时转入Step8,否则,转Step3进行下一次搜索;Step8输出最优调度值和对应的调度解。5标准1:线性减少的惯性权重为验证萤火虫算法求解PFSP的性能,本文选择了广为应用的Car类基准测试问题进行仿真测试,并与采用相同局部搜索策略的粒子群算法、NEH启发式算法性能进行对比。仿真环境为处理器主频2.4GHZ,内存2GB,WindowsXP操作系统,MATLABR2010a编译软件。算法参数设置为,萤火虫算法中,萤火虫数m=40,光强吸收系数γ=1.0,最大吸引度β0=1.0,步长因子α=0.2;粒子群算法中,粒子数m=40;采用线性减少的惯性权重,Wmax=0.9,Wmin=0.4;学习因子为C1=C2=1.4962。最大搜索次数均为MaxT=300,每种算法独立运行20次,测试结果如表1所示。表1中FA代表萤火虫算法,PSO代表粒子群算法,NEH是构造启发式算法。为对比算法的性能,采用寻优成功率(SR)、最优相对误差(BRE)、平均相对误差(ARE)、最差相对误差(WRE)4项指标进行衡量,对于NEH算法,采用相对误差(RE)来衡量。计算公式为BRE=(min(Cmax)-C*)/C*×100%,ARE=(avg(Cmax)-C*)/C*×100%,WRE=(max(Cmax)-C*)/C*×100%,RE=(CmaxC*)/C*×100%。SR用20次测试中找到下界值的比率表示。Cmax表示算法所找到对应调度问题的最小化最大完工时间,C*表示对应问题下界值。从测试数据可以看出,对于所选Car类问题,萤火虫算法均能找到最优解,而且寻优成功率高于对应的PSO和NEH算法,反映出FA具有良好的全局收敛性能。从平均相对误差和最差相对误差数据来看,FA所求得调度解的质量远高于PSO和NEH算法,显示出FA在离散空间也具有良好的进化机制。另外可以看出,NEH作为构造启发式算法,所求得调度解质量一般,只适用于对精度要求不高的场合或用来构造初始解。测试结果反映出FA在组合优化领域具有优良的寻优性能,是解决PFSP的一种有效工