沈阳农业大学信息与电气工程学院智能优化方法课件 第三章.pptVIP

第三章 模拟退火算法 3.1 模拟退火算法及模型 3.1.1 物理退火过程 3.1.2 组合优化与物理退火的相似性 3.1.3 模拟退火算法的基本思想和步骤 3.2 模拟退火算法的关键参数和操作的设计 3.2.1 状态产生函数 3.2.2 状态接受函数 3.2.3 初温 3.2.4 温度更新函数 3.2.5 内循环终止准则 3.2.6 外循环终止准则 3.3 模拟退火算法的改进 3.3.1 模拟退火算法的优缺点 3.3.2 改进内容 3.3.3 一种改进的模拟退火算法 3.4 模拟退火算法实现与应用 3.4.1 30城市TSP问题（d*=423.741 by D B Fogel） 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 热力学中的退火现象指物体逐渐降温时发生的物理現象： 温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。缓慢降温（退火，annealing）时，可达到最低能量状态；但如果快速降温（淬火，quenching），会导致不是最低能态的非晶形。 大自然知道慢工出细活： 缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最稳定。 模仿自然界退火現象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性 从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 3.1 模拟退火算法及模型 3.2 模拟退火算法关键参数和操作的设计 3.2 模拟退火算法关键参数和操作的设计 3.2 模拟退火算法关键参数和操作的设计 3.2 模拟退火算法关键参数和操作的设计 3.2 模拟退火算法关键参数和操作的设计 3.2 模拟退火算法关键参数和操作的设计 3.2 模拟退火算法关键参数和操作的设计 3.3 模拟退火算法的改进 3.3 模拟退火算法的改进 3.3 模拟退火算法的改进 3.3 模拟退火算法的改进 3.3 模拟退火算法的改进 3.3 模拟退火算法的改进 3.4 模拟退火算法的实现与应用 3.4 模拟退火算法的实现与应用 3.4 模拟退火算法的实现与应用 3.4 模拟退火算法的实现与应用 3.4 模拟退火算法的实现与应用 3.4 模拟退火算法的实现与应用 3.4 模拟退火算法的实现与应用 3.4 模拟退火算法的实现与应用 3.4 模拟退火算法的实现与应用 3.4 模拟退火算法的实现与应用 3.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*作为最终解输出，停止算法。 3.3.3 一种改进的模拟退火算法 智能优化方法 沈阳农业大学信电学院 2014年 改进的抽样过程 （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? 若是，则转第(5)步；否则，返回第(2)步； （5）将当前最优解s*’和当前状态s’(k)返回改进退火过程。