人工智能搜索技术

目录第一章绪论第二章知识表示

第三章搜索技术第四章推理技术第五章机器学习

第六章教授系统第七章自动规划系统第八章自然语言了解第九章智能控制第十章人工智能程序设计人工智能搜索技术第1页3.1盲目搜索盲目搜索：即无信息搜索宽度优先与深度优先3.1.1图搜索策略

图搜索策略可看作一个在图中寻找路径方法。初始节点和目标节点分别代表初始数据库和满足终止条件数据库。求得把一个数据库变换为另一数据库规则序列问题就等价于求得图中一条路径问题。研究图搜索普通策略，能够给出图搜索过程普通步骤。

人工智能搜索技术第2页3.1盲目搜索3.1.1图搜索策略例3.1从王某家族四代中找王A后代且其寿命为X人

A,47B1,77A3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51人工智能搜索技术第3页3.1盲目搜索3.1.1图搜索策略1.图搜索(GRAPHSEARCH)普通过程(1)建立一个只含有起始节点S搜索图G，把S放到一个叫做OPEN未扩展节点表中。(2)建立一个叫做CLOSED已扩展节点表，其初始为空表。(3)LOOP：若OPEN表是空表，则失溃退出。(4)选择OPEN表上第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到(指针将在第7步中设置)。人工智能搜索技术第4页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中通向它每个后代节点指针方向。(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GOLOOP。

人工智能搜索技术第5页3.1盲目搜索节点父辈节点3.1.1图搜索策略2.图搜索算法几个主要名词（1）OPEN表与CLOSE表OPEN表CLOSED表编号节点父辈节点人工智能搜索技术第6页3.1盲目搜索3.1.1图搜索策略3.搜索图与搜索树搜索过程框图开

始初始化：S放入OPEN表，CLOES表置空,n=1OPEN表中第一个结点n移至CLOSE表若n后继未曾在搜索图G中出现，则将其放入OPEN表末端，并提供返回结点n指针,置n=n+1依据后继结点在搜索图G中出现情况修改指针方向依某种准则重新排序OPEN表失败成功NYNOPEN为空表NULL？n=目标结点D吗?Y人工智能搜索技术第7页3.1盲目搜索3.1.1图搜索策略4.图搜索方法分析：图搜索过程第8步对OPEN表上节点进行排序，方便能够从中选出一个“最好”节点作为第4步扩展用。这种排序能够是任意即盲目标(属于盲目搜索)，也能够用以后要讨论各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点这条成功路径，其方法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展端节点时，过程就以失败告终(一些节点最终可能没有后继节点，所以OPEN表可能最终变成空表)。在失败终止情况下，从起始节点出发，一定达不到目标节点。

人工智能搜索技术第8页3.1盲目搜索3.1.2宽度优先搜索

定义3.1假如搜索是以靠近起始节点程度依次扩展节点，那么这种搜索就叫做宽度优先搜索（breadth-firstsearch)人工智能搜索技术第9页3.1盲目搜索3.1.2宽度优先搜索宽度优先搜索算法(1)把起始节点放到OPEN表中(假如该起始节点为一目标节点，则求得一个解答)。(2)假如OPEN是个空表，则没有解，失溃退出；不然继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED扩展节点表中。(4)扩展节点n。假如没有后继节点，则转向上述第(2)步。(5)把n全部后继节点放到OPEN表末端，并提供从这些后继节点回到n指针。(6)假如n任一个后继节点是个目标节点，则找到一个解答，成功退出；不然转向第(2)步。人工智能搜索技术第10页3.1盲目搜索3.1.2宽度优先搜索

例3.2

八数码问题操作要求:允许空格四面上、下、左、右数码块移入空格中，不许斜方向移动，不许返回先辈结点。

初始布局S和目标状态D以下列图所表示：

人工智能搜索技术第11页3.1盲目搜索3.1.2宽度优先搜索

例3.2

八数码问题人工智能搜索技术第12页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)。人工智能搜索技术第13页3.1盲目搜索3.1.3深度优先搜索

