人工智能实验指导书作业展示20110427段俊花新解读

人工智能实验指导书+作业展现20110427段俊花-新解读

人工智能实验指导书+作业展现20110427段俊花-新解读

41/41

人工智能实验指导书+作业展现20110427段俊花-新解读

《人工智能技术导论》

实验指导书

西北工业大学计算机学院

目录

一实验大纲1

二上机要求2

三实验内容3

实验一图找寻与问题求解3

实验1.1启迪式找寻3

实验1.2A*算法找寻9

实验1.3其余应用问题12

实验二产生式系统推理错误！不决义书签。

实验三TSP问题的遗传算法实现14

四实验报告模板21

人工智能实验一实验报告21

人工智能实验二实验报告22

人工智能实验三实验报告23

附件1TSP问题的遗传算法程序模板24

附件2学生作业作品展现29

一实验大纲

一实验讲课的目的、任务与要求

将人工智能基础理论应用于实诘问题的解决中间,加深学生对所学知识的理解,提升学

生的实质着手能力。

二实验项目内容

图找寻策略实验

用启迪式找寻方法/A*算法求解重排九宫问题/八数码问题。

产生式系统的推理

以动物鉴识系统为例,实现鉴于产生式规则的推理系统。

3TSP问题的遗传算法实现

以N个结点的TSP问题为例,用遗传算法加以求解。

参照教材

人工智能技术导论-第3版，廉师友编著，西安电子科技大学第一版社，2007。

四使用主要仪器设施说明

在Windows2000/XP上，采纳Java/C/C++/Matlab等语言进行实现。

五实验核查

实验为12学时，分4次课完成。

每个实验题目在讲堂上分别按百分制给出。此中包含讲堂纪律、程序运转结果、讲堂回

答问题及实验报成伟绩等。实验课总成绩为3个实验题目的均匀成绩。

实验课要修业生提早预习，上课时需向指导老师提交预习报告，报告格式和内容不作过

多要求，只需简要说明自己本次实验的大概思想。预习报告形式不限，电子版或手写版均可。

核查方法

由各班指导老师当堂检查源程序和运转结果，并发问有关问题，讲堂上给出成绩并记

录。每个题目完成后把源代码和实验报告提交，由指导老师检查实验报告并给出报成伟绩。

评分标准

每个实验题目依据以下标准进行核查：

1)考勤分20分。准时到课，无违纪现象20分；迟到或事假扣5分；无故少勤，0分；

预习状况10分。认真完成课前预习者10分；不预习，0分；其余状况酌情给分。

3)程序内容成绩30分。程序运转正确，达到规定要求，20分；能在规定的要求上完

成更圆满的功能，或拥有必然的界面见效，25分；特别优异者，30。详尽在此基础上酌情

给分。

4)实验报成伟绩30分。实验报告达到要求，最高分为30分。相互剽窃，记0分；其

他状况酌情给分。

5)回答以下问题成绩10分。回答以下问题正确最高分为10分；回答以下问题均不正确，0分；其余状况酌情给分。

6)第一次实验课只记考勤，无故少勤者总成绩中扣5分。

1

实验报告

在每个实验完成后，在规准时间内提交实验报告。实验报告格式，拜见实验报告模板。

提交内容：1)实验报告2)源代码

提交形式：将实验报告和源代码压缩成zip文件，命名为AI-班号-学号-姓名.zip

二上机要求

上机以前

上机以前做好有关知识复习，上课时捎带课本或参照书。

提早认识实验内容，并准备好自己的算法。

上机过程

依据提早设计的算法，进行上机考证并调试，碰到问题实时解决；

上机时间，恪守实验室纪律；

在规定的时间内向指导教师提交作业。

各自保留好每次实验的源代码，并在规准时间内将源代码和实验报告压缩后提交。

2

三实验内容

实验一图找寻与问题求解

