智能优化计算模拟退火.pptVIP

3.4模拟退火算法的改进智能优化计算改进的思路（1）记录“Bestsofar”状态，并即时更新；（2）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续m1步保持不变则认为Metropolis抽样稳定，若连续m2次退温过程中所得最优解不变则认为算法收敛。3.4.3一种改进的模拟退火算法山东大学威海分校信息工程学院2009年第30页，共49页，星期日，2025年，2月5日3.4模拟退火算法的改进智能优化计算改进的退火过程（1）给定初温t0，随机产生初始状态s，令初始最优解s*=s，当前状态为s(0)=s，i=p=0；（2）令t=ti，以t，s*和s(i)调用改进的抽样过程，返回其所得最优解s*’和当前状态s’(k)，令当前状态s(i)=s’(k)；（3）判断C(s*)C(s*’)?若是，则令p=p+1；否则，令s*=s*’，p=0；（4）退温ti+1=update(ti)，令i=i+1；（5）判断pm2?若是，则转第(6)步；否则，返回第(2)步；（6）以最优解s*作为最终解输出，停止算法。3.4.3一种改进的模拟退火算法山东大学威海分校信息工程学院2009年第31页，共49页，星期日，2025年，2月5日3.4模拟退火算法的改进智能优化计算改进的抽样过程（1）令k=0时的初始当前状态为s’(0)=s(i)，q=0；（2）由状态s通过状态产生函数产生新状态s’，计算增量?C’=C(s’)-C(s)；（3）若?C’0，则接受s’作为当前解，并判断C(s’)C(s*’)?若是，则令s*’=s’，q=0；否则，令q=q+1。若?C’0，则以概率exp(-?C’/t)接受s’作为下一当前状态；（4）令k=k+1，判断qm1?若是，则转第(5)步；否则，返回第(2)步；（5）将当前最优解s*’和当前状态s’(k)返回改进退火过程。3.4.3一种改进的模拟退火算法山东大学威海分校信息工程学院2009年第32页，共49页，星期日，2025年，2月5日3.5模拟退火算法的实现与应用智能优化计算3.5.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山东大学威海分校信息工程学院2009年第33页，共49页，星期日，2025年，2月5日3.5模拟退火算法的实现与应用智能优化计算算法流程3.5.130城市TSP问题（d*=423.741byDBFogel）山东大学威海分校信息工程学院2009年第34页，共49页，星期日，2025年，2月5日3.5模拟退火算法的实现与应用智能优化计算初始温度的计算fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0))/log(0.9);3.5.130城市TSP问题（d*=423.741byDBFogel）山东大学威海分校信息工程学院2009年第35页，共49页，星期日，2025年，2月5日第1页，共49页，星期日，2025年，2月5日3.1模拟退火算法及模型3.1.1物理退火过程3.1.2组合优化与物理退火的相似性3.1.3模拟退火算法的基本思想和步骤3.2模拟退火算法的马氏链描述3.2.1马尔可夫链3.2.2模拟退火算法与马尔可夫链3.3模拟退火算法的关键参数和操作的设计3.3.1状态产生函数3.3.2