人工智能搜索技术第14页3.1盲目搜索3.1.3深度优先搜索有界深度优先搜索：引入搜索深度限制值d，使深度优先搜索过程含有完备性。设定搜索深度限制d=5，问题同深度优先算法中八数码问题(2)。人工智能搜索技术第15页3.1盲目搜索3.1.3深度优先搜索

人工智能搜索技术第16页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无子结点，即不可扩展，转(2)；(7)扩展结点n，将其全部子结点配上返回n指针，并压入OPEN堆栈，转(2)。人工智能搜索技术第17页3.1盲目搜索3.1.4等代价搜索

宽度优先搜索可被推广用来处理寻找从起始状态至目标状态含有最小代价路径问题，这种推广了宽度优先搜索算法叫做等代价搜索算法。等代价搜索中几个记号起始节点记为S；从节点i到它后继节点j连接弧线代价记为c(i，j)；起始节点S到任一节点i路径代价记为g(i)。

假如全部连接弧线含有相等代价，那么等代价算法就简化为宽度优先搜索算法。人工智能搜索技术第18页3.2启发式搜索盲目搜索不足：效率低，花费空间与时间。启发式搜索：利用问题域特征信息（启发信息）进行搜索。3.2.1启发式搜索策略启发式信息按用途分为三种：（1）用于确定要扩展下一个节点，防止盲目扩展。（2）在扩展一个节点过程中，用于确定要生成哪一个或哪几个后继节点，防止盲目生成全部可能节点。（3）用于确定一些应该从搜索树中抛弃或修剪得节点。

人工智能搜索技术第19页3.2启发式搜索有序搜索（orderedsearch）：利用第一个启发信息，总是选择“最有希望”节点作为下一个被扩展节点。估价函数（evaluationfunction)：估算节点“希望”量度，这种量度叫做估价函数。建立估价函数普通方法：试图确定一个处于最正确路径上节点概率；提出任意节点与目标集之间距离量度或差异量度；或者在棋盘式博弈和难题中依据棋局一些特点来决定棋局得分数。这些特点被认为与向目标节点前深入希望程度相关。

f(n)——表示节点n估价函数值

人工智能搜索技术第20页3.2启发式搜索3.2.2有序搜索用估价函数f来排列GRAPHSEARCH第8步中OPEN表上节点。应用某个算法(比如等代价算法)选择OPEN表上含有最小f值节点作为下一个要扩展节点。这种搜索方法叫做有序搜索或最正确优先搜索(best-firstsearch)，而其算法就叫做有序搜索算法或最正确优先算法。

人工智能搜索技术第21页3.2启发式搜索3.2.2有序搜索有序状态空间搜索算法：(1)把起始节点S放到OPEN表中，计算f(S)并把其值与节点S联络起来。(2)假如OPEN是个空表，则失溃退出，无解。(3)从OPEN表中选择一个f值最小节点i。结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，不然就选择其中任一个节点作为节点i。(4)把节点i从OPEN表中移出，并把它放入CLOSED扩展节点表中。

人工智能搜索技术第22页3.2启发式搜索3.2.2有序搜索(5)假如i是个目标节点，则成功退出，求得一个解。(6)扩展节点i，生成其全部后继节点。对于i每一个后继节点j：(a)计算f(j)。(b)假如j既不在OPEN表中，又不在CLOSED表中，则用估价函数f把它添入OPEN表。从j加一指向其父辈节点i指针，方便一旦找到目标节点时记住一个解答路径。(c)假如j已在OPEN表上或CLOSED表上，则比较刚才对j计算过f值和前面计算过该节点在表中f值。假如新f值较小，则

人工智能搜索技术第23页3.2启发式搜索3.2.2有序搜索(i)以此新值取代旧值。(ii)从j指向i，而不是指向它父辈节点。(iii)假如节点j在CLOSED表中，则把它移回OPEN表。(7)转向(2)，即GOTO(2)。

人工智能搜索技术第24页3.2启发式搜索3.2.2有序搜索

