模拟退火算法的教程培训资料.ppt

算法流程 1 30城市TSP问题（d*=423.741 by D B Fogel） 8 模拟退火算法的实现与应用 初始温度的计算 for i=1:100 route=randperm(CityNum); fval0(i)=CalDist(dislist,route); end t0=-(max(fval0)-min(fval0))/log(0.9); 1 30城市TSP问题（d*=423.741 by D B Fogel） 8 模拟退火算法的实现与应用 状态产生函数的设计 （1）互换操作，随机交换两个城市的顺序； （2）逆序操作，两个随机位置间的城市逆序； （3）插入操作，随机选择某点插入某随机位置。 1 30城市TSP问题（d*=423.741 by D B Fogel） 2 8 3 5 9 1 4 6 7 2 8 3 5 9 1 4 6 7 2 8 3 5 9 1 4 6 7 2 8 1 5 9 3 4 6 7 2 8 3 4 1 9 5 6 7 2 3 5 9 8 1 4 6 7 8 模拟退火算法的实现与应用 参数设定 截止温度 tf=0.01; 退温系数 alpha=0.90; 内循环次数 L=200*CityNum; 1 30城市TSP问题（d*=423.741 by D B Fogel） 8 模拟退火算法的实现与应用 运行过程 1 30城市TSP问题（d*=423.741 by D B Fogel） 8 模拟退火算法的实现与应用 运行过程 1 30城市TSP问题（d*=423.741 by D B Fogel） 8 模拟退火算法的实现与应用 运行过程 1 30城市TSP问题（d*=423.741 by D B Fogel） 8 模拟退火算法的实现与应用 模拟退火算法 Simulated Annealing Algorithm 信息与计算科学 卿 铭 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却；加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到某种稳定状态，基态，内能减为最小。 1 模拟退火算法的思想 物理退火过程 加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态； 等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态； 冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。 1 模拟退火算法的思想 缓慢降温（退火，annealing）时，可达到最低能量状态，较为柔韧；但如果快速降温（淬火，quenching），会导致不是最低能态的非晶形，较硬易断。 大自然知道慢工出细活： 缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最稳定。 1 模拟退火算法的思想 模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。 模拟退火算法是通过赋予有哪些信誉好的足球投注网站过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。 模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用。 组合优化与物理退火的相似性比较 组合优化问题 金属物体 解 粒子状态 最优解 能量最低的状态 设定初温 熔解过程 Metropolis抽样过程 等温过程 控制参数的下降 冷却 目标函数 能量 从某一初始温度开始，伴随温度的不断下降，结合概