高等运筹学(第5章)

第5章模拟退火算法

模拟退火算法（SimulatedAnnealing,简称SA）是Kirkpatrick等人于1982年提出的一种适合求解大规模组合优化问题，特别是NP-难问题的通用启发式算法．算法思想源于对固体物质退火过程的模拟；采用Metropolis接受准则；并用一组称之为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解．SA的物理背景：固体物质退火过程．使算法跳离局部最优的关键：Metropolis接受准则．算法应用的前提：冷却进度表的合理选择．1主要内容5.1固体退火过程和Metropolis准则5.2模拟退火算法的基本思想和步骤5.3模拟退火算法关键参数和操作的设计5.4模拟退火算法实现与应用5.5模拟退火算法的改进25.1固体退火过程和Metropolis准则

固体物质退火是先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程.固体物质的退火过程由三部分组成：加温过程等温过程冷却过程对于固体在恒定温度下达到热平衡的过程模拟，Metropolis等人在1953年提出了“重要性采样法”，即以概率接受新状态．若Ej<Ei则接受新状态j为当前状态（“重要”状态）；若Ej>Ei，要依据概率来确定．35.2模拟退火算法的基本思想和步骤

1.固体退火与组合优化之间的相似性固体退火概念与优化问题的对应关系

42.算法思想和步骤

Metropolis算法：从某一初始状态出发，通过计算系统的时间演化过程，求出系统最终达到的状态．SA：从某个初始解出发，经过大量解的变换后，求得给定控制参数值t时优化问题的相对最优解．然后，减少t的值，重复执行Metropolis算法，就可以在t趋于零时，求得优化问题的全局最优解．

SA由与Metropolis准则对应的转移概率Pt确定是否接受从当前解xi到新解xj的转移，即

5ProcedureSimulated_Annealing;Begin

任选一个初始解x0；确定初始温度t0和每一个t值下进行迭代的次数L；

xi:=x0;（置初始解为当前解）

k

:=0;（温度变化计数器置0）Repeat

l

:=0;（迭代次数计数器）Repeat

从邻域N(xi)中随机选一xj；计算Δf=f(xj)-f(xi)；if(Δf≤0)thenxi:=xj;elseifexp(-Δf/tk)>random[0,1]thenxi:=xj;

l

:=l+1;untill=L;

k

:=k+1;tk

:=t(k);until满足终止条件；End;63.模拟退火算法的特点分析

SA依据Metropolis准则接受新解，因此除接受优化解外，还在一定范围内接受恶化解，这正是SA与局部搜索算法的本质区别所在．SA具有如下特点：

(1)优于局部搜索算法．

(2)若在每个t值都达到平衡分布，且所构造的邻域结构能使解空间中的任何两个状态可达，则SA渐近收敛于全局最优解．(3)随着控制参数t值的减小，算法返回某个全局最优解的概率单调增大.7与局部搜索算法相比，SA的性能可概括为高效、健壮、通用和灵活．

(1)高效性．SA可在较短时间里求得更好的最终解．(2)健壮性（鲁棒性，robust）．即算法的最终解并不十分依赖初始解的选取．(3)通用性和灵活性．SA能应用于求解多种组合优化问题，为一个问题编制的程序可以有效地用于其它问题．85.3SA关键参数及其操作设计

SA主要包括“三函数两准则”：解产生函数（邻域结构）、解接受函数、温度更新函数、内循环终止准则和外循环终止准则．

1.解产生函数（邻域结构）

通常选择当前解经简单变换即可产生新解的方法．尽可能保证产生的候选解遍布整个解空间．应能使解空间中的任何两个状态可达．2.解接受函数

判断新解是否被接受的依据是Metropolis准则：93.初始温度

从理论上说，初始温度t0应使平稳分布中每一状态被接受的概率相等，也就是使若取P＝0.9，则在Δf

=100时，t0＞949．在实际应用中可用以下方法进行简单地估计：

(1)Δf=(目标函数值的上界)－(目标函数值的下界)．(2)随机产生若干个解，求所有解对间的目标函数差，然后取其中的最大者作为Δf．