开始把S放入OPEN表OPEN为空表？失败选取OPEN表中f值最小节点i，放入CLOSED表i=Sg？成功是是扩展i得后继节点j，计算f(j)，提供返回i指针，利用f(j)对OPEN表重新排序调整父子关系及指针人工智能搜索技术第25页3.2启发式搜索3.2.2有序搜索宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术特例。对于宽度优先搜索，选择f(i)作为节点i深度。对于等代价搜索，f(i)是从起始节点至节点i这段路径代价。有序搜索有效性直接取决于f选择，如果选择f不合适，有序搜索就可能失去一个最好解甚至全部解。如果没有适用准确希望量度，那么f选择将涉及两个方面内容：一方面是一个时间和空间之间折衷方案；其次是保证有一个最优解或任意解。人工智能搜索技术第26页3.2启发式搜索3.2.2有序搜索例3.4：八数码难题,采取了简单估价函数f(n)=d(n)+W(n)其中：d(n)是搜索树中节点n深度；W(n)用来计算对应于节点n数据库中错放棋子个数。所以，起始节点棋局f值等于0+4=4。

28316475人工智能搜索技术第27页3.2启发式搜索3.2.2有序搜索28316475283164752831476528316475283147652318476528314765832147652837146523184765233184765123847651238476512378465人工智能搜索技术第28页3.2启发式搜索3.2.3A*算法A*算法是一个有序搜索算法，其特点在于对估价函数定义上。

1.A*算法估价函数k(ni，nj)：表示任意两个节点ni和nj之间最小代价路径实际代价(对于两节点间没有通路节点，函数k没有定义)。k(n,ti)：从节点n到某个详细目标节点ti，某一条最小代价路径代价。h*(n)：表示整个目标节点集合｛ti｝上全部k(n,ti)中最小一个，所以，h*(n)就是从n到目标节点最小代价路径代价，而且从n到目标节点能够取得h*(n)任一路径就是一条从n到某个目标节点最正确路径(对于任何不能抵达目标节点节点n，函数h*没有定义)。

人工智能搜索技术第29页3.2启发式搜索3.2.3A*算法定义g*为g*(n)=k(S,n)从已知起始节点S到任意节点n一条最正确路径代价。定义函数f*，f*(n)=g*(n)+h*(n)使得在任一节点n上其函数值f*(n)就是从节点S到节点n一条最正确路径实际代价加上从节点n到某目标节点一条最正确路径代价之和。

人工智能搜索技术第30页3.2启发式搜索3.2.3A*算法希望估价函数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叫做启发函数。人工智能搜索技术第31页3.2启发式搜索3.2.3A*算法2.A算法和A*算法定义定义3.3在GRAPHSEARCH过程中，假如第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*搜索算法直接目标就在于要找到问题最优解及其解路径，即便搜索效率有所降低也在所不惜。

人工智能搜索技术第32页3.2.3A*算法开始把S放入OPEN表,记f=hOPEN为空表？失败选取OPEN表中未设置过含有最小f值节点BESTNODE，放入CLOSED表BESTNODE=Sg？成功是是扩展BESTNODE，产生后继节点SUVVESSOR建立从SUCCESSOR返回BESTNODE指针计算g(SUCCESSOR)=g(BESTNODE)+h(BESTNODE)_SUCCESSOR)SUCCESSOR∈OPEN？否是人工智能搜索技术第33页3.2.3A*算法把SECCESSOR放入OPEN表，加入BESTNODE后代表g(SUCCESSOR)<g(OLD)？否重新确定OLD父辈节点为BESTNODE，并修正父辈节点g值和f值，记下g(OLD)SUCCESSOR∈CLOSED？否是SECCESSOR=OLD，把它添到BESTNODE后继节点表中是否计算f值人工智能搜索技术第34页3.3博弈树搜索3.3.1博弈概述何谓博弈？博弈就是下棋、打牌、竞技、战争等一类竞争性智能活动。“二人零和非偶然性全信息”博弈

（1）二人零和：对垒MAX、MIN双方轮番采取行动，博弈结果只有三种情况：MAX方胜，MIN方胜，和局。

（2）全信息：在对垒过程中，任何一方都了解当前格局及过去历史。

