资源描述：
《遗传算法的运行机理分析_恽为民》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第13卷第3期控制理论与应用Vol.13,No.31996年6月CONTROLTHEORYANDAPPLICATIONSJunl.,1996遗传算法的运行机理分析‘浑为民席裕庚·,(上海交通大学自动化系上海20。。30):,摘要遗传算法是一种自适应启发式群体型迭代式全局搜索算法正受到许多学科的重视.本文首先,以函数优化为例分析了遗传算法的运行过程然后着重探讨了遗传算法的全局收敛性和效率问题,提出了有效基因的新概念及有效基因突变操作,推导出每次遗传搜索产生O(2卜’)数量级的新模式,最后给出了结论.:,;关锐词遗传算法全局收敛性搜索效率,引言eneteaoroan‘
2、,遗传算法(Gilgithm)是由密切根大学Hlld等创立的[〕来源于进化论和群体遗传学,原先用于模拟自然系统的自适应现象,后来被引向了广泛的工程问题.遗传算法,以、发展成一种自适应启发式概率性迭代式全局搜索算法其解决不同非线性问题的鲁棒性全局最优性、不依赖于问题模型的特性、可并行性及高效率,具有独特的吸引力,正引起越来越大的研究及应用热潮.八十年代以来,遗传算法在许多方面得到了应用,如自动控制川、计、,、、.机器人学”〕算机科学[61[l0模式识别[s1工程设计图和神经网络[5]等领域,:遗传算法的运行过程较为简笔但它的整体行为是复杂的其关键间题是为什么遗传算法
3、在解决非线性问题时具有全局收敛性?为什么全局收敛性又存在一定概率的不稳定?为,什么遗传算法的搜索效率很高?HoUand提出的模式定理[l]部分说明了第三个问题对前两个问题的解释是牵强的[2].本文将首先以函数优化间题为例分析遗传算法的运行过程和作,,为遗传算法理论基础的模式定理然后以有效基因的概念来说明前两个问题并提出一种新的对遗传算法效率的估计方法来进一步说明第三个问题.2遗传算法的运行过程,,遗传算法的结构与基因操作方式多种多样难以从形式上明确定义它的标志在于其内在特征,下面以函数优化为例来阐述遗传算法的主要特征和运行过程.:n:,,函数优化问题表述如下有一维
4、未知函数f(x)Rn~R但输人一自变量能知道相应的函数值,求maxf(x).这是一个黑箱问题,没有函数在连续性等方面的任何信息,好的搜索算法必须有较好的能适用于不同函数的鲁棒性以及较高的效率.,,遗传算法把该问题中的自变量当作生物体将其转化为由基因构成的染色体相应的函数值定义为适合度,未知函数为环境,生物体的目标是进化成具有最佳适合度的基因型.本,:文以后称染色体为串用遗传算法求解上述函数优化问题的步骤如下,Stepl;选择编码策略把参数转换成串*国家自然科学基金与上海市自然科学基金资助项目..本文于1993年12月15日收到.1995年3月30日收到修改稿298
5、控制理论与应用13卷,,编码策略有二进制编码和实数编码等若采用二进制码表达实数每个二进制位即为,,,一基因x〔〔a则若一维参数习,尹g2习··x一a+I(b一a,(2‘,玄升了,,.,,,,lg*iab~1l一510101其中是串的长度为第个基因本例中若一O串长串表示实数0.6674;StepZ定义串的适合度函数为F一f(x);,它;适合度函数是目标函数或耗散函数的映射包含了对黑箱所需的所有信息,SteP3n,随机产生n,个串构成群体;选择群体大小等遗传参数Step4计算群体中串的适合度.由串解码所得的解越好,则适合度值越高;,,,,Steps根据串的复制概率P(
6、F)选择2个串适合度越高各复制一份则复制概率越;大,Step6在串上随机选择一个位置在复制的2个串上标记为交位csl;。Step7以交换概率p交换csl后的基因段;Steps对两个,;串中的基因按突变概率户进行翻转ee,n,;Stpg跳至Stps直至已复制个串.Steplo从tep4,S始重复进行直到满足某一性能指标或规定的遗传代数..以上遗传过程描述了最简单的进化模型Stepl和StepZ是实际应用中的关键Steps,至StePS复制实施了适者生存的原则;进行三种基本基因操作交换的作用是组合父代中有价值的信息,产生新的后代,以实现高效搜索;突变的作用是保持群体中
7、基因的多样性.,,,,.下面以最简单的一维线性函数f(x)~x为例x~o卜二31求max了(x)串长为l一,.,5,n,一1,群体大小4遗传过程见表其中第(2)栏是随机产生的群体第(3)栏是串对应的,,,参数值第(4)栏是串对应的函数值和适合度适合度函数定义为F一f(x)第(5)栏是各,,‘,,3,种串的复制概率由F/习F求得第(6)栏是复制数其中第个串消失复制概率高的第,,,、,、(4)个串则复制2个复制后的群体见第(7)栏第(8)栏随机产生配对序号这里1423配,,,,对第(9)栏随机产生2个交换位。51csZ然后交换csl和csZ间的基因产生的新群体见第(1
8、0)栏,第
