第二章第二章 模拟退火算法模拟退火算法（Simulated AnnealingSimulated Annealing）搜索问题描述搜索问题描述除当前高度外，对环境除当前高度外，对环境没有任何感知没有任何感知最优解位于海拔最优解位于海拔最高处最高处搜索问题描述搜索问题描述nLandscape with various featuresObjectivefunctionshoulderglobal maxlocal maxflat local maxcurrent stateState space搜索算法搜索算法n盲目搜索盲目搜索还是还是启发式搜索启发式搜索？n按照预定的控制策略实行搜索，在搜索过程中按照预定的控制策略实行搜索，在搜索过程中获取的中间信息不用来改进控制策略，称为盲获取的中间信息不用来改进控制策略，称为盲目搜索，反之，称为启发式搜索。目搜索，反之，称为启发式搜索。n关于关于“启发式启发式”，可有两种看法：，可有两种看法：n1) 任何有助于找到问题的最优解，但不能保证找到任何有助于找到问题的最优解，但不能保证找到最优解的方法均是启发式方法；最优解的方法均是启发式方法；n2) 有助于加速求解过程和找到较优解的方法是启发有助于加速求解过程和找到较优解的方法是启发式方法。式方法。搜索算法搜索算法n盲目搜索盲目搜索n深度优先、广度优先、代价优先、向前、向后、双深度优先、广度优先、代价优先、向前、向后、双向。向。n启发式搜索启发式搜索n爬山法、模拟退火算法、遗传算法、粒子群算法、爬山法、模拟退火算法、遗传算法、粒子群算法、蚁群算法。蚁群算法。贪心算法贪心算法1.随机选定一个初始解随机选定一个初始解x0；2.Do while （终止条件不满足）终止条件不满足）1.在某个邻域函数所定义的邻域范围内，按照某个在某个邻域函数所定义的邻域范围内，按照某个（随机）扰动（随机）扰动 产生策略，得到一个新解产生策略，得到一个新解xi；2.对新解进行评估，得对新解进行评估，得f(xi)；3.如果如果f(xi) f(xi)（或者或者f(xi) f(xi) 且且f(xi) f(xij)（或者或者f(xi) f(xi) 且且f(xi) f(xij)（或者或者f(xi) Tmin /降温过程降温过程1)for j = 1k /等温过程等温过程1)对对当当前前最最优优解解xbest按按照照某某一一邻邻域域函函数数，产产生生一一新新的的解解xnew。计计算算新新的的目目标标函函数数值值E(xnew) ，并并计计算算目目标标函函数数值值的的增增量量 E = E(xnew) - E(xbest) 。2)如果如果 E 0，则则xbest = xnew；3)如果如果 E 0，则则p = exp(- E /T(i);1)如果如果c = random0,1 p， xbest = xnew; 否则否则 xbest = xbest。2)End for3)按照温度控制策略更新按照温度控制策略更新T；4)End Do5)输出当前最优点，计算结束。输出当前最优点，计算结束。模拟退火算法（要素）模拟退火算法（要素）1、状态空间与状态产生函数（邻域函数）、状态空间与状态产生函数（邻域函数）n搜索空间也称为状态空间，它由经过编码的可行解的搜索空间也称为状态空间，它由经过编码的可行解的集合所组成。集合所组成。n状态产生函数状态产生函数(邻域函数邻域函数)应尽可能保证产生的候选解应尽可能保证产生的候选解能遍布全部解空间。通常由两部分组成，即能遍布全部解空间。通常由两部分组成，即产生候选产生候选解的方式解的方式和和候选解产生的概率分布候选解产生的概率分布。n候选解一般按照某一概率分布对解空间进行随机采样候选解一般按照某一概率分布对解空间进行随机采样来获得。来获得。n概率分布可以是均匀分布、正态分布、指数分布等等。概率分布可以是均匀分布、正态分布、指数分布等等。模拟退火算法（要素）模拟退火算法（要素）2、状态转移概率（接受概率）、状态转移概率（接受概率） pn状态转移概率是指从一个状态状态转移概率是指从一个状态xold(一个可行解一个可行解)向另一向另一个状态个状态xnew(另一个可行解另一个可行解)的转移概率的转移概率;n通俗的理解是接受一个新解为当前解的概率通俗的理解是接受一个新解为当前解的概率;n它与当前的温度参数它与当前的温度参数T有关，随温度下降而减小。有关，随温度下降而减小。n一般采用一般采用Metropolis准则准则模拟退火算法（要素）模拟退火算法（要素）3、冷却进度表、冷却进度表T(t)冷冷却却进进度度表表是是指指从从某某一一高高温温状状态态To向向低低温温状状态态冷冷却却时时的的降降温管理表。温管理表。假设时刻假设时刻t的温度用的温度用T(t)来表示，则来表示，则经典模拟退火算法的降经典模拟退火算法的降温方式温方式为：为： 而而快速模拟退火算法的降温方式快速模拟退火算法的降温方式为：为：这两种方式都能够使得模拟退火算法收敛于全局最小点。这两种方式都能够使得模拟退火算法收敛于全局最小点。模拟退火算法（要素）模拟退火算法（要素）4、初始温度、初始温度T0实验表明，初温越大，获得高质量解的几率越大，但实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：虑优化质量和优化效率，常用方法包括：(1) 均匀抽样一组状态，以各状态目标值的方差为初温。均匀抽样一组状态，以各状态目标值的方差为初温。(2) 随机产生一组状态，确定两两状态间的最大目标值差随机产生一组状态，确定两两状态间的最大目标值差| max|，然后依据差值，利用一定的函数确定初温。比如，然后依据差值，利用一定的函数确定初温。比如，t0= max/pr ，其中其中pr为初始接受概率。为初始接受概率。(3) 利用经验公式给出。利用经验公式给出。模拟退火算法（要素）模拟退火算法（要素）5、内循环终止准则、内循环终止准则或称或称Metropolis抽样稳定准则，用于决定在各温度抽样稳定准则，用于决定在各温度下产生候选解的数目。常用的抽样稳定准则包括：下产生候选解的数目。常用的抽样稳定准则包括：(1) 检验目标函数的均值是否稳定；检验目标函数的均值是否稳定；(2) 连续若干步的目标值变化较小；连续若干步的目标值变化较小；(3) 按一定的步数抽样。按一定的步数抽样。模拟退火算法（要素）模拟退火算法（要素）6、外循环终止准则、外循环终止准则即算法终止准则，常用的包括：即算法终止准则，常用的包括：(1) 设置终止温度的阈值；设置终止温度的阈值；(2) 设置外循环迭代次数；设置外循环迭代次数；(3) 算法搜索到的最优值连续若干步保持不变；算法搜索到的最优值连续若干步保持不变；(4) 检验系统熵是否稳定。检验系统熵是否稳定。模拟退火算法的改进模拟退火算法的改进(1) 设计合适的状态产生函数，使其根据搜索进程的需要设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。表现出状态的全空间分散性或局部区域性。(2) 设计高效的退火策略。设计高效的退火策略。(3) 避免状态的迂回搜索。避免状态的迂回搜索。(4) 采用并行搜索结构。采用并行搜索结构。(5) 为避免陷入局部极小，改进对温度的控制方式为避免陷入局部极小，改进对温度的控制方式(6) 选择合适的初始状态。选择合适的初始状态。(7) 设计合适的算法终止准则。设计合适的算法终止准则。模拟退火算法的改进模拟退火算法的改进也可通过增加某些环节而实现对模拟退火算法的改进。主要的改也可通过增加某些环节而实现对模拟退火算法的改进。主要的改进方式包括：进方式包括：(1) 增加升温或重升温过程增加升温或重升温过程。在算法进程的适当时机，将温度适当提。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。态，避免算法在局部极小解处停滞不前。(2) 增加记忆功能增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将当前遇到的最优解，可通过增加存储环节，将“Best So Far”的的状态记忆下来。状态记忆下来。(3) 增加补充搜索过程增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。初始状态，再次执行模拟退火过程或局部性搜索。(4) 对每一当前状态，采用多次搜索策略，以概率接受区域内的最优对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准状态，而非标准SA的单次比较方式。的单次比较方式。(5) 结合其他搜索机制的算法，如遗传算法、混沌搜索等。结合其他搜索机制的算法，如遗传算法、混沌搜索等。(6)上述各方法的综合应用。上述各方法的综合应用。算法实现与应用算法实现与应用nTSP问题的求解问题的求解n编码（城市编号顺序编码）编码（城市编号顺序编码）n状态产生函数（逆转算子）状态产生函数（逆转算子）n状态接受函数状态接受函数n初温与初始状态，初温与初始状态， T0= max/pr n降温函数设计降温函数设计n温度修改准则和算法终止准则温度修改准则和算法终止准则结果（结果（400个城市）个城市）结果（结果（400个城市）个城市）