人工智能及其应用实验指导书

《人工智能及其应用》

实验指导书

浙江工业大学计算机科学与技术学院—人工智能课程组

2011年9月

前言

本实验是为了配合《人工智能及其应用》课程的理论学习而专门设置的。本实验的目的是巩固和加强人工智能的基本原理和方法，并为今后进一步学习更高级课程和信息智能化技术的研究与系统开发奠定良好的基础。

全书共分为八个实验：1.产生式系统实验；2.模糊推理系统实验；3.A*算法求解8数码问题实验；4.A*算法求解迷宫问题实验；5.遗传算法求解函数最值问题实验；6.遗传算法求解TSP问题实验；7.基于神经网络的模式识别实验；8.基于神经网络的优化计算实验。每个实验包括有：实验目的、实验内容、实验条件、实验要求、实验步骤和实验报告等六个项目。

本实验指导书包括两个部分。第一个部分是介绍实验的教学大纲；第二部分是介绍八个实验的内容。

由于编者水平有限，本实验指导书的错误和不足在所难免，欢迎批评指正。

人工智能课程组

2011年9月

目录

实验教学大纲

1

实验一产生式系统实验

3

实验二模糊推理系统实验

5

实验三A*算法实验I

9

实验四A*算法实验II

12

实验五遗传算法实验I

14

实验六遗传算法实验II

18

实验七基于神经网络的模式识别实验

20

实验八

基于神经网络的优化计算实验

24

实验教学大纲

一、学时：16学时，一般安排在第9周至第16周。

二、主要仪器设备及运行环境：PC机、VisualC++6.0、Matlab7.0。

三、实验项目及教学安排

序号

实验名称

实验

平台

实验内容

学时

类型

教学

要求

1

产生式系统应用

VC++

设计知识库，实现系统识别或分类等。

2

设计

课内

2

模糊推理系统应用

Matlab

1）设计洗衣机的模糊控制器；

2）设计两车追赶的模糊控制器。

2

验证

课内

3

A*算法应用I

VC++

设计与实现求解N数码问题的A*算法。

2

综合

课内

4

A*算法应用II

VC++

设计与实现求解迷宫问题的A*算法。

2

综合

课内

5

遗传算法应用I

Matlab

1）求某一函数的最小值；

2）求某一函数的最大值。

2

验证

课内

6

遗传算法应用II

VC++

设计与实现求解不同城市规模的TSP问题的遗传算法。

2

综合

课内

7

基于神经网络的模式识别

Matlab

1）基于BP神经网络的数字识别设计；

2）基于离散Hopfiel神经网络的联想记忆设计。

2

验证

课内

8

基于神经网络的优化计算

VC++

设计与实现求解TSP问题的连续Hopfield神经网络。

2

综合

课内

四、实验成绩评定

实验课成绩单独按五分制评定。凡实验成绩不及格者，该门课程就不及格。学生的实验成绩应以平时考查为主，一般应占课程总成绩的50%，其平时成绩又要以实验实际操作的优劣作为主要考核依据。对于实验课成绩，无论采取何种方式进行考核，都必须按实验课的目的要求，以实际实验工作能力的强弱作为评定成绩的主要依据。

评定各级成绩时，可参考以下标准：

（一）优秀

能正确理解实验的目的要求，能独立、顺利而正确地完成各项实验操作，会分析和处理实验中遇到的问题，能掌握所学的各项实验技能，能较好地完成实验报告及其它各项实验作业，有一定创造精神和能力。有良好的实验室工作作风和习惯。

（二）良好

能理解实验的目的和要求，能认真而正确地完成各项实验操作，能分析和处理实验中遇到的一些问题。能掌握所学实验技能的绝大部分，对难点较大的操作完成有困难。能一般完成实验报告和其它实验作业。有较好的实验习惯和工作作风。

（三）中等

能粗浅理解实验目的要求，能认真努力进行各项实验操作，但技巧较差。能分析和处理实验中一些较容易的问题，掌握实验技能的大部分。有30%掌握得不好。能一般完成各项实验作业和报告。处理问题缺乏条理。工作作风较好。能认真遵守各项规章制度。学习努力。

（四）及格

只能机械地了解实验内容，能一般按图、或按实验步骤“照方抓药”完成实验操作，能完成60%所学的实验技能，有些虽作但不准确。遇到问题常常缺乏解决的办法，在别人启发下能作些简单处理，但效果不理想。能一般完成实验报告，能认真遵守实验室各项规章制度，工作中有小的习惯性毛病（如工作无计划，处理问题缺乏条理）。

（五）不及格

盲目地“照方抓药”，只掌握50%的所学实验技能。有些实验虽能作，但一般效果不好，操作不正确。工作忙乱无条理。一般能遵守实验室规章制度，但常有小的错误。实验报告较多的时候有结果，遇到问题时说不明原因，在教师指导下也较难完成各项实验作业。或有些小聪明但不努力，不求上进。

实验一产生式系统实验

一、实验目的：

熟悉一阶谓词逻辑和产生式表示法，掌握产生式系统的运行机制，以及基于规则推理的基本方法。

二、实验内容

运用所学知识，设计并编程实现一个小型人工智能系统（如分类、诊断、预测等类型）。

三、实验条件：

产生式系统实验程序，如下图1所示。

图1产生式系统实验程序界面

四、实验要求

1.具体应用领域自选，具体系统名称自定；但所做系统绝对不能雷同。

2.用一阶谓词逻辑和产生式规则作为知识表示，利用如图1所示的产生式系统实验程序，建立知识库，分别运行正、反向推理。

3.系统完成后，提交实验报告。

五、实验步骤：

1.基于如图1所示的产生式系统实验程序，设计并实现一个小型人工智能系统：

