第3章 搜索策略 本章学习目标 ● 理解搜索的基本概念。 ● 掌握盲目搜索算法:深度优先搜索和宽度优先搜索。 ● 掌握启发式搜索算法:A搜索和A*搜索。 ● 掌握局部搜索算法:爬山法、模拟退火法和遗传算法。 人们在求解许多问题时都采用试探的搜索方法,希望尽可能找到一个令人满意的解。 例如,童年时代玩华容道游戏以及八数码问题等智力游戏,就是一个不断尝试和探索的搜索 过程。当我们终于找到了一种解决办法,又会想:这个方案所用的步骤是否最少? 即是不 是最优方案。若不是,怎样才能找到最优方案? 如何用计算机代替人类完成这样的搜索? 为模拟这些试探性的问题求解过程而发展的一种技术就称为搜索技术。 搜索技术是人工智能中的一个核心技术,它直接关系到智能系统的性能和运行效率。 以2.已知智能体的初始状态和目标 4节中介绍的状态空间表示法描述所求解的问题空间, 状态,搜索问题就是求解一个操作序列,使得智能体能从初始状态转移到目标状态,搜索问 题的主要任务是找到正确的搜索策略。搜索策略是指在搜索过程中确定扩展状态顺序的规 则。所求得的从初始状态转移到目标状态的一个操作序列就是问题的一个解,若某操作序 列可以使总代价最低,则该方案称为最优解。 本章将首先介绍图搜索策略的概念,然后介绍盲目搜索的两种典型算法(深度优先搜 索、宽度优先搜索)和启发式搜索的两种典型算法(A搜索、A*搜索), 最后介绍局部搜索的 三种算法(爬山法、模拟退火法、遗传算法)。 3.图搜索策略 1 很多搜索问题都可以转化为图搜索问题,即在图结构中搜索该问题的解决方案。为了 进行搜索,首先需要采用某种形式表示所要求解的问题,表示方法是否适当将直接影响搜索 效率。一般常用状态空间表示法描述所求解的问题空间。然后在状态空间中搜索,以求得 一个从初始状态到目标状态的操作算子序列,即问题的解。对于一个确定的问题,与求解有 关的状态空间往往只是整个状态空间的一部分,只要能生成并存储这部分状态空间,就可求 得问题的解。 在状态空间图中,求解一个问题就是从初始状态出发,不断运用可使用的操作,在满足 约束的条件下达到目标状态,故搜索技术又称为“状态图搜索”方法。通过图搜索求解问题 的基本过程如下。 (1)采用状态空间表示法描述所有状态的一般表示,并给出问题的初始状态和目标 状态。 (2)规定一组操作(算子), 每个操作(算子)都能够将一个状态转换到另一个状态。 (3)选择一种搜索策略,用于遍历或搜索该问题的状态图空间。 (4)将问题的初始状态(即初始节点)作为当前状态。 (5)按已确定的搜索策略选择适用的操作(算子), 对当前状态进行操作,生成一组后继 状态(或称为后继节点、子节点)。 (6)检查新生成的后继状态中是否包含目标状态。若包含,则搜索到了问题的解,从初 始状态到达目标状态的操作序列即为解,算法结束;若不包含,则按已确定的搜索策略,从已 生成的状态中选择一个状态作为当前状态,若已无可操作的状态,则未搜索到解,算法结束。 (7)返回至第(5)步。 例如,4节中介绍的八数码问题,八数码的所有摆法构成了状态集合S,已知初始状态 2. 和目标状态,搜索一个从初始状态到达目标状态的操作序列,即为八数码问题的一个解。 在实现图搜索的算法中,需建立两个数据结构:OPEN 表和CLOSED 表。OPEN 表用 于存放待扩展的节点,CLOSED 表用于存放已扩展的节点。所谓扩展节点,是指用合适的 操作(算子)对该节点进行操作,生成一组后继节点。一个节点经过一个算子操作后,一般只 生成一个后继节点,但对于一个节点,适用的算子可能有多个,故此时会生成一组后继节点。 需要注意的是:在这些后继节点中,可能包含当前节点的父节点、祖父节点,则这些祖先节 点不能作为当前节点的子节点。图搜索不允许重复访问节点,即OPEN 表和CLOSED 表 的交集为空。图搜索策略就是选择下一个被扩展节点的规则。 基于状态空间图的搜索算法的步骤如下。 (1)初始化,将OPEN 表和CLOSED 表置空。 (2)将初始节点 S 放入OPEN 表中,并建立目前只包含 S 的搜索图Graph。 (3)检查OPEN 表是否为空,若为空,则问题无解,算法结束;否则执行下一步。 (4)将OPEN 表的第一个节点(记为n)取出,放入CLODED 表中。 (5)若节点 n 就是目标节点,则已求得问题的解,此解可从目标节点追溯到初始节点的 前驱指针链得到,算法结束;否则继续执行下一步。 (6)扩展节点n,若 n 没有后继节点,则转到步骤(3); 否则生成 n 的一组子节点,将其 中不是 n 祖先的那些子节点记作集合 M ={mi}, 并将所有mi 作为节点 n 的子节点加入图 Graph中。 (7) M 中的节点mi分为三类,需分别处理:第一类是既不包含于OPEN 表,也不包含 于CLOSED 表中的节点,记为{mj}, 设置其前驱指针指向节点n(即令节点 n 成为mj 的父 节点), 并将{mj}放入OPEN 表中;第二类是包含于OPEN 表中的节点,记为{mk }, 检查是 否需要修改它指向父节点的前驱指针;第三类是包含在CLOSED 表中的节点,记为{ml }, 检查是否需要修改其后继节点指向父节点的前驱指针。 (8)按某种搜索策略对OPEN 表中的节点进行排序。 (9)返回至第(3)步。 通常有两种方式的搜索策略:一种是在不具备任何与给定问题有关的知识或信息的情 况下,系统按照某种固定的规则依次或随机地调用操作算子,这种搜索方法称为盲目搜索策 略(blindsearchstrategy), 又称为无信息引导的搜索策略(uninformedsearchstrategy); 另 一种是可应用与给定问题有关的领域知识,动态地优先选择当前最合适的操作算子,这种搜 索方法称为启发式搜索策略(huitcsactaegy) ifrme searchstrategy )。 ersierhsrt或有信息引导的搜索策略(nod 不同搜索策略的搜索性能也不同。搜索策略性能的评价标准包括完备性和最优性。当 问题有解时,若搜索算法保证能找到一个解,则称该搜索算法具有完备性,否则称之为不完 备。当问题有最优解时,若搜索算法保证能找到一个最优解(即最小代价路径), 则称该搜索 算法具有最优性,否则称之为不具有最优性。 3.盲目的图搜索策略 2 在盲目搜索的过程中,没有任何与问题有关的先验知识或者启发信息可以利用,算法只 能判断当前状态是否为目标状态,而无法比较两个非目标状态的好坏。 深度优先搜索和宽度优先搜索是常用的两种盲目搜索算法,它们是采用同一种搜索策 略的不同搜索算法,节点在OPEN 表中的排列顺序是不同的,所以不同搜索算法的区别仅 在于扩展节点的顺序不同。 3.1 深度优先搜索 2. 深度优先搜索(depth-firstsearch,DFS)的基本思想是:优先扩展深度最深的节点。在 一个图中,初始节点的深度定义为0,其他节点的深度定义为其父节点的深度加1。 深度优先搜索总是选择深度最深的节点进行扩展,若有多个相同深度的节点,则按照指 定的规则从中选择一个;若该节点没有子节点,则选择一个除了该节点之外的深度最深的节 点进行扩展。依此类推,直到找到问题的解为止;或者直到找不到可扩展的节点,结束搜索, 此种情况说明没有找到问题的解。 在编程实现深度优先搜索算法时,采用栈(即先进后出的线性表)作为OPEN 表的数据 结构。深度优先搜索算法将OPEN 表中的节点按其深度的降序排序,深度最大的节点总是 排在栈顶,深度相同的节点可按某种事先约定的规则排列。 深度优先搜索算法的过程如下。 (1)将初始节点 S 放入OPEN 表的栈顶。 (2)若OPEN 表为空,表示再也没有可扩展的节点,即未能找到问题的解,则算法 结束 ( 。 3)将OPEN 表的栈顶元素(记为节点n)取出,放入CLOSED 表中。 (4)若节点 n 是目标节点,则已求得问题的解,算法结束。 (5)若节点 n 不可扩展,即 n 没有后继节点,则转至步骤(2)。 (6)扩展节点n,将其所有未被访问过的子节点依次放入OPEN 表的栈顶,并将这些子 节点的前驱指针设为指向父节点n,然后转至步骤(2)。 深度优先搜索一直选择深度最深的节点进行扩展,对于状态空间有限的问题,深度优先 搜索是完备的,因为它最多扩展所有节点,直到找到一个解。但在无限状态空间中,若沿着 一个“错误”的路径搜索下去而陷入“深渊”,则会导致无法到达目标节点,在这种情况下,深 度优先搜索是不完备的。为避免这样的情况,在深度优先搜索中往往会加上一个深度限制, 称为深度受限的深度优先搜索,即在搜索过程中,若一个节点的深度达到了事先指定的深度 阈值k,无论该节点是否有子节点,都强制进行回溯,选择一个比它浅的节点进行扩展,而不 是沿着当前节点继续扩展。深度受限的深度优先搜索相当于假定深度为 k 的节点没有后 继节点,其余的操作与深度优先搜索相同。如此一来,又可能因为深度限制过浅而找不到 解。例如,假设所求解问题的解在深度为6的层次,但将深度限制设为4,就会找不到解。 所以,应该根据具体问题合理地设定深度限制值,或在搜索过程中逐步加大深度限制值,反 复搜索,直到找到解。 下面以八数码问题为例,介绍深度受限的深度优先搜索的过程。 例3.假设有八数码问题的初始状态如图3.a) 要求采用深度优先搜索算法找 1 1(所示, 到图3.1(b)所示的目标状态。 图3.八数码问题的一个实例 1 假设规定空白格的操作依次按向左、向上、向右、向下的顺时针顺序进行深度优先搜索, 深度限制为4,则会形成图3. 2所示的八数码问题的部分状态空间。其中圆圈里的数字编号 表示访问节点的顺序,其间仅扩展了编号为1、2、3、4、7、8、11 、12 、13 的节点。因为深度限制 为4,在深度为4的层上的节点5、6、9、10 均不被扩展。当判断出其为非目标状态时,直接 回溯到上一层,当搜索到节点14 时,判断出其为目标状态,算法结束。 在深度优先搜索过程中,可能会遇到“死循环”情况,即在一个环路中重复搜索而跳不出 来。为避免这种情况,可以在搜索过程中记录从初始节点到当前节点的路径上每个被扩展 的节点;然后,每遇到一个节点,就先检测该节点是否已出现在这条路径上:若未出现,则扩 展它;若已出现过,则采用其他合理操作形成节点,若无合理操作,则强制回溯到该节点的上 一层。例如,在图3.按规定, 则出现与节点3相 2中节点4的状态时, 空白格应先向左移动, 同的状态,这时DFS 算法检测出:节点3已出现在从节点1到节点4的路径上,就会换下一 个合理的操作:向右移动,形成子节点5。由于深度限制为4,虽然节点5不是目标状态,也 不再扩展它,而是强制回溯到上一层的节点4,探索节点4的下一个合理的空白格操作:向 下移动,形成子节点6。基于同样的原因,不再扩展节点6,回溯到节点4,此时已尝试完成 节点4所有合理的空白格操作,只能回溯到上一层节点3,以此类推。 除初始节点外,每个节点的前驱指针均被设置为指向其父节点,当找到目标节点后,依 次沿着路径上每个节点的前驱指针可反向追踪到初始节点,即得到问题的解。例如,在 图3.采用深度限制为4的深度优先搜索算法求解八数码问题的搜索图 2 图3.从目标节点14 开始, 得到路径14→13→12→11→ 2中, 依次追溯各个节点的前驱指针, 1,将该路径反向输出,1中八数码问题的解为1→11→12→13→14 。 即可得到图3. 深度优先搜索不具有最优性,因为它无法避免冗余路径。如图3.从节点1出 2所示, 发,扩展其左子树上的所有节点,都是冗余路径,事实上,从节点1出发,依次扩展其右子树 上的节点11 、12 、13,仅需4步即可找到目标节点14 。若不设置深度限制,则可能经过更多 的冗余路径,而且还可能陷入“深渊”,导致无法到达目标节点。 3.2 宽度优先搜索 2. 宽度优先搜索也称为广度优先搜索(breadth-firstsearch,BFS), 其基本思想是:优先扩 展深度最浅的节点。先扩展根节点,再扩展根节点的所有后继,然后再扩展它们的后继,以 此类推。如果有多个节点深度是相同的,则按照事先约定的规则,从深度最浅的几个节点中 选择一个,进行扩展。 在编程实现宽度优先搜索算法时,采用队列(先进先出的线性表)作为OPEN 表的数据 结构。宽度优先搜索将OPEN 表中的节点按节点深度的增序排列,深度最浅的节点排在 OPEN 表的队头,新节点(深度比其父节点深)总是插入OPEN 表的队尾,深度相同的节点 可按某种事先约定的规则排列,这意味着浅层的老节点会在深层的新节点之前被扩展。宽 度优先搜索算法的过程如下。 (1)将初始节点 S 放入OPEN 表的队头。 (2)若OPEN 表为空,表示再也没有可扩展的节点,即未能找到问题的解,则算法结束。 (3)将OPEN 表的队头元素(记为节点n)取出,放入CLOSED 表中。 (4)若节点 n 是目标节点,则已求得问题的解,算法结束。 (5)若节点 n 不可扩展,即 n 没有后继节点,则转至步骤(2)。 (6)扩展节点n,将其所有未被访问过的子节点依次放入OPEN 表的队尾,并将这些子 节点的前驱指针设为指向父节点n,然后转至步骤(2)。 可见,宽度优先搜索与深度优先搜索的唯一区别是:宽度优先搜索是将节点 n 的子节 点放入OPEN 表的尾部,而深度优先搜索是将节点 n 的子节点放入OPEN 表的首部。仅 此一点不同,就使得搜索的路线完全不同。 例3.采用宽度优先搜索算法求解图3. 2 1中的八数码问题。假设规定空白格的操作 依次按向上、向右、向左的顺时针顺序进行宽度优先搜索,3所示。圆 向下、则搜索图如图3. 圈里的数字编号表示访问节点的顺序,其间仅扩展了编号为1~15 的节点。 图3.采用宽度优先搜索算法求解八数码问题的搜索图 3 宽度优先搜索是完备的。若路径代价是节点深度的非递减函数,或者每步代价都相等, 那么宽度优先搜索还具有最优性。因为宽度优先搜索总是在扩展完第 k 层的所有节点后 才去扩展第k+1 层的节点,所以,若问题有解,宽度优先搜索一定能找到最小代价的解,即 最优解。例如,在八数码问题中,如果移动每个数码牌的代价都相同,假设代价都计为1,则 采用宽度优先搜索算法找到的解一定就是移动数码牌次数最少的最优解。但由于宽度优先 搜索在搜索过程中需保存已访问的所有节点,则运行该算法需要占用较大的存储空间,而且 随着搜索深度的加深,存储空间呈几何级数增加。 与宽度优先搜索相比,深度优先搜索算法所需的存储空间要小得多,因为它只需存储从 初始节点到当前节点的一条路径即可,其所需存储空间与搜索深度呈线性关系。所以,深度 优先搜索的优点是节省大量的时间和空间。 在不要求求解速度且目标节点的层次较深的情况下,BFS 优于DFS,因为BFS 一定能 够求得问题的解,而DFS 在一个扩展得很深但又没有解的分支上进行搜索,是一种无效搜 索,降低了求解的效率,有时甚至还不一定能找到问题的解。在要求求解速度且目标节点的 层次较浅的情况下,DFS 优于BFS,因为DFS 可快速深入较浅的分支,找到解。 3.启发式图搜索策略 3 3.2节介绍的两种搜索算法都属于盲目搜索策略,它们采用固定的搜索模式,不针对具 体问题。盲目搜索策略在选择要被扩展的节点时,没有利用所求解问题的任何先验信息,既 不对待扩展的状态的优劣进行判断,也不考虑所求的解是否为最优解。但很多时候,人类对 两个状态的优劣是要进行判断的。例如,在图3.以节点①为初始状态, 4中, 我们会优先选 择节点⑤进行扩展,因为在节点⑤上仅需移动一次空白格即可到达目标节点;若先扩展节点 ②,目测看不出来是否能到达目标节点,即使能找到解,也一定不是最优解。可见,盲目搜索 策略会导致所需扩展的节点数很多,产生很多无用的节点,搜索效率较低。 启发式搜索是将人类解决问题的“知识”告诉机器,即启发式信息(heuristicinformation), 使搜索算法能够利用启发式信息更“聪明”地搜索,尽可能地缩小搜索范围,减少试探的次 数,提高搜索效率,避免大海捞针。 图3.八数码问题中节点⑤比节点①的状态好 4 启发式搜索策略的基本思想是在搜索过程中利用与所求解问题有关的特征信息,指导 搜索向最有希望到达目标节点的方向前进。启发式搜索的每一步都选择最优的操作,以最 快速度找到问题的解。一般只需要知道问题的部分状态空间就可求解该问题,搜索效率较 高。本节介绍两种常用的启发式搜索算法:A搜索和A*搜索。 3.1 A 搜索 3. 为了尽快找到从初始节点到目标节点的一条代价比较小的路径,在搜索的每一步,我们 都希望选择在最佳路径(即代价最小的路径)上的节点进行扩展,但如何估算一个节点在最 佳路径上的可能性呢?A搜索采用评价函数来计算: f(g(n) n)=n)+h( 其中, n 为待评价的节点,如图3.n) h(n) 5所示,g(为从初始节点 S 到节点 n 的最佳路径上代价 的实际值,为从节点 n 到目标节点 E 的最 佳路径上代价的估计值,称为启发函数,n) f(为 从初始节点 S 出发、经过节点 n 到达目标节点 E 的最佳路径上代价的估计值,称为评价函数。这 里的路径代价,可以是路径长度、经历的时间或 花费的费用等。当h(n)=0时,说明已到达目 标节点。 A搜索是一种贪心算法,其核心思想是:每 5 一步都选择距离目标最近的节点进行扩展。A 图3.评价函数的组成 搜索的策略为:设计一个评价函数f(将所有待评价的节点按评价函数值f(的升序 n), n) 排列,存放在OPEN表中(采用队列作为数据结构),然后选择评价函数f(n)值最低的节点 作为下一个将要被扩展的节点。由于最佳节点总是排在OPEN表的队首,因此A搜索又称 为最佳优先搜索(bestfirstsearch)。 在评价函数f(n)=g(n) 当f(g(即h(=0时, n)+h(中, n)=n), n)A搜索就退 化为盲目搜索。当f(n)=节点 n 在搜索树上的深度时,则A搜索成为宽度优先 n)=g( 搜索。当f(n)=h(n)0时, retfrtsac n),即g(=称为贪婪最佳优先搜索(gedybs-iserh, GBFS),简称贪婪搜索。贪婪最佳优先搜索是最佳优先搜索的特例,它的评价函数仅使用 启发函数h(n)对节点进行评价,其搜索策略是:在每一步,它总是优先扩展与目标最接近 的节点。贪婪搜索策略不考虑整体最优,仅求取局部最优。贪婪搜索是不完备的,也不具有 最优性,但其搜索速度非常快。 例3.采用A搜索求解八数码问题。 3 n), n) 在搜索树中的深度;启发函数h( n)= 首先,需要设计评价函数f(其中g(一般定义为已移动数码牌的步数,即节点 n n)定义如下: h( h(错位数码牌的个数 统计目前所在位置与目标位置 n)的含义是:将待评价的状态与目标状态进行比较, 不同的数码牌的个数,称为错位数码牌的个数,该数值基本上可以反映当前节点与目标节点 的距离。 6中的初始状态与目标状态进行比较, 2、 将图3.发现1、8三个数码牌不在其应该在的 位置上,则错位数码牌的个数为3, n)=3, n) 则f(=3。 即h(初始状态的g(值为0, n) 然后,将空格块依次向左、向下、向右移动,按照上述方法计算各个状态的 h 值和 f 值。 用A搜索求解八数码问题的搜索图如图3.其中 g 的值表示已移动数码牌的步数, 6所示, 从初始状态往下, g 值依次为1~5,即表示该节点在搜索树上的深度。每个节点上面都标 图3.采用 A 搜索解决八数码问题示例 6 注了该状态的 g 值和 h 值,左边的“字母(数值)”表示“状态名称( f 值)”,圆圈中的数字表 示该节点被扩展的顺序,不带圆圈数字的状态表示该节点未被扩展。可见,在搜索的过程 中,只有状态S、A、B、C、D、I、O、P被依次扩展了,因为它们的 f 值在当时情况下最小,而其 他节点的 f 值不是最小,便没有被扩展的机会。直到找到目标节点Q,算法结束,该解的路 径代价为5。 6的搜索过程可知:计算f(其中g( 从图3.n)是实现A搜索的关键, n)是从初始节点 S 到当前节点 n 路径上的代价值,很容易通过已搜索过的路径计算得到。而启发函数h( 则需要根据所求解问题的定义设计。针对同一个待求解问题,可以定义不同的启发函数 n) 。 因此,选取一个好的启发函数h(则有可能找 n)是保证找到最优解的关键。如果选择不当, 不到问题的解,即使能找到解,也不一定是最优解。这时,A搜索是不完备的,也不具有最 优性。 3.搜索 3.2 A* 在A搜索中,由于对启发函数未做出任何限制,所以不好评价A搜索求得的结果。我 们发现:当评价函数中只包含g(时, 若在评价函数中加入“一点”启发信 n) 属于盲目搜索; 息h(n), 搜索效率就会提高; n)过大, n), 导致脱离实际情 但如果启发函数h(则会忽略g( 况,反而不能保证总能找到最优解了。因此,需要对启发函数加以限制,这就是本节要介绍 的A*搜索。 n)定义为从当前状态 n 到目标状态的最佳路径上的实际代价,即最小代价。可以h*( n)满足条件h(( 证明:如果启发函数h(n)≤h*n), 则当问题有解时,A搜索一定能找到 一个代价值最小的解,即最优解。满足该条件的A搜索称为A*搜索。A*搜索是最佳优先 搜索的最广为人知的形式,也称为最佳图搜索算法。 一般来说,(那么如何判断h((这就要根据具 h*n)是未知的, n)≤h*n)是否成立呢? 体问题分析了。例如,所求问题是在地图上找到一条从地点A到地点B的距离最短的路 径,可以采用当前节点到目标节点的欧氏距离作为启发函数h()。虽然不知道h*n)是 因此,( n 肯定有h( ( ( 什么,但由于两点之间直线距离最短, 无论怎样定义h*n), n)≤h*n)。 只要满足此限定条件,就可以用A*搜索找到该问题的一条最优路径。A*搜索与A搜索没 有本质区别,只是规定了启发函数的上限。A*搜索既是完备的,也是最优的。 ()。假设h*( 下面证明例3.3中的启发函数满足限定条件h(n)≤h*nn)定义为:将 当前状态中所有错位的数码牌移动到其正确位置所需的最少的实际步数。令 w(节点 n 所表示的状态中错位数码牌的个数 n) n)= 至少需要移动 w ( 则若要将w(个错位的数码牌放在其各自的目标位置上, n)步,显然有 n)≤h*(选择w(n), n)≤h*n), )。现在, 作为启发函数h(则有h((满 足对h(当选择h(错位数码牌的个数”作为启发函数时,A搜 w(nn) n)=w( n)上界的要求。因此, n)=“ 索就是A*搜索。 例3.传教士与野人渡河问题。在河的左岸有 K 个传教士、 K 个野人和1条船,传教 4 士们想用这条船将所有成员都从河左岸运到河右岸去,但有下面的条件和限制: (1)所有传教士和野人都会划船。 (2)船的容量为r,即一次最多运送 r 个人过河。 (3)任何时刻,在河的两岸以及船上的野人数目不能超过传教士的数目,否则野人将吃 掉传教士。 (4)允许在河的某一岸或船上只有野人而没有传教士。 (5)野人会服从传教士的任何过河安排。 请采用A*搜索出一个确保全部成员安全过河的合理方案。 若想解决传教士与野人渡河的问题,首先需要确定问题的表示方法,仍然采用状态空间 表示法;然后设计状态空间、操作算子集合、满足A*搜索的启发函数;最后用定义好启发函 数的A*搜索搜索合理的过河方案。 第一步:设计状态空间表示。 此问题中包括3类对象:传教士、野人和船,采用三元组形式表示一个状态,令S=(m, c,b), 其中: ● m 为未过河的传教士人数,m∈[0,K], 已过河的传教士人数为 K -m 。 c∈[- c ● c 为未过河的野人数,0, K ], 已过河的野人数为 K 。 b∈[ ● b 为未过河的船数,0,1], 已过河的船数为1b。 初始状态为S0=( K , K ,1), 表示全部成员及船都在河的左岸,目标状态为Sg =(0,0, 0), 表示全部成员及船都已到达了河右岸。 56 第二步:设计操作集合。 根据题意,设计两类操作算子,令Lij操作表示将船从左岸划向右岸,第一下标i 表示船 载的传教士人数,第二下标j 表示船载的野人数;令Rij操作表示将船从右岸划回左岸,下标 的定义同前。这两类操作需满足如下限制:(1)1≤i +j≤r;(2)i ≠0时,i ≥j。 假设K =5,r =3,则合理的操作共有16种,其中船从左岸到右岸的操作有:L01、L02、 L03、L10、L11、L20、L21、L30;船从右岸到左岸的操作有:R01、R02、R03、R10、R11、R20、R21、R30。 第三步:设计满足A* 搜索的启发函数。 若不考虑“野人会吃传教士”的限制,每次3个人(不区分传教士和野人)从左岸到右岸 摆渡过河,然后1个人将船从右岸划回左岸,则至少要单程摆渡9次,这相当于1个人固定 作为船夫,每摆渡一次,只运送1个人过河(即往返一趟,运送2个人过河)。 定义启发函数为:将当前状态下未过河的m 个传道士和c 个野人全部运送到河右岸, 至少需要摆渡的趟数。那么,是否可以令h(n)=m +c 呢? 分析后发现:不可以。因为 h(n)=m +c 不满足h(n)≤h* (n)的条件。例如:对于状态n (1,1,1),h(n)=m +c= 2,而此时最短路径上的实际代价h* (n)=1,即只需1趟摆渡即可完成。而此刻,h* (n)= 10,说明新状态比当前状态要好,则接受该移动,并用 新状态代替当前状态;否则,若ΔE≤0,说明新状态比当前状态要差,模拟退火法并不会像 r 爬山法一样丢弃这个新状态,而是以某个小于1的概率 P =eΔE/(T)接受“变坏”的新状态。 直到温度 T 降至0,返回当前状态作为一个解,算法结束。 在模拟退火法刚开始时,温度 T 较高,接受“变坏”的后继状态的概率较大,随着时间的 推移, T 逐渐下降,算法接受一个“变坏”的后继状态的概率就越来越小。可见,接受“变坏” 移动的概率是随着“温度” T 的降低而下降的。如果调度使温度 T 下降得足够慢,那么模拟 退火法找到全局最优解的概率就可以接近于1。 即可 采用模拟退火法求解八皇后问题 。 h(n) ,关键是设计启发函数 n。 ) 选择启发函数 3.1h) (n)=相互 lue攻击的皇后对的数量,值越小,说明状态越好。用h(代替公式(中的Va 模拟退火法是一种通用的优化算法,理论上讲,该算法具有概率接近1的全局优化性 能。模拟退火法在20世纪80年代早期被广泛用于求解大规模集成电路(verylargescale integrationcircuit,VLSI)布局问题。目前它已经广泛地应用于VLSI 、生产调度、控制工程、 机器学习、神经网络、信号处理等领域的最优化任务中。 3.3 遗传算法 4. 20世纪60年代末,美国密歇根大学的约翰·霍兰德(JohnHoland)教授受达尔文“物 竞天择,适者生存”进化论思想的启发,提出了模拟自然选择和遗传学机理的生物进化过程 的计算模型,通过模仿自然进化过程来搜索复杂问题的最优解,这就是求解优化问题的遗传 算法(geneticalgorithm,GA )。 遗传算法是一种启发式随机搜索算法,它通过数学的方式,利用计算机仿真运算,模仿 生物遗传和进化过程中的染色体基因选择、交叉、变异机理,来完成自适应搜索问题最优解 的过程。求解较为复杂的组合优化问题时,遗传算法通常能比一些常规优化算法更快地获 得较好的优化结果。自从20世纪80年代起,遗传算法已成为研究热点,被人们广泛地应用 于组合优化、机器学习、信号处理、生产调度问题、图像处理、自动控制和人工生命等领域。 3.3.遗传算法的基本概念 4.1 在遗传算法中,后继节点是由两个父辈状态组合生成的,而不是对单一状态修改而得到 的。其处理过程是有性繁殖,而不是无性繁殖。 遗传算法借鉴生物进化中“适者生存”的理论,定义了如下一些术语。 (1)个体(l):个体就是遗传算法要处理的染色体,组成染色体的元素称为基 individua 因。染色体中的每一位就是一个基因,基因的位置称为基因座,基因的取值称为等位基因。 基因决定了染色体的特征,也决定了个体的性状,如眼睛的颜色是黑色、栗色或者蓝色等。 (2)种群(population):种群是由若干个个体(即染色体)组成的集合。一个种群中个 体的个数称为该种群的规模。种群规模会影响遗传优化的结果和效率。大的种群中含有丰 富的个体模式,可以改进遗传算法的搜索质量,防止早熟收敛(算法较早地收敛于局部最优 解,称为早熟收敛)。但大的种群也增加了个体适应度函数的计算量,从而降低了收敛速度。 一般种群规模选取在[20,100]的值。 (3)适应度(ins)用一个估计 fte:适应度是指个体对环境的适应程度。在优化问题中, 函数来度量个体的适应度,这个函数称为适应度函数。适应度函数值是遗传算法实现优胜 劣汰的主要依据。个体适应度的值越大,说明该个体的状态越好,竞争能力越强,被选择参 与遗传操作来产生新个体的可能性就越大,以此体现生物遗传中适者生存的原理。 3.3.编码 4.2 对一个要应用遗传算法求解的具体问题,首先要考虑的问题就是如何编码,因为遗传算 法不能直接处理问题空间的数据,必须通过编码将要求解的问题表示成遗传空间的染色体 或个体。在计算机中,染色体被表示为一个用来描述基本遗传结构的数据结构。尚不存在 一种针对所有问题都适合的通用编码方法,往往需要具体问题具体分析,选择最适合的方 法。下面介绍3种常用的编码方法。 (1)二进制编码。 二进制编码就是用一个二进制的字符串表示一个个体,其中每个0或1为等位基因。 染色体上由若干个基因构成的一个有效信息段称为基因组。例如,11011为一个染色体,每 一位上的0或1表示基因,前3个基因就构成了一个基因组110 。 二进制编码使得交叉、变异等遗传操作易于实现,但在求解高维优化问题时,二进制编 码串会很长,将导致遗传算法的搜索效率很低。 (2)实数编码。 为了克服二进制编码的缺点,在问题变量是实向量的情况下,可直接采用十进制编码, 即为实数编码。实数编码就是用一个十进制的字符串表示一个个体,然后在实数空间上进 行遗传操作。采用实数编码,则不必进行数制转换,便于引入与问题领域相关的启发式信息 来增加算法的搜索能力。近年来,遗传算法在求解高维或复杂优化问题时,一般都采用实数 编码。 (3)有序编码。 有序编码也叫序列编码、排列编码,是针对一些特殊问题的特定编码方式。该编码方式 排列有限集合内的元素。若集合内包含 m 个元素,则存在m! 种排列方法,当 m 不大时, m!也不会太大,采用穷举法就可以解决问题。当 m 比较大时,m!就会非常大,穷举法失 效,遗传算法在解决这类问题上具有优势。 针对很多组合优化问题,目标函数的值不仅与表示解的字符串中各字符的值有关,而且 与其所在字符串中的位置有关。这样的问题称为有序问题。若目标函数的值只与表示解的 字符串中各字符的位置有关,而与具体的字符值无关,则称为纯有序问题,如八皇后问题。 有序编码的优点是使问题简洁,易于理解,编码自然、合理。 3.3.种群设定 4.3 由于遗传算法是对种群进行操作的,因此需要为遗传操作构造一个由若干个个体组成 的初始种群。初始种群中的个体一般是随机产生的。假设设定种群规模为 M ,首先随机生 成一定数目(通常为2M )的个体,然后从中挑选较好的 M 个个体,构成初始种群。 3.3.适应度函数的设计 4.4 适应度函数的设计直接影响遗传算法的收敛速度以及能否找到最优解,因为遗传算法 在进化搜索中基本不利用外部信息,仅根据适应度函数来评价种群中每个个体适应性的优 劣。在遗传算法中,适应度函数值规定为非负,并且在任何情况下都希望其值越大越好。在 具体应用中,适应度函数的设计要结合待求解问题本身的要求而定。一般而言,适应度函数 是由待求解优化问题的目标函数变换得到的。 若问题的目标函数f(x)为最大化问题,则适应度函数可以取为 Fit(x))f((2) f(=x)3. 若问题的目标函数f(x)为最小化问题,则适应度函数可以取为 Fit(x))=f(x) (3. f (1/3) 3.3.遗传操作 4.5 遗传操作(geneticoperator)可作用于种群,用于产生新的种群。标准的遗传操作一般 包括以下3种基本形式:选择、交叉及变异。 selectioreproductio (1)选择(n)操作,也称为复制(n), 是从当前种群中按照一定概率选 出的优良个体,使它们有机会作为父代繁殖下一代。选择操作的目的是使种群优胜劣汰、不 断进化,并且提高种群的收敛速度和搜索效率。根据个体的适应度值来判断其优劣,适应度 值越高,越具有优良性,该个体被选择的机会就越大,显然这一操作借鉴了达尔文“适者生 存”的进化原则。优胜劣汰的选择机制使得适应度值大的个体具有较高的存活概率,这是遗 传算法与一般搜索算法的主要区别之一。 实现选择操作的方法有很多,不同的选择策略对算法的性能也有较大的影响。最常用 的选择方法称为“轮盘赌”方法,它按照适应度比例模型(也称为蒙特卡洛法)计算个体被选 择的概率,设种群规模大小为 M ,个体 i 的适应度值为fi,则这个个体被选择的概率为 Pi= fi (4) 3. fjΣ(M) j=1 每个个体被选择的概率与其适应度值成正比。如表3.4) 第2行给出了6个个体 1所示, 的适应度值,第3行是根据公式(3.计算出的每个个体的选择 概率,总和为1,第4行是前 i 个个体的累计概率。在轮盘选择 方法中,先按个体的选择概率产生一个轮盘,1中列 假设有表3. 出的6个个体,故轮盘分为6个区域, 13 所示, 如图3.每个区域 代表一个个体,其大小与该个体的选择概率成正比,即第 i 个 扇形的中心角为2πPi;然后产生一个位于[0,1]的随机数,它 落入轮盘的哪个区域,就选择该区域所对应的个体,进行交叉。 13 图3.轮盘赌示意图 显然,选择概率大的个体所对应的区域面积也大,该个体被选 中的可能性就大,获得交叉的机会也大。 65 实现选择操作时,产生了一个随机数 r 后,若p1+p2+…+pi-1< r