高级搜索.

Presentation on theme: "高级搜索."— Presentation transcript:

1 高级搜索

2 主要内容 局部搜索方法 模拟退火算法 遗传算法

3 优化与组合优化问题 很多问题属于优化问题，或者可以转化为优化问题 如TSP问题，皇后问题

4 优化问题的描述 设x是决策变量，D是x的定义域，f(x)是指标函数，g(x)是约束条件集合。则优化问题可以表示为，求解满足g(x)的f(x)最小值问题。 如果在定义域D上，满足条件g(x)的解是有限的，则优化问题称为组合优化问题。

5 算法的时间复杂度 对于组合优化问题，由于其可能的解是有限的，当问题的规模比较小时，总可以通过枚举的方法获得问题的最优解，但当问题的规模比较大时，就难于求解了。 常用的算法复杂度函数

6 时间复杂性函数比较（10亿次/秒） 输入量n 10 20 30 40 100 n 10ns 20ns 30ns 40ns 100ns
nlogn 26.0ns 44.3ns 64.1ns 200ns n2 400ns 900ns 1.6us 10us 2n 1.0us 1.0ms 1.1s 18.3min 4.0世纪 n! 3.6ms 77.1年 8.4×1013世纪 2.6×1029世纪 3.0×10139世纪

7 一些难的组合优化问题 旅行商问题 背包问题 装箱问题 ... 寻求在可以接受的时间内得到满意解的方法

8 邻域的概念 邻域，简单的说就是一个点附近的其他点的集合。 在距离空间，邻域就是以某一点为中心的圆。 组合优化问题的定义：
设D是问题的定义域，若存在一个映射N，使得： 则称N(S)为S的邻域。

9 例：皇后问题 S={Si}表示一个可能解，其中Si表示在第i行，第Si列有一个皇后。 如四皇后问题的一个解：S=(2, 4, 1, 3) Q

10 定义映射N为棋盘上任意两个皇后的所在行或列进行交换，即S中任意两个元素交换位置。

11 例：旅行商问题 用一个城市的序列表示一个可能的解。 通过交换两个城市的位置获取S的邻居 例：简单交换方法
设S = (x1, x2, …xi-1, xi, xi+1, …, xj-1, xj, xj+1, …, xn) 则通过交换xi和xj两个城市的位置可以得到S的一个邻居： S' = (x1, x2, …xi-1, xj, xi+1, …, xj-1, xi, xj+1, …, xn)

12 xi-1 xi xi+1 xi-1 xi xi+1 x2 xj-1 x2 xj-1 x1 xj x1 xj xn xn xj+1 xj+1

13 例：逆序交换方法 设xi、xj是选取的两个城市，所谓的逆序交换方式是指，通过逆转xi、xj两个城市之间的城市次序来得到S的邻居。 设：S = (x1, x2, …xi-1, xi, xi+1, …, xj-1, xj, xj+1, …, xn) 则：S' = (x1, x2, …xi-1, xi, xj-1, x j-2…, xi+1, xj, xj+1, …, xn)

14 xi-1 xi xi+1 xi-1 xi xi+1 x2 xj-1 x2 xj-1 x1 xj x1 xj xn xn xj+1 xj+1

15 局部搜索算法 基本思想：在搜索过程中，始终向着离目标最接近的方向搜索。 目标可以是最大值，也可以是最小值。
在后面的介绍中，如果没有特殊说明，均假定是最小值。

16 局部搜索算法（Local Search） 1，随机的选择一个初始的可能解x0∈D，xb=x0，P=N(xb)； 2，如果不满足结束条件，则 3，Begin 4， 选择P的一个子集P'，xn为P'中的最优解 5， 如果f(xn) < f(xb)，则xb ＝ xn，P = N(xb)， 转2；f(x)为指标函数。 6， 否则P = P – P'，转2。 7，End 8，输出计算结果 9，结束

17 例：5城市旅行商问题 B ● 10 7 10 7 A 13 ● ● E 6 9 ● C 5 6 10 ● D

18 设初始的可能解：x0 = (a, b, c, d, e) f(xb) = f(x0) = 38 通过交换两个城市获得领域 P = {(a, c, b, d, e), (a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)} 设每次随机从P中选择一个邻居。

19 第一次循环 从P中选择一个元素， 假设xn = (a, c, b, d, e), f(xn) = 42, f(xn) > f(xb),
P = P – {xn} = {(a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)}

20 第二次循环 从P中选择一个元素， 假设xn = (a, d, c, b, e), f(xn) = 45, f(xn) > f(xb),
P = P – {xn} = {(a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)}