（3）非偶然性：任何一方在采取行动前都要依据当前实际情况，进行得失分析，选取对自己最为有利而对对方最为不利对策，不存在“碰运气”，“侥幸”及“偶然失误”等随机原因。人工智能搜索技术第35页3.3博弈树搜索3.3.1博弈概述参加博弈各方都希望己方取得胜利。所以，当首先临多个行动方案选择时，博弈各方总是要挑选对自己最为有利而对对方最不利那个行动方案。假如MAX方目标：尽可能使自己到达最大（或最高）分数分枝节点，可用“或”关系来描述，称之为MAX方节点；而当轮到MIN方行动时，MIN方目标：尽可能使MIN方取得最小（或最低）分数分枝节点，这对MIN方来说，这些行动方案或分数分枝节点之间，能够用“与”关系来描述，是由MIN方自主进行控制，故又称之为MIN节点。

人工智能搜索技术第36页3.3博弈树搜索3.3.1博弈概述把上述双方逐层交替博弈过程用与/或树（图）描述表示出来，就得到了一棵含有“与/或”节点交替出现博弈树。博弈树有以下特点：（1）博弈初始格局是初始节点。（2）在博弈树中，因为双方轮番地扩展节点，“或”节点和“与”节点逐层交替出现。假如自己一方扩展节点之间是“或”关系，则对方扩展节点之间是“与”关系。（3）把本方获胜终局定义为本原问题，对应最优搜索路径上节点是可解节点，而全部使对方获胜终局和属于对方最优搜索路径上节点则是不可解节点。另外，全部其它节点则是含有风险中间节点。人工智能搜索技术第37页3.3博弈树搜索3.3.2极小极大分析法在二人博弈过程中，最直观而可靠惯用分析方法就是极小极大化搜索法。其主要描述思想和算法：（1）设博弈一方为MAX方，其目标是尽可能使自己得到最高分；另一方为MIN方,其目标是尽可能给MAX方送出最低分。所谓极小极大化分析法是一个要轮番为每一方寻找一个最优行动方案方法。在图中，方框形状“□”表示是MAX方控制或节点；圆形框形状“○”表示MIN方控制与节点。（2）考虑每一方案实施后对方可能采取全部行动，并为其计算可能得分；（3）为计算得分，需要依据问题特征信息定义一个估价函数，用来估算当前博弈树全部端节点得分。此时估算出来得分称为静态估值。人工智能搜索技术第38页3.3博弈树搜索3.3.2极小极大分析法（4）当端节点估值计算出来后，再推算父辈节点等分，推算方法是：对“或”节点，选择其子节点中最大得分作为父辈节点得分（选择对自己最有利方案）；对“与”节点，选其子节点中一个最小得分作为作为父辈节点得分（立足于最坏情况）。这么计算出父辈节点等分称为倒推值。（5）假如一个行动方案能取得较大倒推值，则它就是当前最好行动方案。存放受限问题：先生成一定深度博弈树，进行极小极大分析，找出当前最好行动方案。然后再已选定分支上再扩展一定深度，如此重复。人工智能搜索技术第39页3.3.2极小极大分析法

4-1-1812-50-4-9-1

51143-1–158101425-59606-410–9-1125MAX-MIN博弈树倒推值计算h(S0)=？

4820-14-13.3博弈树搜索人工智能搜索技术第40页3.3博弈树搜索3.3.3α-β剪枝技术基本思想：边生成博弈树边估算各节点倒推值，而且依据评定出倒推值范围，及时停顿扩展那些已无必要再扩展子节点。详细剪枝方法：（1）对于一个“与”节点MIN，若能预计出其倒推值上界β，而且这个β值小于MIN父辈节点（一定是“或”节点）预计倒推值下界α，即α≥β，则就无须要再扩展该MIN节点其余子节点了。这一过程称为α剪枝。（2）对于一个“或”节点MAX，若能预计出其倒推值下界α，而且这个α值大于MAX父辈节点（一定是“与”节点）预计倒推值上界β，即α≥β，则就无须要再扩展该MAX节点其余子节点了。这一过程称为β剪枝。人工智能搜索技术第41页3.3博弈树搜索3.3.3α-β剪枝技术从算法中看到：（1）MAX节点（包含起始节点）α值永不降低。（2）MIN节点（包含起始节点）β值永不增加。在搜索期间，α和β值计算以下：（1）一个MAX节点α值等于其后继节点当前最大最终倒推值。（2）一个MIN节点β值等于其后继节点当前最小最终倒推值。人工智能搜索技术第42页3.3博弈树搜索3.3.3α-β剪枝技术例3.5一字棋搜索树α和β值计算估价函数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方○×人工智能搜索技术第43页3.3.3α-β剪枝技术3.3博弈树搜索×××○×○×○×○×○○×初始节点α=-1ABC-1β=-16-5=15-5=06-5=15-5=04-5=-15-6=-1人工智能搜索技术第44页3.3.3α-β剪枝技术3.3博弈树搜索

