《清华大学人工智能导论课件_第七章》由会员分享，可在线阅读，更多相关《清华大学人工智能导论课件_第七章（61页珍藏版）》请在金锄头文库上搜索。
1、第7章 高级搜索在第一章、第二章，我们分别介绍了深度优先、宽度优先、A*算法和AO*算法等常规的搜索算法。深度优先、宽度优先等盲目搜索算法就不用说了，即便是A*算法，一般情况下，其算法复杂性仍然是指数时间级的。因此，当问题的规模大到一定程度之后，这些常规的搜索算法就显得无能为力了。本章将介绍一些相对比较新的搜索方法，如局部搜索、模拟退火和遗传算法等。这些算法的一个共同特点是引入了随机因素，每次运行并不能保证求得问题的最优解，但经过多次运行之后，一般总能得到一个与最优解相差不太大的满意解。以放弃每次必然找到最佳解，换取了算法时间复杂度的降低，以适合于求解大规模的优化问题。7.1 基本概念7.1.
2、1 组合优化问题在现实世界中，很多问题属于优化问题，或者可以转化为优化问题求解。比如我们前面介绍过的旅行商问题（TSP），就是求解旅行商在满足给定的约束条件下的最短路径问题。这里的约束条件是“从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后再回到出发城市”。还有皇后问题，它要求在一个nn的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”，即在任何一行、一列和任何一个斜线上，只能有一个皇后。皇后问题本身并不是一个优化问题，但可以转化为优化问题来求解。比如我们可以定义指标函数为棋盘上能够相互“捕捉”的皇后数，显然该指标函数的取值范围是一个大于等于0的整数，当棋盘上
3、摆放了n个皇后，且其指标函数取值为最小值0时，刚好是问题的解。因此皇后问题转变成了求解该指标函数最小的优化问题。设x是决策变量，D是x的定义域，f(x)是指标函数，g(x)是约束条件集合。则优化问题可以表示为，求解满足g(x)的f(x)最小值问题。即（7.1）如果在定义域D上，满足条件g(x)的解是有限的，则优化问题称为组合优化问题。现实世界中的大量优化问题，属于组合优化问题。像旅行商问题、皇后问题等是组合优化问题的典型代表。对于组合优化问题，由于其可能的解是有限的，当问题的规模比较小时，总可以通过枚举的方法获得问题的最优解，但当问题的规模比较大时，其状态数往往呈指数级增长，这样就很难通过枚举
4、的方式来获得问题的最优解了。一个问题的大小通常用输入数据量n来衡量，如旅行商问题中的城市数目，皇后问题中的皇后数目等。对于同一个问题，不同的求解方法的效率是不同的，差别可能会非常大。通常用算法的时间复杂性来评价一个求解方法的好坏。常用的算法复杂性函数按复杂性从小到大排列有如下几种：其中O(h(n)表示该算法的复杂性为h(n)量级。如n皇后问题，由问题的约束条件，我们知道每一行、每一列只能并且必须放一个皇后。如果我们先不考虑对角线的情况，先用枚举法生成出n个皇后不在同一行、同一列的所有状态，再从中找出满足约束条件的解。从第一行开始放起，则第一行每个位置都可以放皇后，因此共有n种方法；第二行除了第
5、一行皇后的所在列以外，其他位置都可以放皇后，因此共有n-1种方法；依此类推，第i行共有n-i种摆放方法。所以所有可能的状态数共n!个。这样我们可以大概估算出，用这样一种枚举法求解n皇后问题，所花费的时间与n!成正比关系，其时间复杂性用算法复杂性函数表示就是O(n!)。Nirwan Ansari和Edwin Hou在他们的书中，给出了假定计算机的处理速度为每秒钟执行10亿次运算的条件下，不同输入数据量下各种复杂性函数所需要的计算时间。如表7.1所示。表7.1 时间复杂性函数比较 输入量n复杂性函数10203040100n10ns20ns30ns40ns100nsnlogn10ns26.0ns44
6、.3ns64.1ns200nsn2100ns400ns900ns1.6s10s2n1.0s1.0ms1.1s18.3min4.0世纪n!3.6ms77.1年8.41013世纪2.61029世纪3.010139世纪当一个算法的时间复杂性可以表示为多项式形式时，则称之为多项式时间算法，否则就是一个指数时间算法。从表7.1中可以看出，如果一个算法是指数时间算法（2n或者n!），那么当n大到一定程度时，因为所花费的时间太长了，以至于不可能求解。一些组合优化问题已经找到了多项式时间算法，如线性规划问题。还有一些被称为难于求解的组合优化问题，至今还没有找到求解这些问题的最优解的多项式时间算法。像旅行商问题
7、、背包问题、装箱问题等，都属于这类难于求解的组合优化问题。由于这些问题都有很强的实际背景，为此人们研究一些不一定能求得最优解，但往往能得到一个满意解的算法，以此来降低算法的复杂性。而实际上很多情况下追求最优解并不一定有意义，一个满意解就已经足够了。这就如同夏天去买西瓜。你没有必要非要买一个北京市最甜的西瓜，甚至于也没有必要买一个西瓜摊中最甜的西瓜，因为这样选择的工作量太大了。你只需从面前的35个西瓜中选择一个最好的就可以。当面前的这几个西瓜都感觉不合适时，你可以换一个位置，或者换另一个西瓜摊重新选择。如果你对西瓜的评价是正确的话，那么这样选择出来的西瓜应该是一个令你满意的西瓜，与“最甜的西瓜”
8、差别也不会太多。7.1.2 邻域在后面的介绍中经常会用到邻域的概念。我们先给出邻域的定义。邻域，简单的说就是一个点附近的其他点的集合。在距离空间中，邻域一般定义为以该点为中心的一个圆。在组合优化问题中，距离的概念不一定适用，为此提出其他的邻域定义。设D是问题的定义域，若存在一个映射N，使得：（7.2）则称N(S)为S的邻域，称为S的邻居。下面举几个例子。例1：皇后问题为了简单起见，我们以4皇后问题为例说明。设棋盘从左到右依次为第一列、第二列、第四列，从上到下依次为第一行、第二行、第四行。我们用14的一个序列S=(si)(i = 1, 2, 3, 4; si=1, 2, 3, 4)表示4皇后问题
9、的一个可能的解。其中si表示在第i行、第si列有一个皇后。如：S = (2, 4, 1, 3)表示的是如图7.1所示的棋盘格局。定义映射N为棋盘上任意两个皇后的所在行或列进行交换，即S中任意两个元素交换位置，这样可以得到S的所有邻居共个，所有邻居的集合就是S的邻域。当S = (2, 4, 1, 3)时，其邻域为：N(S) = (4, 2, 1, 3), (1, 4, 2, 3), (3, 4, 1, 2), (2, 1, 4, 3), (2, 3, 1, 4), (2, 4, 3, 1)交换不一定限制在两个皇后之间进行，也可以选择三个皇后进行交换。不同的交换方式，得到的邻域可能是不同的。QQQ
10、Q图7.1，4皇后问题的一个格局例2，旅行商问题旅行商问题可以用一个城市的序列表示一个可能的解。可以采用与皇后问题类似的方法，通过交换两个城市的位置获取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)图7.2给出了这种位置交换方式的示意图。x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1 图7.2. 位置交换方式示
11、意图也可以采取逆序交换的方式获取S的邻居。设i、j是选取的两个整数，ij，0i,jn+1。所谓的逆序交换方式是指，通过逆转xi、xj两个城市之间的城市次序来得到S的邻居。即：S = (x1, x2, xi-1, xi, xj-1, x j-2, xi+1, xj, xj+1, , xn)图7.3给出了逆序交换方式的示意图。x1x2xnxj+1xjxj-1xi-1xixi+1x1x2xnxj+1xjxj-1xi-1xixi+1 图7.3. 逆序交换方式示意图在一个邻域内的最优解，我们称为局部最优解。相应地，在整个定义域上的最优解称为全局最优解。7.2 局部搜索算法局部搜索算法是从爬山法改进而来的
12、。设想我们要爬一座自己从未爬过的高山，目标是爬到山顶，那么如何设计一种策略使得我们可以最快的达到山顶呢？在一般的情况下，如果我们没有任何有关山顶的其他信息，沿着最陡的山坡向上爬，应该是一种不错的选择。这就是局部搜索算法中最基本的思想，即在搜索过程中，始终向着离目标最接近的方向搜索。当然最优解可以是求解最大值，也可以是求解最小值，二者的思想是一样的。在下面的讨论中，如果没有特殊说明，均假定最优解求解的是最小值。下面我们首先给出局部搜索的最一般算法，在下面算法的描述中，“；”号后面的内容为算法的注释。局部搜索算法（Local Search）1，随机的选择一个初始的可能解x0D，xb=x0，P=N(xb)；D是问题的定义域，xb用于记录到目标位置得到的最优解，P为xb的邻域。2，如果不满足结束条件，则；结束条件包括达到了规定的循环次数、P为空等3，Begin4，选择P的一个子集P，xn为P中的最优解5，如果f(xn) f(xb), P = P xn = (a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a