本次实验主要用来熟习图找寻技术在详尽问题中的求解过程，下边主要以八数码问题张开，也能够以其余题目张开实验。

实验1.1启迪式找寻

一实验目的

熟习和掌握启迪式找寻的定义、估价函数和算法过程；

理解和掌握启迪式找寻过程，能够用选定的编程语言求解八数码问题，理解求解流程和找寻序次；

比较并分析图找寻策略的实质，经过实验理解启迪式找寻的意义。

实验内容

以重排九宫问题/八数码问题为例，以启迪式找寻方法求解给定初始状态和目标状态的

最优找寻路径。

重排九宫问题

在一个3*3的方格棋盘上搁置8个标有1、2、3、4、5、6、7、8数字的将牌，留下一

个空格（一般用0表示），规定与空格上下左右相邻的将牌能够移入空格。问题的解是要求

找寻一条从某初始状态S0到目标状态Sg的将牌挪动路线。

下边给出初始状态和目标状态，如：

2

8

3

1

2

3

1

6

4

8

4

7

5

7

6

5

初始棋局

目标棋局

图1

八数码问题示例

问题描绘

要求用某种启迪式找寻方法求解从给定的初始状态到目标状态的挪动路线。

三实验要求

1自己定义启迪式函数,能正确求解出从初始状态到目标状态的挪动路线；

要求界面显示初始状态、目标状态和中间找寻步骤；

对不可以达状态能进行正确鉴识；

对所采纳的启迪式函数做出性能分析。

3

四实验背景知识

图找寻技术

图找寻技术是人工智能中的一个核心技术之一，人工智能的好多分支领域都波及到图搜

索，在状态图中找寻目标或路径的基本方法就是找寻。因为找寻拥有研究性，因此要提升搜

索效率（赶快地找到目标节点），或要找最正确路径（最正确解）就必然注意找寻策略。

关于状态图找寻，已经提出了好多策略，它们大概可分为盲目找寻和启迪式找寻两大类。

用计算机来实现状态图的找寻，有两种最基本的方式：树式找寻和线式找寻。树式盲目找寻

就是穷举式找寻，而线式盲目找寻，关于不回溯的就是随机碰撞式找寻，关于回溯的则也是

穷举式的找寻。树式穷举式找寻主要有广度优先找寻和深度优先找寻。

实践表示，穷举找寻只好解决一些状态空间很小的简单问题，而关于那些大状态空间问

题，穷举找寻就不可以够胜任了。因为大空间问题，常常会致使“组合爆炸”。因此必然研究更

有效的找寻方法，如启迪式找寻策略。

启迪式找寻

启迪式找寻就是利用知识来指引找寻，达到减少找寻范围，降低问题复杂度的目的。一般来说，启迪信息强，能够降低找寻的工作量，但可能致使找不到最优解；而启迪信息弱，

一般会致使找寻的工作量加大，极端状况下演变成盲目找寻，但有可能找到最优解。我们希望，经过引入启迪知识，在保证找到最正确解的状况下，尽可能减少找寻范围，提升找寻效率。

按其用途区分,启迪性信息可分为以下三类：

用于扩展节点的选择,即用于决定应先扩展哪一个节点,免得盲目扩展。

用于生成节点的选择,即用于决定应生成哪些后续节点,免得盲目地生成过多无用

节点。

用于删除节点的选择,即用于决定应删除哪些无用节点,免得造成进一步的时空浪

费。

在启迪式找寻中，平常用所谓启迪函数来表示启迪性信息。启迪函数是用来预计找寻树

上节点x与目标节点Sg凑近程度的一种函数，平常记为h(x)。

启迪函数并没有固定的模式，需要详尽问题详尽分析。平常能够参照的思路有：一个节点

到目标节点的某种距离或差其余胸怀；一个节点处在最正确路径上的概率；或许依据经验的主

观打分等等。在八数码问题种，启迪函数h(x)可定义为目标状态与目前状态相同的节点个

