第三章 搜索(2)—启发式搜索.ppt

1、,第 三章,启发式搜索,启发式搜索,第三章 - 2,纽厄尔和西蒙（Newell and Simon) ，1976年度ACM图灵奖获奖演说,当问题和问题空间确定后，符号系统所要解决 的任务就是如何使用有限的处理资源来产生可能 解，直到发现一个可以通过（问题所定义）检验 的解。 如果符号系统可以对可能解的产生顺序进行 某种控制，并对这个产生顺序加以组织以使高可 能性的解出现，那么这是非常理想的。如果符号 系统成功地做到了这一点，那么它便展示出了智 能。 对于一个处于有限资源下的系统来说，智能 体现在明智地选择下一步该做什么,启发式搜索,第三章 - 3,内容,3.0 简介 3.1 启发式搜索算法 3

2、.1.0 局部择优搜索 3.1.1 全局择优搜索（A算法） 3.1.2 A*算法 3.2 应用举例 3.3 基于搜索的优化问题,启发式搜索,第三章 - 4,3.0 简介,启发式搜索 利用问题自身的特性信息（启发信息）来引导搜索过程,达到减少搜索范围，降低问题复杂度的搜索方法。 引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。 启发信息的强度 强 降低搜索工作量，但可能导致找不到最优解。 弱： 一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解。,启发式搜索,第三章 - 5,3.0 简介,对一个假象状态空间的启发式搜索,【例1】,启发式搜索,第三章 - 6

3、,3.0 简介,【例2】 通过对称抵消后的九宫游戏状态空间的前三层,启发式搜索,第三章 - 7,3.0 简介,假定采用如下“启发”裁减九宫游戏状态空间。 移动到方胜利路线最多的状态,顶角方格有三种 胜利路线,中央方格有四种 胜利路线,边方格有两种 胜利路线,启发式搜索,第三章 - 8,3.0 简介,启发式搜索,第三章 - 9,3.0 简介,启发式搜索基本思想： 定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。,启发式搜索,第三章 - 10,3.0 简介,评价函数 f(n) = g(n) + h(n) f(n)：评价函数 h(n)：启发函数 符号的意义 f*(n)=g

4、*(n)+h*(n) f*(n)：从s经过n到g的最短路径的耗散值。 g*(n)：从s到n的最短路径的耗散值。 h*(n)：从n到g的最短路径的耗散值。 注意： g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值。,启发式搜索,第三章 - 11,3.0 简介,对启发式搜索算法，可根据搜索过程中选择扩展节点的范围，将其分为： 局部择优搜索算法 局部最佳优先搜索算法（Local-Best-First-Search） 全局择优搜索算法 最佳优先搜索算法（Best-First-Search） A算法 A*算法,启发式搜索,第三章 - 12,内容,3.0 简介 3.1 启发式搜

5、索算法 3.1.0 局部择优搜索 3.1.1 全局择优搜索（A算法） 3.1.2 A*算法 3.2 应用举例 3.3 基于搜索的优化问题,启发式搜索,第三章 - 13,3.1.0 局部择优搜索,（1）把初始节点S0放入 Open表中，f(S0)=g(S0)+h(S0) ; （2）如果Open表为空，则问题无解，失败退出； （3）把Open表的第一个节点取出放入Closed表，并记该节点 为n； （4）考察节点n是否为目标节点。若是，则找到了问题的解， 成功退出； （5）若节点n不可扩展，则转第（2）步； （6）扩展节点n，生成其子节点ni(i=1，2，)，计算每一个 子节点的估价值f（ni）（

6、i=1，2，），并按估价值 从小到大的顺序依次放入Open表的首部，并为每一个子 节点设置指向父节点的指针，然后转第（2）步。,局部择优搜索算法,启发式搜索,第三章 - 14,3.1.0 局部择优搜索,Hill Climbing Strategy（爬山策略） 在搜索过程中扩展当前状态； 评估它的孩子； 选择最佳的孩子做进一步扩展； 当搜索遇到了一个比其所有孩子都更佳的状态时 便停止。 注意：这个过程中，既不保留它的兄弟节点，也不保留它的双亲。所以无法辨别局部和全局最大值。,启发式搜索,第三章 - 15,3.1.0 局部择优搜索,基于爬山策略的启发式搜索,Romania Map,h(n)：各城市

