资源描述：
《一种混合遗传模拟退火算法及其应用_刘怀亮.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第4卷第2期广州大学学报(自然科学版)Vol.4No.22005年4月JournalofGuangzhouUniversity(NaturalScienceEdition)Apr.2005文章编号:1671-4229(2005)02-0141-05一种混合遗传模拟退火算法及其应用刘怀亮,刘淼(广州大学信息与机电工程学院,广东广州510405)摘要:分析了遗传算法和模拟退火算法的优缺点,提出了一种混合遗传模拟退火算法,对其进行优化,并将该算法应用于TSP问题的求解之中.理论分析和实验结果表明了这种混合遗传模拟退火算法优于普通的遗传算法和模拟退火算法.关键词:模拟退
2、火算法;遗传算法;TSP问题中图分类号:TP301.6文献标识码:A人的.若用运算速度为1GFLOPS次的CrayÒ型计0引言算机进行搜索,n=7时,需要01000025秒,n=15时需要118小时,n=20时猛增到350年,n=50旅行商问题(TravelingSalesmanProblem,简记48时则需要5@10年!显然,如此求TSP问题的方为TSP)是一种典型组合优化问题(Combinatorial法是不可行的.OptimizationProblem),并且也是一种NP完全问题最初求TSP问题的近似解是采用一些局部搜(NondeterministicPo
3、lynomialCompleteProblem).TSP索方法,如最近邻法、最近插入法等,但这些算法问题可以描述为:有n个城市,它们相互之间距离在最坏情况下得到的解很不理想.由于这一类问是已知的,有一商人从某一城市出发旅行完所有题的复杂性,又有人提出了一些优化技术,如模拟[1][2,3][4]的n个城市,要求每一个城市只能经过一次,且最退火、模拟进化和神经计算等.但这些算后回到出发点,求该旅行商所经过的最短路程和法或因过于注意个别问题的特征而缺乏通用性,相应路线.或因所得解强烈地依赖初始解的选取而缺乏实用TSP问题研究的重要性在于:TSP问题是许多性.遗传算法和
4、模拟退火算法都是起因于大自然最难NP完全问题中的一个,所有NP完全问题在的某些规律,考虑到两种算法的本质特点,本文将数学上都等价于TSP问题,它的研究对于科学和这两种算法相互结合,提出了一种混合遗传模拟工程技术领域中大量组合优化问题,尤其是其中退火算法,并将其用于TSP问题的求解.的NP完全问题的求解有着极为重要的价值.NP完全问题求解时间随问题规模呈指数级1遗传算法增长,当规模稍大时就会因时间限制而失去可行性(Feasibility).TSP问题求解也是如此,例如,对遗传算法(GeneticAlgorithms,简称GA)是(n-1)!J1Holland于19
5、75年受生物进化论的启发而提出于n个城市的TSP,存在可能的路径数为2的,它是模拟生物在自然环境中的遗传和进化过(n-1)![5]条,要从个可能解中找出最优者,需要进程而形成的一种自适应全局优化概率搜索法.2遗传算法模拟自然进化中/优胜劣汰、适者生存0(n-1)!行-1次比较.当n较大时,其数量是惊2的原理进行自学习和寻优,它将问题的求解通过收稿日期:2004-10-30;修回日期:2004-12-14作者简介:刘怀亮(1976-),男,硕士,主要从事分布式人工智能、数据挖掘、数据库的研究.142广州大学学报(自然科学版)第4卷编码表示成染色体,由计算机随机产生
6、一群染色随机搜索技术从概率的意义上找出目标函数的全体,每个染色体在问题的/环境0中对应着其本身局最小点.模拟退火算法可以用马尔柯夫链的遍的适应度,根据适者生存的原则,从中挑选适应度历理论来给它以数学上的描述.在搜索最优解的高的个体进行杂交、变异等基因操作产生出新一过程中,模拟退火算法除了可以接受优化解外,还代个体,不断迭代进化最终收敛到适应度最高的用一个随机接受准则(Metropolis准则)有限度地接个体上,此个体经过解码后就是问题的最优解.遗受恶化解(il-lconditioned),并且接受恶化解的概率传算法求解问题的具体实现过程为:用某种编码慢慢趋向于零
7、,使得算法执行过程中即便落入局技术作用于输入量以形成数串,模拟由数串组成部最优的陷阱中,理论上经过足够长的时间后也的群体的进化过程.通过复制、交叉、变异过程有可跳出来从而收敛到全局最优解,这是模拟退火组织地,然而又是随机地由信息交换来重新组合算法的最大特点.但是由于模拟退火算法对整个那些适应性好的数串,在每一代中,利用上一代数搜索空间的状况了解不多,不便于使搜索过程进串结构中适应性好的位和段来生成一个新的数入最有希望的搜索区域,从而使得模拟退火算法串,并偶尔也在数串结构中尝试用新的位和段来的运算效率不高.替代原来的部分.遗传算法用简单的编码技术和繁殖机制来表3遗
8、传算法与模拟退火算法的混
