模拟退火算法与遗传算法的结合.pdf

第20卷第4期计算机学报VO【l20No．4
I997年4月CHINESEJ．COMPUTERSADr．I997

(哈尔滨工业大学计算机科学与工程系暗尔滨150001)

●
THEC0MBINAT10N0FSIMULATEDANNEA
ANDGENETICALG0RITHMSsA

WANGXuemeiWANGYihe
(DeparzmeatComputerScienceandEngineering，Harbinlm-tit~teofTechnology

1背景
模拟退火算法(简称SA)和遗传算法(简称GA)都是起因于自然界的某些规律的算法，是
按自然法则计算的两大分支，研究将它们有机地结合起来，提高其效率，是有意义的．这也符合
自然界对立与统一的本质．国际上这方面的研究刚刚开始，80年代末，人们开始将注意力投向
SA与GA的结合，较典型的有：SiragDJ和WeisserD．J．的“面向一致化热动态算子”(“To—
wardaunifiedthermodynamicoperator”)口，BosesniukT．和EbelingW．的“玻尔兹曼、达尔文
和黑格尔策略用于优化问题”(“Boltzmann—Darwin—andHeaekel—strategiesinoptimization
problems”)口]，GoldhergD．E．和MahfoudS．W．等人的并行再生模拟退火算法(PRSA)]，
等．
2引人Boltzmann生存机制的遗传算法的基本思想
传统遗传算法最为严重的问题是“过早收敛”问题．由于群是有限的，传统的Reprodue—
tion—Crossover，Mutation机制和按适应性比例选择，使得高于群平均的模式在下一代中获得
较多的取样，这样不断进行，一旦某些模式取样在群中占有优势，传统遗传算法就会强化这种
优势，从而使搜索范围迅速变窄，表现为群收敛向一些相同的串．由于“一遗传漂移”，迅速收
●敛的群达到的未必是全局最优，这～就产生了过早收敛．解决过早收敛问题的方法非常多，而且
J／
一直在发展．目前人们在向动态、适应的方法努力，如文献[4，5]等．
，
，，
●保持群的多样性可以预防“过早收敛”的发生，其道理是不言而喻的．但在本文中我们提到
的多样眭，不是各个随机串的混合．因为若保持这样的多样性，群最终很难收敛．我们指的是有
／D
用的多样性，即群中的一些个体分别代表解空间不同的局部最优所在的区域]，我们在GA中
引入Boltzmann生存机制，试图保持这种“有用的多样性”．
新的个体产生后，传统的GA从群中随机取出一个个体，用一个新个体将它替换出去．这
种做法虽然能保证新产生的子代永远能有再生的机会，但有时是不必要的．而且，这种替换方
法也存在问题．假设在t时刻，新个体i替换旧个体i，存在两种情况：(1)若i与i在同一区域，
替换不会降低多样性，但会使适应性发生波动，特别是若i的适应性低于i的适应性，且i是局
部最优时，就会丢失i．由于i与i是随机的，因此就会出现这样的情况，搜索到局部最优，但后

本文1995—03一l4收到．车课题得到国家自然科技基金和登计划资助．王-梅，硕士研究生，主要研究领域为计算机
应用技术．王义和，教授，主要研究领域为并行计算、人工甯能自理论基础．

计算机学报

来失去，使得在这一局部区域的搜索类似于随机搜索，难于收敛；(2)若i与不在同一局部区
域，则i必代替其它区域中的某一个，i所在局部区域将失去一个元素．而且若i的适应性低于
i，那么这种替换对于收敛相当不利．这种情况出现得越多，越有两种可能：群收敛向某一局部
区域；或各个局部区域之间元素互换量基本相当，但这时群的收敛性同样很差，很难找到接近
全局最优的解．
目前，传统GA的替换策略主要有：(1)新产生的几个子代替换群中几个最坏的个体；(2)

新产生子代替换其父亲等．●
而生存策略(决定新生成的子代哪些能够加入到群中生存，来产生新后代)主要有：(1)接
受所有子代{(2)设f是群的最低适应性，仅接受适应性大于f。+1％的子代；(3)仅接受其适应
性大于其群最低适应性的子代；(4)仅接受其适应性大于群最低适应性的子代；(5)仅接受适应
性大于其父亲的子代．
这些生存策略可以归结为：当新产生子代的适应性大于某一随群进化而变动的阚值f时
被接受．存在这样的情况，例如GA欺骗问题，函数表现为适应度高的山峰被一些低谷所包围
(要达到山峰必须经过低谷)，低适应性的群也可能会包含有用的模式．因此，在遗传搜索中也
应当接受差解．
基于这种考虑，我们在传统GA的生存策略中引入Boltzmann生存机制：设新产生的适应
性为，，变动的阚值为7，当，>7时，接受新个体；否则，以一定概率接受新个体P—exp((f