7、到首都布加勒斯特的直线距离。,启发式搜索,第三章 - 17,3.1.0 局部择优搜索,问题： 使用局部择优搜索从Arad到Bucharest（布加勒斯特）的最短路径。 令：f(n)=h(n),Arad (366),启发式搜索,第三章 - 18,3.1.0 局部择优搜索,启发式搜索,第三章 - 19,3.1.0 局部择优搜索,分析： 深度优先搜索、代价树的深度优先搜索以及局部优先搜索都是以子节点作为考察范围，但选择节点的标准不一样。 对于局部择优搜索算法： 如果取估价函数f（ n）= g（n），则它将退化为代价树的深度优先搜索。 如果取估价函数f（n）= d（n），则它将退化为深度优先搜索。 因

8、此，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。,启发式搜索,第三章 - 20,内容,3.0 简介 3.1 启发式搜索算法 3.1.0 局部择优搜索 3.1.1 全局择优搜索（A算法） 3.1.2 A*算法 3.2 应用举例 3.3 基于搜索的优化问题,启发式搜索,第三章 - 21,3.1.1 A算法,A算法也称为最佳优先搜索(best-first search) 搜索的每一步都利用估价函数f（n）对Open表中的所有节点进行排序。 f（n）=g（n）h（n）,启发式搜索,第三章 - 22,3.1.1 A算法,（1）把初始节点S0放入Open表中，f(S0)=g（S0）h（S0

9、）； （2）如果Open表为空，则问题无解，失败退出； （3）把Open表的第一个节点取出放入Closed表，并记该节点 为n； （4）考察节点n是否为目标节点。若是，则找到了问题的解， 成功退出； （5）若节点n不可扩展，则转第（2）步； （6）扩展节点n，生成其子节点ni（i=1,2,），计算每一 个子节点的估价值f(ni) （i=1,2,），并为每一个 子节点设置指向父节点的指针，然后将这些子节点放入 Open表中； （7）根据各节点的估价函数值，对Onen表中的全部节点按从 小到大的顺序重新进行排序； （8）转第（2）步。,对一般图如何处理？,启发式搜索,第三章 - 23,3.1.1

10、A算法,分析： 如果取估价函数f(n)=g（n），则它将退化为代价树的广度优先搜索。 如果取估价函数f(n)=d（n），则它将退化为广度优先搜索。 因此，广度优先搜索和代价树的广度优先搜索是全局择优搜索的两个特例。,启发式搜索,第三章 - 24,3.1.1 A算法,回顾一般图搜索,.,.,.,.,.,mj,mk,ml,n,a,b,启发式搜索,第三章 - 25,3.1.1 A算法,1 OPEN:=(s), f(s):=g(s)+h(s); 2 LOOP: IF OPEN=( ) THEN EXIT(FAIL); 3 n:=FIRST(OPEN); 4 IF GOAL(n) THEN EXIT(S

11、UCCESS); 5 REMOVE(n, OPEN), ADD(n, CLOSED); 6 EXPAND(n) mi, 计算f(n, mi):=g(n, mi)+h(mi); ADD(mj, OPEN), 标记mj到n的指针； IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 标记mk到n的指针； IF f(n, ml)f(ml) THEN f(ml):=f(n, ml), 标记ml到n的指针, ADD(ml, OPEN); 7 OPEN中的节点按f值从小到大排序； 8 GO LOOP；,一般图搜索的A算法,启发式搜索,第三章 - 26,【例1】,初始节点: a,目

