《人工智能及其应用》实验指导书
实验六 遗传算法实验II
一、实验目的
熟悉和掌握遗传算法的原理、流程和编码策略，理解求解TSP问题的流程并测试主要参数对结果的影响，掌握遗传算法的基本实现方法。 二、实验原理
旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访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种个体选择概
18
《人工智能及其应用》实验指导书
率分配策略（例如按线性排序或者按非线性排序分配个体选择概率）用于求解同一TSP问题（例如10个城市），把结果填入表3。
表2 不同的种群规模、交叉概率和变异概率的求解结果 交叉概率 变异概率 最好适应最差适应平均适应度 度 度 0.85 0.15 0.85 0.15 0.85 0.15 0 0.15 0.5 0.15 1 0.15 0.85 0 0.85 0.5 0.85 1 种群规模 10 20 100 100 100 100 100 100 100 平均运行时间 表3 不同的变异策略和个体选择概率分配策略的求解结果 变异策略 个体选择概率分配 最好适应度 最差适应度 平均适应度 平均运行时间 两点互换 按适应度比例分配 两点互换 按适应度比例分配 4、提交实验报告和源程序。 四、实验报告要求：
1、画出遗传算法求解TSP问题的流程图。
2、分析遗传算法求解不同规模的TSP问题的算法性能。
3、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。
4、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。 下面是实验报告的基本内容和书写格式。
实验名称
班级： 学号： 姓名：
一、实验目的 二、实验原理 三、实验结果
按照实验内容，给出相应结果。 四、实验总结
1. 完成实验报告要求2, 3和4。 2. 总结实验心得体会
——————————————————————————————————
19
《人工智能及其应用》实验指导书
实验七 基于神经网络的模式识别实验
一、实验目的
理解BP神经网络和离散Hopfield神经网络的结构和原理，掌握反向传播学习算法对神经元的训练过程，了解反向传播公式。通过构建BP网络和离散Hopfield网络模式识别实例，熟悉前馈网络和反馈网络的原理及结构。 二、实验原理
BP学习算法是通过反向学习过程使误差最小，其算法过程从输出节点开始，反向地向第一隐含层(即最接近输入层的隐含层)传播由总误差引起的权值修正。BP网络不仅含有输入节点和输出节点，而且含有一层或多层隐(层)节点。输入信号先向前传递到隐节点，经过作用后，再把隐节点的输出信息传递到输出节点，最后给出输出结果。
离散Hopfield神经网络的联想记忆过程分为学习和联想两个阶段。在给定样本的条件下，按照Hebb学习规则调整连接权值，使得存储的样本成为网络的稳定状态，这就是学习阶段。联想是指在连接权值不变的情况下，输入部分不全或者受了干扰的信息，最终网络输出某个稳定状态。
三、实验条件
Matlab 7.X 的神经网络工具箱：在Matlab 7.X 的命令窗口输入nntool，然后在键盘上输入Enter键，即可打开神经网络工具箱。 四、实验内容
1. 针对教材P243例8.1，设计一个BP网络结构模型（63-6-9），并以教材图8.5 为训练样本数据，图8.6为测试数据。
（1）从Matlab工作空间导入（Import）训练样本数据（inputdata，outputdata）和测试数据（testinputdata），然后新建一个神经网络（New Network），选择参数如下表1，给出BP神经网络结构图。
表1 BP网络结构模型的各项参数设置 Network Name（神经网络名称） Network Type（神经网络类型） Feed-forward backprop（前馈反向传播） Input ranges（输入信息范围） 来自训练样本的输入数据（inputdata） Training function（训练函数） TRAINGD(梯度下降BP算法) Performance function（性能函数） MSE（均方误差） 2 Number of layers（神经网络层数）
20
《人工智能及其应用》实验指导书
Layer1（第1层）的Number of neurons (神经元个数) Layer1（第1层）的Transfer Function (传递函数) Layer2（第2层）的Number of neurons (神经元个数) Layer2（第2层）的Transfer Function (传递函数) 6 TANSIG(双曲正切S型函数) 2 LOGSIG（S型函数） （2）输入训练样本数据（inputdata，outputdata），随机初始化连接权（Initialize Weights），给出BP神经网络训练成功后的误差变化曲线图，训练参数设置如表2所示。
表2 BP网络训练参数
训练次数（epochs） 训练时间（time） 训练目标（goal） 学习率（lr） 最大确认失败次数（max_fail） 最小性能梯度（min_grad） 两次显示之间的训练步数（show） 1000 Inf 0 0.3 5 1e-025 25 （3）选择不同的训练函数，例如TRAINGDM（梯度下降动量BP算法）、TRAINLMM（Levenberg-Marquardt BP训练函数），然后输入训练样本数据（inputdata，outputdata），训练参数设置如表2所示，设置相同的初始连接权（Revert Weights），观察不同BP训练算法的学习效果，给出各训练算法下的误差变化曲线图。
（4）在上述3个训练好的BP神经网络中，选择训练误差最小的一个网络，并给出训练后的连接权值和偏置，然后输入测试数据（testinputdata）进行仿真（Simulate），并把训练和测试的结果都导出到工作空间，给出训练后的输出结果和输出误差，以及测试后的输出结果和输出误差。
（5）针对Training function（训练函数）为TRAINGD的BP网络，然后设置不同的学习率（lr），例如0.01、0.1、0.5、1，观察TRAINGD训练算法的学习效果，给出各学习率下的误差变化曲线图。 2. 已知字符点阵为 2 ? 2 模式，两组训练数据为 a ( 1) ? ?1 0 ?T ( 大写字母 L ）1 1a(2)??0101?(小写字母l）
T
21
《人工智能及其应用》实验指导书
图1 训练数据
大写字母L 小写字母l
设计一个能够存储这两个字符的离散Hopfield神经网络，要求： （1）给出相应的离散Hopfield神经网络结构图； （2）计算连接权值及阈值（阈值可设为 0）； （3）输入下列测试数据
t(1)??1101?TTt(2)??0011? 图2 测试数据
给出网络最终输出的稳定状态。 五、实验报告要求：
1． 按照实验内容，给出相应结果。
2．分析比较采用梯度下降训练算法的BP网络学习率的变化对于训练结果的影响。
3. 分析比较BP网络和离散Hopfield网络在模式识别方面的异同点。 下面是实验报告的基本内容和书写格式。
实验名称
班级： 学号： 姓名：
一、实验目的 二、实验原理
22