数，或许目前状态每个节点到目标状态相应节点所需步数的总和（水平的距离与竖直的距离

和，也称为曼哈顿路径）。

3八数码问题的有解和无解判断

将九宫格中数字序次摆列后，形成一个包含0在内的9位数字序列，该字串可用来表示九宫格的目前状态，此中0表示空格所在地点。当空格上下、左右挪动时，易知序列的逆序

值奇偶性不会发生改变。由此可知，九宫问题的362,880种状态被分红逆序值为奇数和逆序值为偶数两部分，每一部分内随意两种状态相互可达。

在八数码问题中，有些状态之间是不可以达的。假如我们能在一开始先判断初始状态和目

4

标状态之间能否可达，这样能够防范不可以达状态之间的盲目求解。

两个状态之间能否可达能够经过两个状态逆序值的奇偶性进行判断。我们把每个状态看作一个数列，此后计算数列的逆序值，若两个数列逆序值的奇偶性相同，则对应的两个状态是可达的，不然不可以达。（注：求逆序值不把空格算在内）。

如图2所示状态：

231

584

67

图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|.

要注意的是，曼哈顿距离依靠坐标系统的转度，而非系统在座标轴上的平移或照耀。

康托张开

（1）康托张开的公式:

5

把一个整数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个。123

132213231312321。代表的数字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把初始节点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）采纳结构体数组示例

6

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）包含初始状态和目标状态的显示，可由指导老师随机输入状态进行检查；

2）对不可以达状态应给出提示；

3）每次找寻过程的步骤，不要求显示树型结构，只需求（动画）表现，每走一步的状态变化；

4）每走一次找寻步，需要有步数的积累显示；

5）最后有完成一次找寻完成的结果显示。

代码要求

检查时要求供给源代码。

7

解说要求

要修业生解说自己设计代码的构架，详尽实现方法（包含使用了何种数据结构，open

表和close表的结构等）；要修业生说明自己所使用的找寻算法，以及程序运转见效。

回答指导老师提出的问题。

提交实验报告（课后把实验报告和源代码在规定的时间内提交到指定邮箱里）。

8

实验1.2A*算法找寻

一实验目的

加深对各样状态图找寻策略看法的理解；

*

2熟习和掌握A找寻的定义、估价函数和算法过程；

*

3理解和掌握A找寻过程，能够用选定的编程语言求解八数码问题，理解求解流程和搜

索序次；

经过实验掌握估价函数的计算方法，理解估价函数定义的意义。

实验内容

以重排九宫问题/八数码问题为例，以A*找寻算法求解给定初始状态和目标状态的最优

找寻路径。

三实验要求

1自己定义估价函数,能正确求解出从初始状态到目标状态的挪动路线；

要求界面显示初始状态、目标状态和中间找寻步骤；

对不可以达状态能进行正确鉴识；

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)

9

此中h*(x)是从节点x到目标节点的最小代价(若有多个目标节点则为此中最小的一个)，则

它就称为A*算法。

A*算法是一种有序找寻算法，其特色在于对估价函数的定义上。关于一般的有序找寻，

老是选择f值最小的节点作为扩展节点。因此，f是依据需要找到一条最小代价路径的看法

来预计节点的，因此，可考虑每个节点x的估价函数值为两个重量：从初步节点到节点x

的代价以及从节点x抵达目标节点的代价。

估价函数示例

f(x)g(x)

h(x)，此中g(x)为初始节点抵达目前节点的所花步数，

h(x)为目前节

点到目标节点的曼哈顿距离。

预计函数为抵达目前节点步数和

Manhattan

距离之和，由有关

资料得Manhattan

距离h(x)

知足h(x)

h*(x)，此中h*(x)是目前节点抵达目标节点的最小

代价，因此此估价函数对应为

A*

算法。

能够用反证法来证明上述预计函数知足

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）包含初始状态和目标状态的显示，可由指导老师随机输入状态进行检查；