4-1-1812-50-4-9-1

51143-1–158101425-59606-410–9-1125MAX-MIN博弈树倒推值计算h(S0)=？

4820-14-1人工智能搜索技术第45页3.3.3α-β剪枝技术3.3博弈树搜索h(S0)=？441133–1–18810822-5-52244x≲554×α×α

×β

×α

×α

×α

×α

博弈树α-β剪枝实现过程

人工智能搜索技术第46页3.3博弈树搜索3.3.3α-β剪枝技术要进行α-β剪枝，必须最少使某一部分搜索树生长到最大深度，因为α和β值必须以端节点静态估值为依据。所以采取α-β剪枝技术通常都要使用某种深度优先搜索方法。人工智能搜索技术第47页3.4遗传算法生物群体生存过程普遍遵照达尔文物竞天择、适者生存进化准则；生物经过个体间选择、交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来表达就是一串数码，仍叫染色体，有时也叫个体；适应能力用对应一个染色体数值来衡量；染色体选择或淘汰问题是按求最大还是最小问题来进行。

遗传算法是模仿生物遗传学和自然选择机理，经过人工方式结构一类优化搜索算法，是对生物进化过程进行一个数学仿真，是进化计算一个最主要形式。

人工智能搜索技术第48页3.4遗传算法遗传算法提出：于20世纪60年代由密歇根(Michigan)大学Hollstien,Bagleyh和Rosenberg等人在其博士论文中首先加以研究；1975年，美国J.H.Holland教授在其著作“AdaptationinNaturalandArtificialSystems”中系统地阐述了遗传算法，给出了遗传算法基本定理和大量数学理论证实。遗传算法发展：DavidE.Goldberg教授1989年出版了“GeneticAlgorichms”一书，这一著作通常被认为是遗传算法方法、理论及应用全方面系统总结。从1985年起，国际上开始陆续举行遗传算法国际会议，以后又更名为进化计算。参加进化计算国际会议人数及收录文章数量、广度和深度逐年扩大。从此，进化计算逐步成为人们用来处理高度复杂问题新思绪和新方法。

人工智能搜索技术第49页3.4遗传算法遗传算法特点：遗传算法是一个基于空间搜索算法，它经过自然选择、遗传、变异等操作以及达尔文适者生存理论，模拟自然进化过程来寻找所求问题解答。遗传算法含有以下特点：(1)遗传算法是对参数集合编码而非针对参数本身进行进化；(2)遗传算法是从问题解编码组开始而非从单个解开始搜索；(3)遗传算法利用目标函数适应度这一信息而非利用导数或其它辅助信息来指导搜索；(4)遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。人工智能搜索技术第50页3.4遗传算法遗传算法应用：J.H.Holland博士于1975年提出遗传算法,当初并没有引发学术界足够重视。直到二十世纪80年代中期,伴随计算机技术日新月异高速发展与进步,遗传算法首先成功地应用于AI机器学习和神经网络方面;以后又在诸如函数优化、自动控制、图象识别、分子生物学、优化调度以及机械、土木、电力工程等工业系统和许多领域中得到应用,显示出诱人前景。从此，遗传算法始才得到学术界普遍关注与认可。人工智能搜索技术第51页3.4遗传算法3.4.1遗传算法基本原理霍兰德提出遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论主要对象，加上适应改进，来分析遗传算法结构和机理。在讨论中会结合销售员旅行问题（TSP）来说明。

