多策略并行遗传算法（精选六篇）
多策略并行遗传算法 篇1
在电网规模不断扩大、网间联系越来越紧密的背景下,限流措施优化配置具有非常重要的理论意义和应用价值。目前用于限制输电系统短路电流的成熟措施主要有:电网结构分层分区、母线分裂运行、电磁解环、加装限流电抗器、采用高阻抗变压器等[1,2,3,4]。文献[3,5]引入优化理论,将限流措施配置归纳为一个混合整数规划问题,使得应用各类成熟的人工智能算法解决该问题成为可能。然而,限流措施优化配置是一个大规模的非连续、非凸、非线性的优化问题,尤其当考虑潮流约束时,模型更加复杂,传统的数学方法难以求解。文献[5]采用不完全枚举法结合改进离散粒子群算法求解,较为有效、可行。现有限流措施优化模型和算法存在以下3个主要缺陷。
1)局限于单目标优化模型。文献[3,5-6]将成本作为唯一的目标函数,短路电流和潮流作为优化的约束条件。实际的限流设备配置是多种因素妥协的结果。有时为了保证经济性,可允许部分节点短路电流适当超标,即系统安全性约束是适度弹性而非绝对硬性的。多目标权衡模型更加适合限流措施优化。
2)未考虑暂态稳定因素。短路对电力系统造成的危害主要有2个方面:①短路电流超过断路器开断能力,使保护装置无法动作;②使系统失去暂态稳定性。因而,短路故障后系统的暂态稳定性是限流措施优化需考虑的因素之一,而目前的模型只着眼于限制电流大小,没有涉及暂态稳定。
3)将粒子群优化(PSO)算法和遗传算法(GA)用于限流措施配置。PSO算法和GA都只能处理单个优化目标,PSO算法容易陷入局部最优;GA需二进制编码,寻优速度较慢[3,5]。
为解决上述问题,本文提出综合考虑安全、稳定、经济因素的限流措施多目标优化模型。模型以限流设备总投资成本最小、预想故障后系统功角稳定性最佳、所考察节点的短路电流综合越限最小为优化目标,在潮流约束下,寻找综合最优的限流措施组合。多目标优化的核心是协调各目标函数之间的关系,找出使各目标函数都能尽量达到最优的解。本文采用目前优化效果最好的非支配排序遗传算法(non-dominated sorting genetic algorithm,NSGA)-Ⅱ用于搜寻Pareto解集。NSGA由Srinivas等人于20世纪90年代初提出[7]。Deb于2002年在NSGA的基础上进行了改进,提出了NSGA-Ⅱ[8]。
为了进一步提升NSGA-Ⅱ的优化速度,本文在MATLAB计算平台上实现了主从并行结构的非支配排序遗传算法(parallel non-dominated sorting genetic algorithm,PNSGA)-Ⅱ。结合算例分析表明,PNSGA-Ⅱ具有较强的全局优化能力和收敛稳定性,且计算速度有很大提升。
1 限流措施多目标优化模型
限流措施多目标优化的决策变量包括2部分:一部分为表示限流措施是否投入的控制变量u,包括控制线路是否开断(母线是否分裂运行)、是否采用限流电抗器或高阻抗变压器;另一部分为表示限流设备具体参数的变量w,包括所采用的电抗器的电抗大小和高阻抗变压器的短路电压百分比增量。
目标函数f1衡量限流措施的经济性,具体定义为投入的限流设备的总成本:
式中:Γ为所有限流措施的集合;控制变量us∈{0,1},取1表示采用措施s,取0表示不采用措施s;k1s,k2s分别为措施s的固定和可变成本系数;ws表示电抗器的阻抗或变压器短路电压百分比增量,本文认为线路开断不会产生显著成本。
目标函数f2衡量系统安全性因素,具体定义为所有节点的短路电流越限惩罚量之和:
式中:Ui为节点i的电压;Zii为节点i的自阻抗;Īi为节点i允许的电流上限;λ1为电流越限惩罚系数,本文取100;Ψ为节点短路电流越限惩罚量的Ψ算子。
Ψ具体执行策略为:
目标函数f3衡量暂态稳定性因素,具体定义为预想故障集发生后,在考察时间范围内所有时刻,机组相对于系统惯性中心的振幅越限的惩罚量之和:
式中:Ξ为预想的故障集合;Ψ算子策略同式(3);本文采用差分方程表示机组的运动特性,δi(t)表示时刻t机组i的功角;t遍历所有时刻,即:t∈{Δt,2Δt,…,nΔt};λ2为功角越限惩罚系数,本文取100;珘δ为功角最大允许振幅,若某机组相对惯性中心的振幅超过该值,则认为该机组与系统失去同步,珘δ一般取1.74rad[9,10];δCOI(t)表示系统在时刻t的惯性中心,可由各机组的功角加权得到[9,10,11],
式中:Tj为机组j的惯性时间常数;m为机组总数。
限流措施优化需满足的等式约束如下:
式中:Pmi为机组i的原动机机械功率;Pei为机组i的电磁功率;ωs为机组的同步角速度,即额定转速;式(6)和式(7)表示潮流平衡方程;式(8)和式(9)表示转子运动方程。
为简化分析,本文在简单模型下进行暂态仿真[9,12],发电机采用Eq′恒定模型;负荷采用阻抗恒定模型;网络方程用直接法求解;微分方程差分化之后采用改进欧拉法迭代计算[12]。
限流措施优化需满足的不等式约束如下:
式中:Uimax,Uimin分别为电压Ui的上、下限;Flmax为支路l的有功潮流Fl的上限;式(10)为节点电压约束;式(11)为支路潮流约束;式(12)和式(13)为决策变量取值范围约束。
2 优化算法
2.1 支路筛选策略
可以通过分析线路上采取限流措施后节点的自阻抗变化量来衡量该线路采取该措施的有效性,从而筛选出效果好的支路作为优化对象。根据文献[6],在线路l上采用支路开断和阻抗装置对节点b的限流效果灵敏度αbl和βbl分别为:
式中:i和j为线路l两端的节点;zl0为线路l的初始阻抗;k为线路l是变压器支路时变压器的变比(标准变比在i侧,对普通线路,k=1);Zii和Zjj分别为节点i和j的自阻抗;Zij,Zji分别为节点i与j和节点j与i的互阻抗;Zbi,Zbj分别为节点b与i和节点b与j的互阻抗。
灵敏度αbl和βbl越大,表示线路l采用相应限流措施对节点b的限流效果越好。实际选择开断的线路和安装限流装置的线路时考虑的是对所有节点的综合限流效果,因此定义线路l的综合开断指标和综合限流装置指标αl和βl为:
式中:Zbmin为节点b满足短路电流约束的最小节点自阻抗;Zbb为节点b的自阻抗;Ω为所有短路电流越限节点的集合。
在同一条线路l上,在限流装置和支路开断这两种措施之间如何选择是一个复杂的问题。文献[6]指出,对于同一条线路,支路开断的限流效果优于串联限流器,应优先考虑。但是每开断一回线路,会造成电网的阻抗矩阵发生较大变化,αl也相应改变,找出最优的支路开断组合需繁琐的计算。由于支路开断相当于该支路的阻抗无穷大,βl在一定程度上可反映支路开断的效果,本文根据βl的大小筛选限流效果好的支路进行综合优化。
2.2 染色体编码
本文根据βl的大小选择M1条普通支路和M2条变压器支路作为优化对象。对两种限流措施进行混合编码,通过NSGA-Ⅱ求解Pareto最优方案。粒子前M1位的范围为{0,ωimin}~{ωimax,ωimax+1},整数值ωimax+1表示支路i(1≤i≤M1)开断,0表示支路i不采用任何限流措施,ωimin~ωimax之间的任意整数表示支路i上串联的电抗器的电抗值;后M2位范围为{0,ωjmin~ωjmax},0表示支路j(1≤j≤M2)不采用高阻抗变压器;ωjmin~ωjmax之间的任意整数表示支路j上采用的高阻抗变压器短路电压百分比增量。
2.3 NSGA-Ⅱ算法
本文采用支路筛选策略与NSGA-Ⅱ相结合的优化算法,算法流程如图1所示。
以下简要叙述NSGA-Ⅱ算法的计算原理。首先,随机生成种群P0,规模为N。对种群进行非支配排序,通过双支联赛选择、交叉和变异,生成子代种群Q0。然后进入NSGA-Ⅱ算法的主循环,主要步骤如下[13]。
1)将父代种群Pt和子代种群Qt结合成种群Rt,Rt=Pt∪Qt。对Rt进行非支配分层确定Rt的非支配解前沿面F=(F1,F2,…)。
2)建立新种群Pt+1=Ø,设置指针i=1。计算Fi的拥挤距离,执行Pt+1=Pt+1∪Fi和i=i+1,直至‖Pt+1‖+‖Fi‖>N。‖·‖表示对应集合中元素的个数。
3)对Fi进行排序(Fi,n)。选择Fi中排序最好的N-‖Pt+1‖个解加入Pt+1,即Pt+1=Pt+1∪Fi{1:(N-‖Pi+1‖)},其中{1:(N-‖Pt+1‖)}表示范围为1~(N-‖Pt+1‖)。
4)对种群Pt+1,应用选择、交叉和变异算子得到子代种群Qt+1。
步骤1中Rt=Pt∪Qt保证了精英策略的实行,即上一代优秀个体有机会直接遗传到下一代。步骤3中应用拥挤对比算子对Fi进行排序,使得种群的演化向Pareto前沿面稳定进行并且保持种群多样性。的具体执行过程[8,14]如下。
即层级irank较低的个体具有选择优先度,对于同一层的个体,其选择优先顺序是基于拥挤度idistance。拥挤度通过以下方式定义:设该层有个体n个,层边缘上的个体给定一个大数作为拥挤度:dl=dn=∞。其他个体的拥挤度通过下式计算[14]:
式中:fm(i)为个体i的第m个目标函数值;fmmax,fmmin分别为该目标函数的上、下限。
子代C1和C2的每一位都由父代P1和P2通过模拟二进制交叉(SBX)算子交叉得到[15]:
多项式变异(PM)算子用于变异操作[16],子代C3的每一位都通过下式由父代P3变异得到:
式(21)和式(23)中,u(j)和r(j)为[0,1]之间均匀分布的随机数;ηn和ηm分别为交叉分布指数和变异分布指数,本文取ηn=ηm=20;交叉率为0.9;变异率为0.2。
在进化过程中,对于不满足式(10)、式(11)约束条件的解,可将其3个目标函数都置为大数,使其在排序和选择时被自动遗弃。在随机生成初始种群以及染色体的交叉变异过程中,也不可避免会产生部分无效解,如孤立节点或潮流不收敛的解,对于无效解,也可采取相同的处理方法。
2.4 主从并行结构的PNSGA-Ⅱ
优化过程中,约束条件的校验需要实时潮流数据,暂态过程仿真需要进行大量的数值积分,这使限流措施优化成为数据密集型问题。
本文采用易于实现的主从并行结构,将复杂的潮流计算和暂态仿真分配给各个子进程(lab),可以大大缩短计算时间。在主从拓扑结构中,令进程1为主进程,负责控制整个计算过程,包括网络拓扑信息的读取以及粒子的排序、选择、交叉、变异等。进程2至进程8为从进程,负责潮流和短路计算以及暂态过程仿真,进而向主进程提供各染色体的目标函数值,并行策略如图2所示。
3 算例分析
3.1 参数设置
采用改进的新英格兰10机39节点系统作为算例,算例参数详见附录A。断路器的最大开断电流为70(标幺值),则母线2,16和39三相短路电流越限,设定如下发生在超标母线端的预想故障集。故障1:0s时,线路1-39近母线39侧发生三相接地,0.23s时切除线路1-39。故障2:0s时,线路1-2近母线2侧发生三相接地,0.20s时切除线路1-2。故障3:0s时,线路17-16近母线16侧发生三相接地,0.12s时切除线路17-16。
为保证故障线路可正常切除,要求母线2,16,39短路电流不超过70(标幺值),且故障后系统尽量保持暂态稳定。考查的暂态过程T=40s,步长Δt=0.01s。
算法根据灵敏度βbl选择6回普通支路和3回变压器支路作为综合优化的对象,即M1=6,M2=3。设定节点电压上限1.20,下限0.95;支路潮流上限950MVA。限流电抗器的阻抗为0~30Ω,高阻抗变压器的短路电压百分比增量为0~10%,电抗器成本系数k1s=750,k2s=30,其他系数见文献[3]。
3.2 Pareto最优解集
记种群规模为m,最大进化n代的PNSGA-Ⅱ优化为(m,n),图3给出了(60,50)的第1代和第50代种群的分布。
由图3可见,种群在进化过程中空间集聚效果较为明显,形成非支配前沿。运行5次,种群空间分布都大致相同,这说明算法有很强的全局优化能力和收敛稳定性。第50代种群中,劣解已全部淘汰,全部个体都满足Pareto最优,其中处于非支配层边缘(目标函数最大或最小)的所有Pareto解如表1所示。
由表1可见,本优化问题3个目标函数是互相矛盾的。以第1、第3组解为例,解1对应的系统最大短路电流仍然越限(82(标幺值)),但在故障3发生后系统是暂态稳定的,各机组功角曲线见图4(a);解3对应的最大短路电流为69(标幺值),全部达标,但故障3发生后系统是不稳定的,各机组功角曲线见图4(b)。
之所以不存在f1,f2,f3同时最小的全局最优解,是由限流措施的特性决定的。例如:在所有措施中,支路开断具有最佳限流效果(ΔX=∞),且具有最低的成本(k1s=0.1,k2s=0),从经济性和安全性角度,应选择更多地开断支路,但是开断支路会减弱机组间的联系,对系统暂态稳定性破坏是相对最大的。
文献[5-6]的单目标优化方法只能得到f2=0的解。而本文方法可提供大容量的Pareto解集供决策者根据实际要求从中选择。例如:若要求短路电流不越限,可选择表1中第3、第4、第5组解。若要求暂态稳定性最佳,可选择第1组解。若要求各目标函数最均衡,则可选择最接近无偏最优的方案(非支配层中心)。这种优化方法避免了加权求解的盲目性,提供给决策者较大的选择弹性,且当需求变化时只需重新从解集中选择,而不必重复寻优计算。
3.3 种群规模和世代数对优化结果的影响
下文通过算子判断(m,n)的全局优化效果,而定向优化效果可通过某个目标函数接近其优化目标的程度来衡量。优化过程中成本f1的最小值不确定,而f2和f3为惩罚函数,只要优化对象可被限制在罚值内(本算例可实现),f2和f3的目标值就是0。另一方面,实际运行结果表明:当m,n较小时也容易得到f2=0的解,m和n对f2的影响并不显著。因此,以f3出现的最小值f3min作为衡量定向优化效果的指标。在此基础上,进行如下操作。
对于每一个m∈{10,20,30,40,50,60,70},随机运行5次(m,60),统计5个Pareto解集中f3min的平均值,记为f3min(m,60);对于每一个n∈{10,20,30,40,50,60,70},随机运行5次(60,n),统计5个Pareto解集中f3min的平均值,记为f3min(60,n)。图5给出了f3min的变化曲线。可见,随着m,n增大,f3min逐渐减小,当m,n增大至一定值时,f3min不再变化,例如,当m增至60时,f3min(m,60)接近0且不再变化。
将全部Pareto解集混合得到规模为N的集合P1,对P1进行非支配分层,同层个体计算拥挤度,采用算子取出容量为0.5 N的子集P2。统计得到图6所示的(60,n)和(m,60)所属的解在P2中所占比例r(60,n)和r(m,60)。显然,r(m,n)越大,对应(m,n)的全局优化效果越佳。由图6可见:r(m,n)随m,n增加而显著增大,但增大速度逐渐变缓,例如:r(60,50),r(60,60),r(60,70),r(70,60)几乎相等。
由以上分析可见,m,n对(m,n)的定向和全局优化效果都有直接影响,但影响的幅度随m,n增大而减小。从兼顾运算速度和优化效果的角度出发,取m=60,n=50较为合理。
3.4 并行加速性能分析
选择2台不同配置的计算机PC1和PC2进行并行加速性能对比实验。PC1为具有一对Intel Core2Duo E7200 2.53 GHz CPU和2 GB DDR2内存的双核计算机;PC2为具有一对Intel Xeon2.33GHz四核CPU和12GB DDR3内存的八核计算机。
并行环境为MATLAB r2009a,该环境在单机调试中最多提供8个进程同时执行计算任务。定义加速比Sn和并行效率En[17]为:
式中:t1为程序在单个进程上串行运行的时间;tn为同一程序在n个进程上并行运行的时间。
在PC1和PC2上分别运行(60,50),Sn和En如表2所示。
由表2可见,(60,50)加速比始终大于1,即并行算法运算速度明显优于串行。通过比较PC1与PC2的加速比,可以看出PNSGA-Ⅱ算法并行性能的发挥需要计算机硬件的支持。在硬件配置较低时,各进程之间争抢计算资源,造成部分进程处于闲置和等待(idle)状态,进程的平均计算效率下降,故PC1的并行效率随着进程增加而显著减小。当计算机硬件满足要求时,并行化有利于充分利用每个核的计算能力,减少闲置和等待,故PC2的并行效率出现短暂上升。本文的PNSGA-Ⅱ为主从结构,主从进程之间无法完全做到完全均衡与同步,不可避免会发生相互等待,这也制约了算法并行性能的进一步提高。
4 结语
基于小种群策略的并行遗传算法 篇2
遗传算法最早是由Michigan大学的J·Holland教授于1975年提出的一种基于生物进化机制的自适应算法, 适用于各类复杂系统的优化计算。遗传算法本身具有很多优点, 如简单易行、通用性强、鲁棒性高、全局搜索能力强等, 这些优点使其可以应用于大量复杂问题求解当中。然而遗传算法固有的一些缺陷如:过早收敛、容易陷入局部最优、算法运行后期搜索效率较低等, 也不可避免地制约了遗传算法的使用与推广。
对于全局范围的搜索算法而言, 早熟现象的产生是其失败的主要原因。种群的规模在很大程度上决定遗传算法应用的成功与否。种群数目过小会导致算法收敛速度过快, 往往来不及找到全局最优解;种群数目过大会消耗过多的进化和处理时间, 使得算法运行异常缓慢。
为了更好地使用遗传算法处理实际问题, 长期以来人们在标准遗传算法 (SGA) 的基础上做了大量的研究和尝试, 并且取得了巨大的成效。其改进方法包括对遗传算子的改进、增强算法的自适应性、与其它智能算法搭配使用等, 然而很多改进方法却使得算法变得较为复杂, 从而失去了遗传算法简单易用的特点。本文在此提出一种新的基于小种群并行的改进型遗传算法:一方面针对实际应用中的一些问题对标准遗传算法的遗传算子加以改进, 另一方面提出在个体总量相同的条件下, 采用多个小种群并行运算, 并在各种群间产生交互的方法, 确保在尽可能保持计算简单性的前提下, 防止遗传算法中早熟现象的产生。
1 遗传算子的改进
交叉算子是遗传算子中最为重要的组成部分, 其不仅对遗传算子的收敛性起到了至关重要的作用, 同时也对遗传算法的收敛速度有很大的影响。传统交叉算子的操作往往具有一定的盲目性, 亲代染色体交叉互换后所形成的子代很可能将亲代个体中所具备的优良基因模式丢弃或者破坏了。本文提出一种改进的交叉算子方案, 以便以较大的可能性保护亲代个体的优秀基因模式并使之得以传递至子代个体。
在此使用相似程度的概念, 通过相似程度的高低来决定是否进行交叉操作。首先给出相似度的定义, 假设有两个二进制编码的父代个体, 分别记作个体X和个体Y, 则此二者的相似程度定义如下:
定义1相似程度:
ε=a/n (1)
其中ε表示个体X和个体Y的相似程度, a表示两个体之间最大相同位串的数目, n表示个体染色体编码的长度。举例来说, 例如个体X的染色体编码为1010110010, 个体Y的染色体编码为1000101001, 则二者的最大相同位串数目a为5, 而个体染色体编码长度n为10, 则个体X与个体Y的相似程度ε为5/10, 即0.5 。显然, 同一种群中任意两个个体的相似程度为一个处于两者之间的数。
为了判别是否进行交叉操作, 需要用到一个临界值作为参照对象, 在此本文给出另一个概念标准交叉点定义2:
其中K为标准交叉点的值, G表示此种群预先设定的总进化代数, g表示算法到目前为止已运行的代数。由上述公式显然可知, 标准交叉点K的值是动态变化的, 其值随着当前种群进化代数的增长而不断增大, 而预先设定的总进化代数对标准交叉点K的变化也有较大影响。当被选中参与交叉运算的两个个体的相似程度ε小于或等于K值时, 则进行染色体的交叉互换操作;而当相似程度ε大于K的值时, 则不允许二者进行交叉互换操作, 而是克隆本身, 复制产生与二者完全相同的子代个体。在遗传算法运行的初期, 随即生成的种群个体之间的相似程度较低, 为了控制交叉率, 以便在确保种群得到充分进化的前提下尽量不破坏个体中的优秀基因模式, 标准交叉点的值K应当相对较小, 反之在遗传算法运行的后期, 种群进化了多代, 此时个体间差异已经较小, 相似程度较高, 故而标准交叉点的值K也应当随之提高。根据上述公式, 动态控制父代染色体标准交叉点的移动, 有助于提高遗传算法的收敛性能和收敛速度。为了简便以及更好地评价本文提出的改进方法, 当一组亲代个体的染色体通过标准交叉点的比较判断后, 本文使用传统的单点交叉方法来对它们进行交叉互换操作。
2 基于小种群并行的算法方案
种群的规模是决定遗传算法能否成功使用的一个重要原因, 显然无论种群的规模过大或是过小, 均不可能令算法最终得到一个令人满意的全局最优解。种群规模过小会导致所得到解的准确性和可信性难以得到保证, 而种群规模过大则会使得遗传算法的收敛速度过低, 且在运行代数不足的前提下仍然不能确保得到准确的全局最优解, 这更加降低了遗传算法的运行效率, 据此, 本文提出一种基于小种群并行的改进型遗传算法。区别于传统的遗传算法, 新方案将在初始化的过程中同时建立多个个体数量完全相同而染色体编码彼此之间完全不同的相对规模较小的种群, 以此实现在不影响算法运行总体效率的前提下, 提高算法的全局搜索能力。算法流程描述如下:
(1) 依据实际问题的需要建立一个由n个种群组成的集合, 每个种群中包含由染色体编码组成完全不同的m个个体。
(2) 根据上文中已经给出的对于遗传算子的改进方案, 在每个小规模的种群内部进行一次独立的遗传运算。即从种群1开始, 每个种群均进行一次使用上文中改进遗传算子的遗传运算过程, 得到下一代种群个体, 直到n个种群均完成了上述运算。
(3) 对种群中各个个体的相对适应度进行计算, 并选择出每个种群中相对适应度最高的个体, 得到的n个个体按照来源的种群编号为1至n, 称为优秀个体。
(4) 使用得到的每一个优秀个体与剩余的所有优秀个体分别进行杂交, 即杂交 (n-1) 次。对n个优秀个体分别进行此项杂交操作, 根据下文中的杂交规则, 在杂交完成后即产生新一代的种群。
(5) 判断算法此时的运行结果是否满足终止条件, 如满足则终止算法, 如不满足则转向步骤 (2) 。
关于上述算法, 说明如下:
(1) 步骤 (1) 中初始化的方式可以为先随机生成m*n个完全不同的个体, 然后再随机将它们分配进入n个种群当中, 每个种群分配m个个体即可。分配完成后, 此n个种群随机编号为从1至n号, 并记为种群1至种群n, 此时种群内的个体即为第一代个体。
(2) 步骤 (4) 中的杂交规则举例说明如下:编号1的优秀个体与编号2至n的优秀个体分别杂交, 当其与优秀个体2进行杂交时, 得到两个新的子代个体, 此时计算两个新个体与优秀个体1和优秀个体2的相似程度。其中与优秀个体1相似程度高的子代个体记为个体1 (2) , 与优秀个体2相似程度高的子代个体记为个体2 (1) 。如果两个子代个体均与某一优秀个体的相似程度高或与两个优秀个体的相似程度相同, 则随机将子代个体中的某一个记作1 (2) , 另一个记作2 (1) 。以上面方法依次进行杂交, 则可分别得到新的子代个体1 (2) 至1 (n) 。同理, 在经过相互间的杂交后, 还可以得到新的子代个体2 (1) 、2 (3) …2 (n) 直至n (1) …n (n-1) 。计算个体1 (2) 至1 (n) 的相对适应程度, 在得到的结果中选择相对适应度最大的一个子代, 并将其作为新的优秀个体1, 并根据上述方法逐步得到新的优秀个体2至优秀个体n。最后, 将此时得到的新优秀个体1至n根据编号带入相应的下一代种群1至n, 从而得到新的下一代种群。
(3) 由于新算法中选取的每个小种群中的个体数量较少, 故而算法的全局搜索能力由优秀个体之间的杂交来保证, 而收敛速度和收敛性能则主要由算法中针对遗传算子的改进来保证。
3 算法测试
为了验证新算法的性能, 本文将选用两个常见的优化函数对其进行测试, 并使用标准遗传算法与之同时测试以作参照。
测试函数1:
maxf1 (x1, x2) =100 (xundefined-xundefined) 2+ (1-x1) 2, -2.048≤xi≤2.048 (i=1, 2) ;f1有2个局部最大点, 即f1 (2.048, -2.048) =389 7.734 2, f1 (-2.048, -2.048) =390 5.926;其中后者为该函数的全局最大点;
测试函数2:
minf1 (x1, x2) = (4-2.1xundefined+xundefined/3) xundefined+x1x2+ (-4+4xundefined) xundefined≤3, -3≤x1≤3, -2≤x2≤2;f2有6个局部最小点, 其中 (-0.089 8, 0.712 6) 和 (0.089 8, 0.712 6) 为该函数的全局最小点。
算法测试过程中, 标准遗传算法记为SGA, 本文提出的基于小种群并行的改进遗传算法记为IGA。算法运行过程中, SGA分别使用轮盘赌选择和单点交叉进行选择和交叉操作, 其中交叉概率取0.7。IGA则根据本文提出的新算法进行运算。其中SGA设定初始种群数为100, IGA则初始化为5个小种群, 每个小种群包含20个个体。算法运行的最大进化代数为200, 变异概率为0.05, 当搜索到的最优解与理想极值的误差小于e-3, 则可认为算法已经成功收敛并停止进化。
表1为两种算法各运行50次后的统计结果。
根据对比结果可以看出, 本文提出的基于小种群并行的改进遗传算法可以有效抑制早熟现象的发生, 并可以减少收敛时间, 以相对较少的遗传代数得到最优解, 从而提高算法的执行效率。
4结论
本文针对标准遗传算法易早熟, 算法运行后期搜索效率较低等问题, 提出了一种基于小种群策略的并行遗传算法。通过对交叉算子的修正, 以及多个小规模种群并行优化求解的方案, 使得算法的执行效率得到了提高, 并且在一定程度上解决了标准遗传算法运行过程中收敛速度与易得到局部最优解之间的矛盾。在对两种算法进行测试后, 仿真结果显示本文提出的改进算法较于标准遗传算法性能更好。
参考文献
[1]HOLLAND J H.Adaptation in nature and artificial system[M].Masscchusetts:Masscchusetts Insititute of Technology, 1992.
[2]M SRINIVAS, L PATNAIK.Adaptive probabilities of crossoverand mutation in genetic algorithm[J].IEEE Trans.On Systems, Man, and Cybernetics, 1994.
[3]姚新, 陈国良, 徐惠敏.进化算法研究进展[J].计算机学报, 1995 (9) .
一种主从式并行遗传算法设计 篇3
遗传算法是一种模拟生物在自然环境中的遗传和进化过程而形成的概率搜索算法,它模仿生物在自然环境中的遗传和进化机理。它将问题的解表示二进制编码串。在搜索前给出一定种群大小的染色体群,然后按适者生存、优胜劣汰的遗传机制,从中选出较适应环境的染色体进行复制,再进行交叉、变异过程。最后就会收敛到最适应环境的一个染色体上,即问题的最优解。
早在70年代,遗传算法的奠基人Holland通过模式定理的分析阐述了它所隐含的固有并行性。近年来,随着并行计算研究的深入和发展,遗传算法的并行实现研究也得到了进一步发展。
2 并行遗传算法与MPI并行算法
2.1 并行遗传算法
就目前的研究现状来看,并行遗传算法可以分为主从模型、粗粒度模型和细粒度模型三种[1]。
主从式模型的特点是将个体适应度的计算交给各个从处理机并行进行,而遗传操作由主处理机完成。1992年Abramson在共享存储的并行计算机上实现了主从式并行遗传算法,用于时间表的优化。主从式方法在适应度评估很费时、远超过通信时间的情况下才有效,否则通情时间超过计算时间反而会降低速度。而且这种方法要求有同步机制,这就会导致主进程忙而子进程闲或反之,引起负载不平衡,效率不高。粗粒度模型就是将群体划分成若干子群体,它们独立地进行演化,每经过一定的时间间隔就将它们的最佳个休迁移到其它子群体中。粗粒度模型是目前应用最为广泛的一种并行遗传算法模型,它主要开发群体之间的并行性。细粒度模型将群体划分成众多的小群体,与粗粒度模型相同,选择、变异等遗传操作均限于子群体内部,不同之处在于细粒度模型是通过同类群的重叠(overlap)完成个体迁移的[2]。
2.2 MPI并行算法
并行计算(Parallel Computing):简单的讲,就是在并行计算机上或分布式计算机等高性能计算系统所作的超级计算,其物质基础是高性能并行计算机(包括分布式网络计算机)[3]。
消息传递接口MPI(Message Passing Interface)是为MIMD模式分布式存储器并行计算机和机群系统制定的消息标准。目标是为这类机器建立一个可移植的、易使用的标准消息传递环境。MPI提供一个独立于平台的消息传递库标准,实现程序可移植性的目的,支持PC机、工作站和几乎所有并行机,用MPI编写的程序可不加修改的应用于所有的操作系统平台。MPI环境的初始化和结束流程如下:在调用MPI例程之前,各个进程都应该执行MPI_INIT,接着调用MPI_COMM_SIZE获取缺省组(group)的大小,调用MPI_COMM_RANK获取调用进程在缺省组中的逻辑编号(从0开始)。然后,进程可以根据需要,向其它节点发送消息或接收其它节点的消息,经常调用的函数是MPI_SEND和MPI_RECV。最后,当不需要调用任何MPI例程后,调用MPI_FINALIZE消除MPI环境,进程此时可以结束,也可以继续执行与MPI无关的语句。
3 基于MPI的主从式遗传算法的设计
3.1 算法设计
该模式采用主从式的MPI程序设计思想:将主进程设计为寻找当前代的最优个体并将其发送给各个从进程,从进程进行串行的GA,寻找最优个体给主进程。
1)产生一个进程(该进程为主进程,用于存放和发送当前最优个体);
3)各从进程进行串行GA,当从进程中遗传代数被n整除,从进程发送最优个体至主进程;
4)主进程选择当前各从进程中最优个体,发送给各从进程;
5)各从进程把主进程选择的最优个体替换各从进程当前代种群中适应值最低个体;
6)若各从进程皆满足条件,执行第7)步,否则执行第3)步;
7)算法终止。
3.2 并行程序间消息传递实现的核心代码
主程序代码:
4 实例测试
4.1 问题描述
针对求遗传算法解的精度和解的效率,常常采用经典的测试遗传算法效率的OliverTSP问题来测试。OliverTSP问题的30个城市位置坐标如图表1所示[4]。
4.2 测试方法和环境
测试方法是:通过从硬盘的文件中读取数据来设置染色体长度、种群的规模、交叉概率和变异概率等参数,分别记录串、并行程序到达指定代数时最短路经的长度。需要指出的是遗传算法是一种概率搜索算法,每次的计算结果各有差异,因此算法的计算结果中最短距离路径的长度指得是计算5次的平均值。测试环境是:通过将四台机器加入一个域中,利用域中的同一个用户来调用四台IBM机器中的资源,实现了并行环境。测试的硬件环境如表2所示,测试的软件环境如表3所示,遗传算法参数如表4所示。
4.3 测试结果及结论
通过多次试验和研究总体的发展趋势如图1所示,不难得出下面结论:
并行遗传算法提高了遗传算法的收敛速度,缩短了达到给定精确度的耗时。但是就遗传算法的精确性而言还是由遗传算法本身的特性决定的。
摘要：该文对串行遗传算法进行了并行设计,加入对当前通用消息传递接口MPI的支持,形成了一个主从式并行遗传算法。针对该算法用经典的测遗传算法效率的OliverTSP问题进行测试,得出并行遗传算法可以更好的提高遗传算法的收敛性。
关键词：主从式并行遗传算法,MPI
参考文献
[1]陈国良,王照法,庄镇泉,等.遗传算法及其应用[M].北京:人民邮电出版社,1996.
[2]郭绚,石晓虹.并行遗传算法的性能分析[J].航空计算技术,1998,28(3):86-89.
[3]陈国良.并行计算——结构～算法～编程[M].北京:高等教育出版社,2001.
并行分布式遗传算法的研究 篇4
并行计算理论的研究始于20世纪70年代,经过40多年的发展,其技术日趋成熟。在生活中有大量的实际应用,比如天气预报、地震数据处理、飞行器数值模拟等等,这些领域的事务处理往往需要几十万亿甚至几百万亿次的浮点运算,并行计算[1]是适合这类事务处理的一种技术。近年来云计算的兴起,使得分布式计算技术也逐渐趋于成熟,并得到了广泛的应用,它把网络上分散于各处的计算机资源汇聚起来完成各种大规模的计算和数据处理任务。
遗传算法(genetic algorithm,GA)基于达尔文自然选择定律以及孟德尔遗传理论,它模拟自然生物遗传和选择的过程将适应度相对高的个体保留,适应度相对低的个体逐渐淘汰,循环重复这一过程,直到满足停止条件,因此它是一种迭代搜索算法。遗传算法的全局搜索比较容易实现与加强,目前在许多领域有广泛的应用,比如建筑的结构性优化、化工领域的资源分配、计算机自动控制等等。但在高维、超高维多模态问题中,传统遗传算法仍会表现出一些不足,全局搜索能力不足,易限于局部极优,收敛速度以及精度有待提高。
文章针对传统遗传算法用于高维、超高维多模态问题时存在的不足,提出了基于PVM的并行分布式遗传算法(PVM-IMGA)。PVM-IMGA算法基于PVM平台,采用了一种比较好的适应度评估方法,并对交叉算子、变异算子做了一些改进,使其具有自适应加速特性。为了验证改进工作的有效性,文章最后对一高维多峰值函数进行了实验测试,实验结果表明PVM-IMGA算法克服了传统遗传算法易限于局部极优的问题,全局搜索能力、收敛能力都有了比较明显的提高。
2 问题分析
高维、超高维问题的一个特点是其搜索空间巨大,要在巨大的范围内搜索到合适精度的目标可行解,耗时往往较长,有时甚至无法找到。多个极值是多峰值问题的特点,多峰值问题较一般的单一峰值问题,寻优难度要更大,算法易陷于局部极值,对遗传算法的全局搜索能力会有更高的要求。
3 优化目标
在多峰值问题中,一般是寻找单类型的所有极值,即在有限定义域、可接受的时间范围内要么寻找所有极大值,要么是极小值。本文实验测试所用的多峰函数寻找的是极小值。
为了检验论文提出的并行分布计算方式的有效性,笔者将论文改进后的遗传算法分别在PVM并行环境以及单机环境对Keane’s Bump函数进行实验测试20次,然后求它们的平均时间。两种算法的实验条件相同,例如相同的种群规模、迭代次数等等。图2是在不同维度下,使用PVM-IMGA算法以及单机环境下的IMGA算法的平均搜索时间变化趋势图。从图我们可以看到,在较低维度的条件下,单机环境下的IMGA算法的搜索时间要比并行环境下的PVM-IMGA算法的执行时间要短,但是当维度逐渐增高之后,它们的搜索时间的差距有了一些变化,当维度高到一定程度时,PVM-IMGA算法的执行效率要比单机环境的IMGA算法要高。另外,当维度达到一定高度后,IMGA算法无法在指定的迭代次数内找到所有极值,当增加种群规模以及迭代次数时,其搜索结果会有一点变化,但是仍然是无法达到多峰值问题的寻优要求。之所以出现这样的结果,究其原因,当维度比较低,问题的搜索空间不是很大时,IMGA具有较好的求解能力,可以比较快速的找到可行解,PVM-IMGA算法虽然也具有求解能力,但是因为网络传输需要比较长的时间,所以PVM-IMGA算法的耗时比IMGA算法要长。但是当维度较高,搜索空间比较巨大时,IMGA算法的局限性就暴露出来了。而PVM-IMGA算法因为能将搜索空间分块细化,并交由不同的计算节点来执行,执行效率开始变得更高。当问题维度增大到一定程度时,笔者可以通过调整数据块大小以及增加计算节点来提高算法的搜索效率。
为进一步验证PVM-IMGA算法的稳定性以及收敛能力,笔者对算法能收敛到的最小极值进行统计,并与文献[5]的DE、ABC、HABC算法,文献[3]的IMBF-GA算法进行比较。从表1的4项实验数据可见,在收敛能力和稳定性方面,PVM-IMGA算法皆优于DE、ABC、HABC、IMBF-GA算法,说明PVM-IMGA算法在高维条件下,对多峰函数具有较好的收敛能力,文章针对多模态问题,对传统遗传算法进行的多项修改是有效的。
文献[3]中提到IMBF-GA算法在一定维度下,搜索到所有极值的概率是比较高的,但是当维度增加时,成功率会下降。对于本文的PVM-IMGA算法,如果去除并行分布式计算形式,仅使用单机运行,其运行效果与IMBF-GA算法大致类似,增大种群规模以及迭代搜索次数尽管能在一定程度上提高成功率,但是当函数维度达到一定程度后,算法执行效率、收敛效果仍然难以让人满意。并行分布式计算方式是解决超大规模计算的有效手段,这也是当今云计算与分布式系统流行的一个重要原因。
摘要：传统遗传算法在面对一些搜索空间巨大的复杂问题时,其表现往往难以令人满意。作者针对传统遗传算法解决高维多峰值问题时可能会出现的困难进行了分析,然后根据困难出现的原因,基于PVM设计了并行分布式遗传算法,并对适应度评估、交叉、变异算子做了一些改进,旨在加强算法的全局搜索能力,提高算法的收敛速度。为了验证算法多项措施的有效性,对一多峰函数在高维条件下进行多方面的测试,实验结果表明这几项措施是有效的。
关键词：并行,分布式,多峰,遗传算法
参考文献
[1]Kai Hwang.云计算与分布式系统:从并行处理到物联网[M].北京:机械工业出版社,2013.
[2]刘洪杰,王秀峰.峰搜索的自适应遗传算法[J].控制理论与应用,2004,4(21):303-310.
[3]黄春.改进遗传算法的函数优化及应用[D].南宁:广西大学,2015.
[4]Adam.Parallel Virtual Machine:A Users'Guide and Tutorial for Networked Parallel Computing[M].The MIT Press,1994.
一种新的并行遗传算法应用研究 篇5
遗传算法是模拟生物进化过程的计算模型。遗传算法作为一种新的全局优化搜索算法, 以其简单通用、适于并行处理以及应用范围广等显著特点, 奠定了它作为21世纪关键智能计算之一的地位[1,2,3]。1996年, Pretty[4], Cohoon[5]等人研究了粗粒度的孤岛模型 (Coarse Grain Genetic Algorithm) , 并成功地用于解决旅行商问题、自组织制造系统的调度问题、弹道规划问题、背包问题等, 显示了此算法的优越性[6]。
传统的粗粒度并行遗传算法中, 把初始种群分割成若干个子群体 (岛屿) , 对每个子群体进行并行的遗传操作。由于自始至终各个岛屿之间相互迁入、迁出的个体数 (迁移率) 是固定的, 每个岛屿中的染色体数量也是保持不变的, 这势必在若干代后会导致相对平均适应度较高的子种群因多样性的降低而仅得到局部最优解。而且, 用固定的迁移率来进行岛屿间个体的迁移, 缺乏一定的导向性, 不利于加快整个算法的收敛速度。针对这些问题, 本文设计了一种新的并行遗传算法 (Parallel Genetic Algorithm with Adjustable Migration Rate, AMRPGA) , 即在进化过程中的每一代, 动态计算出各个岛屿的相对平均适应度, 依据相对平均适应度的高低, 动态算出各个岛屿的迁移率, 动态地调高从其它岛屿到平均适应度较高的岛屿的迁移率, 从而使它有机会获得较多的从其它岛屿迁入的个体, 提高其种群的多样性、抑制了“早熟”现象的发生。同时为了防止某个岛屿中的个体数量过多, 提出了一种新的存活期的计算方法, 并针对新的并行遗传算法的特点, 将基于该方法的淘汰机制嵌入到算法的框架结构中, 增强了新算法的收敛性能并加快了收敛速度。针对作业车间调度中的典型问题, 利用改进的算法进行计算, 结果表明AMRPGA比传统的粗粒度并行遗传算法有了很大的改进。
2 新的并行遗传算法的基本思想
传统粗粒度并行遗传算法存在的主要缺陷是:由于平均适应度较高的子种群中的染色体的数量不能及时更新, 当某个岛屿中的个体整体平均适应度较高时, 必然导致该岛屿中所有个体的平均适应度可能会接近于群体中最佳个体的适应度, 也就是说大部分个体的适应度和最佳个体的适应度差异并不大, 降低了种群的多样性, 在种群内部导致选择压力过小而发生“早熟”现象[7,8]。
新的动态改变迁移率的并行遗传算法的设计, 主要针对传统粗粒度并行遗传算法中迁移率选取随机性的不足以及不能及时使整体平均适应度较高的岛屿获得更多的迁入个体来提高它的多样性, 进行了以下两点改进:①迁移率动态调整机制:各个岛屿之间由于其相对平均适应度的不同, 对迁移率的影响也不同, 即相对平均适应度越大的岛屿陷入局部最优的可能性较大, 动态调高从其它岛屿到它的迁移率, 可以使它获得较多的迁入个体, 提高该岛屿的多样性, 防止其陷入局部最优解;②提出了个体存活期的计算方法, 并将其嵌入到新算法中, 仅对参加迁移的每个个体计算存活期, 将年龄大于存活期的个体淘汰掉, 有效防止了平均适应度高的岛屿种群数膨胀过快, 降低了计算开销、加快了算法的收敛速度。
2.1 动态调整迁移率思想的引入及其优点
本文提出基于岛屿的相对平均适应度来动态调整该岛屿的迁移率的思想, 并给出相对平均适应度的计算方法。这种思想的优点是, 当某个岛屿的平均适应度较高时它陷入局部最优解的可能性也就越大, 此时由于它的相对平均适应度也增大, 故而使从其它岛屿到该岛屿的迁移率被动态地调高。因此会有相对较多的个体从其它岛屿迁入该岛屿, 这就避免了其陷入局部最优解, 抑制了“早熟”的发生。
2.1.1 相对平均适应度的确定
设岛屿X中的所有个体的适应度总和为undefined (其中, N为种群个体数目;fi为第I条个体的适应度) , 则该岛屿的平均适应度为:undefined。假设总共有K座岛屿, 则岛屿X的相对平均适应度为FXavg, 其中undefined。
2.1.2 迁移率的动态调整方法
现在假设K座岛屿中有I和J两座岛屿, 由I到J的迁移率记为M (I, J) , 同时由J到I的迁移率记为M (J, I) , I和J的相对平均适应度分别为undefined和undefined。
若Fundefined
M (I, J) =α (Fundefined-Fundefined) +β (1)
上式两个岛屿中一个岛屿的平均适应度为零时, M (I, J) =1, 故需要满足条件α+β=1。
M (J, I) =a (Fundefined-Fundefined) +b (2)
上式两个岛屿中一个岛屿的平均适应度为零, 另一个为极值时, M (J, I) =0, 故需满足条件a+b=0。
2.2 基于存活期的淘汰机制的引入及其优点
由于迁移率的动态改变会使平均适应度较高的岛屿获得较多的迁入个体, 这就不可避免地会加大该岛屿的计算开销, 降低了其收敛速度。为了防止岛屿的染色体数目增长过快, 同时也为了防止平均适应度较低的岛屿种群数过少, 新算法采用了一种淘汰机制, 即仅对参与迁移的个体计算其存活期, 若迁入的个体年龄大于它的存活期就被淘汰的思想。本文提出的存活期的计算方法主要基于两个原则, 一是适应度高的个体的存活期大于适应度低的个体存活期;二是当某个岛屿种群规模过大时要使其不能再接受新的个体。
下面阐述个体存活期的计算方法。
为了控制相对平均适应度较高的岛屿由于得到太多迁入个体而导致种群数膨胀, 本文引入了存活期的概念。首先对种群中的个体设置了两个参数:一个是年龄A (Xi) ;另一个是寿命L (Xi) 。个体Xi每存活一代, 年龄加1, 其存活的代数不能超过其存活期L (Xi) , 寿命值L (Xi) 并不是不变的, 而是每代进化后重新计算所得的。确定L (Xi) 时应遵守这样的原则:一方面使适应度高的个体具有较长的存活期;另一方面当种群数过大时要制止它再接受新的个体, 以防止种群数过度膨胀。本文在文献[9]中提供的线性分配法计算存活期的方法上加以改进, 引入了规模控制阀值。f (Xi) 为个体的适应度函数, 当前群体的最大、最小和平均适应度为:fmax, fmin, favg。根据实际计算速度, 通常种群数达到1 000时, 进化速度明显减慢, 因此有必要引入规模控制阀值
undefined
。则有:
undefined
式中:minLT和maxLT——允许的最大寿命和最小的寿命。
3 新的动态改变迁移率的粗粒度并行进化遗传算法流程与优点
新的动态改变迁移率的粗粒度并行进化遗传算法的模式结构如图1所示。
有了第二节的度量方法即可得到新的并行遗传算法, 算法描述如下:
Step 1:年龄计数器初始化:t←0;
Step 2:随机产生初始种群P (t) , 将初始种群P (t) 划分为子群体P (t) ={P1 (t) , P2 (t) , …, Pi (t) , …, Pn (t) } (其中n为岛屿数) ;
Step 3:分组计算Pi (t) (i=1, 2, …, n) 中每个个体的适应值;
Step 4:对每个Pi (t) 进行分组独立进化, 并保留当前最优解:
·进行选择操作:Pi′ (t) ←Selection[Pi (t) ]。
·进行交叉操作:Pi″ (t) ←Crossover[Pi′ (t) ]。
·进行变异操作:Pi (t) ←Mutation[Pi″ (t) ];
Step 5:计算各Pi (t) 中个体的适应度;
Step 6:为各个岛屿中的每个个体年龄加1;
Step 7:计算岛屿相互之间的迁移率m (i, j) 和m (j, i) ;
Step 8:按迁移率从相应的岛屿i中选取一定数目的个体迁移到岛屿j中, 并对被加到岛屿中的个体计算它的存活期, 淘汰年龄大于存活期的个体。重复该步骤直到按相应的迁移率两两相互交换信息完毕为止;
Step 9:终止条件判断:若不满足终止条件, 则t←t+1转向Step 4;若满足终止条件, 则输出优化结果, 算法结束。
3.1 新算法的主要优点
(1) 根据相对平均适应度动态调整岛屿的迁移率, 使得平均适应度较高的岛屿能获得较多的迁入个体, 增加了该岛屿的多样性, 加大了该岛屿内部个体之间的竞争压力而避免了“早熟”。
(2) 避免了迁移率选取的随机性, 使各个岛屿向着对自己最有利的方向发展。
(3) 对迁移涉及到的个体引入了存活期的概念, 当种群规模膨胀到一定程度时抑制其继续膨胀, 从而加快了收敛速度。
3.2 新算法的收敛性
定理1:基本遗传算法收敛于最优解的概率小于1。
定理2:选择前保留当前最优解的遗传算法最终能收敛到全局最优解。
推论1:标准遗传算法的种群马尔可夫链序列undefined存在极限分布。
本文提出的新并行遗传算法仅仅是将传统的标准遗传算法并行化, 并没有改变其基本框架, 并且采用了最优保留策略, 因而它遵循马尔可夫链标准, 通过定理2和推论1足以证明该算法收敛。
4 仿真研究
为了测试AMRPGA算法的性能, 本文使用Muth and Thompson问题基准测试用例MT10×10, MT6×6数据, 其经典解分别为55和930。此处选取经典的粗粒度并行遗传算法 (CGPGA) 与本文提出的新算法进行比较, 来验证新算法的有效性。
实验中, 粗粒度并行遗传算法交叉概率为0.8, 变异概率为0.2, 迁移率为0.1, 岛屿个数为4, 两个问题分别取迭代次数50代和300代为终止条件, 种群规模为100。本文的动态改变迁移率粗粒度并行遗传算法中除了计算迁移率的系数分别取0.6, 0.3, 0.3, -0.3, 计算中寿命值分别取25和5以外, 其它条件和上述粗粒度并行遗传算法的条件相同。
对于MT6×6问题和MT10×10, 测试数据如表1所示。
注:Jbest——找到的最优值;Javg——平均值;Gmin——得到最优解最小进化代数;Pbest——求得最优解的概率;Var——平均偏差
图2为随机选取的一次MT10×10时的新并行遗传算法 (实线) 和粗粒度并行遗传算法 (虚线) 的进化曲线, 新并行遗传算法比传统粗粒度并行遗传算法收敛的要更快。
通过比较可以发现, AMRPGA算法因为引入了迁移率动态调整机制和存活期策略, 避免了算法陷入局部最优解, 同时也提高了收敛的速度, 无论从收敛速度还是最终得到的最优解的质量, 都优于传统的粗粒度并行遗传算法。
5 结束语
本文提出的新并行遗传算法, 更好地增加了种群的多样性, 不但有效抑制了“早熟”的发生, 而且使最终结果更加接近理想状态下的全局最优解;不但通过动态调整迁移率为迁移提供了导向性, 而且引入了存活期的概念, 避免了种群过度膨胀的现象, 减少了计算开销, 且找到最优解的概率也更高。对Muth and Thompson基准问题的仿真试验证明了该算法在收敛速度和收敛性能上都有明显的提高。
参考文献
[1]WANG Y, CAIZX, GUO G Q, et al.Multi-objective Optimiza-tion and Hybrid Evolutionary Algorithm to Solve ConstrainedOptimization Problems[J].IEEE Trans on Systems, Man andCybemetics-Part B:Cybemetics (S1083-4419) , 2007, 37 (3) :560-575.
[2]张丽萍, 跃廷遗.遗传算法的现状及发展动向[J].信息与控制, 2001, 30 (6) :531-536.
[3]张超勇, 饶云清, 李培根.求解作业车间调度问题的一种改进的遗传算法[J].计算机集成制造系统, 2004, 10 (8) :966-970.
[4]PETTEY C B, LEUUTZ M R, GNFENSTETTE J J.A ParallelGenetic Algorithm[M].London:Wiley, 1987.
[5]COHOON J P, HEGDE S U, MARTIN W N, et al.PunctuatedEquilibrium:AParallel Genetic Algorithm[M].London:Wiley, 2005.
[6]郭彤城, 慕春棣.并行遗传算法的新进展[J].系统工程理论与实践, 2002, (2) :35-38.
[7]王成栋, 朱永生, 张优云.自适应伪并行遗传算法及其性能分析[J].小型微型计算机系统, 2004, 25 (7) :1313-1316.
[8]MONTES E M, COELLO C A C.A Simple Multi-member Evo-lution Strategy to Solve Constrained Strategy to Solve Constrain-ed Optimization Problems[J].IEEE Trans on EvolutionaryComputation (S1089-778X) , 2005, 9 (1) :1-17.
多策略并行遗传算法 篇6
1 并行遗传算法
遗传算法始于一个初始群体, 群体中的个体都要进行这三种运算。运算后的结果如自然选择一样, 比初始群体具有更好的适应性。并行遗传算法就是一种很好的选择, 它能很容易的实现并得到一个很好数值解。除此之外, 并行遗传算法比遗传算法运算速度更快, 并且能得到一个更优结果[2,3,4,5]。标准的遗传算法以群体集合为运算对象, 对个体所进行的各种遗传操作都有一定的相互独立性, 所以它具有一种天然的并行结构。由于遗传算法的天然并行性, 人们认识到了对其进行并行处理的可能性, 从而基于各种并行计算机或局域网开发了多种并行遗传算法 (Parallel Genetic Algorithm, 简称PGA) 。开发并行遗传算法的主要目的是为了提高遗传算法的运算速度[7,8]。
2 目标函数
损伤由刚度减小率βi表示, 定义为减小刚度与初始刚度的比值。损伤结构的刚度矩阵[Kd]表示所有单元矩阵乘以减小因数的和[4]:
βi=0表示结构未损伤, 0<βi<1表示结构部分或全部损伤。
频率变化:
式中:下标0———初始未损伤状态;
λi———第i个特征值;
ωi———第i个频率。
模态保证标准:
式中:φiu———未损伤的第i阶模态向量;
φid———损伤后的第i阶模态向量。
MAC是一个无量纲的量, 范围从0到1, 代表了两组模态向量之间的关联程度, 1指完全关联, 0指完全不关联。
目标函数:
Fλ, 0, FMAC, 0表示结构未损伤时的值 (β=0) 。FD表示损伤补偿函数。当损伤补偿函数加到目标函数中, 还要包括最小损伤。由此, 由计算误差引起的错误损伤检测就可以避免了。罚函数如下:
此等式由Meruance和Heylen提出, 补偿了全部的损伤, 常数γ取决于计算模型的精确度。
最优问题定义如下:
3 算例
3.1 计算模型及基本假定
用一跨预应力混凝土简支梁进行数值模拟, 为了更好地观察结果, 简支梁外伸形成悬臂梁。如图1所示, 该模型有30个单元, 31个节点, 弹性模量是3.0×1010Pa, 密度是2500kg/m3, 面积是0.06m2, 惯性矩是4.5×10-4m4。
模态观测数据用结构的有限元模型模拟获得, 损伤用弹性模量折减来模拟。损伤工况设计如下[5, 7, 10]:
工况一:10号单元10%损伤, 20号单元35%损伤;
工况二:10号单元20%损伤, 20号单元35%损伤;
工况三:10号单元35%损伤, 20号单元35%损伤。
3.2 初始参数的确定
为了提高收敛速度, 避免过早收敛, 遗传算法的参数和算子取值如下:种群大小:N=75;变异概率pm=0.02;交叉概率ps=0.8。初始种群值为1[5,6,7,8,9]。
3.3 计算结果与讨论
迁移时段如图2所示, 以敏感度分析定义。得到的最优迁移时段是70。图3示出的是通过并行遗传算法收敛率的提高。
并行遗传算法 (PGA) 求解最优解的时间是500多秒钟, 而遗传算法 (GA) 则需要1000多秒。并行遗传算法运算时间是遗传算法的0.5倍。
三种工况的下的损伤探测如图4所示。
从图中可以看出, 损伤检测结果已经达到了完美的程度, 和模拟的损伤很接近, 但并不能说明实际的应用当中也有很好的应用, 所以这方面的研究工作将在以后进行讨论。
4 结论
本文提出了并行遗传算法检测结构损伤的方法。数值模拟结果表明相比于遗传算法, 并行遗传算法在表现上更进一步, 在计算结果相同的条件下, 计算速度是遗传算法的1.5倍。因此, 对于明确问题的并行遗传算法可以使结果得到改进。
本文提出的方法只是针对于预应力简支梁桥模型的损伤识别进行了研究, 对于其他结构, 如高层结构、框架结构等的损伤识别同样有很好的表现。提出的并行遗传算法定位、定量的识别了模拟的损伤, 但是没有考虑损伤发生时刻的检测。其在实际结构损伤中的应用也未做具体的分析实验。这些将在以后进行研究分析, 在损伤识别领域中, 并行遗传算法会有更好的发展。
参考文献
[1]Mares, C.and Surace, C.An application of genetic algorithms to identify damage in elastic structures[J].Journal of Sound and Vibration, 1996, (195) :195-215.
[2]袁颖.遗传算法在结构损伤识别中的应用研究[J].防灾减灾工程学报, 2005, 25 (4) :114-116.
[3]曾国荪.并行遗传算法分析[J].计算机工程, 2001, 29 (9) :96-98.
[4]Meruane, V.and Heylen, W.Damage detection with Parallel Genetic Algorithms and Operational Modes[J].Structural Health Monitoring, 2010, (9) .