《doc基于C＋＋遗传算法实现及其在连续最优化问题中的性能检测.doc》由会员分享，可在线阅读，更多相关《doc基于C＋＋遗传算法实现及其在连续最优化问题中的性能检测.doc（11页珍藏版）》请在三一办公上搜索。
1、基于C遗传算法实现及其在连续最优化问题中的性能检测2004年第20卷第1期2004.Vo1.20No.1电子机械工程ElectroMechanicalEngineering53基于C+遗传算法实现及其在连续最优化问题中的性能检测岳振兴,李莉(南京电子技术研究所,江苏南京210013)摘要:对遗传算法在解连续优化问题中的关键技术进行了讨论.运用C/C+实现了遗传算法的程序编制.数值仿真结果验证了遗传算法计算性能稳健,能够对复杂,非线性的多峰连续函数进行全局寻优.关键词:遗传算法;优化;凸交叉;动态变异中图分类号:TP391.9文献标识码:B文章编号:10085300(2004)O1005304P
2、rogramofGeneticAlgorithmUsingC+andItsApplicationinContinuousOptimizationYUEZhen-xingLILi(NaResearchInstituteofElectronicsTechnology,Nanjing210013,China)Abstract:Thekeytechniqueaboutgeneticalgorithmappliedtocontinuousoptimizationisdiscussedinthispa.per.Andthesourcecodeforgeneticalgorithmisprogrammedu
3、singC/C+.Simulationshowsthatthegeneticalgorithmisrobustandcanfindtheglobaloptimumforanon-linearmulti-peakcontinuousfunction.Keywords:geneticalgorithm;optimization;convex-crossover;dynamicmutation0引言遗传算法是一种借鉴生物界自然选择和自然遗传机制的高度并行,随机,自适应搜索算法,其隐含的对全局信息的有效利用能力使遗传算法具有稳健性,能够很好地处理传统优化方法解决不了的复杂和非线性问题I.遗传算法的执行
4、过程可以简单描述为随机地在参变量空间中进行搜索,由串组成的群体在遗传算子的作用下,同时对空间中不同的区域进行采样计算,从而构成一个不断迭代进化的群体序列.遗传算法的突出表现能力是能够把注意力集中到搜索空间中期望值最高的部分,这是遗传算法中杂交算子作用的直接结果.杂交过程就是模拟生物界中的有性繁殖,它是遗传算法中最重要的部分,是遗传算法区别于其它优化算法的根本所在.遗传算法以迭代群体中的所:有个体为操作对象,从本质上讲属于一种群体操作算法,其基本流程如图1所示.一个标准的遗传算法程序包含收稿日期:200304114个基本组成部分:(1)参数编码;(2)初始群体生成;(3)适应值检测;(4)遗传操
5、作.其中遗传操作是遗传算法的核心,它由3个基本操作算子组成,即选择算子,交叉算子和变异算子,不同的遗传算子对算法的运行性能有着各不相同的影响.文章主要从遗传算法在求解连续最优化问题中的设计与实现环节上对遗传算法进行研究.根据所求解问题的性质,设计合理的遗传算法程序,使之满足求解问题的要求.1基于C/C+遗传算法设计与实现1.1连续最优化问题连续最优化通常是极大或极小某个多变量的连续函数并使其满足一些等式/不等式约束.在实际工程应用中大多数优化问题都属于约束优化类型,但是对无约束优化问题的研究是求解约束优化问题的基础,因此这里取无约束优化模型为优化算法设计求解的目54电子机械工程第20卷选出两个
6、个体执行交叉Ilgen=O.l一初始群体初始化回两赫一出个体执行变制父代到群体空日插入到群体空闽lll插入到群体空间IlL_.J扩大的群体空间_J执行选择更新群体图1遗传算法基本流程图标函数.一般,无约束优化问题可用如下数学模型描述:minf()s.t.X力其中是实值函数,可行域力是E的子集.若点力是上/的局部最优点,如果存在占>0使得所有X力与距离不大于占的点满足f(X)/(X),则点是/在力上的全局最优点.1.2算法的设计与实现在遗传算法的实现上,编码方法,遗传算子选择,控制参数选取等都是十分关键的问题.下面针对这些问题进行设计并实现遗传算法源代码程序编制.(1)编码方法遗传算法的编
7、码方式有多种,这里采用实数编码技术来表达给定问题的解.在实数编码中,每个染色体编码为一个和解向量维数相同的实向量X=(,x,).这种编码方式可以直接对解向量进行遗传操作,从而便于引入与优化问题领域相关的启发式信息以增加遗传算法的搜索能力.遗传个体的简要类定义形式如下:classPPpublic:doubleX:doubleobjvalue;intparentl,parent2;PP();PP()deletex;其中,实向量表示个体染色体;objvalue表示对应个体染色体的适值,由于程序采用最好种群选择策略,因此取objvalue等值于优化函数的目标值.(2)选择算子选择是遗传算法的推动力,选
8、择操作决定了父代和子代中哪些个体将被保存到下一代中作为父代.程序中采用(+A)一选择J,这种选择策略是由Back和Hoffmeister最先引入到遗传算法中的,按这种策略,个父代和A个后代竞争生存,最后选出个最好的父代和后代构成下一代的父代.(+A)一选择策略放宽了交叉概率和变异概率的选取范围,使较大的概率值不会造成个体太多的随机变动.程序中实现选择操作的源代码:for(j=0;j<popsize;j+)for(j1=0;jl<freesize;jl+)newpopj.xj1=listpopj.xj1;newpopj.objvalue:listpopj.objvalue;newpo
9、pj.parentl=listpopj.parentl;newpopj.parent2=listpopj.parent2;其中,数组listpop是扩大的种群采样空间(+A);数组newpop是选出进行进化操作的下一代种群.(3)交叉算子在遗传算法中,交叉算子的作用非常重要.一方面,它使原群体中优良个体的特性能够在一定程度上保持;另一方面,它使算法能够探索新的基因空间,从而使新种群中的个体具有多样性.依所处理问题性质的不同可有多种交叉方式,程序中采用基于算术运算的凸交叉策略,根据交叉概率进行判断,由父代中选出参加交叉的两个个体按照公式(1),(2)计算产生两个新的后代:XI=AIXI+A2X2
10、=At+A2Xt(1)(2)其中,AI,A2均为实数且满足AI+A2=1.0,A>0,A,>0.程序中交叉算子子函数源代码:voidcrossover(doubleparentl,doubleparent2,PPpop,intk5)inti;第1期岳振兴.等:基于c+遗传算法实现及其在连续最优化问题中的性能检测55doublerr;rr=0.4689;ncross+;for(J=0;j<freesize;j+)Ipopk5.xj=rrparentlj+(1.0一rr)parent2j;popk5+1.xJ=rrparent2J+(1.0一rr)parentlJ;其中,变量fr
11、eesize表示个体染色体长度,这里等于优化向量的维数;pop表示种群中的个体实例.(4)变异算子变异是对种群中个体串的某些基因位置上的基因值作变动.在遗传算法中变异算子的使用使遗传算法具有局部随机搜索能力,同时还使遗传算法维持种群的多样性.变异操作基本过程:在群体中所有个体的基因串范围内以事先设定的变异概率P来选择进行变异操作的基因位,然后对选中的基因位作设定的变异操作.程序中针对染色体实数编码方式而采用动态变异l6运算规则来实现变异操作,主要思想是将变异算子与进化代数联系起来,使在进化初期,变异范围相对较大,而随着种群的进化,变异范围越来越小.这一处理方式提高了算法的运算精度,增加了变异算
12、子对进化的微调作用.动态变异操作的具体实现步骤描述:对于父亲=(.,),通过变异概率P,逐次判断各基因位是否发生变异;假设元素z被选出作变异,则产生的后代=(,:,),其中是按公式(3),(4)两种可能选得的:或=+a(t,9CU)=a(t,)(3)(4)函数(t,Y)返回0,Y之间的一个值且随t增加而趋于0(t是进化代数).函数a(t,Y)按公式(5)计算:()=Y(1一专).(5)其中,r是0,1之间的随机数;T是最大进化代数;b是确定不均匀度的参数.程序中变异算子子函数源代码:doublemutation(doublex,intk)Iintrand0;doubletempi,temp2,
13、rand1,value:doublerr,b;nmutation+:srand(unsigned)time(NULL);randl=random(1001)/moo.0:b=3.0;rr=1.0一gen/maxgen:rr=pow(rr,b);tempi=x+rand1rr(topk一x);temp2=xrandlrr(xbottomk);rand0=random(2);if(randO=0)value=tempi;elsevalue=temp2;return(value);f(5)参数选择及初始化算法中控制参数主要包括群体规模(popsize),交叉概率(pcross)和变异概率(pmuta
14、tion)等,它们对整个遗传算法的计算效能有着不同影响:群体规模影响算法最终性能和效率,当群体规模较大时,群体中个体的多样性较强,从而阻止算法过早收敛到局部最优解;然而,群体规模过大,每一代中需要的计算量将很大,这样可能导致极慢的收敛速度.交叉概率控制交叉算子的应用频率,在每代新的群体中有pcrosspopsize个个体进行交叉.交叉概率越高,群体中个体更新越快,如果交叉概率过高,相对选择能够产生的改进而言,高性能的个体被破坏得更快;交叉概率过低,搜索会由于太小的探察率而可能停滞不前.变异概率是遗传算法的一个重要参数,它直接影响到算法的收敛性和最终解的性能.较大的变异概率使算法不断探索新的解空
15、间,增加群体中个体的多样性,但是过高的变异概率造成的实质是随机搜索.实际上,一个低水平的变异概率足以防止整个群体中任一给定位保持永远收敛到单一的值.程序的初始化是由函数voidinitialize()实现的,在程序初始运行时需要提供种群规模(popsize),优化向量维数(freesize)即染色体长度,最大进化代数(maxgen),交叉概率(pcross)和变异概率(pmutation)等五个参数的值以及优化向量的界限值bottom和top.初始种群是在向量取值域内随机产生的,由函数viodinitpop()实现.2仿真例为检测基于C/C+设计编制的遗传算法程序的优化计算性能,我们选取Ack
16、ley函数作为检测函数.Ackley函数是指数函数迭加上适度放大的余弦波再经调制而得到的连续型实验函数,它的拓扑形状如图2所示,其特征是在一个几乎平坦的区域内由余弦波调制形成一个个孔或峰,从而使曲面起伏不平.Ackley函数如下:电子机械工程第20卷mi)=_clp-2/nj=lj1一exp(一季lc.s(c.?)+cl+e(6)这里,一5xj5,cl=20,c2=0.2,c3=2rr,e=2.71282=1,2.该函数的最优解为(,X2)=(0,0)XI,X2)=0.l-ffl鼍图2Ackley函数按照式(5)中所述控制参数对遗传算法计算效能的不同影响规律,程序测试中分别取各输人参数的值:p
17、opsize=160,freesize=2,maxgen=100,pcross=0.4,pmutation=0.05.图3和图4是通过仿真绘出的图形,其中图3中黑点表示60代遗传运算后得到的各代函数最小值点,图4是仿真实验得到的Ackley函数的寻优过程曲线,由图可以看出经过55次进化计算就已找到了最小函数值min=一5.461828e一003,此时对应的=(一4.070457e一011,一1.518713e一010).每图3优化结果图4函数最小值与进化代数关系3结论利用C/C+语言设计并实现了遗传算法中各遗传操作算子的源代码编制,如交叉算子,变异算子及选择算子等.仿真计算结果检验了遗传算法程
18、序的有效性,表明编制的遗传算法具有稳健的全局寻优性能,是求解连续最优化问题的一种有效方法,从而为解决实际工程设计问题提供了良好的优化设计手段.参考文献:1刘勇,康立山.非数值并行算法(第二册)M.北京:科学出版社,1995.2陈国良.遗传算法及其应用M.北京:人民邮电出版社,1996.3玄光男,程润伟.遗传算法与工程设计M.北京:科学出版社,2000.4FogelD.AnIntroductiontoSimulatedEvolutionaryOptimi?zationJ.IEEETransactionsonNeuralNeorks,1994,5:3一l4.5MichalewiczZ.Geneti
19、cAlgorithm+DataStructure=Evo?utionProgramM.2nd.SpringVerlag,NewYork,1994.6JanilowC.MichalewiczZ.AnExperimentalComparisonofBinaryandFloatingPointRepresentationsinGeneticAlgo?rithmsJ,inBelewandBooker,1994,30:3136.作者简介:岳振兴(1976一),男,助3-,主要从事雷达天线座结构设计与现代优化技术等领域的设计与研究工作.孛?夺?孛?孛?孛?孛?孛?孛?孛?争?孛?孛?孛?孛?孛?孛?孛?幸
20、?孛?孛?孛?孛?孛?会议简讯电子机械工程编委会会议于2004年1月10日在南京华江饭店召开.编委和常编共29人参加了会议,会议由编委会常务副主任平丽浩同志主持,中国电子学会电子机械工程分会主任委员严敦善同志到会并作了重要讲话.叶渭川秘书长就电子机械工程分会的工作开展情况以及新年分会的活动安排和打算作了介绍.电子机械工程杂志主编陆萍同志首先报告大家一个喜讯电子机械工程杂志荣获全国首届中国学术期刊(光盘版)(CMCD规范)执行优秀期刊奖,然后汇报了编辑部一年来的工作情况.主编在肯定了本年度编辑部工作的同时,还指出了存在的问题以及今后需要努力的方向.常编们在听取编辑部的总结汇报后,就稿件的录用范围,审稿人员的扩大问题以及杂志今后的发展方向展开了热烈的讨论.新的一年里,编辑部全体人员会更加努力,把电子机械工程杂志办得更好.
