模糊自适应并行遗传算法在函数优化中的应用
2021-11-22潘家文伏云发
潘家文,钱 谦 ,伏云发,冯 勇
1(昆明理工大学 信息工程与自动化学院,昆明 650500)
2(昆明理工大学 云南省计算机技术应用重点实验室,昆明 650500)
1 引 言
遗传算法(Genetic Algorithm,GA)[1]是20世纪70年代初期由美国Michigan大学Holland提出来的借鉴生物界自然选择思想和自然遗传机制的一种全局随机搜索算法.它把问题的可能解看做个体,多个个体组成种群,算法运行时按照预设的进化策略使种群在遗传算子的控制下通过选择、交叉、变异等运算操作进行寻优,适应度高的个体被遗传继承下来,适应度低的个体不断被淘汰,直到产生最优或近似最优解.GA已广泛应用于机器学习,控制,优化等领域[2-4].
GA以适应度函数作为搜索准则,能够同时搜索多个点,具有较好的并行寻优能力,但是该算法也存在着“早熟”收敛和收敛速度慢等缺陷.目前已经提出了许多解决这一问题的方法,如自适应机制[5]、将遗传算法与其他算法结合[6]等,这些方法都取得了较好的效果.
本文首先结合分析GA算法缺陷产生的原因对已有相关研究的不足之处进行讨论,然后在前人研究基础上提出了更加有效的优化算法.
2 相关研究
交叉概率Pc和变异概率Pm是控制交叉操作、变异操作及影响遗传算法性能与收敛的关键控制参数[7].GA易陷入局部收敛的一个原因就是Pc和Pm的具体数值难以选取.传统遗传算法(Standard GA,简称SGA)的Pc和Pm具有固定的数值,如果取值过高,虽然有利于跳出局部最优,增大找到全局最优的可能性,但是会破坏现有的优良个体,使算法沦为随机搜索算法;如果取值过低,又不容易产生新的个体,容易导致进化停滞不前.SGA对于不同优化问题需要反复实验来确定Pc和Pm,过程异常繁琐且效果有限.为了解决这个问题,多种群并行机制被引入遗传算法中,通过对不同种群配置不同的参数能够有效的控制子种群的独立演化特性.文献[8]将局部搜索与并行机制相结合提出一种改进的混合遗传算法并用于求解课程排班问题.Zhou Yu[9]将改进的多种群并行遗传算法用于列车组调度优化问题.文献[10]采用多种群并行机制混合局部优化算法来加强算法的性能.但是上述方法仍存在一些问题,例如,算法中的单个种群均采用了固定的进化策略,不能根据该种群所处进化状态动态调整进化策略,使得种群中大部分染色体进化效果较差.对于具有较大Pc和Pm数值的种群来说,虽然容易丰富群体多样性,扩大种群的搜索范围,但是其中有希望成为全局最优解的优秀个体的基因容易被破坏,使种群无法保持稳定,难以收敛.对于具有较小Pc和Pm数值的种群来说,虽然能够充分利用现有染色体的基因,但其跳出局部最优解探寻全局最优解的可能性较小,并且也缺少对迁移来的优秀个体进行进一步开发的能力.
GA易陷入“早熟”收敛的另一个原因是群体多样性不足,使得种群的搜索范围被限制,算法只能在有限范围内找到最优值,而不能得到满意的全局最优值.为解决上述问题,需要保证算法在计算过程中种群的多样性不能过快丧失,利用多样性来保证种群的搜索范围.目前已有的GA研究多数采用随机初始化方法产生种群,随机初始化方法会产生多样性差,染色体分布不均匀的种群[11].文献[12]提出半初始化方法,该方法虽然丰富了种群多样性,但也增加了计算复杂度,还影响了种群的稳定性.文献[13]提出在随机产生的染色体集合基础上通过海明距离作为标准约束个体来产生初始种群,但是若一开始随机产生的种群多样性就比较差,那么经过挑选后的种群仍无法避免多样性较差的局面,且无法保证种群能够散布在整个解空间,算法在进化时仍然容易陷入“早熟”收敛.若通过扩大种群规模的方法来解决多样性问题,那么算法收敛速度又会受到极大影响.此外,仅通过改进初始化来提高种群多样性的方法具有局限性,在进化过程中由于遗传操作的作用会使得种群获得的多样性不断丧失,种群在进化中后期的搜索范围仍会被限制.为解决该问题,Cheng R等[14]提出了一种竞技方法淘汰相似度较高的劣质染色体来保持种群的多样性.文献[15]也使用了竞技方法作为一种约束来保证算法进化过程中种群具有丰富的多样性.
作为GA算法最核心的3种遗传操作之一,选择操作是控制群体多样性及收敛能力平衡的关键.目前大多数研究采用比例选择作为选择策略,但采用该策略会产生比较大的抽样误差.算法初期,优良个体的适应度与其他个体的适应度差距较大,按比例选择策略进行选择操作时,优秀个体有更大概率被选入种群并迅速复制使算法陷入“早熟”收敛;而在进化过程中,个体之间的适应度差距不断缩小,优秀个体被选中的概率降低,影响收敛速度.为解决上述缺陷,适应度尺度变换方法被应用到遗传算法中,通过改变个体之间的适应度的相对差异性来控制选择操作的灵敏度,即通过缩放个体适应度在群体适应度区间的所占比例来改变个体被选入下一代的概率,该方法在算法进化前期降低了优秀个体被选择的概率,增加了其他个体被选择的概率,保护了种群的多样性,在一定程度上避免了算法陷入“早熟”收敛的现象;而在算法进化中后期则提高了优秀个体被选择的概率,加强了算法的收敛速度.但是若采用固定数值的尺度变换方法,往往不能取得令人满意的效果,为使适应度的变换在算法的运行过程中更加合理,不少学者对适应度尺度变换的方法做出了改进.文献[16]提出了对适应度进行指数变换来克服选择操作对遗传过程的制约,文献[17]采用线性变换法对适应度进行尺度变换来克服比例选择策略的缺陷.
GA不善于对局部区域进行细致搜索,导致该算法的局部搜索能力较差,影响算法的寻优性能.将局部搜索能力较强的优化算法如单纯形法[18]、模拟退火算法[19]等作为局部搜索策略加入遗传算法中,能够提高算法收敛速度,减少遗传代次,是提高遗传算法运行效率和求解质量的一种有效手段.文献[19]采用模拟退火思想对遗传算法的选择算子进行了改进并提出了新的变异算子用于搜索约束条件下的解空间,这一优化方法虽然一定程度上提升了算法的局部搜索能力,但本质上仍是用遗传操作对染色体进行局部搜索,其搜索仍然不够精细.文献[20]使用模拟退火算法作为遗传算法的局部搜索策略,该方法通过随机扰动个体代表的可能解实现更加细致的搜索.但该方法的不足之处在于,Metropolis准则虽然使算法存在能够探索个体其他方向邻域结构的可能性,但每次只探索某单一方向的邻域结构,若能产生稍好解就会以较大概率接收,对个体所在解空间的探索不够充分.
为设计一种更加高效的遗传算法,本文在前人研究基础上做出改进,提出了一类模糊自适应的并行遗传算法(FAPGA,Fuzzy Adaptive Parallel Genetic Algorithm).具体方法如下:
1)算法框架采用了模糊自适应的并行机制,该机制提升了算法克服Pc和Pm数值难以选取及早熟收敛等问题的能力,能够根据染色体之间的个体差异性及种群进化情况自适应调整进化策略.
2)多样性调整采用基于距离调整的种群初始化方法及竞争策略,初始化方法能够使种群内染色体分布在解空间的不同区域,保证初始解的多样性.竞争策略作为一种约束条件持续调整种群在进化过程中丧失的多样性,使种群在进化过程中能够保持丰富的多样性及设置合理的搜索范围.
3)算法进行选择操作时采用改进的适应度变换方法,该方法使用更加稳定的尺度标准,并能够非线性的控制适应度变换,使变换后的新适应度更贴近算法进化的要求.
4)算法局部搜索采用了基于模拟退火构建的Baldwin learning局部搜索策略,该策略能够充分探索个体所在解空间区域,提升算法的局部搜索能力.
3 算法基本思想
在本节中,首先介绍算法的编码方式,然后说明模糊自适应的并行机制的基本思想,接着对算法的初始化方法及竞争策略进行描述,最后对改进的尺度变换方法及局部搜索策略进行说明.FAPGA以并行机制为算法的基本框架,并将多种改进方法融入算法的不同环节中形成一种新的改进遗传算法.
算法的设计首先要考虑编码方案.遗传算法有不同的编码形式,多数可以总结为二进制码方案(二进制码,格雷码等)和十进制码方案(实数编码、整数编码等).相较十进制编码,二进制编码在相同种群规模下进化时变化更加多元,有更强的探索新解空间的能力.而十进制编码在当前个体所映射定义域中的搜索范围更大,相比较二进制编码能更充分的探索当前解空间.FAPGA采用混合编码方案,即二进制编码和十进制编码混用.具体来说,局部搜索操作使用十进制编码进行,其余操作以二进制码进行.将两种编码混合起来,在不同作用的基因操作中使用不同的码制,能充分发挥不同编码方案的优势,更好的提升算法性能.
3.1 模糊自适应的并行机制
3.1.1 并行机制的基本原理
在遗传算法中引入并行机制(Parallel mechanism)能够有效结合GA的天然并行性和计算机的快速并发性,是近年来提出的改进算法性能的一个重要方向.目前遗传算法并行机制的模型包括4个基本类型:主从式模型(Master-slave Model)、细粒度模型(Fine-grained Model)、粗粒度模型(Coarse-grained Model)、及混合模型(Hybrid Model).
主从式模型并不改变遗传算法的框架结构,而是采用单一种群,所有个体的进化均在主处理器上以遗传操作进行,而将开销较大的适应度评估等计算交付给多个从处理器并行处理,该模型简单且易实现,能够有效减少算法运行时间.
细粒度模型采用某种邻域模型将单一种群划分为多个子种群,并把每个种群交付给不同处理器独立演化,算法运行过程中不同种群之间按照其拓扑结构在边界上进行通信来交换信息.该模型能够有效减少算法运行时间并能够充分发挥遗传算法的并行特性.
本文提出的并行机制采用了粗粒度模型,该机制通过多个种群代替单一种群并行演化来扩大搜索范围,其中每个种群自成一个演化单位按照不同的进化策略独立进化,当算法遗传代次达到一定周期时会进行个体迁移,即各种群之间会交换一定数目的优秀个体.该并行机制对不同种群配置不同的算法参数而有效的控制种群的独立演化特性,保证了种群进化过程中的多样性,并通过迁移来实现各种群之间相互协调,提升了算法的性能.
混合模型是由上述模型混合形成的结构,如粗粒度-细粒度、粗粒度-主从式等模型.采用混合模型的并行遗传算法更具普遍性,但算法也更为复杂,实现代价较高.
3.1.2 并行机制的进化策略
目前已有遗传算法改进可以总结为编码、微观遗传策略(对遗传算子及参数选择的改进)、宏观遗传策略(对算法运行机制的改进).本文研究的是宏观多种群并行机制而并非具体的进化策略,因此并行机制采用文献[21]所提出的较简单的进化策略并做出改进.具体来说,将数值较大的Pm和数值较小的Pc称为探索策略(Exploration strategy),并且在遗传操作上选择先进行变异操作再进行交叉操作,最后执行选择复制操作,该进化策略有利于种群跳出局部最优,探索新的解空间.将数值较小的Pm和数值较大的Pc称为开发策略(Development strategy),该策略首先执行交叉操作再进行变异操作,最后执行选择复制操作,该策略能够重组现有基因产生新的个体以期待获得更好的性状改变.普通策略(Normal strategy)采用介于开发策略和探索策略之间程度的Pc和Pm,在进化操作上采用SGA的选择复制、交叉、变异操作,该策略兼具以上两者的功能.此外,FAPGA使用公共种群作为一个容器不断接收其他种群传递过来的优秀个体并进一步开发.首先,给出进化潜能的定义:
定义1.个体xi通过局部搜索(详见3.4节)展现的进化潜能由公式(1)定义:
Q(xi)=ω(1-Kλ)(f′(xi)-fmax)
(1)
式(1)中,ω表示进化潜能的权重,K表示温度衰减系数,λ表示新解搜索次数,f′(xi)表示染色体xi经局部搜索后的最优解,fmax表示种群适应度最大值.个体的进化潜能与新解搜索次数及最优解的适应度相关,搜索次数越少,进化潜能越大.
公共种群首先对优秀个体进行交叉操作,交叉结束后所有个体按照局部搜索策略进行搜索并计算进化潜能,然后按式(2)更新适应度,最后按照适应度选择种群大小数目的染色体进入下一代.
f(xi)=f(xi)+Q(xi)
(2)
公共种群的目的在于使种群能够探索个体周围的解空间,挖掘具有进化潜能的个体及发现新解.进化潜能大的个体有更大概率被选入下一代,一方面能够丰富群体多样性,维持种群的搜索范围,另一方面与其他优秀个体进行交叉有希望产生更加优良的新个体.
3.1.3 自适应判定策略变换的概率
种群进化过程中若处于停滞或者陷入局部最优解,应当根据种群进化情况更换进化策略,本文引入最优解维持不变的进化代数Gf来衡量种群的进化状态,并以式(3)计算种群更改策略的概率.
(3)
式(3)中,Gt是当前进化代数,G是总进化代数,β是控制参数,在文本中值为6,Gf表示种群停滞的代数,Gmax为最大停滞代数.
图1中实体曲线表示进化代数不变时Pch随停滞代数变换的规律,非线性的概率能够更合理的控制种群变换进化策略.Pch在进化停滞前期缓慢增长,留出一定的时间使种群依靠现有进化策略摆脱停滞.随着停滞代数的增加,算法确定种群陷入停滞状态,相比线性控制的概率,显著提升了Pch,避免种群浪费时间在现有的进化策略上.最后,为保持种群探索与算法收敛速度的平衡,当停滞代数不变时Pch随进化代数的进一步增加呈现线性下降的趋势.
3.1.4 模糊推理进化策略
本文借鉴模糊控制的思想,利用模糊推理根据种群个体的差异性及进化状况调整种群的进化策略.采用式(4)表示种群进化状况.
(4)
fmax-favg的大小常被用来衡量种群的进化程度,该方法确实有效,但不足之处在于,适应度函数是依据具体问题而设计的,其数值随具体问题而变化,并且在算法计算过程中,种群最大适应度与最小适应度也在不断变化,因此很难确定合适的阈值去判断种群的进化程度,而采用式(4)衡量种群进化程度更具普遍性.E1的数值越小,种群平均适应度越接近种群最优适应度,说明种群进化程度较高,反之说明种群进化程度较低.式(5)表示种群个体的差异性.
(5)
E2的值越小,说明种群适应度较分散,此时种群差异度较大,多样性好,反之说明种群多样性差.
式(4)和式(5)中,f(xi)表示个体xi的适应度,fmax是种群适应度最大值,fmin是种群适应度最小值,favg是种群适应度的平均值,N为种群染色体的数目.
模糊变量E1和E2划分为3个语言集合{大,中,小}.进化策略划分为3个语言集合{探索,普通,开发}.表1显示算法根据E1和E2推理进化策略的模糊规则.如果E1为“大”,E2为“小”,说明种群进化程度低且多样性好,进化策略应取“开发”.如果E1为“小”,E2为“大”,说明种群进化程度高且多样性差,进化策略应取“探索”,其他规则可以按上述规律进行类似推理得到.
表1 模糊进化策略规则
交叉算子通过重组开发现有基因来获取优良个体,若群体内所有个体都没有某位基因,通过交叉算子无论如何也无法得到这个缺失的基因.变异算子能够模仿生物界的基因突变产生原先个体内不存在的基因,若种群只产生新基因,不进行进一步的开发探索,种群内优秀个体会不断的被破坏,迟迟无法收敛.当种群陷入停滞状态时,若种群的适应度较为集中,此时种群收敛程度较高,染色体之间比较相似,种群多样性差,需要更换能够产生新基因扩大种群多样性的进化策略.若种群适应度较为分散,种群收敛程度低,染色体之间相似度较低,种群内染色体的基因较为丰富,应以探索当前个体的解空间为主,需要更换能够开发现有基因的进化策略.
3.2 基于距离调整的多种群初始化方法及竞争策略
3.2.1 个体相似度
衡量个体相似度的一种传统方法是海明距离.设xi,xj为两个不同个体,它们之间的距离D(xi,xj)可以定义为:
(6)
由于二进制码中不同基因位对个体的影响不同,即海明距离很小的两个个体在解空间的实际距离可能很大,海明距离不能充分说明个体之间的差异性.加权海明距离可以根据基因位作用的不同,在海明距离基础上为不同位置的基因赋予权重,计算式如式(7)所示:
(7)
wk表示基因位k的权值,在本文中wk=2k.设x1=100101,x2=100000,x3=000100,3个个体之间的海明距离均为2,其加权海明距离分别为Dw(x1,x2)=20+22=5;Dw(x1,x3)=20+25=33;Dw(x2,x3)=22+25=36.可以看出具有相同海明距离的两个个体具有不同的加权海明距离,加权海明距离可以更好的衡量个体之间的差异性.
个体之间的距离由加权海明距离与最大加权海明距离的比值定义:
(8)
式(8)中,l为染色体基因长度.个体相似判定的公式如式(9)所示:
(9)
式(9)中,α表示个体相似的距离阈值,低于该阈值时,算法认为xi与xj具有相似性,否则两者之间并不相似.群体内每个个体都需要与其他个体进行个体相似判定,以此来计算个体相似度r(xi):
(10)
可以看出r(xi)表示个体xi与其他个体的相似累积值,r(xi)数值越大,表示群体内有更多与之相似的个体.若r(xi)大于相似度阈值η,则称个体xi为相似个体.
种群进化过程中,采用固定数值的距离阈值α会影响算法进程.FAPGA采用式(11)随着算法的进程改变距离阈值α.
(11)
式(11)中,α1是最大距离阈值,α2是最小距离阈值,g表示当前进化代数,G表示总进化代数.进化初期α的值较大,调整较多相似个体可以维护种群多样性;随着算法的进行,个体之间的距离也在缩小,个体的相似程度也越来越高,若使用固定数值的α,算法后期会判定更多个体为相似个体,调整更多的个体会减缓算法收敛速度,因此随着进化代数的增加,应不断缩小α的值,避免影响算法收敛速度.
3.2.2 种群初始化
多样性是GA能够搜索到全局最优解的基本条件,有效控制种群的多样性是提高算法性能的一个重要途径.种群在建立时应当具有丰富的多样性,FAPGA首先产生初始种群,群体内每个个体都需要计算个体相似度r(xi),并随机产生新染色体代替相似个体,直到种群内不存在相似个体.
3.2.3 竞争策略
FAPGA通过竞争策略在进化过程中每代结束时调整种群的多样性.首先计算群体内所有个体的个体相似度,将群体内低于种群平均适应度且个体相似度高于相似度阈值η的个体以数值较小的变异概率Pmd进行变异.
小数值的Pmd能减小破坏种群优良性的风险.采用变异的方法来调整相似个体,这是因为竞争策略调整个体时,群体已经进化到一定程度,若采用随机产生新染色体的方法调整相似个体,新染色体往往适应度值比较低,无法与群体内其他个体相比较,会减缓算法收敛速度.而被调整的个体虽然适应度较其他个体低,但也有比较高的进化程度,对该类个体进行调整不但能够摆脱相似性,还能探索新的解空间区域,有几率在当前基础上获得更优解.
3.3 改进的自适应尺度变换
(12)
式(12)中,fmin表示种群适应度最小值,fmax表示种群适应度最大值,T为该文献使用的模拟退火方法的温度,β为衰减系数.式(12)能够根据进化时期修正适应度,避免了算法前期因选择超级个体过多陷入“早熟”收敛.但缺陷在于原适应度使用式(12)变换后,个体之间的新适应度差距变得过小,优良的个体在进化前期被选择的概率降低的幅度过大,影响了寻优能力.随着算法的进行,种群的最小适应度与最大适应度的差距变小,算法后期所进行的适应度变换很难如预期般达到改变个体适应度之间的相对差异而促进算法收敛的效果.
FAPGA通过式(13)进行适应度变换,并以变换后的适应度进行比例选择操作.
f′(xi)=f(xi)+Afavg
(13)
式(13)中,favg表示种群适应度平均值,A是适应度变换的重要参数,计算方式如式(14)所示.
(14)
式(14)中,g表示当前进化代数,G表示总进化代数,a的值为6.
根据前面的分析,式(13)采用种群适应度平均值作为尺度标准可以使适应度变换在算法计算期间更加稳定.文献[17]所提的适应度变换是基于线性的改变,而式(14)可以根据进化时期非线性地控制适应度变换,能够更好地根据算法的运行过程进行尺度变换.算法初期,A的值趋近于1,经过适应度变换后,不同个体之间的新适应度差距比原适应度差距小,降低了超级个体的选择概率,增加了其他个体的选择概率,有利于保持群体多样性.随着算法进行,相比线性控制的选择灵敏度,A的下降趋势较为缓慢,能更好的保持进化前期的群体多样性;进化接近后期时,A更快的接近于0,可以更有效的提升f′(xi)的选择灵敏度,增加优秀个体被选择的概率,促进算法加速收敛.
3.4 基于模拟退火构建的Baldwin learning局部搜索策略
3.4.1 遗传算法与生物进化原理
拉马克进化学说(Lamarckian learning)主张环境条件的改变能引起生物发生适应环境的变异,即生物体通过后天学习获得性状改变,这种改变可以通过基因遗传给后代,即“用进废退”和“获得性遗传”.将Lamarckian learning应用在遗传算法中,如果染色体在“环境”影响下个体的表现型(即适应度值)发生改变,会引起个体基因型变化并遗传到下一代.
鲍德温进化学说(Baldwin learning)主张生物后天通过环境改变自身的性状指导了生物进化的方向,即生物在这种指导下通过自然选择改变自身基因并遗传下去.将Baldwin learning应用到遗传算法中,如果染色体在“环境”影响下个体表现型发生改变,不会直接影响到个体的基因型,而是会作为一种“压力”指导下一代的进化.
3.4.2 局部搜索策略基本原理
本文提出一种新的局部搜索策略来加强算法的局部寻优能力,首先将邻域结构X定义为:
(15)
式(15)中,pi(max),pi(min)分别表示决策变量pi定义域的上下界,u表示决策变量维数(即问题维度),基因长度由l表示,δ为搜索空间的范围系数,θ是控制邻域结构大小的系数.
图2 不同维度邻域结构
个体进行局部搜索时,首先探索其周围邻域结构,并以式(16)代表的Metropolis准则判断邻域结构的接收率.若不存在使当前个体优于全局最优解的邻域结构,每个邻域结构被赋予小于1的接受率,并以比例选择的方法随机选择一个邻域结构产生新解进入下一跳.若发现使当前个体优于全局最优解的邻域结构,赋予该邻域结构大于1的接收率.若存在多个使当前个体优于全局最优解的邻域结构,选择接受率最大的邻域结构产生新解进入下一跳.每一跳的邻域结构被确定后产生新解代替当前解时,只有个体的表现型发生变化,而不改变个体的基因型.当个体通过局部搜索发现优于全局最优解的解时,认定该个体具有进化潜能(详见3.1.2节定义1).进化潜能越大,说明个体通过进化搜索到全局最优的概率也就越大,调整具有进化潜能个体的适应度,使其有更大几率进入下一代.
基于模拟退火构建的Baldwin learning局部搜索策略流程如下:
1)初始化策略参数:搜索空间系数δ,决策变量数目u,Markov链长度m=(2δ)u,初始温度T,温度衰减系数K,温度衰减次数k,新解搜索次数λ,B={n1,n2,…,nm}代表邻域结构的集合,f(xi)为染色体xi的初始适应度,局部搜索最优值f′(xi)=fmax,fmax是全局最优适应度.
2)对染色体xi采用邻域结构nj进行局部搜索,按式(16)改进的Metropolis准则计算nj被选中的概率:
(16)
3)若j 4)若存在p(nj)>1,转5),否则转6). 7)若满足终止条件,转8).否则转2). 8)局部搜索结束,输出f′(xi). 如图3所示,圆状实体代表个体,虚线矩阵表示解空间内的邻域结构,箭头表示搜索方向,其序号表示当前搜索次数,图3(a)表示个体通过第1次搜索能够搜索到的邻域结构,图3(b)表示通过第2次搜索理论上能够搜索到的邻域结构.上述策略使个体可以探索多个方向邻域结构,邻域结构的范围可以通过式(15)调整,从而建立起搜索范围与强度均可控的局部搜索策略.局部搜索的目的是充分探索个体所在解空间,只有探索到比全局最优解更加优良的个体才有意义,因此以大于1的接收率采用搜索到更加优良解的邻域结构.若当前温度未搜索到比全局最优解更优良的解,采用比例选择的方法随机选择一个邻域结构产生新解,这种随机方法能够充分利用邻域结构的有效信息进行深度探索,避免了盲目的随机性.已有研究[10,20]多采用以拉马克进化理论为基础的局部搜索策略.其中文献[10]采用爬山法作为算法的局部搜索策略进行细致搜索,文献[20]在遗传算法中加入模拟退火随机扰动决策变量进行局部搜索.以上方法虽然增强了算法的局部寻优能力,但是无法对新个体是否为局部最优解进行有效区分,即个体通过局部搜索发现更优良的表现型就改变原个体的基因型并进入下一代,使得种群更容易陷入局部收敛.而本文提出的局部搜索策略是以鲍德温进化理论为基础,个体通过局部搜索发现了新的最优解的同时,并不改变原个体的基因型,而是一方面记录该最优解,另一方面以该最优解计算个体的进化潜能(即式(1))并作为一种“选择压力”指导个体的进化.通过这样的方式不但达到搜索新最优解的目的,还减少了种群陷入局部最优的风险. 图3 个体理论搜索区域 算法流程如图4所示. 图4 FAPGA算法流程图 步骤1.初始化参数.种群数量M,染色体数量N,染色体长度l,邻域结构范围系数δ,邻域结构大小系数θ,决策变量维数u,初始温度T,温度衰减系数K,最大停滞代数Gmax,按3.2.2小节初始化种群并随机赋予进化策略. 步骤2.计算各种群每个个体的适应度,按照式(13)进行适应度变换. 步骤3.按照式(3)计算各种群更换策略的概率.根据E1与E2按表1中的规则进行模糊推理产生进化策略. 步骤4.各种群按进化策略独立演算进行遗传操作,共享种群内的优秀个体,公共种群首先对个体进行交叉操作,然后按3.4小节的方法进行局部搜索,拥有进化潜能的个体及时修正适应度. 步骤5.判断终止准则,若满足条件,转步骤7,否则转步骤6. 步骤6.种群通过竞争策略进行约束,转步骤2. 步骤7.输出最优解,算法结束. 为验证FAPGA算法的性能,将本文提出的FAPGA与标准并行遗传算法(SMGA)和近年新提出的HGA算法[10]进行对比,以验证算法各方面性能.其中以SMGA主要验证FAPGA所改进的并行机制的性能.HGA将并行遗传算法与局部搜索策略混合增强了并行遗传算法的局部搜索能力,具有较好的局部搜索能力,以该算法主要验证FAPGA改进的局部搜索策略的有效性;3种算法共同对比来验证FAPGA的整体性能. 仿真实验选取3个指标评价算法的性能:1)平均最优解(Average Optimum Solution,AOS),该指标是算法多次运行的最优适应度的均值,反映求解质量的好坏.2)收敛代数平均值(Average Optimum Iteration,AOI),该指标用于评价算法的收敛速度及寻优能力.3)收敛次数/收敛率(Convergence times/Convergence rate,CT/CR),该指标是函数收敛次数及函数收敛次数占实验总执行次数的百分比.其中,收敛成功是指函数求解结果满足于指定的收敛精度(收敛精度设置见表3).收敛精度应综合考量函数维度及不同算法之间的性能来设定,以便更好的区分算法之间的优劣. 将上述3种算法对表2给出的12个标准测试函数进行仿真实验,表2同时给出了测试函数的取值范围及理论最优解,其中D是变量的维数(具体数值见表3).f1-f6为多峰函数,用于测试算法勘探和挖掘信息的能力及摆脱局部收敛的能力,f7-f12为高维函数,用于测试算法并行搜索能力及收敛能力. 表2 测试函数 在算法参数设置上,SMGA、HGA、FAPGA均采用相同的进化策略.SMGA与HGA采用二进制编码,FAPGA采用混合编码(详见第2节).种群数目M为4,种群规模N为50,染色体长度为u×20,u为问题维度,算法执行代数均为400代.3种算法均采用比例选择操作、双点交叉操作及多点变异操作,进化策略遵循2.1.2小节,具体参数为pc1=0.7,pm1=0.1,pc2=0.5,pm2=0.3,pc3=0.85,pm3=0.05.在FAPGA中,δ=3,θ=105,T=100,K=0.9,Gmax=15,η=N/5.所有仿真实验均在windows10计算机操作系统,MATLAB2018b仿真平台下进行,每种算法运行30次. 表3表示3种算法对表2给出的12个标准测试函数各执行30次的优化结果对比.在收敛次数及收敛率上,FAPGA相比SMGA、HGA有更高的CT/CR值,其中FAPGA对f1和f2求解的收敛次数与实验总执行次数一致,在求解高维函数时,收敛率比其他两个算法都要高,说明FAPGA有更好的收敛能力和寻优能力.在求解f3时,HGA虽然收敛次数少,但是该算法收敛时的平均代数也比较少,这是由于HGA在拉马克进化理论的基础上融入了局部优化方法加强了算法的局部寻优能力,但该算法通过局部搜索到新的最优值同时也改变了原有个体的基因,使得算法陷入局部最优的几率增加.从平均最优解的对比来看,FAPGA在整体上都要好于SMGA和HGA,尤其是在f4和f7两个函数最为明显,说明FAPGA的求解质量和稳定性较好.此外,f4中全局最优值附近存在多个局部最优值,算法在求解函数时极易陷入局部最优值,因此该函数可以较好的测试算法的跳出局部最优值的能力,从表3的优化结果可以看出,FAPGA在求解该函数时收敛次数较高,因此算法有较好的跳出局部最优的能力. 表3 函数测试实验结果 从收敛代数平均值可以看出FAPGA的AOI值远小于其他两个算法,说明该算法有较快的收敛速度.这是由于算法采用模糊自适应的并行机制和适应度变换方法,前者使种群能够根据自己的情况及时更换进化策略,与竞争策略共同保证了群体的多样性.而后者通过对适应度进行变换减小了算法前期“超级个体”被选入下一代的概率,降低了种群陷入“早熟”收敛的风险;在算法中后期又加强了优秀个体的选取概率,促进了算法的收敛,两者共同作用使得FAPGA有较好的全局搜索能力和收敛能力.此外,各种群每代都与公共种群进行迁移,公共种群对迁移过来的个体进行二次开发和局部搜索,加强了算法的局部搜索能力.由于公共种群的存在,使其他种群不必考虑群体内优秀个体被破坏的风险而能够不断的勘探解空间,通过这样的方式,各种群之间互相协作使得算法在很少遗传代数内就能收敛. 为直观展现算法的寻优能力,图5描绘了某次实验中3种算法在求解函数f1-f12时每代最优值的比较.其中横轴表示算法的迭代次数,纵轴表示目标函数值.由图5中的(a)、(c)和(g)可以看出,相比较SMGA与HGA,FAPGA在计算初期有更好的解,这是由于种群初始化时对种群进行调整,改善了群体的多样性,使个体在解空间内比较分散,避免了随机初始化方法会导致个体聚集在解空间局部一侧的情况.由图5中的(i)和(j)可以看出,算法前期,HGA的收敛能力要好于SMGA,但是如果该算法前中期算法未能收敛,则该算法后期的收敛曲线一般呈持平状态,这是因为该算法融入局部优化方法,虽然使算法的寻优能力加强,但也使得该算法更易陷入局部收敛.相反,SMGA虽然前期收敛能力较差,但算法中后期总能摆脱局部收敛,这是用于该算法使用不同的进化策略,使种群能够不断探索新的区域.从图5的整体来看,在较少的迭代次数内,FAPGA所代表的收敛曲线在多数函数求解的图像内出现了“陡峭”的趋势,说明算法具有更好的寻优能力和收敛能力. 图5 算法寻优曲线对比图 针对遗传算法存在的优缺点,本文秉承扬长弃短的思想,首先分析GA算法缺陷产生的原因,并讨论了已有研究的不足之处,在前人研究的基础上提出了改进的多种群并行机制、适应度变换方法、种群初始化方法、竞争策略及局部搜索方法.将上述改进方法作用于遗传算法的不同环节形成一种新的改进遗传算法.最后,函数优化实验表明,FAPGA算法能够较好的平衡算法的收敛速度和群体多样性,在优化多峰及高维函数方面具有良好的性能.3.5 算法流程
4 仿真实验
4.1 测试函数及对比算法
4.2 仿真实验结果分析
5 结 论