1）系统设置，包括设置系统名称和系统谓词，给出谓词名及其含义。

2）编辑知识库，通过输入规则或修改规则等，完成整个规则库的建立。

3）建立事实库（综合数据库），输入多条事实或结论。

4）运行推理，包括正向推理和反向推理，给出相应的推理过程、事实区和规则区。

2.撰写实验报告。

六、实验报告

下面是实验报告的基本内容和书写格式。

递交的报告文件名：班级_学号_姓名_实验名称

———————————————————————

实验名称

班级：学号：姓名：

一、实验目的

二、实验内容

三、实验步骤

四、实验结果

1.系统名称及谓词定义

2.系统知识库

3.系统正、反向推理过程、事实区和规则区。

五、实验总结

———————————————————————

实验二模糊推理系统实验

一、实验目的

理解模糊逻辑推理的原理及特点，熟练应用模糊推理，了解可能性理论。

二、实验原理

模糊推理所处理的事物自身是模糊的，概念本身没有明确的外延，一个对象是否符合这个概念难以明确地确定，模糊推理是对这种不确定性，即模糊性的表示与处理。模糊逻辑推理是基于模糊性知识(模糊规则)的一种近似推理，一般采用Zadeh提出的语言变量、语言值、模糊集和模糊关系合成的方法进行推理。

三、实验条件

Matlab7.0的FuzzyLogicTool。

四、实验内容及要求

1.设计洗衣机洗涤时间的模糊控制。已知人的操作经验为：

“污泥越多，油脂越多，洗涤时间越长”；

“污泥适中，油脂适中，洗涤时间适中”；

“污泥越少，油脂越少，洗涤时间越短”。

要求：

（1）假设污泥、油脂、洗涤时间的论域分别为[0,100]、[0,100]和[0,120]，设计相应的模糊推理系统，给出输入、输出语言变量的隶属函数图，模糊控制规则表和推论结果立体图。

（2）假定当前传感器测得的信息为，采用面积重心法反模糊化，给出模糊推理结果，并观察模糊推理的动态仿真环境，给出其动态仿真环境图。

提示：模糊控制规则如下表1所示，其中SD（污泥少）、MD（污泥中）、LD（污泥多）、NG（油脂少）、MG（油脂中）、LG（油脂多）、VS（洗涤时间很短）、S（洗涤时间短）、M（洗涤时间中等）、L（洗涤时间长）、VL（洗涤时间很长）。

图1洗衣机的模糊控制规则表

x

y

z

SD

NG

VS

SD

MG

M

SD

LG

L

MD

NG

S

MD

MG

M

MD

LG

L

LD

NG

M

LD

MG

L

LD

LG

VL

2．假设两汽车均为理想状态，即，Y为速度，U为油门控制输入。

（1）设计模糊推理系统控制2号汽车由静止启动，追赶200m外时速90km的1号汽车并与其保持30m的距离。

（2）在25时刻1号汽车速度改为时速110km时，仍与其保持30m距离。

（3）在35时刻1号汽车速度改为时速70km时，仍与其保持30m距离。

要求：

（1）如下图1所示，设计两输入一输出的模糊推理系统作为2号汽车的模糊控制器，其中输入为误差e和误差的变化，输出为1号汽车的油门控制u，采用面积等分法反模糊化，给出输入、输出语言变量的隶属函数图，模糊控制规则表，推论结果立体图和模糊推理的动态仿真环境图。

图1两车追赶的模糊控制系统框图

（2）用SIMULINK仿真两车追赶的模糊控制系统，给出目标车（1号汽车）的速度曲线图，以及追赶车（2号汽车）的速度曲线图和与目标车（1号汽车）相对距离变化图。

提示：模糊控制规则如下表2所示，其中，r、和油门控制u的论域分别为[0,1]、[-3,3]和[-1,1]，r的隶属函数如图2所示。

表2模糊控制规则表

NB

ZE

PB

PB

ZE

NM

NB

PM

ZE

PM

PB

ZE

ZE

PM

PB

NM

ZE

NM

NB

NB

ZE

NM

NB

图2r的隶属函数图

五、实验报告要求：

1.按照实验要求，给出相应结果。

2．分析隶属度、模糊关系和模糊规则的相互关系。

下面是实验报告的基本内容和书写格式。

实验名称

班级：学号：姓名：

一、实验目的

二、实验内容

三、实验结果

按照实验要求，给出相应结果。

四、实验总结

1.分析隶属度、模糊关系和模糊规则的相互关系。

2.总结实验心得体会

——————————————————————————————————

实验三A*算法实验I

一、实验目的

熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。

二、实验原理

A*算法是一种启发式图搜索算法，其特点在于对估价函数的定义上。对于一般的启发式图搜索，总是选择估价函数f值最小的节点作为扩展节点。因此，f是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数值为两个分量：从起始节点到节点n的实际代价g(n)以及从节点n到达目标节点的估价代价h(n),且，为节点到目的结点的最优路径的代价。

八数码问题是在3×3的九宫格棋盘上，摆有8个刻有1～8数码的将牌。棋盘中有一个空格，允许紧邻空格的某一将牌可以移到空格中，这样通过平移将牌可以将某一将牌布局变换为另一布局。针对给定的一种初始布局或结构（目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。如下图1表示了一个具体的八数码问题求解。

图1八数码问题的求解

三、实验内容

1.参考A*算法核心代码，以8数码问题为例实现A*算法的求解程序（编程语言不限），要求设计两种不同的估价函数。

2.设置相同的初始状态和目标状态，针对不同的估价函数，求得问题的解，并比较它们对搜索算法性能的影响，包括扩展节点数、生成节点数等。

