模拟退火与算法课件 .ppt

Simulated Annealing（模拟退火算法） 模拟退火算法的思想最早是由Metropo比等(1953)提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于Mente Calro迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解．即在局部优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，目前己在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、图像处理等领域。 退火工艺: 退火是将金属和合金加热到适当温度，保持一定时间，然后缓慢冷却的热处理工艺。退火后组织亚共析钢是铁素体加片状珠光体；共析钢或过共析钢则是粒状珠光体。总之退火组织是接近平衡状态的组织。 退火的目的: ①降低钢的硬度，提高塑性，以利于切削加工及冷变形加工。②细化晶粒，消除因铸、锻、焊引起的组织缺陷，均匀钢的组织和成分，改善钢的性能或为以后的热处理作组织准备。③消除钢中的内应力，以防止变形和开裂 SA接受相邻解的标准 令 X 为当前解 X’ 新的解（相邻解） C(x) (C(x’))be the energy state (cost) of x (x’) 概率 Paccept = exp [(C(x)-C(x’))/ T] N=Random(0,1) 无条件接受相邻解，如果： C(x’) C(x), 即相邻解比当前解好 以一定的概率接受相邻解，如果 C(x’) = C(x),即相邻解比当前解差 当 N Paccept时，接受相邻解 参数设置 T 初始温度 t 冷却温度 冷却过程的设定（The cooling schedule） L 每一特定温度下的搜索次数： 退火过程设定 退火过程设定 Algorithm Initialize initial solution x , highest temperature Th, and coolest temperature t T= Th When the temperature is higher than t While not in equilibrium Search for the new solution X’ Accept or reject X’ according to Metropolis Criterion End Decrease the temperature T End Example Traveling Salesman Problem (TSP) Given 6 cities and the traveling cost between any two cities A salesman need to start from city 1 and travel all other cities then back to city 1 Minimize the total traveling cost TSP算例 SA parameter setting Th=2000 t=10 r=0.6 N=2 生成新的解：随机选择两个位置，交换其表示的城市 求得初始解 BS=初始解 Example Solution representation An integer list, i.e., (1,4,2,3,6,5) Search mechanism Swap any two integers (except for the first one) (1,4,2,3,6,5) ? (1,4,3,2,6,5) Cost function Example Step n: visiting sequence (1,4,2,3,6,5) -cost = 189 Generate neighbor: obtain sequence (1,2,4,3,6,5) -cost = 180 Replace current sequence by (1,2,4,3,6,5) Step n+1: visiting sequence (1,2,4,3,6,5) -cost = 180 Generate neighbor: obtain sequence (1,2,4,3,5,6) -cost = 190 Temperature =99 Probability: exp((180-181)/99)=0.904 Random()=0.6 - accept neighbor Replace current sequence by (1,