《人工智能技术及应用》课件-第9章问题求解单元-搜索技术

时间：2020-9-8问题求解单元——搜索技术第09章启发式搜索盲目搜索9.19.2搜索的概念搜索的目的：利用已有的知识一步步的摸索着，求解现实世界中的大多数的非结构化问题这就是搜索。搜索技术：利用计算机来求出问题的解的一种方法寻求问题解答的技术,

搜索技术是人工智能的一个重要内容。9.1盲目搜索盲目搜索，也称无信息搜索，即只按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。深度优先搜索9.1.1宽度优先搜索9.1.2回溯搜索9.1.39.1盲目搜索深度优先搜索是一个针对图和树的遍历算法，其早在19世纪就被用于解决迷宫问题，是一个与问题无关的通用方法。对于右图，深度优先搜索首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。深度优先搜索1深度优先搜索深度优先搜索一般不能保证找到最优解：当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举。深度优先搜索1缺点：如果目标节点不在搜索所进入的分支上,而该分支又是一个无穷分支,则就得不到解.因此该算法是不完备的。优点：如果目标节点恰好在搜索所进入的分支上,则可以较快地得到解。对于图9-2的树而言，宽度优先搜索首先从根节点1开始，其搜索节点顺序是1,2,6,3,4,7,8,5。宽度优先搜索也是一个通用的与问题无关的方法。宽度优先搜索2优点优点：只要问题有解,则总可以得到解,是完备的，而且是最短路径的解。缺点缺点：当目标节点距离初始节点较远时会产生许多无用的节点,搜索效率低。

回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。回溯搜索3基本原理回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯搜索3回溯搜索3

八皇后问题，是一个古老而著名的问题，是回溯搜索的典型案例，以国际象棋为背景：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？（见图9-3）为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n1×n1，而皇后个数也变成n2。而且仅当n2≥1或n1≥4时问题有解。eb八皇后问题9.2启发式搜索启发式搜索利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率，路径的耗散值和求取路径所需搜索的耗散值二者的组合最小。基本思想：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。A算法或A*算法9.2.1模拟退火9.2.2遗传算法9.2.39.2启发式搜索1、A算法描述或图通用算法在采用如下形式的估计函数时,称为A算法。

f(n)=g(n)+h(n)