21 第三次循环 从P中选择一个元素， 假设xn = (a, e, c, d, b), f(xn) = 44, f(xn) > f(xb),
P = P – {xn} = {(a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)}

22 第四次循环 从P中选择一个元素， 假设xn = (a, b, d, c, e), f(xn) = 44, f(xn) > f(xb),
P = P – {xn} = {(a, b, e, d, c), (a, b, c, e, d)}

23 第五次循环 从P中选择一个元素， 假设xn = (a, b, e, d, c), f(xn) = 34, f(xn) < f(xb),
xb = (a, b, e, d, c), P = {(a, e, b, d, c), (a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)}

24 第六次循环 从P中选择一个元素， 假设xn = (a, e, b, d, c), f(xn) = 44, f(xn) > f(xb),
P = P – {xn} = {(a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)}

25 第七次循环 从P中选择一个元素， 假设xn = (a, d, e, b, c), f(xn) = 39, f(xn) > f(xb),
P = P – {xn} = {(a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)}

26 第八次循环 从P中选择一个元素， 假设xn = (a, c, e, d, b), f(xn) = 38, f(xn) > f(xb),
P = P – {xn} = {(a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)}

27 第九次循环 从P中选择一个元素， 假设xn = (a, b, d, e, c), f(xn) = 38, f(xn) > f(xb),
P = P – {xn} = {(a, b, c, d, e), (a, b, e, c, d)}

28 第十次循环 从P中选择一个元素， 假设xn = (a, b, c, d, e), f(xn) = 38, f(xn) > f(xb),
P = P – {xn} = {(a, b, e, c, d)}

29 第十一次循环 从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。

30 存在的问题 局部最优问题

31 解决方法 每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点，指标函数优的点，被选中的概率比较大，而指标函数差的点，被选中的概率比较小。

32 选择概率的计算 设求最大值：

33 选择概率的计算 当求最小值时：

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，结束

35 存在的问题 步长问题 初始值 搜索到的最优解

36 解决方法 变步长 初始值 搜索到的最优解

37 局部搜索算法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，结束

38 存在问题 起始点问题 全局最大值 局部最大值 A B

39 解决方法 随机的生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。

40 局部搜索算法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，结束

41 多种方法的集成 以上几种解决方法可以结合在一起使用，比如第一、第二种方法的结合，就产生了我们将在后面介绍的模拟退火方法。

42 皇后搜索算法（Queen Search） 1，随机地将n个皇后分布在棋盘上，使得棋盘 的每行、每列只有一个皇后。 2，计算皇后间的冲突数conflicts。 3，如果冲突数conflicts等于0，则转（6） 4，对于棋盘上的任意两个皇后，交换他们的行 或者列，如果交换后的冲突数conflicts减少， 则接受这种交换，更新冲突数conflicts，转3。 5，如果陷入了局部极小，既交换了所有的皇后 后，冲突数仍然不能下降，则转1。 6，输出结果 7，结束。

43 不同规模下皇后问题的 平均求解时间 皇 后 数 100 500 1000 2000 5000 10000 30000 平均时间（秒） 5
皇 后 数 100 500 1000 2000 5000 10000 30000 平均时间（秒） 5 12 28 170 900

44 模拟退火算法 是局部搜索算法的一种扩展 最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地将模拟退火算法用于求解组合优化问题。 基本思想是借用金属的退化过程改进局部搜索算法

45 固体退火过程 溶解过程：随着温度的不断上升，粒子逐渐脱离开其平衡位置，变得越来越自由，直到达到固体的溶解温度，粒子排列从原来的有序状态变为完全的无序状态。 退火过程：随着温度的下降，粒子的热运动逐渐减弱，粒子逐渐停留在不同的状态，其排列也从无序向有序方向发展，直至到温度很低时，粒子重新以一定的结构排列。

46 粒子不同的排列结构，对应着不同的能量水平。如果退火过程是缓慢进行的，也就是说，温度的下降如果非常缓慢的话，使得在每个温度下，粒子的排列都达到一种平衡态，则当温度趋于0（绝对温度）时，系统的能量将趋于最小值。

47 如果以粒子的排列或者相应的能量来表达固体所处的状态，在温度T下，固体所处的状态具有一定的随机性。一方面，物理系统倾向于能量较低的状态，另一方面，热运动又妨碍了系统准确落入低能状态。

48 Metropolis准则 从状态i转换为状态j的准则： 如果E(j)≤E(i)，则状态转换被接受；
其中E(i)、E(j)分别表示在状态i、j下的能量，T是温度，K＞0是波尔兹曼常数。

49 在给定的温度T下，当进行足够多次的状态转换后，系统将达到热平衡。此时系统处于某个状态i的概率由波尔兹曼（Boltzmann）分布给出：
（6） 其中 为归一化因子，S是所有可能状态的集合。

