人工智能基础03--搜索技术【教育课件】

1、目录,第一章绪论 第二章知识表示 第三章搜索技术 第四章推理技术 第五章机器学习 第六章专家系统 第七章自动规划系统 第八章 自然语言理解 第九章 智能控制 第十章 人工智能程序设计,技术课件,3.1 盲目搜索,盲目搜索：即 无信息搜索 宽度优先与深度优先 3.1.1 图搜索策略 图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。研究图搜索的一般策略，能够给出图搜索过程的一般步骤,技术课件,3.1 盲目搜索,3.1.1 图搜索策略 例3.1 从王某家族的四代中找王A

2、的后代且其寿命为X的人,A,47,B1,77,A3,52,B2,65,C2,87,C1,96,D1,77,E1,57,E2,92,F1,32,G1,27,H1,51,技术课件,3.1 盲目搜索,3.1.1 图搜索策略 1.图搜索(GRAPHSEARCH)的一般过程 (1) 建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点表中。 (2) 建立一个叫做CLOSED的已扩展节点表，其初始为空表。 (3) LOOP：若OPEN表是空表，则失败退出。 (4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。 (5) 若n为一目标节点，则

3、有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置,技术课件,3.1 盲目搜索,3.1.1 图搜索策略 1.图搜索(GRAPHSEARCH)的一般过程 (6) 扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。 (7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的

4、指针方向。 (8) 按某一任意方式或按某个探试值，重排OPEN表。 (9) GO LOOP,技术课件,3.1 盲目搜索,3.1.1 图搜索策略 2.图搜索算法的几个重要名词 （1）OPEN表与CLOSE表 OPEN表 CLOSED表,技术课件,3.1 盲目搜索,3.1.1 图搜索策略 3. 搜索图与搜索树 搜索过程框图,技术课件,3.1 盲目搜索,3.1.1 图搜索策略 4.图搜索方法分析： 图搜索过程的第8步对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发

5、式搜索)。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点,技术课件,3.1 盲目搜索,3.1.2 宽度优先搜索 定义3.1 如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索（breadth-first search,技术课件,3.1 盲目搜索,3.1.2 宽度优先搜索 宽度优先搜索算法 (1) 把起

6、始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。 (2) 如果OPEN是个空表，则没有解，失败退出；否则继续。 (3) 把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。 (4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。 (5) 把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步,技术课件,3.1 盲目搜索,3.1.2 宽度优先搜索,例3.2 八数码问题 操作规定: 允许空格四周上、下、左、右的数码块移入空格中，不许斜方

7、向移动，不许返回先辈结点。 初始布局S和目标状态D如下图所示,技术课件,3.1 盲目搜索,3.1.2 宽度优先搜索,例3.2 八数码问题,技术课件,3.1 盲目搜索,3.1.3 深度优先搜索 深度优先算法步骤： (1) 初始结点S放到未扩展节点OPEN中； (2) 若OPEN为空，则搜索失败，问题无解； (3) 弹出OPEN表中最顶端结点放到CLOSE表中，并给出顺序编号n； (4) 若n为目标结点D，则搜索成功，问题有解； (5) 若n无子结点，转(2)； (6) 扩展n结点，将其所有子结点配上返回n的指针，并按次序压入OPEN堆栈，转(2),技术课件,3.1 盲目搜索,3.1.3 深度优先

8、搜索,技术课件,3.1 盲目搜索,3.1.3 深度优先搜索 有界深度优先搜索： 引入搜索深度限制值d，使深度优先搜索过程具有完备性 。 设定搜索深度限制d=5，问题同深度优先算法中的八数码问题(2,技术课件,3.1 盲目搜索,3.1.3 深度优先搜索,技术课件,3.1 盲目搜索,3.1.3 深度优先搜索 有界深度优先算法步骤： (1)初始结点S放入堆栈OPEN中； (2)若OPEN为空，则搜索失败，问题无解； (3)弹出OPEN中栈顶结点n，放入CLOSE表中，并给出顺序编号n； (4)若n为目标结点D，则搜索成功，问题有解； (5)若n的深度d(n)=d，则转(2) ； (6)若n无子结点，

9、即不可扩展，转(2) ； (7)扩展结点n，将其所有子结点配上返回n的指针，并压入OPEN堆栈，转(2),技术课件,3.1 盲目搜索,3.1.4 等代价搜索 宽度优先搜索可被推广用来解决寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。 等代价搜索中的几个记号 起始节点记为S； 从节点i到它的后继节点j的连接弧线代价记为c(i，j)； 起始节点S到任一节点i的路径代价记为g(i)。 如果所有的连接弧线具有相等的代价，那么等代价算法就简化为宽度优先搜索算法,技术课件,3.2 启发式搜索,盲目搜索的不足：效率低，耗费空间与时间。 启发式搜索：利用问题

10、域特性的信息（启发信息）进行搜索。 3.2.1 启发式搜索策略 启发式信息按用途分为三种： （1）用于确定要扩展的下一个节点，避免盲目扩展。 （2）在扩展一个节点的过程中，用于确定要生成哪一个或哪几个后继节点，避免盲目生成所有可能节点。 （3）用于确定某些应该从搜索树中抛弃或修剪得节点,技术课件,3.2 启发式搜索,有序搜索（ordered search）：利用第一种启发信息，总是选择“最有希望”的节点作为下一个被扩展的节点。 估价函数（evaluation function )：估算节点“希望”的量度，这种量度叫做估价函数。 建立估价函数的一般方法：试图确定一个处在最佳路径上的节点的概率；提

11、出任意节点与目标集之间的距离量度或差别量度；或者在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。 f(n)表示节点n的估价函数值,技术课件,3.2 启发式搜索,3.2.2 有序搜索 用估价函数f来排列GRAPHSEARCH第8步中OPEN表上的节点。应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索或最佳优先搜索(best-first search)，而其算法就叫做有序搜索算法或最佳优先算法,技术课件,3.2 启发式搜索,3.2.2 有序搜索 有序状态空间搜索算法： (1

12、) 把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联系起来。 (2) 如果OPEN是个空表，则失败退出，无解。 (3) 从OPEN表中选择一个f值最小的节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。 (4) 把节点i从OPEN表中移出，并把它放入CLOSED的扩展节点表中,技术课件,3.2 启发式搜索,3.2.2 有序搜索 (5) 如果i是个目标节点，则成功退出，求得一个解。 (6) 扩展节点i，生成其全部后继节点。对于i的每一个后继节点j： (a) 计算f(j)。 (b) 如果j既不在OPEN表中，又不在CLOSED表

13、中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。 (c) 如果j已在OPEN表上或CLOSED表上，则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小，则,技术课件,3.2 启发式搜索,3.2.2 有序搜索 (i) 以此新值取代旧值。 (ii) 从j指向i，而不是指向它的父辈节点。 (iii) 如果节点j在CLOSED表中，则把它移回OPEN表。 (7) 转向(2)，即GO TO(2,技术课件,3.2 启发式搜索,3.2.2 有序搜索,开始,把S放入OPEN表,OPEN为空表,失败,选取OPEN表中f值最小

14、 的节点i，放入CLOSED表,i=Sg,成功,是,是,扩展i得后继节点j，计算f(j)，提 供返回i的指针，利用f(j)对OPEN 表重新排序调整父子关系及指针,技术课件,3.2 启发式搜索,3.2.2 有序搜索 宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对于宽度优先搜索，选择f(i)作为节点i的深度。对于等代价搜索，f(i)是从起始节点至节点i这段路径的代价。 有序搜索的有效性直接取决于f的选择，如果选择的f不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么f的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一方面

15、是保证有一个最优的解或任意解,技术课件,3.2 启发式搜索,3.2.2 有序搜索 例3.4：八数码难题, 采用了简单的估价函数 f(n)=d(n)+W(n) 其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。因此，起始节点棋局 的f值等于0+4=4,2,8,3,1,6,4,7,5,技术课件,3.2 启发式搜索,3.2.2 有序搜索,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,8,3,1,6,4,7,5,2,8,3,1,4,7,6,5,2,3,1,8,4,7,6,5,2,8,3,1,4,7,6,5,

16、8,3,2,1,4,7,6,5,2,8,3,7,1,4,6,5,2,3,1,8,4,7,6,5,2,3,3,1,8,4,7,6,5,1,2,3,8,4,7,6,5,1,2,3,8,4,7,6,5,1,2,3,7,8,4,6,5,技术课件,3.2 启发式搜索,3.2.3 A*算法 A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。 1. A*算法的估价函数 k(ni，nj)：表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点，函数k没有定义)。 k(n,ti)：从节点n到某个具体的目标节点ti，某一条最小代价路径的代价。 h*(n)：表示整个目标节点集合ti

17、上所有k(n,ti)中最小的一个，因此，h*(n)就是从n到目标节点最小代价路径的代价，而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径(对于任何不能到达目标节点的节点n，函数h*没有定义,技术课件,3.2 启发式搜索,3.2.3 A*算法 定义g* 为g*(n)=k(S,n) 从已知起始节点S到任意节点n的一条最佳路径代价。 定义函数f*， f*(n)=g*(n)+h*(n) 使得在任一节点n上其函数值f*(n)就是从节点S到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和,技术课件,3.2 启发式搜索,3.2.3 A*算法 希

18、望估价函数f是f*的一个估计，此估计可由下式给出： f(n)=g(n)+h(n) 其中：g是g*的估计；h是h*的估计。 对于g(n)：一个明显的选择就是搜索树中从S到n这段路径的代价，这一代价可以由从n到S寻找指针时，把所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。这个定义包含了g(n)g*(n)。 h(n)：对 h*(n)的估计，依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数W(n)所用的那种信息相似。把h叫做启发函数,技术课件,3.2 启发式搜索,3.2.3 A*算法 2. A算法和A*算法的定义 定义3.3 在GRA

19、PHSEARCH过程中，如果第8步的重排OPEN表是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。 定义3.4 在A算法中，如果对所有的x存在h(x)h*(x),则称h(x)为h*(x)的下界，它表示某种偏于保守的估计。 定义3.5 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算法。当h=0时，A*算法就变为有序搜索算法。 A算法和A*搜索算法的目标有所不同： A搜索算法虽然希望能找到问题的最优解，但主要追求的是求解效率；而A*搜索算法直接目标就在于要找到问题的最优解及其解的路径，即便搜索效率有所降低也在所不惜,技术课件,3.2 启发式搜索,3.2.3 A*算法,开始

20、,把S放入OPEN表,记f=h,OPEN为空表,失败,选取OPEN表中未设置过的具有最小f值 的节点BESTNODE，放入CLOSED表,BESTNODE=Sg,成功,是,是,扩展BESTNODE，产生后继节点SUVVESSOR 建立从SUCCESSOR返回BESTNODE的指针 计算g(SUCCESSOR)=g(BESTNODE)+h(BESTNODE)_SUCCESSOR,SUCCESSOROPEN,否,是,技术课件,3.2 启发式搜索,3.2.3 A*算法,把SECCESSOR放入OPEN表， 加入BESTNODE的后裔表,g(SUCCESSOR)g(OLD),否,重新确定OLD的父辈节

21、点为BESTNODE， 并修正父辈节点的g值和f值，记下g(OLD,SUCCESSORCLOSED,否,是,SECCESSOR=OLD，把它添到 BESTNODE的后继节点表中,是,否,计算f值,技术课件,3.3 博弈树搜索,3.3.1 博弈概述 何谓博弈？博弈就是下棋、打牌、竞技、战争等一类竞争性智能活动。 “二人零和非偶然性全信息”博弈 （1）二人零和：对垒的MAX、MIN双方轮流采取行动，博弈的结果只有三种情况：MAX方胜，MIN方胜，和局。 （2）全信息：在对垒过程中，任何一方都了解当前格局及过去的历史。 （3）非偶然性：任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对

22、自己最为有利而对对方最为不利的对策，不存在“碰运气”，“侥幸”及“偶然失误”等随机因素,技术课件,3.3 博弈树搜索,3.3.1 博弈概述 参加博弈的各方都希望己方取得胜利。因此，当一方面临多个行动方案选择时，博弈的各方总是要挑选对自己最为有利而对对方最不利的那个行动方案。 假如MAX方的目标：尽可能使自己达到最大（或最高）的分数分枝节点，可用“或”关系来描述，称之为MAX方节点； 而当轮到MIN方行动时，MIN方的目标：尽可能使MIN方获得最小（或最低）的分数分枝节点，这对MIN方来说，这些行动方案或分数分枝节点之间，可以用“与”关系来描述，是由MIN方自主进行控制的，故又称之为MIN节点,

23、技术课件,3.3 博弈树搜索,3.3.1 博弈概述 把上述双方逐层交替的博弈过程用与/或树（图）描述表达出来，就得到了一棵具有“与/或”节点交替出现的博弈树。 博弈树有如下特点： （1）博弈的初始格局是初始节点。 （2）在博弈树中，由于双方轮流地扩展节点，“或”节点和“与”节点逐层交替出现。如果自己一方扩展的节点之间是“或”关系，则对方扩展的节点之间是“与”关系。 （3）把本方获胜的终局定义为本原问题，相应最优搜索路径上的节点是可解节点，而所有使对方获胜的终局和属于对方最优搜索路径上的节点则是不可解节点。此外，所有其它的节点则是具有风险的中间节点,技术课件,3.3 博弈树搜索,3.3.2 极小

24、极大分析法 在二人博弈过程中，最直观而可靠的常用分析方法就是极小极大化搜索法。其主要描述思想和算法： （1）设博弈的一方为MAX方，其目标是尽可能使自己得到最高分；另一方为MIN方, 其目标是尽可能给MAX方送出最低分。所谓极小极大化分析法是一种要轮流为每一方寻找一个最优行动方案的方法。在图中，方框形状“”表示是MAX方控制的或节点；圆形框形状“”表示MIN方控制与节点。 （2）考虑每一方案实施后对方可能采取的所有行动，并为其计算可能的得分； （3）为计算得分，需要根据问题的特性信息定义一个估价函数，用来估算当前博弈树所有端节点的得分。此时估算出来的得分称为的静态估值,技术课件,3.3 博弈树

25、搜索,3.3.2极小极大分析法 （4）当端节点的估值计算出来后，再推算父辈节点的等分，推算方法是：对“或”节点，选择其子节点中最大的得分作为父辈节点的得分（选择对自己最有利的方案）；对“与”节点，选其子节点中一个最小的得分作为作为父辈节点的得分（立足于最坏的情况）。这样计算出的父辈节点的等分称为倒推值。 （5）如果一个行动方案能获得较大的倒推值，则它就是当前最好的行动方案。 存储受限问题：先生成一定深度的博弈树，进行极小极大分析，找出当前的最好的行动方案。然后再已选定的分支上再扩展一定的深度，如此反复,技术课件,3.3.2极小极大分析法,4 -1 -1 8 1 2 -5 0 -4 -9 -1,

26、5 11 4 3 -1 1 5 8 10 1 4 2 5 -5 9 6 0 6 -4 10 9 -1 12 5,MAX-MIN博弈树的倒推值计算,h(S0)=,4 8 2 0 -1,4 -1,3.3 博弈树搜索,技术课件,3.3 博弈树搜索,3.3.3 -剪枝技术 基本思想：边生成博弈树边估算各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点。 具体剪枝方法： （1） 对于一个“与”节点MIN，若能估计出其倒推值上界，并且这个值不大于MIN的父辈节点（一定是“或”节点）的估计倒推值的下界，即 ，则就不必要再扩展该MIN节点的其余子节点了。这一过程称为剪枝。 （2

27、）对于一个“或”节点MAX，若能估计出其倒推值下界 ，并且这个 值不小于MAX的父辈节点（一定是“与”节点）的估计倒推值的上界 ，即 ，则就不必要再扩展该MAX节点的其余子节点了。这一过程称为 剪枝,技术课件,3.3 博弈树搜索,3.3.3 -剪枝技术 从算法中看到： （1）MAX节点（包括起始节点）的值永不减少。 （2）MIN节点（包括起始节点）的值永不增加。 在搜索期间， 和 值的计算如下： （1）一个MAX节点的值等于其后继节点当前最大的最终倒推值。 （2）一个MIN节点的 值等于其后继节点当前最小的最终倒推值,技术课件,3.3 博弈树搜索,3.3.3 -剪枝技术 例3.5 一字棋搜索树

28、和值计算 估价函数g(p)定义如下： （1）若当前棋局对任何一方都不是获胜的，则 g(p)=(所有空格都放上MAX的棋子之后3个棋子所组成的行列及对角线的总数）（所有空格都放上MIN的棋子之后3个棋子所组成的行列及对角线的总数） （2）若p是MAX获胜，则 g(p)=+ （3）若p是MIN获胜，则 g(p)=- 上图中，g(p)=6-4=2，其中表示MAX方， 表示MIN方,技术课件,3.3.3 -剪枝技术,3.3 博弈树搜索,初始节点,-1,A,B,C,1,-1,6-5=1,5-5=0,6-5=1,5-5=0,4-5=-1,5-6=-1,技术课件,3.3.3 -剪枝技术,3.3 博弈树搜索,

29、4 -1 -1 8 1 2 -5 0 -4 -9 -1,5 11 4 3 -1 1 5 8 10 1 4 2 5 -5 9 6 0 6 -4 10 9 -1 12 5,MAX-MIN博弈树的倒推值计算,h(S0)=,4 8 2 0 -1,4 -1,技术课件,3.3.3 -剪枝技术,3.3 博弈树搜索,h(S0)=,4,4,11,3,3,1,1,8,8,10,8,2,2,5,5,2,2,4,4,x5,5,4,博弈树的-剪枝实现过程,技术课件,3.3 博弈树搜索,3.3.3 -剪枝技术 要进行-剪枝，必须至少使某一部分的搜索树生长到最大深度，因为和值必须以端节点的静态估值为依据。因此采用-剪枝技术

30、通常都要使用某种深度优先的搜索方法,技术课件,3.4 遗传算法,生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则；生物通过个体间的选择、交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；适应能力用对应一个染色体的数值来衡量；染色体的选择或淘汰问题是按求最大还是最小问题来进行。 遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种最重要形式,技术课件,3.4 遗传算法,遗传算法提出：于20世纪60年代由密歇根(Michigan)大学Hollstien,

31、 Bagleyh和Rosenberg等人在其博士论文中首先加以研究；1975年，美国J.H.Holland教授在其著作“Adaptation in Natural and Artificial Systems”中系统地阐述了遗传算法，给出了遗传算法的基本定理和大量的数学理论证明。 遗传算法发展：David E. Goldberg教授1989年出版了 “Genetic Algorichms”一书，这一著作通常被认为是遗传算法的方法、理论及应用的全面系统的总结。从1985年起，国际上开始陆续举行遗传算法的国际会议，后来又更名为进化计算。参加进化计算国际会议的人数及收录文章的数量、广度和深度逐年扩大

32、。从此，进化计算逐渐成为人们用来解决高度复杂问题的新思路和新方法,技术课件,3.4 遗传算法,遗传算法特点：遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文适者生存的理论，模拟自然进化过程来寻找所求问题的解答。遗传算法具有以下特点： (1) 遗传算法是对参数集合的编码而非针对参数本身进行进化； (2) 遗传算法是从问题解的编码组开始而非从单个解开始搜索； (3) 遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索； (4) 遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作,技术课件,3.4 遗传算法,遗传算法应用： J.H.H

33、olland博士于1975年提出遗传算法,当时并没有引起学术界足够的重视。直到二十世纪80年代中期,随着计算机技术日新月异高速发展与进步,遗传算法首先成功地应用于AI机器学习和神经网络方面;后来又在诸如函数优化、自动控制、图象识别、分子生物学、优化调度以及机械、土木、电力工程等工业系统和许多领域中得到应用,显示出诱人的前景。从此，遗传算法始才得到学术界普遍关注与认可,技术课件,3.4 遗传算法,3.4.1 遗传算法的基本原理 霍兰德提出的遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。在讨论中会结合销售员旅行问题（TSP）来说明。 1

34、. 编码与解码 许多应用问题的结构很复杂，但可以化为简单的位串形式编码表示。将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体,技术课件,3.4 遗传算法,3.4.1 遗传算法的基本原理 例：对于销售员旅行问题（Travelling salesman Problem, TSP），设有n个城市，城市i和城市j之间的距离为d(i,j)，要求找到一条遍访每个城市一次而且恰好一次的旅行线路，使其路径总长度为最短。按一条回路中城市的次序进行编码。从城市w1开始，依次经过城市w2 ，wn，最后回到城市w1，我们

35、就有如下编码表示： w1 w2 wn 由于是回路，记wn+1=w1。它其实是1，n的一个循环排列。要注意w1，w2，wn是互不相同的,技术课件,3.4 遗传算法,3.4.1 遗传算法的基本原理 2. 适应度函数 为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数（fitness function）。TSP的目标是路径总长度为最短，自然地，路径总长度的倒数就可作为TSP问题的适应度函数: 其中wn+1=w1 适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。适应度函数的取值大小与求解问题对象的意义有很大的关系,技术课件,3.4 遗传算法,3.4.

36、1 遗传算法的基本原理 3. 遗传操作 简单遗传算法的遗传操作主要有有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。 选择操作也叫复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。 简单遗传算法采用赌轮选择机制，令fi表示群体的适应度值之总和， fi表示种群中第i个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额fi /fi,技术课件,3.4 遗传算法,3.4.1 遗传算法的基本原理 3. 遗传操作 交叉操作的简单方式是将被选择出的

37、两个个体P1和P2作为父母个体，将两者的部分码值进行交换。 产生一个17之间的随机数c，假设为3，则将P1和P2的低3位交换,P1,P2,技术课件,3.4 遗传算法,3.4.1 遗传算法的基本原理 3. 遗传操作,P1,P2,Q1,Q2,技术课件,3.4 遗传算法,3.4.1 遗传算法的基本原理 3. 遗传操作 变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0。 随机产生一个18之间的数k，假设k=5，对从右往左第5位变异操作,1,技术课件,3.4 遗传算法,3.4.1 遗传算法的基本原理 4. 控制参数 交叉发生的概率：0.

38、60.95 变异的概率：0.0010.01 种群的个数：30100 个体的长度：定长和变长,技术课件,3.4 遗传算法,3.4.2 遗传算法的结构 选择：由个体适应度值决定 的某个规则。 交叉：按概率Pc进行 变异：按概率Pm进行 终止条件： 完成了预先给定的进化代数 种群中的最优个体在连续若干代 没有改进或平均适应度在连续若 干代基本没有改进,开始,初始化种群,选择操作,终止条件,否,适应度最有优个体,计算适应度值,交叉操作,变异操作,结束,技术课件,3.4 遗传算法,3.4.3 遗传算法的性能 遗传算法求得的解是一满意解。影响解质量的因素： 种群的数量：太小缺少多样性，太多影响效率 适应度

39、函数：提升优良个体的适应度 交叉和变异：不同的问题需构造性能更优的交叉和变异操作 交叉概率和变异概率,技术课件,分析：对该问题虽然也可以采用枚举的方法来解决,但枚举法却是一种效率很低的方法.可运用遗传算法来求解该问题. 解：首先对问题进行初始化，以获得初始种群; （1） 确定适当的编码方案：将x编码表示为染色体的数字符号串。针对本题自变量x定义域,取值范围为0，31,考虑采用二进制数来对其编码,由25 = 32,故使用5位无符号二进制数组成染色体数字字符串,用以表达变量x及问题的解答过程,例: 设有函数f(x)=x2, 请用遗传算法求其自变量x在区间0，31 取整数值时的最大值，并说明此函数的

40、优化问题,3.4 遗传算法,技术课件,2）选择初始种群:通过随机的方法来产生染色体的数字串，并组成初始种群。例如，为得到数字串的某位又称之为基因(genes)，使用计算机在01之间产生随机数K，并按照数K的变化区域来规定基因代码如下： 0， （0K0.5） 1， （0.5K1,3.4 遗传算法,技术课件,于是随机生成4个染色体的数字符串为： 01101 11000 01000 10011 从而构造了初始种群，完成了遗传算法的准备,3.4 遗传算法,技术课件,表 初始种群染色体及对应的适应值,3.4 遗传算法,技术课件,3）复制(选择): 选择适应值大的串作为母本，使在下一代中有更多的机会繁殖其

41、子孙。 要在四个种子个体中做选择，要求仍然得到四个染色体，可依据适应度概率比例制定如下规则： 低于0.125以下的染色体被淘汰； 在0.1250.375之间的染色体被复制一个； 在0.3750.625之间的染色体被复制两个； 在0.6250.875之间的染色体被复制三个； 在0.875以上的染色体可复制四个,3.4 遗传算法,技术课件,对应于上例，按照适应度的计算，经复制操作后，得到新的染色体种群为 01101 11000 11000 10011,3.4 遗传算法,技术课件,某个染色体是否被复制,可以通过概率决策法、适应度比例法或“轮盘赌”的随机方法来断定。对应轮盘赌转盘的随机方法,根据表6.

42、1数据，绘制出的轮盘赌转盘,如图所示,进化计算基本遗传算法原理,01101 11000 11000 10011,技术课件,3.4 遗传算法,初始种群染色体准备复制操作的各项计算数据,技术课件,4）交叉: 交叉具体分两步：将新复制产生的染色体随机两两匹配,称其为双亲染色体；再把双亲染色体进行交叉繁殖。 交叉的实现: 设染色体数字串长度为L，把L个数字位间空隙分别标记为： 1，2，L1 随机从1，L1中选取某一整数位置k，0kL 交换双亲染色体交换点位置k右边的部分，就形成了两个新的数字符串（也可以只交换其中的第k基因），得到了两个新的染色体，又称之为下一代染色体,3.4 遗传算法,技术课件,例如

43、，将上例初始种群的两个体 A1=01101 A2=11000 假定从1到4间选取两个随机数，得到1=2，2=4，那么经过交叉操作之后将得到如下两组新的数字符串 A1#=01000 A2#=11101,3.4 遗传算法,A3#=01100 A4#=11001,前一组数字串是使用1=2,即将第2位后的35位交换得到； 后一组数字串是使用2=4，即仅将第5位因子进行交换而得,技术课件,3.4 遗传算法,复制、交叉操作的各项数据,技术课件,5）变异: 设变异概率取为0.001,则对于种群总共有20个基因位. 期望的变异串位数计算:200.001 =0.02(位), 故一般来说,该例中无基因位数值的改变.从表11-2和11-3可以看出,每经过一次复制、交叉和变异操作后,目标函数的最优值和平均值就会有所提高。 在上例中，种群的平均适应值从293增至446.5;最大的适应度数值从576增至841。 特点：每经一次进化计算步骤,问题解答便向着最优方向前进了一步;若该过程一直进行下去,就将最终走向全局的最优解.可见进化计算的每一步操作简单,并且系统的求解过程是依照计算方法与规律来决定,与本源问题自身的特性很少相关,3.4 遗传算法,技术课件,固体