104.温度更新函数

表示温度下降的方式并控制温度下降的速度．常用的温度更新函数是tk+1=αtk，0<α<1，通常α=0.75~0.99．

5.内循环终止准则

用于决定在各温度下产生候选解的数目，即每一个tk值下进行迭代的次数L．

L往往只能取一个近似的足够大的数，如L=100n～300n，其中n为问题的规模．还可用如下的抽样稳定准则来判断L是否足够大：(1)目标函数的均值是否稳定．(2)连续若干步的目标值变化较小．

116.外循环终止准则

用于决定SA何时结束．常用的终止准则有：(1)设定终止温度．在实际应用中，可以给定一个足够小的正数ε，当温度tk≤ε时，算法终止．(2)给定一个确定的外循环总迭代次数．(3)给定当前的最好解保持不变的最大连续迭代次数．

7.冷却进度表

初始温度t0，温度更新函数tk+1=αtk，每一个tk值下进行迭代的次数L和外循环终止准则称为模拟退火过程的冷却进度表，是SA应用的关键参数．这些参数之间存在相互影响．125.4模拟退火算法实现与应用

讨论如何在SA所提供的通用算法框架下，针对具体问题予以实现．对问题的简明描述：解空间：指问题的所有可能解的集合，它限定了初始解选取和新解产生时的范围．目标函数：通常表述为若干优化目标的一个和式．目标函数值不一定就是问题的优化目标值，但其对应关系应是明显的．此外，目标函数式应当是易于计算的．初始解：可以考虑随机生成．131.旅行商问题

设有n个城市和距离矩阵D=(dij)，其中dij表示城市i到城市j的距离．问题是要找遍访每个城市恰好一次的一条回路，且其路径长度为最短．求解TSP的模拟退火算法描述如下：解空间：可表示为{1,2,…,n}的所有循环排列的集合，即S={(π1,π2,…,πn)|(π1,π2,…,πn)为{1,2,…,n}的循环排列}．πi=j表示在第i个次序访问城市j，并约定πn+1=π1．初始解：可选为（1,2,…,n）．

目标函数：访问所有城市的一个回路的长度14新解的产生：设用以下方法产生（分别或交替使用）①2-交换．任选访问的序号u和v（设u<v），逆转u和v及其之间的访问顺序．当前解：π1…πu-1

πu

πu+1

…πv-1

πv

πv+1…πn

新解：π1…πu-1

πvπv-1…πu+1πuπv+1…πn

②3-交换．任选序号u、v和w（设u<v<w），将u和v之间的子路径插到w之后访问．当前解：π1…πu-1

πu…πv

πv+1…

πw

πw+1…πn新解：π1…πu-1

πv+1…

πw

πu…πv

πw+1…πn目标函数差（2-交换）15当距离矩阵D=（dij）为对称矩阵时，因为dij=dji，上式可简化为

目标函数差（３-交换）162.0－1背包问题（Zero-oneKnapsackProblem）

给定一个装载量为M的背包及n件物品，物品i的重量和价值分别为wi和ci，i=1,2,…,n．要求选择若干件物品装入背包，使其价值之和为最大．设则问题的数学模型为

xi∈{0,1},i=1,2,…,n17求解0-1背包问题的模拟退火算法描述如下：解空间S={(x1,x2,…,xn)|w1x1+…+wnxn≤M,xi∈{0,1}}

目标函数f(x1,x2,…,xn)=c1x1+c2

x2+…+cnxn→max新解的产生

随机选取物品i，执行下列三种操作之一：

①若i不在背包中，则将其装入背包．

②若i不在背包中，则将其装入背包，同时从背包中随机取出另一物品j．

③若i已在背包中，则将其取出，并同时随机装入另一物品j．

归纳：xi:=1－xi，且（或）xj:=1－xj，i≠j

18背包价值差（目标函数差）及重量差根据产生新解的三种可能，相应的背包价值差为

为判定解的可行性，求出对应的背包重量差为

其中Δm为当前背包重量m的增量．

19接受准则：是增加了可行性测定的Metropolis准则