人工智能基础之搜索技术

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

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

第六章专家系统

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

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

3.1盲目搜索3.1.1图搜索策略例3.1从王某家族的四代中找王A的后代且其寿命为X的人

A,47B1,77A3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,513.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步中设置)。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。

3.1盲目搜索节点父辈节点3.1.1图搜索策略2.图搜索算法的几个重要名词（1）OPEN表与CLOSE表

OPEN表CLOSED表编号节点父辈节点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吗

?Y3.1盲目搜索3.1.1图搜索策略4.图搜索方法分析：图搜索过程的第8步对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的即盲目的(属于盲目搜索)，也可以用以后要讨论的各种启发思想或其它准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某些节点最终可能没有后继节点，所以OPEN表可能最后变成空表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点。

3.1盲目搜索3.1.2宽度优先搜索

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

例3.2

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

初始布局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深度优先搜索

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无子结点，即不可扩展，转(2)；(7)扩展结点n，将其所有子结点配上返回n的指针，并压入OPEN堆栈，转(2)。3.1盲目搜索3.1.4等代价搜索

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

如果所有的连接弧线具有相等的代价，那么等代价算法就简化为宽度优先搜索算法。3.2启发式搜索盲目搜索的不足：效率低，耗费空间与时间。

启发式搜索：利用问题域特性的信息（启发信息）进行搜索。3.2.1启发式搜索策略启发式信息按用途分为三种：（1）用于确定要扩展的下一个节点，避免盲目扩展。（2）在扩展一个节点的过程中，用于确定要生成哪一个或哪几个后继节点，避免盲目生成所有可能节点。（3）用于确定某些应该从搜索树中抛弃或修剪得节点。

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

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

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

3.2启发式搜索3.2.2有序搜索有序状态空间搜索算法：(1)把起始节点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表中，则用估价函数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)，即GOTO(2)。

3.2启发式搜索3.2.2有序搜索

开始把S放入OPEN表OPEN为空表？失败选取OPEN表中f值最小的节点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的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意解。

3.2启发式搜索3.2.2有序搜索例3.4：八数码难题,采用了简单的估价函数f(n)=d(n)+W(n)其中：d(n)是搜索树中节点n的深度；W(n)用来计算对应于节点n的数据库中错放的棋子个数。因此，起始节点棋局的f值等于0+4=4。

283164753.2启发式搜索3.2.2有序搜索283164752831647528314765283164752831476523184765283147658321476528371465231847652331847651238476512384765123784653.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*没有定义)。

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到某目标节点的一条最佳路径的代价之和。

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叫做启发函数。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*搜索算法直接目标就在于要找到问题的最优解及其解的路径，即便搜索效率有所降低也在所不惜。

3.2启发式搜索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？否是3.2启发式搜索3.2.3A*算法把SECCESSOR放入OPEN表，加入BESTNODE的后裔表g(SUCCESSOR)<g(OLD)？否重新确定OLD的父辈节点为BESTNODE，并修正父辈节点的g值和f值，记下g(OLD)SUCCESSOR∈CLOSED？否是SECCESSOR=OLD，把它添到BESTNODE的后继节点表中是否计算f值3.3博弈树搜索3.3.1博弈概述何谓博弈？博弈就是下棋、打牌、竞技、战争等一类竞争性智能活动。“二人零和非偶然性全信息”博弈

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

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

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

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

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

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