3.设置与上述2相同的初始状态和目标状态，用宽度优先搜索算法（即令估计代价h(n)＝0的A*算法）求得问题的解，以及搜索过程中的扩展节点数、生成节点数。

*4.参考A*算法核心代码，实现A*算法求解15数码问题的程序，设计两种不同的估价函数，然后重复上述2和3的实验内容。

5.提交实验报告和源程序。

四、实验报告要求

1.分析不同的估价函数对A*算法性能的影响。

2.根据宽度优先搜索算法和A*算法求解8、15数码问题的结果，分析启发式搜索的特点。

下面是实验报告的基本内容和书写格式。

实验名称

班级：学号：姓名：

一、实验目的

二、实验原理

三、实验结果

按照实验内容，把结果填入表1。

表1不同启发函数h(n)求解8数码问题的结果比较

启发函数h(n)

不在位数

0

初始状态

目标状态

123804765

123804765

123804765

最优解

扩展节点数

生成节点数

运行时间

*表2不同启发函数h(n)求解15数码问题的结果比较

启发函数h(n)

不在位数

0

初始状态

目标状态

最优解

扩展节点数

生成节点数

运行时间

四、实验总结

1.画出A*算法求解N数码问题的流程图

2.完成实验报告要求1和2。

3.总结实验心得体会

——————————————————————————————————

实验四A*算法实验II

一、实验目的

熟悉和掌握A*算法实现迷宫寻路功能，要求掌握启发式函数的编写以及各类启发式函数效果的比较。

二、实验原理

A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。公式表示为：f(n)=g(n)+h(n)，其中f(n)是节点n从初始点到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)小于等于n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低，但能得到最优解。如果估价值大于实际值，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。

寻路问题常见于各类游戏中角色寻路、三维虚拟场景中运动目标的路径规划、机器人寻路等多个应用领域。迷宫寻路问题是在以方格表示的地图场景中，对于给定的起点、终点和障碍物（墙），如何找到一条从起点开始避开障碍物到达终点的最短路径。

假设在一个n*m的迷宫里，入口坐标和出口坐标分别为(1,1)和(5,5)，每一个坐标点有两种可能：0或1，其中0表示该位置允许通过，1表示该位置不允许通过。

如地图：

00000

10101

00111

01000

00010

最短路径应该是

AB000

1C101

ED111

F1JKL

GHI1M

即：(1,1)-(1,2)-(2,2)-(3,2)-(3,1)-(4,1)-(5,1)-(5,2)-(5,3)-(4,3)-(4,4)-(4,5)-(5,5)

三、实验内容

1．参考迷宫求解的核心代码，观察求解过程与思路，画出用A*算法求解迷宫最短路径的流程图。

2．设置不同的地图，以及不同的初始状态和目标状态，记录A*算法的求解结果，包括最短路径、扩展节点数、生成节点数和算法运行时间。

3．对于相同的初始状态和目标状态，设计不同的启发式函数，比较不同启发式函数对迷宫寻路速度的提升效果，包括扩展节点数、生成节点数和算法运行时间。

4．提交实验报告和源程序。

四、实验报告要求：

1．画出A*算法求解迷宫最短路径问题的流程图。

2．试分析不同启发式函数h(n)对迷宫寻路求解的速度提升效果。

3．分析A*算法求解不同规模迷宫最短路径问题的性能。

下面是实验报告的基本内容和书写格式。

实验名称

班级：学号：姓名：

一、实验目的

二、实验原理

三、实验结果

按照实验内容，给出相应结果。

四、实验总结

1.完成实验报告要求2和3。

2.总结实验心得体会

——————————————————————————————————

实验五遗传算法实验I

一、实验目的

熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解流程并测试主要参数对结果的影响。

二、实验原理

遗传算法(GeneticAlgorithms,GA)是基于生物界自然选择和基因遗传学原理的一种广为应用的、高效的随机搜索算法，20世纪60年代由美国的密执根大学的Holland教授首先提出。该算法将优化问题看作是自然界中生物的进化过程，通过模拟大自然中生物进化过程中的遗传规律，来达到寻优的目的。近年来，遗传算法已广泛地应用于作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。

用遗传算法求解优化问题，首先对优化问题的解进行编码，编码后的一个解称为一个染色体，组成染色体的元素称为基因。一个群体由若干个染色体组成，染色体的个数称为群体的规模。在遗传算法中用适应度函数表示环境，它是已编码的解的函数，是一个解适应环境程度的评价。当适应度函数确定后，自然选择规律以适应度函数值的大小来决定一个染色体是否继续生存下去的概率。生存下来的染色体成为种群，它们中的部分或全部以一定的概率进行交叉、变异，从而得到下一代群体。

三、实验条件

Matlab7.X的遗传算法工具箱。

四、实验内容：

1．用遗传算法求解下列函数的最大值，设定求解精度到15位小数。

给出适应度函数（FitnessFunction）的M文件（Matlab中要求适应度函数最小化）。

设计及选择上述问题的编码、选择操作、交叉操作、变异操作以及控制参数等，填入表1，给出最佳适应度(Bestfitness)和最佳个体（Bestindividual）图。

表1遗传算法参数的选择

编码

编码方式（populationtype）

种群参数

种群规模（populationsize）

初始种群的个体取值范围（Initialrange）

选择操作

个体选择概率分配策略（对应Fitnessscaling）

个体选择方法（Selectionfunction）

最佳个体保存

优良个体保存数量（Elitecount）

交叉操作

交叉概率（Crossoverfraction）

交叉方式（Crossoverfunction）

变异操作

变异方式(Mutationfunction)

停止参数

最大迭代步数（Generations）