2）每次找寻过程的步骤，不要求树型结构，只需求（动画）表现，每走一步的状态

10

变化；

3）每走一次找寻步，需要有步数的积累显示；

4）最后有完成一次找寻完成的结果显示。

代码要求

检查时要求供给源代码。

解说要求

要修业生解说自己设计代码的构架，怎样实现的（包含使用了何种数据结构，open

表和close表的结构等）；要修业生说明自己所使用的估价函数，以及程序运转见效。

回答指导老师提出的问题。

5提交实验报告（课后把实验报告和源代码在规定的时间内提交到指定邮箱里）。

11

实验1.3其余应用问题

一迷宫问题

走迷宫是人们熟习的一种游戏，以以下列图就是一个迷宫。假如我们把该迷宫的每一个格

子以及进口和出口都作为节点，把通道作为边，则该迷宫能够由一个有向图表示(如图4所

示)。那么，走迷宫其实就是从该有向图的初始节点S0(进口)出发，找寻目标节点Sg(出口)

的问题，或许是找寻通向目标节点(出口)的路径的问题。

S0

S1S2S3

S4S5S6

S7S8S9

图4迷宫图

Sg

请用图找寻算法进行求解。

二八皇后问题

八皇后问题，是一个古老而有名的问题，是回溯算法的典型例题。该问题是十九世纪

有名的数学家高斯1850年提出：在88格的国际象棋上摆放八个皇后，使其不可以够相互攻击，

即随意两个皇后都不可以够处于同一行、同一列或同一斜线上，问有多少种摆法。高斯以为有

76种方案。1854年在柏林的象棋杂志上不一样样的作者宣布了40种不一样样的解，今后有人用图论

的方法解出92种结果。计算机发明后，有多种方法能够解决此问题。

请用图找寻算法进行求解。

三一字棋游戏

设有一个三行三列的棋盘，两个棋手A，B轮番走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自己的棋子成三子一线为赢。

初始棋盘各走一步后棋盘

图5一字棋

设A的棋子用“a”表示，B的棋子用“b”表示。为了不致于生成太大的博弈树，假定每次仅扩展两层。估价函数定义以下：

设棋局为P，估价函数为e(P)。

若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成为三子成一线的数目。比方，关于上图所示的棋局，则

12

e(P)=6-4=2

其余，我们假定拥有对称性的两个棋局算作一个棋局。还假定A先走棋，我们站在A的立场

上。以下列图给出了A的第一着走棋生成的博弈树。图中节点旁的数字分别表示相应节点的静态

估值或倒推值。由图能够看出，关于A来说最好的一着棋是S3，因为S3比S1和S2有较大的

倒推值。

图6一字棋极小极大找寻

请用图找寻算法进行求解，并要求应用α-β剪枝技术。

13

实验三TSP问题的遗传算法实现

一实验目的

熟习和掌握遗传算法的基本看法和基本思想；

理解和掌握遗传算法的各个操作算子，能够用选定的编程语言设计简单的遗传优化系

统；

经过实验培育学生利用遗传算法进行问题求解的基本技术。

实验内容

以N个节点的TSP（旅游商问题）问题为例，应用遗传算法进行求解，求出问题的最优解。

旅游商问题

旅游商问题（TravelingSalesmanProblem,TSP），又译为旅游销售员问题、货担郎问

题，简称为TSP问题，是最基本的路线问题。假定有n个可直抵的城市，一销售商今后中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在全部可能的路径中求出

路径长度最短的一条。

TSP问题是组合数学中一个古老而又困难的问题，

也是一个典型的组合优化问题，现已

纳入NP齐备问题类。NP问题用穷举法不可以够在有效时间内求解，

因此只好使用启迪式找寻。

遗传算法是求解此类问题比较适用、有效的方法之一。

下边给出

30个城市的地点信息：

表1

OliverTSP问题的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)

最优路径为：

其路径长度为：424.869292

