03模拟退火SA

《03模拟退火SA》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、导言早在1953年，Metropolis等人就提出了原始的SA算法，但是并没有引起反响，直到1983年，Kirkpatrick等人提出现在的SA算法，并成功的利用它解决大规模的组合最优化问题。由于现代SA算法能够有效地解决具有NP复杂性的问题，避免陷入局优，克服初值依赖性等优点，目前已在工程中得到了广泛的应用，诸如VLS、生产调度、控制工程、机器学习、神经网络、图像处理等领域。模拟退火算法的基本思想是源于热力学中的退火过程，因此首先介绍一下热力学当中的退火过程。热力学中的退火过程一般由一下三部分组成：1

2、.加热过程2.等温过程3.冷却过程退火与模拟退火金属物体的退火过程实际上就是随温度的缓慢降低，金属由高能无序的状态转变为低能有序的固体晶态的过程。在退火中，需要保证系统在每一个恒定温度下都要达到充分的热平衡，这个过程可以用MonteCarlo的方法加以模拟，该方法虽然比较简单，但是需要大量采样才能获得比较精确的结果，计算量比较大。1953年，Metropolis等提出了一种重要性采样法，即以概率来接受新状态。它能够大大减少采样的计算量。表5.1组合优化问题的求解与物理退火优化问题物理退火解状态目标函数能

3、量函数最优解最低能量的状态设定初始高温加温过程基于Metropolis准则的搜索等温过程温度参数t的下降冷却过程由此可以看出，在高温下，S可以处于任何能量状态，此时SA可以看成是在进行广域搜索，以避免陷入局优；在低温下，S只能处于能量较小的状态，此时SA可以看成是在做局域搜索，以便于将解精确化；当温度无限趋近于零时，S只能处于最小能量状态，此时SA就获得了全局最优解。模拟退火算法的构造及流程基本思想SA算法是一种启发式的随机巡游算法，它模拟了物理退火过程，由一个给定的初始高温开始，利用具有概率突跳特性的

4、Metropolis抽样策略来解空间中随机进行搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解。算法的要素构成在SA算法执行过程中，算法的效果取决于一组控制参数的选择，关键技术的设计对算法性能影响很大。本节从算法使用的角度讨论算法实现中的一些要素。包括状态表达、领域定义与移动、热平衡达到、降温控制等的概念。1.状态表达：同GA和TS中编码含义相同，状态表达是利用一个数学形式来描述系统所处的一种能量状态。在SA中，一个状态就是问题的一个解，而问题的目标函数就对应于状态的能量函数。状态表达是S

5、A的基础工作，直接决定着领域的构造和大小，一个合理的状态表达方法会大大减小计算复杂性，改善算法的性能。2.领域定义与移动：同TS一样，SA也是基于领域搜索的。领域定义的出发点应该是保证其中的解能够尽量遍布整个解空间，其定义方式通常是由问题的性质所决定的。SA算法采用了一种特殊的Metropolis准则的领域移动方法，也就是说，依据一定的概率来决定当前解是否移向新解。在SA中，领域移动的方式分为两种：无条件移动和有条件移动。若新解的目标函数值小于当前解得目标函数值（新状态的能量小于当前状态的能量），则进行

6、无条件移动；否则，依据一定的概率进行有条件移动。3.热平衡达到：热平衡的到达相当于物理退火中的等温过程，是指在一个给定的温度下，SA基于Metropolis准则进行随机搜索，最终达到一种平衡状态的过程。这是SA算法中的内循环过程，为了保证能够达到平衡状态，内循环次数要足够大才行。但是在实际应用中达到理论的平衡状态是不可能的，只能接近这一结果。最常见的方法就是将内循环次数设成一个常数，在每一温度，内循环迭代相同的次数。次数的选取同问题的实际规模有关，往往根据一些经验公式获得。4.降温函数：降温函数用来控制

7、温度的下降凡是，这是SA算法中的外循环过程。利用温度的下降来控制算法的迭代是SA的特点，从理论上说，SA仅要求温度最终趋于0，而对温度的下降速度并没有什么限制，但这并不意味着可以随意下降温度。由于温度的大小决定着SA进行广域搜索还是局域搜索，当温度很高时，当前领域中几乎所有的解都会被接受，SA进行广域搜索；当温度变低时，当前领域中越来越多的解将被拒绝，SA进行领域搜索。若温度下降的过快，SA将很快从广域搜索转变为局域搜索，这就很可能造成过早的陷入局部最优状态，为了跳出局优，只能通过增加内循环次数来实现，

8、这就会大大增加算法进程的CPU时间。当然，如果温度下降的过慢，虽然可以减少内循环次数，但是由于外循环次数的增加，也会影响算法进程的CPU时间。选择合理的降温函数能够帮助提高SA算法的性能。算法的计算步骤和流程图一个优化问题可以描述为其中，S是一个离散有限状态空间，i代表状态。针对这样一个优化问题，SA算法的计算步骤能够描述如下：第1步：初始化，任选初始解，给定初始温度和终止温度，令迭代指标k=0，。第2步：随机产生一个领域解（表示i的领域）