混合遗传模拟算法（共8篇）
混合遗传模拟算法 篇1
指派问题是物流活动中经常遇到的组合性优化问题,应用十分广泛,因此对其研究较多。在实际物流活动中指派问题通常有平衡与非平衡两种类型,即有n项任务,指派n个人员来分派完成称为平衡指派问题;有n项任务,指派m个人员来分派完成称为非平衡指派问题。近几年来模拟退火算法和遗传算法对指派问题在优化领域得到广泛深入的研究和应用,并得到很好的效果。在此基础上本文研究模拟退火遗传混合算法对指派问题的思路及求解。经实例计算该方法收敛较快,搜索效率较高。
1 指派问题数学模型
为方便研究将平衡与非平衡两种指派问题归纳为如下两种形式研究:
设有n项任务,要派m个人去完成,Cij表示第i个人完成第j项任务要付出的代价,tij表示第i个人完成第j项任务所需时间,则如何分派会使整体效益最好,即用时少费用低。
为建立模型引入0-1变量:
1.1 人数大于或等于工作项目时m≥≥n≥
1.2 人数小于工作项目时m<n
式中b———每人限制的最大工作量
2 指派问题的模拟退火遗传混合算法实现
2.1 模拟退火遗传混合算法思想
Step1:选定初始温度t=t0
利用模拟退火算法的温度控制方法选定较合适的初始温度。如果初始温度选择过高会导致计算时间较长,从而降低计算效率。如果初始温度选择过低又有可能使最终收敛得不到最优解。因此根据(14)式的条件来确定初始温度t0。
式中Δfij———任意两个相邻的温度差
Step2:确定初始群体initpop
首先,用实数编码方法对任务数n进行编码且不变;
其次,用实数编码方法对人数m进行编码且可以随机抽取;
最后,利用随机生成法对l!l=m-1个解中随机选取一个解为初始群体initpop。
Step3:构造适应函数f0=fitfun1,ft=fitfun1
Step4:利用遗传算法对初始群体initpop进行优化,产生种群seedpop1
(1)确定评价函数eval Vi
取一个小于1的实数α=0.9,fie是随着i的增大而不断减小的基于序的评价函数,则评价函数eva Vi是随i的增加(fie的减小)而缓慢减小的。
(2)利用评价函数可以确定进入种群的个体
当qi-1≤γ≤qi时(γ为(0～1)的伪随机数),第i个染色体进入种群,从而形成种群seedpop1。
Step5:利用模拟退火算法对种群seedpop1进行训练,产生更优的新种群seedpop2
(1)对seedpop1中1～m个体的适应值与初始群体中f0的值进行比较,满足条件的进入seedpop2;
(2)否则,根据评价函数来判断进入seedpop2的个体。当个体的适应值满足时,则选择进入seedpop2;
(3)经过优化训练,产生新种群seedpop2。
Step6:对新种群seedpop2进行交叉、变异,产生子代children
(1)对新种群seedpop2进行双亲双子法交叉,交叉率β,生成crosspop;
(2)再进行变异,交叉率ε,生成mutpop;
(3)生成子代children。
Step7:返回Step4,直到满足终止条件
Step8:得到最优解
3 算例演示
某大型生产企业为生产和人员安全每年都要定期对生产设备进行检修,检修分为平时检修和7月分大检修。现取其中一个车间来做算例,该车间只有3个维修工,平时每次平均会有2个地方出现故障,到7月大检修时该车间5个检修点都要停止运作重新进行检查和修理。已知工人维修故障所需时间Pij见表1,每个维修工的基本维修费用Cij见表2,注:在7月份大检修时天气比较炎热为保证维修工安全要求每个工人至多维修两个故障点。
单位:小时
单位:百元
混合算法相关参数选择α、初始时间t0=6、交叉率β=0.2、变异率=0.05。利用前面设计的混合算法进行运算得到结果及比较结果见表3,运行次数都为10次。按照该方案进行分配所得到的完成任务的花费时间大约要比单一使用模拟退火或遗传算法获得最优解短五分之二。
4 结论
本文结合模拟退火算法和遗传算法的优点,提出模拟退火遗传混合算法来解决实际中的指派问题。指派问题属于组合优化问题,很适合用本文研究的算法来实现。这种混合算法能够准确快速地求解最优结果或分配方案,针对较大规模的指派问题,能够缩短搜索时间,取得良好的效果。
参考文献
[1]贺国先.现代物流系统仿真[M].北京:中国铁道出版社,2008.
[2]焦永兰.管理运筹学[M].北京:中国铁道出版社,2000.
[3]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2005.
[4]谢凡荣.求解指派问题的一个算法[J].运筹与管理,2004(6):24-26.
[5]张新辉.任务数多于人数的指派问题[J].运筹与管理,1997(3):15-18.
[6]Cattrysse D G,Van Wassenhove L N.A survey of algoirths for the generalized assignment problem[J].Europena Joumla ofOperationla Research,1992,60(3):260-272.
[7]Marco Dorigo,Vittorio Maniezzo,Alberto Colomi.Ant system:Optimization by a colony of cooperating agents[J].IEEE Trans-actions on Cybernetics,1996(26):55-57.
混合遗传模拟算法 篇2
混合遗传算法及其在翼型气动[1*9/9]多目标优化设计中的应用
把基于实数编码的自适应遗传算法(SAGA)与可变容差法相结合,建立了数值优化设计中的混合遗传算法(HGA),并将其与翼型的气动分析相结合进行跨声速翼型的单目标和多目标气动优化设计.与自适应遗传算法相比,混合遗传算法的优化质量略有改善,优化效率有明显的`提高.优化结果表明混合遗传算法在翼型单目标和多目标气动优化设计中是十分有效的.
作 者：王晓鹏 作者单位：西北工业大学刊 名：空气动力学学报 ISTIC EI PKU英文刊名：ACTA AERODYNAMICA SINICA年，卷(期)：19(3)分类号：V211.1关键词：混合遗传算法 跨声速翼型 气动优化设计
混合遗传模拟算法 篇3
关键词：遗传算法,启发式算法,车间作业调度
1 引言
作业车间调度问题(Job—shop Secheduling Problem,JSP)是一类满足任务配置和顺序约束要求的资源分配问题,是最困难的组合优化问题之一[1],由于该问题计算复杂性过高,因此在工程实践中,大多采用启发式算法求其近优解.随着人工智能和计算机技术的发展,一些较复杂的优化方法得到了迅速发展,如神经网络、模拟退火和遗传算法等,并已成为调度理论的研究热点。
本文提出应用混合遗传算法即:在遗传算法中融入启发式算法的方法来解决生产调度的排序问题。遗传算法作为一种群体优化算法,通过选择、变异、交叉等操作,使解集性能不断得到进化,最终以较快的速度进行搜索,但其存在早熟和收敛性难以控制的问题。而传统的启发式算法结构简单,搜索速度快,但全局搜索能力差,容易陷入局部最优。因此把传统的启发式算法嵌入到遗传算法中构造一个能力更强的遗传算法对于解决复杂的优化问题是很有意义的。该算法将遗传计算的并行性、记忆功能和启发式算法的快速搜索能力相结合,提高了求解质量。
2 混合遗传算法
本文将传统的启发式算法和遗传算法结合起来,应用该混合遗传算法解决作业计划排序问题。针对遗传算法的早熟和收敛性的问题,加入启发式算法的一些规则,同时对遗传算法的一些关键参数(如交叉概率、变异概率)设置了自适应功能,使得算法在车间作业调度方面得到改进。
我们主要通过以下方式实现遗传算法的改进:
(1)把启发式嵌入到初始化中,产生一个适应性好的初始解群。按这种方式,混合式遗传算法能够优于启发式算法。
(2)将启发式嵌入到评估函数中,将染色体解码为作业调度。
(3)自适应设计个体的交叉率与变异率。
其中,遗传算法被用于个体中的全局搜索,而启发式算法在染色体中施行局部探寻。由于遗传算法和启发式算法的互补性能,混合遗传算法将优于两种单独的算法。
3 生产调度问题描述
所谓调度,就是为了实现某一目的而对共同使用的资源进行时间分配。本文所说的生产调度问题,是指用一组机床加工一组零件,如何安排每台机器上的工件加工顺序,使得某种指标(比如,总的加工时间、总的加工费用或者相对加工时间等)最优。
一般零件的加工过程由若干工序组成,且应满足一定的约束关系,车间作业调度约束条件的数目和内容会随作业需求和作业环境的不同而不同,如零件生产的工艺需求、设备条件等。
本文定义P={P1,P2,…,Pn}代表n个工件的集合,M={M1,M2,…,Mm}代表m台机床的集合,工件Pi的工序数目为Ki,工件Pi的加工工序为Pi1(Ji1),Pi2(Ji2),…,Pi Ki(Ji Ki)(Ki∈Z+,i=1,2,…,n),其中Z+表示正整数,Ji Ki表示工件Pi第Ki道工序在某台机床上加工,(Ji Ki∈M)。STi Ki表示工件Pi第Ki工序的加工起始时间,ETi Ki表示工件Pi第Ki工序的加工终止时间。用Ti Ki表示工件Pi第Ki工序的加工时间。
基于以上的定义,作业调度要满足以下几个约束:
1.每个工件包含一个由多道工序组成的工序集合,工件的工序顺序是预先给定的。
2.一台机床仅能同时加工一个工件的一道工序。
3.不同工件的工序之间没有先后的约束。相同工件工序满足先后约束关系。
4.工序Pi Ki(Ji Ki)与Pi Ki+1(Ji Ki+1)之间的时间间隔为零,即STi Ki+1-ETi Ki=0。
5.STi Ki≥0,即每个工件的每道工序的开工时间一定大于或等于零。
6.∑Ti Ki=Ti(Ti为工件Pi的总加工时间),即要求所有工件在交工期前加工完毕。
4 混合遗传算法求解作业调度
⑴.参数编码
应用遗传算法,必须将问题空间的参数转换成遗传空间的、由基因按一定结构组成的染色体或个体,这一转换操作就是编码。编码有基于工序的表达方法、基于工件的表达方法、基于位置“列表”的表达方法、基于机床的表达方法等。这里采用基于机床的表达方法。染色体编码为机床的序列,基于该机床序列,具体编码如下:
工件编号0 1,0 2,…n,每个工件的工序编号0 1,02,…k,机床编号01,02,…m。那么符号01.01.01表示工件01的01工序在设备01上完成。以3(工件)×3(机床)为例。假设工件中工序最多为4,机床对应不存在的加工工序则定义为00.00.00,工件工序加工必须满足工序先后关系的约束。则如表1所示,表示了工件、工序与机床的关系。
⑵.初始种群的生成和适应度函数的设计
初始种群的产生采取随机产生的方式,这样容易达到解空间所有状态的遍历。通过约束条件检验判断其是否为可行解,若是,将其加入初始种群;否则淘汰。但是初始群体的随机产生加大了进化的代数,大大增加遗传算法的计算时间,这里加入了启发式算法,运用启发式算法的局部搜索能力强的特性,加快优良个体的产生。
个体的适应函数应该是工件总的加工时间单调递减函数,即总工时越小,个体适应度函数值越大;总工时越大,个体适应度函数值越小。个体i的适应函数定义为:
式中Cmax为f(x)的最大值估计。初始种群的生成流程图如图1所示。
⑶.选择操作:采用了轮盘赌选择方法。若某个个体i,
其适应度为fi,则选择概率为:选择适应度最优的Pop Size个个体作为新一代种群。
⑷.交叉操作:交叉算子采用一点交叉运算,对参与交叉运算的两个个体母体M和父体F依据自适应交叉概率Pc进行交叉运算。记参与交叉运算的两个个体母体M和父体F,M与F经交叉运算后产生的子代个体记为D和S,染色体长度为L。随机地生成整数p,1
式中,fmax—群体中最大的适应度值;favg—每代群体的平均适应度值;f'—要交叉的两个个体中较大的适应度值。
自适应调整与算法的收敛程度成反向,从而有效地防止了算法收敛于局部最优,并使好的进化结果得以保存。
⑸.变异操作:变异操作采取互换变异,即先随机生成整数m,m取值范围为机器数量。在本机器上随机选择某一位,将此道工序与相临的工序互换。变异时要注意相临加工工序是否是同一工件的加工,如果是,变异后的染色体非法。自适应变异概率P?m定义如下:
式中,fmax—群体中最大的适应度值;favg—每代群体的平均适应度值;f—要变异个体的适应度值;
⑹.目标函数:本文将工件完工时间最小化作为目标,其目标函数为:
惩罚技术是用遗传算法解约束优化问题中最常用的技术[2]。本质上它是通过惩罚不可行解将约束问题转化为无约束问题。在遗传算法中,惩罚技术用来在每代的种群中保持部分不可行解,使遗传搜索可以从可行域和不可行域两边来达到最优解。
惩罚策略的主要问题是设计一个惩罚函数p(x),从而能有效地引导遗传搜索达到解空间的最好区域。对于本文研究的作业调度问题,根据上面的目标函数,相应的惩罚函数定义为所有工件的超期时间之和。设wai为工件i的超期时间段,则相应的惩罚函数表示则带有惩罚项的调度的目标函数表示为:
5 调度算法应用
为了检验的合理性,现采用文献[3]中的例2。该例由4台机器和8个工件组成,每个工件分别在4台机器上各加工一次,每个工件的加工路线与每道工序的加工时间按照文献[3]所示,如表2。
采用混合遗传算法进行作业计划排序,基本参数设置为:初始种群数=20,遗传代数=200代,经遗传算法重组运算后,作业计划的排序结果GANTT图如图2和3。由图中可见,最长加工路径为33,整个系统的设备空闲等待时间为2。
文献[3]中的例2的任务在文献[4]中用神经网络方法排序,最长加工路径为36;在文献[3]中采用基于效率函数方法经调度后,最长加工路径为33,但是设备的空闲等待时间为3。采用本文混合遗传算法经调度后,最长加工路径为33,设备的空闲等待时间为2。因此,根据例2的执行结果,采用本文研究的混合遗传算法进行作业计划排序,不仅所得的最长加工路径最短,而且设备利用率也是最高的。
6 结束语
车间调度问题已经证明为N P问题,难以找到能够求得最优解的确定性调度算法。又由于遗传算法的优良特性,因此,采用遗传算法对车间调度问题进行求解已成为求解该类问题的趋势。本文提出的基于混合遗传算法的调度算法,融入启发式规则,充分发挥遗传算法优势的同时,又加入启发式算法的快速搜索等优点,提高了分配效果。实例表明该算法能够取得较优的调度结果。
参考文献
[1]GERVEY M R,JOHSON D S,SOTHI R.The com-plexity of flowshop and jobshop scheduling[J].Mathematics and Operations Research1976(1):117-129.
[2][日]玄光男,程润伟著,汪定伟,康加福,黄敏译,遗传算法与工程设计[M].北京:科学出版社,2000.
[3]常会友,刘丕娥,张淑丽,王凤儒,基于效率函数求解的单件车间调度问题的算法[J].CIMS计算机集成制造系统.1998,(4):5-6
混合遗传模拟算法 篇4
目前,在云计算环境下基于遗传算法的资源调度问题已经进行了大量研究工作。文献[2]提出一种双适应度的遗传算法,通过两个适应度函数来选择种群,从而保证较短的总任务执行时间和任务平均执行时间。由于云计算的中心思想,是实现廉价高效的运算,对整个系统进行负载均衡研究是十分重要的。文献[3]通过自适应的变异概率,对任务响应时间和资源损耗代价同时进行优化。不但最短化任务执行时间,而且使虚拟机群的资源利用率最高。但未解决传统遗传算法局部搜索能力差以及早熟现象等问题。因此从改变染色体的编码方式出发,文献[4]采用组方式和三空间分割方法分别对染色体进行编码和译码,并根据不同染色体长度的变化设计交叉和变异遗传算子,算法对解空间内的多个区域同时搜索,具有群体和自我进化的优势,优化一次即可获得对不同目标的权值运算多次才能得到的最优解,提高了获得最优解的速度。文献[5]基于负载均衡度和最优跨度准则,改进了染色体编码方式,这种编码方式所形成的基因串的总数小于系统资源池内的总数,所以在计算过程中可以达到最优的资源调度,从而达到提高计算速度和计算准确度的目的。从初始化种群出发,文献[6]通过染色体匹配率将种群个体均匀分布在解空间上,有效地避免了早熟问题; 并通过对作业运行时间、费用、系统带宽以及服务质量的子适应度函数加权获得总适应度函数,并通过调节权值系数来满足不同用户需求。从混合遗传算法出发,文献[7]使用了多Agent与遗传算法相结合的混合遗传算法,通过个体之间的交互、协作和自学习,在解决负载均衡问题的同时具有更好的算法收敛性能。文献[8]提出了将贪婪和遗传算法相结合的混合遗传算法,对每个染色体都通过贪婪算法进行处理,达到内存使用量最小,同时能够在较短的时间内找到问题的优化解。但这种使得内存使用量最小的方法依然会出现局部最优解的可能。文献[9]同样采用了贪婪与遗传算法相结合的方式,这里贪婪算法只对无效染色体进行处理,将物理机使用数量引入总适应度函数,可降低局部最优解的出现。并分别从物理机使用数量、负载均衡度和迁移次数3 个方面进行加权组合,对资源利用率、能源节约和迁移代价多目标问题进行联合优化。但负载均衡度和迁移次数的适应度函数在不同染色体间的差异度不足,限制了算法的收敛速度; 同时只通过物理机数量来衡量内存使用量是不完善的。
针对文献[9]的不足,本文提出了以下两个改进方法: 一是对其适应度函数进行改进,从遗传算法染色体选择性出发,通过提高染色体间的优选概率,进而提升遗传算法的收敛速度; 二是提出了内存适应度函数,将其与物理机数量适应度函数相结合,增加相同物理机数量染色体间内存使用量的差异度,进一步提高内存使用率的同时,也提高了选择算子中的择优性能。仿真结果表明,该方法能够有效提高遗传算法的收敛速度。
1 总体架构调度系统模型
任务上传到云端的数据中心,数据中心的调度器响应该任务,将其随机分配给物理机PM,并在PM上建立相应的虚拟机VM来执行该任务。由于应用程序信息的不确定性以及PM处理能力的差异性,导致了PM负载不均衡,因此需要实施高效的调度策略,通过迁移VM技术来协调不同PM上的负载,提高资源利用率,同时也降低系统能耗。调度系统模型示意图,如图1 所示［10］。
通过云端的检测模块,检测初始负载信息和VM的配置信息。然后执行调度策略,得到新的配置方案。将其与原配置方案进行比较,是否提高资源利用率。具体通过以下指标进行判断: PM的使用数量和使用的PM负载均衡度。由于通过迁移VM技术来执行调度策略的结果,所以还需要考虑VM迁移成本。若迁移成本太高,则不执行调度算法; 反之执行调度算法。
2 混合遗传算法
为了解决云端资源优化问题,可采用基于多维混合遗传算法的资源调度策略［9］。算法考虑了3 个评价指标,包括PM使用数量、负载差异度和VM迁移次数。并将其进行加权组合,实现了权值可调的多目标优化。
2. 1 混合遗传算法
混合遗传算法执行过程如图2 所示。
1) 选取种群数目P,种群中的个体称为染色体。每个染色体代表着一种VM配置方案,即将所有VM分配在哪些PM上。
2) 计算种群中每个个体的适应度函数值。
3) 选择: 通过适应度函数值得到累积概率,进行染色体的选择。
4) 交叉: 采用单点交叉法,即随机设置一个交叉点,在该点相互交换部分染色体。
5) 修正无效因子: 由于每个PM内存是有限的,这样经过交叉后的染色体,可能会产生无效因子,此时通过贪婪算法对无效因子进行修正。
6) 变异: 依据变异概率将染色体中的某个基因值用其他值替换,从而形成一个新的个体。
7) 修正无效因子: 同步骤5) 。
8) 是否达到最大进化代数,如果已是最大代数,则产生最优个体,算法结束。反之,则返回到步骤2) 。
注意,为了确保当前种群中最好的个体不被交叉或变异操作破坏,将其直接保留至下一代,覆盖下一代种群中最差的个体。
2. 2 适应度函数
适应度函数由3 种子适应度函数组合而成,表示染色体被选择的概率。适应度函数值越高,染色体被选中的概率越大,反之,则被选中的概率越小。3 种子适应度函数代表着3种评价指标,分别是对物理机使用数量、负载差异度和VM迁移次数的评价。下面进行具体描述。
1) 子适应度函数Ei1
物理机数量的评价函数Ei1为
式中: pm表示云端的物理机数量; counti表示第i条染色体占用的物理机数量; p表示种群中含有的染色体数量。
2) 子适应度函数Ei2
云端负载主要是3 种负载: CPU负载、网络吞吐量和I/O负载。假设第k个PM含有n个VM,3 种负载分别用a,b,c表示。这样n个VM的3 种负载的大小是: [ak1,ak2,…,akn],[bk1,bk2,…,bkn]和[ck1,ck2,…,ckn]。为了方便处理,将3 种负载的值都归一化,即值的范围在[0,1]之间。每种负载的平均值分别为:。
则第k个物理机的负载差异度为
则第i个染色体负载差异度为
因此,负载差异度的评价函数Ei2可表示为
式中: Si表示第i条染色体的负载差异度; ∑S表示种群中所有染色体的负载差异度之和,即。
3) 子适应度函数Ei3
迁移次数的评价函数Ei3可表示为
式中: Mi表示第i条染色体需要迁移VM的次数; ∑M表示所有染色体需要迁移VM的总次数,即。
4) 子适应度函数Ei
Ei为总适应度函数,其将3 个子适应度函数进行加权求和
式中: x,y和z分别为Ei1,Ei2和Ei3的权重系数,且x + y + z =1。通过改变这3 个系数的值来调节评价指标所占的权重。
2. 3 评价函数的差异度
以负载差异度的评价函数式( 4 ) 为例,,其分母是对适应度函数进行归一化,而分子决定了不同染色体间的差异度。假设两个染色体的评价函数值分别为E12和E22,其比值为,若比值接近1 说明两个染色体的评价函数值差异度小,反之差异度大。从上式可以看出,差异度受到∑S的影响。因此随着p的增大,的值将会接近1,即两个染色体的评价函数值的差异度将会缩小。而评价函数值差异度的缩小,会导致染色体在选择时的择优性能下降,影响到算法的收敛速度。
3 改进的评价函数
3. 1 改进的适应度函数
1) 子适应度函数E'i2
因此,将子适应度函数Ei2中的评价指标总量用其最大值进行替换,即式( 4) 中的∑S改为Si的最大值,得到改进后负载均衡度的适应度函数E'i2,可表示为
其中,Smax表示种群中最大的负载差异度。
可将E'i2和Ei2的选择概率简化为
式中:为染色体协方差的归一化值;为所有染色体的归一化协方差和。由于中至少有一个 Smax项，且ni≤1,故1≤N < p。
从式( 8) 和式( 9) 可以看出,E'i2和Ei2均是负斜率的一次函数,其斜率分别为
由于N≥1,所以,即︱k'i2︱≥︱ ki2︱。这表明当ni取值区间为[0,1]时,E'i2的函数值范围将大于Ei2的范围。因此不同染色体的负载差异度对应的选择概率将比原有的选择概率更加稀疏,这意味着改进后的评价函数增加了不同染色体间优劣的区分度。
当负载差异度取最小值,即Si= 0,此时ni= 0,Ei1和E'i1都取得最大值且分别为
当负载差异度取最大值,即Si= Smax,此时ni= 1,Ei1和E'i1都取得最小值且分别为
由于N≥1,,所以E'i2max≥Ei2max。且仅当种群的染色体个数为1,负载差异度为Smax时,等号才成立。同理可得E'i2min≤Ei2min。则E'i2和Ei2随ni的变化如图3所示。
从图3 可以看出,当ni取较大值时,E'i2≤Ei2,这意味着差异度大的染色体以E'i2作为评价函数时,该染色体被选中的概率小于以Ei2作为评价函数时该染色体被选中的概率; 同理,当ni取较小值时,E'i2≥Ei2,这意味着差异度小的染色体以E'i2作为评价函数时,被选中的概率大于以Ei2作为评价函数时的概率。所以改进后的适应度函数提高了好的染色体被选择的概率,降低了差的染色体被选择的概率,即增加了不同负载差异度染色体的选择概率的区分度,从而提高了遗传算法的收敛速度。
2) 子适应度函数E'i3
与E'i2原理相同,由于虚拟机最大迁移次数为虚拟机的总个数。因此可将Ei3改为E'i3
式中: Mi表示第i条染色体需要迁移虚拟机的次数; vm表示总虚拟机的个数。
而对于物理机数量的评价函数Ei1,其使用物理机数量的最大值即为物理机的总数量pm,因此不需要进行改动。
3. 2 内存适应度函数
PM内存利用率对衡量资源利用率是一个很重要的指标。虽然贪婪算法是以内存最小化为目标修正无效因子,但是在选择最优染色体的时候,评价函数并不会因此选择内存空闲率低的染色体。图4 所示为更新迭代150 次后,物理机数量达到最小染色体的内存使用量。从图中可以看出,具有物理机数量最小的染色体方案不止一种,但每种方案物理机的内存空闲量是不同的,这表明评价函数不仅要考虑物理机数量,同时也应该考虑到内存使用量。所以需要选取恰当的物理机以便满足虚拟机的需求,同时还不浪费物理机的内存资源。
1) 内存利用率评价指标
式( 17) 为物理机内存利用率评价函数。其中,sum_ pm表示云端所有物理机的内存和; Ri表示第i个染色体的闲置内存量,闲置内存量为染色体中所使用PM的总容量与所有虚拟机的内存容量之差。
2) 适应度函数E'i
总的适应度函数需要综合所有子适应度函数,原有的方法是将子适应度函数进行加权求和得到总的适应度函数Ei。但在一些情况下,这样直接进行加权求和存在一定的问题,如物理机数量越小内存空闲率就会越小,这样内存空闲率与物理机数量具有一定的相关度,如果直接进行加权,会使得总的适应度函数值偏向物理机数量和内存空闲率这两个评价指标,会造成对其他评价指标的不公平性。
将Ei1与Ei4的和平均得到E'i1
从式( 18) 可以看出,相同物理机数量的Ei1具有相同的值,Ei4的引入将增加具有相同Ei1染色体的区分度。这样有利于增加物理机数量的择优性,从而提高算法的收敛性。并且在选择染色体时,E'i1不仅兼顾了内存空闲率,同时还不会影响到其他不相关的评价指标在总评价函数中的权重,保证了评价指标之间的公平性。总的评价函数如下
式中: x,y和z分别是E'i1,E'i2和E'i3的权重系数,且x + y + z =1。可通过改变这3 个系数的值来调节评价指标所占的比重,满足不同的优化需求。
4 仿真结果及分析
4. 1 遗传算法收敛性
仿真参数如表1 所示。
为了更好地分析物理机负载均衡度和虚拟机迁移度的收敛性能,分别取负载均衡加权系数为0. 9 和迁移度加权系数为0. 9,对原始算法与改进算法的收敛曲线进行对比,如图5、图6 所示。物理机数量变化率为最优方案与原始方案的物理机数量之比; 负载均衡变化率为最优方案与原始方案的协方差之比; 迁移次数变化率为最优方案的迁移次数与总的VM数量之比。
从图5、图6 可以看出,随着遗传迭代次数的增加,负载均衡变化率和迁移次数变化率逐渐降低。但改进后的负载均衡度和迁移次数变化率曲线整体要低于原始的收敛性曲线,说明在相同的遗传迭代次数下,改进后的遗传算法的收敛速度比原始方法的收敛速度快,这与理论分析一致。
图7、图8 所示迭代150 次后,负载均衡度和迁移度随权值变化曲线。
从图7 中可以看出,随着负载加权系数y的逐步增大,负载均衡度在Ei中的比重就会增大,所以负载均衡变化率会逐步降低。同时,从图8 可以看出,随着迁移度权重z的增大,迁移次数变化率也逐步降低。但是经过改进后得到的负载均衡度曲线和迁移次数变化率曲线整体均低于改进前的负载均衡度和迁移次数变化率曲线。这表明改进后的方法在不同的加权系数下均具有更好的收敛速度。
4. 2 内存使用率的收敛性
图9、图10 所示为E'i的加权系数x = 0. 9 时,内存空闲率与物理机使用率的收敛性对比图。其中,实线表示添加了内存使用量评价函数的内存收敛曲线; 虚线表示原始未添加时的内存使用量收敛曲线。内存空闲率为当前最优方案中物理机的空闲内存与物理机总内存之比。
从图9、图10 中可以看出,对E'i添加了内存使用量的评价函数后,其内存空闲率曲线和物理机数量曲线整体低于未添加内存使用量的收敛曲线。这表明添加了内存使用量评价函数,有利于提高内存空闲率和物理机数量的收敛性能。
图11 所示为各指标随E'i1的权值变化曲线。其中内存空闲率与物理机数量变化率曲线均低于改进前,同时迁移次数和负载均衡度曲线在改进前后基本保持不变。这表明在不同加权系数下,内存使用量评价指标的引入,有利于提高内存空闲率与物理机数量变化率的收敛性。同时,这种引入新评价函数的方法,并不会对负载均衡度曲线和迁移次数变化率产生影响。
5 小结
本文基于混合遗传算法在云计算资源调度中的应用,对其收敛性能进行了分析,并通过改进其评价函数,增加了适应度函数值在不同染色体间的差异度,提高了染色体的择优性。同时提出了内存使用率的评价函数,通过将物理机数量与内存使用量适应度值相结合,提升了内存的优化效率。最后通过仿真对比,表明算法的收敛速度得到了有效的提高。
摘要：在云计算中,系统规模和虚拟机迁移数量都是十分庞大的,需要高效的调度策略对其进行优化。将云计算的任务分配抽象为背包求解问题,可通过遗传算法进行求解。传统的遗传算法具有局部搜索能力差以及早熟现象的缺点,采用遗传和贪婪相结合的混合遗传算法。针对混合遗传算法在资源利用率与能源消耗的收敛速度较慢问题,通过改进适应度函数,改变了适应度函数在不同染色体间的差异度,从而提高了染色体在选择算子中的择优性能。仿真结果表明,该方法能够有效提高混合遗传算法在云计算资源优化中的收敛速度。
基于混合遗传算法的车间调度研究 篇5
生产车间调度是离散制造系统中关键的一个环节,车间调度通过合理分配现有的资源、安排零件加工次序和加工时间,能够有效的提高生产效率,对车间调度进行研究具有深远的意义[1,2]。生产车间调度问题种类繁多,本研究主要针对单件作业车间调度问题 ( job shop problem,JSP) 。在用遗传算法求解JSP问题时,初期种群之间差异非常大,很容易造成整个种群过早收敛,算法后期种群趋于一致,个体之间优势不明显,导致种群进化停滞不前[3,4,5]。为了使调度方案更实用高效,遗传算法得到不断改进和发展。Parviz Fatah[6]在求解过程中建立一个数学性规划模型,用启发式遗传算法结合模拟退火算法求解; 张超勇[7]设计了一个种基于工序和机器编码的改进遗传算法,具有更好的遗传特性; 王万良等[8]提出了改进自适应遗传算法,改进自适应遗传算法提高了获得最优解的速度; Victor等[9]改进了混合遗传算法的交叉操作,并将改进的算法应用与车间调度问题中。
本研究针对遗传算法搜索效率低,易于过早收敛等缺点,提出一种新的混合遗传算法。这种算法核心在于: 在每一代遗传进化过程中,引入退火思想,在迭代初期退火算法具有很高温度,此时算法有很强的概率突跳性,有利于打破过早收敛问题; 引入自适应交叉和变异概率,能使算法在优化过程中自动改变交叉和变异概率,避免盲目交叉,从而提高搜索效率; 设计新型的交叉和变异算子,以避免交叉后产生不可行解,相对于传统的算子新算子能够使种群更加的多样化,从而提高找到最优解的概率。
1JSP问题的数学模型
JSP问题主要研究n个工件( J1J2…Jn) 在M个机器( M1M2…Mn) 上完成加工,每个工件有k个工序,每个工序在不同的机器上完成,相应的完成时间也不同。JSP问题的目标就是通过优化工件在机器上的加工顺序,使加工完成的时间最短。通常JSP问题有以下假设:
( 1) 不同工件的工序不存在先后顺序的约束。
( 2) 各个工序一开始加工就不能中断。
( 3) 每台机器可以加工不同工件的不同工序,但一台机器不能同时加工多种工序。
( 4) 每一个工件只有当前一个工序完成加工后, 才能开始加工该工件后一道工序。
( 5) 每一个工序的加工时间和加工机器都是预先给定的。
JSP问题的数学描述如下:
式( 1) 表示目标函数。式中: Cik—工件i在机器k上的完成时间; n—工件数; m—机器数。
式( 2) 表示各工件的加工先后顺序。式中: cjk, tik—工件j在机器k上的完成时间和加工时间; M—一个足够大的正整数,如果工件j比工件i先在机器k上加工,则xijk为1,反之为0。
式( 3) 表示工艺条件约束下各工件的加工顺序。 其中: 如果机器h优先与机器k加工工件i,则aijk为1, 反之为0。
另外对一些符号作如下说明:
( 1) 加工时间矩阵T。T( i,j) 表示加工第i个工件的第j个工序所用的时间。
( 2) 机器顺序矩阵J。J( i,j) 表示加工第j个工件的第j个工序所用的机器号。
2混合遗传算法的设计
在用混合遗传算法求解JSP问题的过程中,关键步骤包括设计编码和解码方式、确定目标函数、设计遗传算子、确定遗传参数以及设计模拟退火过程等。
2.1染色体编码
编码是遗传算法求解调度问题的关键,本研究采用基于工序的编码方式,该编码方式可以避免产生不可行解和死锁现象。当求解n个工件在m台机器上加工的问题时,染色体的基因数等于全部工序的数,为n·m个。每一个工件的工序都用相应的工件号表示, 第i次出现的工件号就表示加工该工件的第i道工序。 如个体[2 3 1 2 3 1 1 2 3]表示3个工件在3台机器上加工,该染色体的加工顺序为工件2,工件3,工件1, 工件2,工件3,工件1,工件1,工件2,工件3。
2.2染色体解码
对于已有的染色体,结合机器顺序矩阵,可以得到加工所有工序的机器序号,从而得到一个有效的生产调度。
2.3适应度值
适应度值用来衡量个体适应环境的能力,适应度值越大越优秀,遗传到下一代概率越大[9]。对于车间调度问题,适应度值是加工完成所有工件的时间Cmax的最小值。
式中: Cmax—加工完成所有工件的时间。
2.4选择算子
选择算子是选择种群中高适应度值的个体进入下一代的操作。本研究采用比例选择方式,即被选中个体的概率正比与个体的适应度值:
式中: Pi—选择的概率,F( xi) —个体适应值。
2.5交叉操作
种群通过交叉操作产生新个体,从而推动种群进化,因此交叉操作是最重要的操作。对于JSP问题,笔者采用传统的交叉操作,产生的新染色体可能存在某个工序的多余或缺失,因此交叉操作的难点在于如何保证交叉产生的新染色体是可行解。本研究设计了基于工件序号的交叉操作,具体步骤如下:
步骤1: 从父代中随机选择两个个体P1P2,随机产生两个不同的随机数i1和i2( 0 < i1,i2< n) ,然后把P1P2中i1和i2都提取出来,保存在新的基因串A1A2中,并且保持这些基因相对位置不变,P1P2中相应的基因位置用0来代替。
步骤2: 然后把A2的基因插入到P1中基因为0的位置,产生子代B1,把A1的基因插入到P2中基因为0的位置产生子代B2。
步骤3: 把子代B1所有基因向左移动一位,子代B2向右移动一位,分别得到最终个体C1C2。例如:
通过以上交叉产生的个体不存在某个基因多余或缺失的情况,都是可行解。步骤3中将子代向左向右移动,可以提高种群多样性,避免遗传算法早熟。
2.6变异操作
种群通过变异操作,产生新个体,在保证种群多样性的同时推动种群向前进化。本研究中变异操作具体步骤如下: 首先随机选择一个个体,随机产生两个位置,将两个位置之间的基因片段逆转,获得新的个体。 例如P1为[4 2 3 1 1 4 2 3 1 3 2 4],两个交叉位置Pose1和Pose2分别为4,9,则两个位置间的基因片段A1为: [1 1 4 2 3 1],通过逆转A1,得到新片段A2为: [1 3 2 4 1 1],最后用A2替换A1,得到子代B1为: [4 2 3 1 3 2 4 1 1 3 2 4]。
2.7初始参数确定
在遗传算法中,交叉概率Pc和变异概率Pm会直接影响算法的收敛性。因此本研究对Pc和Pm进行重新的设计,Pc和Pm会随着适应度值变化而变化,具体如下: 当个体的适应度值大于种群的平均适应度值时, 该个体属于优良个体,应尽力保留,故Pc和Pm应该较小; 反之,Pc和Pm应取较大的值。具体计算公式如下:
式( 6 ~ 7) 中: fmax—当代种群中最大适应度值,favg—当代种群适应度值的平均值,f'—两个交叉个体中较大个体的适应度值,f—要变异个体的适应度值。一般取
2.8模拟退火算法设计
本研究引入模拟退火算法中的Metropolis接受准则使算法跳出局部最优解的“陷阱”。Metropolis接受准则是以一定的概率P来接受比原个体差的新个体, 由该准则判断进过遗传算子的新个体是否替代父代个体,具体公式如下:
式中: T—模拟退火算法中的温度; Δf—经过遗传算子的新个体与原个体适应度值之差,若 Δf大于0,则接受适应值更高的新个体,否则产生一个[0,1]随机数b,若P > b,用新个体代替旧个体。
本研究给定初始温度T0,终止温度Tend,以及降温系数K,在每一次退温过程中,用Metropolis接受准则决定最终的个体,直到达到温度达到Tend。
2.9算法流程图
混合遗传算法流程图如图1所示。
3仿真结果与分析
在混合遗传算法仿真实验中,笔者采用FT06问题作为仿真案例[11],即6个工件,6台机器的调度问题。 机器的顺序矩阵J和加工的时间矩阵T如下所示:
Matlab仿真试验中,采用的初始参数为Pc为0. 9, Pm= 0. 1,Size = 40,T0= 10 000,Tend= 0. 1,K = 0. 9。用混合遗传算法得到最佳个体为[3 3 2 6 1 1 3 2 6 4 2 4 5 3 4 6 2 1 1 1 5 4 5 2 3 6 5 2 3 4 5 5 6 1 6 4],需要的加工时间为55 s,达到该问题的最优解。算法收敛曲线如图2所示,最佳个体的甘特图如图3所示,即工件加工顺序图。
为验证混合遗传算法的可行性,在同样的参数下,笔者分别用遗传算法和模拟退火算法求解FT06问题,得到相应的结果,3种算法的收敛曲线对比图如图4所示。
从图2中可以看到,混合遗传算法进过50代完成了收敛,得到的最佳完工时间为55,与FT06问题的最优解一致,表明混合算法具有一定的搜索精度和较高的效率。
从图3中可以看到,每台机器加工工件的顺序,例如机器1的加工工序顺序依次为工件1第2工序、工件4第2工序、工件3第4工序、工件6第4工序、第5工件第5工序和第2工件第5工序。6台机器上加工顺序包含了所有工件的所有工序,是一个完整的生产计划,也证明混合遗传算法编码方式避免了交叉和变异后产生非法个体。
3种算法收敛曲线对比图如图4所示。对比SA和GASA曲线,可以看到SA曲线前期有很大的波动, GASA收敛更早,表明混合遗传算法能在全局进行搜索最优解,能够控制寻优方向,相对于SA具有更快的搜索速度。对比GA和GASA曲线,可以看到GA曲线前期收敛的非常快,在求解复杂问题时比较容易早熟, 从而只求得局部解。GASA曲线收敛较为平滑,能克服GA容易早熟的缺点。
4结束语
本研究描述了车间调度的数学模型,分析遗传算法在求解车间调度问题时存在的不足之处,重新设计基于工件编号的交叉算子和变异算子,优化了交叉和变异过程,同时采用自适应交叉和变异概率,避免遗传算法在迭代后期出现停滞不前的现状。同时笔者在优化过程中引入模拟退火算法,克服算法容易早熟的缺点。仿真结果显示混合遗传算法能够找到全局最优解,很好的解决JSP调度问题。
本研究以产品的最小完工时间作为目标函数,找到了全局最优解,但实际生产过程中还应考虑客户满意度、生产成本、交货延期惩罚等其他指标,下一阶段应考虑多目标遗传算法的实现,提高算法实用性。
摘要：针对用遗传算法求解车间调度问题(job shop problem)容易早熟的缺点,对遗传算法的收敛性、搜索效率和最优解等方面进行了研究,改进了遗传算法,引入了模拟退火算法,提出了新的混合遗传算法。重新设计了基于工件编号的交叉算子和变异算子;采用自适应交叉概率和变异概率;在每一代遗传进化中引入了Metropolis接受准则。通过结合遗传算法、自适应概率和模拟退火算法的各自优点,提高了算法搜索能力。用遗传算法、模拟退火算法和混合遗传算法对Job Shop Problem中FT06问题进行了仿真。仿真结果表明,混合遗传算法提高了搜索效率,能够找到最佳的调度方案。
混合遗传模拟算法 篇6
机组组合优化问题包括两个基本方面,一是机组组合,即在考虑系统容量和备用以及机组的最小开停机时间等约束的条件下,确定计划周期中每个时刻机组的运行方式;二是机组负荷经济分配,即确定每个时刻系统负荷需求在运行机组中的分配[1],并使系统的发电能耗最小。
目前,用于机组组合优化的算法有优先级表法[2]、动态规划法[3]、拉格朗日松弛法[4]等传统方法和遗传算法[5~7]、粒子群算法[8~10]等智能算法以及智能混合算法[11]。文献[2]的优先级表法,按照某种经济指标投切机组,计算速度快,但往往不能找到最优解。文献[3]的动态规划法状态变量的维数较高,容易造成“维数灾”,计算速度很慢。文献[5]采用分时段处理机组组合优化,取得了比文献[4]中拉格朗日松弛法好的效果。文献[8~10]中的粒子群算法具有较强的局部寻优能力,计算速度快。文献[11]混合使用两种智能算法,取得了更强的寻优能力。在研究了遗传算法和粒子群算法基本原理的基础上,综合遗传算法的全局优化能力和粒子群算法的局部寻优能力,提出一种优化机组组合的遗传粒子群混合算法,相对于文献[11]更好地解决了各约束条件,避免了硬约束的使用。先用二进制编码的遗传算法优化机组的组合状态,并在设置变异算子时充分体现节能调度尽量开大机组、少开小机组的原则。再在遗传算法优化得到机组组合的基础上,用粒子群算法实现负荷在开机机组之间的经济分配。
1 机组组合的数学模型
1.1 目标函数
机组组合优化就是合理安排机组的启停计划,以使系统的总发电成本最小,总发电成本包括机组发电耗量和机组启动耗量。所以机组组合优化的目标函数为
式中,T为总时段数;N为机组数;uit为机组i在时段t的状态,其值为0时表示停机,为1时表示开机;itP为机组i在时段t的出力;F i(P it)和Si分别表示机组i的发电耗量和启动耗量。
计算发电耗量和启动耗量的公式分别为
式中:ai、bi和ci为机组i的运行耗量特性参数;S0,i、S1,i和τi为机组i的启动耗量特性参数;Titoff为机组i在时段t的已停机时间。
1.2 约束条件
(1)负荷平衡约束
式中:PDt为t时段的负荷。
(2)旋转备用约束
式中:PRt为t时段的旋转备用,本文取
PRt=0.07PDt;Pimax为机组i的最大出力。
(3)机组出力上下限约束
式中:Pimin为机组i的最小出力。
(4)最小开停机时间约束
式中:Toitn和Titoff分别为机组i在时段t的连续开机时间和停机时间;Tonimin和Toffimin分别为机组i在开停机后必须保持开停机状态的最短时间。
(5)机组加减出力速率约束
式中:PUi和iDP分别为机组i加减出力上限(不包括机组启停情况)。
(6)线路潮流限制、分区功率平衡等约束,本文未考虑这些因素。
2 机组组合优化的遗传粒子群混合算法
2.1 遗传算法及其改进
遗传算法(GA)是一种模拟生物的自然选择和群体遗传机理的数值优化算法,根据适应值函数(目标函数)进行选择、交叉、变异操作,经过反复进化迭代,逐渐逼近全局最优解。
在保留GA算法基本步骤和结构的同时作了如下改进。
(1)遗传种群
采用文献[4]中的10机系统,并按照全天最小负荷的80%确定9、10机组承担基荷,即全天为开机状态,且不参加变异操作;8、7为大机组;1、2、3为小机组。采用一个T×N的0-1矩阵代表种群中的个体,产生的个体满足式(5)、(7)、(8)。
(2)选择操作
在研究了传统轮盘赌选择特点的基础上,决定采用PK选择法和最优保留策略法,即在父代中任意选择两个个体,比较其适应值,适应值小的选中,而最优个体直接进入子代。
(3)交叉操作
分两步进行列交叉和行交叉。列交叉后检查是否满足式(5),不满足就重新交叉;行交叉后检查是否满足式(7)、(8),不满足就取消本次交叉。如下个体,箭头所示位置即为列交叉和行交叉的交叉点。
(4)变异操作
为了更快地得到最优解,并体现节能调度的原则,使用两步变异操作。首先根据节能调度中“上大压小”的原则,进行机组全天变异操作,对大机组给出一定的概率p,满足概率要求,就把该机组的停机状态全部转为开机,然后依次关闭小机组,关闭一台就检查个体是否满足式(5),不满足就取消上步操作,并终止全天变异操作。接着进入单点变异操作,变异时需检查是否满足式(5)、(7)、(8)。
2.2 负荷经济分配
遗传算法中的选择操作需要各个体的适应值,由遗传算法得到机组组合,然后根据负荷经济分配结果计算发电成本。本文采用粒子群算法处理负荷经济分配。
式中:pmax、pmin分别为机组出力的上下限;a为(0,1)之间的随机数;u为机组状态。
在粒子群算法中,按式(10)初始化粒子的速度和位置,并按式(11)更新粒子速度。
式中:vij(n)为第n个粒子群中粒子i第j维的速度;1c和2c为加速率;r1,i(n)和r2,i(n)为(0,1)上的随机数;p ij(n)为第n个粒子群中粒子i的极值在j维的位置;∧pj(n)为第n个粒子群的极值在j维的位置;xij(n)为第n个粒子群中粒子i第j维的位置;w为惯性权重,且
式中:wmax=0.9,wmin=0.4,Iter为当前迭代次数,Max Iter为最大迭代次数。
得到更新后的粒子速度,按式(13)更新粒子位置。
如果位置更新后,xij(n)大于pmax,则
xij(n)=pmax;小于pmin,则xij(n)=pmin。得到粒子位置后计算目标函数值,并更新粒子群的极值位置和粒子的极值位置。计算目标函数时,用罚函数处理不满足式(4)、(9)的情况,并用罚函数处理平衡节点机组不满足式(6)的情况。t时段第k个粒子对应的第i台机组的出力为
综上,遗传粒子群混合算法优化机组组合的流程如图1所示。
3 仿真结果与分析
3.1 仿真参数
机组参数、负荷等数据见文献[4]。仿真实验参数如下:遗传算法中,种群个体数为40,迭代次数50,交叉算子0.6,全天变异算子0.6,单点变异算子0.5;粒子群算法中,粒子数为20,迭代次数为50,惯性权重如式(12),加速因子1c和2c为2.05。
3.2 算例结果和分析
用遗传粒子群混合算法(GA-PSO)对10机系统24时段内的机组组合问题进行优化计算,计算46次得到的燃料耗量结果分布如图2所示,得到最差解80 277.27 t相对于最好解78 862.72 t的偏差为1.79%,且偏差在1%以下的次数达到71.74%。由46次平均计算结果可以得到混合算法的收敛曲线如图3所示。由此可见,提出的混合算法具有较好的寻优能力和收敛性。
计算46次得到的燃料耗量最好结果与拉格朗日松弛算法(LR)[4]、遗传算法(GA)[5]、蚁群算法(ACO)[12]、蚁群粒子群混合算法(ACO-PSO)[13]的结果比较见表1。10机系统优化的经济分配结果见表2,出力为0表示停机状态,不为0表示开机状态。
通过表1可以看出,智能算法的结果优于传统算法,而混合智能算法又优于单一智能算法。GA-PSO算法计算出的运行耗量为78 655.44 t标准煤,启动耗量为207.280 5 t标准煤,总耗量为78862.7 t标准煤。较文献[4]LR算法节省2.932 8%(2382.779 t标准煤)。较文献[5]一般GA节省1.1832%(944.279 2 t标准煤)。较文献[13]ACO-PSO节省0.186 5%(147.379 2 t标准煤)。如果不设置全天变异操作,则GA-PSO求得的耗量最低为80594.02 t标准煤,通过负荷经济分配结果发现,这时小机组还有一台开机,且大机组没有能够全天开机,这可能是造成总耗量高的原因。
4 结语和展望
混合遗传模拟算法 篇7
敏捷卫星是近年来出现的新一代对地观测卫星,由于保密的原因,国内外公开的相关敏捷卫星任务规划问题的文献资料不是很多。典型的主要有法国Lemaitre等人针对新一代敏捷卫星Pleiades的任务规划问题研究,提出了约束规划模型,比较了约束规划、贪婪、动态规划以及局部搜索等四种算法,并指出了各自的适用范围[1]。Panwadee针对敏捷卫星任务规划问题建立了多目标优化模型,提出了遗传算法的求解策略[2]。在国内研究中针对敏捷卫星的常规任务规划问题,陈宇宁,等分析了灵巧卫星调度问题的约束条件,构建约束满足模型,提出了基于蚁群算法的调度求解策略[3]。李玉庆构建了任务规划调度的数学模型,并采用了模拟退火算法和遗传算法相结合的混合遗传算法求解策略[4]。对于非敏捷卫星任务规划,美国的Wolfe等学者采用了三种算法求解对地观测卫星任务规划问题,研究表明遗传算法求解效率优于优先级调度算法和具有前看功能的求解算法[5]。由此可见,在解决卫星任务规划非线性NP-hard问题时,智能优化算法在求解敏捷卫星任务规划问题时具有很多优势。
在深入分析敏捷卫星任务规划特点的基础上,首先对敏捷卫星任务规划问题进行了抽象描述;然后构建了基于多目标的敏捷卫星任务规划模型;最后提出了蚁群算法和免疫遗传算法相结合的混合遗传求解方法。
1 问题描述及模型构建
1.1 敏捷卫星观测方式
敏捷卫星观测视角可以围绕翻滚、俯仰和偏航三个轴变化,具有三维观测自由度,它可以进行完成滚动、俯仰、偏航的星上动作,因此其具有很强的姿态机动能力。敏捷卫星有可能在能力允许的范围内沿任意走向对目标进行观测,因此敏捷卫星的灵活性和观测效率由于姿态敏捷的控制而得到了很大的提高,如图1所示[6,7]。敏捷卫星切换速度快,在俯仰轴14秒内可达到45度,平均速度可达到了3.2度每秒[8]。敏捷卫星能够进行俯仰,其可视时间窗口也相对比较宽泛,其可以在可见时间窗口内较自由地选择可见时间窗对观测目标进行观测。而非敏捷卫星不能做出俯仰的姿态,因此其只有在经过地面目标上空时才可见观测目标[9,10]。它们的观测方式对比如图2所示。正是由于敏捷卫星观测方式的复杂性,导致其任务规划求解对比于传统的非敏捷卫星任务规划问题更为复杂。
1.2 敏捷卫星对地观测组织实施
敏捷卫星对地实施过程是将包含有任务类型、任务目标优先级以及任务图像分辨率等要求的多用户任务需求,经过智能辅助分析后形成规范化的任务集;以敏捷卫星和地面站部署的现有资源集为基础,充分考虑敏捷卫星携带传感器类型、存储容量、俯仰角以及侧视角范围等一系列约束条件,在一定的规划时间范围内统一规划有限的敏捷卫星资源,将待观测任务集合理地安排到各个敏捷卫星上执行完成观测任务;然后将任务规划方案提交给地面测控中心进行操控实施调度,通过地面测控与观测目标的数据接收处理、评估后将用户所需的数据发送给敏捷卫星需求用户。卫星任务规划可以大大提高敏捷卫星的对地观测效率,可以满足更多的敏捷卫星用户需求。如图3所示敏捷卫星对地观测组织实施流程。
1.3 模型假设
敏捷卫星任务规划问题是一个极为复杂的问题,涉及到的决策对象繁多,还需要考虑对象间的关系错综复杂,而在解决问题时不可能考虑到所有的约束条件;为了更贴近实际,解决关键问题,需要对任务规划问题简化并适当做出一些假设,而这些假设都是与卫星任务规划调度实际紧密结合的,假设也是合理的[11]。
(1)每个敏捷卫星只携带一个星载传感器。
(2)同一颗敏捷卫星同一时刻只能执行一个元任务,而且只要开始执行一个元任务,则不能中断。
(3)敏捷卫星可靠性高,工作时故障发生的可能性很低;同时也不考虑天气、云层等有关气象条件对目标观测的影响。
(4)除周期性任务外,每个元任务在敏捷卫星规划的一个周期内只执行一次。
1.4 模型构建
1.4.1 目标函数
敏捷卫星任务规划的目标是在某一确定的时间段内,在满足卫星约束的前提条件下以尽量少的资源消耗完成尽可能多的任务、获得最大的综合收益,同时也希望各个敏捷卫星间负载更加均衡,达到尽量好的卫星成像效果。因此其敏捷卫星任务规划问题是一个多目标优化问题。任务规划目标函数数学表述如下。
目标1:任务收益率最大,即
目标2:任务完成率最大,即:
目标3:资源使用均衡度最大,即尽可能满足各可用载荷上负载均衡,工作时长均匀一些。即:
资源使用均衡度公式如下:
其中,max SWT=mjax(SWTj)。wi为观测任务ti的收益,PRI(ti)为观测任务ti的优先级,N为观测任务集中的任务总数。Tetij代表观测任务ti的结束时间,Tstij代表观测任务ti的开始时间。对于上述三个目标可以利用加权法实现。
maxf1=αM1+βM2+γM3,其中α,β,γ为影响因子,α+β+γ=1。
1.4.2 主要约束条件及数学描述
(1)可见时间约束
式(1)和式(2)要求观测任务起始时间必须在卫星与观测目标的可见时间窗内执行,其可见时间长度必须要大于任务的执行时长。其中,ETik为观测任务ti的可见时间窗的结束时间,Tstij为可见时间窗ti的开始时间。DuraT(ti)为观测任务的持续时间。
(2)俯仰角和侧摆角约束
式(3)和式(4)是侧摆角与俯仰角的约束条件,要求在任务转换时敏捷卫星在有限的时间内能够达到下次观测任务时所需要满足俯仰角和侧摆角的约束条件。其中,FAgij和BAgij分别为敏捷卫星j中观测任务ti在STjik时刻的俯仰角和侧摆角;ajf和ajb分别为敏捷卫星j进行姿态调整俯仰和侧摆两个姿态时的角加速度。
(3)太阳高度角约束
式(5)是太阳高度角约束,要求卫星执行任务时刻应该满足最小太阳高度角要求。其中,Ai(Ai∈(0,90])是任务ti在STjik时刻的太阳高度角。SEAmin是满足成像要求的最小太阳高度角。
(4)能量约束
式(6)是能量约束,卫星侧摆俯仰以及照相时所消耗的能量敏捷卫星应该能满足,其应该小于卫星最大能量。其中,ηi为敏捷卫星j观测单位时间内所消耗的能量;ρi表示敏捷卫星j在姿态调整时单位角度内所消耗的能量;πj卫星j在阳照区单位时间内的充电量;SNLij表示执行观测任务ti前敏捷卫星j可用的能量;SNLi表示敏捷卫星j最大的可用能量。
(5)存储容量约束
存储容量约束式(7)要求敏捷卫星在一个轨道圈次内执行观测任务ti时星上可用的存储容量满足成像要求。其中,SSRjt代表敏捷卫星j在t时刻的存储容量;imageSSR(tj)表示为执行观测任务ti所需要的存储容量;MaxSSRj代表敏捷卫星j的最大存储容量。
2 免疫遗传蚁群混合求解算法
从敏捷卫星任务规划模型中可以得出其目标函数具有非可导性、非连续;任务规划中的一些先验信息较少或者不存在;因此其为求解带来了一定的难度。遗传算法对于解决多数组合优化和调度问题,处理复杂约束问题和非线性问题具有众多优势。
同时针对蚁群算法具有初始解好,易陷入局部最优,收敛速度慢,求解精度不高等特点,并结合遗传算法的优点[12]。本文提出了将蚁群算法与免疫遗传算法相结合的求解算法,其能够克服每个算法的缺点,充分发挥各自的优势。
2.1 混合求解算法流程
设计的求解算法基本思想是将蚁群算法每次迭代中所产生的全部解的集合作为初始种群,对初始种群进行免疫遗传算法的多次进化迭代操作,尝试寻找相对于当前全局最优解更优秀的解,如图4所示求解算法流程图。
2.2 状态转移规则及信息素的更新
针对敏捷卫星任务规划的特点,借鉴蚂蚁系统的思想,本文在蚁群算法中的状态转移规则如下:一只处于节点r的蚂蚁应用式(8)选择将要移动到的下一个j节点[13]。
式(8)中,q为[0,1]均匀分布的随机变量,q0(0≤q0≤1)是一个参数;ηij是距离tij的倒数,tij是任务执行间隔时间的影响;Y的选择主要依据式(9)中的概率分布函数。
式(9)中,alldk(Ti)为蚂蚁k下一步可执行任务的集合;τij是信息素分布,PRI(ti)为观测任务的优先级影响。α,β,γ分别为各个影响因素作用强度的权重。
信息素局部更新策略:当蚂蚁从任务T(t0)出发,依照状态转移寻优策略选择下一个任务节点,若找不到,则返回;若找到,则构造可执行任务序列TSequ,将其目标值与当前全局最优任务执行序列TSequB的目标进行比较,若小于,则TSequ所有边上的信息素挥发,τNij=(1-ρ)τijOld,ρ为信息素挥发率;若大于,则更新全局最优解TSequB=TSequ。为加快收敛速度,每次依据式(10)只对最优任务序列上的信息素浓度进行更新。
式(10)中,,R为设定的参数。
2.3 混合求解算法基本操作
2.3.1 染色体编码结构
编码是遗传算法的关键,编码结构的选择会对求解空间产生直接的影响。编码方案是确定染色体串与问题的搜索空间中的点之间的映射关系。本文采用二进制编码方式构造染色体。敏捷卫星成像目标任务只有完成或不能完成两种状态,长度为N的等长0—1二进制编码构造染色体被选择采用。每一个二进制序列被称之为一个染色体段,因此整个二进制序列所代表的敏捷卫星成像任务的集合即为任务规划的结果。染色体串的每一位取值代表了该观测目标是否被选取,每个基因位对应着一个敏捷卫星观测元任务。
其中,将X={x1x2…xi…xN}。
为种群中的一个染色体,其染色体编码结构如图5所示。
2.3.2 遗传操作
选择:选择基于适应度比例的选择策略,即常用的轮盘赌法,个体i被选中的概率为,其中fi为个体i的适应度值;N为种群个体数目。
交叉:采用多点交叉的方法来进行,如图6所示。多点交叉比单点交叉具有更好的鲁棒性,具有更好的重组能力,不但可以解决过早收敛的问题,而且可以加快算法对整个解空间的搜索速度。
变异:每个个体的变异概率采用公式(11)来计算:
式(11)中,fmin和favg分别表示当前种群中个体适应度值的最小值和平均值,fi代表第i个个体的适应度值,P[i]代表第i个体变异概率。
3 实例分析
实例为10颗星,600个元任务的仿真场景,应用STK软件及Matlab2011a软件,卫星轨道数据来源于AGI公司于2010年6月发布的全球卫星轨道数据库,任务分布主要集中在重点热点地区,任务生成方法采用文献[14]的方法。为表述更加清晰,选择在实际应用中最广泛的点目标观测需求为例展开研究。仿真中的参数设置为:免疫遗传操作最大代数MAXGEN=1 300,交叉概率pc=0.95,变异概率pm=0.08,疫苗接种概率pv=0.5;蚂蚁数AntCount=40。所设计的算法与遗传算法和免疫遗传算法进行了对比,在内存为4 G,Intel-i5双核心CPU的环境下将每个算法运行15次,取平均值,对任务收益率、负载均衡度以及综合收益率几个方面进行了比较分析。运行结果统计处理后如表1、图7、图8所示。
从表1中可以看出在达到约98%最佳解性能时,遗传算法所用时间最多,免疫遗传算法次之,IA-COGA算法所用的时间最少,与GA相比节省了约373 s,可见其求解效率很高。
为运算结果对比更加清晰,加入了求解敏捷卫星任务规划的规则算法,主要有先来先服务(FIFS)和优先级规则算法(Priority),由于规则方法执行时间极短,因此本文将其画成直线与其它算法形成直观的对比,便于分析。从图7中可以得出IACOGA算法综合指标最高,其任务收益率高于其它算法;其次是IGA算法得到的结果,较接近IACOGA算法求得的值;GA算法、IGA算法以及IACOGA算法最终都超过了FIFS算法和Priority算法,相比较而言GA得到的理想解是最不理想的。从图8中可以得出IACOGA算法的任务均衡度也是最高的,优于其它两种算法。
综合来看,在算法初期,IGA算法曲线起点较高,但随着时间的推移,曲线上升幅度很小,很平缓。GA算法曲线初始起点较低,一段时间内上升幅度较大,但到最后曲线很是平缓,其方差波动也较大。IACOGA算法曲线起点较高,曲线上升也较快,其方差波动也较小,因此所设计的混合遗传算法具有较佳性能。
4 结束语
混合遗传模拟算法 篇8
关键词：云遗传算法,混沌,粒子群算法,混合算法
Kennedy和Eberhart受到鸟群觅食行为的启发,提出一种模仿鸟群觅食行为的多元搜索优化算法,即粒子群(particle swarm optimization,PSO)算法[1,2,3,4]。PSO算法因其自身良好的局部收敛效果、快速的收敛速度、易于实现以及控制参数少等优点[5,6],在提出后得到了广泛应用。但是PSO算法种群随机初始化遍历性差、易陷入早熟收敛和不具备全局收敛性的缺点[7,8],极大地限制了PSO算法的性能。为了提高PSO算法的性能,文献[9]通过自适应策略,动态地调整PSO算法的惯性权重参数,来提高PSO算法的全局收敛性能;文献[10]提出一种遗传算法和PSO算法相结合的混合路径规划方法,避免了PSO算法陷入早熟收敛;文献[11]通过在PSO算法初始化阶段引入Logistics混沌映射,利用Logistics混沌映射的遍历性和随机性,提高了初始粒子的质量。
为了解决PSO算法存在的不足,本文提出一种基于云遗传的混合混沌粒子群算法(cloud genetic hybrid PSO,CGHP),使用均匀性更优的无限折叠混沌映射实现粒子的初始化,通过自适应云算子、改进的Metropolis接受准则以及动态调整粒子集规模等策略,实现了云遗传算法和PSO算法的协同,并进行了全局收敛性证明、时间复杂度分析和实验分析。
1 算法介绍
1.1 PSO算法
在一个涉及到h维解空间的问题中,假设粒子群的规模为m,第i个粒子为Zi=(zi1,zi2,…,zih),粒子i的速度为Vi=(vi1,vi2,…,vih)。依据不同粒子的适应度值来判定不同粒子的优劣,粒子i适应度最佳的个体最优解为Pi=(pi1,pi2,…,pih),而种群中具有最佳适应度值的种群全局最优解为Pg=(pg1,pg2,…,pgh)。粒子群算法在运算过程中,根据速度更新公式和位置更新公式来实现粒子的进化,速度更新和位置更新的公式[6]如下
其中,i表示粒子数,t为迭代次数,T为最大迭代次数。c1与c2为加速常数,r1和r2是两个随机数,ω为惯性权重[11]。图1为二维空间内粒子位移示意图。粒子群根据更新公式不断向最优粒子靠拢,但当最优粒子为局部最优时,算法将会陷入早熟收敛[7]。
1.2 云遗传算法
1995年李德毅教授在概率论、数理统计和模糊数学基础上首次提出云模型理论[12]。云模型是一种用自然语言描述定性概念与定量概念的双向认知转换模型[13]。云模型具有三个典型数字特征,即Ex,En和He。其中,Ex是云的期望,集中体现云的定性概念,最能代表样本空间中最优个体的特征;熵En用来表征不确定性的带宽,亦代表随机性和模糊性的范围;He是熵的熵,衡量熵的不确定性和模糊性,通常,采用这三个数字特征共同反映一朵云的定性概念。
云模型发生器是指被软件模块化或硬件固化了的云模型生成算法[14],现采用Y条件云发生器进行交叉操作,由正态云发生器进行变异操作,如图2。
云遗传算法在传统的遗传算法思想中集合了云模型理论[15],借助云模型的随机性和稳定倾向性的特点,采用云模型更新个体,保证了给个体的多样性和全局最佳定位,从而有效克服了传统遗传算法的早熟收敛和易陷入局部最优等缺点。
2 CGHP算法
2.1 初始化
标准的PSO算法初始化过程是随机的,往往使初始粒子分布不均匀,出现大量粒子远离最优解的现象[6]。为了克服这一缺陷,文献[16]和文献[17]利用混沌模型来对PSO算法进行初始化。混沌(Chaos)是确定性系统在长期演进中表现出来的一种从有序到无序的伪随机自组织过程,具有规律性、遍历性等特点[18]。Logistic映射是一种常用的一维迭代混沌模型,其函数映射式为
当μ=2时,映射处于满射混沌状态,其在(0,1)上概率密度函数为:
Logistic映射在(0,1)区间上的概率密度曲线如下
从图3中可以看出,Logistics映射存在着边缘骤变,中间平缓,区间两端处概率大于区间中部概率的特点[19],映射的均匀分布特性较差。文献[20]提出一类无限折叠混沌映射,并通过实验证明了在区间(0,1)内较Logistics映射具有更佳的均匀分布特性,其函数映射式为
为避免搜索的盲目性,提高搜索效率及遍历程度,采用均匀性更优的无限折叠混沌映射产生随机数序列randi对初始种群进行赋值,种群中粒子不同维度取值范围为[zmin,zmax],则采用下式对种群粒子的各个维度进行初始化:
2.2 自适应云算子
在云模型的三个数字特征中,He与En成正比,En一方面反映云模型中元素在论域空间中的范围,即云模型的水平宽度,另一方面其又是随机性的度量,反映了云滴的离散程度[18]。在执行云遗传算法时,对于适应度低的粒子,需要产生方差较大、离散程度髙的云滴,以增强搜索能力,提高产生更高适应度后代的概率;对于适应度髙的粒子,则产生方差小、离散度低的云滴,以保证算法的收敛效果。因此,本文提出一种自适应于粒子适应度的云交叉算子和云变异算子,对云遗传算法进行改进。
自适应En定义如下:
式(7)中Fmax为父代最大适应度,Fmin为父代最小适应度,m=t(D1),t(D1)为区间(0,5)上服从t分布的随机数,D1的表达式如下
在自适应条件下,适应度低的粒子,D1较小,t分布产生较大随机数的概率髙,易产生较大En值,可以产生离散程度高的云滴,提高产生更高适应度后代的概率;适应度髙的粒子,D1较大,t分布产生较小随机数的概率较髙,易产生较小的En值,可以产生离散程度低的云滴,可以保证算法的收敛性。
定义云交叉算子如下
式(9)中Ex为两个父代个体的适应度均值,He=n1En,E'n是以En为期望值,以He为标准差生成的一个正态随机数。
定义云变异算子如下
式(10)中Ex为单个父代个体的适应度值,He=n2Ee,E'n是以En为期望值,以He为标准差生成的一个正态随机数。
2.3 基于云遗传的混合粒子群算法
在传统的PSO算法中,随着算法的进行和迭代次数的增加,粒子群种群多样性不断损失,直到算法陷入早熟收敛[7]。因此,定义种群密度(population density,PD)来衡量粒子群种群多样性水平,作为判断是否进入早熟收敛的依据,其表达式为:
式(11)中zij为第i个粒子的当前第j维值,pgj为群体当前最优粒子的第j维值。当种群密度小于预设值时,表示粒子群算法陷入早熟收敛。
为了解决PSO算法的早熟收敛问题,提出改进Metropolis接受准则更新全局最优解和动态减少PSO算法粒子数两种策略,实现PSO算法和云遗传算法的协同。
改进的Metropolis接受准则:若云遗传算法种群最优粒子Pgc的适应度fc大于PSO算法的种群最优粒子Pgp的适应度fp,则将Pgc作为共同的全局最优粒子Pgt存储于全局最优数据库中,并令Pgp=Pgt;否则,若Er=exp[-(fc-fp)/A]大于随机数R,则仍接受Pgc为全局最优粒子存储于全局最优数据库中,若Er小于R,则接受Pgp为全局最优粒子存储于全局最优数据库中,并令Pgc=Pgt。其中A=a/lg(t+T),a为一个趋近于1的常数,T为协同算法最大迭代次数,t为算法当前迭代次数,R=t(D2)/5,t(D2)为区间[0,5]上由t分布产生的随机数,D2公式如下:
当种群密度小于预设值,PSO算法陷入局部收敛时,依据式(11),保留PSO算法当前粒子数mt中前mt+1个粒子,将其他粒子加入云遗传算法中。
CGHP算法流程如下。
Step1:利用无限折叠映射对种群进行初始化,产生两个规模为m的粒子集A、B。
Step2:判断是否达到结束条件,若达到,终止运算,并输出全局最优数据库中适应度值最大的粒子;否则执行Step3。
Step3:根据种群密度,判断PSO算法是否进入早熟收敛,若进入早熟收敛,动态增减数据集A、B的粒子数,然后执行Step4;否则,直接执行Step4。
Step4:对数据集A、B分别进行PSO算法和云遗传算法,将PSO算法和云遗传算法产生的各自的全局最优解Pgp和Pgc利用改进的Metropolis接受准则进行筛选,将接受的最优解赋值给协同算法全局最优解Pgt存入全局最优数据库中,并令Pgp=Pgt、Pgc=Pgt,然后执行Step2。
CGHP算法流程图如图4。
其中执行云遗传算法的流程图5所示。
3 收敛性和时间复杂度
3.1 收敛性分析
对于云遗传算法,虽然相较于传统的遗传算法,其采用云模型进行选择、交叉和变异操作,但是由于“交叉-变异-选择”操作和进化代数无关,云遗传算法构成了一个有限状态齐次马尔科夫链[15],且CGHP算法中的云遗传部分采用保留最优个体的精英选择方法。文献[21]应用齐次有限马尔科夫链分析并证明了保留最优个体的遗传算法以概率1全局收敛,云遗传算法构成有限齐次马尔科夫链并保留最优个体,虽然在遗传算法的基础上引入了云模型,但仍然具有全局收敛性。
Solis和Wets[22]给出的一般随机搜索算法收敛性判定准则及相关定理,文献[5]利用收敛判定准则证明了协同算法的收敛性。根据收敛性判定准则及相关定理,并参考文献[5],给出CGHP算法全局收敛性的证明。
一般最优化问题可记为<A,f>,对于随机搜索算法D,其第k次寻优结果为Xk,下一次迭代寻优结果为Xk+1=D(Xk,ζk)。其中,A为Rn上某个子集的σ-域,f为适应度函数,ζk为算法D寻优过程中找到的解。
判定准则1:算法D满足f(D(x,ζ))≤f(x),若ζ∈A,则f(D(x,ζ))≤f(ζ)。
准则1要求随机搜索算法D是广义单调非递增的,从而保证适应度值f(x)是非递增的。
判定准则2:对于A的任意Borel子集P,若满足v(P)>0,则有
式(15)中,μk(P)为算法D在第k次迭代中搜索到的解在集合P上的概率测度。准则2说明,只要是可行解空间A中概率测度大于零的子集P,算法D连续无穷次搜索不到集合P中解的概率为0。
引理(随机算法全局收敛的充要条件):若函数f可测,可测空间A是Rn上可测子集,且算法D满足条件1和条件2,{xk}∞k=1是算法D产生的解序列,则
式(16)中,P(xk∈Rε,M)是算法D第k步搜索到的解xk在最优区域Rε,M中的概率测度。
文献[8]指出PSO算法不能以概率1收敛于最优解,文献[23]证明种群初始分布不会直接影响算法收敛性,因此证明CGHP算法的全局收敛性,仅需证明PSO算法和云遗传算法的协同过程的全局收敛性。
定理设CGHP算法优化的目标函数f是一个可测函数,其解空间S为Rn上可测子集,并且CGHP算法满足随机搜索算法全局收敛的准则1和准则2,设{xk}k∞=0是CGHP算法所产生的解序列,则
式(17)中,P(xk∈Rε,M)是CGHP算法第k步搜索到的解xk在最优区域Rε,M中的概率测度。
证明:
依据CGHP算法协同部分的流程,迭代函数F可定义为
因为CGHP算法利用全局最优数据库保留种群最优解,即采用适应度值非递增的精英保留策略,可知算法满足准则1。
如果CGHP算法满足准则件2,则规模为n的混合种群样本采样空间的并集一定包含目标函数f的解向量空间S,即
式(19)中,Mi,k为第k次迭代种群中粒子i的样本空间支撑,即概率测度为1的最小闭子集。
令Yk为云遗传算法在第k次迭代时搜索到的解。因为单独执行云遗传算法算法得到的解序列{Yk}以概率l全局收敛于最优区域Rε,M。因此,在CGHP算法中,对于有限个满足f(Yk)>f(Pg,k)的解Yk,可令其下一状态为Pg,k,并将其存储于全局最优数据库中,而且该机制对云遗传算法全局收敛性没有影响,即在CGHP算法中恒有公式(20)成立,也就是说,当f(Yk)<f(Pg,k)时,存在一个粒子i0,其支撑集Mi0,k=S。
而对于其他粒子i,
式(20)中,0≤φ1≤c1,0≤φ2≤c2,可知Mi,k为一个顶点为(φ1,φ2)=(0,0),另一个顶点为(φ1,φ2)=(c1,c2)的超矩形。
当max{c1|Pi-X(t-1)|,c2|Pg-X(t-1)|}<0.5diameterj(S)时,有:v(Mi,k∩S)<v(S),其中,diameterj(S)表示解向量空间S在第j维分量的长度。因xi收敛到平衡点(φ1Pi+φ2Pg)/(φ1+φ2),所以Mi,k长度趋于0。随着迭代次数k增加,v((Mi,k∩S))和v(∪i≠i0(Mi,k∩S))逐渐减少,从而存在整数k1,当k>k1时,v(∪i≠i0(Mi,k∩S))<v(S)),但是因为有支撑集Mi0,k=S,所以∪ni=1Mi,k=S。令S的Borel子集A=Mi,k,则v(A)>0,且(22)式成立,从而CGHP算法满足准则2。
综上所述,CGHP算法的PSO算法和云遗传算法的协同部分,满足随机搜索算法全局收敛的判定准则1和判定准则2。因此CGHP算法的搜索序列以概率1收敛于全局最优解,即CGHP算法具有全局收敛性。
3.2 时间复杂度分析
算法时间复杂度[24]是衡量算法性能优劣的标准之一,CGHP算法的时间复杂度主要由四部分构成:无限折叠混沌映射初始化、PSO算法和云遗传算法并行协作全局搜索、种群密度判定和改进Metropolis接受准则进行最优解筛选。
设种群规模为2m,粒子维数为h,T为最大迭代次数。初始化的时间复杂度为O(h·m)。设PSO算法和云遗传算法的粒子数分别为mtp和mtc,t为迭代次数,则在PSO算法中,初始化粒子群的速度、适应度值的复杂度均为O(h·mtp),个体最优和种群全局最优选取也均为O(h·mtp);在一次迭代寻优过程中,所有粒子速度、位置更新及适应度评价的复杂度均为O(h·mtp);对于云遗传算法在一次交叉、变异和计算适应度的复杂度均为O(h·mtc),选择和评价优劣等操作复杂度均为常数O(C)。因此协同部分的时间复杂度为O[h·(mtp+mtc)·T],又因为mtp+mtc=2m,PSO算法和云遗传算法协同部分的复杂度为O(h·m·T)。种群密度判定和改进Metropolis接受准则进行最优解筛选的时间复杂度均为O(T)。综上,CGHP算法的时间复杂度为O(h·m·T),且与PSO算法的复杂度[[25,26]]在同一数量级上。
4 实验分析
4.1 测试函数
为测试CGHP算法性能,选取4个典型benchmark测试函数[[27,28]]对算法性能进行验证,并对测试结果进行分析,测试函数如表1所示。
测试函数的三维视图如图6所示。
其中,Quadric noise具有一个广阔的平坦区域;Rosenbrock是一个非凸且变量间具有高度相关性的函数,其全局最优位置在狭长的抛物面状谷底内,搜索方向极难辨别;Griewanks是一个变量间相互独立的多峰值函数;Rastrigin是一个具有大量正弦波动特性局部最优位置的多峰值函数,其变量间相互独立。本文采用的多峰函数均为非线性复杂函数,大量局部极值点的存在特别适合测试改进算法全局寻优特性和避免过早收敛等方面的性能。
4.2 实验结果和分析
所有算法实现的编译环境均为MATLAB R2014a。实验参数设置如下:初始种群规模为40,两个子种群规模各为20,为进一步优化CGHP算法在进化过程中的开发和开采性能,惯性权重ω从0.9线性递减至0.4,学习因子c1、c2均为1.494,最大迭代次数为1 000,种群密度阈值为0.05。同于对比的PSO算法[29]和CSPSO算法[30]的参数设置与原始文献中设置保持一致。
实验对维数为30的测试函数(f1~f4)分别进行30次独立实验,算法性能测试的最终结果如表2所示。
为便于验证分析,表2中实验结果均以“寻优平均值+标准差”形式表示每个解,同时,在表2中的0.05显著水平下双侧t-检验结果符号标记及相应释义如表3所示。
从表3中的实验结果可以看出,对于单峰函数f1和f2而言,CGHP算法与标准PSO算法、CSPSO算法相比,在提高寻优精度的同时,解的标准差为0,解的稳定性显著提高;三种算法都可以找到全局最优解,CGHP算法的全局最优解质量最高,标准PSO算法和CSPSO算法均可收敛到相应容忍度下限,且CSPSO算法优于标准PSO算法。多峰函数f3和f4具有众多的局部极值点,CGHP算法相较于其他两种算法,同样可以显著提高解的质量,并且获得了测试函数f3的全局最优解;对于测试函数f4而言,CGHP算法虽未获得全局最优解,但是子PSO算法和云遗传算法的协同以及全局最优数据库保存全局最优的策略仍然能够使CGHP算法得到精度更高的解。在0.05显著水平下的双侧t-检验结果也验证了CGHP算法在寻优精度和稳定性方面的优势。
为进一步说明CGHP算法的收敛性能,图7(a)~图7(d)展示了三种算法在迭代1 000次过程中对于四种测试函数的收敛情况。
从图7可以看出,CGHP算法的收敛性明显优于PSO算法和CSPSO算法,在算法迭代前期,CGHP算法的适应度值迅速减小,收敛速度快于PSO算法和CSPSO算法;在迭代后期,CGHP算法的适应度值维持在极小的水平,算法寻优精度较好。
图7(a)显示30维f1函数的实验结果,CGHP算法在迭代初期适应度值迅速减小,表明算法定位到最优解区域,CGHP算法具有优于其他两种算法的全局搜索性能;在迭代中后期,CGHP算法的适应度值维持在极小的水平,表明算法具有良好的寻优精度,优于PSO算法和CSPSO算法的全局搜索能力和寻优精度,体现PSO算法和云遗传算法协同策略的优势。对于f2函数的优化问题,如图7(b)所示,当传统PSO算法获得的最优粒子为局部最优时,算法将会陷入早熟收敛而难以迅速寻找到全局最优解,而CGHP算法采用并行协同机制,借助动态调整粒子集规模和改进的Metropolis接受准则策略,使算法能够有效地跳出早熟收敛,实现最优解区域的准确定位,在短时间内实现算法的快速收敛。f3和f4函数是典型的用来测试算法全局搜索性能的函数,如图7(c)和图7(d)所示,CGHP算法在开始阶段即能找到全局最优解所在的区域,并且可以有效跳出早熟收敛并找到全局最优解,虽然迭代后期收敛速度放缓,但相对于PSO算法和CSPSO算法仍然具有良好的寻优精度,表明CGHP算法的搜索能力要优于其他两种算法。
5 结论