人工智能实验要求.doc

实验一：产生式系统
——动物识别系统
一、实验目的
1、掌握知识的产生式表示法
2、掌握用程序设计语言编制智能程序的方法
二、实验内容
1、 所选编程语言：C语言；
2.拟订的规则：
（1）若某动物有奶，则它是哺乳动物。
（2）若某动物有毛发，则它是哺乳动物。
（3）若某动物有羽毛，则它是鸟。
（4）若某动物会飞且生蛋，则它是鸟。
（5） 若某动物是哺乳动物且有爪且有犬齿且目盯前方，则它是食肉动物。
（6）若某动物是哺乳动物且吃肉，则它是食肉动物。
（7）若某动物是哺乳动物且有蹄，则它是有蹄动物。
（8）若某动物是哺乳动物且反刍食物，则它是有蹄动物。
（9）若某动物是食肉动物且黄褐色且有黑色条纹，则它是老虎。
（10）若某动物是食肉动物且黄褐色且有黑色斑点，则它是金钱豹。
（11）若某动物是有蹄动物且长腿且长脖子且黄褐色且有暗斑点，则它是长颈鹿。
（12）若某动物是有蹄动物且白色且有黑色条纹，则它是斑马。
（13）若某动物是鸟且不会飞且长腿且长脖子且黑白色，则它是驼鸟。
（14）若某动物是鸟且不会飞且会游泳且黑白色，则它是企鹅。
（15）若某动物是鸟且善飞，则它是海燕。
2、 设计思路：
用户界面：采用问答形式；
知识库（规则库）：存放产生式规则，推理时用到的一般知识和领域知识，比如动物的特征，动物的分类标准，从哺乳动物、食肉动物来分，再具体地添加一些附加特征得到具体动物；建立知识库的同时也建立了事实库。事实库是一个动态链表，一个事实是链表的一个结点。知识库通过事实号与事实库发生联系。
数据库：用来存放用户回答的问题，存放初始状态，中间推理结果，最终结果；
推理机：采用正向推理，推理机是动物识别的逻辑控制器，它控制、协调系统的推理，并利用知识库中的规则对综合数据库中的数据进行逻辑操作。推理机担负两项基本任务：一是检查已有的事实和规则，并在可能的情况下增加新的事实；二是决定推理的方式和推理顺序。将推理机制同规则对象封装在一起，事实对象记录了当前的状态，规则对象首先拿出前提条件的断言（只有这些前提都有符合时才会做这条规则的结论），询问事实对象集，如事实对象集不知道，则询问用户，如所有前提条件都被证实为真则结论为真，否则系统不知道结论真假。
3、 程序流程图：

以老虎，金钱豹，长颈鹿为例画出程序流程图如下：
哺乳动物
有毛发
有奶
吃肉
有爪
有犬齿
目盯前方
有蹄
长腿
长脖子
有暗斑点
黄褐色
有黑色条纹
食肉动物
有黑色斑点
有蹄动物
老虎
金钱豹
长颈鹿

实验二：遗传算法求TSP问题
一、实验目的：
旅行商问题是一个经典的优化组合问题，它可以扩展到很多问题，如电路布线、输油管路铺设等，但是，由于TSP问题的可行解数目与城市数目N是成指数型增长的，是一个NP难问题，因而一般只能近似求解，遗传算法（GA）是求解该问题的较有效的方法之一。遗传算法是美国学者Holland根据自然界“物竞天择，适者生存”现象而提出的一种随机搜索算法，本文采用C/C++语言来实现遗传算法解决TSP问题
二、实验内容：
旅行商问题可以具体描述为：已知n个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。用图论术语来表示，就是有一个图g=(v,e),其中v是定点5，e是边集，设d=(dij)是有顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的最短距离的回路。若对与城市v={v1,v2,v3…vn}的一个访问顺序为t=(t1,t2,t3…,tn)，其中ti∈v(i=1,2,..n),且记tn+1=t1,则旅行上问题的数学模型为式1：
（1）
三、实验环境：
软件环境：Windows XP ， Microsoft Visual Studio C++ 6.0， Notepad
硬件环境：PC机，2.0GHZ主频，2G内存
四、算法流程
4.1遗传算法
遗传算法的基本原理是通过作用于染色体上的基因寻找好的染色体来求解问题，它需要对算法所产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会，在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗产操作后的个体集合形成下一代新的种群，对这个新的种群进行下一轮的进化。
4.2遗传算法的过程
1. 初始化群体。
2. 计算群体上每个个体的适应度值
3. 由个体适应度值所决定的某个规则选择将进入下一代个体。
4. 按概率Pc进行交叉操作。
5. 按概率Pm进行变异操作。
6. 没有满足某种停止条件，则转第2步，否则进入第7步。
7. 输出种群中适应度值最优的染色体作为问题的满意解或最优界。
停止条件有两种：一是完成了预先给定的进化代数则停止；二是种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。

图1：遗传算法过程框图
实验三、状态空间搜索策略——八数码问题求解
一、实验问题
八数码问题求解

二、实验软件
VC6.0 编程语言或其它编程语言

三、实验目的
1. 熟悉人工智能系统中的问题求解过程；
2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；
3. 熟悉对八数码问题的建模、求解及编程语言的应用。

四、实验数据及步骤
（一、） 实验内容
八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。

2 8 3 1 2 3

1 4 8 4

7 6 5 7 6 5

(a) 初始状态 (b) 目标状态
图 1 八数码问题示意图