1.编码与解码许多应用问题结构很复杂，但能够化为简单位串形式编码表示。将问题结构变换为位串形式编码表示过程叫编码；而相反将位串形式编码表示变换为原问题结构过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。

人工智能搜索技术第52页3.4遗传算法3.4.1遗传算法基本原理例：对于销售员旅行问题（TravellingsalesmanProblem,TSP），设有n个城市，城市i和城市j之间距离为d(i,j)，要求找到一条遍访每个城市一次而且恰好一次旅行线路，使其路径总长度为最短。按一条回路中城市次序进行编码。从城市w1开始，依次经过城市w2，……，wn，最终回到城市w1，我们就有以下编码表示：w1

w2……wn因为是回路，记wn+1=w1。它其实是1，……，n一个循环排列。要注意w1，w2，……，wn是互不相同。人工智能搜索技术第53页3.4遗传算法3.4.1遗传算法基本原理2.适应度函数为了表达染色体适应能力，引入了对问题中每一个染色体都能进行度量函数，叫适应度函数（fitnessfunction）。TSP目标是路径总长度为最短，自然地，路径总长度倒数就可作为TSP问题适应度函数:其中wn+1=w1适应度函数要有效反应每一个染色体与问题最优解染色体之间差距。适应度函数取值大小与求解问题对象意义有很大关系。

人工智能搜索技术第54页3.4遗传算法3.4.1遗传算法基本原理3.遗传操作简单遗传算法遗传操作主要有有三种:选择(selection)、交叉(crossover)、变异(mutation)。改进遗传算法大量扩充了遗传操作，以到达更高效率。选择操作也叫复制（reproduction）操作，依据个体适应度函数值所度量优劣程度决定它在下一代是被淘汰还是被遗传。简单遗传算法采取赌轮选择机制，令∑fi表示群体适应度值之总和，fi表示种群中第i个染色体适应度值，它产生后代能力恰好为其适应度值所占份额fi/∑fi。人工智能搜索技术第55页3.4遗传算法3.4.1遗传算法基本原理3.遗传操作交叉操作简单方式是将被选择出两个个体P1和P2作为父母个体，将二者部分码值进行交换。产生一个1~7之间随机数c，假设为3，则将P1和P2低3位交换

10001110P1：11011001P2：人工智能搜索技术第56页3.4遗传算法3.4.1遗传算法基本原理3.遗传操作

10001110P1：11011001P2：1000100111011110Q1：Q2：人工智能搜索技术第57页3.4遗传算法3.4.1遗传算法基本原理3.遗传操作变异操作简单方式是改变数码串某个位置上数码。二进制编码表示简单变异操作是将0与1交换：0变异为1，1变异为0。随机产生一个1~8之间数k，假设k=5，对从右往左第5位变异操作。

101001101人工智能搜索技术第58页3.4遗传算法3.4.1遗传算法基本原理4.控制参数交叉发生概率：0.6~0.95变异概率：0.001~0.01种群个数：30~100个体长度：定长和变长人工智能搜索技术第59页3.4遗传算法3.4.2遗传算法结构选择：由个体适应度值决定某个规则。交叉：按概率Pc进行变异：按概率Pm进行终止条件：①完成了预先给定进化代数②种群中最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进开始初始化种群选择操作终止条件否适应度最有优个体计算适应度值交叉操作变异操作结束人工智能搜索技术第60页3.4遗传算法3.4.3遗传算法性能

遗传算法求得解是一满意解。影响解质量原因：种群数量：太小缺乏多样性，太多影响效率适应度函数：提升优良个体适应度交叉和变异：不一样问题需结构性能更优交叉和变异操作交叉概率和变异概率：人工智能搜索技术第61页分析：对该问题即使也能够采取枚举方法来处理,但枚举法却是一个效率很低方法.可利用遗传算法来求解该问题.解：首先对问题进行初始化，以取得初始种群;（1）确定适当编码方案：将x编码表示为染色体数字符号串。针对本题自变量x定义域,取值范围为[0，31],考虑采取二进制数来对其编码,由25=32,故使用5位无符号二进制数组成染色体数字字符串,用以表示变量x及问题解答过程。

