第九章 智能优化-2模拟退火算法培训资料.ppt

Sequence The length of the route 123456 30 BS Sequence The length of the route 132456 28 当前解 温度T＝1200 n=2 T=Th 求得初始解 BS=初始解 n=0 求得新的解 新的解比 当前解好？ 接受新的解 用新的解替换 当前解; n=n+1 nN？ BS=新的解 新的解比BS好？ T=rT T=t? End Start T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的有哪些信誉好的足球投注网站次数 是 否 是 否 是 否 是 否 是 否 Sequence The length of the route 123456 30 当前解 Sequence The length of the route 213456 27 新的解 接受新的解 温度T＝1200 n=0 T=Th 求得初始解 BS=初始解 n=0 求得新的解 新的解比 当前解好？ 接受新的解 用新的解替换 当前解; n=n+1 nN？ BS=新的解 新的解比BS好？ T=rT T=t? End Start T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的有哪些信誉好的足球投注网站次数 是 否 是 否 是 否 是 否 是 否 Sequence The length of the route 213456 27 BS Sequence The length of the route 213456 27 当前解 温度T＝1200 n=1 2.4 模拟退火算法的改进 模拟退火算法的优点 质量高； 初值鲁棒性强； 简单、通用、易实现。 模拟退火算法的缺点 由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。 2.4.1 模拟退火算法的优缺点 2.4 模拟退火算法的改进 改进的可行方案 （1）设计合适的状态产生函数； （2）设计高效的退火历程； （3）避免状态的迂回有哪些信誉好的足球投注网站； （4）采用并行有哪些信誉好的足球投注网站结构； （5）避免陷入局部极小，改进对温度的控制方式； （6）选择合适的初始状态； （7）设计合适的算法终止准则。 2.4.2 改进内容 2.4 模拟退火算法的改进 改进的方式 （1）增加升温或重升温过程，避免陷入局部极小； （2）增加记忆功能（记忆“Best so far”状态）； （3）增加补充有哪些信誉好的足球投注网站过程（以最优结果为初始解）； （4）对每一当前状态，采用多次有哪些信誉好的足球投注网站策略，以概率接受区域内的最优状态； （5）结合其它有哪些信誉好的足球投注网站机制的算法； （6）上述各方法的综合。 2.4.2 改进内容 2.4 模拟退火算法的改进 改进的思路 （1）记录“Best so far”状态，并即时更新； （2）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续 m1 步保持不变则认为Metropolis抽样稳定，若连续 m2 次退温过程中所得最优解不变则认为算法收敛。 2.4.3 一种改进的模拟退火算法 2.4 模拟退火算法的改进 改进的退火过程 （1）给定初温t0，随机产生初始状态s，令初始最优解s*=s，当前状态为s(0)=s，i=p=0； （2）令t=ti，以t，s*和s(i)调用改进的抽样过程，返回其所得最优解s*’和当前状态s’(k)，令当前状态s(i)=s’(k)； （3）判断C(s*)C(s*’)? 若是，则令p=p+1；否则，令s*=s*’，p=0； （4）退温ti+1=update(ti)，令i=i+1； （5）判断pm2? 若是，则转第(6)步；否则，返回第(2)步； （6）以最优解s*作为最终解输出，停止算法。 2.4.3 一种改进的模拟退火算法 2.4 模拟退火算法的改进 改进的抽样过程 （1）令k=0时的初始当前状态为s’(0)=s(i)，q=0； （2）由状态s通过状态产生函数产生新状态s’，计算增量?C’=C(s’)-C(s)； （3）若?C’0，则接受s’作为当前解，并判断C(s*’)C(s’)? 若是，则令s*’=s’，q=0；否则，令q=q+1。若?C’0，则以概率exp(-?C’/t)接受s’作为下一当前状态； （4）令k=k+1，判断qm1? 若是，则转第(