龙源期刊网httpwwwqika
comc
模拟退火算法和遗传算法的比较与思考
作者：解晨韦雄奕来源：《电脑知识与技术》2013年第19期
摘要：在目前的计算机学科中，有一大类问题至今还没有快速合理的解决算法，并且其中有很多问题都是在实际应用中所碰到的优化问题。虽然目前没有能精确解决这些问题的最优算法，但是在实际应用中，人们还是找到了许多能产生近似最优解的有效算法，模拟退火算法和遗传算法便是这一类算法中的经典算法。该文浅析了此两种算法的原理，并通过一个简单的例子对这两种算法进行了比较和总结。
关键词：组合优化；模拟退火算法；遗传算法
中图分类号：TP311文献标识码：A文章编号：10093044（2013）19441802
组合优化问题是当今世界中非常重要的一类问题，在这类问题中，有一部分问题在如今的计算机性能条件下进行求解往往需要耗费巨大的时间和储存空间，以至于根本无法进行求解，并且其中有很多问题是在人们的生活中产生的实际组合优化应用问题，若能很好地解决这类问题，人们的工作和生活方式便能变的更有效率。
模拟退火算法和遗传算法是人们多年来所找到的两种比较有效的算法，这两个算法虽不能得出优化问题的精确最优解，但是可以给出近似的最优解。下面，就让我们来看看这两个算法的原理，并根据一个简单的应用来分析和比较这两个算法。
1模拟退火算法原理
模拟退火算法是根据自然界中的固体退火原理而推出的算法。
在自然界中，对于一个固体，将其加热使其温度至充分高，其内部粒子便随温度升变为无序状，此时内能增大，然后再让其徐徐冷却，此时其粒子逐渐趋向为有序状态，在每个温度都达到平衡态，最后，在常温时达到基态，固体的内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为eΔE（kT），其中E为温度T时的内能，ΔE为其改变量，k为Boltzma
常数。
模拟退火算法便是模拟上述的物理退火过程。在模拟退火算法中，用上述退火原理中的内能E来模拟目标函数值f，温度T为控制参数t，由t和一个初始解开始，对当前的解不断重复产生新解、计算目标函数差、接受或舍弃新解的迭代步骤，同时每一步迭代逐步衰减t值，最终当温度降低，算法终止于特定的温度，便得到近似最优解。其中退火过程由冷却进度表控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
f龙源期刊网httpwwwqika
comc
2遗传算法原理
同模拟退火算法一样，遗传算法也是人们由自然现象推导而来。
遗传算法的根源是r