人工智能试验指导书+作业展示

1、人工智能技术导论实验指导书西北工业大学计算机学院一实验纲要1二上机要求2三实验内容3实验一图搜索与问题求解3实验1.1启发式搜索3实验1.2A*算法搜索9实验1.3其他应用问题12实验二产生式系统推理14实验三TSP问题的遗传算法实现20四实验报告模板27人工智能实验一实验报告27人工智能实验二实验报告28人工智能实验三实验报告29附件1TSP问题的遗传算法程序模板30附件2学生作业作品展示35一实验纲要一实验教学的目的、任务与要求将人工智能基础理论应用于实际问题的解决当中，加深学生对所学知识的理解，提高学生的实际动手能力。二实验项目内容1图搜索策略实验用启发式搜索方法/A*算法求解重排九宫问

2、题/八数码问题。2产生式系统的推理以动物识别系统为例，实现基于产生式规则的推理系统。3TSP问题的遗传算法实现以N个结点的TSP问题为例，用遗传算法加以求解。三参考教材人工智能技术导论-第3版，廉师友编著，西安电子科技大学出版社，2007。四使用主要仪器设备说明在Windows2000/XP上，选用Java/C/C+/Matlab等语言进行实现。五实验考核实验为12学时，分4次课完成。每个实验题目在课堂上分别按百分制给出。其中包括课堂纪律、程序运行结果、课堂回答问题及实验报告成绩等。实验课总成绩为3个实验题目的平均成绩。实验课要求学生提前预习，上课时需向辅导老师提交预习报告，报告格式和内容不作

3、过多要求，只需简要说明自己本次实验的大体思想。预习报告形式不限，电子版或手写版均可。1考核方法由各班辅导老师当堂检查源程序和运行结果，并提问相关问题，课堂上给出成绩并记录。每个题目完成后把源代码和实验报告提交，由辅导老师检查实验报告并给出报告成绩。2评分标准每个实验题目根据以下标准进行考核：1）考勤分20分。按时到课，无违纪现象20分；迟到或事假扣5分；无故缺勤，0分;2）预习情况10分。认真完成课前预习者10分；不预习，0分；其他情况酌情给分。3）程序内容成绩30分。程序运行正确，达到规定要求，20分；能在规定的要求上完成更完善的功能，或具有一定的界面效果，25分；特别优秀者，30。具体在此

4、基础上酌情给分。4）实验报告成绩30分。实验报告达到要求，最高分为30分。互相抄袭，记0分；其他情况酌情给分。5）回答问题成绩10分。回答问题正确最高分为10分；回答问题均不正确，0分；其他情况酌情给分。6）第一次实验课只记考勤，无故缺勤者总成绩中扣5分。3实验报告在每个实验完成后，在规定时间内提交实验报告。实验报告格式，参见实验报告模板。提交内容：1）实验报告2）源代码提交形式：将实验报告和源代码压缩成zip文件，命名为AI-班号-学号-姓名.zip二上机要求1 上机之前上机之前做好相关知识复习，上课时捎带课本或参考书。提前了解实验内容，并准备好自己的算法。2 上机过程1 .根据提前设计的算

5、法，进行上机验证并调试，遇到问题及时解决；2 .上机时间，遵守实验室纪律；3 .在规定的时间内向指导教师提交作业。各自保存好每次实验的源代码，并在规定时间内将源代码和实验报告压缩后提交。实验内容实验一图搜索与问题求解卜面主要以八数码问题展本次实验主要用来熟悉图搜索技术在具体问题中的求解过程,开，也可以以其它题目展开实验。实验1.1启发式搜索一实验目的1熟悉和掌握启发式搜索的定义、估价函数和算法过程；2理解和掌握启发式搜索过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜索顺序；3比较并分析图搜索策略的实质，通过实验理解启发式搜索的意义。二实验内容以重排九宫问题/八数码问题为例，以启发式

6、搜索方法求解给定初始状态和目标状态的最优搜索路径。1重排九宫问题在一个3*3的方格棋盘上放置8个标有1、2、3、4、5、6、7、8数字的将牌，留下一个空格（一般用0表示），规定与空格上下左右相邻的将牌可以移入空格。问题的解是要求寻找一条从某初始状态S0到目标状态Sg的将牌移动路线。1八数码问题示例图2问题描述要求用某种启发式搜索方法求解从给定的初始状态到目标状态的移动路线。三实验要求1自己定义启发式函数，能正确求解出从初始状态到目标状态的移动路线;2要求界面显示初始状态、目标状态和中间搜索步骤；3对不可达状态能进行正确识别；4对所采用的启发式函数做出性能分析。四实验背景知识1图搜索技术图搜索技

