《人工智能及其应用》实验指导书
三、实验内容
1．参考迷宫求解的核心代码，观察求解过程与思路，画出用A*算法求解迷宫最短路径的流程图。
2．设置不同的地图，以及不同的初始状态和目标状态，记录A*算法的求解结果，包括最短路径、扩展节点数、生成节点数和算法运行时间。
3．对于相同的初始状态和目标状态，设计不同的启发式函数，比较不同启发式函数对迷宫寻路速度的提升效果，包括扩展节点数、生成节点数和算法运行时间。
4．提交实验报告和源程序。 四、实验报告要求：
1．画出A*算法求解迷宫最短路径问题的流程图。
2．试分析不同启发式函数h(n)对迷宫寻路求解的速度提升效果。 3．分析A*算法求解不同规模迷宫最短路径问题的性能。 下面是实验报告的基本内容和书写格式。
实验名称
班级： 学号： 姓名：
一、实验目的 二、实验原理 三、实验结果
按照实验内容，给出相应结果。 四、实验总结
1. 完成实验报告要求2和3。 2. 总结实验心得体会
——————————————————————————————————
13
《人工智能及其应用》实验指导书
实验五 遗传算法实验I
一、实验目的
熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解流程并测试主要参数对结果的影响。 二、实验原理
遗传算法 ( Genetic Algorithms, GA )是基于生物界自然选择和基因遗传学原理的一种广为应用的、高效的随机搜索算法，20世纪60年代由美国的密执根大学的Holland教授首先提出。该算法将优化问题看作是自然界中生物的进化过程，通过模拟大自然中生物进化过程中的遗传规律，来达到寻优的目的。近年来，遗传算法已广泛地应用于作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。
用遗传算法求解优化问题，首先对优化问题的解进行编码，编码后的一个解称为一个染色体，组成染色体的元素称为基因。一个群体由若干个染色体组成，染色体的个数称为群体的规模。在遗传算法中用适应度函数表示环境，它是已编码的解的函数，是一个解适应环境程度的评价。当适应度函数确定后，自然选择规律以适应度函数值的大小来决定一个染色体是否继续生存下去的概率。生存下来的染色体成为种群，它们中的部分或全部以一定的概率进行交叉、变异，从而得到下一代群体。 三、实验条件
Matlab 7.X 的遗传算法工具箱。
四、实验内容：
1．用遗传算法求解下列函数的最大值，设定求解精度到15位小数。
6.452(x?0.125y)(cos(x)?cos(2y))2f(x,y)??3.226y220.8?(x?4.2)?2(y?7)x?[0,10],y?[0,10]1）给出适应度函数（Fitness Function）的M文件（Matlab中要求适应度函数最小化）。
2）设计及选择上述问题的编码、选择操作、交叉操作、变异操作以及控制参数等，填入表1，给出最佳适应度(Best fitness)和最佳个体（Best individual）图。
14
《人工智能及其应用》实验指导书
表1 遗传算法参数的选择 编码 编码方式（population type） 种群规模（population size） 种群参数 初始种群的个体取值范围（Initial range） 个体选择概率分配策略（对应Fitness scaling） 选择操作 个体选择方法（Selection function） 最佳个体保存 优良个体保存数量（Elite count） 交叉概率（Crossover fraction） 交叉操作 交叉方式（Crossover function） 变异操作 变异方式(Mutation function) 最大迭代步数（Generations） 最大运行时间限制（Time limit） 停止参数 最小适应度限制（Fitness limit） 停滞代数（Stall generations） 停滞时间限制（Stall time limit） 3）使用相同的初始种群（Use random state from previous run），设置不同的种群规模（population size），例如5、20和100，初始种群的个体取值范围（Initial range）为[0;1]，其他参数同表1，然后求得相应的最佳适应度(Best fitness)、平均适应度（Mean fitness）和最佳个体（Best individual），填入下表2，分析种群规模对算法性能的影响。
表2 不同的种群规模的GA运行结果 最佳适应度 平均适应度 x 种群规模 5 20 100 最佳个体 y *4) 设置种群规模（population size）为20，初始种群的个体取值范围（Initial range）为[0;10]，选择不同的选择操作、交叉操作和变异操作，其他参数同表1，然后独立运行算法10次，完成下表3，并分析比较采用不同的选择策略、交叉策略和变异策略的算法运行结果。
表3不同的选择策略、交叉策略和变异策略的算法运行结果 遗传算法参数设置（gaoptimset） 1 2 个体选择概率Rank（排序） √ √ @fitscalingrank 分配 FitnessScalingProportional（比率） Fcn @fitscalingprop 选择操作 Roulette（轮盘赌选择） √ √ @selectionroulette 个体选择 SelectionFcn Tournament（竞标赛选择） @selectiontournament √ 单点交叉 @crossoversinglepoint 交叉操作 CrossoverFcn 两点交叉 @crossovertwopoint √ √ √ Uniform（均匀变异）@mutationuniform 变异操作 MutationFcn Gaussian（高斯变异）@mutationgaussian
15
3 √ √ √ √ 4 √ √ √ √ 《人工智能及其应用》实验指导书
最好适应度 最差适应度 平均适应度 备注： 1：
options=gaoptimset('PopulationSize',20,'PopInitRange',[0;10],'FitnessScalingFcn',@fitscalingrank,'SelectionFcn',@selectionroulette,'CrossoverFcn',@crossoversinglepoint,'MutationFcn',@mutationuniform)
2．用遗传算法求解下面一个Rastrigin函数的最小值，设定求解精度到15位小数。
f(x1,x2)?20?x12?x22?10(cos2?x1?cos2?x2)
1）给出适应度函数的M文件（Matlab中要求适应度函数最小化）。
2）设计上述问题的编码、选择操作、交叉操作、变异操作以及控制参数等，填入表4，并画出最佳适应度(Best fitness)和最佳个体（Best individual）图。
表4 遗传算法参数的选择 编码 编码方式（population type） 种群规模（population size） 种群参数 初始种群的个体取值范围（Initial range） 个体选择概率分配策略（对应Fitness scaling） 选择操作 个体选择方法（Selection function） 最佳个体保存 优良个体保存数量（Elite count） 交叉概率（Crossover fraction） 交叉操作 交叉方式（Crossover function） 变异操作 变异方式(Mutation function) 最大迭代步数（Generations） 最大运行时间限制（Time limit） 停止参数 最小适应度限制（Fitness limit） 停滞代数（Stall generations） 停滞时间限制（Stall time limit） 3）设置种群的不同初始范围，例如[1;1.1]、[1;100]和[1;2]，画出相应的最佳适应度值(Best fitness)和平均距离（Distance）图，比较分析初始范围及种群多样性对遗传算法性能的影响。
4）设置不同的交叉概率（Crossover fraction=0、0.8、1），画出无变异的交叉（Crossover fraction=1）、无交叉的变异(Crossover fraction=0)以及交叉概率为0.8时最佳适应度值(Best fitness)和和平均距离（Distance）图，分析交叉和变异操作对算法性能的影响。
16
《人工智能及其应用》实验指导书
五、实验报告要求：
1．画出遗传算法的算法流程图。 2．根据实验内容，给出相应结果。
3. 总结遗传算法的特点，并说明适应度函数在遗传算法中的作用。 下面是实验报告的基本内容和书写格式。
实验名称
班级： 学号： 姓名：
一、实验目的 二、实验原理 三、实验结果
按照实验内容，给出实验结果以及结果分析。 四、实验总结
1. 完成实验报告要求3。 2. 总结实验心得体会
——————————————————————————————————
17