12、标节点: q,3,2,3,3,3,2,2,1,2,2,2,2,3,5,4,1,3,1,1,3,2,3,2,2,G 值: 从初始节点到当前节点的成本。 H 值: 到目标节点的估计值(, .) F = G + H,启发式搜索,第三章 - 27,（1）,（2）,（3）,（4）,（5）,（6）,（7）,（8）,（9）,（10）,（11）,（12）,（13）,（14）,启发式搜索,第三章 - 28,3.1.1 A算法,【例2】八数码问题。 定义评价函数：f(n) = g(n) + h(n),启发式搜索,第三章 - 29,3.1.1 A算法,启发1： 数出每个状态与目标状态相比错位的牌数。,启发2： 对错

13、位的牌必须要移动的距离求和。,启发3： 对每个“直接颠倒”乘以一个小的数字。,启发式搜索,第三章 - 30,3.1.1 A算法,错位牌数,错位的距离和,2*直接颠倒数,启发式搜索,第三章 - 31,3.1.1 A算法,g(n)=0,g(n)=1,启发式搜索,第三章 - 34,思考题,八皇后问题 在国际象棋棋盘的一个88区域放置8个皇后棋子，并满足约束：每行、每列和对角线上只允许出现一个皇后，以避免皇后间发生冲突。,启发式搜索,第三章 - 35,思考题,设计四皇后问题的启发函数h(n) 问题状态： 用列表L指示，L的元素就是皇后在棋盘中的位置ij(1I,j4)； 按自上而下的次序在棋盘的4行中放

14、置皇后； 空表L指示初始状态；当表L包含4个满足约束的皇后位置时，到达目标状态； 当皇后位置发生冲突时，意味着进入不合法状态（失败状态）。,(12 24 31 43),启发式搜索,第三章 - 36,思考题,设计四皇后问题的启发函数h(n),(12 24 31 43),启发式搜索,第三章 - 37,内容,3.0 简介 3.1 启发式搜索算法 3.1.0 局部择优搜索 3.1.1 全局择优搜索（A算法） 3.1.2 A*算法 3.2 应用举例 3.3 基于搜索的优化问题,启发式搜索,第三章 - 38,内容,3.1.2 A*算法 1.A*算法定义 2.A*算法的性质 3.启发函数h（n）的评价方法

15、4.A*算法复杂性 5.A*算法的改进,启发式搜索,第三章 - 39,1.A*算法定义,如果A算法使用的评估函数h（n）满足： h（n）h*（n） 那么该算法称为A*算法。,例如： 8数码问题 h1(n) = “不在位”的将牌数 h2(n) = 将牌“不在位”的距离和,启发式搜索,第三章 - 40,内容,3.1.2 A*算法 1.A*算法定义 2.A*算法的性质 3.启发函数h（n）的评价方法 4.A*算法复杂性 5.A*算法的改进,启发式搜索,第三章 - 41,2. A*算法的性质,A*算法的假设 设ni、nj是任意两个节点，有： C(ni, nj) 其中为大于0的常数,几个等式 f*(s)

16、 = f*(t) = h*(s) = g*(t) = f*(n) s是初始节点 t是目标节点 n是s到t的最佳路径上的节点。,s,t,启发式搜索,第三章 - 42,2. A*算法的性质定理1,定理1 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。,引理1.1 对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)f*(s)。,s,t,启发式搜索,第三章 - 43,2. A*算法的性质定理1,引理1.2 A*结束前，OPEN表中必存在f(n)f*(s)。,存在一个节点n，n在最佳路径上。 f(n) =

17、g(n) + h(n) = g*(n)+h(n) g*(n)+h*(n) = f*(n) = f*(s),定理1 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。,启发式搜索,第三章 - 44,2. A*算法的性质定理2,定理2（完备性） 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。,引理1.1：A*如果不结束，则OPEN中所有的n有 f(n) f*(s) 引理1.2：在A*结束前，必存在节点n，使得 f(n) f*(s) 所以，如果A*不结束，将导致矛盾。,启发式搜索,第三章 - 45,2. A*算法的性质定理2,推论2.1 OPEN表上任一具

