遗传算法概述

???E(i)?eKTlim(Pi(T))?lim?E(j)T??T?????eKT??j?s???1??S，其中s表示系统所有可能的状态数。 ???由上式可以看出，当温度很高时，系统处于各个状态的概率基本相等，接近于平均值，与所处状态的能量几乎无关。 当温度很低时则有：

???E(i)?eKTlim(Pi(T))?lim?E(j)T?0T?0???eKT??j?S???? ???EmKT设Sm表示系统最小能量状态的集合，Em是系统的最小能量。上式分子、分母乘以e有：

???E(i)?Em?eKTlim(Pi(T))?lim?E(j)?EmT?0T?0?KT?e??j?S?m???E(i)?Em?eKT =lim?E(j)?EmT?0??eKT?j???Sm???????lim?T?0???????ej?SmE(i)?Em?KT?e?E(j)?EmKT?j?Sm?e?E(j)?EmKT???? ??????1，如果i?Sm?? ?S??m??0,如果i?Sm???由上式可以看出，当温度趋近于0时，系统以等概率趋近于几个能量最小的状态之一，而系统处于其他状态的概率为0。 由于：

?Pi(T)?eE(i)e1?KT?ZTE(i)Pi(T)?ZT ?()??e?Pi(T)?2?T?TZT?TZT?TKT2ZTZTKT2=

?E(i)KT?E(i)KTE(i)E(i)Pi(T)1Pi(T)?ZTKT2KT2?E(j)ej?SE(j)?KT?Pi(T)e(E(i)?E(j)) ?2ZTKTj?S?E(j)KT=

Pi(T)Pi(T)(E(i)?E(j)Pj(T))?(E(i)?ET) ?22KTKTj?S其中：ET??E(j)Pj(T)是温度T下，各状态能量的期望值。由于Pi(T)、K、T均大于0，

j?S?Pi(T)??0.如果E(i)?ET所以有： ??T??0,如果E(i)?ET由此可以看出，系统落入能量较低的状态的概率是随温度T单调下降的，而系统落入高能量状态的概率是随温度T单调上升的。也就是说，系统落入低能量状态的概率随着温度的

下降单调上升，而系统落入高能量状态的概率随着温度的下降单调下降。

总结可得出如下结论：在高温下，系统基本处于无序状态，基本以等概率落入各个状态。在给定的温度下，系统落入低能量状态的概率大于落入高能量状态的概率。这样在同一温度下，如果系统交换得足够充分，则系统会趋向于落入较低能量的状态。随着温度的缓慢下降，系统落入低能量状态的概率逐步增加，而落入高能量状态的概率逐步减小，使得系统各状态能量的期望值随温度的下降单调下降，而只有那些能量小于期望值的状态，其概率才随温度下降增加，其他状态均随温度下降而下降。因此，随着能量期望值的逐步下降，能量低于期望值的状态逐步减少，当温度趋于0时，只剩下那些具有最小能量的状态，系统处于其他状态的概率趋近于0。因此最终系统将以概率1处于具有最小能量的一个状态。

固体退火过程，最终达到最小能量的一个状态，从理论上来说，必须满足以下3个条件：

① 初始温度必须足够高； ② 在每个温度下，状态的交换必须足够充分； ③ 温度T的下降必须足够缓慢。

受固体退火过程的启发，Kirkpatrick等人意识到组合优化问题与固体退火过程的类似性，将组合优化问题类比为固体的退火过程，提出了求解组合优化问题的模拟退货算法。

设一个定义在有限集S上的组合优化问题，i∈S是该问题的一个解，f(i)是解i的指标函数。由组合优化问题与退火过程的类比关系，i对应物理系统的一个状态，f(i)对应该状态的能量E(i)，一个用于控制算法的进程、其值随算法进程递减的控制参数t对应固体退火中的温度T，粒子的热运动则用解在领域中的交换来代替。这样就将一个组合优化问题与固体退火过程建立了联系。

在求解组合优化问题时，首先给定一个比较大的t值，这相当于给定一个比较高的温度T。随机给定一个问题的解i，作为问题的初始解。在给定的t下，随机产生一个问题的解j，j∈N(i)，其中N(i)是i的领域。从解i到新解j的转移概率按照Metropolis准则确定即：

f(i)??1,ff(j()?jf)(i?)Pt(i?j)???

t?,其他?e如果新解j被接受，则以解j代替解i，否则继续保持解i。重复该过程，直到在该控制参数

t下达到平衡。与退火过程中的温度T缓慢下降相对应，在进行足够多的状态转移之后，控制参数t要缓慢下降，并在每个参数t下重复以上过程，直到控制参数t降低到足够小为止。最终得到的是该组合优化问题的一个最优解。由于这样一个过程模拟的是退火过程，所以被称为模拟退火算法。

模拟退火算法可描述为： ① 随机选择一个解i，k=0，t0=Tmax(初始温度)，计算指标函数f(i)。 ② 如果满足结束条件，则转。 ③ Begin ④ 如果在该温度内达到了平衡条件，则转。 ⑤ Begin ⑥ 从i的领域N(i)中随机选择一个解j。 ⑦ 计算指标函数f(i)。 ⑧ 如果f(j)

(0,1),则i?j,f(i)?f(j)。⑩ 如果Pt(i??j)?Random

? 转④ ? End

? tk?1?Dorp(tk),k?k?1

? End ? 输出结果。 ? 结束。

该算法有内外两层循环。内循环模拟的是在给定温度下系统达到热平衡的过程。每次循环随机地产生一个新解，然后按照Metropolis准则，随机地接受该解。算法中Random(0，1)，是一个在【0，1】间均匀分布的随机数发生器，与从解i到劣解j的转移概率相结合，模拟系统是否接受了劣解j。外循环模拟的是温度下降的过程，控制参数tk起到与温度T相类似的作用，表示的是第k次循环时系统所处的温度。算法中的Dorp(tk)是一个温度下降函数，它按照一定的原则实施温度的缓慢下降。 模拟退火算法与局部搜索算法很相似，二者最大的不同是模拟退火算法按照Metropolis准则随机地接受一些劣解，即指标函数值大的解。当温度比较高时，接受劣解的概率比较大，在初始高温下，几乎以接近100%的概率接受劣解。随着温度的下降，接受劣解的概率逐渐减小，直到当温度趋于0时，接受劣解的概率也同时趋于0。这样，将有利于算法从局部最优解中跳出，求的问题的全局最优解。 模拟退火算法在现实应用中非常的有效，大多数情况下都能找到最优解结束，即便不是最优解，也是一个可以接受的满意解。即使是最差的结果，与最优解的差距也不是很大。该算法的研究有待进一步加深。