最大运行时间限制（Timelimit）

最小适应度限制（Fitnesslimit）

停滞代数（Stallgenerations）

停滞时间限制（Stalltimelimit）

使用相同的初始种群（Userandomstatefrompreviousrun），设置不同的种群规模（populationsize），例如5、20和100，初始种群的个体取值范围（Initialrange）为[0;1]，其他参数同表1，然后求得相应的最佳适应度(Bestfitness)、平均适应度（Meanfitness）和最佳个体（Bestindividual），填入下表2，分析种群规模对算法性能的影响。

表2不同的种群规模的GA运行结果

种群规模

最佳适应度

平均适应度

最佳个体

x

y

5

20

100

*4)设置种群规模（populationsize）为20，初始种群的个体取值范围（Initialrange）为[0;10]，选择不同的选择操作、交叉操作和变异操作，其他参数同表1，然后独立运行算法10次，完成下表3，并分析比较采用不同的选择策略、交叉策略和变异策略的算法运行结果。

表3不同的选择策略、交叉策略和变异策略的算法运行结果

遗传算法参数设置（gaoptimset）

1

2

3

4

选择操作

个体选择概率分配

FitnessScalingFcn

Rank（排序）

@fitscalingrank

√

√

√

Proportional（比率）

@fitscalingprop

√

个体选择

SelectionFcn

Roulette（轮盘赌选择）

@selectionroulette

√

√

√

Tournament（竞标赛选择）

@selectiontournament

√

交叉操作

CrossoverFcn

单点交叉@crossoversinglepoint

√

√

√

两点交叉@crossovertwopoint

√

变异操作

MutationFcn

Uniform（均匀变异）@mutationuniform

√

√

√

Gaussian（高斯变异）@mutationgaussian

√

最好适应度

最差适应度

平均适应度

备注：

1：options=gaoptimset('PopulationSize',20,'PopInitRange',[0;10],'FitnessScalingFcn',@fitscalingrank,'SelectionFcn',@selectionroulette,'CrossoverFcn',@crossoversinglepoint,'MutationFcn',@mutationuniform)

2．用遗传算法求解下面一个Rastrigin函数的最小值，设定求解精度到15位小数。

1）给出适应度函数的M文件（Matlab中要求适应度函数最小化）。

设计上述问题的编码、选择操作、交叉操作、变异操作以及控制参数等，填入表4，并画出最佳适应度(Bestfitness)和最佳个体（Bestindividual）图。

表4遗传算法参数的选择

编码

编码方式（populationtype）

种群参数

种群规模（populationsize）

初始种群的个体取值范围（Initialrange）

选择操作

个体选择概率分配策略（对应Fitnessscaling）

个体选择方法（Selectionfunction）

最佳个体保存

优良个体保存数量（Elitecount）

交叉操作

交叉概率（Crossoverfraction）

交叉方式（Crossoverfunction）

变异操作

变异方式(Mutationfunction)

停止参数

最大迭代步数（Generations）

最大运行时间限制（Timelimit）

最小适应度限制（Fitnesslimit）

停滞代数（Stallgenerations）

停滞时间限制（Stalltimelimit）

设置种群的不同初始范围，例如[1;1.1]、[1;100]和[1;2]，画出相应的最佳适应度值(Bestfitness)和平均距离（Distance）图，比较分析初始范围及种群多样性对遗传算法性能的影响。

设置不同的交叉概率（Crossoverfraction=0、0.8、1），画出无变异的交叉（Crossoverfraction=1）、无交叉的变异(Crossoverfraction=0)以及交叉概率为0.8时最佳适应度值(Bestfitness)和和平均距离（Distance）图，分析交叉和变异操作对算法性能的影响。

五、实验报告要求：

1．画出遗传算法的算法流程图。

2．根据实验内容，给出相应结果。

3.总结遗传算法的特点，并说明适应度函数在遗传算法中的作用。

下面是实验报告的基本内容和书写格式。

实验名称

班级：学号：姓名：

一、实验目的

二、实验原理

三、实验结果

按照实验内容，给出实验结果以及结果分析。

四、实验总结

1.完成实验报告要求3。

2.总结实验心得体会

——————————————————————————————————

实验六遗传算法实验II

一、实验目的

熟悉和掌握遗传算法的原理、流程和编码策略，理解求解TSP问题的流程并测试主要参数对结果的影响，掌握遗传算法的基本实现方法。

二、实验原理

旅行商问题，即TSP问题（TravelingSalesmanProblem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，n个城市之间的相互距离已知，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。TSP问题是一个典型的组合优化问题，该问题可以被证明具有NPC计算复杂性，其可能的路径数目与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本实验采用遗传算法求解。

遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一个最适应环境的类似个体，即得到问题最优的解。

三、实验内容

1、参考实验系统给出的遗传算法核心代码，用遗传算法求解不同规模（例如10个城市，20个城市，100个城市）的TSP问题，把结果填入表1。

表1遗传算法求解不同规模的TSP问题的结果

城市规模

最好适应度

最差适应度

平均适应度

平均运行时间

10

20

100

2、对于同一个TSP问题（例如10个城市），设置不同的种群规模（例如10，20，100）、交叉概率（0，0.5，1）和变异概率（0，0.5，1），把结果填入表2。

3、设置种群规模为100，交叉概率为0.85，变异概率为0.15，然后增加1种变异策略（例如相邻两点互换变异、逆转变异或插入变异等）和1种个体选择概率分配策略（例如按线性排序或者按非线性排序分配个体选择概率）用于求解同一TSP问题（例如10个城市），把结果填入表3。

表2不同的种群规模、交叉概率和变异概率的求解结果

种群规模

交叉概率

变异概率

最好适应度