50 考察一下式（6）随温度T的变化情况： 同一温度下，两个能量不同的状态 高温下的情况 低温下的情况 当温度下降时的情况

51 在给定的温度T下，设有i、j两个状态，E(i)＜E(j) ：

52 当温度趋于无穷时： 其中|S|表示系统所有可能的状态数。 当温度很高时，系统处于各个状态的概率基本相等，接近于平均值，与所处状态的能量几乎无关。

53 当温度趋于0时 ： 设Sm表示系统最小能量状态的集合，Em是系统的最小能量。上式分子、分母同乘以

54

55 当温度趋近于0时，系统以等概率趋近于几个能量最小的状态之一，而系统处于其他状态的概率为0。以概率1达到能量最小的状态。

56 当温度上升或下降时：

57

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

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

60 达到最小能量状态的三个条件 （1）初始温度必须足够高； （2）在每个温度下，状态的交换必须足够充分； （3）温度T的下降必须足够缓慢。

61 组合优化问题与退火过程的类比 固体退火过程 组合优化问题 物理系统中的一个状态 组合优化问题的解 状态的能量 解的指标函数 能量最低状态
最优解 温度 控制参数

62 1，随机选择一个解i，k=0，t0=Tmax（初始温度），计算指标函数f(i)。
2，如果满足结束条件，则转（15）。 3，Begin 4， 如果在该温度内达到了平衡条件，则转（13）。 5， Begin 6， 从i的邻域N(i)中随机选择一个解j。 7， 计算指标函数f(j)。 8， 如果f(j)<f(i)，则i=j，f(i)=f(j)，转（4）。 9， 计算 10， 如果Pt(i=>j)>Random(0, 1)，则i=j，f(i)=f(j)。 11， 转（4） 12， End 13， tk+1=Drop(tk)，k=k+1。 14，End 15，输出结果。 16，结束。

63 算法中的问题 初始温度的选取 内循环的结束条件，即每个温度状态交换何时结束 外循环的结束条件，即温度下降到什么时候结束 温度的下降方法

64 在模拟退火过程中，给定温度下状态（解）的转移可以看作是一个马尔可夫链。对于任意两个状态i和j，我们用Pt(i, j)表示温度t下，从状态i转移到状态j的一步转移概率，则有：
其中：Gt(i,j) 是产生概率，表示从状态i产生状态j的概率。At(i,j) 是接受概率，表示在状态i产生状态j后，接受状态j的概率。

65 定理1

66 满足条件的Gt(i,j)、At(i,j) 举例：
说明：条件2的后半部分除外，该条件与具体的问题有关。

67 定理2： 在定理1的条件下，如果对于任意两个状态 有： 则有：

68 Gt(i,j)、At(i,j)满足定理1中除条件（2）以外的所有其他条件，并且：
定理3（放宽了定理1的条件） Gt(i,j)、At(i,j)满足定理1中除条件（2）以外的所有其他条件，并且： 1，对于任意两个状态i、j，它们相互为邻居或者相互都不为邻居； 2，对于任意i，Gt(i,j)满足： 3，状态空间S对于邻域是连通的； 则与模拟退火算法相伴的时齐马尔可夫链存在平稳分布，其分布概率为： 主要是放宽了对称的要求 邻域连同：可以理解为从任何一个邻域可以到达另一个邻域，即邻域是一环一环套在一起的。

69 算法的实现 （1）初始温度t0； （2）温度t的衰减函数，即温度的下降 方法； （3）算法的终止准则，用终止温度tf或 者终止条件给出；
（4）每个温度t下的马尔可夫链长度Lk。

70 起始温度的选取（1） 一个合适的初始温度，应保证平稳分布中每一个状态的概率基本相等，也就是接受概率P0近似等于1。在Metropolis准则下，即要求：

71 如果我们给定一个比较大的接受概率P0，则：

72 其中， 可以有以下估计方式：

73 起始温度的选取（2） 假设在t0下随机的生成一个状态序列，分别用m1和m2表示指标函数下降的状态数和指标函数上升的状态数， 表示状态增加的平均值。则m2个状态中，被接受的个数为：

74 所以平均接受率为： 求解有：

75 起始温度的选取（3） 模拟固体的升温过程： （1）给定一个希望的初始接受概率P0，给定一个较低的初始温度t0，比如t0＝1；
（2）随机的产生一个状态序列，并计算该序列的接收率： 如果接收率大于给定的初始接受概率P0，则转（4）； （3）提高温度，更新t0，转（2）； （4）结束。

76 温度的下降方法（1） 等比例下降

77 温度的下降方法（2） 等值下降

