多目标自适应遗传算法（精选9篇）
多目标自适应遗传算法 第1篇
在传感器与作动器的优化配置问题求解上, 前人采取了枚举法等一般算法, 但随着计算机技术的发展, 随机类算法得到了广泛的开发和应用。目前国内的相关研究以遗传算法居多:研究遗传算法在搜索目标函数方面的应用, 以及基于其他智能算法思想对遗传算法的改进。
许锐等[1]使用粒子群算法, 姜冬菊等[3]使用混沌优化算法, 研究了结构优化问题。李红芳等[2]基于混沌理论 (Chaos theory) 改进遗传算法, 使算法对初值敏感性加强、提高局部搜索速度, 提高了遗传算法的运行效率。
1 力学模型
研究以压电材料和普通材料组成的智能桁架结构, 为简化。压电材料以堆叠形式叠加形成作动器, 作为主动杆对结构产生的形变或震动进行响应, 并产生电压与应变, 通过一定的控制方式 (如主动控制、被动控制或混合控制) , 对外界作用进行响应和调整, 使结构能够更加稳定。
对模型进行简化, 忽略温度等较低因素以及压电材料的磁场效应, 得到机电耦合模型:
其中:{T}是压电杆的应力矢量, 是压电杆的应变矢量 (无单位) ;{E}是电场强度矢量, {σ}电位移矢量;{c}是弹性常数矩阵;[d]是压电应力系数矩阵;是夹持介电常数矩阵。
在仅考虑轴力作用, 则式 (1) 可以简化为:
假设主动杆 (图1所示) 由n个相同压电片组成, 场强为:
得到输出总位移如下:
其中, φ为压电堆并联电路中中各个压电片两端的电势差, t为单个压电片的轴向厚度, k为压电片轴向刚度。
根据式 (2) 和式 (3) 以及受力平衡电荷平衡推导得到:
节点处位移受到外界力、压电作用产生的电荷力以及惯性力影响, 根据节点的力和电荷平衡, 由式 (6) 得到全局坐标系下的力和电荷平衡方程:
其中N为杆两端受力, Q为压电杆受力产生的电荷, 杆轴向长记为l, 轴面横截面积为A, Δu为杆两端位移。Pε为单元荷载向量;Mε为单元质量阵;uε为单元位移向量;λ为坐标转换矩阵;Φε为单元势差向量;Qε为单元电荷向量。
消去电势差Φε, 得到动力学有限元方程如下:
杆作用力P分为外界载荷Fd与作动器产生的作动力Fc, 有如下关系:
可以得到桁架有限元模型:
2 遗传算法设计
针对遗传算法的收敛过程中的早熟问题, 对适应度函数进行调整。有相关文献提出的自适应函数, 使用动态适应度对演化过程进行调节:最大适应度Fitmax, 最低适应度Fitmin和平均适应度Fitave。设计阀值a (0.5<a<1) 和b (0.5<b<1) , 操作如下:
对于压电桁架, 通过设计各杆的横截面以及主动杆位置, 使得桁架总质量与节点位移满足优化目标。以最小重量W为目标, 在控制电压V和杆应力σ不超过上限, 节点位移在要求范围内, 对主动杆布置以及各杆的横截面在取值区间内进行搜索:
其中:ρ1为普通杆密度;ρ2为压电杆密度;ai=0表示杆为普通杆, ai=1表示杆为压电杆。
3 计算实例
使用压电材料优化十杆桁架问题 (文献[5]) , 在原有杆截面问题上增加压电作动器优化结构, 使得重量最小且节点位移在要求内。尺寸结构, 左端节点3、6铰接固定, 右端自由。杨氏模量为, 许用应力为25ksi=172.375MPa, 各杆横截面下限为, 普通杆密度为, 压电作动器密度, 斜杆 (杆2、4、6、10) 作动因子为8.81, 横杆 (杆1、3、7、8、9、10) 作动因子为1.25, 压电杆最大电压为300V, 要求位移小于杆长, 载荷作用于节点5。
设计自适应遗传算法, 取初始种群数M=60;使用浮点编码横截面积;使用长度为10的字符串通过二进制编码进行杆位的编码, 其中1代表主动杆, 0代表普通杆。设定交叉概率为, 变异概率为。迭代200代进行搜索, 结果如表1所示。
计算结果相比较文献中, 添加了作动器使得结构在设置条件下质量降低9.6%, 可以证明使用遗传算法进行计算是可行的。
4 结束语
结果证明了使用遗传算法进行作动器位置、杆件截面的多目标优化的可行性, 其应用于大型复杂结构多也成为可能。
摘要：针对压电智能桁架的作动器配置问题与桁架结构截面优化与压电杆配置问题进行一体化设计, 通过改进的自适应遗传算法进行求解, 保持了种群多样性, 提高优化搜索的全局性。最后通过算例, 证明方法的有效性和可行性。
关键词：智能桁架,压电作动器,遗传算法,优化配置
参考文献
[1]许锐, 王泽兴, 罗雪.桁架优化的改进粒子群算法[J].佳木斯大学学报 (自然科学版) , 2012, 30 (1) .
[2]李红芳.混沌遗传算法与结构优化设计[D].天津大学建筑工程学院, 2004.
[3]姜冬菊.结构拓扑和布局优化及工程应用研究[D].河海大学, 2008.
[4]张世君.压电桁架中作动器与传感器的优化布置研究[D].河北工程大学, 2012.
多目标自适应遗传算法 第2篇
用自适应伪并行遗传算法求解双准则三维运输问题
采用并行计算的思想,在单台计算机上应用自适应的`伪并行遗传算法,求解了双准则三维运输问题,最后通过实验验证该方法可产生适合需求的解,同时体现了该算法有较快的收敛速度.
作 者：张春梅 武钧 梁治安 ZHANG Chun-mei Wu jun LIANG Zhi-an 作者单位：张春梅,武钧,ZHANG Chun-mei,Wu jun(内蒙古大学,理工学院,呼和浩特,010020)梁治安,LIANG Zhi-an(上海财经大学,应用数学系,上海,33)
刊 名：数学的实践与认识 ISTIC PKU英文刊名：MATHEMATICS IN PRACTICE AND THEORY 年，卷(期)： 37(11) 分类号：O1 关键词：伪并行 自适应 遗传算法 运输双准则多目标自适应遗传算法 第3篇
关键词:量子遗传算法;多目标分配;最优化
中图分类号:TP18 文献标识码:A 文章编号:1674-7712 (2012) 12-0176-01
一、引言
遗传算法不同于传统寻优算法的特点在于:遗传算法在寻优过程中,仅需要得到适应度函数的值作为寻优的依据;同时使用概率性的变换规则,而不是确定性的变换规则;遗传算法适应度函数的计算相对于寻优过程是独立的;算法面对的是参数的编码集合,而并非参数集合本身,通用性强。它尤其适用于处理传统优化算法难于解决的复杂和非线性问题。[1]
目前,GA已经在很多领域得到成功应用,但随着问题规模的不断扩大和搜索空间的更加复杂,GA在求解很多具体问题时往往并不能表现出其优越性。于是,近年来便出现了遗传算法与其它理论相结合的实践,其中遗传算法与量子理论的结合是一个崭新的、极富前景和创意的尝试。
量子遗传算法QGA是量子计算特性与遗传算法相结合的产物。基于量子比特的叠加性和相干性,在遗传算法中借鉴量子比特的概念,引入了量子比特染色体。由于量子比特染色体能够表征叠加态,比传统GA具有更好的种群多样性,同时QGA也会具有更好的收敛性,因此在求解优化问题时,QGA在收敛速度、寻优能力方面比GA都将有较大的提高。QGA的出现结合了量子计算和遗传算法各自的优势,具有很高的理论价值和发展潜力。
本论文提出用量子遗传算法处理和解决多目标分配问题,为多目标问题的解决提供一种新的思路。
二、量子遗传算法
在传统计算机中,信息存储是以二进制来表示,不是“0”就是“1”态,但是在量子计算机中,充当信息存储单元的物质是一个双态量子系统,称为量子比特(qubit),量子比特与比特不同之就在于它可以同时处在两个量子态的叠加态,量子进化算法建立在量子的态矢量表述基础上,将量子比几率幅表示应用于染色体的编码,使得一条染色体可以表示个态的叠加,并利用量子旋转门更新染色体,从而使个体进达到优化目标的目的。
一个 位的量子位染色体就是一个量子位串,其表示如下:
其中 。在多目标优化中,一个量子染色体代表一个决策向量,在量子态中一个 位的量子染色体可以表达 个态,采用这种编码方式使得一个染色体可以同时表达多个态的叠加,使得量子进化算法比传统遗传算法拥有更好的多样性特征。
为了实现个体的进化,经典进化算法中通过染色体的交叉、变异操作推进种群的演化,而对量子进化算法而言,量子染色体的调整主要是通过量子旋转门实现的,算法流程如下:
(1)进化代数初始化: ;
(2)初始化种群 ,生成并评价 ;
(3)保存 中的最优解 ;
(4) ;
(5)由 生成 ;
(6)个体交叉、变异等操作,生成新的 (此步可省评价);
(7)评价 ,得到当前代的最优解 ;
(8)比较 与 得到量子概率门 ,保存最优解于 ;
(9)停机条件 当满足停机条件时,输出当前最优个体,算法结束,否则继续;
(10)以 更新 ,转到4)。
三、基于量子遗传算法的多目标分配应用
如今为了满足市场的需要,很多工厂的生产种类多、生产量大,从而设置了不同的生产车间,根据产品的性质分配生产车间合理与否直接影响工厂的经济收益,这同样可采用遗传算法的目标分配方法进行分配。
模型构建:设工厂有i个生产车间。 为在第i个车间生产第j种产品的收益, 为第j种产品的需求量;如果第j种产品被选中,则 为在第i个车间生产该产品的总收益。由题意知为求解 最大问题。
仿真实例:设有10个生产车间,要生产15种产品,用Matlab程序编程,设定40个粒子,迭代200次,代沟0.9。运行结果如下:
此图表明经200次迭代后的目标分配方案为:第1种产品由第3个车间生产,以此类推,车间5生产第2种产品,车间8生产第3种产品,……。次方案对应的车间总收益值为2.7030e+003,成功进行了多目标分配问题的解决。
四、结论
基于量子遗传算法的多目标分配,为多目标分配突破传统寻优模式找到了一个可行的解决方法。根据这种方法实验,仿真结果可以看出,基本符合要求,并且能够在一定的时间内得到最优的分配方案,因此,本文在探索多目标分配问题上找到了一种新的解决思路。
参考文献:
[1]吉根林.遗传算法研究综述[J].计算机应用与软件,2004,21(2):69-73
[2]肖晓伟,肖迪.多目标优化问题的研究概述[J].计算机应用研究,2011,3,28(3):805-808
[3]原银忠,韩传久.用遗传算法实现防空导弹体系的目标分配[J].火力与指挥控制,2008,3,33(3):80-83
[4]郭张龙,李为民,王刚.基于遗传算法的目标分配问题的研究[J].现代防御技术,2002,6:0172-0180
[5]孙祥,徐流美.matlab7.0基础教程[M].北京:清华大学出版社,2005
多目标自适应遗传算法 第4篇
在过程控制系统的分析和设计中,由于被控对象的复杂性或者是工况的变化以及系统元器件老化等一系列的因素,要想获得精确的数学模型往往是不可能的。众所周知,鲁棒理论和鲁棒系统设计方法是解决模型参数不确定性的有效工具。Owens等人在多变量系统频域方法的基础上,提出了多变量系统近似模型的方法[1]。庞国仲等人在此研究的基础上,提出了基于近似模型的多变量系统鲁棒设计方法[2]。多变量系统鲁棒设计方法易于工程实现,但是近似模型的选取需要进行多次试凑,难以获得较优的鲁棒设计结果。
针对该问题,本文提出了基于自适应遗传算法的多变量系统近似模型设计方法。遗传算法是借鉴生物界自然选择和自然遗传机制发展起来的搜索算法,可实现全局并行、随机搜索。简单遗传算法由于交叉概率Pc和变异概率Pm取为恒定值,用于复杂的多变量优化问题时优化效率不高,并且存在“早熟”的现象。文献[3]提出的自适应遗传算法可有效地提高遗传算法的优化能力。本文将自适应遗传算法用于多变量系统近似模型的选取,对一大型工业加热炉进行鲁棒系统设计,取得令人满意的结果。
2 多变量近似模型设计方法[4]
对多变量系统,一种工程实用设计方法如图1所示。图1中的G(s)∈Cmm为广义对象的传递函数矩阵;Kp(s)∈Cmm为预补偿矩阵;Kc(s)∈Cmm为主控制器矩阵;undefined为反馈增益矩阵。
2.1 多变量近似模型的设计方法
对于许多复杂的工业对象,模型G(s)的参数具有不确定性。对这类系统,多变量近似模型方法是一种有效、实用的鲁棒系统设计方法。其思想是:在选定的典型工况下,不同运行时间用实验方法建模,得到一组被控对象的传递函数矩阵G(k)(s)(1≤k≤n)。根据G(k)(s)选取近似模型GA(s),对它进行系统设计,然后用近似模型理论,检验实际系统的稳定性。有如下定理保证系统G(k)(s)是鲁棒稳定的。
记各实际模型与近似模型的误差模型为G(k)e(s),则:
G(k)e(s)=G(k)(s)-GA(s) (1≤k≤n) (1)
令:
L(k)(s)=[I+KP(s)Kc(s)FGA(S)]-1KP(s)Kc(s)FG(k)e(s) (2)
式中:L(k)(s)关联矩阵,它体现了误差模型的影响;Imm单位阵。
定理[2] 若:
(1)近似闭环系统是稳定的;
(2)L(k)(s)的谱半径:
r[L(k)(s)]<1 (∀s∈D) (3)
则实际闭环系统是稳定的。
由此可以得到多变量系统近似模型设计方法的设计步骤:
①从对象的一组传递函数矩阵G(k)(s)中,选取近似模型GA(s);
②对GA(s)设计预补偿器KP(s),使Q(s)=GA(s)KP(s)为对角优势阵;
③设计主控制器矩阵Kc(s),使GA(s)稳定,且具有良好的性能;
④选定系统工作频段,绘制L(k)(s)的谱半径曲线,判断实际闭环系统的稳定性。若不稳定,则返回③,重新设计Kc(s);
⑤作G(k)(s)的闭环单位阶跃响应,检验系统是否鲁棒稳定,性能是否符合设计要求。若不满足,则返回③,重新设计Kc(s)。
在上述设计方法中,关键的一步是近似模型GA(s)的选取。传统的设计方法需要凭借工程设计人员的经验来选取近似模型,不能保证所选的近似模型是最优的。如何选择最优GA(s),使根据GA(s)设计的控制器与实际对象组成的控制系统具有鲁棒稳定性,并满足要求的性能指标,是需要解决的问题。
2.2 最优近似模型选取
选择最优近似模型首先应当确定近似模型的衡量标准。由文献[5]可知,误差模型G(k)e(s)的变差矩阵的谱范数‖N∞(G(k)e)‖2越小,多变量系统鲁棒稳定性的条件越容易得到满足。‖N∞(G(k)e)‖2反映了近似模型GA(s)与实际对象模型G(k)(s)之间的误差,若‖N∞(G(k)e)‖2(1≤k≤n)都比较小,则GA(s)就能较好地反映实际对象的特性。‖N∞(G(k)e)‖2的计算方法如下:
①作实际对象模型G(k)(s)各元素gundefined(s)的单位阶跃响应yundefined(t),并写成矩阵形式:
Y(k)(t)={yundefined(t)}mm (4)
②作近似模型GA(s)各元素gAij(s)的单位阶跃响应yAij(t),并写成矩阵形式:
YA(t)={yAij(t)}mm (5)
③求GA(s)与G(k)(s)的误差函数矩阵:
Y(k)e(t)=Y(k)(t)-YA(t)={yundefined(t)-yAij(t)}mm={yundefined(t)}mm (1≤k≤n) (6)
④求误差函数矩阵变差矩阵:
undefined
⑤求变差矩阵的谱范数:
‖N∞(G(k)e)‖2=r[N∞(G(k)e)TN∞(G(k)e)] (8)
3 基于自适应遗传算法的近似模型设计方法
3.1 编码方案
将遗传算法用于GA(s)的选取,第一步就是如何对矩阵的各参数进行编码。由于求解参数比较多,本文选用实数编码。编码的形式因GA(s)的元素gAij(s)(1≤i,j≤m)的结构不同而变化。根据大部分工业过程的特点,我们考虑了四种元素gAij(s)(这里仅考虑稳定的过程对象),其对应的编码形式如表1所示。
据表1确定GA(s)的编码为:
3.2 初始种群
设种群中染色体的个数为q,我们在选择初始种群的样本时,随机产生若干倍于q的染色体,将这些染色体按照适应度从大到小排列,选取前q个染色体作为初始种群,这样有利于遗传算法逼近全局最优解。
3.3 适应度函数
根据最优近似模型的选取准则,取适应度函数为:
undefined
适应度函数的计算方法:从实际对象模型库中依次取出G(k)(s),将待评价的染色体解码后得到GA(s),根据前文所述的方法得到‖N∞(G(k)e)‖2,根据式(10)得到该染色体的适应度。
3.4 自适应交叉和变异
自适应遗传算法的交叉率Pc和变异率Pm按如下公式进行自适应调整:
undefined
undefined
式中:fmax群体中最大适应度值;favg群体平均适应度值;f ′要交叉的两个个体中较大的适应度;f要变异个体的适应度。
当群体有陷入局部最优解的趋势时,就相应地提高Pc和Pm;当群体在解空间发散时,就降低Pc和Pm。同时,对于适应度高于群体平均适应值的个体对应较低的Pc和Pm,该解被保留进入下一代;而低于平均适应度的个体对应较高的Pc和Pm,该解被淘汰。因此,自适应的Pc和Pm能够提供相对某个解的最佳Pc和Pm[6]。自适应遗传算法在保持群体多样性的同时,保证遗传算法的收敛能力,有效地提高了遗传算法的优化能力。
4 应 用
控制对象为某烷基苯厂的一个大型加热炉,它是一个两输入、两输出的多变量系统,输入量分别为燃油压力P、烟道挡板开度α,输出量分别为炉出口温度T和烟气氧含量O2。工艺要求出口温度在310±1 ℃,为提高热效率,加热炉实现低氧燃烧。机理分析表明,该广义对象具有明显的非线性、大时滞和时变特性。
在典型工况下,不同的时间对加热炉进行建模,得到三个不同的数学模型。由于时延变化不显著,可以用Smith预估器作近似补偿。补偿之后的传递函数矩阵分别为:
undefined
undefined
undefined
取近似模型的结构为:
undefined
采用自适应遗传算法对GA(s)的各个参数进行寻优,其编码之后的染色体为K11,ζ11,T11,K12,ζ12,T12,K21,T21,K22,T22。
遗传算法的参数设置:群体大小为40,选择机制采用适应度比例法,自适应交叉概率Pc1=0.9,Pc2=0.6,变异方式采用动态变异,自适应变异概率Pm1=0.1,Pm2=0.001,迭代次数为500,仿真步长为2 s,仿真时间为2 000 s。得到最佳个体为:
x′=[0.463 4,102.641 8,3 047.301 7,-0.059 9,86.650 3,2 752.883 7,-0.999 4,61.173 5,0.613 0,63.595 6]
即:
undefined
最优近似模型GA(s)与各个实际对象模型G(k)(s)(1≤k≤3)的误差模型的单位阶跃响应曲线如图2所示。GA(s)与G(k)(s)的‖N∞(G(k)e)‖2分别为0.345 3、0.347 9和0.237 0。可见,本文使用自适应遗传算法寻优得到的GA(s)使‖N∞(G(k)e)‖2都比较小,所以该近似模型是最优的。
在自行研制的多变量系统设计平台中,对GA(s)进行系统设计,取F为单位阵,可以得到预补偿矩阵和主控制器:
undefined
undefined
将设计的KP,Kc(s)与G(k)(s)组成一个实际闭环系统。该实际闭环系统的工作频段取为0.001～0.08 rad/s,根据式(3)可以得到各系统的谱半径曲线,如图3所示。可见,三个系统谱半径曲线的最大值全部小于1,由文献[2]可知,实际闭环系统是鲁棒稳定的。
作出实际闭环系统的单位阶跃响应曲线,如图4所示。可见,系统不仅稳定,而且具有良好的鲁棒性能。
5 结 论
本文提出的基于遗传算法选择最优近似模型的方法,是一种启发式智能选择方法,已在自行研制的多变量鲁棒设计平台中实现,它改变了一直以来凭设计人员的经验选取近似模型的方法,使用方便、准确度高。本文所实现的基于近似模型技术的多变量系统鲁棒设计平台,集模型优化、系统分析和系统设计于一体,在工程上具有较大的应用价值。
参考文献
[1]OWENS D H,CHOTAI A.Robust Controller Design for LinearDynamic Systems Using Approximate Model[J].IEE Proc,1983,130(2):45-46.
[2]庞国仲,白方周,等.多变量控制系统实践[M].安徽:中国科技大学出版社,1989.
[3]SRINIVAS M,PATNAIK L M.Adaptive Probabilities of Cross-over and Mutation in Genetic Algorithm[J].IEEE Trans onSMC,1994,24(4):656-667.
[4]尹君,薛福珍.一种综合改进型遗传算法及其在多变量解耦中的应用[J].化工自动化及仪表,2008,35(2):16-20.
[5]庞国仲,韩珂,陈振跃.多变量系统近似模型设计方法[J].计算技术与自动化,1989,8(1):24-31.
多目标自适应遗传算法 第5篇
多目标优化问题MOP (multiobjective optimization problem) 是指需要同时优化两个或多个互相冲突目标的优化问题[1]。MOP往往不存在一个解使得所有目标同时取得最优, 只能找出一组解使得目标函数尽可能达到Pareto前端[2], 因此, 寻找能够通过一次计算就可以得到均匀分布在Pareto前端最优解集的多目标优化算法是学者们研究的热点之一[3]。
传统的多目标优化算法将多目标优化问题通过加权方式转化为单目标问题, 在每次求解过程中, 只能得到一个解, 算法效率较低, 而且对权重值和目标给定次序比较敏感[4]。智能优化算法通过种群代与代之间维持潜在解组成的集合实现多目标优化, 近十几年来, 相继提出了不同的多目标优化算法, 如早期的矢量评价遗传算法 (VEGA) 、非劣排序遗传算法 (NSGA) , 随后出现的基于精英保留机制的PAES、SPEA2及经典的NSGA-Ⅱ[5]等算法。将新的机制和策略引入多目标优化算法并对其改进是当前多目标优化的前沿领域, 文献[6]利用多目标优化问题PS分布规则, 提出了一种分布多目标优化问题估计算法RM-MEDA;文献[7]针对多目标粒子群算法 (MOPSO) [8]在优化Pareto前段分段不连续函数时存在收敛效率低、多样性差的缺陷, 提出了一种基于杂草克隆的多目标粒子群算法;文献[9]通过引入克隆选择机制, 提出了一种基于非支配邻域的改进多目标优化算法NNIA-Ⅱ, 实验结果证明了NNIA-Ⅱ具有优秀的求解性能。
混合蛙跳算法SFLA[10]是一种新型的群智能启发式计算技术, 由于SFLA具有实现容易, 收敛速度快等特点, 被广泛使用[11,12], 然而将SFLA应用于多目标优化问题的研究很少。SF-LA较强的寻优能力使其能够快速接近理论Pareto最优解, 但是, 对于多目标优化问题, SFLA存在易于陷入局部最优及需要根据Pareto支配进行多目标函数适应度赋值等问题, 针对这些问题, 本文提出了一种自适应混沌混合蛙跳算法求解多目标优化问题MACSFLA (Adaptive Chaos Shuffled Frog Leaping Algorithm for multiobjective optimization) , 并做了如下改进:
1) 针对SFLA容易陷入局部极值的问题, 使用动态权重因子策略以增强算法跳出局部最优能力和提高算法收敛效率;
2) 引入基于Pareto支配能力的SFLA子族群划分策略, 使得SFLA能够应用于多目标优化问题;
3) 为提高MACSFLA算法的收敛效率, 采用自适应网格密度机制动态维护外部存储器Pareto最优解规模, 并使用自适应混沌优化技术改善Pareto最优解集样本多样性;
4) 利用Pareto最优解选择策略为青蛙种群选择最优更新粒子。
通过对多目标函数实验测试, 结果表明, 与MOPSO和NS-GA-Ⅱ相比, MACSFLA在Pareto最优解集均匀性和多样性上有明显优势。
1多目标优化问题和混合蛙跳算法
1.1多目标优化问题数学描述和基本概念
多目标优化是对多个目标函数同时进行优化, 是优化问题主要的研究领域之一, 不失一般性, 一个决策变量维数为n, 目标变量数目为m的多目标优化问题可以表述为:
其中, x= (x1, x2, …, xn) 为n维决策变量, y= (y1, y2, …, ym) 为目标函数, gi (x) 、hi (x) 分别为不等式约束和等式约束。
定义1 Pareto支配
设有f:Rn→Rm, 对于给定决策变量x1和x2 (x1, x2∈Rn) , 则称与x2相比, x1支配x2, 当且仅当:
定义2 Pareto最优解与Pareto最优解集
决策变量x*称为Pareto最优解, 当且仅当满足条件:
所有Pareto最优解的集合就是Pareto最优解集, 并记为:
定义3 Pareto前端
Pareto最优解集P*中的解对应的y= (y1, y2, …, ym) 组成的集合成为Pareto前端, 并记为:
1.2混合蛙跳算法 (SFLA)
基本SFLA工作原理可以描述为:青蛙种群F包含N只青蛙, 每只青蛙代表n维优化问题的一个解, 设第i只青蛙的位置为Xi={xi1, xi2, …, xin}。青蛙种群将青蛙按照适应度值[13]f (Xk) 降序排列, 并平均分配到M个子族群El (1≤l≤M) 中, 子族群青蛙数为Q, 其中, El按照式 (6) 进行划分。
SFLA对子族群El中适应度最差的个体Xl, w进行更新:
其中, r∈ (0, 1) 为随机数, Xl, b为El适应度最好的个体。如果f[Xl, w (t+1) ]优于f[Xl, w (t) ], 则用新个体替代原个体, 否则用种群内适应度最好的解Xg代替Xl, b重新执行更新策略式 (7) , 如果仍不能优于原个体, 则随机生成青蛙取代原个体。所有子族群执行一定次数的局部迭代搜索后, 青蛙种群重新混合, 然后划分新的子族群, 并重新进行局部搜索, 算法如此往复, 直到满足终止条件。
研究表明, SFLA存在易于陷入局部极值的缺陷, 特别是在算法迭代后期, 当某个青蛙十分接近局部极值时, 算法需要迭代多次才有可能跳出。为了避免SFLA早熟, 对算法更新策略进行改进, 引入动态权重因子策略:
其中, ξ1、ξ2、c1为比例系数, rmin、rmax为权重因子最小值与最大值, Tmax为算法最大迭代次数。从式 (8) 和式 (9) 可以看出, 动态权重因子策略实质为在非线性指数函数递减权重因子的基础上增加了随机扰动, 采用该权重因子策略使得算法在运算初期, r'取值较大, 青蛙能在比较大的空间进行搜索;算法运算后期, 随机扰动让算法能够进一步深度搜索, 提高了算法收敛精度。
对于多目标优化问题, SFLA无法直接根据适应度值进行子族群划分, 因此, 本文提出基于Pareto支配能力的SFLA子族群划分策略:青蛙种群完成一次迭代后, 将所有青蛙进行Pareto支配关系比较, 对于青蛙Xi, 由其支配的青蛙组成的集合为Zi, 即:
设|Zi|为Zi内青蛙个数, 种群根据|Zi|将青蛙降序排序, 如果两只青蛙具有相同的|Zi|, 则随机进行排列。当所有青蛙完成排序后, 根据式 (6) 进行子族群划分。在子族群El内, 对具有最小|Zi|的青蛙按照式 (7) 进行更新, 如果子族群多只青蛙具有相同的|Zi|, 则随机选择一个个体进行更新。如果更新后的个体支配原个体, 则用新个体替代原个体, 否则随机产生新的个体进行替代。
2自适应混沌混合蛙跳算法
2.1自适应网格密度机制
本文将Pareto最优解存储器记为Archive集, MACSFLA每次进化会产生新的Pareto最优解粒子, 称这些粒子为Archive集候选解, 当候选解满足如下条件之一时就可以进入Archive集。
1.Archive集为空集。
2.Archive集为非空集, 且候选解不受Archive集中任一个粒子支配。
3.候选解支配Archive集所有粒子。
4.候选解不受Archive集中至少一个粒子支配, 且候选解所在网格的密度值比该非支配解所在网格的要小。
随着算法迭代不断增加, Archive集规模不断增加, 其计算复杂度为O (t·m·N2) , 如果不控制Archive集规模, 将很大程度地增加计算复杂度, 因此, 本文规定Archive集规模为N, 并采用自适应网格密度机制动态维护Archive集规模。自适应网格密度机制工作原理可以描述为:
Step1 自适应网格划分。将m维目标空间划分为K1×K2×…×Km相同的网格, 网格i维宽度di为:
Step2 Archive集粒子网格定位。设第t代Archive集集合为At={a1, …, aj, …, ah} (h≤N) , 对于aj, 其第i维网格编号wij为:
由式 (13) 可以确定aj在目标空间内的位置aj (w1j, …, wmj) 。
Step3 Archive集网格粒子密度计算。设网格Gk的粒子密度为Dk, 并定义Dk为网格内Pareto最优解的个数, 如果网格内没有粒子, 其Dk为0。
Step4 Archive集粒子淘汰。当候选解加入Archive集后, 可能会使得Archive集规模大于N, 因此需要进行Archive集粒子淘汰:对于网格Gk, 如果其Dk>1, 则根据式 (14) 对其中粒子进行删除。
其中, Gd为网格Gk需要删除的粒子数, 为Archive集加入候选解后的规模。确定Gd后, 根据式 (15) 计算Gk中粒子与理论Pareto前端距离, 并依次删除远离Pareto前端的粒子。
其中, DGk, i为Gk内粒子i与理论Pareto前端最短距离。
2.2自适应混沌优化技术
Archive集中的个体决定了青蛙种群的进化方向, 自适应网格密度机制在一定程度上保证了Archive集中粒子的均匀分布, 但是, 如果某些理论Pareto最优解没有存储在Archive集中, 那么之后会很难再找到该Pareto最优解[4]。为了改善Archive集样本多样性, 引入自适应混沌优化技术, 其思路可以描述为:随机选择Archive集部分粒子进行混沌优化 (限于篇幅, 混沌优化过程不再赘述) , 设粒子i在混沌优化第k-1代、k代和k+1代的位置分别为Ck-1, i、Ck, i和Ck+1, i, Pk-1, i、Pk, i和Pk+1, i分别为Ck-1, i、Ck, i和Ck+1, i的Pareto前端, 则第k-1代、k代和k+1代之间Pareto前端距离Dk, k-1、Dk, k+1分别为:
定义混沌迭代控制系数diffD为Dk, k-1、Dk, k+1的差值, 即:
当diffD>0表示算法处于进化状态, 可以减少混沌优化迭代次数, 以提高算法速度, 当diffD<0表示算法进化能力降低, 需要增加混沌优化迭代次数, 以提高算法精度, 混沌优化迭代次数KCmax自适应策略为:
自适应混沌优化技术在每次混沌优化后, 自适应调整KCmax, 直到新解优于原解或达到设定的最大迭代次数为止。
2.3 Pareto最优解选择策略
MACSFLA根据网格粒子密度值, 在Archive集中为每只青蛙选择一个Pareto最优解进行更新。对于网格Gk, 如果Dk>0, 则其网格适应度值f (Gk) 可以定义为Dk的倒数, 即:
MACSFLA根据网格f (Gk) , 采用轮盘赌的方式为每只青蛙选择一个网格, 并从网格中随机选择一个个体作为最优解进行更新。该Pareto最优解选择策略使得Archive集中Dk越小的网格被选择的概率越大, 确保了Pareto最优解多样性。
2.4自适应混沌混合蛙跳算法实现流程
MACSFLA算法流程可以描述为:
3性能验证
3.1评价指标和测试函数
本文采用文献[14]中的世代距离指标GD和多样性指标Δ进行算法性能评价, 并分别采用文献[1]和文献[4]中的KUR、ZDT1、ZDT2、ZDT3和ZDT6多目标函数进行实验仿真, 其中, KUR函数的n=3, 决策变量取值范围为 (-5, 5) , 其他4个函数的n=30, 决策变量取值范围为[0, 1]。
MACSFLA参数设置如下:N=200, Q=20, Kmax=10, Tmax=500, ξ1=0.2, ξ2=0.8, c1=3, rmin=0.35, rmax=0.95。
3.2实验结果及其分析
分别采用MACSFLA算法、NSGA-Ⅱ算法和MOPSO算法对测试函数进行实验, 每种算法独立测试30次, 表1给出了世代距离指标GD对比结果, 表2给出了多样性指标Δ对比结果 (分别取最大值M和平均值AV) , 图1给出了通过MACSFLA优化后测试函数Pareto前端和理论Pareto前端仿真图。
从表1, 表2和图1可以看出, MACSFLA能够有效地获得Pareto前端, MACSFLA得到的Pareto前端更加均匀, 世代距离指标GD和多样性指标Δ要优于其他两种算法, 而且对于Pareto前端两端端点的逼近程度很高, 特别是对于不连续多目标函数ZDT3, MACSFLA得到的Pareto前端粒子均匀分布在理论Pareto前端上。
5结语
提出了一种新的基于自适应混沌混合蛙跳算法的多目标函数优化算法。对混合蛙跳算法权重因子进行了改进, 设计了基于Pareto支配能力的SFLA子族群划分策略, 提出了自适应网格密度机制动和自适应混沌优化技术, 最终实现了多目标优化问题求解。仿真结果表明, 与MOPSO和NSGA-Ⅱ相比, MACSF-LA在Pareto最优解集均匀性和多样性上有明显优势。
摘要：针对多目标优化问题提出一种自适应混沌混合蛙跳算法MACSFLA (Adaptive chaos shuffled frog leaping algorithm for multiobjective optimization) 。使用动态权重因子策略以提高混合蛙跳算法SFLA (Shuffled Frog Leaping Algorithm) 收敛效率, 引入基于Pareto支配能力的SFLA子族群划分策略, 使得SFLA能够应用于多目标优化问题。在此基础上, MACSFLA首先利用SFLA快速寻优能力接近理论Pareto最优解, 然后采用自适应网格密度机制动态维护外部存储器Pareto最优解规模, 并使用自适应混沌优化技术改善Pareto最优解集样本多样性, 最后利用Pareto最优解选择策略为青蛙种群选择最优更新粒子。多目标函数测试实验结果表明, 与MOPSO和NSGA-Ⅱ相比, MACSFLA在Pareto最优解集均匀性和多样性上有明显优势。
多目标自适应遗传算法 第6篇
针对这些问题,本文对基于空间全局单位化的蚁群算法[1]中涉及的全局挥发因子α引入了自适应策略,形成参数自适应的蚁群算法,以此克服停滞的现象,并通过加权的方法,将多目标问题转化为单目标问题,通过对多目标问题的测试,证明了算法的性能良好。
1全局信息素挥发因子的自适应策略
在文献[1]中提出的基于空间全局单位化的蚁群算法中,全局信息挥发因子ɑ 和局部信息挥发因子ρ的选择是影响算法行为和性能的关键所在,当问题规模比较大时,由于信息量的挥发因子的存在,使那些从未被搜索到的解上信息量会减小到接近于0,降低了算法的全局搜索能力,而且全局信息挥发因子ɑ 过大时,当解的信息量增大时,以前搜索过的解被选择的可能性过大,也会影响到算法的全局搜索能力,通过减小全局信息挥发因子ɑ 虽然可以提高的全局搜索能力,但又会使算法的收敛速度降低。因此,在本文中对全局信息挥发因子ɑ 引入一种自适应策略,ɑ 的值如式(1)。
式中ɑ ∈[ɑmin, ɑmax],且ɑmin,ɑmax分别表示ɑ 的最小值与最大值,根据不同的问题中取值不同;I表示连续找到相同解的次数;r(t)与q(t)的取值如式(2)和(3)所示。
式中r∈[rmin,rmax],rmin,rmax分别表示r的最小值与最大值。
式中q∈[qmin,qmax],qmin,qmax分别表示q的最小值与最大值。
从式(1)、(2)和(3)可以发现,如果确定了ɑ 、r、q的上下界,并确定了Iɑ的值ɑ 就可以在变化区间内,根据算法找到的最优解的情况自适应的调整,并且若算法连续迭代Iɑ次找到的解相同,即在算法处于暂时的停滞状态,此时ɑ 就会按上式(1)来自适应的调整取值,以使算法尽快跳出暂时停滞,继续进行优化找到更优解,防止算法陷入局部最优,并缩短迭代次数。
对于参数自适应的蚁群算法,在全局离散化思想,算法的初始化,蚂蚁的状态转移规则与信息素的局部更新规则四个过程延续文献[1]的做法,而在信息素的全局更新这一步,对全局挥发因子ɑ 引入自适应策略,如式(1),从而使算法具有更强的搜索全局最优解的能力。
2多目标优化试验
2.1优化目标函数
为了检验参数自适应的蚁群算法能否有效的应用于多目标函数优化问题,在多目标函数优化问题中能否表现出算法优良的性能,选取表1中多目标优化函数作为测试函数进行试验。
首先,选用简单加权的方法将多目标优化问题转化为单目标优化问题的形式,如式(4),然后再利用参数自适应的空间全局单位化蚁群算法的思想进行优化。
式中ω1+ω2=1,在本次试验中取ω1=0.5,ω2=0.5。
2.2参数研究
为了对多目标优化问题进行优化,以表1中多目标函数优化问题MOP1为例,对算法参数取值做了研究如表2,算法迭代100次停止,表2中平均最优值是指当参数取值确定时算法运行10次所得到解的平均值。
表2中数据显示:对于多目标函数的优化问题,本文算法在表3的参数取值下能表现出较好的性能,并且算法稳定,所以对多目标函数优化问题MOP1和MOP2,选择表3中的参数取值进行优化。
2.3优化结果及结果分析
本文蚁群算法对多目标函数优化问题MOP1和MOP2进行优化,得到了如表3的优化结果,优化过程中适应值的变化如图1和图2,优化过程中两个目标函数的函数值的变化如图3和图4 。
从图1、图2、图3和图4中可以看出参数自适应的蚁群算法能够在迭代10代就能找到使两目标函数同时最优的值,整个过程中克服停滞现象,并且两个函数的优化能同步进行,在表4中,对MOP1问题的优化结果与文献[2]中的优化结果作了比较,从表中数据可以看出虽然两算法的适应值和运行所用时间相同,但是本文算法找到的两个目标函数值更加接近理论最优值
3结束语
本文对文献[1]中提出的蚁群算法作了改进,对全局信息挥发因子ɑ 引入一种自适应策略,克服了优化过程中陷入局部最优的现象,通过简单加权的方式将多目标函数优化问题转化为单目标问题,在优化过程中通过多次试验比较,选取一组较稳定的参数取值,通过试验结果比较,说明本文的改进策略具有较好的效果,也可以解决简单的多目标函数优化问题。
参考文献
[1]周晓静,吕翠英.基于全局单位化的连续函数的改进蚁群算法[J].微电子学与计算机,2009,4(26):54-57.
[2]岳凤,刘希玉.自适应调整挥发系数的逆向蚁群算法[J].计算机工程与应用,2008,44(3):105-107.
[3]段海滨,马冠军,王道波,等.一种求解连续空间优化问题的改进蚁群算法[J].系统仿真学报,2007,19(5):974-977.
[4]熊俊文.多目标优化方法研究及在工程中的应用[D].广州:华南理工大学,2005.
多目标自适应遗传算法 第7篇
关键词：背包问题,遗传算法,鲁棒性,贪婪算法
0 引言
1975年, Holland等人基于自然界的遗传和自然选择, 提出了全局优化算法———遗传算法[1]。遗传算法具有鲁棒性强, 适用于并行计算以及高效性、实用性等显著特点, 在各领域得到了广泛应用, 取得了良好效果, 并逐渐成为重要的智能算法之一。随后, 自适应调整交叉率和变异率被应用到遗传算法中, 较好地提高了算法的收敛速度, 但算法的鲁棒性仍十分具有挑战性[5]。
本文将自适应遗传算法应用于求解0-1背包问题, 并利用贪婪算法对不可行解和背包资源利用不足的问题进行修复, 提出了一种基于贪婪算法的改进的自适应遗传算法。数值实验表明此算法在求解0-1背包问题时非常有效。
1 背包问题
若有n个不同的物体, 对于物体j, 其重量为wi, 价值为pj, b是背包的最大容量, 背包问题就是要在不超过背包承受重量的前提下, 使装入背包的物品价值最大, 则背包问题的数学模型如下:
其中xj为0-1决策变量 (当物品j被选择时xj=1, 否则xj=0) 。
2 价值密度及贪婪算法
第j个物体的价值密度midu (j) 定义为:midu (j) =pj/wj。按价值密度的次序逐一选取物体装入背包, 若两个物体的价值密度相同则重量大的排在前面, 由此背包价值增大, 直到背包不能装入任一物体为止, 此种排序方法还可以提高贪婪算法的质量。
3 改进的自适应遗传算法
3.1 编码修复
算法采用二进制编码, 不可行性的初始解主要有:第一, 构造初始种群时产生的不可行解;第二, 自适应遗传操作 (如交叉和变异算子) 导致的不可行解。
修复不可行解的贪婪算法[4]:将已装入背包中的物品按照价值与重量之比的升序排列, 依此顺序去掉物品, 保证背包不超重。
3.2 适应度函数
由于适应度值是群体中个体生存机会选择的唯一确定性指标, 所以适应度函数的形式直接决定着群体的行为进化。为了直接将适应度函数与群体中的个体优劣度量相联系, 在遗传算法中规定适应度为非负, 并且在任何情况下总是越大越好。由于本算法对每个个体使用了贪婪算法修正, 即保证了不会产生无效染色体, 所以在进行个体适应度评价时无须引用惩罚函数项, 而是直接用目标函数值作为适应度函数值, 即。
3.3 初始种群的产生
随机产生初始群体p= (p1, p2, …, ppopsize) , popsize是种群规模, 并对不可行解进行修复, 再用贪婪算法产生一个近似最优解代替初始种群中适应度最小的个体, 得到初始种群p′= (p′1, p′2, …p′popsize) 。
3.4 选择操作
先计算群体中个体所对应的适应度总和 , 再计算个体相对的适应度, 即个体遗传到下一代的概率, 最后产生一个0到1之间的随机数, 根据此随机数来确定各个个体被选中的次数, 并将上一代的最优个体直接进入下一代, 这样, 每进化一代, 下一代的最优个体一定不劣于上一代[6]。
3.5 自适应的交叉和变异算子
在遗传算法中, 交叉和变异是影响GA行为和性能的关键。本文所使用的交叉与变异率公式如下:
fmax为群体中适应度的最大值, favg为每代群体适应度的平均值, f′为要交叉的两个个体中适应度的较大值, f为要变异个体的适应度。
4 算法流程
在新算法中, 当进行交叉和变异操作后就要进行不可行解的修复, 由此可以保证父代产生的子代都是比较优秀的, 也可以加快算法向最优解的方向前进。
5 仿真实验
背包容量为1000, 50个物品的重量为
W=[80 82 85 70 72 70 66 50 55 25 50 55 40 48 50 3222 60 30 32 40 38 35 32 25 28 30 22 50 30 45 30 60 5020 65 20 25 30 10 20 25 15 10 10 10 4 4 2 1],
对应的价值为V=[220 208 198 192 180 180 165 162160 158 155 130 125 122 120 118 115 110 105 101 100100 98 96 95 90 88 82 80 77 75 73 72 70 69 66 65 63 6058 56 50 30 20 15 10 8 5 3 1];
设定为群体大小M=50, 终止进化代数T=200, 各种参数设定为k1=0.8, k2=0.6, k3=0.50, k4=0.07, 数值结果如表1所示。
从表可以得出, 新算法在解的质量和求解速度方面都有较大改进。
6 结束语
本文对基本的自适应遗传算法加以改进, 引入了新的交叉算子和变异算子, 并利用贪婪算法对不可行解进行修复。通过算例的数值试验, 新算法在解决背包问题时获得了较好的解的质量和较快的求解速度。因此, 采用上述改进的交叉率和变异率无论在收敛速度上还是在对最佳适应度的搜索上均保持了较高的鲁棒性。因此, 将此算法应用于求解0-1背包问题, 是一次十分有意义的尝试。
参考文献
[1]王小华, 曹立明.遗传算法—理论, 应用与软件实现[M].西安:西安交通大学出版社, 2002.
[2]金晶, 苏勇.一种改进的自适应遗传算法[J].计算机工程与应用, 2005 (18) :64-69.
[3]严太山.用基于贪婪算法的混合遗传算法求解0/1背包问题[J].研究与开发, 2007 (8) .
[4]黄与林.0-1背包问题的贪心算法[J].鄂州大学学报, 2006, 13 (6) :38-40.
[5]李肯立, 李庆华, 戴光明等.背包问题的一种自适应算法[J].计算机研究与发展, 2004, 41 (7) .
多目标自适应遗传算法 第8篇
数据挖掘 (Data Mining) 是从大量的无规律的繁杂数据中抽取出潜在的、不为人知的有用信息、模式和趋势的过程。对信息社会中数据和数据库的爆炸式增长, 人类分析数据和从中提取有用信息的能力远远不能满足实际需要。当前, 很多成功的企业正在应用数据挖掘进行关联规则的提取来帮助它们更好地制定决策, 利用功能强大的数据挖掘技术, 可以把数据转化为有用的信息以帮助制定决策, 从而在市场竞争中获得优势地位。
关联规则挖掘是数据挖掘中一个很重要的研究课题。近年来, 人们研究了许多挖掘算法。Apriori算法是关联规则挖掘的经典算法, 但计算复杂度高, 不能满足对大规模数据库的实时挖掘要求;Park etal提出了DHP算法, 可是修整和剪枝属性在许多实际应用中是不切实际的;分割算法减少了I/O消耗, 但在处理高维项目集事件中存在问题;FP-growth算法创建了一种关系紧密的树结构, 有助于候选项目集的产生, 但需要遍历整个数据库, 计算量大, 对大规模数据库而言, 效率非常低。
遗传算法 (Genetic Algorithm, GA) 是一种基于群体的进化算法, 具有很强的随机性、鲁棒性和隐含并行性, 能快速、有效地进行全局优化搜索是处理大规模数据项目集的有效方法。但是遗传算法的易早熟和局部收敛的问题难以解决。本文将模拟退火 (Simulated Annealing, SA) 机制引入遗传算法, 提出了一种基于自适应策略的动态模拟退火遗传挖掘算法 (Dynamic Simulated Annealing Genetic Mining Algorithm, DSAGMA) 的挖掘算法。DSAGMA算法是将GA和SA算法相结合而构成的一种优化算法。GA的局部搜索能力较差, 但把握搜索过程总体的能力较强;而SA算法搜索总体的能力较差, 但把握局部搜索的能力较强。
1 问题的定义
关联规则是数据项之间存在的规则, 是在同一事件中出现的不同项之间的相关性。为了便于分析问题, 我们特作以下形式化定义:
定义1关联规则三元组Rule= (I, T, R)
其中, I={i1, i2, ..., in}是数据项集, T={T1, T2, ..., Tm}是事务数据集, Tk (1≤k≤m) 是事务数据集T的数据项, 也是数据项集I中的数据项。R表示的关联规则是形如X→Y的蕴涵关系, X∪I, Y∪I, 并且X∩Y=。
定义2支持可信度二元组SC= (S, C)
关联规则X→Y的支持度和可信度分别用S (X→Y) 和C (X→Y) 表示。
支持度反映了规则X→Y在T中所占的比例, 可信度说明X→Y成立的必然程度, 表明由规则的前提导致结论的可信程度。
2 DSAGMA算法的框架
我们将模拟退火和遗传算法进行融合, 提出了一种基于动态模拟退火遗传算法DSAGMA的挖掘算法。DSAGMA算法的设计框架如下描述:
2.1 染色体编码
在DSAGMA算法编码问题中, 字符串代表染色体, 它是遗传信息传递的载体, 串上的每个位置的元素代表遗传因子。采用实数数组的方法进行编码, 实数数组的元素个数与事务数据库中的字段的个数相对应, 元素值代表了字段的属性值。DSAGMA算法中的个体A可以描述为如下染色体串:A=A[1]A[2]...A[n], 其中n为染色体的长度。
2.2 适应度函数
本文设计的适应度函数为:
Fi (X→Y表明:在各种规则的竞争中, 只有支持度和可信度都高才有可能生存下来。
2.3 选择算子
选择是将父代的个体信息传递到子代。每代中的每一个个体按照适应度函数的大小决定它能够复制到下一代的概率。通过选择, 体现了“适者生存, 优胜劣汰”的进化原则。我们采取“轮盘赌”式的选择策略, 使得群体中的优秀个体数目不断增加, 整个进化过程朝着更优解的方向进行。
2.4 交叉算子
交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。交叉概率PC直接影响算法的收敛性。PC越大最佳个体的遗传模式被破坏的可能性越大;PC过小会使算法搜索过程缓慢。本文定义的交叉算子如下:
(1) 计算交叉概率PC,
其中, Fimax (X) 为群体中最大的适应度值;Fimix (X) 为群体中最小的适应度值;Fi (X) 为每代群体的平均适应度值
(2) 采用两点交叉的方法, 父个体V1和V2经交叉算子后分别得到子个体V1′和V2′。
(3) 计算V1′和V2′的适应度f (V1′) , f (V2′) , 若min{1, exp (- (V′) -f (V) /Tk) }>random[0, 1], 则接受新解。
2.5 变异算子
变异操作的作用是在种群出现局部收敛时通过变异算子的突变, 使整个种群能保持一定的多样性。变异概率Pm的选择是影响遗传算法行为和性能的关键所在。Pm过小不易产生新的个体结构;若Pm过大, 则遗传算法变成纯粹的随机搜索。本文定义的变异算子如下:
(1) 计算变异概率Pm
其中, Fi (X) 为群体的平均适应度, PC为交叉概率。
(2) 采用高斯变异的方法, 父个体V1和V2经高斯变异后分别得到子个体V1′和V2′。
(3) 按照交叉算子的方法决定是否接受变异后的解。
2.6 DSAGMA算法流程
DSAGMA算法流程如下: (1) 初始化控制参数:群体规模M, 初始温度T0, k=0; (2) 对个体进行编码, 并随机产生初始种群P0; (3) 计算个体支持度、可信度和适应度值;将结果添加到有趣规则表, 并将大于最小阈值的规则添加到关联规则表中; (4) 在当前温度Tk下, 分别对群体进行选择, 交叉, 变异操作得到下一代群体; (5) 当满足终止条件时, 退火过程自然结束, 从关联规则表中输出本次挖掘结果;否则, 返回到步骤 (3) 。
3 结束语
本文利用动态模拟退火遗传挖掘算法构造了数据挖掘中的关联规则挖掘的模型, 通过支持度和可信度的对比, 发现隐藏在数据库中的规律。本文设计的DSAGMA算法显示了DSAGMA算法能弥补基于传统遗传算法的挖掘方法的缺点。
摘要：关联规则挖掘是数据挖掘中一个很重要的研究课题。提出了一种基于自适应策略的动态模拟退火遗传挖掘算法。实验结果证明它能弥补基于传统遗传算法的挖掘方法的缺点。
多目标自适应遗传算法 第9篇
1 无功优化的数学模型
本文从经济性角度出发, 以系统的有功网损最小作为优化目标, 其优化模型可表示为
式中:NK为支路集合;Gk (i, j) 为支路k的电导;θij为节点i与节点j之间的电压相角差。
等式约束条件为:
式中:QGi、QCi、QDi分别为发电机节点注入无功功率、负荷节点无功功率和补偿节点的补偿无功功率;NPQ为PQ节点的集合;Gij和Bij为节点导纳阵的系数;θij同式 (1) 。
不等式约束条件:
1) 控制变量约束有:
式中:UGi、UGimax、UGimin分别为发电机的端电压及上、下限;QCi、QCimax、QCimin分别为无功补偿容量及上、下限;Tki、Tkimax、Tkiminx分别为变压器分接头的位置及上、下限;NG、NC、NT、N分别为发电机节点数、补偿电容器节点数、变压器支路数和总的节点数。
2) 状态变量约束有:
式中:QGi、QGimax、QGimin分别为发电机无功出力及上、下限;Ui、Uimax、Uimin分别为负荷节点i的电压及上、下限;NG、N分别为发电机节点数和总的节点数。
在不等式约束中, 状态变量不等式约束以惩罚项形式处理, 则目标函数式 (1) 构成一个新的目标函数f, 可表示为
λ1 (t) 和λ2 (t) 罚因子取值是否恰当, 将影响算法的收敛速度。因此, 本文根据状态变量不等式约束在优化计算过程中越界量的大小, 动态地调节罚函数, 这样可以有效提高算法的收敛速度和精度。λ (t) 的数值随迭代次数而改变, 若t为迭代次数, 则本文取
2 改进云自适应遗传算法
2.1 基本遗传算法
遗传算法的基本流程如下:
1) 初始化种群, 设置相关参数, 对个体进行编码;
2) 设计一个适应度函数, 对种群中的个体进行评估;
3) 进行选择、交叉和变异等遗传操作;
4) 判断是否到达最大进化代数, 如到达, 则停止进化, 输出最优解, 否则转到步骤 (2) , 继续进化。
2.2 云理论
2.2.1 云模型
云模型由李德毅等人提出[5], 是一种定性知识描述和定型概念与其定量数据之间的不确定性转换模型, 主要反映客观世界、人类知识等领域中概念的模糊性和随机性。
定义1:云和云滴[6], 设U为用数值表示的定量论域, C是U上的定性概念, 映射u:U→[0, 1], x∈U, x→u (x) , 其中, 定量值x∈U是定性概念C的一次随机实现, u (x) ∈[0, 1]是x对C的确定度, 它是一个随机数, 具有稳定倾向性, 则x在论域U上的分布称为云, 记为云C (x) , x就称为一个云滴。
定义2:正态云, 设U为用数值表示的定量论域, C是U上的定性概念, 定量值x∈U是定性概念C的一次随机实现, 且x∈U (Ex, En'2) , 其中En'~N (En, He2) , 即, 且x对C的确定度, 则π称H ex在论域U上的分布为正态云。正态云模型的三个参数如图1所示。
2.2.2 云发生器
本文要用到的云发生器是X-条件云发生器[8]。
X-条件云发生器是指给定云的三个参数 (Ex, En, He) 和论域U上的某个值x0产生云滴 (x0, u) 的云发生器。
input:{Ex En He}, n, x0//参数和云滴数
output:{ (x0, u1) , … (x0, un) }://生成符合条件的云滴
2.2.3 云自适应遗传算法的步骤
云自适应遗传算法的具体步骤如下:
1) 云自适应交叉概率新算法步骤:
2) 云自适应变异概率新算法步骤:
云自适应交叉和变异概率如图2所示。
2.3 收缩搜索
在模拟农夫捕鱼算法 (SFOA) 中, 假设i渔夫经过m次移动搜索后 (m=0, 1, 2, …M;M为正整数, m=0表示i渔夫处于初始位置) , 则该渔夫当前位置为Pm (i) 。
式中:
则i渔夫没有新移动收索的位移点, 此时, i渔夫选择停在当前位置Pm (i) 处, 并以该点为中心, 以另一种方式建立方体, 同时在停留处的前后上下左右撒网各一次。此时得到关于点Pm (i) 的下网点集为
式中:l'j (-) =αlj (-) ;l'j (+) =αlj (+) ;0<α<1;α为收缩系数。所以把这一搜索方式定义为收缩搜索。
Pc—交叉变异概率;Pm—变异概率;fmax—种群最大适应度;f軃—平均适应度;f为变异个体的适应度;f′—交叉两个体适应度的较大值。
2.4 改进云自适应遗传算法的流程图
把收缩搜索的思想引入云自适应遗传算法, 从而提出改进云自适应遗传算法, 其流程如图3所示。
3 算例分析
3.1 典型函数优化仿真
3.1.1 测试函数
验证算法的性能, 本节选取4个典型的函数进行仿真测试, 验证算法的有效性和优越性。
f1:Ackley函数
函数f1的最优状态和最优值分别为点X*= (0, 0, …, 0) 和f1 (X*) =0
f2:Beale函数
函数f2的最优状态和最优值分别为点X*= (3, 0.5) 和f2 (X*) =0
f3:Branin函数
函数f3的最优状态和最优值分别为点X*= (-π, 12.275) , (π, 2.275) , (9.424 78, 2.475) 和f3 (X*) =0.397 887
f4:Bohachevsky函数
函数f4的最优状态和最优值分别为点X*= (0, 0) 和f4 (X*) =0
3.1.2 仿真结果
对以上4个典型测试函数分别用GA算法和ICAGA算法进行10次函数优化实验, 并对实验结果进行分析。算法参数分别设为:种群规模均为100, 最大进化代数也均为100, 终止条件是最大进化代数;其中GA的Pc=0.9, Pm=0.1。仿真结果的两种算法性能对比如表1所示。函数仿真对比如图4—图7所示。
从表1和图4~7可以看到, 对f1和f3, ICAGA在计算精度上要优于GA, ICAGA在收敛速度上也要优于GA;对于f2, ICAGA算法依然表现了良好的收敛性能;对于f3, 在仿真实验中, GA完全不能收敛;此时ICAGA在精度和跳出局部搜索能力上的优势明显得以体现, 几乎达到了零误差, 取得了非常好的收敛速度和计算精度。
3.2 IEEE-14和IEEE30节点系统仿真
在相同条件下, 分别在IEEE14和IEEE30节点系统运行标准GA (遗传算法) 、AGA (自适应遗传算法) 、CAGA (云自适应遗传算法) 和ICAGA (改进云自适应遗传算法) , 网损优化曲线如图8、图9所示。
从图8、图9可以看出, ICAGA算法的收敛速度和收敛精度都优于另外3种算法, ICAGA算法的收敛性更佳, 能够跳出局部最优解, 比另外3种算法更加接近全局最优解。电压曲线比较如图10和图11所示。
从图10和图11可以看出ICAGA算法的电压曲线更趋合理, 没有电压越限。
对4种算法分别进行10次计算, 得到目标函数的优化解如表2和表3所示。表中网损数据为标幺值, 基准功率为100 MVA。
从表2、表3可以看到, ICAGA计算得到的平均网损小于另外3种算法, 能够跳出局部最优解, 更加接近目标函数的全局最优解。
4 结论
1) 改进云自适应遗传算法 (ICAGA) 是在传统的遗传算法的基础之上引入云理论, 由X条件发生器自适应调整交叉变异概率, 使交叉变异概率既具有传统AGA的趋势性, 满足快速寻优, 又具有随机性。当种群适应度最大时并非绝对的零值, 有利于提高种群多样性和改善避免陷入局部最优的能力, 然后用模拟农夫捕鱼算中的收缩搜索来对云自适应遗传算法进行改进。
2) 通过4个典型测试函数, 及以网损最小为目标函数, 对标准IEEE14节点系统和IEEE30节点系统进行仿真计算, 结果表明ICAGA算法在跳出局部最优解, 寻找更好的全局最优解方面有很大的优势, 收敛性能好, 解的质量高, 较稳定。同时在进一步降低网损方面, 具有很强的实用性和可行性。
参考文献
[1]白云, 徐刚刚, 宋阳.基于改进社会认知算法的电力系统多目标无功优化[J].黑龙江电力, 2012, 12 (1) :21-24.BAI Yun, XU Ganggang, SONG Yang.Multi-objective reactive power optimization based on modified society cognitive optimization for electric power system[J].Heilongjiang Electric Power, 2012, 12 (1) :21-24.
[2]祝洪博, 徐刚刚, 海冉冉, 等.基于云自适应梯度粒子群算法的无功优化[J].电网技术, 2012, 31 (2) :51-56.ZHU Hongbo, XU Ganggang, HAI Ranran, et al.Reactive power optimization based on cloud adaptive gradient particle swarm optimization[J].Power System Engineering, 2012, 31 (2) :51-56.
[3]海冉冉.《基于云自适应遗传算法的优化问题研究》[M].吉林:东北电力大学, 2013.HAI Ranran.Research on the optimization based on cloud adaptive genetic algorithm[M].Jilin:Northeast Dianli University, 2013.
[4]袁晓辉, 王乘, 张勇传, 等.遗传优化算法在电力系统中的应用[J].电网技术, 2004, 28 (19) :14-19.YUAN Xiaohui, WANG Sheng, ZHANG Yongchuan, et al.Application of genetic algorithm in power system[J].Power System Engineering, 2004, 28 (19) :14-19.
[5]李德毅, 杜!.不确定性人工智能[M].北京:国防工业出版社, 2005.LI Deyi, DU Yi.Artificial intelligence with uncertainty[M].Beijing:National Defend Industry Press, 2005.
[6]李德毅, 孟海军, 史雪梅.隶属云和隶属云发生器[J].计算机研究与发展1995 (6) :15-20.LI Deyi, MENG Haijun, SHI Xuemei.Membership clouds and membership cloud generators[J].Computer R&D, 1995 (6) :15-20.
[7]陈建荣.群智能优化算法研究及其应用[D], 广西:广西民族学院, 2009.CHEN Jianrong.Study and application of warm intelligence optimization[D].Guangxi:Guangxi University for nationalities, 2009.