18、有f(n)f*(s)的节点n，最终都将被A*选作扩展的节点。,定理2 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。,由定理2，知A*一定结束，由A*的结束条件，OPEN表中f(t)最小时才结束。而 f(t) f*(t) f*(s) 所以f(n)f*(s)f(t)的n，均被扩展。得证。,启发式搜索,第三章 - 46,2. A*算法的性质定理3,定理3（可采纳性） 若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。,由定理1、2知A*一定找到一条路径结束 设找到的路径s t不是最佳的（t为目标） 则：f(t) = g(t) f*(s) 由引理1.2知结束前OP

19、EN中存在f(n)f*(s)的节点n，所以 f(n) f*(s) f(t) 因此A*应选择n扩展，而不是t。与假设A*选择t结束矛盾。得证。 注意：A*的结束条件,证明,启发式搜索,第三章 - 47,2. A*算法的性质定理3,定理3（可采纳性） 若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。 推论3.1 A*选作扩展的任一节点n，有f(n)f*(s)。,由引理1.2知在A*结束前，OPEN中存在节点n， f(n)f*(s) 设此时A*选择n扩展。 如果nn，则f(n)f*(s)，得证。 如果n n，由于A*选择n扩展，而不是n，所以有f(n) f(n)f*(s)。得证。,证

20、明,启发式搜索,第三章 - 48,2. A*算法的性质定理4,定理4（最优性） 设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n) h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。 简写为： 如果h2(n) h1(n) (目标节点除外)，则 A1扩展的节点数A2扩展的节点数 注意： 在定理4中，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只计算一次。,启发式搜索,第三章 - 49,2. A*算法的性质定理4,定理4,使用数

21、学归纳法，对节点的深度进行归纳 （1）当d(n)0时，即只有一个节点，显然定理成立 （2）设d(n)k时定理成立。（归纳假设） （3）当d(n)=k+1时，用反证法。 设存在一个深度为k1的节点n，被A2扩展，但没有被A1 扩展。而由假设，A1扩展了n的父节点，即n已经被生成 了。因此当A1结束时，n将被保留在OPEN中。,证明：,启发式搜索,第三章 - 50,2. A*算法的性质,定理4证明（续）,所以有：f1(n) f*(s) 即：g1(n)+h1(n) f*(s) 所以： h1(n) f*(s) - g1(n) 另一方面，由于A2扩展了n，有f2(n) f*(s) 即： h2(n) f*

22、(s) g2(n) (A) 由于d(n)=k时，A2扩展的节点A1一定扩展，有 g1(n) g2(n) (因为A2的路A1均走到了) 所以： h1(n) f*(s) - g1(n) f*(s) g2(n) (B) 比较A、B两式，有 h1(n) h2(n) ，与定理条件矛盾。故定理得证。,启发式搜索,第三章 - 51,内容,3.1.2 A*算法 1.A*算法定义 2.A*算法的性质 3.启发函数h（n）的评价方法 4.A*算法复杂性 5.A*算法的改进,启发式搜索,第三章 - 52,3. 启发函数h（n）的评价方法,平均分叉树 共扩展了L层节点 平均分支数（状态空间的分支因子）为B 共搜索了T

23、个节点,T = B + B2 + + BL,B越小，说明h效果越好。 实验表明， B是一个比较稳定的常数，同一问题基本不随问题规模变化。,启发式搜索,第三章 - 53,3. 启发函数h（n）的评价方法,例：8数码问题，随机产生若干初始状态。 使用h1： 使用h2：,L=14, N=539, B=1.44; L=20, N=7276， B=1.47；,L=14, N=113, B=1.23; L=20, N=676,B=1.27;,启发式搜索,第三章 - 54,3. 启发函数h（n）的评价方法,相对于分支因子B和不同解路径长度L的函数曲线产生的节点数，摘自Nilsson（1980）,启发式搜索,

