24模拟退火算法

第三篇模拟退火算法一、模拟退火算法的基本思想二、模拟退火算法的实现三、模拟退火算法的应用一、模拟退火算法的基本思想启发注意到一个自然规则：物质总是趋于最低的能态。水总是向低处流。电子总是向最低能级的轨道排布。最低能态是最稳定的状态。物质会”自动”地趋向的最低能态。模拟退火算法的设计与原理猜想物质自动趋向的最低能态与函数最小值之间有相似性！！！我们能不能设计一种算法求函数最小值，就像物质”自动”地趋向最低能态？降温图像离散函数图像相似性?最小值最低能态模拟退火算法的设计与原理物理模型——固体退火退火俗称固体降温先把固体加热至足够高温，使固体中所有粒子处于无序的状态（最高的熵值），然后将温度缓慢下降，粒子渐渐有序（熵值下降），这样只要温度上升得足够高，冷却过程足够慢，则所有粒子最终会处于最低能态（最低的熵值）。t07a0.187H5Tt()Ht0H()eatt0()0102030051015Tt()t最低能态时间温度Metropolis准则（1953）——以概率接受新状态p=exp[-(Ej-Ei)/kBT]在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。模拟退火算法的设计与原理提出模拟退火算法(SA)就是这样一个将退火过程中系统熵值类比为目标函数值F，来模拟这个退火系统的算法。二、模拟退火算法的实现SA算法在Markov链长度内持续进行“产生新解—判断—接受/舍弃”的迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。算法终止时的当前解即为所得近似最优解。这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。相似性比较优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量组合优化与物理退火的相似性模拟退火算法的优化回火技术如图所示，若粒子开始处于D状态，若让能量逐渐减小，则粒子最终到达的是A点(局部最低点)而不是B(全局最低点)点，这是我们所不希望的。解决的办法是对系统经常地”摇动”一下，就很可能把粒子从D点越过C点摇到B点，而把它摇到A点的可能性减小。这就是回火技术：降温后以一定概率升温，引入产生函数扰动因子，来控制搜寻全局最优值的范围。ABCD模拟退火算法的应用前景算法特性优点1.可并行性2.扩展性和通用性它可以高效的解决几乎所有的组合优化问题。3.高效率，高性价比1.逼近速度快，可极快的求得很好的近似值2.SA算法比传统算法速度快的多了，解也以1的概率趋于最优解。在解的质量与时间的比上效果良好。传统算法要运行几年的情况，SA只需几秒。3.具有全局优化特性三、模拟退火算法的应用3.130城市TSP问题（d*=423.741byDBFogel）TSPBenchmark问题4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450算法流程给给给给给给给给给给给给给Si给给给给给Sj给给给给给给给s*给给给给给给给给给给给给min{1,exp[-(C(sj)-C(si))/tk]}=random[0,1]给给给给给给给给给给给给给给给给k=0Metropolis给给给给给给给给给给tk+1=update(tk)给k=k+1给Si给Sj，给给给给给给给给s*给给给给给给给给YNYNYN初始温度的计算fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0))/log(0.9);三、模拟退火算法的实现与应用3.130城市TSP问题（d*=423.741byDBFogel）状态产生函数的设计（1）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。283591467283591467283591467281593467283419567235981467三、模拟退火算法的应用3.130城市TSP问题（d*=423.741byDBFogel）参数设定截止温度tf=0.01;退温系数alpha=0.90;内循环次数L=200*CityNum;三、模拟退火算法的应用3.130城市TSP问题（d*=423.741byDBFogel）运行过程三、模拟退火算法的应用3.130城市TSP问题（d*=423.741byDBFogel）运行过程三、模拟退火算法的应用3.130城市TSP问题（d*=423.741byDBFogel）运行过程三、模拟退火算法的应用3.130城市TSP问题（d*=423.741byDBFogel）运行过程三、模拟退火算法的应用3.130城市TSP问题（d*=423.741byDBFogel）运行过程三、模拟退火算法的应用3.130城市TSP问题（d*=423.741byDBFogel）运行结果三、模拟退火算法的应用3.130城市TSP问题（d*=423.741byDBFogel）小结模拟退火：模仿自然界的物理行为，来求解函数最小值的方法小结创意独特摒弃旧思维----从函数性质分析创造新思维----从自然规律入手个人认为这个创意是独特的，独辟蹊径。向自然学习，利用了物理的理论来解决数学问题。效率高虽不是最优解，但其优性较速度来说，效率是极高的。时间就是金钱。在现代市场中这很重要。