最差适应度

平均适应度

平均运行时间

10

0.85

0.15

20

0.85

0.15

100

0.85

0.15

100

0

0.15

100

0.5

0.15

100

1

0.15

100

0.85

0

100

0.85

0.5

100

0.85

1

表3不同的变异策略和个体选择概率分配策略的求解结果

变异策略

个体选择概率分配

最好适应度

最差适应度

平均适应度

平均运行时间

两点互换

按适应度比例分配

两点互换

按适应度比例分配

4、提交实验报告和源程序。

四、实验报告要求：

1、画出遗传算法求解TSP问题的流程图。

2、分析遗传算法求解不同规模的TSP问题的算法性能。

3、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。

4、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。

下面是实验报告的基本内容和书写格式。

实验名称

班级：学号：姓名：

一、实验目的

二、实验原理

三、实验结果

按照实验内容，给出相应结果。

四、实验总结

1.完成实验报告要求2,3和4。

2.总结实验心得体会

——————————————————————————————————

实验七基于神经网络的模式识别实验

一、实验目的

理解BP神经网络和离散Hopfield神经网络的结构和原理，掌握反向传播学习算法对神经元的训练过程，了解反向传播公式。通过构建BP网络和离散Hopfield网络模式识别实例，熟悉前馈网络和反馈网络的原理及结构。

二、实验原理

BP学习算法是通过反向学习过程使误差最小，其算法过程从输出节点开始，反向地向第一隐含层(即最接近输入层的隐含层)传播由总误差引起的权值修正。BP网络不仅含有输入节点和输出节点，而且含有一层或多层隐(层)节点。输入信号先向前传递到隐节点，经过作用后，再把隐节点的输出信息传递到输出节点，最后给出输出结果。

离散Hopfield神经网络的联想记忆过程分为学习和联想两个阶段。在给定样本的条件下，按照Hebb学习规则调整连接权值，使得存储的样本成为网络的稳定状态，这就是学习阶段。联想是指在连接权值不变的情况下，输入部分不全或者受了干扰的信息，最终网络输出某个稳定状态。

三、实验条件

Matlab7.X的神经网络工具箱：在Matlab7.X的命令窗口输入nntool，然后在键盘上输入Enter键，即可打开神经网络工具箱。

四、实验内容

1.针对教材P243例8.1，设计一个BP网络结构模型（63-6-9），并以教材图8.5为训练样本数据，图8.6为测试数据。

（1）从Matlab工作空间导入（Import）训练样本数据（inputdata，outputdata）和测试数据（testinputdata），然后新建一个神经网络（NewNetwork），选择参数如下表1，给出BP神经网络结构图。

表1BP网络结构模型的各项参数设置

NetworkName（神经网络名称）

NetworkType（神经网络类型）

Feed-forwardbackprop（前馈反向传播）

Inputranges（输入信息范围）

来自训练样本的输入数据（inputdata）

Trainingfunction（训练函数）

TRAINGD(梯度下降BP算法)

Performancefunction（性能函数）

MSE（均方误差）

Numberoflayers（神经网络层数）

2

Layer1（第1层）的Numberofneurons(神经元个数)

6

Layer1（第1层）的TransferFunction(传递函数)

TANSIG(双曲正切S型函数)

Layer2（第2层）的Numberofneurons(神经元个数)

9

Layer2（第2层）的TransferFunction(传递函数)

LOGSIG（S型函数）

（2）输入训练样本数据（inputdata，outputdata），随机初始化连接权（InitializeWeights），给出BP神经网络训练成功后的误差变化曲线图，训练参数设置如表2所示。

表2BP网络训练参数

训练次数（epochs）

1000

训练时间（time）

Inf

训练目标（goal）

0

学习率（lr）

0.3

最大确认失败次数（max_fail）

5

最小性能梯度（min_grad）

1e-025

两次显示之间的训练步数（show）

25

（3）选择不同的训练函数，例如TRAINGDM（梯度下降动量BP算法）、TRAINLMM（Levenberg-MarquardtBP训练函数），然后输入训练样本数据（inputdata，outputdata），训练参数设置如表2所示，设置相同的初始连接权（RevertWeights），观察不同BP训练算法的学习效果，给出各训练算法下的误差变化曲线图。

（4）在上述3个训练好的BP神经网络中，选择训练误差最小的一个网络，并给出训练后的连接权值和偏置，然后输入测试数据（testinputdata）进行仿真（Simulate），并把训练和测试的结果都导出到工作空间，给出训练后的输出结果和输出误差，以及测试后的输出结果和输出误差。

（5）针对Trainingfunction（训练函数）为TRAINGD的BP网络，然后设置不同的学习率（lr），例如0.01、0.1、0.5、1，观察TRAINGD训练算法的学习效果，给出各学习率下的误差变化曲线图。

2.已知字符点阵为模式，两组训练数据为

大写字母L小写字母l

图1训练数据

设计一个能够存储这两个字符的离散Hopfield神经网络，要求：

（1）给出相应的离散Hopfield神经网络结构图；

（2）计算连接权值及阈值（阈值可设为0）；

（3）输入下列测试数据

图2测试数据

给出网络最终输出的稳定状态。

五、实验报告要求：

1．按照实验内容，给出相应结果。

2．分析比较采用梯度下降训练算法的BP网络学习率的变化对于训练结果的影响。

3.分析比较BP网络和离散Hopfield网络在模式识别方面的异同点。

下面是实验报告的基本内容和书写格式。

实验名称

班级：学号：姓名：

一、实验目的

二、实验原理

三、实验结果

按照实验内容，给出相应结果。

四、实验总结

1.完成实验报告要求2。

2.总结实验心得体会

