模拟退火算法和遗传算法的比较与思考

开篇：润墨网以专业的文秘视角，为您筛选了一篇模拟退火算法和遗传算法的比较与思考范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：在目前的计算机学科中，有一大类问题至今还没有快速合理的解决算法，并且其中有很多问题都是在实际应用中所碰到的优化问题。虽然目前没有能精确解决这些问题的最优算法，但是在实际应用中，人们还是找到了许多能产生近似最优解的有效算法，模拟退火算法和遗传算法便是这一类算法中的经典算法。该文浅析了此两种算法的原理，并通过一个简单的例子对这两种算法进行了比较和总结。

关键词：组合优化；模拟退火算法；遗传算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）19-4418-02

组合优化问题是当今世界中非常重要的一类问题，在这类问题中，有一部分问题在如今的计算机性能条件下进行求解往往需要耗费巨大的时间和储存空间，以至于根本无法进行求解，并且其中有很多问题是在人们的生活中产生的实际组合优化应用问题，若能很好地解决这类问题，人们的工作和生活方式便能变的更有效率。

模拟退火算法和遗传算法是人们多年来所找到的两种比较有效的算法，这两个算法虽不能得出优化问题的精确最优解，但是可以给出近似的最优解。下面，就让我们来看看这两个算法的原理，并根据一个简单的应用来分析和比较这两个算法。

1 模拟退火算法原理

模拟退火算法是根据自然界中的固体退火原理而推出的算法。

在自然界中，对于一个固体，将其加热使其温度至充分高，其内部粒子便随温度升变为无序状，此时内能增大，然后再让其徐徐冷却，此时其粒子逐渐趋向为有序状态，在每个温度都达到平衡态，最后，在常温时达到基态，固体的内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/（kT），其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。

模拟退火算法便是模拟上述的物理退火过程。在模拟退火算法中，用上述退火原理中的内能E来模拟目标函数值f，温度T为控制参数t，由t和一个初始解开始，对当前的解不断重复产生新解、计算目标函数差、接受或舍弃新解的迭代步骤，同时每一步迭代逐步衰减t值，最终当温度降低，算法终止于特定的温度，便得到近似最优解。其中退火过程由冷却进度表控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

2 遗传算法原理

同模拟退火算法一样，遗传算法也是人们由自然现象推导而来。

遗传算法的根源是自然界生物的进化法则。

众所周知，在进化过程中，每个种群将会面临一系列复杂的变异和环境选择，只有能适应环境变化的变异体才能继续生存下去，同时，对于生存有利的突变会随着存活下来的个体的染色体传给其下一代。

在遗传算法中，用一组染色体的集合模拟解的集合，用评价函数来模拟自然筛选。通过评价函数而筛选存活下来的解可以进行“产生突变的繁殖”，产生不同的下一代解集，然后再对下一代解集用评价函数进行筛选，选出下一代最优解，并与上一代最优解进行比较，看哪一个更合适，合适的那个解再用来繁殖下一代，如此反复，直到得出符合要求的最优解。

3 模拟退火算法与遗传算法的比较

下面，作者使用了模拟退火算法和遗传算法对一个简单的优化问题进行求解，并对此做出了浅析。

此优化问题为寻找一个目标函数的最大值，目标函数为f（x）=|11·number（x） - 150|，其中x为一个长度为30的二进制串，如x=（110100110100001111010110011010），number（x）代表的是x中1的个数，如number（000000000000000000000000000000） = 0、number（111111111111111111111111111111） = 30。

1）首先，作者使用模拟退火算法对此问题进行求解，算法的伪代码形式如下：

开始

t = 0

初始化温度 T

随即选择一个解x（30位二进制串形式）

对x进行评价

重复

重复

选择一个新的解x1，x1为对x中的一位进行反转（0变为1，1变为0）

若 f（x） < f（x1）

则x = x1

否则，若random[0，1） < exp{ （ f（x1） – f（x） ） / T }

则x = x1

直到 “达到热平衡”

T = g（T，t）

t= t+1

直到不再有可接受的变化

结束

其中，g（T，t）使温度T逐渐下降。

如上所示，经检验，此算法能成功地得出最优解，即最大值，为180。

2）接下来，作者使用了遗传算法对此问题进行了求解，其算法伪代码如下：

开始

随即地产生一个解的集合X

对X种所有的解进行评价，得出一个最优解xmax，并且记录下X中的得到最小值的解的集合Xmin。

无限循环：

对X中的解进行一定的“杂交操作”，得到下一代的解x1

若f（x1） > f（xmax）

则xmax = x1

淘汰Xmin中的一个解

否则，若f（x1） 大于{f（Xmin）}中的任何一个，则将x1加入解集中，并淘汰Xmin中的一个解。

可以看出，在此优化问题中，遗传算法的过程是个无限循环，并且该算法回鹘一个解集，此解集不断产生突变的后代，并不断向最优解靠近

以上便是使用两个算法求f（x）=|11·number（x） - 150|的最大值的全过程，经分析后知，模拟退火算法运行速度较慢，但是能得出最优化的解，而遗传算法是维护着一个接近最优解的解集，有可能最终会包含最优解。

4 总结

通过上述的分析，我们可以看出模拟退火算法和遗传算法的特点与不同。

总体来说，两个算法都能得到近似的最优解，并且稍加修改可以得出最优解的一个集合。模拟退火算法最终可以得到最好的解，但是其速度比较受影响，其算法过程由于退火过程和概率问题导致其速度很可能非常慢。遗传算法则可能一直得不到最好的最优解，但是其可以得到一个广阔的近似最优解的空间，使得解的选择性更多，并且在无法得到最优解的情况下会探索出无限接近最优解的解集。

参考文献：

[1] 米凯利薇姿.演化程序—遗传算法和数据编码的结合[M].北京：科学出版社，1999.

[2] Brian Christian.The most human human.POSTS&TELECOM PRESS，2012.

[3] Jeff Hawkins，Sandra Blakeslee.ON INTELLIGENCE[M].西安：陕西科学技术出版社，2006.

[4] George F Luger.Artificial intelligence.China Machine Press，2010.