智能搜索算法教学实验系统

　　智能搜索算法教学实验系统提供算法学习功能，如果你对算法不了解就可以下载这款软件，软件界面显示算法介绍、算法演示程序、算法验证程序、算法自主实验四个项目，点击对应的项目就可以弹出详细介绍，对于初学算法的朋友很有帮助，软件提供实验功能，当你了解算法以后就可以在软件做实验，使用软件提供的实验案例就可以分析算法运行过程，从而掌握更多知识，这款软件主要介绍了三种算法，支持A*算法、模拟退火算法、遗传算法，每种算法都提供实验程序，如果你需要就下载吧！

软件功能

　　(1) 算法介绍

　　算法介绍子模块的主要功能是向学生介绍A*算法、模拟退火算法、遗传算法等智能搜索算法的特点和流程。

　　(2) 演示程序

　　演示程序子模块的主要功能是展示各算法求解八数码问题、自动寻路、TSP问题、求解函数最值等的搜索过程、运算结果。同时展示不同算法对同一问题的求解性能，以作对比。另外可以通过“运行”、“暂停”、“下一步”，查看算法运行过程中临时变量的状态。

　　(3) 验证程序

　　验证程序子模块的主要功能是通过设定给定问题的规模，以及算法的一些参数设置，测试智能搜索算法对于不同规模问题的解决效果，以及参数设置对算法性能的影响。

　　(4) 自主实验

　　自主实验子模块的主要功能是根据系统所提供的一些算法核心代码，开展各算法的自主实验设计，解决最短路径问题、TSP问题和Flow shop调度问题等一些难题。

　　实验帮助模块提供了各算法的一些核心代码，方便学生开展自主实验设计，同时提供了系统安装、卸载、使用说明、技术支持等系统帮助和系统版本信息。

软件特色

　　本系统是人工智能课程教学实验的计算机辅助系统，包含了A*算法、模拟退火算法、遗传算法、实验帮助和技术支持五大模块

　　各算法模块又提供了算法介绍，以及各算法的演示程序、验证程序和自主实验等子模块。

　　通过使用该系统，可以实现不同智能搜索算法在求解自动寻路、八数码、TSP问题、函数优化问题时的过程演示和对比

　　直观地了解模拟退火算法的新解产生、遗传算法的交叉和变异操作等

　　比较A*算法与深度优先、宽度优先求解八数码问题时在“搜索结果”、“访问结点数”和“耗时”方面的不同，并通过下载核心代码进行自主实验。

安装方法

　　1、打开setup.exe就可以安装软件

　　2、设置软件的安装地址C:\Program Files (x86)\智能搜索算法教学实验系统\

　　3、软件即将安装的界面，点击安装

　　4、提示安装进度界面，等待软件安装结束吧

　　5、这里是软件的安装完毕界面，点击关闭

使用说明

　　1、打开智能搜索算法教学实验系统显示非常多的功能，显示算法实验列表

　　2、点击顶部的算法菜单就可以查看介绍内容，可以对算法介绍查看

　　3、A*(A-Star)算法是一种启发式搜索方法，目前在网络路由算法、机器人探路、人工智能、游戏设计等方面有着普遍的应用

　　4、可以查看自动寻路问题演示、8数码问题演示

　　5、这里就是掩饰界面，软件已经输入数值，点击开始按钮就可以在软件右侧显示数据

　　6、显示OPEN表内容，点击下一步查看弹出结点并扩展，也可以查看CLOSED表

　　7、显示的数据就是这样的，如果你看懂这些算法数据就自己研究吧

　　8、自动寻路问题演示界面如图所示， 在软件设置起点，设置终点，点击开始显示数据

　　9、点击继续就可以自动演示从起点到终点的数据算法

　　10、算法验证程序，显示8数码问题，在软件随机生成数据，点击计算得到结果

　　11、实验要求：在自主实验中,要求用A算法来解决一些实际问题,例如传教士和野人问题、迷宫问题、最短路径问题等。

　　12、实验内容，软件界面显示三个实验，可以查看传教士和野人问题、迷宫问题、最短路径问题

　　13、其他算法介绍自己查看吧，您可以点击实验帮助打开这款软件的说明书

官方教程

　　智能搜索算法教学实验系统

　　遗传算法模块操作说明

　　单击主界面的“遗传算法”菜单，即进入遗传算法模块。该模块同样分为遗传算法介绍、遗传算法演示程序、遗传算法验证程序和遗传算法自主实验四部分。

　　（1）遗传算法介绍

　　单击下拉菜单“遗传算法介绍”，即进入遗传算法介绍子模块，如图1所示，介绍遗传算法的“算法描述”、“算法参数”、“算法特点”等。

　　图1遗传算法介绍

　　（2）遗传算法演示程序

　　（a）遗传算法的交叉操作演示

　　单击下拉菜单“遗传算法演示程序”→“交叉操作演示”，即进入遗传算法的交叉操作演示子模块，如图2所示。