——————————————————————————————————

实验八基于神经网络的优化计算实验

一、实验目的：

掌握连续Hopfield神经网络的结构和运行机制，理解连续Hopfield神经网络用于优化计算的基本原理,掌握连续Hopfield神经网络用于优化计算的一般步骤。

二、实验原理

连续Hopfield神经网络的能量函数的极小化过程表示了该神经网络从初始状态到稳定状态的一个演化过程。如果将约束优化问题的目标函数与连续Hopfield神经网络的能量函数对应起来，并把约束优化问题的解映射到连续Hopfield神经网络的一个稳定状态，那么当连续Hopfield神经网络的能量函数经演化达到最小值时，此时的连续Hopfield神经网络的稳定状态就对应于约束优化问题的最优解。

三、实验条件：

VC＋＋6.0。

四、实验内容：

1、参考求解TSP问题的连续Hopfield神经网络源代码，给出15个城市和20个城市的求解结果（包括最短路径和最佳路线），分析连续Hopfield神经网络求解不同规模TSP问题的算法性能。

2、对于同一个TSP问题（例如15个城市的TSP问题），设置不同的网络参数，分析不同参数对算法结果的影响。

3、上交源代码。

五、实验报告要求：

1、画出连续Hopfield神经网络求解TSP问题的流程图。

2、根据实验内容，给出相应结果及分析。

3、总结连续Hopfield神经网络和遗传算法用于TSP问题求解时的优缺点。

下面是实验报告的基本内容和书写格式。

实验名称

班级：学号：姓名：

一、实验目的

二、实验原理

三、实验结果

按照实验内容，给出相应结果。

四、实验总结

1.完成实验报告要求1和3。

2.总结实验心得体会

——————————————————————————————————

附录资料：不需要的可以自行删除

Pascal/C/C++语句对比（补充版）

一、Helloworld

先看三种语言的样例：

Pascal

begin

writeln(‘Helloworld’);

end.

C

#include<stdio.h>

intmain()

{

printf("Helloworld!\n");

return0;

}

C++

#include<iostream>

usingnamespacestd;

intmain()

{

cout<<"Helloworld!"<<endl;

return0;

}

从这三个程序可以看到一些最基本的东西。在Pascal中的begin和end，在C/C++里就是{}；Pascal主程序没有返回值，而C/C++返回0（好像在C中可以为NULL）。在C/C++中，main函数以前的是头文件，样例中C为stdio.h，C++除了iostream还有第二行的usingnamespacestd，这个是打开命名空间的，NOIP不会考这个，可以不管，只要知道就行了。

此外说明注释单行用//，段落的话Pascal为{}，C/C++为/**/。

**常用头文件（模板）

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<string>

usingnamespacestd;

intmain()

{

……

system(“pause”);

return0;

}

二、数据类型及定义

这里只列出常用的类型。

1、整型

Pascal

C/C++

范围

shortint

-

-128…127

integer

short

-32768…32767

longint

Int

-2147483648…2147483647

int64

longlong

-9223372036854775808…9223372036854775807

byte

-

0…255

word

unsignedshort

0…65535

longword

unsignedint

0…4294967295

qword

unsignedlonglong

0…18446744073709551615

**当对longlong变量赋值时，后要加LL

Longlongx=6327844632743269843LL

**如果位移x<<2LL

**Linux:printf(“%lld\n”,x);

**Windows:printf(“%I64d\n”,x);

2、实型

Pascal

C/C++

范围

real

float

2.9E-39…1.7E38

single

-

1.5E-45…3.4E38

double

double

5.0E-324…1.7E308

3、字符即字符串

字符在三种语言中都为char，C里没有字符串，只有用字符数组来代替字符串，Pascal和C++均为string。Pascal中字符串长度有限制，为255，C++则没有。

字符串和字符在Pascal中均用单引号注明，在C/C++中字符用单引号，字符串用双引号。

4、布尔类型

Pascal中为boolean，C/C++为bool。值均为True或False。C/C++中除0外bool都为真。

5、定义

常量的定义均为const，只是在C/C++中必须要注明常量的类型。在C/C++中还可以用宏来定义常量，此时不注明类型。

Pascal

C/C++

const

a=60;

b=-a+30;

d=‘‘;

constinta=60;

constintb=-a+30;

conststringd=“”;

defineMAXN501//这个是宏

**宏定义其实就是直接在程序相应的位置替换：

#definerandomizesrand(unsignedtime(NULL))

#definewaitfor(intw=0;w<100000;w++)

变量的定义，C/C++在定义的同时可以赋值：

Pascal

C/C++

var

a,b:integer;

c:char;

d:string;

inta,b=50;

charc=‘A’;

stringd;

boolflag;

三、输入输出

C/C++中没有以回车作为结束的读入方式（就本人所知）。”\n”表示换行。常规输入输出：

Pascal

C

C++

read(a);//读入变量a

readln(a);//读入变a,回车结束

write(a);//输出a

writeln(a);//输出a并换行

scanf(“%d”,&a);

printf(“%d”,a);

printf(“%d\n”,a);

cin>>a;

cout<<a;

cout<<a<<endl;

特别说明C++中cin一个字符的话会自动跳过空格和回车，Pascal和C则会读入空格和回车。在Pascal中writeln(a:n:m)表示在n个字符宽的输出域上输出a保留m位小数。

例如：pascalwrite(a:6)c/c++printf(“%6d”,a)

Pascalwrite(a:6:2)c/c++printf(“%6.2f”,a)

C++如果用cout?(繁琐！！)

需要加头文件#inlude<iomanip>

cout<<setprecision(2)<<a;//作用永久

cout<<setw(6)<<a;//作用临时

