文档介绍：第9讲模拟退火算法等-精品
邻域的概念
邻域，简单的说就是一个点附近的其他点的集合。
在距离空间，邻域就是以某一点为中心的圆。
组合优化问题的定义：
设D是问题的定义域，若存在一个映射N，使得：
则称N(S),
f(xn) = 38,
f(xn) > f(xb),
P = P – {xn} = {(a, b, e, c, d)}
第十一次循环
从P中选择一个元素，
假设xn = (a, b, e, c, d),
f(xn) = 41,
f(xn) > f(xb),
P = P – {xn} = {}
P等于空，算法结束，
得到结果为xb = (a, b, e, d, c), f(xb) = 34。
存在的问题
局部最优问题
解决方法
每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点，指标函数优的点，被选中的概率比较大，而指标函数差的点，被选中的概率比较小。
选择概率的计算
设求最大值：
选择概率的计算
当求最小值时：
局部搜索算法1（Local Search 1）
1，随机的选择一个初始的可能解x0∈D，xb=x0，P=N(xb)
2，如果不满足结束条件，则
3，Begin
4，对于所有的x∈P计算指标函数f(x)，并按照式（3）或者式（4）计算每一个点x的概率
5，依计算的概率值，从P中随机选择一个点 xn，xb ＝ xn，P = N(xb)，转2
6，End
7，输出计算结果
8，结束
存在的问题
步长问题
初始值
搜索到的最优解
解决方法
变步长
初始值
搜索到的最优解
局部搜索算法2（Local Search 2）
1，随机的选择一个初始的可能解x0∈D，xb=x0，
确定一个初始步长计算P=N(xb)
2，如果不满足结束条件，则
3，Begin
4，选择P的一个子集P'，xn为P'中的最优解
5，如果f(xn) < f(xb)，则xb ＝ xn
6, 按照某种策略改变步长，计算P = N(xb)，转2
7，否则P = P – P'，转2。
8，End
9，输出计算结果
10，结束
存在问题
起始点问题
A
B
全局最大值
局部最大值
解决方法
随机的生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。
局部搜索算法3（Local Search 3）
1，k = 0
2，随机的选择一个初始的可能解x0∈D，xb=x0，
P=N(xb)
3，如果不满足结束条件，则
4，Begin
5，选择P的一个子集P'，xn为P'中的最优解
6，如果f(xn) < f(xb)，则xb ＝ xn，P = N(xb)，转3
7，否则P = P – P'，转3。
8，End
9，k = k+1
10，如果k达到了指定的次数，则从k个结果中选
择一个最好的结果输出，否则转（2）
11，输出结果
12，结束
多种方法的集成
以上几种解决方法可以结合在一起使用，比如第一、第二种方法的结合，就产生了我们将在后面介绍的模拟退火方法。
2. 模拟退火算法
是局部搜索算法的一种扩展
最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地将模拟退火算法用于求解组合优化问题。
基本思想是借用金属的退化过程改进局部搜索算法
固体退火过程
溶解过程：随着温度的不断上升，粒子逐渐脱离开其平衡位置，变得越来越自由，直到达到固体的溶解温度，粒子排列从原来的有序状态变为完全的无序状态。
退火过程：随着温度的下降，粒子的热运动逐渐减弱，粒子逐渐停留在不同的状态，其排列也从无序向有序方向发展，直至到温度很低时，粒子重新以一定的结构排列。
粒子不同的排列结构，对应着不同的能量水平。如果退火过程是缓慢进行的，也就是说，温度的下降如果非常缓慢的话，使得在每个温度下，粒子的排列都达到一种平衡态，则当温度趋于0（绝对温度）时，系统的能量将趋于最小值。
如果以粒子的排列或者相应的能量来表达固体所处的状态，在温度T下，固体所处的状态具有一定的随机性。一方面，物理系统倾向于能量较低的状态，另一方面，热运动又妨碍了系统准确落入低能状态。
Metropolis准则
从状态i转换为状态j的准则：
如果E(j)≤E(i)，则状态转换被接受；
如果E(j)＞E(i)，则状态转移被接受