《 人工智能技术导论 》实验指导书

一实验纲要一实验教学的目的、任务与要求将人工智能基础理论应用于实际问题的解决当中,加深学生对所学知识的理解,提高学生的实际动手能力。二实验项目内容1图搜索策略实验用启发式搜索方法/A*算法求解重排九宫问题/八数码问题。2产生式系统的推理以动物识别系统为例,实现基于产生式规则的推理系统。3TSP问题的遗传算法实现以N个结点的TSP问题为例,用遗传算法加以求解。三参考教材人工智能技术导论-第3版，廉师友编著，西安电子科技大学出版社，2007。四使用主要仪器设备说明在Windows2000/XP上，选用Java/C/C++/Matlab等语言进行实现。五实验考核实验为12学时，分4次课完成。每个实验题目在课堂上分别按百分制给出。其中包括课堂纪律、程序运行结果、课堂回答问题及实验报告成绩等。实验课总成绩为3个实验题目的平均成绩。实验课要求学生提前预习，上课时需向辅导老师提交预习报告，报告格式和内容不作过多要求，只需简要说明自己本次实验的大体思想。预习报告形式不限，电子版或手写版均可。1考核方法由各班辅导老师当堂检查源程序和运行结果，并提问相关问题，课堂上给出成绩并记录。每个题目完成后把源代码和实验报告提交，由辅导老师检查实验报告并给出报告成绩。2评分标准每个实验题目根据以下标准进行考核：考勤分20分。按时到课，无违纪现象20分；迟到或事假扣5分；无故缺勤，0分；预习情况10分。认真完成课前预习者10分；不预习，0分；其他情况酌情给分。3)程序内容成绩30分。程序运行正确，达到规定要求，20分；能在规定的要求上完成更完善的功能，或具有一定的界面效果，25分；特别优秀者，30。具体在此基础上酌情给分。4)实验报告成绩30分。实验报告达到要求，最高分为30分。互相抄袭，记0分；其他情况酌情给分。5)回答问题成绩10分。回答问题正确最高分为10分；回答问题均不正确，0分；其他情况酌情给分。6)第一次实验课只记考勤，无故缺勤者总成绩中扣5分。3实验报告在每个实验完成后，在规定时间内提交实验报告。实验报告格式，参见实验报告模板。提交内容：1)实验报告2)源代码提交形式：将实验报告和源代码压缩成zip文件，命名为AI-班号-学号-姓名.zip二上机要求上机之前上机之前做好相关知识复习，上课时捎带课本或参考书。提前了解实验内容，并准备好自己的算法。上机过程根据提前设计的算法，进行上机验证并调试，遇到问题及时解决；上机时间，遵守实验室纪律；在规定的时间内向指导教师提交作业。各自保存好每次实验的源代码，并在规定时间内将源代码和实验报告压缩后提交。三实验内容实验一图搜索与问题求解本次实验主要用来熟悉图搜索技术在具体问题中的求解过程，下面主要以八数码问题展开，也可以以其它题目展开实验。实验1.1启发式搜索一实验目的1熟悉和掌握启发式搜索的定义、估价函数和算法过程；2理解和掌握启发式搜索过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜索顺序；3比较并分析图搜索策略的实质，通过实验理解启发式搜索的意义。二实验内容以重排九宫问题/八数码问题为例，以启发式搜索方法求解给定初始状态和目标状态的最优搜索路径。1重排九宫问题在一个3*3的方格棋盘上放置8个标有1、2、3、4、5、6、7、8数字的将牌，留下一个空格（一般用0表示），规定与空格上下左右相邻的将牌可以移入空格。问题的解是要求寻找一条从某初始状态S0到目标状态Sg的将牌移动路线。下面给出初始状态和目标状态，如：2831647512384765初始棋局目标棋局图1八数码问题示例2问题描述要求用某种启发式搜索方法求解从给定的初始状态到目标状态的移动路线。三实验要求1自己定义启发式函数,能正确求解出从初始状态到目标状态的移动路线；2要求界面显示初始状态、目标状态和中间搜索步骤；3对不可达状态能进行正确识别；4对所采用的启发式函数做出性能分析。四实验背景知识1图搜索技术图搜索技术是人工智能中的一个核心技术之一，人工智能的许多分支领域都涉及到图搜索，在状态图中寻找目标或路径的基本方法就是搜索。由于搜索具有探索性，所以要提高搜索效率（尽快地找到目标节点），或要找最佳路径（最佳解）就必须注意搜索策略。对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索和启发式搜索两大类。用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索。树式盲目搜索就是穷举式搜索，而线式盲目搜索，对于不回溯的就是随机碰撞式搜索，对于回溯的则也是穷举式的搜索。树式穷举式搜索主要有广度优先搜索和深度优先搜索。实践表明，穷举搜索只能解决一些状态空间很小的简单问题，而对于那些大状态空间问题，穷举搜索就不能胜任了。因为大空间问题，往往会导致“组合爆炸”。所以必须探索更有效的搜索方法，如启发式搜索策略。2启发式搜索启发式搜索就是利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。一般来说，启发信息强，可以降低搜索的工作量，但可能导致找不到最优解；而启发信息弱，一般会导致搜索的工作量加大，极端情况下演变为盲目搜索，但有可能找到最优解。我们希望，通过引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。按其用途划分,启发性信息可分为以下三类：(1)用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展。(2)用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。(3)用于删除节点的选择,即用于决定应删除哪些无用节点,以免造成进一步的时空浪费。在启发式搜索中，通常用所谓启发函数来表示启发性信息。启发函数是用来估计搜索树上节点x与目标节点Sg接近程度的一种函数，通常记为h(x)。启发函数并无固定的模式，需要具体问题具体分析。通常可以参考的思路有：一个节点到目标节点的某种距离或差异的度量；一个节点处在最佳路径上的概率；或者根据经验的主观打分等等。在八数码问题种，启发函数h(x)可定义为目标状态与当前状态相同的节点个数，或者当前状态每个节点到目标状态相应节点所需步数的总和（水平的距离与竖直的距离和，也称为曼哈顿路径）。3八数码问题的有解和无解判定 将九宫格中数字顺序排列后，形成一个包含0在内的9位数字序列，该字串可用来表示九宫格的当前状态，其中0表示空格所在位置。当空格上下、左右移动时，易知序列的逆序值奇偶性不会发生改变。由此可知，九宫问题的362,880种状态被分成逆序值为奇数和逆序值为偶数两部分，每一部分内任意两种状态相互可达。在八数码问题中，有些状态之间是不可达的。如果我们能在一开始先判断初始状态和目标状态之间是否可达，这样可以避免不可达状态之间的盲目求解。两个状态之间是否可达可以通过两个状态逆序值的奇偶性进行判断。我们把每个状态看作一个数列，然后计算数列的逆序值，若两个数列逆序值的奇偶性相同，则对应的两个状态是可达的，否则不可达。（注：求逆序值不把空格算在内）。如图2所示状态：23158467图2棋局示例它对应的数列是：23158467（不包括空格）。对于一个数列，数列中每个数的逆序值是指位于这个数前面的比这个数大的数的个数。数列的逆序值就是数列中每个数的逆序值之和。逆序值求法：例：23158467的逆序值为6，求解过程为：0+0+2(1<2,1<3)+0+0+2(4<5,4<8)+1(6<8)+1(7<8)=6而状态12345678的逆序值自然就是0。曼哈顿路径曼哈顿距离（ManhattanDistance），又称为出租车距离，是由十九世纪的赫尔曼·闵可夫斯基所创词汇，是种使用在几何度量空间的几何学用语，用以标明两个点上在标准坐标系上的绝对轴距总和。图3曼哈顿距离示意图我们可以定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标（x1,y1）的点P1与坐标（x2,y2）的点P2的曼哈顿距离为：|x1-x2|+|y1-y2|.要注意的是，曼哈顿距离依赖坐标系统的转度，而非系统在坐标轴上的平移或映射。5康托展开（1）康托展开的公式:把一个整数X展开成如下形式：X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!其中，a为整数，并且0<=a[i]<i(1<=i<=n)（2）康托展开的应用实例{1,2,3,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}排列数中第几个大的数：第一位是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表和CLOSE表，有时需要判断两个节点是否相同，求节点序列的康托展开是个不错的方法。五实验关键技术1全局择优启发式算法步1把初始节点S0放入OPEN表中，计算h(S0)；步2若OPEN表为空，则搜索失败，退出。步3移出OPEN表中第一个节点N放入CLOSED表中，并冠以序号n；步4若目标节点Sg=N，则搜索成功，结束。步5若N不可扩展，则转步2；步6扩展N，计算每个子节点x的函数值h(x)，并将所有子节点配以指向N的返回指针后放入OPEN表中，再对OPEN表中的所有子节点按其函数值大小以升序排序，转步2。2CLOSED表和OPEN表的设计CLOSED表和OPEN表的设计是图搜索程序实现中一个关键问题。我们用一个称为CLOSED表的动态数据结构来专门记录考查过的节点。对于树式搜索来说，CLOSED表中存储的正是一棵不断成长的搜索树；采用一个称为OPEN表的动态数据结构，来专门登记当前待考查的节点。CLOSED表和OPEN表的数据结构设计比较灵活，和具体采用的算法密切相关，这里列举两个示例：（1）采用结构体数组示例typedefstruct{ intindex;//结点序号intParent;//父结点序号intGrid[SIZE][SIZE];//八数码状态intH;//启发式函数值}State;StateOPEN[MAXSIZE];//存放已经生成的未考察的节点StateCLOSE[MAXSIZE];//存放已经考察过得节点（2）采用链表存储示例 structLNode //普通结点,存储八数码信息 {intindex;//结点序号 intH;//启发式函数值intGrid[9];//八数码状态 intzeroposition;//空格的位置 structLNode*parent;//指向父节点 structLNode*child[4];//指向子节点（最多有四个） structLNode*next; }; typedefstructLHead//头结点 { intnum; structLNode*first; }LHead,*LinkList;LinkListLopen，Lclose;//定义指向open、close表的指针六实验检查要求1界面显示要求：（1）包含初始状态和目标状态的显示，可由指导老师随机输入状态进行检查；（2）对不可达状态应给出提示；（3）每次搜索过程的步骤，不要求显示树型结构，只要求（动画）表现，每走一步的状态变化；（4）每走一次搜索步，需要有步数的累积显示；（5）最后有完成一次搜索完毕的结果显示。2代码要求检查时要求提供源代码。3讲解要求要求学生讲解自己设计代码的构架，具体实现方法（包含使用了何种数据结构，open表和close表的结构等）；要求学生说明自己所使用的搜索算法，以及程序运行效果。4回答辅导老师提出的问题。5提交实验报告（课后把实验报告和源代码在规定的时间内提交到指定邮箱里）。实验1.2A*算法搜索一实验目的1加深对各种状态图搜索策略概念的理解；2熟悉和掌握A*搜索的定义、估价函数和算法过程；3理解和掌握A*搜索过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜索顺序；4通过实验掌握估价函数的计算方法，理解估价函数定义的意义。二实验内容以重排九宫问题/八数码问题为例，以A*搜索算法求解给定初始状态和目标状态的最优搜索路径。三实验要求1自己定义估价函数,能正确求解出从初始状态到目标状态的移动路线；2要求界面显示初始状态、目标状态和中间搜索步骤；3对不可达状态能进行正确识别；4对所采用的估价函数做出性能分析，分析g(n)和h(n)的主要作用是什么，以及不同取值的实验效果，并进行分析。四实验背景知识A算法和A*算法是图搜索的两种典型的启发式搜索算法。1A算法A算法是在图搜索算法中的树式搜索算法中增加了估价函数f(x)的一种启发式搜索算法。估价函数的一般形式为：f(x)＝g(x)＋h(x)其中g(x)为从初始节点S0到节点x已经付出的代价，h(x)是启发函数，表示估计搜索树上节点x与目标节点Sg接近程度。估价函数f(x)是从初始节点S0到达节点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)的比重适当，这样才能取得理想的效果。2A*算法对A算法限制其估价函数中的启发函数h(x)，使其满足：对所有的节点x均有：

h(x)≤h*(x)其中h*(x)是从节点x到目标节点的最小代价(若有多个目标节点则为其中最小的一个)，则它就称为A*算法。A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般的有序搜索，总是选择f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点x的估价函数值为两个分量：从起始节点到节点x的代价以及从节点x到达目标节点的代价。3估价函数示例，其中为初始节点到达当前节点的所花步数，为当前节点到目标节点的曼哈顿距离。估计函数为到达当前节点步数和Manhattan距离之和，由相关资料得Manhattan距离满足，其中是当前节点到达目标节点的最小代价，所以此估价函数对应为算法。可以用反证法来证明上述估计函数满足A*算法要求。若存在最佳路径且长度为L1，a为最佳路径上的任意一节点，假设A*没有得出最优解，其求出路径长度为L2>L1，b为其求解路径上的终结点。因为估价函数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放入OPEN表；步2若OPEN表为空，则搜索失败，退出。步3移出OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n；步4若目标节点Sg=N，则搜索成功，结束。步5若N不可扩展，则转步2；步6扩展N，生成一组附有f(x)的子节点，对这组子节点作如下处理：（1）考察是否有已在OPEN表或CLOSED表中存在的节点；若有则再考察其中有无N的先辈节点，若有则删除之；对于其余节点，也删除之，但由于它们又被第二次生成，因而需考虑是否修改已经存在于OPEN表或CLOSE表中的这些节点及其后裔的返回指针和f(x)值，修改原则是“抄f(x)值小的路走”；（2）对其余子节点配上指向N的返回指针后放入OPEN表中，并对OPEN表按f(x)值以升序排序，转步2。六实验检查要求1界面显示要求：（1）包含初始状态和目标状态的显示，可由指导老师随机输入状态进行检查；（2）每次搜索过程的步骤，不要求树型结构，只要求（动画）表现，每走一步的状态变化；（3）每走一次搜索步，需要有步数的累积显示；（4）最后有完成一次搜索完毕的结果显示。2代码要求检查时要求提供源代码。3讲解要求要求学生讲解自己设计代码的构架，如何实现的（包含使用了何种数据结构，open表和close表的结构等）；要求学生说明自己所使用的估价函数，以及程序运行效果。4回答辅导老师提出的问题。5提交实验报告（课后把实验报告和源代码在规定的时间内提交到指定邮箱里）。实验1.3其他应用问题一迷宫问题走迷宫是人们熟悉的一种游戏，如下图就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点，把通道作为边，则该迷宫可以由一个有向图表示(如图4所示)。那么，走迷宫其实就是从该有向图的初始节点S0(入口)出发，寻找目标节点Sg(出口)的问题，或者是寻找通向目标节点(出口)的路径的问题。图4迷宫图请用图搜索算法进行求解。二八皇后问题八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出：在88格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。请用图搜索算法进行求解。三一字棋游戏设有一个三行三列的棋盘，两个棋手A，B轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。初始棋盘各走一步后棋盘图5一字棋设A的棋子用“a”表示，B的棋子用“b”表示。为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下：设棋局为P，估价函数为e(P)。(1)若P是A必胜的棋局，则e(P)=+∞。(2)若P是B必胜的棋局，则e(P)=-∞。(3)若P是胜负未定的棋局，则e(P)=e(+P)-e(-P)其中e(+P)表示棋局P上有可能使a成为三子成一线的数目；e(-P)表示棋局P上有可能使b成为三子成一线的数目。例如，对于上图所示的棋局，则e(P)=6-4=2另外，我们假定具有对称性的两个棋局算作一个棋局。还假定A先走棋，我们站在A的立场上。下图给出了A的第一着走棋生成的博弈树。图中节点旁的数字分别表示相应节点的静态估值或倒推值。由图可以看出，对于A来说最好的一着棋是S3，因为S3比S1和S2有较大的倒推值。图6一字棋极小极大搜索请用图搜索算法进行求解，并要求应用α-β剪枝技术。实验三TSP问题的遗传算法实现一实验目的1熟悉和掌握遗传算法的基本概念和基本思想；2理解和掌握遗传算法的各个操作算子，能够用选定的编程语言设计简单的遗传优化系统；3通过实验培养学生利用遗传算法进行问题求解的基本技能。二实验内容以N个节点的TSP（旅行商问题）问题为例，应用遗传算法进行求解，求出问题的最优解。1旅行商问题旅行商问题（TravelingSalesmanProblem,TSP），又译为旅行推销员问题、货担郎问题，简称为TSP问题，是最基本的路线问题。假设有n个可直达的城市，一销售商从其中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。TSP问题是组合数学中一个古老而又困难的问题，也是一个典型的组合优化问题，现已归入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(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个城市的坐标进行测试：表2

OliverTSP问题的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，71)有人求得的最优路径为：03549876210路径长度是166.541336上述10个城市的求解中编号从0开始，把所有路径搜索完又返回到出发节点。2问题描述应用遗传算法求解30/10个节点的TSP（旅行商问题）问题，求问题的最优解。三实验要求1掌握遗传算法的基本原理、各个遗传操作和算法步骤；2要求求出问题最优解，若得不出最优解，请分析原因；3对实验中的几个算法控制参数进行仔细定义，并能通过实验选择参数的最佳值；4要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。四实验背景知识遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程的一种数学仿真，是进化计算的一种最重要形式。遗传算法为那些难以找到传统数学模型的难题找出了一个解决方法。自从Holland于1975年在其著作《AdaptationinNaturalandArtificialSystems》中首次提出遗传算法以来，经过近30年的研究，现在已发展到一个比较成熟的阶段，并且在实际中已经得到了很好的应用。1遗传算法基本步骤(1)初始化群体;(2)计算群体上每个个体的适应度值;(3)按由个体适应度值所决定的某个规则选择将进入下一代的个体;(4)按概率Pc进行交叉操作;(5)按概率Pm进行变异操作;(6)没有满足某种停止条件，则转第(2)步，否则进入(7)；(7)输出种群中适应度值最优的染色体作为问题的满意解或最优解。2参数编码把待求解问题的解空间中的每个可行解看作一个染色体，并用编码的方式来表示，通常编码中的每一位都看作是一个组成该染色体的基因。在TSP问题中，多采用以遍历城市的次序排列进行编码。如对于8个城市的TSP问题，123456781就表示一个可行解。还有其它编码方法如Grefenstette编码，其他可以查阅相关参考文献。3初始群体初始群体是指问题的一组初始可行解，可行解的数量（可定义为变量popsize）和分布对于遗传算法的运行有着很大的影响。实际求解中，初始群体往往采用随机生成的方法。在TSP问题中，随机生成popsize条可行路径序列。4评价函数评价函数即适应度函数，在遗传算法中用来计算一个染色体优劣的函数。在进行遗传操作和种群进化的时候，每个染色体的适应值是决定它是否进入下一轮种群进化的关键因素。适应值高的函数被选作新一代个体的可能性就会大。TSP问题中适应度函数常取路径长度的倒数（或倒数的相关函数），如：其中，N是个调节参数，根据实验情况进行确定。5选择算子赌轮算法是选择算子中常用的一种方法。它的名称来源于赌博中的轮盘赌，轮盘赌是一种随机性赌博游戏，我们这里就是由它的随机性来选择出某些个体，这些个体相对来说具有较优良的适应性。我们定义f(xi)为第i（i=1,2,3popsize）个染色体的适应度，则每个个体被选中的概率是：22P图10赌轮盘示意图在算法中赌轮选择法可用下面的子过程来模拟：在[0,1]区间内产生一个均匀分布的伪随机数r。若r<=q1，则染色体x1被选中。若，则染色体xk被选中。其中qi称为染色体xi（i=1，2，...,popsize)的积累概率，其计算公式为：赌轮选择算子在个体数不太多时，有可能出现不正确反映个体适应度的选择过程，也就是说适应度高的个体有可能反而被淘汰了。为了改进赌轮选择算子的这种缺点，有很多改进的交叉选择算子，如：最佳个体保存法、期望值方法、排序选择方法、联赛选择方法、排挤方法等。6交叉算子在自然界生物进化过程中，起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中，起核心作用的是遗传操作的交叉算子。所谓交叉算子就是把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉算子设计一般与所求解的具体问题有关。下面列举几种在TSP问题中常见的交叉方法：部分匹配交叉（PMX，partiallymappedcrossover）由Goldberg于1985年提出。在PMX操作时，先依据均匀随机分布产生两个位串交叉点，定义这两点之间的区域为匹配区域，并交换两父串的匹配区域。如父串及匹配区域为：A=984|567|1320B=871|230|9546首先交换A、B的匹配区域，得：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根据匹配区域的映射关系，在其匹配区域外的相应位置标记HA‘=984|567|1HHHB’=8H1|230|9H4H再移动匹配区域至起点位置，且在其后预留相应于匹配区域的空间（H数目），然后将其余的码按相对次序排列在预留区后面A‘’=567|HHH|1984B‘’=230|HHH|9481最后将父串A、B的匹配区域互换，并放置到A‘’、B‘’的预留区域，得到子代：A‘‘’=567|230|1984B‘’’=230|567|9481（3）改进的启发式顺序交叉与OX法有点类似。随机在串中选择一个交配区域，如两父串及交配区域选定为：A=12|3456|789B=98|7654|321将B的交配区域加到A的前面或后面，A的交配区域加到B的前面或后面得到：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圈的长度变化而言属于最细微的调整，因而局部优化的精度较高；但码串绝对位置所呈现的“模式”变化较大。（3）对换变异随机选择串中的两点，交换其值（码）。对于串AA=1234|567|89若对换点位4，7，则经对换后，A’为：A’=1237|564|89这种变异操作在求解TSP问题优化算法中常被采用。在遗传算法中，对换变异操作对码串绝对位置所呈现的“模式”变化影响较大，所需的计算也简单一些，但局部优化精度稍差一点。插入变异从串中随机选择1个码，将此码插入随机选择的插入点中间，对于上述A而言，若取插入码为5，选取插入点位2~3之间，则A’=125346789此外，还有一些有关上述变异操作的变体形式，如引入连续逆转，进化变异（爬山法）和混合变异等。8Grefenstette编码在TSP问题中，以遍历城市的次序进行编码是最自然的一种方式，但是这种编码方法所对应的交叉运算和变异运算实现起来比较困难。Grefenstette等人提出了一种新编回路线。对于一个城市列表V，假定对各个城市的一个访问顺序为T=(t1,t2,…，tn,tn+1）。规定每访问完一个城市，就从未访问城市列表W=V-{t1,t2,…，ti-1}(i=1,2,3,…，n)中将该城市去掉。然后用第i个所访问城市ti在未访问城市列表W中的对应位置序号gi(1≤gi≤n-i+1)表示具体访问哪个城市。如此进行一直到处理完V中所有的城市。将全部gi顺序排列在一起所得到的一个列表G=(g1g2g3…gn）就表示一条巡回路线。设有7个城市分别为V=(a,b,c,d,e,f,g)，对于如下两条巡回路线：Tx=(a,d,b,f,g,e,c,a)Ty=(b,c,a,d,e,f,g,b)用Grefenstette等人所提出的编码方法，其编码为：Gx=(1313321)Gy=(2211111)对于TSP使用Grefenstette编码时，个体基因型和个体表现型之间具有一一对应的关系，也就是它使得经过遗传运算后得到的任意的编码串都对应于一条合法的TSP路径。所以我们就可以用基本遗传算法来求解TSP。于是交叉算子可以使用通常的单点或者多点交叉算子；变异运算也可使用常规的一些变异算子，只是基因座gi(i=1,2,3,…,n)所对应的等位基因值应从{1，2，3，…,n-i+1}中选取。例如将上面的两个TSP个体编码经过单点交叉（交叉点为5）之后可得两个新个体：Gx=(1313321)单点交叉G，x=(1313111)Gy=(2211111)G’y=(2211321)对它们进行解码处理后，可得到两条新的巡回路线：T’x=(a,d,b,f,c,e,g,a)T’y=(b,c,a,d,g,f,e,b)在设计遗传算子时，一般希望它能够有效遗传个体的重要表现性状。对于TSP使用Grefenstette编码时，编码串中前面基因座上的基因值改变，会对后面基因座上的基因值产生不同解释。所以这里使用单点交叉算子，个体在交叉点之前的性状能够被完全继承下来，而在交叉点之后的性状就改变得相当大。9算法控制参数设定（1）N群体大小，即群体中所含个体的数量，根据具体问题来选择，本实验可取20~100；（2）T遗传算法的终止进化代数，本实验可取100~500；（3）Pc交叉概率，它体现了被选择出来进行杂交的个体的比例，一般取0.4~0.9；（4）Pm变异概率，它体现了发生变异的个体的比例。一般取0.001~0.1。五实验关键技术遗传算法求解问题时操作算子比较多，所以在求解时要注意分模块分层次地进行编码。程序实现中的几个关键点：（1）种群规模、进化代数以及交叉和变异概率的定义。（2）染色体编码方法；（3）适应度函数定义方法；（4）选择、交叉和变异这三个遗传操作的定义方法；为了帮助大家快速掌握该方法，附件中给出一个应用遗传算法求解TSP问题的程序模板。该模板中染色体编码采用的是城市序列的自然排列编码方法。六实验检查要求1界面显示要求（1）显示求出的最优解；（2）显示迭代次数及每次迭代求出的局部最优值。2代码要求：要求提供选择、交叉和变异算子的核心代码。3讲解要求要求学生讲解自己设计代码的构架，主要有以下几个要点：（1）染色体编码方法；（2）适应度函数定义方法；（3）选择、交叉和变异这三个遗传操作的定义方法；（4）种群规模、进化代数以及交叉和变异概率的定义；（5）实际求得的最优解，若不是最优解，自己分析可能的原因。4回答辅导老师提出一些问题。5提交实验报告（课后把实验报告和源代码在规定的时间内提交到指定邮箱里）四实验报告模板人工智能实验一实验报告班级：***姓名：****学号：*******一实验题目图搜索与问题求解二实验目的1熟悉和掌握启发式搜索/A*搜索的定义、估价函数和算法过程；2理解和掌握搜索过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜索顺序；3比较并分析图搜索策略的实质，通过实验理解启发式搜索/A*搜索的意义。三实验要求1以九宫问题/八数码问题为例，以某种启发式搜索/A*搜索策略编程演示其搜索过程；2自己定义启发式函数,能正确求解出从初始状态到目标状态的移动路线；3对不可达状态能进行正确识别；4对所采用的启发式函数做出性能分析。四数据结构请说明八数码状态、OPEN表和CLOSE表是如何定义的。五实验算法1说明有解和无解如何判定；2说明启发式函数如何设定；3说明open表和close表如何实现；4说明实验中采用的搜索算法。六实验结果1要求有实验运行结果截图，以及必要的说明；2对不可达状态能进行正确识别；3对所采用的策略进行性能分析。七实验总结及体会人工智能实验二实验报告班级：***姓名：****学号：*******一实验题目产生式系统推理二实验目的1熟悉和掌握产生式系统的构成和运行机制；2掌握基于规则推理的基本方法和技术，掌握正确的正向推理和逆向推理方法；3熟悉在具体问题中如何实现正向推理和逆向推理的求解流程。三实验要求1以产生式推理模式为基础，实现小型动物分类系统，推理方法可以采用正向推理或反向推理；2要求表示规则的语言必须能体现出规则前提和结论的对应关系，必须能体现出前提和结论中的逻辑关系；3要求能对规则库进行动态地增加、删除和修改操作；4要求用界面显示要查询的初始事实、推理方法、推理中用到的规则和结论。四数据结构请说明如何表示事实和特征的知识，如何定义规则。五实验算法1请详细介绍所采用的推理算法，以及程序中如何实现推理机？2对存在矛盾的初始事实/数据是如何判别的？六实验结果1要求有实验运行结果截图，以及必要的说明；2对所实现的产生式系统进行性能分析。七实验总结及体会人工智能实验三实验报告班级：***姓名：****学号：*******一实验题目TSP问题的遗传算法实现二实验目的熟悉和掌握遗传算法的基本概念和基本思想；加深对遗传算法的理解，理解和掌握遗传算法的各个操作算子；理解和掌握利用遗传算法进行问题求解的基本技能。三实验要求1以10/30个结点的TSP问题为例,用遗传算法加以求解；2掌握遗传算法的基本原理、各个遗传操作和算法步骤；3能求出问题最优解，若得不出最优解，请分析原因；4要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。四数据结构请说明染色体个体和群体的定义方法。五实验算法1说明算法中对染色体的编码方法，适应度函数定义方法；2采用的选择、交叉、变异操作算子的具体操作；3实验中采用的算法参数的最佳选择值是多少。六实验结果1要求有实验运行结果截图，以及必要的说明；2要求说明是否搜索到了最优解，如果没有，请分析原因。七实验总结及体会附件1TSP问题的遗传算法程序模板#include"stdafx.h"#include<stdio.h>#include<stdlib.h>#include"math.h"#include"time.h"#defineCITY_NUM10//城市编号是0~CITY_NUM-1#definePOPSIZE20#defineMAXVALUE10000//路径越短越好#defineN1//需要根据实际求得的路径值修正unsignedseed=(unsigned)time(0);intCityPos[10][2]={{87,7},{91,38},{83,46},{71,44},{64,60},{68,58},{83,69},{87,76},{74,78},{71,71}};/*intCityPos[30][2]={{87,7},{91,38},{83,46},{71,44},{64,60},{68,58},{83,69},{87,76},{74,78},{71,71},{58,69},{54,62},{51,67},{37,84},{41,94},{2,99},{7,64},{22,60},{25,62},{18,54},{4,50},{13,40},{18,40},{24,42},{25,38},{41,26},{45,21},{44,35},{58,35},{62,32}};*/doubleCityDistance[CITY_NUM][CITY_NUM];typedefstruct{ intcolony[POPSIZE][CITY_NUM+1];//城市种群,默认出发城市编号为0，则城市编号的最后一个城市还应该为0 doublefitness[POPSIZE];//路径适应值 doubleDistance[POPSIZE];//路径实际长度 intBestRooting[CITY_NUM+1];//最优城市路径序列 doubleBestFitness;//最优路径适应值 doubleBestValue;//最优路径长度}TSP,*PTSP;voidCalculatDist(){inti,j; inttemp1,temp2; for(i=0;i<CITY_NUM;i++){ for(j=0;j<=CITY_NUM;j++){//最后一个城市还应该返回到出发节点 temp1=CityPos[j][0]-CityPos[i][0]; temp2=CityPos[j][1]-CityPos[i][1]; CityDistance[i][j]=sqrt(temp1*temp1+temp2*temp2); } }}boolcheck(PTSPcity,intpop,intnum,intk){//用来检查新生成的节点是否在当前群体中，0号节点是默认出发节点和终止节点 inti; for(i=0;i<=num;i++){ if(k==city->colony[pop][i]) returntrue;//新生成节点存在于已经生成的路径中 } returnfalse;//新生成节点没有存在于已经生成的路径中}voidInitColony(PTSPcity){ inti,j,r; for(i=0;i<POPSIZE;i++){ city->colony[i][0]=0; city->colony[i][CITY_NUM]=0; city->BestValue=MAXVALUE; city->BestFitness=0;//适应值越大越好 } for(i=0;i<POPSIZE;i++){ for(j=1;j<CITY_NUM;j++){ r=rand()%(CITY_NUM-1)+1;//产生1～CITY_NUM-1之间的随机数 while(check(city,i,j,r)){ r=rand()%(CITY_NUM-1)+1; }city->colony[i][j]=r; } }}voidCalFitness(PTSPcity){ inti,j; intstart,end; for(i=0;i<POPSIZE;i++){//求适应值 city->Distance[i]=0; for(j=1;j<=CITY_NUM;j++){ start=city->colony[i][j-1];end=city->colony[i][j]; city->Distance[i]=city->Distance[i]+CityDistance[start][end]; } city->fitness[i]=N/(city->Distance[i]); }}voidSelect(PTSPcity){//选择算子}voidCross(PTSPcity,doublepc){//交叉概率是p}voidMutation(PTSPcity,doublepm){//变异概率是pm}voidOutPut(PTSPcity){ inti,j; printf("Thepopulationis:\n"); for(i=0;i<POPSIZE;i++){ for(j=0;j<=CITY_NUM;j++){ printf("%5d",city->colony[i][j]); } printf("\n"); }}intmain(intargc,char*argv[]){ PTSPcity; doublepcross,pmutation;//交叉概率和变异概率 intMaxEpoc;//最大迭代次数 inti; srand(seed); MaxEpoc=1; pcross=0.6;pmutation=0.05; CalculatDist();//求城市间两两之间的距离 city=(PTSP)malloc(sizeof(TSP)); InitColony(city);//生成初始种群 CalFitness(city);//计算适应值,考虑应该在这里面把最优选出来 for(i=0;i<MaxEpoc;i++){ Select(city);//选择(复制) Cross(city,pcross);//交叉 Mutation(city,pmutation);//变异 CalFitness(city);//计算适应值 } OutPut(city);//输出 return0;}附件2学生作业作品展示一八数码问题求解界面显示示例1）Dos演示界面2）图形界面演示（1）示例一初始状态和目标状态：（空格用0表示）然后系统将按如下界面逐步演示滑块移动过程。（2）示例二（3）示例三数据分析展示（1）示例一搜索步数最小步数效率占用时间1方法一247249.72%125ms2方法二1382820.29%125ms3方法三1362820.59172ms4方法四8153160.20%13703ms（2）示例二初始状态：854617032目标状态：012345678广度优先：用时：167301ms搜索节点：198023个步数：24启发函数1：用时：2ms搜索节点：291个步数：38启发函数2：用时：2ms搜索节点：375个步数：64A*：用时：61ms搜索节点：2685个步数：24初始状态：867201345目标状态：012345678广度优先：用时：73328ms搜索节点：130969个步数：22启发函数1：用时：8ms搜索节点：809个步数：52启发函数2：用时：4ms搜索节点：488个步数：68A*：用时：10ms搜索节点：996个步数：22初始状态：274835160目标状态：012345678广度优先：用时：40010ms搜索节点：97672个步数：22启发函数1：用时：67ms搜索节点：2388个步数：64启发函数2：用时：1ms搜索