　　由于传统的交叉操作可能出现不满足约束条件的非法染色体，如TSP问题中，整数编码的染色体出现两个标号一样的基因。为解决这一问题，在TSP问题中，采用部分匹配交叉(partially matched crossover, PMX)和顺序交叉(order crossover, OX)。这些方法对于其他一些问题也同样适用。

　　在图2所示的遗传算法交叉操作演示中，给出了部分匹配交叉(PMX)和顺序交叉(OX)的演示，可以通过点击“随机产生”产生新的待交叉染色体组，点击“下一步”可以观察到部分匹配交叉和顺序交叉的交叉操作过程和交叉操作结果。

　　图2遗传算法交叉操作演示界面

　　（b）遗传算法的变异操作演示

　　单击下拉菜单“遗传算法演示程序”→“变异操作演示”，即进入遗传算法的变异演示程序子模块，如图3所示。

　　针对TSP问题，本系统中的遗传算法采用整数编码的方式对染色体进行编码，并设计了4种变异方法。

　　两点互换。随机选取染色体的两个基因进行简单互换。

　　相邻互换。随机选取染色体的两个相邻基因进行简单互换。

　　区间逆转。在原染色体中随机选择两点（称为逆转点），然后将两个逆转点之间的序列逆向排序插入到原位置中。

　　单点移动。在染色体中随机选择一个位置，然后将该位置上的基因插入随机选择的插入点中间。

　　在图3所示的遗传算法变异操作演示中，以8个城市的TSP问题为例，给出了“两点互换”、“相邻互换”、“区间逆转”、“单点移动”四种变异算子的演示，通过演示可以了解四种新解产生函数的差异。

　　图3遗传算法变异操作演示界面

　　（c）遗传算法求解函数极值问题演示

　　单击下拉菜单“遗传算法演示程序”→“函数最值问题演示”，即进入遗传算法求解函数最值问题的演示程序子模块，如图4所示。

　　在图4所示的遗传算法演示程序中，在程序左上方可以修改选择概率分配的方法、交叉率和交叉率，程序的右上方显示所求函数的表达式，点击该区域可以切换查看函数图，程序的上方显示遗传算法求解该函数过程中，所求最优解 和对应参数 和 的变化。可通过单击程序中间的“自动运行”按钮和设置自动运行代数，可进行规定代数的自动运行，程序的下方是手动运行区。

　　图4遗传算法求解函数最值问题的演示程序

　　在图5所示的步骤1“计算”中，可以看到种群中10个染色体的编码、适应度和排名（按适应度从小到大排序），点击“计算选择概率”进入步骤2“选择”。

　　图5 步骤1 计算

　　在图6所示的步骤2“选择”中，一个轮盘按10个染色体的选择概率（按步骤1中的适应度或排名计算而来）分成10份，点击选择后，轮盘转动10次，将选择到的染色体填入右侧的框中，进入步骤3“交叉”。

　　图6 步骤2 选择前和选择后

　　在图7所示的步骤3“交叉”中，步骤2选择的5组染色体以设定的交叉率进行交叉操作，并将交叉结果显示在右侧，进入步骤4“变异”。

　　图7 步骤3 交叉前和交叉后

　　在图8所示的步骤4“变异”中，步骤3中交叉后的结果进入变异步骤，以设定的变异率进行变异操作，并将变异结果显示在右侧，进入步骤1“计算”。

　　图8 步骤4 变异前和变异后

　　在运行的同时，如图9所示，程序上方的曲线图动态显示所求最优解 和对应参数 和 的变化。

　　图9 遗传算法运算结果曲线图

　　（3）遗传算法验证程序

　　单击下拉菜单“遗传算法验证程序”，即进入遗传算法求解TSP问题的验证程序子模块，如图10所示。

　　图10遗传算法解决TSP问题的验证实验

　　图11 遗传算法参数设置页面

　　在图10所示的遗传算法验证程序中，通过点击“参数设置”打开如图11所示的参数设置页面，设置不同的算法参数。另外验证程序左侧下方“状态”提示显示“停止”和“计算中”这两种程序执行信息。

　　点击“开始”按钮后，将调用C++编写的程序进行计算，程序结束后返还结果，在“地图”框上方显示“最好解”、“最差解”和“平均解质量”，“地图”框显示最好解的旅行路线。

　　在图11所示的参数设置页中通过设置遗传算法的参数，通过选择、修改不同的种群规模、遗传代数、选择个体方法、交叉方法、变异方法、个体选择概率分配方法和交叉率、变异率，比较不同的参数设置对遗传算法性能的影响。

　　（4）遗传算法自主实验

　　单击下拉菜单“遗传算法自主实验→实验要求”，即进入遗传算法自主实验的实验要求模块，如图12所示。

　　图12 遗传算法自主实验要求界面

　　单击下拉菜单“遗传自主实验→实验内容”，即进入遗传算法自主实验的实验内容模块，如图13所示。该模块提供了函数优化问题、TSP问题、Flow Shop问题、车辆路径问题等实验题目，要求学生利用“实验帮助”的算法核心代码完成自主实验。

　　图13 遗传算法自主实验内容界面