维普资讯 doc.guandang.net
混合遗传算法与模拟退火法 田东平迟洪钦
(海师范大学数理信息学院,海 2 0 3 )上上 0 2 4 E m i tp ao. m. - a: 2 ̄ ho o c l d 1C 1 c n 摘要论文将适合全局搜索的遗传算法 ( A) G和适合局部搜索的模拟退火算法 ( A ̄结合,出了混合 G— A计算 S )n提 AS方法。方面,法采用混沌初始化,高了初始群体的质量;一算提另一方面,法采用 Ga算 r y编码以及动态自适应调节交叉概率和变异概率,高了收敛速度,有效防止种群早熟现象。实例验证了该算法的可行性和有效性。提并 关键词遗传算法模拟退火算法混沌初始化 G a ry编码文章编号 1 0— 3 1 ( 0 6 2— 0 3 0 文献标识码 A 0 2 8 3 - 2 0 )2 0 6— 3 中图分类号 T 3 1 P0 . 6
Hy rd Ge e i g rt m n i u a e n ai g b i n tc Al o i h a d S m l t d An e l n Ti n Do g i g Ch n q n a n pn i Ho g i
( te ai n cec sC l g,h n hiN r a U i ri,h n h i2 0 3 ) Ma m t sa d S i e ol e S a g a om l nv sy S ag a 0 2 4 h c n e e t Ab ta t hs p p rp t ow r y r GA- A y o iig G n t g rh GA)a d Smuae n aig S sr c:T i a e usfr ad h b d i S b c mbnn e ei Alo tm( c i n i ltd An e l ( A) n t g t e, i h t e fr r i ut b e f r g o a e r h n n h atr i s i b e fr lc l s ac i gI h s p p r o eh r i wh c h o me s s i l o l b l s ac i g a d t e lt s ut l o a e r hn . ti a e, n a e a o n O h n a d, h o n i l ai n i d p e n o d r t mp o e t e u l y o n t l o u ai n On h t e a d, n t e o e h n c a s i t i t s a o td i r e o i r v
h q a i f i i a p p lt . te o h r h n az o t i o
G a o ig n y a c d pie p o a i t fco sv r a d ry c dn a d d n mi a a tv rb bl o rso e n muain ae a o td, ih a mpo e te e ouin i y tt r d pe whc c n i rv h v lt o o s e d a d p e e t t e p p lt n fo p e t r . o r e a l s s o h t t e h b d GA— A s f a i l n f cie p e n r v n h o u ai r m r ma u eF u x mp e h w t a h y r o i S i e sb e a d e e t . v
Ke wo d:G n t grtm( y r s e ei Alo h GA) Smuae A n aig S,h o nil ain, ry cdn c i,i ltd n e l ( A) c a s it i t G a o ig n az o
l引言 遗传算法 I G是模拟生物在自然环境中的遗传和进化 A) 1 (过程而形成的一种自适应全局优化概率搜索算法。由于该算法采用随机选择,搜索空间无特殊要求,对无需求导,有运算简具单、收敛速度快等优点 .其适用于处理传统搜索方法难以解尤决的复杂和非线性问题。是一种全局搜索能力很强而局部搜它索能力不足的算法。 A直接以目标函数作为搜索信息 .一定 G在范围内同时搜索多个点 .比传统优化算法寻优效率高 .合处适理较复杂的优化问题。如组合优化 .产调度 .杂布局,生复自动控制,经网络,神图像处理等。究发现, A可以用极快的速度研 G达到最优解的 9%左右 .要得到真正的最优解则要花费很长 0但 时间。
2基本优化算法 21遗传算法 ( A) . G 遗传算法是 2 0世纪 7 0年代初发展起来的一种自适应全局优化概率搜索算法。它模拟自然进化过程来搜索问题的最优解,广泛应用于许多学科领域。G并 A进行问题求解时,首先对 优化问题的解进行编码 .码的目的主要是用于优化问题解的编
表现形式和利于其后 G中的计算:构造和应用适应度函数, A
适应度函数基本上依据优化问题的目标函数而定。当适应度函数确定之后 .自然选择规律是以适应函数值的大小决定的概率分布来确定哪些个体适应生存,哪些个体被淘汰。生存下来的个体组成可以繁衍下一代群体的新的种群;过 R po ut n 通 e r c o— d i C osv r M t in机制和按适应性比例的选择 .不断进行解 rs e— ua o o t
模拟退火算法[ S是局部搜索算法的扩展。它不同于局 2 A) t (部搜索之处是以一定的概率选择领域中费用值大的状态。S A是一种随机组合优化方法 .它模拟高温金属降温的热力学过程,广泛应用于组合优化问题。理论上说,A在初始温度足并 S够高、度下降足够慢的条件下 .以概率 1收敛到全局最温能优值。 针对 G A在局部搜索能力方面的不足和 S在全局搜索能 A力方面的不足 .文将两者有机结合,势互补 .挥 G全局本优发 A搜索能力和 S A局部搜索能力 .克服 G局部搜索能力差及其 A早熟现象和 S A全局搜索能力差及效率不高的问题 .构造出混合 G— A算法。使用四个基准测试函数作算例 . M D S . AS在 S O2 0环境下编程实现了混合 G— A算法 .并通过与单一的 G和 AS A S A相比,明了该算法的可行性和有效性。表
的搜索 .至达到全局优化。算法的求解过程如下:直 步骤 1选择问题的一个编码;给出一个有Ⅳ个染色体的初始群体 p p 1,:1 o ( )t=;步骤 2对群体 P ()的每一个染色体 p .£计算它的 p o£中 p o ()
适应函数 ft s(o t) i n sP (); e p 步骤 3若满足停止规则 .算法停止;则 .算概率:则否计 :— ,
1, 2…,Ⅳ
∑。 并以此概率分布从 P ()随机选一些染色体构成一个 p o t中 种群:
e pp t ){叩,£ 12,; nw o ( 1=P ()=,…,】+ v 步骤 4以概率 P进行交叉 .得到一个有Ⅳ个染色体的
作者简介:田东平 (9 1 )男,士研究生,要研究方向为智能优化计算。迟洪钦 (9 3,,教授
,士生导师, 18一,硕主 15一)男副硕主要研究方向为遗传算法 教育统计。
计算机 T程与应用 2 0 . 6 0 62 2 3

如果将遗传算法与模拟退火算法相 结合 ,互相取长补短 , 则有可能开发出性能优良 的新的全局搜索算法 . 基于模拟退火的混合遗传算法是将遗传算 法与模拟退火算法...
一种混合遗传模拟退火算法及其应用_理学_高等教育_教育专区。一种混合遗传模拟退火...由于这一类问 题的复杂性 ,又有人提出了一些优化技术 , 如模拟 法或因过于...
龙源期刊网 http://www.qikan.com.cn 基于混合遗传模拟退火算法的最优路径求解 作者:双珍珍 雷晓娟 来源:《科技探索》2013 年第 04 期 摘要:本文采用遗传算法...
基于混合遗传模拟退火算法的最优路径求解 摘要:本文采用遗传算法和模拟退火算法相结合的混合算法, 求解路网拓扑图中的任意两点之间的最优路径,既能发挥遗传算法 收敛...
一类模拟退火算法与遗传算法混合优化策略_专业资料。提出一类模拟退火算法(GA)和遗传算法(SA)的混合策略。算法结构上,提出模拟退火算法与遗传算法相结合,既发挥模拟退...
结合离散时间系统最优控制问题,提出一种新的混合算法.该算法是在遗传操作中嵌入模拟退火算子,有效地结合了遗传算法隐含并行与模拟退火算法全局寻优的特点,同时用罚函...
基于遗传算法和模拟退火算法的混合算法_IT/计算机_专业资料。基于遗传算法和模拟退火算法的混合算法第33 卷第 2 期昆明理工大学学报 (理工版 ) 2008 年 4 月 Jo...
广东 广州 510405) 摘要: 分析了遗传算法和模拟退火算法的 优缺点, 提出 了一种 混合遗 传模拟 退火算法 , 对 其进行 优化, 并将 该算 法应用于 TSP 问题...
混合算法. 该算法是在遗传操作中嵌入模 拟退火算子,有效地结合了遗传算法隐含并行与模拟退火算法全局寻优的特点,同时用罚函数方 法处理约束条件,设计了专门的遗传...
7 2? 计 算机 应用 研究 200 5焦 基于模拟退火的混合遗传算法研究 周丽 ,黄 素珍 (. 州师范学院 数 学与信 息科 学学 院,江温州353 1温浙205;2温 ...
热门文档