模拟退火算法ppt课件.ppt

《模拟退火算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、SimulatedAnnealing（模拟退火算法）模拟退火算法的思想最早是由Metropo比等(1953)提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于MenteCalro迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解．即在局部优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，目前己在工程中

2、得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、图像处理等领域。退火工艺:退火是将金属和合金加热到适当温度，保持一定时间，然后缓慢冷却的热处理工艺。退火后组织亚共析钢是铁素体加片状珠光体；共析钢或过共析钢则是粒状珠光体。总之退火组织是接近平衡状态的组织。退火的目的:①降低钢的硬度，提高塑性，以利于切削加工及冷变形加工。②细化晶粒，消除因铸、锻、焊引起的组织缺陷，均匀钢的组织和成分，改善钢的性能或为以后的热处理作组织准备。③消除钢中的内应力，以防止变形和开裂SimulatedAnn

3、ealing相似性：金属问题能量状态成本函数温度控制参数完整排列的晶体结构问题的最优解Globaloptimalsolutioncanbeachievedaslongasthecoolingprocessisslowenough.Optimization,steepestdescentandlocalminimaf(x)GlobalminimumLocalminimumLocalminimumLocalminimum要从局部最优逃出，必须上行（up-step）SA的上行机制：△＝（当前

4、解）—（下一个解）T为温度，即SA的控制参数SA接受相邻解的标准令X为当前解X’新的解（相邻解）C(x)(C(x’))betheenergystate(cost)ofx(x’)概率Paccept=exp[(C(x)-C(x’))/T]N=Random(0,1)无条件接受相邻解，如果：C(x’)=C(x),即相邻解比当前解差当N

5、e）L每一特定温度下的搜索次数：退火过程设定CoolingSchedule:N温度T的主要作用：决定接受差的解的概率初始温度的设定：由可忍受的解差的程度和接受的概率决定，比如以0.8的概率接受比当前解值大100，初始温度应为多少？一般温度设定为500——1000较为合适。需要运行程序多试。退火过程设定N温度T的降低过程：每次减少固定的值：T’=T-Td每次按固定比例减少：T’=T*r，此方法比较常用每个特定温度下的搜索次数L：根据计算耗时来确定。搜索的收敛：温度降低到设定的最低温度，如0.5度。Alg

6、orithmInitializeinitialsolutionx,highesttemperatureTh,andcoolesttemperaturetT=ThWhenthetemperatureishigherthantWhilenotinequilibriumSearchforthenewsolutionX’AcceptorrejectX’accordingtoMetropolisCriterionEndDecreasethetemperatureTEndT=Th求得初始解BS=初始解n=0求得新

7、的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1n

8、itiesthenbacktocity1MinimizethetotaltravelingcostTSP算例Citytocity12345611247910211201383617134695156SAparametersettingTh=2000t=10r=0.6N=2生成新的解：随机选择两个位置，交换其表示的城市T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1n