例:设有函数f(x)=x2,请用遗传算法求其自变量x在区间[0，31]取整数值时最大值，并说明此函数优化问题。

3.4遗传算法人工智能搜索技术第62页

（2）选择初始种群:经过随机方法来产生染色体数字串，并组成初始种群。比如，为得到数字串某位——又称之为基因(genes)，使用计算机在0～1之间产生随机数K，并按照数K改变区域来要求基因代码以下：

0，（0≤K＜0.5）1，（0.5≤K≤1）3.4遗传算法G=人工智能搜索技术第63页于是随机生成4个染色体数字符串为：01101110000100010011从而结构了初始种群，完成了遗传算法准备。3.4遗传算法人工智能搜索技术第64页表初始种群染色体及对应适应值

3.4遗传算法染色体标号

串

x

适应值f(x)=x2占整体百分数

1

01101

169

14.4%

2

11000

576

49.2%

301000

64

5.5%

4

10011

361

30.9%

总计∑（初始种群值）

1170

100.0%人工智能搜索技术第65页（3）复制(选择):选择适应值大串作为母本，使在下一代中有更多机会繁殖其子孙。要在四个种子个体中做选择，要求依然得到四个染色体，可依据适应度概率百分比制订以下规则：低于0.125以下染色体被淘汰；在0.125～0.375之间染色体被复制一个；在0.375～0.625之间染色体被复制两个；在0.625～0.875之间染色体被复制三个；在0.875以上染色体可复制四个。3.4遗传算法人工智能搜索技术第66页对应于上例，按照适应度计算，经复制操作后，得到新染色体种群为011011100011000100113.4遗传算法人工智能搜索技术第67页

某个染色体是否被复制,能够经过概率决议法、适应度百分比法或“轮盘赌”随机方法来断定。对应轮盘赌转盘随机方法,依据表6.1数据，绘制出轮盘赌转盘,如图所表示:

进化计算——基本遗传算法原理49.2﹪30.9%14.4%5.5%01101110001100010011人工智能搜索技术第68页3.4遗传算法初始种群x值适应度选择概率期望值实际复制数编号（随机产生）（无符号整数）f(x)=x2Pc

f(xi)/fA（或转轮法）

101101131690.1440.581

211000245760.4921.972

3010008640.0550.220

410011193610.3091.231

∑11701.004.004.0

平均(A)

2930.251.001.0

MAX5760.491.972.0初始种群染色体准备复制操作各项计算数据

人工智能搜索技术第69页（4）交叉:交叉详细分两步：①将新复制产生染色体随机两两匹配,称其为双亲染色体；②再把双亲染色体进行交叉繁殖。交叉实现:设染色体数字串长度为L，把L个数字位间空隙分别标识为：1，2，…，L－1随机从[1，L－1]中选取某一整数位置k，0<k<L交换双亲染色体交换点位置k右边部分，就形成了两个新数字符串（也能够只交换其中第k基因），得到了两个新染色体，又称之为下一代染色体。3.4遗传算法人工智能搜索技术第70页比如，将上例初始种群两个体A1=01┇10┇1A2=11┇00┇0假定从1到4间选取两个随机数，得到к1=2，к2=4，那么经过交叉操作之后将得到以下两组新数字符串A1#=01000A2#=11101

3.4遗传算法A3#=01100A4#=11001前一组数字串是使用к1=2,即将第2位后3～5位交换得到；后一组数字串是使用к2=4，即仅将第5位因子进行交换而得。人工智能搜索技术第71页3.4遗传算法编号复制操作后区配池匹配号(随机选取)交叉空隙位(随机选取)交叉后新种群新种群x值适应度f(x)=x21011012201000864211000121110129841311000441100125625410011341000016256总计（∑）1786平均(A)446.5最大值(MAX)

841复制、交叉操作各项数据

人工智能搜索技术第72页（5）变异:设变异概率取为0.001,则对于种群总共有20个基因位.期望变异串位数计算:20×0.001=0.02(位),故普通来说,该例中无基因位数值改变.从表11-2和11-3能够看出,每经过一次复制、交叉和变异操作后,目标函数最优值和平均值就会有所提升。在上例中，种群平均适