退火算法（一种物理算法）

退火算法

一种物理算法

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。作为模拟退火算法应用，讨论旅行商问题（Travelling Salesman Problem,简记为TSP）：设有n个城市，用数码1，......，n代表。温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。

参数控制

模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制。其主要问题有以下三点：

（1）温度T的初始值设置问题。

温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。

（2）退火速度问题。

模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索（退火）是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。

（3）温度管理问题。

温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：

T（t+1）=k×T（t）

式中k为正的略小于1.00的常数，t为降温的次数

优缺点及改良方式

优点：计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。

缺点：收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等缺点。

经典模拟退火算法的缺点：

（1）如果降温过程足够缓慢，多得到的解的性能会比较好，但与此相对的是收敛速度太慢。

（2）如果降温过程过快，很可能得不到全局最优解。

模拟退火算法的改进：

（1）设计合适的状态产生函数，使其根据搜索进程的需要

表现出状态的全空间分散性或局部区域性。

（2）设计高效的退火策略。

（3）避免状态的迂回搜索。

（4）采用并行搜索结构。

（5）为避免陷入局部极小，改进对温度的控制方式

（6）选择合适的初始状态。

（7）设计合适的算法终止准则。

也可通过增加某些环节而实现对模拟退火算法的改进。

主要的改进方式包括：

（1）增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。

（2）增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将一些在这之前好的态记忆下来。

（3）增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。

（4）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。

（5）结合其他搜索机制的算法，如遗传算法、混沌搜索等。

（6）上述各方法的综合应用。

参考资料

1.最优化算法-模拟退火(SA)·IT610