7、术是人工智能中的一个核心技术之一，人工智能的许多分支领域都涉及到图搜索，在状态图中寻找目标或路径的基本方法就是搜索。由于搜索具有探索性，所以要提高搜索效率(尽快地找到目标节点)，或要找最佳路径(最佳解)就必须注意搜索策略。对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索和启发式搜索两大类。用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索。树式盲目搜索就是穷举式搜索，而线式盲目搜索，对于不回溯的就是随机碰撞式搜索，对于回溯的则也是穷举式的搜索。树式穷举式搜索主要有广度优先搜索和深度优先搜索。实践表明，穷举搜索只能解决一些状态空间很小的简单问题，而对于那些大状态空间问题

8、，穷举搜索就不能胜任了。因为大空间问题，往往会导致“组合爆炸”。所以必须探索更有效的搜索方法，如启发式搜索策略。2启发式搜索启发式搜索就是利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。一般来说，启发信息强，可以降低搜索的工作量，但可能导致找不到最优解；而启发信息弱，一般会导致搜索的工作量加大，极端情况下演变为盲目搜索，但有可能找到最优解。我们希望，通过引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。按其用途划分，启发性信息可分为以下三类：(1)用于扩展节点的选择(2)用于生成节点的选择节点。(3)用于删除节点的选择费。,即用于决定应先扩展哪一个节点,即用

9、于决定应生成哪些后续节点,即用于决定应删除哪些无用节点在启发式搜索中，通常用所谓启发函数来表示启发性信息。上节点x与目标节点Sg接近程度的一种函数，通常记为h(x)。,以免盲目扩展。,以免盲目地生成过多无用,以免造成进一步的时空浪启发函数是用来估计搜索树启发函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有：一个节点到目标节点的某种距离或差异的度量；一个节点处在最佳路径上的概率；或者根据经验的主观打分等等。在八数码问题种，启发函数h(x)可定义为目标状态与当前状态相同的节点个数，或者当前状态每个节点到目标状态相应节点所需步数的总和(水平的距离与竖直的距离和，也称为曼哈顿路径)。3八

10、数码问题的有解和无解判定将九宫格中数字顺序排列后，形成一个包含0在内的9位数字序列，该字串可用来表示九宫格的当前状态，其中0表示空格所在位置。当空格上下、左右移动时，易知序列的逆序值奇偶性不会发生改变。由此可知，九宫问题的362,880种状态被分成逆序值为奇数和逆序值为偶数两部分，每一部分内任意两种状态相互可达。在八数码问题中，有些状态之间是不可达的。如果我们能在一开始先判断初始状态和目标状态之间是否可达，这样可以避免不可达状态之间的盲目求解。两个状态之间是否可达可以通过两个状态逆序值的奇偶性进行判断。我们把每个状态看作一个数列，然后计算数列的逆序值，若两个数列逆序值的奇偶性相同，则对应的两个

11、状态是可达的，否则不可达。(注：求逆序值不把空格算在内)。如图2所示状态：它对应的数列是：23158467(不包括空格)。对于一个数列，数列中每个数的逆序值是指位于这个数前面的比这个数大的数的个数。数列的逆序值就是数列中每个数的逆序值之和。逆序值求法：例：23158467的逆序值为6,求解过程为：0+0+2(12,13)+0+0+2(45,48)+1(68)+1(78)=6而状态12345678的逆序值自然就是0。4曼哈顿路径曼哈顿距离(ManhattanDistance),又称为出租车距离，是由十九世纪的赫尔曼闵可夫斯基所创词汇，是种使用在几何度量空间的几何学用语，用以标明两个点上在标准坐标

12、系上的绝对轴距总和。图3曼哈顿距离示意图我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标(x1,y1)的点P1与坐标(x2,y2)的点P2的曼哈顿距离为：|x1-x2|+|y1-y2|.要注意的是，曼哈顿距离依赖坐标系统的转度，而非系统在坐标轴上的平移或映射。5康托展开(1)康托展开的公式：把一个整数X展开成如下形式:X=an*(n-1)!+an-1*(n-2)!+ai*(i-1)!+a2*1!+a1*0!其中，a为整数，并且0=aii(1=i=n)(2)康托展开的应用实例(1,2,3

13、,4,.,n)表示1,2,3,.,n的排列如1,2,3)按从小到大排列一共6个。123132213231312321。代表的数字123456也就是把10进制数与一个排列对应起来。他们间的对应关系可由康托展开来找到，如想知道321是1,2,3)中第几个大的数可以这样考虑：第一位是3,当第一位的数小于3时，那排列数小于321如123、213，小于3的数有1、2。所以有2*2!个。再看小于第二位2的：小于2的数只有一个就是1,所以有1*1!=1所以小于321的1,2,3)排列数有2*2!+1*1!=5个。所以321是第6个大的数。2*2!+1*1!是康托展开。再举个例子：1324是1,2,3,4)排

