编辑:连吃十三碗
校正:随心
目录
1. 模拟退火算法基本概念
2. 模拟退火算法基本流程
3. 遗传模拟退火算法matlab代码
1. 模拟退火算法基本概念
自然凝结的、不受外界干扰而形成的晶体拥有整齐规则的几何外形。那么从液态到固态,晶体分子是如何从杂乱无章的状态转变为排列极为整齐的状态呢?分子之间是如何“寻优”,找到“最优解”的呢?
模拟退火(simulated annealing,SA)的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是一种通用的优化算法,其物理退火过程由加温过程、等温过程、冷却过程这三部分组成。
模拟退火最明显的特点就是使用了Metropolics准则,使得算法在迭代时能有效跳出局部最优,寻求全局最优。
2. 模拟退火算法基本流程
一、加温过程
给我们的算法设置一个初温T0。
二、等温过程
1初始解
设置初始解S1
2产生新解
以旧解S1创建新解S2。可以用单个体产生单个体,也可以像遗传算法中通过个体间选择、交叉和变异的方式产生新个体。
如10个城市的TSP问题{1,2,3,4,5,6,7,8,9,10}
S1中某个体
1 2 3 4 5 6 7 8 9
变换为S2中与S1中相同位置个体(单个体产生单个体)
1 2 9 4 5 6 7 8 3 10(调换两城市)
或者
1 2 9 8 7 6 5 4 3 10(路径中某一段调转)
3 Metropolics准则
Metropolics准则规定,在新旧解选取中,如果新解优于旧解,则选用新解。如果新解非优于旧解,则生成一个概率选取新解。
如目标函数f(S),目标值取值越小越好。旧解S1,目标值f(S1),新解S2,目标值f(S2),目标值差df=f(S2)-f(S1)。如果df<0,则选用新解,淘汰旧解。否则以概率exp(-df/T)接受新解。
三、冷却过程
设置一个降温速率q,则第n代的温度为Tn=q*Tn-1。降温速率q一般设置为0.9左右,慢工出细活。降温一次为一轮迭代,当温度降到结束温度Tend时,程序结束。
简单来说,整体过程与晶体冷却过程一致。降温前,分子间距离很远且在空间顺序上没有规律。如图
降温时,分子间距离变短,但仅仅缩短距离很容易使整体过程陷入局部最优,如图
但如果以概率接受恶化解(Metropolics准则),就像分子在缩短距离的同时每个分子本身也在做小规模的无规则运动,这就给凝固过程提供了很多可能性。你挤一挤,我让一让,最终使得分子的结构有序,我们也得到了最优解。如图。
3. 遗传模拟退火算法matlab代码
链接:https://pan.baidu.com/s/1rANhfxwkvvuLh5ZbiCmV0w
提取码:h444