也可取前10个城市的坐标进行测试：

14

表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，71)

有人求得的最优路径为：

路径长度是166.541336

上述10个城市的求解中编号从0开始，把全部路径找寻完又返回到出发节点。

问题描绘

应用遗传算法求解30/10个节点的TSP（旅游商问题）问题，求问题的最优解。

三实验要求

掌握遗传算法的基根源理、各个遗传操作和算法步骤；

要求求出问题最优解，若得不出最优解，请分析原由；

对实验中的几个算法控制参数进行认真定义，并能经过实验选择参数的最正确值；

要求界面显示每次迭代求出的局部最优解和最后求出的全局最优解。

实验背景知识

遗传算法是模拟生物遗传学和自然选择机理，经过人工方式结构的一类优化找寻算法，

是对生物进化过程的一种数学仿真，是进化计算的一种最重要形式。遗传算法为那些难以找

到传统数学模型的难题找出了一个解决方法。自从Holland于1975年在其著作《Adaptation

inNaturalandArtificialSystems》中初次提出遗传算法以来，经过近30年的研究，现

在已发展到一个比较成熟的阶段，而且在实质中已经获得了很好的应用。

遗传算法基本步骤

初始化集体;

计算集体上每个个体的适应度值;

(3)按由个体适应度值所决定的某个规则选择将进入下一代的个体;

按概率Pc进行交叉操作;

按概率Pm进行变异操作;

没有知足某种停止条件，则转第(2)步，不然进入(7)；

输出种群中适应度值最优的染色体作为问题的满意解或最优解。

15

参数编码

把待求解问题的解空间中的每个可行解看作一个染色体，并用编码的方式来表示，平常

编码中的每一位都看作是一个构成该染色体的基因。在TSP问题中，多采纳以遍历城市的序次摆列进行编码。如关于8个城市的TSP问题，123456781就表示一个可行解。还有其余编码方法如Grefenstette编码，其余能够查阅有关参照文件。

3初始集体

初始集体是指问题的一组初始可行解，可行解的数目（可定义为变量popsize）和散布

关于遗传算法的运转有着很大的影响。实质求解中，初始集体常常采纳随机生成的方法。在

TSP问题中，随机生成popsize条可行路径序列。

谈论函数

谈论函数即适应度函数，在遗传算法顶用来计算一个染色体利害的函数。在进行遗传操

作和种群进化的时候，每个染色体的适应值是决定它能否进入下一轮种群进化的重点要素。

适应值高的函数被选作新一代个体的可能性就会大。

TSP问题中适应度函数常取路径长度的倒数（或倒数的有关函数），如：

n1

f(x1,x2,,xn)Nd(xi,xi1)d(xnx1)

i1

此中，N是个调理参数，依据实验状况进行确立。

选择算子

赌轮算法是选择算子中常用的一种方法。它的名称根源于赌博中的轮盘赌，轮盘赌是

一种随机性赌博游戏，我们这里就是由它的随机性来选择出某些个体，这些个体相对来说具

有较优异的适应性。

我们定义f(xi)为第i（i=1,2,3popsize）个染色体的适应度，则每个个体被选中的概率

popsize

是：P(xi)f(xi)f(xj)

j1

22P

图10赌轮盘表示图

在算法中赌轮选择法可用下边的子过程来模拟：

（1）在[0,1]区间内产生一个均匀散布的伪随机数r。

（2）若r<=q1，则染色体x1被选中。

16

（3）若

qk1

r

qk

(2

k

)，则染色体xk被选中。

popsize

此中qi称为染色体xi（i=1，2，...,popsize)

的积累概率，其计算公式为：

i

qi

P(xj)

j

1

赌轮选择算子在个体数不太多时，

有可能出现不正确反应个体适应度的选择过程，

也就

是说适应度高的个体有可能反而被裁汰了。为了改良赌轮选择算子的这类弊端，有好多改良