14、列数中第几个大的数：第一位是1小于1的数没有，是0个0*3!第二位是3小于3的数有1和2,但1已经在第一位了，所以只有一个数21*2!。第三位是2小于2的数是1,但1在第一位，所以有0个数0*1!,所以比1324小的排列有0*3!+1*2!+0*1!=2个，1324是第三个大数。(3)康托展开的启示图搜索求解中，对于频繁访问的OPEN!和CLOSER,有时需要判断两个节点是否相同，求节点序列的康托展开是个不错的方法。五实验关键技术1全局择优启发式算法步1把初始节点S0放入OPE破中，计算h(S0);步2若OPEN1为空，则搜索失败，退出。步3移出OPEN1中第一个节点N放入CLOSER中，并冠

15、以序号n；步4若目标节点Sg=N,则搜索成功，结束。步5若N不可扩展，则转步2;步6扩展N,计算每个子节点x的函数值h(x),并将所有子节点配以指向N的返回指针后放入OPEN1中，再对OPEN!中的所有子节点按其函数值大小以升序排序，转步2。2CLOSED和OPEN1的设计CLOSED1和OPEN1的设计是图搜索程序实现中一个关键问题。我们用一个称为CLOSED1的动态数据结构来专门记录考查过的节点。对于树式搜索来说，CLOSED1中存储的正是一棵不断成长的搜索树；采用一个称为OPEN1的动态数据结构，来专门登记当前待考查的节点。CLOSED1和OPEN1的数据结构设计比较灵活，和具体采用的算

