《人工智能基础03--搜索技术[教育课件]》由会员分享，可在线阅读，更多相关《人工智能基础03--搜索技术[教育课件]（79页珍藏版）》请在金锄头文库上搜索。
1、合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室1/79目录o第一章第一章绪论o第二章第二章知知识表示表示 o第三章搜索技第三章搜索技术o第四章推理技第四章推理技术o第五章机器学第五章机器学习 o第六章第六章专家系家系统 o第七章自第七章自动规划系划系统o第八章第八章 自然自然语言理解言理解o第九章第九章 智能控制智能控制o第十章第十章 人工智能程序人工智能程序设计技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工
2、智能与数据挖掘研究室2/793.1 盲目搜索盲目搜索：即盲目搜索：即 无信息搜索无信息搜索 宽度度优先与深度先与深度优先先3.1.1 图搜索策略搜索策略 图搜索策略可看作一种在搜索策略可看作一种在图中中寻找路径的方法。初始找路径的方法。初始节点点和目和目标节点分点分别代表初始数据代表初始数据库和和满足足终止条件的数据止条件的数据库。求。求得把一个数据得把一个数据库变换为另一数据另一数据库的的规则序列序列问题就等价于求就等价于求得得图中的一条路径中的一条路径问题。研究。研究图搜索的一般策略，能搜索的一般策略，能够给出出图搜索搜索过程的一般步程的一般步骤。 技术课件合肥工业大学合肥工业大学合肥工业
3、大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室3/793.1 盲目搜索3.1.1 图搜索策略搜索策略 例例3.1 从王某家族的四代中找王从王某家族的四代中找王A的后代且其寿命的后代且其寿命为X的人的人 A,47B1,77A3,52B2,65C2,87C1,96D1,77E1,57E2,92F1,32G1,27H1,51技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室4/793.1 盲目搜索3.1.1 图搜索策略搜索策略1.
4、图搜索搜索(GRAPHSEARCH)的一般的一般过程程(1) 建立一个只含有起始建立一个只含有起始节点点S的搜索的搜索图G，把，把S放到一个叫做放到一个叫做OPEN的未的未扩展展节点表中。点表中。(2) 建立一个叫做建立一个叫做CLOSED的已的已扩展展节点表，其初始点表，其初始为空表。空表。(3) LOOP：若：若OPEN表是空表，表是空表，则失失败退出。退出。(4) 选择OPEN表上的第一个表上的第一个节点，把它从点，把它从OPEN表移出并放表移出并放进CLOSED表中。称此表中。称此节点点为节点点n。(5) 若若n为一目一目标节点，点，则有解并成功退出，此解是追踪有解并成功退出，此解是追
5、踪图G中沿中沿着指着指针从从n到到S这条路径而得到的条路径而得到的(指指针将在第将在第7步中步中设置置)。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室5/793.1 盲目搜索3.1.1 图搜索策略搜索策略1.图搜索搜索(GRAPHSEARCH)的一般的一般过程程(6) 扩展展节点点n，同，同时生成不是生成不是n的祖先的那些后的祖先的那些后继节点的集合点的集合M。把。把M的的这些成些成员作作为n的后的后继节点添入点添入图G中。中。(7) 对那些未曾在那些未曾在G中出中出现过的的(既未曾在
6、既未曾在OPEN表上或表上或CLOSED表上出表上出现过的的)M成成员设置一个通向置一个通向n的指的指针。把。把M的的这些成些成员加加进OPEN表。表。对已已经在在OPEN或或CLOSED表上的每表上的每一个一个M成成员，确定是否需要更改通到，确定是否需要更改通到n的指的指针方向。方向。对已在已在CLOSED表上的每个表上的每个M成成员，确定是否需要更改，确定是否需要更改图G中通向它中通向它的每个后裔的每个后裔节点的指点的指针方向。方向。(8) 按某一任意方式或按某个探按某一任意方式或按某个探试值，重排，重排OPEN表。表。(9) GO LOOP。 技术课件合肥工业大学合肥工业大学合肥工业大学
7、合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室6/793.1 盲目搜索节点节点父辈节点父辈节点3.1.1 图搜索策略搜索策略2.图搜索算法的几个重要名搜索算法的几个重要名词（1）OPEN表与表与CLOSE表表 OPEN表表 CLOSED表表编号编号节点节点父辈节点父辈节点技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室7/793.1 盲目搜索3.1.1 图搜索策略搜索策略3. 搜索搜索图与搜索与搜索树搜索搜索过程框程框图开 始
8、初始化：S放入OPEN表，CLOES表置空, n=1OPEN表中的第一个结点 n移至CLOSE表若n 的后继未曾在搜索图 G中出现，则将其放入OPEN表的末端，并提供返回结点 n的指针, 置n=n+1根据后继结点在搜索图 G中的出现情况修改指针方向依某种准则重新排序 OPEN表失败成功NYNOPEN为空表NULL ？n=目标结点D吗 ?Y技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室8/793.1 盲目搜索3.1.1 图搜索策略搜索策略4.图搜索方法分析：搜索方法分析：图搜索搜索过程的第
9、程的第8步步对OPEN表上的表上的节点点进行排序，以便能行排序，以便能够从从中中选出一个出一个“最好最好”的的节点作点作为第第4步步扩展用。展用。这种排序可以种排序可以是任意的即盲目的是任意的即盲目的(属于盲目搜索属于盲目搜索)，也可以用以后要，也可以用以后要讨论的各的各种启种启发思想或其它准思想或其它准则为依据依据(属于启属于启发式搜索式搜索)。每当被。每当被选作作扩展的展的节点点为目目标节点点时，这一一过程就宣告成功程就宣告成功结束。束。这时，能能够重重现从起始从起始节点到目点到目标节点的点的这条成功路径，其条成功路径，其办法是从法是从目目标节点按指点按指针向向S返回追溯。当搜索返回追溯。
10、当搜索树不再剩有未被不再剩有未被扩展的展的端端节点点时，过程就以失程就以失败告告终(某些某些节点最点最终可能没有后可能没有后继节点，所以点，所以OPEN表可能最后表可能最后变成空表成空表)。在失。在失败终止的情况下，止的情况下，从起始从起始节点出点出发，一定达不到目，一定达不到目标节点。点。 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室9/793.1 盲目搜索3.1.2 宽度度优先搜索先搜索 定定义3.1 如果搜索是以接近起始如果搜索是以接近起始节点的程度依次点的程度依次扩展展节点的，
11、点的，那么那么这种搜索就叫做种搜索就叫做宽度度优先搜索（先搜索（breadth-first search)技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室10/793.1 盲目搜索3.1.2 宽度度优先搜索先搜索宽度度优先搜索算法先搜索算法(1) 把起始把起始节点放到点放到OPEN表中表中(如果如果该起始起始节点点为一目一目标节点，点，则求得一个解答求得一个解答)。(2) 如果如果OPEN是个空表，是个空表，则没有解，失没有解，失败退出；否退出；否则继续。(3) 把第一个把第一个节点点(节
12、点点n)从从OPEN表移出，并把它放入表移出，并把它放入CLOSED的的扩展展节点表中。点表中。(4) 扩展展节点点n。如果没有后。如果没有后继节点，点，则转向上述第向上述第(2)步。步。(5) 把把n的所有后的所有后继节点放到点放到OPEN表的末端，并提供从表的末端，并提供从这些后些后继节点回到点回到n的指的指针。(6) 如果如果n的任一个后的任一个后继节点是个目点是个目标节点，点，则找到一个解答，找到一个解答，成功退出；否成功退出；否则转向第向第(2)步。步。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人
13、工智能与数据挖掘研究室11/793.1 盲目搜索3.1.2 宽度度优先搜索先搜索 例例3.2 八数八数码问题操操作作规定定: 允允许空空格格四四周周上上、下下、左左、右右的的数数码块移移入入空空格格中，不中，不许斜方向移斜方向移动，不，不许返回先返回先辈结点。点。 初始布局初始布局S和目和目标状状态D如下如下图所示：所示： 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室12/793.1 盲目搜索3.1.2 宽度度优先搜索先搜索 例例3.2 八数八数码问题技术课件合肥工业大学合肥工业大学合
14、肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室13/793.1 盲目搜索3.1.3 深度深度优先搜索先搜索深度深度优先算法步先算法步骤：(1) 初始初始结点点S放到未放到未扩展展节点点OPEN中；中； (2) 若若OPEN为空，空，则搜索失搜索失败，问题无解；无解； (3) 弹出出OPEN表中最表中最顶端端结点放到点放到CLOSE表中，并表中，并给出出顺序序编号号n； (4) 若若n为目目标结点点D，则搜索成功，搜索成功，问题有解；有解； (5) 若若n无子无子结点，点，转(2)；(6) 扩展展n结点，将其所有子点，将其
15、所有子结点配上返回点配上返回n的指的指针，并按，并按次序次序压入入OPEN堆堆栈，转(2) 。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室14/793.1 盲目搜索3.1.3 深度深度优先搜索先搜索 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室15/793.1 盲目搜索3.1.3 深度深度优先搜索先搜索有界深度有界深度优先搜索先搜索： 引入搜索深度限制引入搜索深度限制值d，使深
16、度使深度优先搜索先搜索过程具有完程具有完备性性 。设定搜索深度限制定搜索深度限制d=5，问题同深度同深度优先算法中的八数先算法中的八数码问题(2)(2)。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室16/793.1 盲目搜索3.1.3 深度深度优先搜索先搜索 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室17/793.1 盲目搜索3.1.3 深度深度优先搜索先搜索有界深度有界深度
17、优先算法步先算法步骤：(1)(1)初始初始结点点S S放入堆放入堆栈OPEN中；中；(2)(2)若若OPEN为空，空，则搜索失搜索失败，问题无解；无解；(3)(3)弹出出OPEN中中栈顶结点点n n，放入，放入CLOSE表中，并表中，并给出出顺序序编号号n n；(4)(4)若若n n为目目标结点点D D，则搜索成功，搜索成功，问题有解；有解；(5)(5)若若n n的深度的深度d(n)=dd(n)=d，则转(2) (2) ；(6)(6)若若n n无子无子结点，即不可点，即不可扩展，展，转(2) (2) ；(7)(7)扩展展结点点n n，将其所有子，将其所有子结点配上返回点配上返回n n的指的指针
18、，并，并压入入OPEN堆堆栈，转(2) (2) 。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室18/793.1 盲目搜索3.1.4 等代价搜索等代价搜索 宽度度优先搜索可被推广用来解决先搜索可被推广用来解决寻找从起始状找从起始状态至目至目标状状态的具有最小代价的路径的具有最小代价的路径问题，这种推广了的种推广了的宽度度优先搜索算法先搜索算法叫做等代价搜索算法叫做等代价搜索算法。等代价搜索中的几个等代价搜索中的几个记号号 起始起始节点点记为S； 从从节点点i到它的后到它的后继节点点j的的
19、连接弧接弧线代价代价记为c(i，j)； 起始起始节点点S到任一到任一节点点i的路径代价的路径代价记为g(i)。 如果所有的如果所有的连接弧接弧线具有相等的代价，那么等代价算法就具有相等的代价，那么等代价算法就简化化为宽度度优先搜索算法先搜索算法。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室19/793.2 启发式搜索盲目搜索的不足：效率低，耗盲目搜索的不足：效率低，耗费空空间与与时间。 启启发式搜索：利用式搜索：利用问题域特性的信息（启域特性的信息（启发信息）信息）进行搜索。行搜索。3
20、.2.1 启启发式搜索策略式搜索策略启启发式信息按用途分式信息按用途分为三种：三种： （1）用于确定要）用于确定要扩展的下一个展的下一个节点，避免盲目点，避免盲目扩展。展。 （2）在）在扩展一个展一个节点的点的过程中，用于确定要生成哪一个或程中，用于确定要生成哪一个或哪几个后哪几个后继节点，避免盲目生成所有可能点，避免盲目生成所有可能节点。点。 （3）用于确定某些）用于确定某些应该从搜索从搜索树中抛弃或修剪得中抛弃或修剪得节点。点。 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室20/7
21、93.2 启发式搜索 有序搜索（有序搜索（ordered search）：利用第一种启）：利用第一种启发信息，信息，总是是选择“最有希望最有希望”的的节点作点作为下一个被下一个被扩展的展的节点。点。 估价函数（估价函数（evaluation function )：估算：估算节点点“希望希望”的量的量度，度，这种量度叫做估价函数。种量度叫做估价函数。 建立估价函数的一般方法：建立估价函数的一般方法：试图确定一个确定一个处在最佳路径上在最佳路径上的的节点的概率；提出任意点的概率；提出任意节点与目点与目标集之集之间的距离量度或差的距离量度或差别量度；或者在棋量度；或者在棋盘式的博弈和式的博弈和难题中
22、根据棋局的某些特点来决中根据棋局的某些特点来决定棋局的得分数。定棋局的得分数。这些特点被些特点被认为与向目与向目标节点前点前进一步的希一步的希望程度有关。望程度有关。 f(n)表示表示节点点n的估价函数的估价函数值 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室21/793.2 启发式搜索3.2.2 有序搜索有序搜索 用估价函数用估价函数f来排列来排列GRAPHSEARCH第第8步中步中OPEN表上表上的的节点。点。应用某个算法用某个算法(例如等代价算法例如等代价算法)选择OPEN表上具
23、有表上具有最小最小f值的的节点作点作为下一个要下一个要扩展的展的节点。点。这种搜索方法叫做种搜索方法叫做有序搜索有序搜索或或最佳最佳优先搜索先搜索(best-first search)，而其算法就叫做，而其算法就叫做有序搜索算法有序搜索算法或或最佳最佳优先算法先算法。 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室22/793.2 启发式搜索3.2.2 有序搜索有序搜索有序状有序状态空空间搜索算法：搜索算法： (1) 把起始把起始节点点S放到放到OPEN表中，表中，计算算f(S)并把其并
24、把其值与与节点点S联系起来。系起来。 (2) 如果如果OPEN是个空表，是个空表，则失失败退出，无解。退出，无解。 (3) 从从OPEN表中表中选择一个一个f值最小的最小的节点点i。结果有几个果有几个节点点合格，当其中有一个合格，当其中有一个为目目标节点点时，则选择此目此目标节点，否点，否则就就选择其中任一个其中任一个节点作点作为节点点i。 (4) 把把节点点i从从OPEN表中移出，并把它放入表中移出，并把它放入CLOSED的的扩展展节点表中。点表中。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据
25、挖掘研究室23/793.2 启发式搜索3.2.2 有序搜索有序搜索(5) 如果如果i是个目是个目标节点，点，则成功退出，求得一个解。成功退出，求得一个解。(6) 扩展展节点点i，生成其全部后，生成其全部后继节点。点。对于于i的每一个后的每一个后继节点点j： (a) 计算算f(j)。 (b) 如果如果j既不在既不在OPEN表中，又不在表中，又不在CLOSED表中，表中，则用用估价函数估价函数f把它添入把它添入OPEN表。从表。从j加一指向其父加一指向其父辈节点点i的指的指针，以便一旦找到目以便一旦找到目标节点点时记住一个解答路径。住一个解答路径。 (c) 如果如果j已在已在OPEN表上或表上或C
26、LOSED表上，表上，则比比较刚刚对j计算算过的的f值和前面和前面计算算过的的该节点在表中的点在表中的f值。如果新的。如果新的f值较小，小，则技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室24/793.2 启发式搜索3.2.2 有序搜索有序搜索(i) 以此新以此新值取代旧取代旧值。(ii) 从从j指向指向i，而不是指向它的父，而不是指向它的父辈节点。点。(iii) 如果如果节点点j在在CLOSED表中，表中，则把它移回把它移回OPEN表。表。(7) 转向向(2)，即，即GO TO(2)。
27、 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室25/793.2 启发式搜索3.2.2 有序搜索有序搜索开始开始把把S放入放入OPEN表表OPEN为空表？为空表？失败失败选取选取OPEN表中表中f值最小值最小的节点的节点i，放入，放入CLOSED表表i=Sg？成功成功是是是是扩展扩展i得后继节点得后继节点j，计算，计算f(j)，提，提供返回供返回i的指针，利用的指针，利用f(j)对对OPEN表重新排序调整父子关系及指针表重新排序调整父子关系及指针技术课件合肥工业大学合肥工业大学合肥工业大
28、学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室26/793.2 启发式搜索3.2.2 有序搜索有序搜索宽度度优先搜索、等代价搜索和深度先搜索、等代价搜索和深度优先搜索先搜索统统是有序是有序搜索技搜索技术的特例。的特例。对于于宽度度优先搜索，先搜索，选择f(i)作作为节点点i的深的深度。度。对于等代价搜索，于等代价搜索，f(i)是从起始是从起始节点至点至节点点i这段路径的代段路径的代价。价。 有序搜索的有效性直接取决于有序搜索的有效性直接取决于f的的选择，如果，如果选择的的f不不合适，有序搜索就可能失去一个最好的解甚至全部的解。如
29、果合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么没有适用的准确的希望量度，那么f的的选择将涉及两个方面的将涉及两个方面的内容：一方面是一个内容：一方面是一个时间和空和空间之之间的折衷方案；另一方面是的折衷方案；另一方面是保保证有一个最有一个最优的解或任意解。的解或任意解。 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室27/793.2 启发式搜索3.2.2 有序搜索有序搜索例例3.4：八数：八数码难题, 采用了采用了简单的估价函数的估价函数 f(n)
30、=d(n)+W(n)其中：其中：d(n)是搜索是搜索树中中节点点n的深度；的深度；W(n)用来用来计算算对应于于节点点n的数据的数据库中中错放的棋子个数。因此，起始放的棋子个数。因此，起始节点棋局点棋局的的f值等于等于0+4=4。 2 8 31 6 475技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室28/793.2 启发式搜索3.2.2 有序搜索有序搜索2 8 31 6 4752 8 31 6 47 52 8 3147 6 52 8 31 6 47 52 8 31 47 6 5231
31、8 47 6 52 8 31 47 6 58 32 1 47 6 52 8 37 1 46 52 31 8 47 6 52 3 31 8 47 6 51 2 38 47 6 51 2 3847 6 51 2 37 8 46 5技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室29/793.2 启发式搜索3.2.3 A*算法算法A*算法是一种有序搜索算法，其特点在于算法是一种有序搜索算法，其特点在于对估价函数的定估价函数的定义上。上。 1. A*算法的估价函数算法的估价函数 k(ni，nj)：
32、表示任意两个：表示任意两个节点点ni和和nj之之间最小代价路径的最小代价路径的实际代价代价(对于两于两节点点间没有通路的没有通路的节点，函数点，函数k没有定没有定义)。 k(n,ti)：从：从节点点n到某个具体的目到某个具体的目标节点点ti，某一条最小代，某一条最小代价路径的代价。价路径的代价。 h*(n)：表示整个目：表示整个目标节点集合点集合ti上所有上所有k(n,ti)中最小中最小的一个，因此，的一个，因此，h*(n)就是从就是从n到目到目标节点最小代价路径的代价，点最小代价路径的代价，而且从而且从n到目到目标节点能点能够获得得h*(n)的任一路径就是一条从的任一路径就是一条从n到到某个
33、目某个目标节点的最佳路径点的最佳路径(对于任何不能到达目于任何不能到达目标节点的点的节点点n，函数，函数h*没有定没有定义)。 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室30/793.2 启发式搜索3.2.3 A*算法算法定定义g* 为g*(n)=k(S,n)从已知起始从已知起始节点点S到任意到任意节点点n的一条最佳路径代价。的一条最佳路径代价。定定义函数函数f*， f*(n)=g*(n)+h*(n)使得在任一使得在任一节点点n上其函数上其函数值f*(n)就是从就是从节点点S到到节点
34、点n的一条的一条最佳路径的最佳路径的实际代价加上从代价加上从节点点n到某目到某目标节点的一条最佳路点的一条最佳路径的代价之和。径的代价之和。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室31/793.2 启发式搜索3.2.3 A*算法算法 希望估价函数希望估价函数f是是f*的一个估的一个估计，此估，此估计可由下式可由下式给出：出： f(n)=g(n)+h(n)其中：其中：g是是g*的估的估计；h是是h*的估的估计。 对于于g(n)：一个明：一个明显的的选择就是搜索就是搜索树中从中从S到到
35、n这段路径的段路径的代价，代价，这一代价可以由从一代价可以由从n到到S寻找指找指针时，把所遇到的各段弧，把所遇到的各段弧线的代价加起来的代价加起来给出出(这条路径就是到目前条路径就是到目前为止用搜索算法找到止用搜索算法找到的从的从S到到n的最小代价路径的最小代价路径)。这个定个定义包含了包含了g(n)g*(n)。 h(n)：对 h*(n)的估的估计，依，依赖于有关于有关问题的的领域的启域的启发信息。信息。这种信息可能与八数种信息可能与八数码难题中的函数中的函数W(n)所用的那种信息相似。所用的那种信息相似。把把h叫做启叫做启发函数。函数。 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大
36、学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室32/793.2 启发式搜索3.2.3 A*算法算法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(
37、x)为启启发函数的函数的A算法，称算法，称为A*算算法。当法。当h=0时，A*算法就算法就变为有序搜索算法。有序搜索算法。 A A算法和算法和A*A*搜索算法的目标有所不同：搜索算法的目标有所不同： A A搜索算法虽然希搜索算法虽然希望能找到问题的最优解，但主要追求的是求解效率；而望能找到问题的最优解，但主要追求的是求解效率；而A*A*搜索搜索算法直接目标就在于要找到问题的最优解及其解的路径，即便算法直接目标就在于要找到问题的最优解及其解的路径，即便搜索效率有所降低也在所不惜。搜索效率有所降低也在所不惜。 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智
38、能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室33/793.2 启发式搜索3.2.3 A*算法算法开始开始把把S放入放入OPEN表表,记记f=hOPEN为空表？为空表？失败失败选取选取OPEN表中未设置过的具有最小表中未设置过的具有最小f值值的节点的节点BESTNODE，放入，放入CLOSED表表BESTNODE=Sg？成功成功是是是是扩展扩展BESTNODE，产生后继节点，产生后继节点SUVVESSOR建立从建立从SUCCESSOR返回返回BESTNODE的指针的指针计算计算g(SUCCESSOR)=g(BESTNODE)+h(BESTNODE)_SUCCESSOR)SU
39、CCESSOROPEN？否否是是技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室34/793.2 启发式搜索3.2.3 A*算法算法把把SECCESSOR放入放入OPEN表，表，加入加入BESTNODE的后裔表的后裔表g(SUCCESSOR)g(OLD)？否否重新确定重新确定OLD的父辈节点为的父辈节点为BESTNODE，并修正父辈节点的并修正父辈节点的g值和值和f值，记下值，记下g(OLD)SUCCESSORCLOSED？否否是是SECCESSOR=OLD，把它添到，把它添到BESTNO
40、DE的后继节点表中的后继节点表中是是否否计算计算f值值技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室35/793.3 博弈树搜索3.3.1 博弈概述博弈概述 何何何何谓谓博弈？博弈？博弈？博弈？博弈就是下棋、打牌、博弈就是下棋、打牌、竞技、技、战争等一争等一类竞争争性智能活性智能活动。 “二人零和非偶然性全信息二人零和非偶然性全信息”博弈博弈 （1 1）二人零和：）二人零和：）二人零和：）二人零和：对垒的的MAX、MIN双方双方轮流采取行流采取行动，博，博弈的弈的结果只有三种情况：果只有
41、三种情况：MAX方方胜，MIN方方胜，和局。，和局。 （2 2）全信息：）全信息：）全信息：）全信息：在在对垒过程中，任何一方都了解当前格局及程中，任何一方都了解当前格局及过去的去的历史。史。 （3 3）非偶然性：）非偶然性：）非偶然性：）非偶然性：任何一方在采取行任何一方在采取行动前都要根据当前的前都要根据当前的实际情况，情况，进行得失分析，行得失分析，选取取对自己最自己最为有利而有利而对对方最方最为不利不利的的对策，不存在策，不存在“碰运气碰运气”，“侥幸幸”及及“偶然失偶然失误”等随机等随机因素。因素。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工
42、智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室36/793.3 博弈树搜索3.3.1 博弈概述博弈概述 参加博弈的各方都希望己方取得参加博弈的各方都希望己方取得胜利。因此，当一方面利。因此，当一方面临多多个行个行动方案方案选择时，博弈的各方博弈的各方总是要挑是要挑选对自己最自己最为有利而有利而对对方最不利的那个行方最不利的那个行动方案。方案。 假如假如MAXMAX方的目方的目方的目方的目标标：尽可能使自己达到最大（或最高）的分尽可能使自己达到最大（或最高）的分数分枝数分枝节点，点，可用可用“ “或或或或” ”关系来描述，称之关系来描述，称之为MAX方方节点；点； 而当而当
43、轮到到MIN方行方行动时，MINMIN方的目方的目方的目方的目标标：尽可能使尽可能使MIN方方获得最小（或最低）的分数分枝得最小（或最低）的分数分枝节点，点，这对MIN方来方来说，这些行些行动方案或分数分枝方案或分数分枝节点之点之间，可以用，可以用“ “与与与与” ”关系来描述，是由关系来描述，是由MINMIN方方方方自主自主进行控制的，故又称之行控制的，故又称之为MIN节点。点。 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室37/793.3 博弈树搜索3.3.1 博弈概述博弈概述 把
44、上述双方逐把上述双方逐层交替的博弈交替的博弈过程用与程用与/或或树（图）描述表达）描述表达出来，就得到了一棵具有出来，就得到了一棵具有“与与/或或”节点交替出点交替出现的博弈的博弈树。博弈博弈树有如下特点：有如下特点：（1）博弈的初始格局是初始）博弈的初始格局是初始节点。点。（2）在博弈）在博弈树中，由于中，由于双方双方双方双方轮轮流地流地流地流地扩扩展展展展节节点，点，点，点，“ “或或或或” ”节节点和点和点和点和“ “与与与与” ”节节点逐点逐点逐点逐层层交替出交替出交替出交替出现现。如果自己一方如果自己一方扩展的展的节点之点之间是是“或或”关系，关系，则对方方扩展的展的节点之点之间是是
45、“与与”关系。关系。（3）把本方）把本方获胜的的终局定局定义为本原本原问题，相，相应最最优搜索路径搜索路径上的上的节点是可解点是可解节点，而所有使点，而所有使对方方获胜的的终局和属于局和属于对方最方最优搜索路径上的搜索路径上的节点点则是不可解是不可解节点。此外，所有其它的点。此外，所有其它的节点点则是具有是具有风险的中的中间节点。点。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室38/793.3 博弈树搜索3.3.2 极小极大分析法极小极大分析法 在二人博弈在二人博弈过程中，最直程中，最
46、直观而可靠的常用分析方法就是极而可靠的常用分析方法就是极小极大化搜索法。其主要描述思想和算法：小极大化搜索法。其主要描述思想和算法： （1）设博弈的一方博弈的一方为MAX方，其目方，其目标是尽可能使自己得到是尽可能使自己得到最高分；另一方最高分；另一方为MIN方方, 其目其目标是尽可能是尽可能给MAX方送出最低方送出最低分。所分。所谓极小极大化分析法是一种要极小极大化分析法是一种要轮流流为每一方每一方寻找一个最找一个最优行行动方案的方法。在方案的方法。在图中，方框形状中，方框形状“”表示是表示是MAX方方控制的或控制的或节点；点；圆形框形状形框形状“”表示表示MIN方控制与方控制与节点。点。
47、（2）考）考虑每一方案每一方案实施后施后对方可能采取的所有行方可能采取的所有行动，并，并为其其计算可能的得分；算可能的得分； （3）为计算得分，需要根据算得分，需要根据问题的特性信息定的特性信息定义一个估一个估价函数，用来估算当前博弈价函数，用来估算当前博弈树所有端所有端节点的得分。此点的得分。此时估算出估算出来的得分称来的得分称为的静的静态估估值。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室39/793.3 博弈树搜索3.3.2极小极大分析法极小极大分析法 （4）当端）当端节点的估点
48、的估值计算出来后，再推算父算出来后，再推算父辈节点的等分，点的等分，推算方法是：推算方法是：对“或或”节点，点，选择其子其子节点中最大的得分作点中最大的得分作为父父辈节点的得分（点的得分（选择对自己最有利的方案）；自己最有利的方案）；对“与与”节点，点，选其子其子节点中一个最小的得分作点中一个最小的得分作为作作为父父辈节点的得分（立足点的得分（立足于最坏的情况）。于最坏的情况）。这样计算出的父算出的父辈节点的等分称点的等分称为倒推倒推值。 （5）如果一个行）如果一个行动方案能方案能获得得较大的倒推大的倒推值，则它就是当它就是当前最好的行前最好的行动方案。方案。 存存储受限受限问题：先生成一定深
49、度的博弈：先生成一定深度的博弈树，进行极小极大分行极小极大分析，找出当前的最好的行析，找出当前的最好的行动方案。然后再已方案。然后再已选定的分支上再定的分支上再扩展一定的深度，如此反复。展一定的深度，如此反复。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室40/793.3.2极小极大分析法极小极大分析法 4 -1 -1 8 1 2 -5 0 -4 -9 -14 -1 -1 8 1 2 -5 0 -4 -9 -1 5 11 4 3 -1 5 11 4 3 -1 1 5 8 10 1 4 2
50、 5 -5 9 6 0 6 -4 10 1 5 8 10 1 4 2 5 -5 9 6 0 6 -4 10 9 -1 12 5 9 -1 12 5 MAX-MIN博弈树的倒推值计算博弈树的倒推值计算h h( (S0)=S0)=？ 4 8 2 0 -1 4 8 2 0 -1 4 -14 -13.3 博弈树搜索技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室41/793.3 博弈树搜索3.3.3 -剪枝技剪枝技术 基本思想：基本思想：边生成博弈生成博弈树边估算各估算各节点的倒推点的倒推值，并且
51、根，并且根据据评估出的倒推估出的倒推值范范围，及，及时停止停止扩展那些已无必要再展那些已无必要再扩展的展的子子节点。点。 具体剪枝方法：具体剪枝方法：（1） 对于一个于一个“与与”节点点MIN，若能估，若能估计出其倒推出其倒推值上界上界，并且并且这个个值不大于不大于MIN的父的父辈节点（一定是点（一定是“或或”节点）的估点）的估计倒推倒推值的下界的下界，即，即 ，则就不必要再就不必要再扩展展该MIN节点的其点的其余子余子节点了。点了。这一一过程称程称为剪枝。剪枝。（2）对于一个于一个“或或”节点点MAX，若能估，若能估计出其倒推出其倒推值下界下界 ，并且，并且这个个 值不小于不小于MAX的父的
52、父辈节点（一定是点（一定是“与与”节点）点）的估的估计倒推倒推值的上界的上界 ，即，即 ，则就不必要再就不必要再扩展展该MAX节点的其余子点的其余子节点了。点了。这一一过程称程称为 剪枝。剪枝。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室42/793.3 博弈树搜索3.3.3 -剪枝技剪枝技术 从算法中看到：从算法中看到：（1）MAX节点（包括起始点（包括起始节点）的点）的值永不减少。永不减少。（2）MIN节点（包括起始点（包括起始节点）的点）的值永不增加。永不增加。 在搜索期在搜索期
53、间， 和和 值的的计算如下：算如下：（1）一个）一个MAX节点的点的值等于其后等于其后继节点当前最大的最点当前最大的最终倒推倒推值。（2）一个）一个MIN节点的点的 值等于其后等于其后继节点当前最小的最点当前最小的最终倒推倒推值。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室43/793.3 博弈树搜索3.3.3 -剪枝技剪枝技术例例3.5 一字棋搜索一字棋搜索树和和值计算算 估价函数估价函数g(p)定定义如下：如下： （1）若当前棋局）若当前棋局对任何一方都不是任何一方都不是获胜的，的
54、，则 g(p)=(所有空格都放上所有空格都放上MAX的棋子之后的棋子之后3个棋子所个棋子所组成的行成的行列及列及对角角线的的总数）数）（所有空格都放上（所有空格都放上MIN的棋子之后的棋子之后3个个棋子所棋子所组成的行列及成的行列及对角角线的的总数）数） （2）若）若p是是MAX获胜，则 g(p)=+ （3）若）若p是是MIN获胜，则 g(p)=-上上图中，中，g(p)=6-4=2，其中，其中表示表示MAX方，方， 表示表示MIN方方技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室44/7
55、93.3.3 -剪枝技剪枝技术3.3 博弈树搜索初始节点初始节点=-1ABC-1=-16-5=15-5=06-5=15-5=04-5=-15-6=-1技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室45/793.3.3 -剪枝技剪枝技术3.3 博弈树搜索 4 -1 -1 8 1 2 -5 0 -4 -9 -14 -1 -1 8 1 2 -5 0 -4 -9 -1 5 11 4 3 -1 5 11 4 3 -1 1 5 8 10 1 4 2 5 -5 9 6 0 6 -4 10 1 5 8
56、10 1 4 2 5 -5 9 6 0 6 -4 10 9 -1 12 5 9 -1 12 5 MAX-MIN博弈树的倒推值计算博弈树的倒推值计算h h( (S0)=S0)=？ 4 8 2 0 -1 4 8 2 0 -1 4 -14 -1技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室46/793.3.3 -剪枝技剪枝技术3.3 博弈树搜索h h( (S0)=S0)=？4 44 411113 33 3 1 1 1 18 88 810108 82 22 2-5-5-5-52 22 24 44
57、 4 4 4x x 5 55 5 4 4 博弈树的博弈树的-剪枝实现过程剪枝实现过程 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室47/793.3 博弈树搜索3.3.3 -剪枝技剪枝技术 要要进行行-剪枝，必剪枝，必须至少使某一部分的搜索至少使某一部分的搜索树生生长到最大到最大深度，因深度，因为和和值必必须以端以端节点的静点的静态估估值为依据。因此采用依据。因此采用-剪枝技剪枝技术通常都要使用某种深度通常都要使用某种深度优先的搜索方法。先的搜索方法。技术课件合肥工业大学合肥工业大学合肥
58、工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室48/793.4 遗传算法 生物群体的生存生物群体的生存过程普遍遵循达程普遍遵循达尔文的物文的物竞天天择、适者生、适者生存的存的进化准化准则；生物通；生物通过个体个体间的的选择、交叉、交叉、变异来适异来适应大大自然自然环境。生物染色体用数学方式或境。生物染色体用数学方式或计算机方式来体算机方式来体现就是一就是一串数串数码，仍叫染色体，有，仍叫染色体，有时也叫个体；适也叫个体；适应能力用能力用对应一个染一个染色体的数色体的数值来衡量；染色体的来衡量；染色体的选择或淘汰或淘汰问题是
59、按求最大是按求最大还是是最小最小问题来来进行。行。 遗传算法是模仿生物算法是模仿生物遗传学和自然学和自然选择机理，通机理，通过人工方人工方式构造的一式构造的一类优化搜索算法，是化搜索算法，是对生物生物进化化过程程进行的一种数行的一种数学仿真，是学仿真，是进化化计算的一种最重要形式。算的一种最重要形式。 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室49/793.4 遗传算法遗传算法提出：算法提出：于于2020世世纪6060年代由密歇根年代由密歇根(Michigan)(Michigan)大
60、学大学Hollstien, BagleyhHollstien, Bagleyh和和RosenbergRosenberg等人在其博士等人在其博士论文中首先加以文中首先加以研究；研究；19751975年，美国年，美国J.H.HollandJ.H.Holland教授在其著作教授在其著作“Adaptation Adaptation in Natural and Artificial Systemsin Natural and Artificial Systems”中系中系统地地阐述了述了遗传算算法，法，给出了出了遗传算法的基本定理和大量的数学理算法的基本定理和大量的数学理论证明。明。遗传算法算法发展：
61、展：David E. GoldbergDavid E. Goldberg教授教授19891989年出版了年出版了 “Genetic AlgorichmsGenetic Algorichms”一一书，这一著作通常被一著作通常被认为是是遗传算算法的方法、理法的方法、理论及及应用的全面系用的全面系统的的总结。从。从19851985年起，国年起，国际上开始上开始陆续举行行遗传算法的国算法的国际会会议，后来又更名，后来又更名为进化化计算。算。参加参加进化化计算国算国际会会议的人数及收的人数及收录文章的数量、广度和深度文章的数量、广度和深度逐年逐年扩大。从此，大。从此，进化化计算逐算逐渐成成为人人们用来解
62、决高度复用来解决高度复杂问题的新思路和新方法。的新思路和新方法。 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室50/793.4 遗传算法遗传算法特点：算法特点：遗传算法是一种基于空算法是一种基于空间搜索的算法，它通搜索的算法，它通过自然自然选择、遗传、变异等操作以及达异等操作以及达尔文适者生存的理文适者生存的理论，模，模拟自然自然进化化过程来程来寻找所求找所求问题的解答。的解答。遗传算法具有以下特算法具有以下特点：点：(1) 遗传算法是算法是对参数集合的参数集合的编码而非而非针对参数本
63、身参数本身进行行进化；化；(2) 遗传算法是从算法是从问题解的解的编码组开始而非从开始而非从单个解开始搜个解开始搜索；索；(3) 遗传算法利用目算法利用目标函数的适函数的适应度度这一信息而非利用一信息而非利用导数数或其它或其它辅助信息来指助信息来指导搜索；搜索；(4) 遗传算法利用算法利用选择、交叉、交叉、变异等算子而不是利用确定异等算子而不是利用确定性性规则进行随机操作。行随机操作。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室51/793.4 遗传算法遗传算法算法应用：用： J.H.
64、HollandJ.H.Holland博士于博士于19751975年提出年提出遗传算法算法, ,当当时并没有引起学并没有引起学术界足界足够的重的重视。直到二十世。直到二十世纪8080年代中期年代中期, ,随着随着计算机技算机技术日新月异高速日新月异高速发展与展与进步步, ,遗传算法首先成功地算法首先成功地应用用于于AIAI机器学机器学习和神和神经网网络方面方面; ;后来又在后来又在诸如函数如函数优化、自化、自动控控制、制、图象象识别、分子生物学、分子生物学、优化化调度以及机械、土木、度以及机械、土木、电力力工程等工工程等工业系系统和和许多多领域中得到域中得到应用用, ,显示出示出诱人的前景。从人
65、的前景。从此，此，遗传算法始才得到学算法始才得到学术界普遍关注与界普遍关注与认可。可。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室52/793.4 遗传算法3.4.1 3.4.1 遗传算法的基本原理算法的基本原理 霍霍兰德提出的德提出的遗传算法通常称算法通常称为简单遗传算法（算法（SGA）。）。现以此作以此作为讨论主要主要对象，加上适象，加上适应的改的改进，来分析，来分析遗传算法算法的的结构和机理。在构和机理。在讨论中会中会结合合销售售员旅行旅行问题（TSP）来）来说明。明。 1. 编
66、码与解与解码 许多多应用用问题的的结构很复构很复杂，但可以化，但可以化为简单的位串形的位串形式式编码表示。将表示。将问题结构构变换为位串形式位串形式编码表示的表示的过程叫程叫编码；而相反将位串形式；而相反将位串形式编码表示表示变换为原原问题结构的构的过程叫解程叫解码或或译码。把位串形式。把位串形式编码表示叫染色体，有表示叫染色体，有时也叫个体。也叫个体。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室53/793.4 遗传算法3.4.1 3.4.1 遗传算法的基本原理算法的基本原理例：例：
67、对于于销售售员旅行旅行问题（Travelling salesman Problem, TSP），），设有有n个城市，城市个城市，城市i和城市和城市j之之间的距离的距离为d(i,j)，要求，要求找到一条遍找到一条遍访每个城市一次而且恰好一次的旅行每个城市一次而且恰好一次的旅行线路，使其路路，使其路径径总长度度为最短。按一条回路中城市的次序最短。按一条回路中城市的次序进行行编码。从城市。从城市w1开始，依次开始，依次经过城市城市w2 ，wn，最后回到城市，最后回到城市w1，我，我们就有如下就有如下编码表示：表示：w1 w2 wn由于是回路，由于是回路，记wn+1=w1。它其。它其实是是1，n的一个
68、循的一个循环排列。要注意排列。要注意w1，w2，wn是互不相同的。是互不相同的。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室54/793.4 遗传算法3.4.1 3.4.1 遗传算法的基本原理算法的基本原理2. 适适应度函数度函数 为了体了体现染色体的适染色体的适应能力，引入了能力，引入了对问题中的每一个染中的每一个染色体都能色体都能进行度量的函数，叫适行度量的函数，叫适应度函数（度函数（fitness function）。）。TSP的目的目标是路径是路径总长度度为最短，自然地，路径最
69、短，自然地，路径总长度的倒数度的倒数就可作就可作为TSP问题的适的适应度函数度函数:其中其中wn+1=w1适适应度函数要有效反映每一个染色体与度函数要有效反映每一个染色体与问题的最的最优解染色解染色体之体之间的差距。适的差距。适应度函数的取度函数的取值大小与求解大小与求解问题对象的意象的意义有很大的关系。有很大的关系。 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室55/793.4 遗传算法3.4.1 3.4.1 遗传算法的基本原理算法的基本原理3. 遗传操作操作简单遗传算法的算法的遗传
70、操作主要有有三种操作主要有有三种:选择(selection)、交叉、交叉(crossover)、变异异(mutation)。改。改进的的遗传算法大量算法大量扩充了充了遗传操操作，以达到更高的效率。作，以达到更高的效率。 选择操作也叫复制（操作也叫复制（reproduction）操作，根据个体的适）操作，根据个体的适应度度函数函数值所度量的所度量的优劣程度决定它在下一代是被淘汰劣程度决定它在下一代是被淘汰还是被是被遗传。简单遗传算法采用算法采用赌轮选择机制，令机制，令fi表示群体的适表示群体的适应度度值之之总和，和， fi表示种群中第表示种群中第i个染色体的适个染色体的适应度度值，它，它产生后代
71、的能力生后代的能力正好正好为其适其适应度度值所占份所占份额fi /fi。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室56/793.4 遗传算法3.4.1 3.4.1 遗传算法的基本原理算法的基本原理3. 遗传操作操作交叉操作的交叉操作的简单方式是将被方式是将被选择出的两个个体出的两个个体P1和和P2作作为父母个体，将两者的部分父母个体，将两者的部分码值进行交行交换。 产生一个生一个17之之间的随机数的随机数c，假，假设为3，则将将P1和和P2的低的低3位交位交换1 0 0 0 1 1
72、1 0P1：1 1 0 1 1 0 0 1P2：技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室57/793.4 遗传算法3.4.1 3.4.1 遗传算法的基本原理算法的基本原理3. 遗传操作操作1 0 0 0 1 1 1 0P1：1 1 0 1 1 0 0 1P2：1 0 0 0 1 0 0 11 1 0 1 1 1 1 0Q1：Q2：技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室
73、58/793.4 遗传算法3.4.1 3.4.1 遗传算法的基本原理算法的基本原理3. 遗传操作操作变异操作的异操作的简单方式是改方式是改变数数码串的某个位置上的数串的某个位置上的数码。二二进制制编码表示的表示的简单变异操作是将异操作是将0与与1互互换：0变异异为1，1变异异为0。随机随机产生一个生一个18之之间的数的数k，假，假设k=5，对从右往左第从右往左第5位位变异异操作。操作。 101001101技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室59/793.4 遗传算法3.4.1
74、3.4.1 遗传算法的基本原理算法的基本原理4. 控制参数控制参数交叉交叉发生的概率：生的概率：0.60.95 变异的概率：异的概率：0.0010.01 种群的个数：种群的个数：30100 个体的个体的长度：定度：定长和和变长 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室60/793.4 遗传算法3.4.2 3.4.2 遗传算法的算法的结构构选择：由个体适：由个体适应度度值决定决定 的某个的某个规则。交叉：按概率交叉：按概率Pc进行行变异：按概率异：按概率Pm进行行终止条件：止条件：
75、完成了完成了预先先给定的定的进化代数化代数 种群中的最种群中的最优个体在个体在连续若干代若干代 没有改没有改进或平均适或平均适应度在度在连续若若 干代基本没有改干代基本没有改进开始开始初始化种群初始化种群选择操作选择操作终止条件终止条件否否适应度最有优个体适应度最有优个体计算适应度值计算适应度值交叉操作交叉操作变异操作变异操作结束结束技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室61/793.4 遗传算法3.4.3 3.4.3 遗传算法的性能算法的性能 遗传算法求得的解是一算法求得的解是
76、一满意解。影响解意解。影响解质量的因素：量的因素： 种群的数量：太小缺少多种群的数量：太小缺少多样性，太多影响效率性，太多影响效率 适适应度函数：提升度函数：提升优良个体的适良个体的适应度度 交叉和交叉和变异：不同的异：不同的问题需构造性能更需构造性能更优的交叉和的交叉和变异操作异操作 交叉概率和交叉概率和变异概率：异概率：技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室62/79分析：分析：对该问题虽然也可以采用枚然也可以采用枚举的方法来解决的方法来解决, ,但枚但枚举法却法却是一种效率
77、很低的方法是一种效率很低的方法. .可运用可运用遗传算法来求解算法来求解该问题. .解：首先解：首先对问题进行初始化，以行初始化，以获得初始种群得初始种群; ; （1 1） 确定适当的确定适当的编码方案：将方案：将x x编码表示表示为染色体的数字符染色体的数字符号串。号串。针对本本题自自变量量x x定定义域域, ,取取值范范围为00，31,31,考考虑采采用二用二进制数来制数来对其其编码, ,由由2 25 5 = 32,= 32,故使用故使用5 5位无符号二位无符号二进制数制数组成染色体数字字符串成染色体数字字符串, ,用以表达用以表达变量量x x及及问题的解答的解答过程。程。 例例: : 设
78、设有有函函数数f(xf(x)=)=x x2 2, , 请请用用遗遗传传算算法法求求其其自自变变量量x x在在区区间间00，31 31 取整数值时的最大值，并说明此函数的优化问题。取整数值时的最大值，并说明此函数的优化问题。 3.4 遗传算法技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室63/79 （2 2）选择初始种群初始种群: :通通过随机的方法来随机的方法来产生染色体的数生染色体的数字串，并字串，并组成初始种群。例如，成初始种群。例如，为得到数字串的某位得到数字串的某位又称之又称之为
79、基因基因(genes)(genes)，使用，使用计算机在算机在0 01 1之之间产生生随机数随机数K K，并按照数，并按照数K K的的变化区域来化区域来规定基因代定基因代码如下：如下： 0 0， （0 0K K0.50.5） 1 1， （0.50.5K K1 1）3.4 遗传算法G =G =G =G =技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室64/79于是于是随机生成随机生成4 4个个染色体的数字符串染色体的数字符串为： 011010110111000110000100001000
80、1001110011从而构造了初始种群，完成了从而构造了初始种群，完成了遗传算法的准算法的准备。3.4 遗传算法技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室65/79表表 初始种群染色体及初始种群染色体及对应的适的适应值 3.4 遗传算法染染 色色体体 标标号号 串串 x 适应值适应值f (x) = x2 占占 整整 体体 的的百分数百分数 1 1 0110101101 169169 14.4 %14.4 % 2 2 1100011000 576576 49.2%49.2% 3 3 0
81、100001000 6464 5.5%5.5% 4 4 1001110011 361361 30.9%30.9% 总计总计（初始种群值）（初始种群值） 11701170 100.0%100.0%技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室66/79（3 3）复制）复制( (选择):):选择适适应值大的串作大的串作为母本，使在下一代中有更多的机会繁殖母本，使在下一代中有更多的机会繁殖其子其子孙。要在四个种子个体中做要在四个种子个体中做选择，要求仍然得到四个染色体，可依，要求仍然得到四个染
82、色体，可依据适据适应度概率比例制定如下度概率比例制定如下规则： 低于低于0.1250.125以下的染色体被淘汰；以下的染色体被淘汰； 在在0.1250.1250.3750.375之之间的染色体被复制一个；的染色体被复制一个； 在在0.3750.3750.6250.625之之间的染色体被复制两个；的染色体被复制两个； 在在0.6250.6250.8750.875之之间的染色体被复制三个；的染色体被复制三个； 在在0.8750.875以上的染色体可复制四个。以上的染色体可复制四个。3.4 遗传算法技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研
83、究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室67/79对应于上例，按照适于上例，按照适应度的度的计算，算，经复制操作后，得到新复制操作后，得到新的染色体种群的染色体种群为 01101 01101 11000 11000 11000 11000 10011 100113.4 遗传算法技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室68/79 某个染色体是否被复制某个染色体是否被复制, ,可以通可以通过概率决策法、适概率决策法、适应度度比例法或比例法或“轮盘赌”的随机方法来断定。的随机
84、方法来断定。对应轮盘赌转盘的随机方法的随机方法, ,根据表根据表6.16.1数据，数据，绘制出的制出的轮盘赌转盘, ,如如图所示所示: : 进化计算进化计算基本基本遗传算法原理遗传算法原理49.230.9%14.4%5.5%n n01101 01101 01101 01101 n n11000 11000 11000 11000 n n11000 11000 11000 11000 n n10011100111001110011技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室69/793.
85、4 遗传算法 初始种群初始种群 x 值值 适应度适应度 选择概率选择概率 期望值期望值 实际复制数实际复制数编号编号 （随机产生）（随机产生） （无符号整数）（无符号整数） f (x) = x2 Pc f(xi)/fA （或转轮法）（或转轮法） 1 01101 13 169 0.144 0.58 11 01101 13 169 0.144 0.58 1 2 11000 24 576 0.492 1.97 2 2 11000 24 576 0.492 1.97 2 3 01000 8 64 0.055 0.22 0 3 01000 8 64 0.055 0.22 0 4 10011 19 361
86、 0.309 1.23 1 4 10011 19 361 0.309 1.23 1 1170 1.00 4.00 4.0 1170 1.00 4.00 4.0 平均平均(A(A) 293293 0.25 1.00 1.0 0.25 1.00 1.0 MAX MAX 576576 0.49 1.97 2.0 0.49 1.97 2.0初始种群染色体准备复制操作的各项计算数据初始种群染色体准备复制操作的各项计算数据 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室70/79（4 4）交叉交叉:
87、 : 交叉具体分两步：交叉具体分两步：将新复制将新复制产生的生的染色体染色体随机两两匹配随机两两匹配, ,称其称其为双双亲染色体染色体；再把再把双双亲染色体染色体进行交叉繁殖。行交叉繁殖。 交叉的交叉的实现: : 设染色体数字串染色体数字串长度度为L L，把，把L L个数字位个数字位间空空隙分隙分别标记为： 1 1，2 2，L L1 1 随机从随机从11，L L11中中选取某一整数位置取某一整数位置k k，0k0kL L 交交换双双亲染色体交染色体交换点位置点位置k k右右边的部分，就形成了两个新的的部分，就形成了两个新的数字符串（也可以只交数字符串（也可以只交换其中的第其中的第k k基因），
88、得到了两个新基因），得到了两个新的染色体，又称之的染色体，又称之为下一代染色体。下一代染色体。3.4 遗传算法技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室71/79例如，将上例初始种群的两个体例如，将上例初始种群的两个体例如，将上例初始种群的两个体例如，将上例初始种群的两个体A A A A1 1 1 1=01101=01101=01101=01101A A A A2 2 2 2=11000=11000=11000=11000假假假假定定定定从从从从1 1 1 1到到到到4 4 4 4间
89、间选选取取取取两两两两个个个个随随随随机机机机数数数数，得得得得到到到到 1 1 1 1=2=2=2=2， 2 2 2 2=4=4=4=4，那那那那么么么么经经过过交交交交叉叉叉叉操作之后将得到如下两操作之后将得到如下两操作之后将得到如下两操作之后将得到如下两组组新的数字符串新的数字符串新的数字符串新的数字符串A A A A1 1 1 1# # # #=01000 =01000 =01000 =01000 A A A A2 2 2 2# # # #=11101=11101=11101=11101 3.4 遗传算法n nA A A A3 3 3 3# # # #=01100=01100=0110
90、0=01100n nA A A A4 4 4 4# # # #=11001 =11001 =11001 =11001 n n前一组数字串是使用前一组数字串是使用前一组数字串是使用前一组数字串是使用 1 1 1 1=2,=2,=2,=2,即将第即将第即将第即将第2 2 2 2位后的位后的位后的位后的3 3 3 35 5 5 5位交换得到；位交换得到；位交换得到；位交换得到；n n后一组数字串是使用后一组数字串是使用后一组数字串是使用后一组数字串是使用 2 2 2 2=4=4=4=4，即仅将第，即仅将第，即仅将第，即仅将第5 5 5 5位位位位因子因子因子因子进行交换而得。进行交换而得。进行交换而
91、得。进行交换而得。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室72/793.4 遗传算法编编号号复复制制操操作作后后的的区区配配池池匹匹配配号号(随随机选取机选取) )交交叉叉空空隙隙位位 ( (随随 机机选取选取) )交交叉叉后后新种群新种群新新种种群群x值值适应度适应度f(x) = x21 101101011012 22 201000010008 864642 211000110001 12 211101111012929841841311000110004 44 41100111
92、00125256256254 410011100113 34 410000100001616256256总计（总计（）17861786平均平均(A(A)446.5最大值最大值(MAX(MAX) 841841复制、交叉操作的各项数据复制、交叉操作的各项数据 技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室73/79 （5 5）变异异: : 设变异概率取异概率取为0.001,0.001,则对于种群于种群总共有共有2020个基因位个基因位. . 期望的期望的变异串位数异串位数计算算:20:200
93、.001 =0.02(0.001 =0.02(位位),), 故一般来故一般来说, ,该例中无基因位数例中无基因位数值的改的改变. .从表从表11-211-2和和11-311-3可可以看出以看出, ,每每经过一次复制、交叉和一次复制、交叉和变异操作后异操作后, ,目目标函数的最函数的最优值和平均和平均值就会有所提高。就会有所提高。 在上例中，种群的平均适在上例中，种群的平均适应值从从293293增至增至446.5;446.5;最大的适最大的适应度数度数值从从576576增至增至841841。 特点：每特点：每经一次一次进化化计算步算步骤, ,问题解答便向着最解答便向着最优方向前方向前进了一步了一
94、步; ;若若该过程一直程一直进行下去行下去, ,就将最就将最终走向全局的最走向全局的最优解解. .可可见进化化计算的每一步操作算的每一步操作简单, ,并且系并且系统的求解的求解过程是依照程是依照计算算方法与方法与规律来决定律来决定, ,与本源与本源问题自身的特性很少相关。自身的特性很少相关。 3.4 遗传算法技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室74/79 固体退火原理：固体内部粒子随着温度升高而固体退火原理：固体内部粒子随着温度升高而变为无序，无序，内能增大，而徐徐冷却内能增大
95、，而徐徐冷却时粒子粒子渐趋有序，在每个温度都达到平有序，在每个温度都达到平衡衡态，在常温，在常温时达到基达到基态，内能减，内能减为最小。最小。 Metropolis Metropolis准准则： 粒子在温度粒子在温度T T时趋于平衡的概率于平衡的概率= =e e- -E/(kT)其中，其中，E为固体在温度固体在温度T时的内能，的内能，E为内能的改内能的改变量，量，k为波波尔兹曼（曼（Boltzmann）常数。）常数。 模模拟退火算法：由初始解退火算法：由初始解i和控制参数初和控制参数初值t开始，开始，对当前当前解重复解重复进行行“产生新解生新解计算目算目标函数差函数差接受或舍弃接受或舍弃”的迭
96、的迭代，并逐步衰减代，并逐步衰减t值，算法，算法终止止时的当前解的当前解为所得近似最所得近似最优解。解。退火退火过程由冷却程由冷却进度表控制，包括控制参数的初度表控制，包括控制参数的初值t及其衰减及其衰减因子因子t、每个、每个t值时的迭代次数的迭代次数L和停止条件和停止条件S。3.5 模拟退火算法技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室75/79 生物机体系生物机体系统：脑神神经系系统、遗传系系统、自然免疫系、自然免疫系统和内和内分泌系分泌系统。 免疫免疫计算：模仿自然免疫系算：模
97、仿自然免疫系统而而产生的一种新的生的一种新的计算理算理论和方法。和方法。 自然免疫系自然免疫系统：一个复：一个复杂的自适的自适应系系统，通，通过一套复一套复杂的的机制来重机制来重组基因，以基因，以产生相生相应入侵抗原的抗体；同入侵抗原的抗体；同时还具有学具有学习和和记忆功能，可以区分自身功能，可以区分自身细胞和抗原胞和抗原细胞，并最胞，并最终消消灭抗抗原原细胞。胞。 人工免疫系人工免疫系统的研究：的研究：20世世纪90年代，解决网年代，解决网络适适应性性问题、传感器网感器网络故障故障诊断、病毒断、病毒检测、机器学、机器学习。3.6 免疫算法技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大
98、学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室76/79 免疫算法（免疫算法（immunealgorithm）：在模仿生物免疫机制的）：在模仿生物免疫机制的基基础上，上，综合基因合基因进化机理，人工地构造的一化机理，人工地构造的一类优化算法，它化算法，它实现了了类似于免疫系似于免疫系统自我自我调节功能和生成不同抗体的功能。功能和生成不同抗体的功能。 抗原（抗原（antigen）：在免疫算法中抗原指非最佳个体的基因，）：在免疫算法中抗原指非最佳个体的基因，或者可能或者可能错误地基因；在免疫学中，抗原指有一种能地基因；在免疫学中，抗原指有一种能
99、够刺激机刺激机体体产生相生相应抗体的物抗体的物质。 疫苗（疫苗（vanccine）：在免疫算法中疫苗指根据已有的先）：在免疫算法中疫苗指根据已有的先验知知识得到的关于得到的关于对最佳个体的一个估最佳个体的一个估计值；在免疫学中，疫苗；在免疫学中，疫苗是一是一类能引起免疫能引起免疫应答反答反应的生物制的生物制剂，通常，通常为蛋白蛋白质。 抗体（抗体（antibody）：在免疫算法中抗体是指根据疫苗修正）：在免疫算法中抗体是指根据疫苗修正某个个体基因所得到的新个体（新基因）；在免疫学中，抗体某个个体基因所得到的新个体（新基因）；在免疫学中，抗体是一种具有免疫功能的球蛋白，是人体抵抗力最重要的是一种
100、具有免疫功能的球蛋白，是人体抵抗力最重要的组成部成部分。分。3.6 免疫算法技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室77/793.6 免疫算法 当病原体入侵时，免疫系统首先要识别这一抗原，然后产生当病原体入侵时，免疫系统首先要识别这一抗原，然后产生相应的抗体来消灭它。识别的过程实际上就是免疫细胞与抗原相应的抗体来消灭它。识别的过程实际上就是免疫细胞与抗原匹配并结合的过程，如果一个系统中所有抗原都被抗体识别匹配并结合的过程，如果一个系统中所有抗原都被抗体识别（随后被消灭）了，那么这个
101、系统就达到了最佳状态。（随后被消灭）了，那么这个系统就达到了最佳状态。 识别的有限性：一个免疫细胞（抗体）不一定能够与所有识别的有限性：一个免疫细胞（抗体）不一定能够与所有的抗原匹配。的抗原匹配。 识别的多样性：一个免疫细胞可以识别多种不同的抗原。识别的多样性：一个免疫细胞可以识别多种不同的抗原。技术课件合肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室78/79 免疫系免疫系统进化的目化的目标：以最少的抗体数量覆盖几乎整个抗原：以最少的抗体数量覆盖几乎整个抗原空空间。 亲和力：描述抗体和抗原之和力
102、：描述抗体和抗原之间的匹配程度（覆盖能力）。的匹配程度（覆盖能力）。 排斥力：描述两个抗体之排斥力：描述两个抗体之间的相异程度。的相异程度。 算法步算法步骤： （1）识别抗原。抗原。输入入问题的目的目标函数和各种函数和各种约束条件，作束条件，作为免疫算法的抗原。免疫算法的抗原。 （2）产生初始抗体群。通常是在解空生初始抗体群。通常是在解空间中随机中随机产生生n个候个候选解作解作为初始抗体，初始抗体，n为抗体群众抗体的数目。抗体群众抗体的数目。 （3）计算算亲和力和排斥力。分和力和排斥力。分别计算每个抗体的算每个抗体的亲和力以和力以及各抗体之及各抗体之间排斥力。排斥力。3.6 免疫算法技术课件合
103、肥工业大学合肥工业大学合肥工业大学合肥工业大学 人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室人工智能与数据挖掘研究室79/79 （4）产生新的抗体。通生新的抗体。通过免疫算子免疫算子产生新的抗体，并生新的抗体，并计算算新抗体的新抗体的亲和力及其之和力及其之间的排斥力。的排斥力。 （5）更新）更新记忆能力。将与抗原能力。将与抗原亲和力高的抗体加入到和力高的抗体加入到记忆单元中，并淘汰与其排斥力最高的原有抗体。元中，并淘汰与其排斥力最高的原有抗体。 （6）判断是否）判断是否满足停止条件。若新抗体中有与抗原相匹配足停止条件。若新抗体中有与抗原相匹配的抗体，或以的抗体，或以满足足预定的停机条件定的停机条件则停机。否停机。否则转（7）。）。 （7）利用免疫算子）利用免疫算子产生新的抗体群。免疫算子包括生新的抗体群。免疫算子包括选择、交叉和交叉和变异等操作。在异等操作。在选择时，给那些那些亲和力大的抗体和力大的抗体赋予予较大的大的选择概率。概率。 （8）转（3）3.6 免疫算法技术课件
