多峰值函数优化问题的免疫遗传算法求解

使用遗传算法进行优化问题求解的技巧遗传算法是一种模拟自然进化过程的优化算法，被广泛应用于各种优化问题的求解中。

它通过模拟自然界中的遗传、交叉和变异等过程，不断演化出更优解的种群。

本文将介绍使用遗传算法进行优化问题求解的一些技巧。

一、问题建模在使用遗传算法求解优化问题之前，首先需要将问题进行合理的建模。

建模的关键是定义适应度函数，即评价解的好坏程度的函数。

适应度函数应该能够准确地反映出问题的目标和约束条件。

在建模时，还需要确定问题的变量范围、约束条件等。

二、编码与解码遗传算法对问题的解进行编码，将解表示为染色体或基因的形式。

编码的方式有很多种，常见的有二进制编码、实数编码和排列编码等。

编码的选择应根据问题的特点和求解的要求进行合理的选择。

解码是将编码后的染色体或基因解码成问题的实际解。

解码过程应与编码过程相逆，保证解码后的结果能够准确地表示问题的解。

三、种群初始化种群初始化是遗传算法的起点，它决定了算法的初始状态。

种群的初始化应该尽量保证多样性，避免陷入局部最优解。

常见的初始化方法有随机初始化和启发式初始化等。

在初始化时，还可以利用问题的特点进行有针对性的初始化，提高算法的效率。

四、选择操作选择操作是遗传算法中的关键步骤，它决定了哪些个体能够生存下来并参与后续的交叉和变异操作。

选择操作的目标是根据个体的适应度值，按照一定的概率选择优秀个体，并保留下来。

常见的选择方法有轮盘赌选择、锦标赛选择和排名选择等。

选择操作应该保证优秀个体有更高的生存概率，同时也应该给予较差个体一定的生存机会，以保持种群的多样性。

五、交叉操作交叉操作是遗传算法中的重要步骤，它模拟了自然界中的基因交叉过程。

交叉操作通过将两个个体的染色体或基因进行交叉，产生新的个体。

交叉操作的目标是将两个个体的优秀特征结合起来，产生更优解的个体。

常见的交叉操作有单点交叉、多点交叉和均匀交叉等。

在进行交叉操作时，应该根据问题的特点和求解的要求进行合理的选择。

