爬⼭算法
在介绍这两种算法前，先介绍⼀下爬⼭算法。
爬⼭算法是⼀种简单的贪⼼搜索算法，该算法每次从当前解的临近解空间中选择⼀个最优解作为当前解，直到达到⼀个局部最优解。
爬⼭算法实现很简单，其主要缺点是会陷⼊局部最优解，⽽不⼀定能搜索到全局最优解。如图1所⽰：假设C点为当前解，爬⼭算法搜索到A点这个局部最优解就会停⽌搜索，因为在A点⽆论向那个⽅向⼩幅度移动都不能得到更优的解。
模拟退⽕算法(SA)绍兴市树人中学
为了解决局部最优解问题， 1983年，Kirkpatrick等提出了模拟退⽕算法（SA）能有效的解决局部最优解问题。模拟退⽕其实也是⼀种贪⼼算法，但是它的搜索过程引⼊了随机因素。模拟退⽕算法以⼀定的概率来接受⼀个⽐当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。
算法介绍
我们知道在分⼦和原⼦的世界中，能量越⼤，意味着分⼦和原⼦越不稳定，当能量越低时，原⼦越稳定。 “退⽕”是物理学术语，指对物体加温在冷却的过程。模拟退⽕算法来源于晶体冷却的过程，如果固体不处于最低能量状态，给固体加热再冷却，随着温度缓慢下降，固体中的原⼦按照⼀定形状排列，形成⾼密度、低能量的有规则晶体，对应于算法中的全局最优解。 ⽽如果温度下降过快，可能导致原⼦缺少⾜够的时间排列成晶体的结构，结果产⽣了具有较⾼能量的⾮晶体，这就是局部最优解。
radarsat
因此就可以根据退⽕的过程，给其在增加⼀点能量，然后在冷却，如果增加能量，跳出了局部最优解，这本次退⽕就是成功的。
算法原理
模拟退⽕算法包含两个部分即Metropolis算法和退⽕过程。Metropolis算法就是如何在局部最优解的情况下让其跳出来，是退⽕的基础。1953年Metropolis提出重要性采样⽅法，即以概率来接受新状态，⽽不是使⽤完全确定的规则，称为Metropolis准则。
状态转换规则
温度很低时，材料以很⼤概率进⼊最⼩能量状态
模拟退⽕寻优⽅法
注意事项
理论上，降温过程要⾜够缓慢，使得在每⼀温度下达到热平衡。如果降温速度过缓，所得到解的性能会较为令⼈满意，但是算法太慢会导致较搜索算法不具备优势。要确定在每⼀温度下状态转换的结束规则。实际操作可以考虑当连续m次的转换过程没有使状态发⽣变化时结束该温度下的状态转换。
选择初始温度和确定某个可⾏解的邻域的⽅法也要恰当。
算法流程
平台期
初始化
初始温度T
初始解状态S0（算法迭代的起点）
在可⾏解的邻域内产⽣新解S′，并判断该新解是否可以被接受。当连续m次的转换过程没有使状态发⽣变化时结束该温度下的状态转换。
判断是否满⾜终⽌温度，如果满⾜输出当前解作为最优解，否则降低温度。
最简单的下降⽅式是取定⼀降温系数α<1，以T n+1=αT n的形式下降，⽐如取α=0.99，⼀般取值为0.8到0.99之间；
其他温度下降⽅式有：T n=
T0
log(1+n)、T
n=
T0
1+n
遗传算法(GA)
算法介绍
初代种产⽣之后，按照适者⽣存和优胜劣汰的原理，逐代（generation）演化产⽣出越来越好的近似解，在每⼀代，根据问题域中个体的适应度（fitness）⼤⼩选择（selection）个体，并借助于⾃然遗传学的遗传算⼦（genetic operators）进⾏组合交叉（crossover）和变异（mutation），产⽣出代表新的解集的种。 遗传算法的流程
随机产⽣种。
根据策略判断个体的适应度，是否符合优化准则，若符合，输出最佳个体及其最优解，结束。否则，进⾏下⼀步。
依据适应度选择⽗母，适应度⾼的个体被选中的概率⾼，适应度低的个体被淘汰。
我上三年级了⽤⽗母的染⾊体按照⼀定的⽅法进⾏交叉，⽣成⼦代。
对⼦代染⾊体进⾏变异。
算法实现
编码
仅对浮点编码法进⾏介绍。
三星m300个体的每个基因值⽤某⼀范围内的⼀个浮点数来表⽰。在浮点数编码⽅法中，必须保证基因值在给定的区间限制范围内，遗传算法中所使⽤的交叉、变异等遗传算⼦也必须保证其运算结果所产⽣的新个体的基因值也在这个区间限制范围内。
⽐如⼀个9⽬标问题的⼀个染⾊体为:
[0.23, 0.82, 0.45, 0.74, 0.87, 0.11, 0.56, 0.69, 0.78], 区间范围限制为[0,1]
初始化种
⾃⾏⽤某种算法得到⼀个较好的初始种。
设定适应度函数
⽤于区分体中个体好坏的标准。
设置选择函数
对体中的所有个体按适应度⼤⼩进⾏排序，基于这个排序来分配各个个体被选中的概率。
单点交叉坂茂
变异操作
按照给定的变异率，对选定变异的个体，随机地进⾏变异。可随机取三个整数u,v,w，把u,v之间的基因段插到w后⾯。
参考⽹站与书籍
[1]【算法】超详细的遗传算法(Genetic Algorithm)解析www.jianshu/p/ae5157c26af9
[2] 深度学习 --- 模拟退⽕算法详解（Simulated Annealing， SAblog.csdn/weixin_42398658/article/details/84031235
[3] 数学建模算法与应⽤，司守奎，孙兆亮
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议