4820-14-13.3博弈树搜索3.3博弈树搜索3.3.3α-β剪枝技术基本思想：边生成博弈树边估算各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点。具体剪枝方法：（1）对于一个“与”节点MIN，若能估计出其倒推值上界β，并且这个β值不大于MIN的父辈节点（一定是“或”节点）的估计倒推值的下界α，即α≥β，则就不必要再扩展该MIN节点的其余子节点了。这一过程称为α剪枝。（2）对于一个“或”节点MAX，若能估计出其倒推值下界α，并且这个α值不小于MAX的父辈节点（一定是“与”节点）的估计倒推值的上界β，即α≥β，则就不必要再扩展该MAX节点的其余子节点了。这一过程称为β剪枝。3.3博弈树搜索3.3.3α-β剪枝技术从算法中看到：（1）MAX节点（包括起始节点）的α值永不减少。（2）MIN节点（包括起始节点）的β值永不增加。在搜索期间，α和β值的计算如下：（1）一个MAX节点的α值等于其后继节点当前最大的最终倒推值。（2）一个MIN节点的β值等于其后继节点当前最小的最终倒推值。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方○×3.3.3α-β剪枝技术3.3博弈树搜索×××○×○×○×○×○○×初始节点α=-1ABC-1β=-16-5=15-5=06-5=15-5=04-5=-15-6=-13.3.3α-β剪枝技术3.3博弈树搜索

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

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

4820-14-13.3.3α-β剪枝技术3.3博弈树搜索h(S0)=？441133–1–18810822-5-52244x≲55

4

×α×α

×β

×α

×α

×α

×α

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

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

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

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

3.4遗传算法遗传算法特点：遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文适者生存的理论，模拟自然进化过程来寻找所求问题的解答。遗传算法具有以下特点：

(1)遗传算法是对参数集合的编码而非针对参数本身进行进化；

(2)遗传算法是从问题解的编码组开始而非从单个解开始搜索；

(3)遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；

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

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

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是互不相同的。3.4遗传算法3.4.1遗传算法的基本原理2.适应度函数为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数（fitnessfunction）。TSP的目标是路径总长度为最短，自然地，路径总长度的倒数就可作为TSP问题的适应度函数:其中wn+1=w1适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。适应度函数的取值大小与求解问题对象的意义有很大的关系。

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

/∑fi。3.4遗传算法3.4.1遗传算法的基本原理3.遗传操作交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。产生一个1~7之间的随机数c，假设为3，则将P1和P2的低3位交换

10001110P1：11011001P2：3.4遗传算法3.4.1遗传算法的基本原理3.遗传操作

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

1010011013.4遗传算法3.4.1遗传算法的基本原理4.控制参数交叉发生的概率：0.6~0.95

变异的概率：0.001~0.01

种群的个数：30~100

个体的长度：定长和变长

3.4遗传算法3.4.2遗传算法的结构选择：由个体适应度值决定

的某个规则。交叉：按概率Pc进行变异：按概率Pm进行终止条件：①完成了预先给定的进化代数②种群中的最优个体在连续若干代

没有改进或平均适应度在连续若

干代基本没有改进开始初始化种群选择操作终止条件否适应度最有优个体计算适应度值交叉操作变异操作结束3.4遗传算法3.4.3遗传算法的性能

遗传算法求得的解是一满意解。影响解质量的因素：

种群的数量：太小缺少多样性，太多影响效率

适应度函数：提升优良个体的适应度

交叉和变异：不同的问题需构造性能更优的交叉和变异操作

交叉概率和变异概率：分析：对该问题虽然也可以采用枚举的方法来解决,但枚举法却是一种效率很低的方法.可运用遗传算法来求解该问题.解：首先对问题进行初始化，以获得初始种群;（1）确定适当的编码方案：将x编码表示为染色体的数字符号串。针对本题自变量x定义域,取值范围为[0，31],考虑采用二进制数来对其编码,由25=32,故使用5位无符号二进制数组成染色体数字字符串,用以表达变量x及问题的解答过程。

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

3.4遗传算法

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

0，（0≤K＜0.5）

1，（0.5≤K≤1）3.4遗传算法G=于是随机生成4个染色体的数字符串为：01101110000100010011从而构造了初始种群，完成了遗传算法的准备。3.4遗传算法表

初始种群染色体及对应的适应值

3.4遗传算法染色体标号

串

x

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

1

01101

169

14.4%

2

11000

576

49.2%

3

01000

64

5.5%

4

10011

361

30.9%

总计∑（初始种群值）

1170

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

011011100011000100113.4遗传算法

某个染色体是否被复制,可以通过概率决策法、适应度比例法或“轮盘赌”的随机方法来断定。对应轮盘赌转盘的随机方法,根据表6.1数据，绘制出的轮盘赌转盘,如图所示:

进化计算——基本遗传算法原理49.2﹪30.9%14.4%5.5%011011100011000100113.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初始种群染色体准备复制操作的各项计算数据

（4）交叉:交叉具体分两步：①将新复制产生的染色体随机两两匹配,称其为双亲染色体；②再把双亲染色体进行交叉繁殖。交叉的实现:设染色体数字串长度为L，把L个数字位间空隙分别标记为：1，2，…，L－1

随机从[1，L－1]中选取某一整数位置k，0<k<L交换双亲染色体交换点位置k右边的部分，就形成了两个新的数字符串（也可以只交换其中的第k基因），得到了两个新的染色体，又称之为下一代染色体。3.4遗传算法例如，将上例初始种群的两个体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位因子进行交换而得。3.4遗传算法编号复制操作后的区配池匹配号(随机选取)交叉空隙位(随机选取)交叉后新种群新种群x值适应度f(x)=x21011012201000864211000121110129841311000441100125625410011341000016256总计（∑）1786平均(A)446.5最大值(MAX)

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

（5）变异:设变异概率取为0.001,则对于种群总共有20个基因位.期望的变异串位数计算:20×0.001=0.02(位),

故一般来说,该例中无基因位数值的改变.从表11-2和11-3可以看出,每经过一次复制、交叉和变异操作后,目标函数的最优值和平均值就会有所提高。在上例中，种群的平均适应值从293增至446.5;最大的适应度数值从576增至841。特点：每经一次进化计算步骤,问题解答便向着最优方向前进了一步;若该过程一直进行下去,就将最终走向全局的最优解.可见进化计算的每一步操作简单,并且系统的求解过程是依照计算方法与规律来决定,与本源问题自身的特性很少相关。3.4遗传算法固体退火原理：固体内部粒子随着温度升高而变为无序，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，在常温时达到基态，内能减为最小。Metropolis准则：粒子在温度T时趋于平衡的概率=e-△E/(kT)其中，E为固体在温度T时的内能，△E为内能的改变量，k为波尔兹曼（Boltzmann）常数。

模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复进行“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解为所得近似最优解。退火过程由冷却进度表控制，包括控制参数的初值t及其衰减因子△t、每个t值时的迭代次数L和停止条件S。3.5模拟退火算法生物机体系统：脑神经系统、遗传系统、自然免疫系统和内分泌系统。免疫计算：模仿自然免疫系统而产生的一种新的计算理论和方法。

自然免疫系统：一个复杂的自适应系统，通过一套复杂的机制来重组基因，以产生相应入侵抗原的抗体；同时还具有学习和记忆功能，可以区分自身细胞和抗原细胞，并最终消灭抗原细胞。

人工免疫系统的研究：20世纪90年代，解决网络适应性问题、传感器网络故障诊断、病毒检测、机器学习。3.6免疫算法免疫算法（immunealgorithm）：在模仿生物免疫机制的基础上，综合基因进化机理，人工地构造的一类优化算法，它实现了类似于免疫系统自我调节功能和生成不同抗体的功能。

抗原（antigen）：在免疫算法中抗原指非最佳个体的基因，或者可能错误地基因；在免疫学中，抗原指有一种能够刺激机体产生相应抗体的物质。

疫苗（vanccine）：在免疫算法中疫苗指根据已有的先验知识得到的关于对最佳个体的一个估计值；在免疫学中，疫苗是一类能引起免疫应答反应的生物制剂，通常为蛋白质。

抗体（antibody）：在免疫算法中抗体是指根据疫苗修正某个个体基因所得到的新个体（新基因）；在免疫学中，抗体是一种具有免疫功能的球蛋白，是人体抵抗力最重要的组成部分。3.6免疫算法3.6免疫算法

当病原体入侵时，免疫系统首先要识别这一抗原，然后产生相应的抗体来消灭它。识别的过程实际上就是免疫细胞与抗原匹配并结合的过程，如果一个系统中所有抗原都被抗体识别（随后被消灭）了，那么这个系统就达到了最佳状态。识别的有限性：一个免疫细胞（抗体）不一定能够与所有的抗原匹配。