16、法密切相关，这里列举两个示例：(1)采用结构体数组示例6typedefstruct(intindex;/结点序号intParent;/父结点序号intGridSIZESIZE;/八数码状态intH;/启发式函数值State;StateOPENMAXSIZE;存放已经生成的未考察的节点StateCLOSEMAXSIZE;存放已经考察过得节点(2)米用链表存储不例structLNode/(intindex;/intH;/intGrid9;/intzeroposition;/structLNode*parent;/structLNode*child4;/structLNode*next;typede

17、fstructLHead/(intnum;structLNode*first;LHead,*LinkList;普通结点，存储八数码信息结点序号启发式函数值八数码状态空格的位置指向父节点指向子节点(最多有四个)头结点LinkListLopen,Lclose;/定义才旨向open、close表的指针六实验检查要求1 界面显示要求：(1)包含初始状态和目标状态的显示，可由指导老师随机输入状态进行检查；(2)对不可达状态应给出提示；(3)每次搜索过程的步骤，不要求显示树型结构，只要求(动画)表现，每走一步的状态变化；(4)每走一次搜索步，需要有步数的累积显示；(5)最后有完成一次搜索完毕的结果显示。2

18、 代码要求检查时要求提供源代码。73 讲解要求要求学生讲解自己设计代码的构架，具体实现方法（包含使用了何种数据结构，open表和close表的结构等）；要求学生说明自己所使用的搜索算法，以及程序运行效果。4 回答辅导老师提出的问题。5 提交实验报告（课后把实验报告和源代码在规定的时间内提交到指定邮箱里）。实验1.2A*算法搜索一实验目的1加深对各种状态图搜索策略概念的理解；2熟悉和掌握A*搜索的定义、估价函数和算法过程；3理解和掌握A*搜索过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜索顺序；4通过实验掌握估价函数的计算方法，理解估价函数定义的意义。二实验内容_一一.*.-.,.一

19、.以重排九宫问题/八数码问题为例，以A搜索算法求解给定初始状态和目标状态的最优搜索路径。三实验要求1自己定义估价函数，能正确求解出从初始状态到目标状态的移动路线；2要求界面显示初始状态、目标状态和中间搜索步骤；3对不可达状态能进行正确识别；4对所采用的估价函数做出性能分析，分析g(n)和h(n)的主要作用是什么，以及不同取值的实验效果，并进行分析。四实验背景知识一.*一.一.A算法和A算法是图搜索的两种典型的启发式搜索算法。1 A算法A算法是在图搜索算法中的树式搜索算法中增加了估价函数f(x)的一种启发式搜索算法。估价函数的一般形式为：f(x)=g(x)+h(x)其中g(x)为从初始节点S0到

20、节点x已经付出的代价，h(x)是启发函数，表示估计搜索树上节点x与目标节点Sg接近程度。估价函数f(x)是从初始节点&到达节点x处已付出的代价与节点x到达目标节点Sg的接近程度估计值之总和。有时估价函数还可以表示为f(x)=d(x)+h(x)其中d(x)表示节点x的深度。f(x)中的g(x)或d(x)有利于搜索的横向发展，h(x)则有利于搜索的纵向发展，因而可提高搜索的效率和搜索的完备性。但在确定f(x)时，要权衡利弊，使g(x)(或d(x)与h(x)的比重适当，这样才能取得理想的效果。2 A算法对A算法限制其估价函数中的启发函数h(x),使其满足：对所有的节点x均有：h(x)L1,b为其求解

21、路径上的终结点。因为估价函数f(n)=step+h(n),h(n)=n(n为到目标的实际路径)。所以f(a)=L1,f(b)=L2,推出f(a)f(b),在小顶堆中是不可能先发展b而不发展a的。与A*算法矛盾。五实验关键技术下面给出A算法的具体步骤：步1把附有f(S0)的初始节点S0放入OPEN1;步2若OPEN1为空，则搜索失败，退出。步3移出OPEN1中第一个节点N放入CLOSED1中，并冠以顺序编号n；步4若目标节点Sg=N,则搜索成功，结束。步5若N不可扩展，则转步2;步6扩展N,生成一组附有f(x)的子节点，对这组子节点作如下处理：(1)考察是否有已在OPEN或CLOSED!中存在的

22、节点；若有则再考察其中有无N的先辈节点，若有则删除之；对于其余节点，也删除之，但由于它们又被第二次生成，因而需考虑是否修改已经存在于OPEN!或CLOSER中的这些节点及其后裔的返回指针和f(x)值，修改原则是“抄f(x)值小的路走”；(2)对其余子节点配上指向N的返回指针后放入OPEN1中，并对OPEN1按f(x)值以升序排序，转步2。六实验检查要求1界面显示要求：(1)包含初始状态和目标状态的显示，可由指导老师随机输入状态进行检查；(2)每次搜索过程的步骤，不要求树型结构，只要求(动画)表现，每走一步的状态10变化;(3)每走一次搜索步，需要有步数的累积显示；(4)最后有完成一次搜索完毕的

23、结果显示。2 代码要求检查时要求提供源代码。3 讲解要求open要求学生讲解自己设计代码的构架，如何实现的(包含使用了何种数据结构，表和close表的结构等)；要求学生说明自己所使用的估价函数，以及程序运行效果。4 回答辅导老师提出的问题。5提交实验报告(课后把实验报告和源代码在规定的时间内提交到指定邮箱里)11实验1.3其他应用问题一迷宫问题走迷宫是人们熟悉的一种游戏，如下图就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点，把通道作为边，则该迷宫可以由一个有向图表示(如图4所示)。那么，走迷宫其实就是从该有向图的初始节点S0(入口)出发，寻找目标节点Sg(出口)的问题，或者

24、是寻找通向目标节点(出口)的路径的问题。11Si+S2+S3S4+S5+S6S7IS8IS9So主4图4迷宫图请用图搜索算法进行求解。二八皇后问题八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在88格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。请用图搜索算法进行求解。三一字棋游戏设有一个三行三列的棋盘，两个棋手A

25、,B轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。图5一字棋设A的棋子用“a”表示，B的棋子用“b”表示。为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下：设棋局为P,估价函数为e(P)。(1) 若P是A必胜的棋局，则e(P)=+8。(2) 若P是B必胜的棋局，则e(P)=-(3)若P是胜负未定的棋局，则e(P)=e(+P)-e(-P)其中e(+P)表示棋局P上有可能使a成为三子成一线的数目；e(-P)表示棋局P上有可能使b成为三子成一线的数目。例如，对于上图所示的棋局，则12e(P)=6-4=2另外，我们假定具有对称性的两个棋局算作一个棋局

26、。还假定A先走棋，我们站在A的立场上。下图给出了A的第一着走棋生成的博弈树。图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可以看出，对于A来说最好的一着棋是S,因为S3比S和Q有较大的倒推值。图6一字棋极小极大搜索请用图搜索算法进行求解，并要求应用a-3剪枝技术。13实验二产生式系统推理一实验目的1熟悉和掌握产生式系统的构成和运行机制；2掌握基于规则推理的基本方法和技术，掌握正确的正向推理和逆向推理方法；3熟悉在具体问题中如何实现正向推理和逆向推理的求解流程。二实验内容以动物识别系统为例，用选定的编程语言建造规则库和综合数据库，并能对它们进行增加、删除和修改操作，开发能进行正确的正向

27、推理或反向推理的推理机。1动物分类规则集(I)(1)若某动物有奶，则它是哺乳动物。(2)若某动物有毛发，则它是哺乳动物。(3)若某动物有羽毛，则它是鸟。(4)若某动物会飞且生蛋，则它是鸟。(5)若某动物是哺乳动物且有爪且有犬齿且目盯前方，则它是食肉动物。(6)若某动物是哺乳动物且吃肉，则它是食肉动物。(7)若某动物是哺乳动物且有蹄，则它是有蹄动物。(8)若某动物是有蹄动物且反刍食物，则它是偶蹄动物。(9)若某动物是食肉动物且黄褐色且有黑色条纹，则它是老虎。(10)若某动物是食肉动物且黄褐色且有黑色斑点，则它是金钱豹。(11)若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点，则它是长颈鹿。(1

28、2)若某动物是有蹄动物且白色且有黑色条纹，则它是斑马。(13)若某动物是鸟且不会飞且长腿且长脖子且黑白色，则它是驼鸟。(14)若某动物是鸟且不会飞且会游泳且黑白色，则它是企鹅。(15)若某动物是鸟且善飞且不怕风浪，则它是海燕。下面是该规则集所形成的(部分)推理网络：14老虎金钱豹长颈鹿2问题描述由上述动物识别规则组成规则库，推理机分别采用正向推理算法或反向推理算法，实现对动物的查询。如给出初始事实：F1:某动物有毛发F2:吃肉F3:黄褐色F4:有黑色条纹目标条件为：该动物是什么？3规则库扩充在上述规则集(I)基础上增加以下规则集(n)：(1)兔子：有毛发，有奶，善跳跃，唇裂；(2)猫：有毛发，

29、有奶，善捕鼠，脚有肉垫；(3)犀牛：有毛发，有奶，鼻子上有角，褐色，皮糙肉后，皮糙肉厚，有蹄；(4)熊猫：有毛发，有奶，黑眼圈，四肢短小；(5)鹦鹉：鸟类，上嘴鹰钩，会模仿人说话；(6)鸭子：鸟类，腿短，嘴扁平，善潜水游泳；(7)鹰：鸟类，上嘴鹰钩，有爪，吃肉；(8)鸭子：有羽毛，卵生，善游泳，嘴扁平，腿短；(9)鹅：有羽毛，卵生，善潜水游泳，白色或黑色，颈长，嘴大，腿长，颈部有肉只凸起；(10)鸦：有羽毛，卵生，黑色，嘴大；(11)鹰：有羽毛，卵生，有爪，吃肉，上嘴鹰钩；(12)鹦鹉：有羽毛，卵生，上嘴鹰钩，能模仿人说话；(13)青蛙：卵生，生活在水中，生活在陆地，有皮肤呼吸，用肺呼吸，皮肤

30、光滑，吃昆虫，15会变色；(14)蛛螂：卵生，生活在水中，生活在陆地，有皮肤呼吸，用肺呼吸，吃昆虫，皮肤粗糙,四肢扁，背部黑色；(15)蟾蛛：卵生，生活在水中，生活在陆地，有皮肤呼吸，用肺呼吸，吃昆虫，皮肤粗糙;(16)比目鱼：用鲤呼吸，身体有鳍，生活在海洋中，身体扁平，两眼在头部同侧；(17)鲫鱼：用鲤呼吸，身体有鳍，生活在淡水中，身体扁平，头高尾部窄；(18)蛇：生活在陆地，用肺呼吸，胎生，身体有鳞或甲，身体圆而细长，吃小动物；(19)壁虎：生活在陆地，用肺呼吸，胎生，身体有鳞或甲，有四肢，尾巴细长易断，吃昆虫；(20)乌龟：生活在陆地，用肺呼吸，胎生，身体有鳞或甲，身体圆而扁，有坚硬的壳

31、；(21)玳瑁：生活在陆地，用肺呼吸，胎生，身体有鳞或甲，壳为黄褐色，皮肤光滑，有黑斑；(22)鳄鱼：生活在陆地，用肺呼吸，胎生，身体有鳞或甲，有四肢，善游泳，皮硬黑褐色。要求在动物分类规则集(I)的基础上添加上述22条知识，共构成29种动物的知识库系统，对原有动物分类系统进行扩充和修改。三实验要求1以产生式推理模式为基础，实现小型动物分类系统，推理方法可以采用正向推理或反向推理；2要求表示规则的语言必须能体现出规则前提和结论的对应关系，必须能体现出前提和结论中的逻辑关系；3要求能对规则库进行动态地增加、删除和修改操作；4要求用界面显示要查询的初始事实、推理方法、推理中用到的规则和结论。四实验

32、背景知识1产生式系统产生式系统是人工智能系统的一种最典型最普遍的结构形式，许多专家系统都是以产生式系统的形式实现的，有的机器学习系统也是用产生式系统实现的。产生式系统由三部分组成：产生式规则库、推理机和动态数据库，其结构如图所示：图8产生式系统结构2产生式的一般形式产生式的一般形式为：16前件-后件其中，前件就是前提，后件是结论或动作，前件和后件可以是由逻辑运算符ANDORNOT组成的表达式。产生式规则的语义是：如果前提满足，则可得结论或者执行相应的动作，即后件由前件来触发。所以，前件是规则的执行条件，后件是规则体。3产生式规则的程序语言实现在实践中人们往往把规则的前提部分作成形如：条件iAN

33、陈彳2AN0AN陈彳n或条件iOR条彳2OR-OR条件m的形式（其中的条件可以带否定词）；把规则结论部分作成形如断言i/动作iANET言2/动作2ANED-ANEt言k/动作k或断言i/动作iOR断言2/动作2OR-O即言k/动作k的形式，或者进一步简化成断言/动作即仅有一项的形式。如果推理机不能直接支持上述的谓词或元组表示形式，那么，可用通常的记录、数组、结构、函数等数据结构来实现规则中的条件和断言，用通常的赋值式、运算式、函数、过程等形式实现规则中的动作。表示规则的语言在程序执行时必须能体现出规则前提和结论的对应关系，必须能体现出前提和结论中的逻辑关系。例如我们完全可以用一个二元组：（,）

34、表示一个产生式规则。五实验关键技术i产生式系统推理算法产生式系统的推理可分为正向推理和反向推理两种基本方式。（i）正向推理步i将初始事实/数据置入动态数据库；步2用动态数据库中的事实/数据，匹配/测试目标条件，若目标条件满足，则推理成功，结束。步3用规则库中各规则的前提匹配动态数据库中的事实/数据，将匹配成功的规则组成待用规则集；步4若待用规则集为空，则运行失败，退出。步5将待用规则集中各规则的结论加入动态数据库，或者执行其动作，转步2;i7(2)反向推理步1将初始事实/数据置入动态数据库，将目标条件置入目标链；步2若目标链为空，则推理成功，结束。步3取出目标链中第一个目标，用动态数据库中的事

35、实/数据同其匹配，若匹配成功，转步2;步4用规则集中的各规则的结论同该目标匹配，若匹配成功，则将第一个匹配成功且未用过的规则的前提作为新的目标，并取代原来的父目标而加入目标链，转步3;步5若该目标是初始目标，则推理失败，退出。步6将该目标的父目标移回目标链，取代该目标及其兄弟目标，转步3;2事实和规则程序代码示例事实多用数字来表征。规则集在程序中可用数组来存放，如：boolenfactfactnum;structruleintcon10;intres;rulerulesrulenum=2,-1,24,3,-1,24,7,-1,23,8,9,-1,23,24,0,1,4,-1,22,24,5,-

36、1,22,24,6,-1,25,22,21,20,-1,26,22,21,19,-1,27,25,15,16,21,17,-1,28,25,18,20,-1,29,23,10,15,16,11,-1,30,23,10,12,11,-1,31,23,13,14,-1,32规则集也可以记录在.txt文件中，在程序中读入文件，.txt文件示例如下:2口,孑444766-7755b34*222222222220-31-1-1*1IXO.J-o-TfJ201225899256911111111269QO?26,o5223-1312331图9规则集文件示例这里只作示例，具体代表内容不详细介上述示例中的数字

37、代表的是规则中的一些知识,绍。18六实验检查要求1界面显示要求(1)有若干选择动物特征的选择列表；(2)表现判断动物时，使用了哪些规则；(3)显示规则的调用次序；(4)显示最后的结果，包含动物能识别出来和动物不能识别出来两种情况；(5)至少检查两个例子来检验推理系统的正确与全面性。2代码要求要求学生展示如何表征事实和特征的知识、所有规则的代码、控制策略的代码。3讲解要求要求学生讲解采用的推理算法，规则的程序表示方法，规则库如何动态修改等，并说明程序运行效果。4回答辅导老师提出一些问题。5提交实验报告(课后把实验报告和源代码在规定的时间内提交到指定邮箱里)。19实验三TSP问题的遗传算法实现一实

38、验目的1熟悉和掌握遗传算法的基本概念和基本思想；2理解和掌握遗传算法的各个操作算子，能够用选定的编程语言设计简单的遗传优化系统；3通过实验培养学生利用遗传算法进行问题求解的基本技能。二实验内容以N个节点的TSP(旅行商问题)问题为例，应用遗传算法进行求解，求出问题的最优解。1旅行商问题旅行商问题(TravelingSalesmanProblem,TSP),又译为旅行推销员问题、货担郎问题，简称为TSP问题，是最基本的路线问题。假设有n个可直达的城市，一销售商从其中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。TSP问题是组合数学中一个古老

39、而又困难的问题，也是一个典型的组合优化问题，现已归入NP完备问题类。NP问题用穷举法不能在有效时间内求解，所以只能使用启发式搜索。遗传算法是求解此类问题比较实用、有效的方法之一。下面给出30个城市的位置信息：表1OliverTSP问题的30个城市位置坐标城市编号坐标城市编号坐标城市编号坐标1(87,7)11(58,69)21(4,50)2(91,38)12(54,62)22(13,40)3(83,46)13(51,67)23(18,40)4(71,44)14(37,84)24(24,42)5(64,60)15(41,94)25(25,38)6(68,58)16(2,99)26(41,26)7(

40、83,69)17(7,64)27(45,21)8(87,76)18(22,60)28(44,35)9(74,78)19(25,62)29(58,35)10(71,71)20(18,54)30(62,32)最优路径为：123465789101112131415161719182021222324252826272930其路径长度为：424.869292也可取前10个城市的坐标进行测试：20表2OliverTSP问题的10个城市位置坐标城市编号坐标1(87,7)2(91,38)3(83,46)4(71,44)5(64,60)6(68,58)7(83,69)8(87,76)9(74,78)10(71

41、,71)有人求得的最优路径为：03549876210路径长度是166.541336上述10个城市的求解中编号从0开始，把所有路径搜索完又返回到出发节点。2问题描述应用遗传算法求解30/10个节点的TSP(旅行商问题)问题，求问题的最优解。三实验要求1掌握遗传算法的基本原理、各个遗传操作和算法步骤；2要求求出问题最优解，若得不出最优解，请分析原因；3对实验中的几个算法控制参数进行仔细定义，并能通过实验选择参数的最佳值；4要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。四实验背景知识遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程的一种数学仿

42、真，是进化计算的一种最重要形式。遗传算法为那些难以找到传统数学模型的难题找出了一个解决方法。自从Holland于1975年在其著作AdaptationinNaturalandArtificialSystems中首次提出遗传算法以来，经过近30年的研究，现在已发展到一个比较成熟的阶段，并且在实际中已经得到了很好的应用。1遗传算法基本步骤(1)初始化群体；(2)计算群体上每个个体的适应度值；(3)按由个体适应度值所决定的某个规则选择将进入下一代的个体；(4)按概率Pc进行交叉操作；(5)按概率Pm进行变异操作；(6)没有满足某种停止条件，则转第(2)步，否则进入(7);(7)输出种群中适应度值最优

43、的染色体作为问题的满意解或最优解。212参数编码把待求解问题的解空间中的每个可行解看作一个染色体，并用编码的方式来表示，通常编码中的每一位都看作是一个组成该染色体的基因。在TSP问题中，多采用以遍历城市的次序排列进行编码。如对于8个城市的TSP问题，123456781就表示一个可行解。还有其它编码方法如Grefenstette编码，其他可以查阅相关参考文献。3初始群体初始群体是指问题的一组初始可行解，可行解的数量(可定义为变量popsize)和分布对于遗传算法的运行有着很大的影响。实际求解中，初始群体往往采用随机生成的方法。在TSP问题中，随机生成popsize条可行路径序列。4评价函数评价函

44、数即适应度函数，在遗传算法中用来计算一个染色体优劣的函数。在进行遗传操作和种群进化的时候，每个染色体的适应值是决定它是否进入下一轮种群进化的关键因素。适应值高的函数被选作新一代个体的可能性就会大。TSP问题中适应度函数常取路径长度的倒数(或倒数的相关函数)，如：f(X1,X2,Xn)Nn1d(Xi,Xi1)d(XnXi)i1其中，N是个调节参数，根据实验情况进行确定。5选择算子赌轮算法是选择算子中常用的一种方法。它的名称来源于赌博中的轮盘赌，轮盘赌是一种随机性赌博游戏，我们这里就是由它的随机性来选择出某些个体，这些个体相对来说具有较优良的适应性。则每个个体被选中的概率我们定义f(xi)为第i(

45、i=1,2,3.popsize)个染色体的适应度,popsizef(Xj)j1是：P(Xi)f(Xi)图10赌轮盘示意图在算法中赌轮选择法可用下面的子过程来模拟：(1) 在0,1区间内产生一个均匀分布的伪随机数r。(2) 若r=q1,则染色体xi被选中。22若qk1rqk(2kpopsize),则染色体Xk被选中。其中qi称为染色体Xi(i=1,2,.,popsize)的积累概率，其计算公式为：qiP(Xj)j1赌轮选择算子在个体数不太多时，有可能出现不正确反映个体适应度的选择过程，也就是说适应度高的个体有可能反而被淘汰了。为了改进赌轮选择算子的这种缺点，有很多改进的交叉选择算子，如：最佳个体

46、保存法、期望值方法、排序选择方法、联赛选择方法、排挤方法等。6交叉算子在自然界生物进化过程中，起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中，起核心作用的是遗传操作的交叉算子。所谓交叉算子就是把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉算子设计一般与所求解的具体问题有关。下面列举几种在TSP问题中常见的交叉方法：(1)部分匹配交叉(PMXpartiallymappedcrossover)由Goldberg于1985年提出。在PMXB作时，先依据均匀随机分布产生两个位串交叉点，定义这两点之间的区域为匹配区域，并交换两父串的

47、匹配区域。如父串及匹配区域为：A=984|567|1320B=871|230|9546首先交换AB的匹配区域，得：A=984|230|1320B=871|567|9546.一一.再对A、B两子串匹配区域以外的地方出现的遍历重复，依据匹配区域内的位置映射.、一一一?.、一-.关系，逐一交换。如A区域外的2,3,0分别以5,6,7交换，得：_A=984|230|1657B=801|567|9243(2)顺序交叉(OX,ordercrossover)Davis在1985年提出。此方法开始也是选择一个匹配区域：A=984|567|1320B=871|230|9546根据匹配区域的映射关系，在其匹配区域

48、外的相应位置标记HA=984|567|1HHHB=8H1|230|9H4H再移动匹配区域至起点位置，且在其后预留相应于匹配区域的空间(H数目)，然后将其余的码按相对次序排列在预留区后面A=567|HHH|1984B=230|HHH|948123.一.一.一.一.最后将父串A、B的匹配区域互换，并放置到A、B的预留区域，得到子代：-A=567|230|1984B=230|567|9481(3)改进的启发式顺序交叉与OX法有点类似。随机在串中选择一个交配区域，如两父串及交配区域选定为：A=12|3456|789B=98|7654|321将B的交配区域加到A的前面或后面，A的交配区域加到B的前面或后

49、面得到：A=7654|123456789B=3456|987654321.在A中自交配区域后依次删除与交配区相同的城市码，得到最终的两子串为：A=765412389B=3456987217变异算子TSP问题中，经常采取的变异操作主要有：(1)位点变异变异仅以一定的概率(通常较小)对串的某些位作值的变异。(2)逆转变异在串中，随机选择两点，再将这两点内的子串按反序插入到原位置中，如选择A的你.一、一转点为3,6,则经逆转后，变为A。如A=123|456|789A=123|654|789这种变异操作对于TSP问题，就调整前后引起的TSP圈的长度变化而言属于最细微的调整，因而局部优化的精度较高；但码

50、串绝对位置所呈现的“模式”变化较大。(3)对换变异随机选择串中的两点，交换其值(码)。对于串AA=1234|567|89一一一若对换点便4,7,则经对换后，A为：A=1237|564|89这种变异操作在求解TSP问题优化算法中常被采用。在遗传算法中，对换变异操作对码串绝对位置所呈现的“模式”变化影响较大，所需的计算也简单一些，但局部优化精度稍差一点。(4)插入变异从串中随机选择1个码，将此码插入随机选择的插入点中间，对于上述A而言，若取插入码为5,选取插入点位23之间，则A=12534678924此外，还有一些有关上述变异操作的变体形式，如引入连续逆转，进化变异(爬山法)和混合变异等。8Gre

51、fenstette编码在TSP问题中，以遍历城市的次序进行编码是最自然的一种方式，但是这种编码方法所对应的交叉运算和变异运算实现起来比较困难。Grefenstette等人提出了一种新编回路线。对于一个城市列表V,假定对各个城市的一个访问顺序为T=(t1,t2,tn,tn+1)。规定每访问完一个城市，就从未访问城市列表W=V-tl,t2,，ti-1(i=1,2,3,n)中将该城市去掉。然后用第i个所访问城市ti在未访问城市列表W中的对应位置序号gi(1gin-i+1)表示具体访问哪个城市。如此进行一直到处理完V中所有的城市。将全部g顺序排列在一起所得到的一个列表G二(gg2g3-gn)就表示一条

52、巡回路线。TT用GrefenstetteGG设有7个城市分别为V=(a,b,c,d,e,f,g),对于如下两条巡回路线：x=(a,d,b,f,g,e,c,a)y=(b,c,a,d,e,f,g,b)等人所提出的编码方法，其编码为:x=(1313321)y=(2211111)对于TSP使用Grefenstette编码时，个体基因型和个体表现型之间具有对应的关系，也就是它使得经过遗传运算后得到的任意的编码串都对应于一条合法的TSP路径。所以我们就可以用基本遗传算法来求解TSP于是交叉算子可以使用通常的单点或者多点交叉算子；变异运算也可使用常规的一些变异算子，只是基因座gi(i=1,2,3,n)所对应的等位基因值应从1,2,3,，n-i+1中选取。例如将上面的两个TSP个体编码经过单点交叉(交叉点为5)之后可得两个新个体：Gx=(131332J_单点交叉Gx=(13