的交叉选择算子，如：最正确个体保留法、希望值方法、排序选择方法、联赛选择方法、排斥

方法等。

交叉算子

在自然界生物进化过程中，起核心作用的是生物遗传基因的重组(加上变异)。相同，遗

传算法中，起核心作用的是遗传操作的交叉算子。所谓交叉算子就是把两个父代个体的部分

结构加以取代重组而生成新个体的操作。经过交叉，遗传算法的找寻能力得以飞奔提升。

交叉算子设计一般与所求解的详尽问题有关。下边列举几种在TSP问题中常有的交叉方法：

（1）部分般配交叉（PMX，partiallymappedcrossover）

由Goldberg于1985年提出。在PMX操作时，先依据均匀随机散布产生两个位串交叉点，定义这两点之间的地区为般配地区，并交换两父串的般配地区。如父串及般配地区为：

A=984|567|1320

B=871|230|9546

第一交换A、B的般配地区，得：

A’=984|230|1320

B’=871|567|9546

再对A’、B’两子串般配地区之外的地方出现的遍历重复，依据般配地区内的地点照耀

关系，逐个交换。如A’地区外的2，3，0分别以5，6，7交换，得：

A‘’=984|230|1657

B‘’=801|567|9243

(2)序次交叉（OX，ordercrossover）

Davis在1985年提出。此方法开始也是选择一个般配地区：

A=984|567|1320

B=871|230|9546

依据般配地区的照耀关系，在其般配地区外的相应地点标志H

‘

A=984|567|1HHH

’

B=8H1|230|9H4H

再挪动般配地区至起点地点，且在今后预留相应于般配地区的空间（H数目），此后将

其余的码按相对序次摆列在预留区后边

A‘’=567|HHH|1984

B‘’=230|HHH|9481

17

最后将父串A、B的般配地区交换，并搁置到

A‘’、B‘’的预留地区，获得子代：

‘‘’

=567|230|1984

A

B

‘’’=230|567|9481

（3）改良的启迪式序次交叉

与OX法有点近似。

随机在串中选择一个交配地区，如两父串及交配地区选定为：

A=12|3456|789

B=98|7654|321

将B的交配地区加到A的前面或后边，A的交配地区加到B的前面或后边获得：

A’=7654|123456789B’=3456|987654321

在A’中自交配地区后挨次删除与交配区相同的城市码，获得最后的两子串为：

A‘’=765412389

B‘’=345698721

变异算子

TSP问题中，常常采纳的变异操作主要有：

1）位点变异

变异仅以必然的概率（平常较小）对串的某些位作值的变异。

2）逆转变异

在串中，随机选择两点，再将这两点内的子串按反序插入到原地点中，如选择A的你

’

转点为3，6，则经逆转后，变成A。如

A’=123|654|789

这类变异操作关于TSP问题，就调整前后惹起的TSP圈的长度变化而言属于最细微的

调整，因此局部优化的精度较高；但码串绝对地点所表现的“模式”变化较大。

（3）对调变异

随机选择串中的两点，交换其值（码）。关于串A

A=1234|567|89

若对调点位4，7，则经对调后，A’为：

A’=1237|564|89

这类变异操作在求解TSP问题优化算法中常被采纳。在遗传算法中，对调变异操作对码串绝对地点所表现的“模式”变化影响较大，所需的计算也简单调些，但局部优化精度稍差一点。

（4）插入变异

从串中随机选择1个码，将此码插入随机选择的插入点中间，关于上述A而言，若取插

入码为5，采纳插入点位2~3之间，则

A’=125346789

18

其余，还有一些有关上述变异操作的变体形式，如引入连续逆转，进化变异（登山法）

