人工智能导论课件人工智能导论——第三章1_2319080261章节幻灯片.pptVIP

* 比较慢的机器上的结果 本科2016.4.5 * * * * * * 充分条件：左边是大于1的，因此是充分的 * 忽略最后一式的推导，具体过程参考书上的内容 * * 起始温度的选取（1） 一个合适的初始温度，应保证平稳分布中每一个状态的概率基本相等，也就是接受概率P0近似等于1。在Metropolis准则下，即要求： 如果我们给定一个比较大的接受概率P0，则： 其中， 可以有以下估计方式： 起始温度的选取（2） 假设在t0下随机的生成一个状态序列，分别用m1和m2表示指标函数下降的状态数和指标函数上升的状态数， 表示状态增加的平均值。则m2个状态中，被接受的个数为： 所以平均接受率为： 求解有： 起始温度的选取（3） 模拟固体的升温过程： （1）给定一个希望的初始接受概率P0，给定一个较低的初始温度t0，比如t0＝1； （2）随机的产生一个状态序列，并计算该序列的接收率： 如果接收率大于给定的初始接受概率P0，则转（4）； （3）提高温度，更新t0，转（2）； （4）结束。 温度的下降方法（1） 等比例下降 温度的下降方法（2） 等值下降 温度的下降方法（3） 在一定的条件下，与模拟退火算法相伴的时齐马尔可夫链存在平稳分布。如果温度每次下降的幅度比较小的话，则相邻温度下的平稳分布应该变化不大，也就是说，对于任意一个状态i，相邻温度下的平稳分布应满足： 一个充分条件是： 两边取对数，并整理得： 用 代替 可得温度的衰减函数： 每一温度下的停止准则（1） 固定长度方法 在每一个温度下，都使用相同的Lk。Lk的选取与具体的问题相关，一般与邻域的大小直接关联，通常选择为问题规模n的一个多项式函数。 每一温度下的停止准则（2） 基于接受率的停止准则 ： 规定一个接受次数R，在某一温度下，只有被接受的状态数达到R时，在该温度下的迭代才停止，转入下一个温度。 规定一个状态接受率R，R等于该温度下接受的状态数除以总生成的总状态数。如果接受率达到了R，则停止该温度下的迭代，转入下一个温度。 在迭代的过程中，若干相邻的状态称为“一代”，如果相邻两代的解的指标函数差值小于规定的值的话，则停止该温度下的迭代。 算法的终止原则 （1） 零度法 设定一个正常数e，当时tke时，算法结束。 算法的终止原则 （2） 循环总控制法 给定一个指定的温度下降次数K，当温度的迭代次数达到K次时，则算法停止。 算法的终止原则 （3） 无变化控制法 如果在相邻的n个温度中，得到的解的指标函数值无任何变化，则说明算法已经收敛。 算法的终止原则 （4） 接受概率控制法 给定一个小的概率值p，如果在当前温度下除了局部最优状态外，其他状态的接受概率小于p值，则算法结束。 算法的终止原则 （5） 领域平均概率控制法 设大小为N的一个邻域，在邻域内一个状态被接受的平均概率为1/N。设f0、f1为该领域中的局部最优值和局部次最优值。则次最优解是除了局部最优解以外接受概率最大的，其接受概率为： 如果该概率值小于平均值1/N时，即： 可以认为从局部最优解跳出的可能性已经很小了，因此可以终止算法。此时的终止温度tf为： 算法的终止原则 （6） 相对误差估计法 设温度t时指标函数的期望值为： 则当终止温度1时，由泰勒展开近似有： 由于： 所以可用下式估计当前解与最优解之间的误差 ： 或者使用相对于 的相对误差： 说明：推导请见补充教材 实际计算时： 其中： 应用举例——旅行商问题 解的表示： n个城市的任何一种排列均是问题的一个可能解，表示为: 指标函数(能量函数) 其中 新解的产生 采用第一节介绍的两个城市间的逆序交换方式得到问题的一个新解。 设当前解是 ，被选中要逆序交换的城市是第u和第v个到访的城市，uv。则逆序排列u和v之间的城市，得到问题的新解为： 则两个路径的距离差为： 新解的接受准则 初始参数的确定 康立山等人的方法： 初始温度t0=280； 在每个温度下采用固定的迭代次数，Lk=100n，n为城市数； 温度的衰减系数＝0.92，即tk+1=0.92×tk； 算法的停止准则为：当相邻两个温度得到的解无任何变化时算法停止。 Nirwan Ansari和Edwin Hou的方法： 初始温度t0是这样确定的：从t0=1出发，并以t0=1.05×t0对t0进行更新，直到接受概率大于等于0.9时为止，此时得到的温度