智能优化算法前言前言(C.)前言(C.)前言(C.)前言(C.)前言(C.)前言(C.)前言(C.)前言(C.e)模拟退火算法与模型模拟退火算法与模型(C.)模拟退火算法与模型(C.)模拟退火算法与模型(C.)数学描述：显然：其中，|S|表示状态空间集合中状态的数量。这就表明，所有状态在高温下具有相同的概率。数学描述：而当温度下降时：上式表明当温度降至很低时，材料会以很大概率进入最小能量状态。数学描述：从另外一个角度来看：在同一个温度T，选定两个能量E1<E2，有：在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。数学描述：针对上述现象，Metropolis提出了著名的Metropolis准则（1953）——以概率接受新状态——来模拟这一过程：固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。Metropolis准则(1953)—以概率接受新状态：若在温度T，当前状态i→新状态j若Ej<Ei，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/KT]大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立，则保留状态i为当前状态。p=exp[-(Ej-Ei)/KT]：在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。组合优化问题与物理退火过程的相似性：模拟退火法的基本步骤：给定初温t=t0，随机产生初始状态s=s0，令k=0；RepeatRepeat产生新状态sj=Genete(s)；ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；Until算法终止准则满足；输出算法搜索结果。算法关键参数和操作的设定：从算法流程上看，模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定模拟退火算法的优化性能。此外，初温的选择对模拟退火算法性能也有很大影响。状态产生函数：原则：设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布方法：在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生状态接受函数：原则：函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。设计状态接受概率，应该遵循以下原则：(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；(3)当温度趋于零时，只能接受目标函数下降的解。方法：状态接受函数的引入是模拟退火算法实现全局搜索的最关键的因素，模拟退火算法中通常采用min[1,exp(-△C/t)]作为状态接受函数初始温度：初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程。原则：通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；实际应用时往往要让初温充分大。实验表明：初温越大，获得高质量解的机率越大，但花费较多的计算时间。方法：1)均匀抽样一组状态，以各状态目标值的方差为初温；2)随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温，譬如，其中为初始接受概率；3)利用经验公式。温度更新函数：温度更新函数，即温度的下降方式，用于在外循环中修改温度值。常用的算法温度下降函数：1)：α越接近1温度下降越慢，且其大小可以不断变化；2）：其中t0为起始温度，K为算法温度下降的总次数。内循环终止准则：常用的Metropolis抽样稳定准则：（1）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；（3）按一定的步数抽样。外循环终止准则（1）设置终止温度的阈值；（2）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；（4）概率分析方法。模拟退火算法的优缺点：优点：质量高；初值鲁棒性强；简单、通用、易实现。缺点由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。改进的可行方案：设计合适的状态产生函数；设计高效的退火历程；避免状态的迂回搜索；采用并行搜索结构；避免陷入局部极小，改进对温度的控制方式；选择