以下三个进制设定都是永久作用：

cout<<dec<<a;相当printf(“%d”,a);//十进制

cout<<hex<<a;相当printf(“%X”,a);//十六进制

cout<<oct<<a;相当printf(“%o”,a);//八进制

例如：cout<<12<<hex<<12<<oct<<12<<12<<endl;

输出：12c1414

C的输入输出里面的字符串中%表示变量，%后面的字目表示变量类型。下面是类型表：

%hd

1个short型整数

%d

1个int型整数

%u

1个unsignedint型整数

%I64d

1个longlong型整数

%c

1个字符

%s

1个C字符串

%f

1个float型实数

%lf

1个double型实数

%10.4f

输出1个总宽度为10,保留4位小数的实数

文件输入输出：

Pascal

assign(input,‘test.in’);

assign(output,‘test.out’);

reset(input);

rewrite(output);

read(a,b);

writeln(a,b);

close(input);

close(output);

C

FILE*fin=fopen(“test.in”,“r”);

FILE*fout=fopen(“test.out”,“w”);

fscanf(fin,“%d%d”,&a,&b);

fprintf(fout,“%d%d”,a,b);

fclose(fin);

fclose(fout);

C++

#include<fstream>

usingnamespacestd;

ifstreamfin(“test.in”);

ofstreamfout(“test.out”);

fin>>a>>b;

fout<<a<<b<<endl;

fin.close();

fout.close();

因为C++的读入较慢，个人建议C++的话使用C的输入方式。当然也有人用C的读入，C++的输出的，这种方式我们称之为城乡结合。

**中国计算机学会竞赛须知发布的C读写程序：

（C++也能用，cin,cout,scanf,printf可混用）

#include<stdio.h>

intmain()

{

inta,b;

freopen(“sum.in”,”r”,stdin);

freopen(“sum.out”,”w”,stdout);

scanf(“%d%d”,&a,&b);

printf(“%d\n”,a+b);

return0;

}

或者：

freopen(“sum.in”,”r”,stdin);

freopen(“sum.out”,”w”,stdout);

ios::sync_with_stdio(false);\\取消同步，cin,cout的速度就不慢了！！

cin>>a>>b;

cout<<a+b<<endl;

return0;

以下扩充c/c++混用是可行的：

#include<iostream>

#include<cstdio>

usingnamespacestd;

intmain()

{

inta,b,c,d;

freopen("sum.in","r",stdin);

freopen("sum.out","w",stdout);

scanf("%d%d",&a,&b);

cin>>c>>d;

printf("%d\n",a+b);

cout<<a+b+c+d<<endl;

return0;

}

**如何判断文件结束（EOF）？

C++

while(cin>>s>>n)

{

...

}

C