识别的多样性：一个免疫细胞可以识别多种不同的抗原。××××××××××××××××××××××××××××××××××××××××××××××××××××××××····免疫系统进化的目标：以最少的抗体数量覆盖几乎整个抗原空间。

亲和力：描述抗体和抗原之间的匹配程度（覆盖能力）。

排斥力：描述两个抗体之间的相异程度。

算法步骤：

（1）识别抗原。输入问题的目标函数和各种约束条件，作为免疫算法的抗原。

（2）产生初始抗体群。通常是在解空间中随机产生n个候选解作为初始抗体，n为抗体群众抗体的数目。

（3）计算亲和力和排斥力。分别计算每个抗体的亲和力以及各抗体之间排斥力。3.6免疫算法（4）产生新的抗体。通过免疫算子产生新的抗体，并计算新抗体的亲和力及其之间的排斥力。

（5）更新记忆能力。将与抗原亲和力高的抗体加入到记忆单元中，并淘汰与其排斥力最高的原有抗体。。

（6）判断是否满足停止条件。若新抗体中有与抗原相匹配的抗体，或以满足预定的停机条件则停机。否则转（7）。

（7）利用免疫算子产生新的抗体群。免疫算子包括选择、交叉和变异等操作。在选择时，给那些亲和力大的抗体赋予较大的选择概率。

（8）转（3）3.6免疫算法演讲完毕，谢谢观看！附录资料：人工智能简介​AboutTeachingPlan基本要求：人工智能是计算机科学中涉及研究、设计和应用智能机器的一个分支，是目前迅速发展的一门新兴学科，新思想新方法层出不穷。其基本思想是利用机器来模仿和执行人脑的功能，如判断、推理、证明、识别、感知、理解、设计、思考、规划、学习和问题求解等思维活动。对于培养学生计算机技术的应用能力，开阔思路和视野，有重要意义。

​AboutTeachingPlan因此，要求学生掌握知识表示和问题求解的几种常用方法，尤其是不确定性推理；掌握机器学习基本概念，了解几种机器学习方法尤其是神经网络学习方法；掌握专家系统的概念，了解专家系统设计方法，掌握一些智能控制方法，了解国内外人工智能研究尤其是机器人的最新进展；具有一定的人工智能编程设计能力（利用Lisp或Prolog语言）。​AboutTeachingPlan课程内容以及学时分配人工智能引论(1) 人工智能概念及与计算机的关系，研究途径、内容和应用领域概况介绍，其他最新材料。符号主义、连接主义、行为主义三大流派人工智能数学基础(1)知识表示方法（2） 状态空间法、问题归约法，谓词逻辑法、产生式表示法（动物识别系统）；CLIPS语言；语义网络法、框架法（这是结构化表示）；剧本、过程、Petri网、面向对象的表示。​AboutTeachingPlan 搜索技术和策略（3-4）状态空间法，盲目搜索和启发式搜索，A*算法；海伯伦理论、消解原理和策略；与\或形推理和搜索策略；其他求解技术。 不确定推理技术（3-4）主观Bayes理论；可信度方法和证据理论；系统组织技术；非单调推理；Rete快速算法；模糊推理技术；基于语义网络和框架不确定推理； 专家系统（2）专家系统概念、结构和知识获取；黑板模型、知识组织、管理及系统建造和开发工具；专家系统举例及编程。

