模拟退火算法与MATLAB实现PPT课件.pptx

模拟退火算法及其MATLAB实现，1、第6章模拟退火算法及其MATLAB实现，6.1算法基本理论，6.2算法MATLAB实现，6.3应用实例，2、简单了解退火算法的特点，介绍爬山前模拟退火算法。爬山算法是一种简单的贪婪搜索算法，每次都从当前解的相邻解空间中选择一个最优解作为当前解，直到达到局部最优解。如果点c是当前解，爬山算法在找到点A的局部最优解时将停止搜索，因为它不能得到更好的解，不管它在点A处稍微向那个方向移动。在搜索局部最优解A之后，模拟退火算法将以一定的概率接受E的移动。也许在几次这样的非局部最优的移动之后，它将到达点D并跳出局部最大值A。算法概述。工程中许多实际优化问题的目标函数是非凸的，存在许多局部最优解。解决全局优化问题的方法可以分为两类：确定性方法和随机方法。确定性算法适用于解决具有某些特殊性质的问题，而梯度法和一般随机搜索法是沿着目标函数的下降方向搜索，因此它们往往陷入局部最优解而不是全局最优解。5、6.1算法基本理论，1、算法概述，模拟退火算法是一种通用的概率算法。它用于在大的搜索空间中寻找问题的最优解。1953年，Metropolis等人提出了模拟退火的概念。1983年，柯克帕特里克等人将模拟退火算法引入组合优化领域。基本理论，基本思想，退火，通常称为固体冷却，首先将固体加热到足够高的温度，使固体中的所有粒子处于无序状态，然后缓慢降低温度，使粒子逐渐有序化，因此只要温度升得足够高，冷却过程足够慢，所有粒子最终将处于最低能量状态。该算法试图随着控制参数t的减小而逐渐减小目标函数值f(内部能量e)，直到它接近全局最小值(在中低温退火中的最低能量状态)。该算法的工作原理类似于固体退火过程。6.1算法基本理论，模拟退火算法起源，8，6.1算法基本理论，大都会标准，-接受概率新状态。如果在温度T，当前状态I(解1)新状态J(解2)如果(目标函数2)，概率=大于区间0，1的随机数，则状态J仍被接受为当前状态；如果不是，保留状态I是当前状态。9，新状态的内部能量，当前状态的内部能量，温度，EjEi(差解)，0，当前解，扰动数，1=，结束，输出当前解，扰动，生成新解1，Y，N，N，Y，Y，N，14，6.1算法的基本理论，4，算法的基本步骤，算法本质上分为两层循环，随机扰动在任何温度下生成新解，计算目标函数值的变化，并决定是否接受。由于算法的初始温度相对较高，初始时也可以接受E增加的新解，这样就可以跳出局部最小值，然后通过缓慢降低温度，算法可以收敛到全局最优解。尽管在低温下接受函数已经很小，但仍有可能接受更差的解决方案。因此，在退火过程中遇到的最佳可行解(历史最优解)通常被记录下来，并在算法终止之前与最后被接受的解一起输出。该算法的基本理论如下：1 .新解决方案的生成需要在解决方案空间的每个区域尽可能多地覆盖。这样，当在某个恒定温度下不断产生新的解时，局部最优解可能会跳出。2.收敛的一般条件：初始温度足够高；热平衡时间足够长；终端温度足够低；冷却过程足够慢。16，6.1算法基础理论，5，几种解释，17，6.1算法基础理论，6，算法adv算法的MATLAB实现，18，6.2，旅行推销员问题，一个商人想在N个不同的城市销售商品，每两个城市中我和J之间的距离是D，如何选择一条路径使商人在每个城市走一次后返回起点的最短路径。例如，有52个城市，每个城市的坐标都是已知的。请每个城市去一次，然后回到起点。走最短的路。19，初始温度(93)，随机初始解(1至52的随机排列)。计算两个解的目标函数之间的差(两条路径之间的差)，0，接受新解作为当前解，计算概率与随机数的差0，1，差大于0，3，当前解，扰动数10000，1=0.99，结束，输出当前解，扰动，生成新解1，y，n，y，y，n，扰动数0.5，随机生成数0-1，两次变换， 三次变换，n，MATLAB实现Y，20，6.2算法，1，算法设计步骤，21，6.2算法MATLAB实现，1，算法设计步骤，2，新解生成(扰动)(1)两种变换方法：可选序号，集合，交换，访问之间的顺序。 (2)三种转换方法：可选序列号，设置=tfforr=1:马尔可夫_长度如果(rand 0.5)%，随机生成一个01的数，如果小于0.5，则两次转换ind 1=0；ind 2=0；而(ind 1=ind 2)ind 1=ceili(rand。*金额)；ind2=上限(兰特。*金额)；endtmp 1=sol _ new(ind 1)；sol _ new(ind 1)=sol _ new(ind 2)；sol _ new(ind 2)=tmp 1；否则，ind1=0的三个转换；ind 2=0；ind 3=0；而(ind1=ind2)|(ind1=ind3).| |(ind 2=ind 3)| |(ABS(ind 1-ind 2)=1)ind 1=ceili(r