和混淆变异等。

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=(g1

g2g3gn）就表示一条巡回路线。

设有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

。

19

五实验重点技术

遗传算法求解问题时操作算子比好多，因此在求解时要注意分模块分层次地进行编码。

程序实现中的几个重点点：

（1）种群规模、进化代数以及交叉和变异概率的定义。

（2）染色体编码方法；

（3）适应度函数定义方法；

（4）选择、交叉和变异这三个遗传操作的定义方法；

为了帮助大家迅速掌握该方法，附件中给出一个应用遗传算法求解TSP问题的程序模

板。该模板中染色体编码采纳的是城市序列的自然摆列编码方法。

六实验检查要求

界面显示要求

1）显示求出的最优解；

2）显示迭代次数及每次迭代求出的局部最优值。

代码要求：

要求供给选择、交叉和变异算子的核心代码。

解说要求

要修业生解说自己设计代码的构架，主要有以下几个重点：（1）染色体编码方法；（2）

适应度函数定义方法；（3）选择、交叉和变异这三个遗传操作的定义方法；（4）种群规模、

进化代数以及交叉和变异概率的定义；（5）实质求得的最优解，若不是最优解，自己分析可能的原由。

回答指导老师提出一些问题。

提交实验报告（课后把实验报告和源代码在规定的时间内提交到指定邮箱里）

20

四实验报告模板

人工智能实验一实验报告

班级：***姓名：****学号：*******

一实验题目

图找寻与问题求解

二实验目的

*

1熟习和掌握启迪式找寻/A找寻的定义、估价函数和算法过程；

2理解和掌握找寻过程，能够用选定的编程语言求解八数码问题，理解求解流程和找寻

序次；

3比较并分析图找寻策略的实质，经过实验理解启迪式找寻/A*找寻的意义。

三实验要求

1以九宫问题/八数码问题为例，以某种启迪式找寻/A*找寻策略编程演示其找寻过程；

2自己定义启迪式函数,能正确求解出从初始状态到目标状态的挪动路线；

对不可以达状态能进行正确鉴识；

对所采纳的启迪式函数做出性能分析。

数据结构

请说明八数码状态、OPEN表和CLOSE表是怎样定义的。

五实验算法

说明有解和无解怎样判断；

说明启迪式函数怎样设定；

说明open表和close表怎样实现；

说明实验中采纳的找寻算法。

实验结果

要求有实验运转结果截图，以及必需的说明；

对不可以达状态能进行正确鉴识；

对所采纳的策略进行性能分析。

七实验总结及意会

21

人工智能实验二实验报告

班级：***姓名：****学号：*******

一实验题目

产生式系统推理

二实验目的

熟习和掌握产生式系统的构成和运转系统；

掌握鉴于规则推理的基本方法和技术，掌握正确的正向推理和逆向推理方法；

熟习在详尽问题中怎样实现正向推理和逆向推理的求解流程。

实验要求

以产生式推理模式为基础，实现小型动物分类系统，推理方法能够采纳正向推理或反向推理；

要求表示规则的语言必然能表现出规则前提和结论的对应关系，必然能表现出前提和结论中的逻辑关系；

要求能对规则库进行动向地增添、删除和改正操作；

要求用界面显示要查问的初始事实、推理方法、推理顶用到的规则和结论。

四数据结构

请说明怎样表示事实和特色的知识，怎样定义规则。

五实验算法

请详尽介绍所采纳的推理算法，以及程序中怎样实现推理机？

对存在矛盾的初始事实/数据是怎样判其余？

实验结果

要求有实验运转结果截图，以及必需的说明；

对所实现的产生式系统进行性能分析。

实验总结及意会

22

人工智能实验三实验报告

班级：***姓名：****学号：*******

一实验题目

TSP问题的遗传算法实现

二实验目的

熟习和掌握遗传算法的基本看法和基本思想；

加深对遗传算法的理解，理解和掌握遗传算法的各个操作算子；

理解和掌握利用遗传算法进行问题求解的基本技术。

实验要求

以10/30个结点的TSP问题为例,用遗传算法加以求解；

掌握遗传算法的基根源理、各个遗传操作和算法步骤；

能求出问题最优解，若得不出最优解，请分析原由；

4要求界面显示每次迭代求出的局部最优解和最后求出的全局最优解。

数据结构

请说明染色体个体和集体的定义方法。

五实验算法

说明算法中对染色体的编码方法，适应度函数定义方法；

采纳的选择、交叉、变异操作算子的详尽操作；

实验中采纳的算法参数的最正确选择值是多少。

实验结果

要求有实验运转结果截图，以及必需的说明；

要求说明能否找寻到了最优解，假如没有，请分析原由。

实验总结及意会

23

附件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}};