人工智能程序设计（1）人工智能语言基本机制：LISP和PROLOG。​AboutTeachingPlan 模式识别导论（3）模式识别专题：概率模式识别。模式识别专题：结构模式识别 机器学习（1）：机械,解释经验,事例,归纳,概念,类比学习等；统计,结构,模糊模式识别。 专题讲座（3次） 1)神经网络基本理论和应用 (史奎凡课程：安排于人工智能理论与应用课程内)； 2)智能体（Agent）； 3)自然语言处理； 4)智能控制和机器人科学 智能控制的结构理论和研究领域，智能控制系统及应用示例；机器人规划、机器视觉和自然语言理解等。​AboutTeachingPlan 实践：1) 搜索技术和策略2) 不确定推理技术3) 专家系统：动物识别系统4) 模式识别技术5) 调研： 搜索技术和策略、不确定推理技术、统计模式识别、机器学习等四个领域进展报告。​ChapterOne:BriefIntroductiontoArtificialIntelligence1.WhatisAI?人工智能（ArtificialIntelligence,AI）是当前科学技发展的一门前沿学科，同时也是一门新思想，新观念，新理论，新技术不断出现的新兴学科以及正在发展的学科。它是在计算机科学，控制论，信息论，神经心理学，哲学，语言学等多种学科研究的基础发展起来的，因此又可把它看作是一门综合性的边缘学科。它的出现及所取得的成就引起了人们的高度重视,并取得了很高的评价。有的人把它与空间技术，原子能技术一起并誉为20世纪的三大科学技术成就。​Intelligence智能是知识与智力的总合。 知识——智能行为的基础； 智力——获取知识并运用知识求解问题的能力。智能具有以下特征：(1)具有感知能力——指人们通过视觉、听觉、触觉、味觉、嗅觉等感觉器官感知外部世界的能力；(2)具有记忆与思维的能力——这是人脑最重要的功能，亦是人之所以有智能的根本原因；(3)具有学习能力及自适应能力；(4)具有行为能力。ArtificialIntelligence人工智能——计算机科学的一个分支，是智能计算机系统，即人类智慧在机器上的模拟，或者说是人们使机器具有类似于人的智慧（对语言能理解、能学习、能推理）。​2.BriefHistoryofAI (1) 孕育（1956年前）古希腊的Aristotle（亚里士多德）（前384-322），给出了形式逻辑的基本规律。英国的哲学家、自然科学家Bacon（培根）（1561-1626），系统地给出了归纳法。“知识就是力量”德国数学家、哲学家Leibnitz（布莱尼茨）（1646-1716）。提出了关于数理逻辑的思想，把形式逻辑符号化，从而能对人的思维进行运算和推理。做出了能做四则运算的手摇计算机英国数学家、逻辑学家Boole（布尔）（1815-1864）实现了布莱尼茨的思维符号化和数学化的思想，提出了一种崭新的代数系统——布尔代数。​美籍奥地利数理逻辑学家Godel（哥德尔）（1906-1978），证明了一阶谓词的完备性定；任何包含初等数论的形式系统，如果它是无矛盾的，那么一定是不完备的。意义在于，人的思维形式化和机械化的某种极限，在理论上证明了有些事是做不到的。英国数学家Turing(图灵)（1912-1954）,1936年提出了一种理想计算机的数学模型（图灵机），1950年提出了图灵试验，发表了“计算机与智能”的论文。图灵奖。美国数学家Mauchly，1946发明了电子数字计算机ENIAC美国神经生理学家McCulloch，建立了第一个神经网络数学模型。美国数学家Shannon（香农）,1948年发表了《通讯的数学理论》，代表了“信息论”的诞生。​ (2) 形成（1956-1969）1956年提出了“ArtificialIntelligence（人工智能）”1956年夏由麻省理工学院的J.McCarthy、M.L.Minsky,IBM公司信息研究中心的N.Rochester,贝尔实验室的C.E.Shannon共同发起，邀请了Moore,Samuel,Selfridge,Solomonff,Simon,Newell等人，10位数学家、信息学家、心理学家、神经生理学家、计算机科学家，在Dartmouth大学召开了一次关于机器智能的研讨会，会上McCarthy提议正式采用了ArtificialIntelligence（人工智能）这一术语。这次会议，标志着人工智能作为一门新兴学科正式诞生了。 McCarthy（麦卡锡）——人工智能之父。这次会议之后的10年间，人工智能的研究取得了许多引人瞩目的成就.机器学习方面：塞缪尔于1956年研制出了跳棋程序，该程序能从棋谱中学习，也能从下棋实践中提高棋艺；​在定理证明方面：王浩于1958年在IBM机上证明了《数学原理》中有关命题演算的全部定理（220条），还证明了谓词演算中150条定理85%；1965年，鲁宾逊（Robinson）提出了消解原理；在模式识别方面：1959年塞尔夫里奇推出了一个模式识别程序；1965年罗伯特（Robert）编制出可辨别积木构造的程序；在问题求解方面：1960年纽厄尔等人通过心理学试验总结出了人们求解问题的思维规律，编制了通用问题求解程序GPS,可以用来求解11种不同类型的问题；在专家系统方面：斯坦福大学的费根鲍姆（E.A.Feigenbaum）自1965年开始进行专家系统DENDRAL（化学分析专家系统），1968年完成并投入使用；在人工智能语言方面：1960年McCarthy等人建立了人工智能程序设计语言Lisp，该语言至今仍是建造智能系统的重要工具；1969年成立了国际人工智能联合会议（InternationalJointConferencesOnArtificialIntelligence）​ (3) 发展（1970年以后）70年代，开始从理论走向实践，解决一些实际问题。同时很快就发现问题：归结法费时、下棋赢不了全国冠军、机器翻译一团糟。以Feigenbaum为首的一批年轻科学家改变了战略思想，1977年提出知识工程的概念，以知识为基础的专家咨询系统开始广泛的应用。著名专家系统的有：DENDRAL化学分析专家系统（斯坦福大学1968）MACSYMA符号数学专家系统（麻省理工1971）MYCIN诊断和治疗细菌感染性血液病的专家咨询系统（斯坦福大学1973）CASNET(CausalASsciationalNetwork)诊断和治疗青光眼的专家咨询系统（拉特格尔斯（Rutgers）大学70年代中）CADUCEUS(原名INTERNIST)医疗咨询系统（匹兹堡大学）；HEARSAYI和II语音理解系统（卡内基-梅隆大学）PROSPECTOR地质勘探专家系统（斯坦福大学1976）XCON计算机配置专家系统（卡内基-梅隆大学1978）​•80年代，人工智能发展达到阶段性的顶峰。•87,89年世界大会有６－７千人参加。硬件公司有上千个。并进行Lisp硬件、Lisp机的研究。•在专家系统及其工具越来越商品化的过程中,国际软件市场上形成了一门旨在生产和加工知识的新产业——知识产业。应该说，知识工程和专家系统是近十余年来人工智能研究中最有成就的分支之一。•同年代，1986年Rumlhart领导的并行分布处理研究小组提出了神经元网络的反向传播学习算法，解决了神经网络的根本问题之一。从此，神经网络的研究进入新的高潮。•90年代，计算机发展趋势为小型化、并行化、网络化、智能化。•人工智能技术逐渐与数据库、多媒体等主流技术相结合，并融合在主流技术之中，旨在使计算机更聪明、更有效、与人更接近。•日本政府于1992年结束了为期十年的称为“知识信息处理体统”的第五代计算机系统研究开发计划。并开始了为期十年的实况计算（RealWordComputing）计划。​3.ResearchObjectsandMainContents

(1)人工智能的研究目标

人工智能的长期研究目标：构造智能计算机。

人工智能的近期研究目标：使现有的电子计算机更聪明，更有用，使它不仅能做一般的数值计算及非数值信息的数据处理，而且能运用知识处理问题，能模拟人类的部分智能行为。​(2)人工智能研究的基本内容

1.机器感知以机器视觉与机器听觉为主。机器感知是机器获取外部信息的基本途径，是使机器具有智能不可或缺的组成部分，对此人工智能中已形成两个专门的研究领域——

模式识别和自然语言理解。2.机器思维指通过感知的外部信息及机器内部的各种工作信息进行有目的的处理。主要开展以下几方面的研究：(1)知识表示(2)知识的组织，累计，管理技术(3)知识的推理(4)各种启发式搜索及控制策略(5)神经网络，人脑的结构及其工作原理​3.机器学习

使计