78 温度的下降方法（3） 由定理1我们知道，在一定的条件下，与模拟退火算法相伴的时齐马尔可夫链存在平稳分布。如果温度每次下降的幅度比较小的话，则相邻温度下的平稳分布应该变化不大，也就是说，对于任意一个状态i，相邻温度下的平稳分布应满足：

79 一个充分条件是： 充分条件：左边是大于1的，因此是充分的

80 两边取对数，并整理得： 用 代替 可得温度的衰减函数：

81 每一温度下的停止准则（1） 固定长度方法 在每一个温度下，都使用相同的Lk。Lk的选取与具体的问题相关，一般与邻域的大小直接关联，通常选择为问题规模n的一个多项式函数。

82 每一温度下的停止准则（2） 基于接受率的停止准则 ：
规定一个接受次数R，在某一温度下，只有被接受的状态数达到R时，在该温度下的迭代才停止，转入下一个温度。 规定一个状态接受率R，R等于该温度下接受的状态数除以总生成的总状态数。如果接受率达到了R，则停止该温度下的迭代，转入下一个温度。 在迭代的过程中，若干相邻的状态称为“一代”，如果相邻两代的解的指标函数差值小于规定的值的话，则停止该温度下的迭代。

83 算法的终止原则 （1） 零度法 设定一个正常数e，当时tk<e时，算法结束。

84 算法的终止原则 （2） 循环总控制法 给定一个指定的温度下降次数K，当温度的迭代次数达到K次时，则算法停止。

85 算法的终止原则 （3） 无变化控制法 如果在相邻的n个温度中，得到的解的指标函数值无任何变化，则说明算法已经收敛。

86 算法的终止原则 （4） 接受概率控制法 给定一个小的概率值p，如果在当前温度下除了局部最优状态外，其他状态的接受概率小于p值，则算法结束。

87 算法的终止原则 （5） 领域平均概率控制法 设大小为N的一个领域，在邻域内一个状态被接受的平均概率为1/N。设f0、f1为该领域中的局部最优值和局部次最优值。则次最优解是除了局部最优解以外接受概率最大的，其接受概率为：

88 如果该概率值小于平均值1/N时，即： 可以认为从局部最优解跳出的可能性已经很小了，因此可以终止算法。此时的终止温度tf为：

89 算法的终止原则 （6） 相对误差估计法 设温度t时指标函数的期望值为： 则当终止温度<<1时，由泰勒展开近似有：

90 由于： 所以可用下式估计当前解与最优解之间的误差 ：

91 或者使用相对于 的相对误差：

92 实际计算时： 其中：

93 应用举例——旅行商问题 解的表示： n个城市的任何一种排列均是问题的一个可能解，表示为: 指标函数(能量函数) 其中

94 新解的产生 采用第一节介绍的两个城市间的逆序交换方式得到问题的一个新解。
设当前解是 ，被选中要逆序交换的城市是第u和第v个到访的城市，u<v。则逆序排列u和v之间的城市，得到问题的新解为： 则两个路径的距离差为：

95 新解的接受准则

96 初始参数的确定 康立山等人的方法： 初始温度t0=280； 在每个温度下采用固定的迭代次数，Lk=100n，n为城市数；
温度的衰减系数＝0.92，即tk+1=0.92×tk； 算法的停止准则为：当相邻两个温度得到的解无任何变化时算法停止。

97 Nirwan Ansari和Edwin Hou的方法：
初始温度t0是这样确定的：从t0=1出发，并以t0=1.05×t0对t0进行更新，直到接受概率大于等于0.9时为止，此时得到的温度为初始温度； 在每个温度下采用固定的迭代次数，Lk=10n，n为城市数； 温度的衰减系数＝0.95，即tk+1=0.95×tk；

98 10城市旅行商问题求解结果 路径长度 出现次数 平均转移次数 路径 最优 2.691 906 3952 BCADEFGHIJ 次优
路径长度 出现次数 平均转移次数 路径 最优 2.691 906 3952 BCADEFGHIJ 次优 2.752 46 4056 BCADEGFHIJ 第三 2.769 10 4053 DEFGHIJCBA 最差 2.898 5 4497 ABCDEFHIJG

99 20城市旅行商问题求解结果 路径长度 出现次数 平均转移次数 路径 最优 24.38 792 8740
路径长度 出现次数 平均转移次数 路径 最优 24.38 792 8740 ACLBIQFTMEPRGSOJHDKN 次优 24.62 167 8638 ADCLBIQFTMEPRGSOJHKN 第三 25.17 39 9902 ANKDHIOJSGRPEMTFQBLC 最差 25.50 1 5794 AQFTMEPRGSJOIBLCDHKN