/*int

CityPos[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()

{

24

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++)

25

{

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

}

26

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);//计算适应值,考虑应当在这里面把最精选出来

27

for(i=0;i<MaxEpoc;i++)

{

Select(city);//选择(复制)

Cross(city,pcross);//交叉

Mutation(city,pmutation);//变异

CalFitness(city);//计算适应值

}

OutPut(city);//输出

return0;

}

28

附件2学生作业作品展现

一八数码问题求解

界面显示示例

1）Dos演示界面

29

2）图形界面演示

（1）示例一

初始状态和目标状态：（空格用0表示）

此后系统将按以下界面逐渐演示滑块挪动过程。

（2）示例二

30

（3）示例三

2数据分析展现

（1）示例一

搜寻步

最小步

效率

占用时

数

数

间

1方法一

247

24

9.72%

125ms

2

方法二

138

28

20.29%

125ms

3

方法三

136

28

20.59

172ms

4

方法四

8153

16

0.20%

13703ms

（2）示例二

初始状态：854617032

目标状态：012345678

广度优先：

用时：167301ms找寻节点：

198023个步数：24

启迪函数

1：

用时：2ms

找寻节点：291

个

步数：38

启迪函数

2：

用时：2ms

找寻节点：375个

步数：64

A*：

用时：61ms

找寻节点：2685个

步数：24

初始状态：867201345

目标状态：012345678

广度优先：用时：73328ms找寻节点：130969个步数：22

启迪函数1：用时：8ms找寻节点：809个步数：52

31

启迪函数

2：

用时：4ms

找寻节点：488个

步数：68

A*：

用时：10ms

找寻节点：996个

步数：22

初始状态：274835160

目标状态：012345678

广度优先：

用时：40010ms找寻节点：97672个步数：22

启迪函数

1：

用时：67ms

找寻节点：2388个

步数：64

启迪函数

2：

用时：1ms

找寻节点：158个

步数：32

A*：

用时：9ms

找寻节点：933个

步数：22

（3）示例三

算法/指标

Time（ms）

Step

初始状态

广度优先

全局择优

A*

算法

广度优先

全局择优

A*

算法

123405678

11

0

1

14

28

14

432156780

111

2

3

20

90

20

436578012

461

1

6

26

86

26

781542063

356

1

15

24

50

26

816573240

570

0

51

30

64

30

二动物鉴识系统

界面显示示例（1）示例一

成功的正向查问的结果：

32

成功的反向找寻：

下边是编写框里的文字：

正在试一试能否知足老虎

使用了规则7：食肉动物黄褐色黑色条纹>老虎

食肉动物知足！

黄褐色知足！

黑色条纹不知足！

不知足老虎

正在试一试能否知足金钱豹

使用了规则8：食肉动物黄褐色黑色斑点>金钱豹

食肉动物知足！

黄褐色知足！

黑色斑点知足！

鉴识结果：金钱豹

某次不可以功的反向找寻：

下边是编写框里的内容：

正在试一试能否知足老虎

使用了规则7：食肉动物黄褐色黑色条纹>老虎

正在试一试能否知足食肉动物

使用了规则4：哺乳动物有爪有犬齿目视前面>食肉动物正在试一试能否知足哺乳动物

33

使用了规则0：有奶>哺乳动物

有奶不知足！

使用了规则1：有毛发