while(scanf(%s%d",s,&n)!=EOF)

{

...

}

四、赋值语句及运算符号

一一对应的关系

Pascal

C/C++

赋值运算

赋值

:=

=

基本运算

加

+

+

减

-

-

乘

*

*

除（实数）

/

/(double)

除法

取整

div

(int)/(int)

取余

mod

%

比较

等于

=

==

不等于

<>

!=

大于

>

>

大于等于

>=

>=

小于

<

<

小于等于

<=

<=

逻辑

且

and

&&

或

or

||

非

not

!

位运算

左移(*2)

shl

<<

右移(/2)

shr

>>

且

and

&

或

or

|

非

not

~

异或

xor

^

其他

增一

inc(x)

x++

减一

dec(x)

x--

在C/C++中对某个变量自身进行运算可以简写为

变量名运算符号=改变量

如x+=8就表示x=x+8，即inc(x,8)。

在C/C++里还存在一种三目运算

变量名=条件?值A:值B

如x=x>0?x:-x;//表示若x>0则取x，否则取–x，

同ifx>0thenx:=xelsex:=-x;

五、条件语句

1、if

C/C++中if语句的条件必须要用括号括起来，后面不使用then。

Pascal

C/C++

ifa>bthenflag:=true

elseflag:=false;

if(a>b)flag=true;

elseflag=false;

2、多种分支

C/C++中为switch，Pascal为case：

Pascal

C/C++

casexof

1:inc(x);

2:dec(x);

elsex:=x*x;

end;

switch(x)

{

case1:x++;break;

case2:x--;break;

default:x*=x;

}

切记C/C++中一定要写break，后果你可以去掉break，运行看看就知道了。

六、循环语句

1、for

Pascal

C/C++

for变量名:=初始值to(downto)终止值do

for(变量名=初始值;条件;改变方式)

fori:=5to10dodec(a);

//终止值大于初始值用to

fori:=5downto1dodec(a);

//终止值小于于初始值用downto

for(i=5;i<=10;i++)a--;

for(i=5;i>=1;i--)a--;

/*只要i满足条件就会一直循环。

C/C++中i是实数、指针都可以*/

C/C++中for的特殊用法：

//变量为实数

for(doublei=1;i<=2;i*=1.01)

k++;

//变量为指针，->符号为间接引用，后面会提到。

for(type1*p=head->next;p;p=p->next)

printf(“%d”,p->k);

2、while

Pascal

C/C++

while条件do

while(条件)

whilei<>0dodec(i);

while(i!=0)i--;

//也可写作while(i)i--;

//在C/C++中非0即为真。

3、repeat-until&do-while

Pascal

C/C++

repeat语句until结束条件;

do{}while(运行条件)

repeatint(i)untili>100;

do{i++;}while(i<=100);

七、数组

Pascal中数组的下标可以随意定义，而C/C++下标始终为从0开始到(数组大小–1)。

Pascal

C/C++

定义

a:array[1..100]ofinteger;

b:array[1..10,1..10]ofint64;

inta[100];

intb[10][10];

含义

a为大小为100的integer数组，合法下标为1到100

b为大小为10*10的int64数组，合法下标为1,1到10,10

a为大小为100的int数组，合法下标为0到99

b为大小为10*10的int数组，合法下标为0,0到9,9;

使用

inc(a[21]);

b[2,2]:=b[1,1]+b[1,2]+b[2,1];

a[21]++;

b[1][1]=b[0][1]+b[0][0]+b[1][0];

数组清零

Pascal

C/C++

Fillchar(a,sizeof(a),0);

memset(a,0,sizeof(a));

//头文件包含string.h

**如果要填最大：memset(a,127,sizeof(a))（但达不到INT_MAX）

如果要填最小：memset(a,128,sizeof(a))(但达不到INT_MIN）

如果填0：memset(a,0,sizeof(a))

如果填-1：memset(a,-1,sizeof(a))

八、字符串

C风格的字符串就是字符数组。

C++和Pascal的字符串使用基本相同，只是C++中字符串下标以0开始，Pascal以1开始。字符串处理很多这里不一一列举，只写最常用的几个。

Pascal

C(包含<string.h>)

定义用：chars[]

C++（包含<string>）

定义用：strings

输入

输

出

Readln(s);

Writeln(s);

Scanf(“%s”,s);

Printf(“%s\n”,s);

注：不能输入输出c++的字符串

Cin>>s;

Cout<<s<<endl;

注：可以输入输出c的字符串

查找

pos(‘a’,s);//不存在返回0

没有

s.find(‘a’);//不存在返回-1

串

长

len=length(s);

Strlen(s)

len=s.size();或

Len=s.length();

复制

copy(st,pos,num);

st:=‘abcde’;

s:=copy(st,3,2);

//s=‘cd’

Strcpy(s1,s2)

全部复制

Strncpy(s1,s2,n)

前n个复制

但没有从第几个开始的！

substr(pos,n)//返回从pos开始的长度为n的子串;

strings1=“abcde”,s2;

s2=s1.substr(2,2);

//s2=“cd”

插入

insert(obj,target,pos);

st:=‘helloworld’;

st:=insert(‘‘,st,6);

//st=‘helloworld’

没有

insert(pos,s)//在pos位置处插入字符串s;

strings1=“0123”;

s1.insert(1,“XYZ”);//s1=“0XYZ123”

删除

delete(st,pos,num);

st:=‘helloworld’;

st:=delete(st,6,1);

//st=‘helloworld’

没有

erase(pos,n)//从pos位置开始删除n个字符;

strings1="abcdefghi";

s1.erase(5,3);//得到"abcdei"

C++还有以下功能：

用s.replace(2,2,"ttt")可以部分替换

用s.empty()判断是否为空

可访问s[i],位置从0算起

可以s1+s2

可以s1=s2

可以比较s1==s2当然><=>=<=!=都可以比较。

C++字符串整串读入：

getline(cin,s)和cin>>s的区别：

getline(cin,s)

cin>>s

一次性整行读入，直至行末尾。

只读入一个“单词”，遇空格和行末停止。

例如输入；Howareyou?

s=”Howareyou?”

读入整串含空格

例如输入；Howareyou?

s=”How”

如果三个都读：cin>>s1>>s2>>s3

**C++数字与数值之间的转换：

#include<iostream>

#include<string>

#include<sstream>//必须加入

usingnamespacestd;

intmain()

{

stringtext="152";

intnumber;

stringstreamss;

ss<<text;//可以是其他数据类型

ss>>number;//string->int

cout<<number+100<<endl;

ss<<number;//int->string

stringstr=ss.str();

return0;

}

九、过程和函数

1、过程

在C/C++中没有过程，但可以把返回值为“空”的函数理解为过程。

Pascal

C/C++

无参过程

procedure过程名;

说明部分

begin语句部分end;

//说明部分、begin、end语句部分统称为过程体

void函数名();

{

主体部分;

return;

}

带参过程

procedure过程名(形参表)

过程体

void函数名(形参表)

过程体

值传和址传：当一个参数是值传时，形参在子过程中相当于一个局部变量，对它的改变不影响实在的参数值。址传则会影响。下例中a为值传，b为址传。初始a=5,b=5，运行后a=5,b=10；

Pascal

C/C++

vara,b:integer;

proceduredoit(a:integer;varb:integer);

begin

b:=a+b;

a:=a+b;

end;

begin

a:=5;

b:=5;

doit(a,b);

writeln(a,‘‘,b);

end.

voiddoit(inta,int&b)

{

\\a

认为值参，b认为变量传参

b+=a;

a+=b;

return;

}

intmain()

{

inta=5,b=5;

doit(a,b);

cout<<a<<‘‘<<b;

return0;

}

**用若干地址传参可以给调用者传回若干值

Voidtryit(int&x,int&y,int&z)

调用时:tryit(a,b,c),可以传回a,b,c的值。

**用数组名（也是地址）传参可以传回整组的数据

Voidtryit(inta[])

调用时:tryit(x),可以传回整个数组。

例如：

voidtryit(inta[])

{

for(inti=0;i<=10;i++)a[i]=i*2;

return;

}

intmain()

{

intx[10];

tryit(x);

for(inti=0;i<=10;i++)

cout<<x[i]<<endl;

system("pause");

return0;

}

**用指向函数的指针作为参数，可以执行指定的函数。(略)

STL的两个应用：

**C++快排函数

#include<algorithm>

Boolcom(inta,intb)

{

Returna>b;

}

Intmain()

{

Inta[10]={5,7,3,2,6,8,4,3,5,7};

Sort(a,a+10,com);//如果升序可以省略com.

For(