[人工智能]模拟退火算法及实践.pdfVIP

[⼈⼯智能]模拟退⽕算法及实践 模拟退⽕算法 算法原理 算法伪码 解决TSP问题 算法可视化演⽰ 算法原理 摸拟退⽕算法是 于随机有哪些信誉好的足球投注网站的，即在解的空间中展开随机有哪些信誉好的足球投注网站的。当问题的空间很⼤，⽽可⾏解⽐较多，并且对解的精度要求不⾼时，随 机有哪些信誉好的足球投注网站是很有效的解决办法，因为其他的做法在这个时候时空效率不能让⼈满意。⽽借助演化思想和群集智能思想改进过的随机算法更是对 解的分布有规律的复杂问题有 良好的效果。 所谓退⽕是冶⾦专家为了达到某些特种晶体结构重复将⾦属加热或冷却的过程，该过程的控制参数为温度T。模拟退⽕法的 本思想是 ：在 系统朝着能量减⼩的趋势这样⼀个变化过程中，偶尔允许系统跳到能量较⾼的状态，以避开局部极⼩点，最终稳定达到全局最⼩点。可以看 到模拟退⽕不是单纯的采⽤贪⼼策略，它每获得⼀个解，对于该解有两种做法 ：若该解为更优解，则100%采纳 ；若该解为劣解，以⼀定的 概率采纳该解，也就是说可能丢弃，可能采纳。所以在模拟退⽕算法的随机有哪些信誉好的足球投注网站过程中，当前的采纳解是时好时坏，呈现出⼀种不断波动的 情况，但在总体的过程中⼜朝着最优的⽅向收敛。 评估解的好坏取决于问题的语境，例如旅⾏商TSP问题，我们⽤全部的距离加起来作为解的优劣情况。 算法伪码 （1）由⼀个产⽣函数从当前解产⽣⼀个位于解空间的新解 ；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变 换即可产⽣新解的⽅法，如对构成新解的全部或部分元素进⾏置换、互换等。 （2）计算与新解所对应的⽬标函数差。因为 ⽬标函数差仅由变换部分产⽣，所以⽬标函数差的计算最好按增量计算。 （3）判断新解是否被接受,判断的依据是⼀个接受准则，最常⽤的接受准则是Metropolis准则: 若ΔT0则接受S′作为新的当前解S，否则 以概率exp(- ΔT/T)接受S′作为新的当前解S。 （4）当新解被确定接受时，⽤新解代替当前解，这只需将当前解中对应于产⽣新解时的变换部分予以实现，同时修正 ⽬标函数值即可。此 时，当前解实现了⼀次迭代。可在此 础上开始下⼀轮试验。⽽当新解被判定为舍弃时，则在原当前解的 础上继续下⼀轮试验。 //参考百度百科 s:=s0;e:=E(s)//设定⽬前状态为s0，其能量E(s0) k:=0//评估次数k while kkmax and eemax //若还有时间 （评估次数k还不到kmax）且结果还不够好 （能量e不够低）则 ： sn:=neighbour(s)// 随机选取⼀临近状态sn en:=Esn)//sn的能量为E(sn) if random() (e,en,temp(k/kmax)) then//决定是否移⾄临近状态sn s:=sn;e:=en//移⾄临近状态sn k:=k+1//评估完成，次数k加⼀ returns// 回转状态s 模拟退⽕是⼀个不断迭代的过程，我们通过设定⼀个迭代次数来模拟时间，注意这个迭代次数，不能多也不能少，具体是通过实践出来的。 如果设置得太⼩，那么模拟过程还没有收敛就已经结束了；⽽设置得太⼤，那么收敛之后的迭代式浪费时间，因为收敛之后已经不会再变 了。 （收敛就是达到 ⽬前的最优解状态）所以经过多次尝试调出⼀个恰当的迭代次数是⾮常有必要。 解决TSP问题 了解模拟退⽕的 本原理之后，实践是最好的学习⽅式。 TSP问题背景 TSP问题，假设⼀个旅⾏商⼈要去n个城市，给出n个城市的坐标，他必须经过且只经过每个城市⼀次，要求最后回到出发的城市，并且要求 他选择的路径是所有路径中的最⼩值。 拟定算法 (1).随机⽣成⼀个城市序列作为初始解，⽐如1、2、… 140，这样的⼀个序列 ；设置合适的初温 ； (2).通过交换两个城市的位置得到序列的领域，作为新解，如果温度为0，则转(6) ； (3).将新解与最优解⽐较，如果新解⼩于最优解，则将新解作为最优解,否则则以Metropolis 准则决定是否接受差解为最优解 ； (4).如果系统处于平衡状态，则转(5)，否则接着执⾏(2) ； (5).降温，迭代计数器加 1，返回(2) ； (6).输出最优解。 其中，我们给每个城市编号1-n，每⼀个解对应⼀个路径序列，代表通过这个路径⾛遍全部城市。我们评估函数就是这个路