24、第三章 - 55,内容,3.1.2 A*算法 1.A*算法定义 2.A*算法的性质 3.启发函数h（n）的评价方法 4.A*算法复杂性 5.A*算法的改进,启发式搜索,第三章 - 56,4. A*算法复杂性,一般来说，A*的算法复杂性是指数型的，可以证明，当且仅当以下条件成立时： A*的算法复杂性才是非指数型的，但是通常很难做到。,abs(h(n)-h*(n) O(log(h*(n),启发式搜索,第三章 - 57,4. A*算法复杂性,如何降低复杂性？ 定向搜索（beam search） 搜索算法的复杂性可以用Open和Closed列表的大小来衡量。 能否使Open列表仅仅保存一定数量的最好的

25、状态节点，以使Open列表的大小保持在一个合理的范围内? 优点： 可以使搜索更加集中，从而降低复杂性。 缺点： 可能存在排除最好的或者是唯一的解路径的风险。,启发式搜索,第三章 - 58,4. A*算法复杂性,如何降低复杂性？ 更高信息度的启发 搜索所用启发的信息度h（n）越高，那么为了得到最短路径解所必须搜索的空间就越小。,但是所用启发的信息度h（n）越复杂，计算每个状态空间节点的h（n）所用的CPU开销也越大。 计算h（n）的运算开销将会降低搜索算法的速度。,因此，需要一种折衷的办法。,启发式搜索和宽度优先搜索所搜索的状态空间的比较,启发式搜索,第三章 - 60,4. A*算法复杂性,搜索

26、开销和评估启发的开销相对于启发信息度的粗略曲线，摘自Nilsson（1980）,启发式搜索,第三章 - 61,思考题,8格拼图游戏 启发函数h1（n）：（不受阻拦）错位的牌数。 启发函数h2（n）：（不受阻拦）错位牌的距离和。 问题： 启发函数h1（n）和h2（n）是否满足A*算法的条件？ 画出搜索图，并给出各搜索循环结束时Open和Close表的内容。 用A算法搜索从给定的初始状态到目标状态的路径 通过比较两种启发搜索扩展的节点数目分析两种启发函数的信息度。 方法一：定性比较h1（n）和h2（n）的大小； 方法二：分析两种启发搜索的分支因子B的大小；,启发式搜索,第三章 - 62,内容,3.

27、1.2 A*算法 1.A*算法定义 2.A*算法的性质 3.启发函数h（n）的评价方法 4.A*算法复杂性 5.A*算法的改进,启发式搜索,第三章 - 63,5. A*算法的改进,例如：,s(10),s(10),A(7) B(8) C(9),A(7) s(10),B(8) C(9) G(14),A(5) C(9) G(14),C(9) G(12),B(7) G(12),A(4) G(12),G(11),B(8) s(10),A(5) B(8) s(10),C(9) A(5) s(10),B(7) C(9) s(10),A(4) B(7) C(9) s(10),注：假定图中节点括号中的值为启发值

28、h，弧上的值为两节点间的实际距离。,启发式搜索,第三章 - 64,5. A*算法的改进,问题的提出： 因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。,.,.,.,.,.,mj,mk,ml,n,a,b,启发式搜索,第三章 - 65,5. A*算法的改进,解决的途径 对h加以限制 能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。 对算法加以改进 能否对算法加以改进，避免或减少节点的多次扩展。 改进的条件 可采纳性不变 不多扩展节点 不增加算法的复杂性,启发式搜索,第三章 - 66,5. A*算法的改

29、进对h加以限制,定义 一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足：,h(ni) - h(nj) c(ni, nj) h(t) = 0,或,h(ni) c(ni, nj) + h(nj) h(t) = 0,则称h是单调的。,h(ni),ni,nj,h(nj),c(ni,nj),启发式搜索,第三章 - 67,5. A*算法的改进对h加以限制,定理5（ h的单调性） 定理5.1： 若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。 即：当A*算法选n扩展时，有g(n)=g*(n)。 定理5.2： 由A*算法所扩展的节点序列其f值是非递减的。 定

30、理5.3： 启发函数h满足单调性也必然满足A*算法的条件，即任何单调的启发是可采纳的。,启发式搜索,第三章 - 68,5. A*算法的改进对h加以限制,证明定理5.3 把空间中的任何路径看作是状态s1，s2，sg的序列，其中s1是初始状态，sg是目标状态。,根据单调属性，从s1到s2：h(s1)-h(s2) cost(s1,s2) 根据单调属性，从s2到s3：h(s2)-h(s3) cost(s2,s3) 根据单调属性，从s3到s4：h(s3)-h(s4) cost(s3,s4) 根据单调属性，从sg-1到sg：h(sg-1)-h(sg) cost(sg-1,sg),h(s1) cost(s1

31、,sg),启发式搜索,第三章 - 69,5. A*算法的改进,解决的途径 对h加以限制 能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。 对算法加以改进 能否对算法加以改进，避免或减少节点的多次扩展。 改进的条件 可采纳性不变 不多扩展节点 不增加算法的复杂性,查阅相关论文,启发式搜索,第三章 - 70,内容,3.0 简介 3.1 启发式搜索算法 3.1.0 局部择优搜索 3.1.1 全局择优搜索（A算法） 3.1.2 A*算法 3.2 应用举例 3.3 基于搜索的优化问题,启发式搜索,第三章 - 71,3.2 应用举例,【例1 】Romania,启发式搜索,

32、第三章 - 72,3.2 应用举例,启发式搜索,第三章 - 73,3.2 应用举例,启发式搜索,第三章 - 74,3.2 应用举例,Optimal solution (only if h(n) is admissable),启发式搜索,第三章 - 75,3.2 应用举例（游戏中的路径规划问题）,【例2】游戏中的路径规划问题 游戏AI中，经常需要为智能主体在游戏世界中规划出一条路径，以使其从某处到达另一处。,关键问题 (1) 定义搜寻区域 (划分地形) 将连续的地形离散化， 用于创建可搜索的数 据、(建立尽可能少的 节点)。,PATHDEMO,启发式搜索,第三章 - 76,启发式搜索,第三章 -

33、 77,启发式搜索,第三章 - 78,3.2 应用举例（游戏中的路径规划问题）,【例2】游戏中的路径规划问题,关键问题 (2) 障碍物的躲避 (3) 不同类型地形 的识别问题 (4) 最优路径搜寻 (A*算法),启发式搜索,第三章 - 79,3.2 应用举例（游戏中的路径规划问题）,没有考虑不同类型地形成本,考虑不同类型地形成本得到的最低代价路径,启发式搜索,第三章 - 80,3.2 应用举例（游戏中的路径规划问题）,【例2】游戏中的路径规划问题 关键问题 （5）绝好的路径搜索在不占用大量CPU的情况下难以实 现。如何保证几百个部队能同时在地图各处搜索路 径而不让系统瘫痪？ A*算法执行性能分

34、析及优化技术,启发式搜索,第三章 - 81,3.2 应用举例（游戏中的路径规划问题）,【例2】游戏中的路径规划问题 简单实例分析,启发式搜索,第三章 - 82,3.2 应用举例,启发式搜索,第三章 - 83,启发式搜索,第三章 - 84,启发式搜索,第三章 - 85,启发式搜索,第三章 - 86,启发式搜索,第三章 - 87,启发式搜索,第三章 - 88,内容,3.0 简介 3.1 启发式搜索算法 3.1.0 局部择优搜索 3.1.1 全局择优搜索（A算法） 3.1.2 A*算法 3.2 应用举例 3.3 基于搜索的优化问题,启发式搜索,第三章 - 89,3.3 基于搜索的优化问题,解决优化问

35、题的启发式算法 爬山算法 禁忌搜索算法 模拟退火算法 遗传算法 蚂蚁算法 ,优化问题描述: Find the values of a vector that minimize a scalar valued loss function L(). : the domain of allowable values for a vector 注: loss function 也被称为: performance measure， cost function， objective function， fitness function, or criterion etc.,启发式搜索,第三章 - 90,T

36、he N-Queens Problem,启发式搜索,第三章 - 91,3.3 基于搜索的优化问题,3.3.1 爬山法(贪婪局部搜索算法) 实现启发式搜索最简单的方式。 无法把握整个状态空间的情况，所以他可能永远达不到全局最佳值。,转载 兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。,启发式搜索,第三章 - 92,3.3 基于搜索的优化问题,禁忌搜索算法（tabu搜索算法） 禁忌搜索是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的。

37、,转载 兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。,启发式搜索,第三章 - 93,3.3 基于搜索的优化问题,模拟退火算法（Simulated Annealing） 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。,转载 兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳

38、去。这就是模拟退火。,启发式搜索,第三章 - 94,3.3 基于搜索的优化问题,启发式搜索,第三章 - 95,3.3 基于搜索的优化问题,模拟退火算法伪码：,Simulated-Annealing() Create initial solution S repeat for i=1 to iteration-length do Generate a random transition from S to Si If ( C(S) random0,1) ) then S=Si Reduce Temperature t until ( no change in C(S) ) C(S): Cost

39、or Loss function of Solution S.,启发式搜索,第三章 - 96,3.3 基于搜索的优化问题,模拟退火算法举例（8 Queens）,Solution Encoding,启发式搜索,第三章 - 97,3.3 基于搜索的优化问题,模拟退火算法举例（8 Queens）,Energy,The energy of a solution is defined as the number of conflicts that arise given an encoding. The goal is to find an encoding that exhibits energy o

40、f zero, or no conflicts on the board.,启发式搜索,第三章 - 98,3.3 基于搜索的优化问题,模拟退火算法举例（8 Queens）,Temperature Schedule,启发式搜索,第三章 - 99,3.3 基于搜索的优化问题,模拟退火算法举例（8 Queens）,Procedure N-Queens-SA:begin init-of-T; T为初始温度S=1，n; S为初始值termination=false;while termination=falsebegin for i=1 to L dobegingenerate(Sform S); 从当

41、前回路S产生新回路St:=f(S)-f(S);f(S)为路径总长IF(tRandom-of-0,1)S=S;IF the-halt-condition-is-TRUE THEN termination=true;End;T_lower;End;End,启发式搜索,第三章 - 100,3.3 基于搜索的优化问题,模拟退火算法举例（假定有40个皇后）,启发式搜索,第三章 - 101,3.3 基于搜索的优化问题,遗传算法（Genetic Algorithms,GAs） 基于对生物遗传和进化过程的计算机模拟。 基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的自适应全局优化概率搜索算法(以字符串表

42、示状态空间)。,转载 兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。,启发式搜索,第三章 - 102,3.3 基于搜索的优化问题,遗传算法（Genetic Algorithms,GAs）,自然界,染色体,基因,等位基因(allele),基因座(locus),基因型(genotype),表现型(phenotype),遗传算法,字符串,字符，特征,特征值,字符串位置,结构,参数集，译码结构,启发式搜索,第三章 - 103,Genetic algorith

43、m high-level flow,Creating the initial population,染色体编码示例：01010010100101001111,启发式搜索,第三章 - 104,3.3 基于搜索的优化问题,遗传算法（Genetic Algorithms,GAs） 例如：迷宫问题,1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 8, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1

44、, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 5, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,启发式搜索

45、,第三章 - 105,3.3 基于搜索的优化问题,遗传算法（Genetic Algorithms,GAs） 例如：迷宫问题 染色体编码,111110011011101110010101,3, 3, 2, 1, 2, 3, 2, 3, 2, 1, 1, 1,例如：,启发式搜索,第三章 - 106,Genetic algorithm high-level flow,fitness is then computed,启发式搜索,第三章 - 107,Genetic algorithm high-level flow,chromosomes are selected for propagation to

46、 future populations,Roulette-wheel selection,启发式搜索,第三章 - 108,Genetic algorithm high-level flow,mutation and crossover, generate next generation,启发式搜索,第三章 - 109,3.3 基于搜索的优化问题,遗传算子 交叉（Crossover） The crossover operator takes two chromosomes, separates them at a random site (in both chromosomes) and then swaps the tails of the two, resulting in two new chromosomes.,启发式搜索,第三章 - 110,3.3 基于搜索的优化问题,遗传算子 变异（Mutation） The