文档介绍：●PUTERSVO【(哈尔滨工业大学计算机科学与工程系暗尔滨150001)ICALG0RITHMSWANGXuemeiWANGYihe(puterScienceandEngineering,Harbinlm-tit~teofTechnology1背景EAsA模拟退火算法(简称SA)和遗传算法(简称GA)都是起因于自然界的某些规律的算法,是按自然法则计算的两大分支,研究将它们有机地结合起来,提高其效率,,80年代末,人们开始将注意力投向SA与GA的结合,较典型的有:“面向一致化热动态算子”(“To—wardaunifiedthermodynamicoperator”)口,“玻尔兹曼、达尔文和黑格尔策略用于优化问题”(“Boltzmann—Darwin—andHeaekel—strategiesinoptimizationproblems”)口],(PRSA)],“过早收敛”,传统的Reprodue—tion—Crossover,Mutation机制和按适应性比例选择,使得高于群平均的模式在下一代中获得较多的取样,这样不断进行,一旦某些模式取样在群中占有优势,传统遗传算法就会强化这种优势,从而使搜索范围迅速变窄,“一遗传漂移”,迅速收敛的群达到的未必是全局最优,,、适应的方法努力,如文献[4,5]“过早收敛”的发生,,,,即群中的一些个体分别代表解空间不同的局部最优所在的区域],我们在GA中引入Boltzmann生存机制,试图保持这种“有用的多样性”.新的个体产生后,传统的GA从群中随机取出一个个体,,,,新个体i替换旧个体i,存在两种情况:(1)若i与i在同一区域,替换不会降低多样性,但会使适应性发生波动,特别是若i的适应性低于i的适应性,且i是局部最优时,,因此就会出现这样的情况,搜索到局部最优,但后本文1995—-梅,硕士研究生,,教授,主要研究领域为并行计算、人工甯能自理论基础./D,,/~维普资讯学报来失去,使得在这一局部区域的搜索类似于随机搜索,难于收敛;(2)若i与不在同一局部区域,则i必代替其它区域中的某一个,,,越有两种可能:群收敛向某一局部区域;或各个局部区域之间元素互换量基本相当,但这时群的收敛性同样很差,,传统GA的替换策略主要有:(1)新产生的几个子代替换群中几个最坏的个体;(2)(决定新生成的子代哪些能够加入到群中生存,来产生新后代)主要有:(1)接受所有子代{(2)设f是群的最低适应性,仅接受适应性大于f。+1%的子代;(3)仅接受其适应性大于其群最低适应性的子代;(4)仅接受其适应性大于群最低适应性的子代;(5):,例如GA欺骗问题,函数表现为适应度高的山峰被一些低谷所包围(要达到山峰必须经过低谷),,,我们在传统GA的生存策略中引入Boltzmann生存机制:设新产生的适应性为,,变动的阚值为7,当,>7时,接受新个体;否则,以一定概率接受新个体P—exp((f7)/T),其中丁是控制参数,,,若它的适应性高于最相似的个体,则替换这个父本;否则,以概率P=exp((一7)/T)替换其父本;而在SSB2中,设群平均适应性为,.,最低适应性为,对于每一新产生的