1.模拟退火算法的数学模型
由解空间、目标函数和初始解三部分组成。
1）解空间
模拟退火算法的解空间为关于一个问题所有可能的解（可能包括不可行的解）的集合，它限定了初始解选取的范围和新解产生的范围。对于无约束条件的优化问题，以求解最大解问题为例，其求得的任一可能解都为可行解，因为此时的解空间就是所有可能产生的解的集合：但对于大多数实际生活中的组合优化问题，如独立集问题、图着色问题等，这些问题中的解不仅需要满足目标函数值最优这要求，而且还需要满足另外一些特别的约束，因此在解集中就可能包含一些不可行的解。解決这一问题的一种方法是，在产生新解时就考虑到问题对解的特殊约束，即将解空间直接限定为所有可行解的集合：另一种方法是，允许在解空间中包含不满足约束的不可行解，在目标函数中增加罚函数对产生的不可行解进行惩罚。
2）目标函数
目标函数是对问题的优化目标的数学描述，通常表述为若干优化目标的一个和式。目标函数的选取必须正确体现对问题的整体优化要求。例如，如上所述，当解空间包含不可行解时，目标函数总应包含对不可行解的罚函数项，借此将一个有约束的优化问题转化为无约束的优化问题。此外，目标函数式应当是易于计算的，这将有利于在优化过程中简化目标函数差的计算以提高算法的效率。
3）初始解
初始解是算法开始迭代的起点。初始解的选取应使得算法导出较好的最终解。但大量的试验结果表明，模拟退火算法是一种“健壮的”算法，即算法的最终解并不十分依赖初始解的选取。
2.模拟退火算法的运作流程
1）初始化：给定温度T的变化范围并对其进行初始化，对解S进行初始化，并计算初始化解S所对应的当前目标函数值E（S），这是模拟退火算法迭代的起点
初始温度T的选择要注意以下问题：
（1）初始T要足够大，特別是当求解问题的规模比较大的时候，如果T的初始值过小，则容易导致算法陷入局部最优无法跳出而达不到最优解。
（2）T的初始值也不宜选取过大，如果选取过大，会导致算法的迭代次数过多，直接影响算法的执行效率。
对每一温度T下迭代的次数L进行初始化，通常L的选取原则如下：
（1）如果待解決问题的规模不大，L可以稍微选取得小一些，以减少算法的迭代次数，提高算法效率。
（2）如果待解决问题规模较大，L可以选取得大一些，以保证在每个温度T下都可以进行充分的迭代。
2）设一个整数k用来记录每一温度T下迭代已进行的次数，k的取值范同是[0，L]，在每一温度T下，循环k次第3）～6）步。
3）产生一个新解S'，根据目标函数分别计算当前解S和新解S'所对应的E（S）和E（S'），并计算增量ΔE=E（S'）-E（S）。
4）如果ΔE＜0，则新解S'代替当前解S作为新的当前解，新解所对应的E（S'）作为新的当前目标函数值；如果ΔE＞0，则需要计算新解的接受率
，若算得的r＞rand，则可以接受S'作为新的当前解，这里所说的rand为一个自动生成的介于[0，1）之间的随机数。
5）如果迭代满足终止条件，则输出当前解作为最优解，结束程序，终止算法。终止条件通常取为已设定的迭代次数或连续若干个新解都没有被接受或温度达到终止条件，合理的算法终止准则既能保证算法收敛于某一近似解，又能使最终解具有一定的全局性。
6）逐渐降低温度控制参数T。如T依然大于0，转至第2）步继续进行，直至满足终止条件为止。
模拟退火算法的全局搜索性能与退火速度（温度控制参数的降低策略）是密切相关的。一般来说，同一温度下的“充分”搜索（退火）是相当必要的，但这需要以计算时间作为代价。在实际应用中，要针对具体问题的性质和特征设置合理的温度控制参数的降低策略。常见的温度控制参数降温策略有以下四种（设Tk为进行第k次迭代时的温度）。
（1）对数降温策略，Tk=a/lg（k+k0）。
（2）快速降温策略，Tk=b/（1+k）。(www.xing528.com)
（3）直线降温策略，Tk=（1-K/k）x T0。
（4）指数降温策略，Tk=ax Tk-1。
以上四种降温策略中温度降低的速率是不同的，如果温度下降速率太快，则可能错过极点值；但温度下降速率过慢，则又会大大降低算法的收敛速率。因对数降温策略温度下降较为缓慢，故其降温效率也较低。快速降温策略在高温区的时候，温度降低较快；在低温区的时候，温度降低较慢。直线降温策略在高温和低温状态下，降温速度是相同的。指数降温策略是现阶段最常使用的温度降低策略，该策略中的温度降低较有规律，温度变化直接与公式中的参数a有关，它的取值直接决定着降温的过程，a是一个趋近于1的常数，一般取值在[0.5，0.99]。
模拟退火算法中新解的产生和接受机制由以下四个步骤构成。
1）按某种随机机制（如产生函数或扰动机制）由当前解产生一个新解，通常为了简化后续计算和方使接受，减少计算时间，一般通过对当前解进行一些扰动来产生新解，扰动的做法是以目前解为中心，对部分或整个解空间随机取样一个解。可能产生的新解构成当前解的邻域。可见，对产生函数或扰动机制的选择直接影响着当前解的邻域范围，进而对冷却进度表也有一定程度的影响。
扰动产生新解的过程如图4-1所示。
图4-1 扰动产生新解的过程
2）计算新解所对应的目标函数值与当前解所对应的目标函数值之间的差值，因为这一差值是由于当前解进行简单扰动变换产生的，所以一般使用变换过程中改变的部分直接计算得到。实践证明，在绝大多数应用中，这样可以快速准确地计算出目标函数的差值。
3）根据接受准则（最常使用的是Metropolis接受准则）判断是否接受新产生的解。当新解较当前解更优时，或新解虽然恶化但满足接受准则时，则可以接受新产生的解。对于有限定的解空间，则需先判断新产生解的可行性。
4）当新产生的解满足接受准则时，用新产生的解替换当前解，一般是参照新解对当前解进行相应的简单变换，同时对当前目标函数值进行修正。此时，当前解和目标函数值就实现了一次迭代。当新产生的解不满足接受准则时，则以当前解为基础继续进行下一轮的变换比对试验。
模拟退火算法的基本思想是，从一个初始解出发，不断重复迭代产生新解，对新解进行判定、舍弃，最终取得令人满意的全局最优解。
模拟退火算法流程图如图4-2所示。
图4-2 模拟退火算法流程图
下面，用k=SC表示算法终止条件，Generate（S'from S）用来表示从当前解S产生出新解S'的过程，Random（ ）表示在区间（0，1）上随机产生一个数，SA（ ）表示模拟退火算法函数，根据上面描述的模拟退火算法的运行流程，可以得到以下的模拟退火算法伪程序：
4.4.1.2 基本退火算法的特点
模拟退火算法在搜索最优解时，不但往好的方向搜索，也往差的方向搜索，从而使得该算法可以跳出局部最优解的陷阱，搜索到全局的最优解。在模拟退火算法执行期间，随着温度控制参数的减小，该算法返回全局最优解的概率逐渐增大，返回非全局最优解的概率单调减小。模拟退火算法与初始值无关，即算法求得的解与初始解（或状态或算法迭代的起点）的选取无关。模拟退火算法具有渐近收敛性，并已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法。而且，模拟退火算法的计算过程简单、通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。
但模拟退火算法也存在一些不足：返回一个高质量的近似解的时间花费较多，当问题规模不可避免地增大时，难以承受的运行时间将使算法丧失可行性。如果降温过程足够缓慢，这样得到的解的性能会比较好，但与此相对的是计算速度太慢；如果降温过程过快，很可能得不到全局最优解。
因为这些不足，对于实际应用中即刻调度的问题是一个不小的影响，所以必须探求改进算法性能、提高算法执行效率的可行途径，具体途径如下：
1）改变算法进行过程中的各种变异方法，如在算法中加入记忆器，记住算法进行过程中曾出现过的最优近似解。
2）对算法进行大规模并行计算，真正缩短计算时间。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
