模拟退火的基本概念
在物理退火中,将金属加热到高温后缓慢冷却,使得原子逐渐排列到能量最低的状态,形成稳定的晶体结构。模拟退火算法将这一过程应用于优化中,通过引入“温度”变量控制解的更新,使算法在初期能接受一些较差的解,以跳出局部最优,最终随“温度”降低收敛到全局最优解。
模拟退火算法的工作原理
模拟退火算法通过以下步骤逐步逼近最优解:
- 初始解和温度设定:从某个初始解开始,设定一个较高的温度 T。
- 随机扰动:在当前解的邻域内随机选择一个新的解。
- 接受准则:计算新解的损失函数值,如果新解比当前解更优,则接受新解。若不更优,则以概率exp(−ΔE/T) 接受新解,概率随温度 T下降逐渐降低。
- 降温过程:逐步降低温度 T,重复步骤2和3,使得解逐渐收敛到最优。
在优化梯度中的应用
在标准的梯度下降方法难以直接用于损失最小化问题时,模拟退火适用于此类非梯度优化问题。因为交换任意两个item的排序对NDCG和Hellinger距离的影响可以在常数时间 O(1) 内计算,这一特性使得模拟退火在逐步优化item排序时十分有效。
总结
模拟退火的优势在于其随机性,能有效避免局部最优。通过随机交换房源位置,并在退火过程中逐步减少这种交换的概率,最终获得最优的房源排序。
Thompson J.M Dowsland K.A. 2012. Simulated Annealing. In: Rozenberg G., Bck T., Kok J.N. (eds) Handbook of Natural Computing. Springer, Berlin, Heidelberg. Springer, Berlin, Heidelberg.