其中g(n)表示从s到n点费用的估计，因为n为当前节点，搜索已达到n点，所以g(n)可计算出。h(n)表示从n到g接近程度的估计，因为尚未找到解路径，所以h(n)仅仅是估计值。A算法或A*算法12、算法说明：（1）若令h(n)≡0，则A算法相当于宽度优先搜索，因为上一层节点的搜索费用一般比下一层的小。（2）g(n)≡h(n)≡0，则相当于随机算法。（3）g(n)≡0，则相当于最佳优先搜索算法。（4）特别是当要求h(n)≤h*(n），

就称为这种A算法为A*算法。A算法或A*算法13、A算法举例如在8数码问题中，可以用不正确位置的数字个数作为状态描述好坏的一个度量：f(n)=位置不正确的数字个数(和目标相比)，在搜索过程中采用这个启发式函数将产生图9-5所示的图，每个节点的数值是该节点的值。其他搜索算法：（1）爬山法（局部搜索算法）（2）动态规划法：如果对于任何n，当h(n)=0时，A*算法就成为了动态规划算法。（3）分支界限法：分支界限法是优先扩展当前具有最小耗散值分支路径的端节点；评价函数：f(n)=g(n)。模拟退火21、物体以晶体形态呈现的过程在热力学上，退火现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称淬炼）时，会导致不是最低能态的非晶形。如图所示，首先（左图）物体处于非晶体状态。我们将固体加温至充分高（中图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）。定义模拟退火2模拟退火其实也是一种贪婪算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。模拟退火算法在搜索到局部最优解B后，会以一定的概率接受向右继续移动。也许经过几次这样的不是局部最优的移动后会到达B和C之间的峰点，于是就跳出了局部最小值B。原理模拟退火2关于普通贪婪算法与模拟退火，有一个有趣的比喻：普通贪婪算法：兔子朝着比现在低的地方跳去。它找到了不远处的最低的山谷。但是这座山谷不一定最低的。这就是普通贪婪算法，它不能保证局部最优值就是全局最优值。模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向低处，也可能踏入平地。但是，它渐渐清醒了并朝最低的方向跳去。这就是模拟退火。原理

遗传算法（GeneticAlgorithm）是一种模拟自然界“自然选择”和“自然遗传”的启发式搜索算法，通过模拟自然进化过程搜索最优解的方法。SGA处理流程：遗传算法3遗传算法3在遗传算法中，将染色体称为个体，常见的基因编码方式有二进制编码、浮点数编码和字符编码3种。（1）二进制编码：用二进制表示参数空间，优点：易实现（2）浮点数编码：直接将参数值当成染色体的基因，省去了编码和译码的动作，缺点：无法默认搜索的精确度，不适合处理不连续的变量空间（3）字符编码：直接用字符代表基因的方式算法流程根据SGA处理流程可知，遗传演算开始前，需要先产生初代种群（由一堆随机产生的染色体组成的），由于一个染色体代表一个问题解，因而初代种群也代表初始解的集合。那一个种群应该包括多少染色体呢？这个要视问题复杂度来定，一般来说，越复杂的问题需要越大的种群规模来解决。种群遗传算法3实现选择机制的两种常用方法是竞争选择法和轮盘赌选择法。（1）竞争选择法从种群中选出两个染色体进行适应度值的比较，最后留下适应度较高的染色体作为父代，重复进行这个步骤，直到选出所有的父代为止。（2）轮盘赌选择法按照适应度值的大小决定每一个槽的面积大小，可以使用下面公式来表示：被选中的概率P(i)=f(i)/(f(1)+f(2)+…+f(S))其中f(i)：适应度值；S：染色体总个数，也就是说个体被选中的概率与其适应度函数值成正比。选择遗传算法3第二个遗传算子叫做交叉。作用：希望通过父代之间进行基因交换的动作后，产生具有较高适应度的子代。交叉遗传算法3

交叉过程遗传算法3位于配对库中的染色体是经过选择运算的结果，在交叉流程开始时，会先从配对库中任意取出两个染色体，并将它们作为父代。但是并非所有父代都会进行交叉（取决于交叉概率），实现程序时，可以将交叉概率设置为0.8~1的数值，接着再取一个随机实数，如果该随机实数小于交叉概率，就进行交叉运算。交叉概率的大小会影响搜索最优解的速度，太高的交叉概率有可能流失优良的染色体，反之又会造成进化停滞，故一般把交叉概率设置在0.8~1为宜。交叉过程遗传算法3最后一个遗传算子叫做变异。是否进行变异取决于变异概率，当随机实数小于变异概率时就会引发突变运算，也就是会将染色体中的某个位，由原来的0置换成1，或是由原来的1置换成0。可以置换某个固定位置的位，也可以由随机数来决定位置。使用这种随机漫步的方式，突变运算将使遗传算法脱离布局最优解的窘境，得到全局最优解。根据文献研究显示，建议将变异概率设置为0.001左右。变异遗传算法3经过选择、交叉、变异3个遗传算子后，即可产生新的子代，继续下一个循环的进化，目前常用的取代方式有：

（1）整群取代：全部用新产生的染色体取代旧种群的染色体；

（2）精英保留策略：保留旧种群中适应度值最高的前几名，用新产生的染色体取代其余的染色体。演化迭代遗传算法3

*

Pj：交叉发生的概率

*

Pb：变异发生的概率

*

M：种群规模

*

G：终止进化的代数

*

T：进化产生的任何一个个体的适应度函数超过T，则可以终止进化过程

*/初始化Pb，Pj，M，G，T等参数，随机产生第一代种群Popdo{

计算种群Pop中每一个体的适应度f(i)，初始化空种群newPop

do{

根据适应度以轮盘赌算法从种群Pop中选出2个个体

if(random(0,1)<Pj){对2个个体按交叉