!第"#卷第$期郑州大学学报!理学版"%&’("#)&($ !$#*+年,月-./012340&56278.!)9:.;<7.=>."-52.$#*+程序性细胞死亡进化算法的实现刘作军*!$!!张!晓*!!陈玲玲*!$!!张!燕*!$!*.河北工业大学控制科学与工程学院!天津C##*C##$.智能康复装置与检测技术教育部工程研究中心!天津C##*C#"摘要!为了克服遗传算法易陷入早熟收敛的缺陷’提出一种程序性细胞死亡进化算法.新算法将生理学中程序性细胞死亡的C个关键控制基因以算子的方式引入到遗传算法中’即算子<1>@C和<1>@B协同完成选择操作’而算子<1>@A单独执行精英策略’提高了收敛效率.经典的测试函数和K;L问题的实验结果表明’与其他遗传算法对比’该算法收敛速度快’寻优性能好.关键词!程序性细胞死亡#遗传算法#进化算法#精英策略#协助进化中图分类号!K L*+文献标志码!M文章编号!*,?*@,+B*!$#*+"#$@##,C@#,!"#!*#(*C?#"N O.7P P2.*,?*@,+B*($#*?$$A$%引言遗传算法!3121:7<9’3&S7:0F’D M"由美国f&’’92>教授于*A?"年提出’是一种智能优化算法.由于遗传算法不依赖于问题具体的信息’且具有很强的全局搜索能力’所以广泛应用于函数优化)故障诊断)车间调度)旅行商问题等众多领域**Q?+’但其具有易陷入局部最优解的缺陷.针对传统遗传算法的不足’各种改进算法相继被提出’其中文献*$Q*#+通过结合聚类)量子理论)生物免疫概念)小生境技术或其他进化算法等思想对遗传算法进行了改进.例如’文献*A+提出了基于聚类划分子种群的多种群遗传算法’将满足约束条件的个体根据其特征划分到不同种群中’避免所有子群陷入局部最优#文献**#+通过带精英策略的快速非支配排序遗传算法在多目标无功优化中的应用’保留了父代中的优良个体.而文献***Q*B+通过设计交叉)变异操作对遗传算法进行改进.例如’文献**B+采用自适应交叉变异’最大限度地保留了父代的优良特性’增强了算法的寻优能力.本文提出了程序性细胞死亡进化算法!RS&3S9F F1><1’’>19:018&’5:7&29S H9’3&S7:0F’L b W M".首先’程序性细胞算子<1>@C和<1>@B协同完成选择操作’程序性细胞算子<1>@A执行精英策略’目的是引导种群中的个体朝着最优解方向进化#其次’经过自适应交叉)变异操作**B+’算法运行到一定代数后’结合聚类思想将种群划分为多个子种群#最后’求解多峰值函数优化问题及经典K;L问题’结果表明了该算法的有效性.&%程序性细胞死亡进化算法&,&%程序性细胞死亡原理文献**"+描述了程序性细胞死亡原理(程序性细胞死亡是一个具有遗传性和程序性特征的过程’在生物体中能保持细胞的生死动态平衡.目前最新的研究进展是<1>@B激活<1>@C的机制’该机制是清华大学施一公实验室发现的’即<1>@B以八聚体的形式存在’与两个<1>@C结合激活<1>@B的功能’而<1>@B的功能又和<1>@A有关联’这样就形成一个精确的调控系统**,+.在发育过程中’细胞只有在正确的时间发生正确的分化’才能产生正确的细胞类型.人体内的所有细胞根据特征的区别形成各种各样的组织和器官’如肌肉)血液)心脏和神经系统.细胞在正确的时间才发生分化收稿日期!$#*?@#?@$+基金项目!国家自然科学基金项目!,**?B##A"#河北省教育厅科研计划项目!$#*B#"A".作者简介!刘作军!*A?*&"’男’天津人’教授’主要从事智能算法研究’=@F97’(a7545&O52I01T5:.1>5.<2#通信作者(张晓!*AA*&"’女’河北衡水人’硕士研究生’主要从事遗传算法研究’=@F97’(*$+"B#B"?"IJJ.<&F.郑州大学学报!理学版"第"#卷对遗传算法的启发是(在进化过程中’个体只有到特定的代数才能正确地对种群进行划分’产生具有相同特征的子种群.本文结合程序性细胞死亡原理改进遗传算法’设计了程序性细胞死亡进化算法.该算法在遗传算法操作的基础上添加C 个算子参加运算(算子<1>@C 和<1>@B 参与遗传算法的选择过程’而算子<1>@A 参与精英策略.图&!子种群和优良种群的关系()*+&!K 01S 1’9:7&2P 07R T1:\112P 5T R&R5’9:7&2P92>3&&>R&R5’9:7&2P&,’%多种群协同进化构建了一个多种群协同进化模型.首先采用随机法产生初始群体.’进行遗传操作’直到特定的代数#然后将种群通过对所有个体聚类的方法分解为2个子种群!.*’.$’/’.2"’在进化过程中所有子种群协同进化’在各自种群的内部单独完成选择)交叉和变异操作’在各个子种群中选择有限的优良个体作为精英个体组成优良种群..’子种群可以从优良种群中获取其他种群的精英个体’以改善本种群的品质’子种群和优良种群的关系如图*所示’这种种群结构既增加了种群多样性’又提高了算法的收敛速度.&,/%算子操作&,/,&%选择%!模拟$个<1>@C 结合激活<1>@B 功能的生理过程’在L b W M 算法的选择过程中’<1>@C 算子根据轮盘赌选择分别对子种群中的个体进行$次标记’每次标记的结果都是将适应度高的个体标记为$*%’适应度低的个体标记为$#%.$次<1>@C 算子标记过后’<1>@B 算子将标记为$##%的个体淘汰’标记为$**%的优秀个体采用<1>@A 算子保存’标记为$#*%或$*#%的大部分个体保留在原子种群中便于后续的进化操作’<1>@B 共有C 种状态(<1>"B !*+"-#’<1>"C "*!*+")<1>"C "$!*+"’*’<1>"C "*!*+"-<1>"C "$!*+"-*’4*’<1>"C "*!*+"-<1>"C "$!*+"-#{’!*"式中(*+是子种群中的第+个个体#<1>@C@*!*+"是对*+执行第*次选择#<1>@C@$!*+"是对*+执行第$次选择#<1>@B Z #时’不对个体进行任何操作#<1>@B Z *时’<1>@A 被激活执行精英保留操作#<1>@B ZQ *时’删除个体*+.&,/,’%交叉%遗传算法中起核心作用的是遗传操作的交叉算子.标准遗传算法采用的是一个恒定的交叉概率’而恒定不变的交叉概率存在自身缺陷’即经过几代的进化后’在算法运行后期种群内部的个体绝大多数是适应度高的个体’所以适应度高的个体作为父代的概率要大’从而被破坏的概率变大.针对恒定的交叉概率带来的不足’本文采用自适应交叉概率**?+’即在进化的过程中使交叉概率随着适应度值的变动自动调整’在进化后期避免了破坏种群中的优秀个体.自适应交叉概率的调整公式**++为.>-.>*4.>*4.>$A F 9j 4A 983.!A 4A 983"’A ,A 983’.>*’A YA 983{’!$"式中(A F 9j 为群体中最大的适应度值#A 983为每代群体的平均适应度值#A 表示交叉的两个个体中较大的适应度值.本文将.>*设置为#(A.&,/,/%变异!变异操作使遗传算法具有局部的随机搜索能力.如果变异概率很大’那么整个搜索过程就退化为一个随机搜索过程.本文采用的自适应变异可以提供一个适度的变异概率’自适应变异概率的调整公式**++为.6-.6*4.6*4.6$A F 9j 4A 983.!A 74A 983"’A 7,A 983’.6*’A 7YA 983{’!C "式中(A F 9j 为群体中最大的适应度值#A 983为每代群体的平均适应度值#A 7是即将变异的个体的适应度值.本文将.6*设置为#(*.B,!第$期刘作军#等$程序性细胞死亡进化算法的实现引入的自适应交叉和自适应变异策略都与适应度值有关’两者的结合能够解决进化过程中因交叉和变异概率固定不变所导致的收敛速度缓慢的问题’克服种群早熟化的固有弊端’改善算法的收敛速度**++.&,0%算法流程算法具体流程如下(;:1R *!初始化.采用二进制编码得到的初始种群.包含V 个个体’个体染色体的长度设置为T #对初始种群进行遗传操作’直到特定的代数M ’才将种群分解为2个子种群’每个子种群含有的个体数没有必要一定相同#;:1R $!根据目标函数计算适应值函数A #;:1R C!执行选择操作.两次轮盘赌操作的结果由<1>@C 算子标记’由<1>@B 算子执行’由<1>@A 算子精英保留到优良种群中#;:1R B!执行自适应交叉)变异操作#;:1R "!为了实现子种群之间的共享’从优良种群中获取优良个体#;:1R ,!判断是否到达最大遗传代数.如满足’算法运行结束’输出结果#如不满足’则返回;:1R $.’%实例验证’,&%测试函数实验分析用文献**A +中V &P 12TS &<G 函数和文献*$#Q $*+中的三维;05T1S :函数测试算法性能’并与其他算法进行了对比.’,&,&%V &P 12TS &<G 函数!V &P 12TS &<G 函数为A !3*’3$"-*##!3$*43$"$N !*43*"$’3*’3$$*4$(#B+’$(#B++$!B"图’!V&P 12TS &<G 函数的图形()*+’!K 01[735S 1&[V &P 12TS &<G [52<:7&2!!函数的描述如式!B "所示’该函数是求解V &P 12TS &<G 函数的全局最大值.它有两个局部极大点’分别是(A !$(#B+’Q$(#B+"ZC +A?(?CB $$?和A !Q$(#B+’Q $(#B+"Z C A#"(A$,$$?’其中V &P 12TS &<G 函数的图形如图$所示.采用标准遗传算法!;DM "和本文的L b W M 算法对V &P 12TS &<G 函数求解最优’结果如图C 所示.由图C !9"可知’;DM 算法在*B#代左右稳定在得到的最优解处’此时得到的最优解为C +A?(?$"’即算法陷入了局部最优解#由图C !T "可知’大概进化到B 代时’种群根据个体的特征划分为多种群’使大概在"B 代时Lb W M 算法得到了两个稳定的解’实线是Lb W M 算法得到的最优解!C A#"(A$,"’虚线是L b W M 算法得到的次优解!C +A?(?C*".由此可得(Lb W M 算法收敛速度快’能同时得到全局最优解和次优解’有利于全局分析.图/!$种算法对V&P 12TS &<G 函数的进化过程()*+/!K 0118&’5:7&2RS &<1P P &[:\&9’3&S 7:0F P :&V &P 12TS &<G [52<:7&2",郑州大学学报!理学版"第"#卷’,&,’%;05T1S :函数!;05T1S :函数为A !3’5"-!"+-*+<&P *!+N *".3N++.!"+-*+<&P *!+N *".5N++’3’5$*4*#’*#+$!""图0!;05T1S :函数的图形()*+0!K 01[735S 1&[;05T1S :[52<:7&2!!;05T1S :函数是多峰值函数’用!""式求解该多峰值函数的全局最小点’全局最小点共有*+个’全局最小点为A F 72ZQ *+,(?C*’其中;05T1S :函数的图形如图B 所示.为了证明程序性细胞死亡进化算法的优越性’将它与改进的小生境算法!U)D M "*$#+)自适应遗传算法!M D M ")改进的自适应遗传算法!U M D M "*$*+和标准遗传算法!;D M "进行了对比.涉及到的实验部分参数为(种群规模V ZB#’最大进化代数为"#’共进行"##次实验.表*是"种算法进程中C 个算子操作的设计.表&!C 个算子操作的设计U :J +&!K 01>1P 732&[:0S 11&R1S 9:&S P算子操作;D M U )D M M D M U M D M L b W M 选择轮盘赌轮盘赌轮盘赌轮盘赌轮盘赌交叉概率#(+"#(?.>.>.>变异概率#(#"#(#$.6.6.6!!由于篇幅所限’各个算法的进化图不能全部展示.图"!9")!T "分别是;D M 算法和L b W M 算法对;05T1S :函数进行全局寻优的进化图’达到最大代数’进化终止.由图"可以看出’L b W M 算法确实收敛速度快并且能够搜索到最优点.图1!$种算法对;05T1S :函数的进化过程()*+1!K 0118&’5:7&2RS &<1P P &[:\&9’3&S 7:0F P :&;05T1S :[52<:7&2表’!"种算法的运算结果U :J +’!c R1S 9:7&2S 1P 5’:P &[[7819’3&S 7:0F P 算法平均进化代数搜索到最优解的成功率Nd L b W M *#*##U )D M *"AA(+U M D M *"AA(+M D M $+A#;D MC*?$!!表$列出了L b W M 算法和其他B 种算法的平均进化代数以及"种算法搜索到最优解的成功率.由表$可知’在求解多峰值;05T1S :函数最优解的进程中’最差的;DM 算法收敛到最小点处的成功率只有?$d ’而Lb W M 算法却每次都能搜到全局最优解’说明了Lb W M 算法在求解多峰值函数问题中的收敛率高于其他B 种算法.对比以上"种算法的数据可以看出’Lb W M 算法在求解复杂的多峰值寻优问题时不仅搜索到全局最优解’而且提高了算法的收敛率和收敛速度.,,!第$期刘作军#等$程序性细胞死亡进化算法的实现’,’%U M-问题的求解为验证本文算法的有效性’将该算法应用于典型的K;L问题.选用K;L a U E测试库中的经典案例17’"*进行了测试.取种群数V Z*##’迭代次数为,##’个体长度C Z"*’交叉率.>Z#(A’.>*Z#(A’.>$Z#(,’变异率.6Z#(#"’.6*Z#(#"’.6$Z#(##*’随机运行*#次.L b W M算法运行结果的最优解为B$A(**+’次优解为BC+(#*$’而文献*$$+中D M算法得到最优解为BCC(BBC.L b W M算法运行到$$$代就得到了最优路径!见图,"’比D M算法的C##代提前了很多.L b W M算法和D M算法的进化过程如图?所示.图2!最优路径()*+2!K01&R:7F9’R9:图3!进化过程()*+3!=8&’5:7&29S H RS&<1P P/%结论针对遗传算法易陷入早熟收敛的缺陷’提出了一种程序性细胞死亡进化算法!L b W M".为了验证该算法的可行性’分别在V&P12TS&<G函数和;05T1S:函数上进行了性能测试’且与标准遗传算法!;D M"和其他改进的遗传算法进行了比较.从实验结果可以看出’对于多峰值函数寻优’L b W M算法表现出了良好的搜索性能’从而验证了L b W M算法的有效性和可行性.在L b W M算法进化过程中’得到的次优解是潜在的最优解.当算法陷入到局部最优时’有必要考虑新的可能解’使之跳出局部最优’从而为决策者对实际问题的解决提供多种方案.该算法对于多峰值函数寻优问题具有很好的优势’它能使多峰值函数得到全局最优解.K;L问题的实验结果表明该算法可以解决工程中非线性)多极值的问题.参考文献!**+!马超’邓超’熊尧’等.一种基于混合遗传和粒子群的智能优化算法*-+.计算机研究与发展’$#*C’"#!**"($$?+Q$$+,. *$+!万建臣’靳宗信.多峰值函数优化问题的免疫遗传算法求解*-+.电子科技大学学报’$#*C’B$!""(?,A Q??$.*C+!刘占生’窦唯’王东华’等.基于遗传算法的旋转机械故障诊断方法融合*-+.机械工程学报’$##?’BC!*#"($$?Q$CC.*B+!刘晓冰’焦璇’宁涛’等.基于双链量子遗传算法的柔性作业车间调度*-+.计算机集成制造系统’$#*"’$*!$"(BA"Q"#$. *"+!张鑫龙’陈秀万’肖汉’等.一种求解旅行商问题的新型帝国竞争算法*-+.控制与决策’$#*,’C*!B"("+,Q"A$.*,+!K c_U)M D Me’c g M_c K ce’^M g M c;’1:9’.E729S H@T9P1>:&R&’&3H&R:7F749:7&2&[F9321:&P:9:7<P071’>723TH90H TS7>18&’5@ :7&29S H9’3&S7:0F<&F T727233121:7<9’3&S7:0F92>1j:12>1><&F R9<:3121:7<9’3&S7:0F*-+.U===:S92P9<:7&2P&2F9321:7<P’$#*C’BA!""($#AC Q$#A,.*?+!f c6e’^6)‘’/f c6_b’1:9’.L9S1:&@&R:7F749:7&2[&S P<01>5’723&[<S5>1&7’&R1S9:7&2P72S1[721S H8793121:7<9’3&S7:0F *-+.U===:S92P9<:7&2P&2P H P:1F P F9292><H T1S21:7<P’$#*?’B?!C"("*?Q"C#.*++!D6)K=VV.b&281S312<1929’H P7P&[<92&27<9’3121:7<9’3&S7:0F P*-+.U===:S92P9<:7&2P&2215S9’21:\&S GP’*AAB’"!*"(A,Q *#*.*A+!丁若冰’邹书蓉.基于聚类划分子种群的多种群遗传算法*-+.四川理工学院学报!自然科学版"’$#*B’$?!C"(B,Q BA.**#+冯士刚’艾芊.带精英策略的快速非支配排序遗传算法在多目标无功优化中的应用*-+.电工技术学报’$##?’$$!*$"( *B,Q*"*.?,+,郑州大学学报!理学版"第"#卷***+蔡良伟’李霞.遗传算法交叉操作的改进*-+.系统工程与电子技术’$##,’$+!,"(A$"Q A$+.**$+钟国坤’曾碧’余永权.基于异位交叉的遗传算法的研究*-+.控制与决策’$##C’*+!C"(C,*Q C,C.**C+杨新武’杨丽军.基于交叉模型的改进遗传算法*-+.控制与决策’$#*,’C*!*#"(*+C?Q*+BB.**B+徐克林’朱伟’李艳冰.配装@运输集成决策模型及其遗传算法*-+.浙江大学学报!工学版"’$#**’B"!A"(*,C#Q*,C".**"+M b=f M)W’-U M)D i’_c V D M)W D’1:9’.K0S11@>7F12P7&29’P:S5<:5S1&[:019R&R:&P&F1(7F R’7<9:7&2P[&S9P P1F T’H’RS&@ <9P R9P1@A T72>723’92>9<:789:7&2*-+._&’1<5’9S<1’’’$##$’A!$"(B$C Q BC$.**,+施一公’孙兵法.细胞凋亡的结构生物学研究进展*-+.生命科学’$#*#’$$!C"($$B Q$$+.**?+;V U)U%M;_’L M K)M U ga_.M>9R:781RS&T9T7’7:71P&[<S&P P&81S92>F5:9:7&2723121:7<9’3&S7:0F P*-+.U===:S92P9<:7&2P&2 P H P:1F P F9292><H T1S21:7<P’$##$’$B!B"(,",Q,,?.**++刘爱军’杨育’程文明’等.复杂制造环境下的改进非支配排序遗传算法*-+.计算机集成制造系统’$#*$’*+!**"($BB,Q $B"+.**A+李纯莲’王希诚’赵金城’等.一种基于信息熵的多种群遗传算法*-+.大连理工大学学报’$##B’BB!B"("+A Q"AC.*$#+黄聪明’陈湘秀.小生境遗传算法的改进*-+.北京理工大学学报’$##B’$B!+"(,?"Q,?+.*$*+陈明杰’刘胜.改进自适应遗传算法在函数优化中的应用研究*-+.哈尔滨工程大学学报’$##?’$+!+"(+?"Q+?A.*$$+郁磊._M K a M E智能算法C#个案例分析*_+.北京(北京航空航天大学出版社’$#*".#I B H<I<7D:D)C7CQ->C*>:I I<=T<H H!<:D98?CH P D)C7:>@6H*C>)D9Ia U6/5&O52*’$’/f M)Di79&*’b f=)a723’723*’$’/f M)De92*’$!*$9>?@@#@A J@2%B@#9>+E2>E&2/U2D+2E E B+2D’P E)E+H2+I E B,+%5@A;E>?2@#@D5’;+&2G+2C##*C#’J?+2&# $$U2D+2E E B+2D*E,E&B>?J E2%E B@A=2%E##+DE2%*E?&)+#+%&%+@2X E I+>E&2/X E%E>%+2D;E>?2@#@D5@AC+2+,%B5@A U/K>&%+@2’;+&2G+2C##*C#’J?+2&"6J G D>:;D(U2&S>1S:&&81S<&F1:01P0&S:<&F723&[RS1F9:5S1723121:7<9’3&S7:0F’9RS&3S9F F1><1’’>19:018&’5:7&29S H9’3&S7:0F\9P RS&R&P1>.U2:07P9’3&S7:0F’:0S11G1H R0H P7&’&37<9’<&2:S&’’7233121P&[ RS&3S9F F1><1’’>19:0\1S172:S&>5<1>72:&3121:7<9’3&S7:0F9P&R1S9:&S P.K01&R1S9:7&2&[P1’1<:7&2\9P 1j1<5:1>TH&R1S9:&S<1>@C92><1>@B<&’’9T&S9:781’H.M2>:011’7:7P:P:S9:13H\9P1j1<5:1>TH<1>@A.K01 <&281S312<11[[7<712<H\9P7F RS&81>.K011j R1S7F12:9’S1P5’:P&[<’9P P7<9’[52<:7&2P92>K;LRS&T’1F P P0&\1>:09::07P9’3&S7:0F<&5’><&281S31[9P:1S’92>09>T1::1S P19S<0723R1S[&S F92<1:092&:01S3121:7< 9’3&S7:0F P.K<@L C>=G(RS&3S9F F1><1’’>19:0#3121:7<9’3&S7:0F#18&’5:7&29S H9’3&S7:0F#1’7:7P:P:S9:13H#9P P7P:1> 18&’5:7&2!责任编辑(孔!薇"。