智能信息处理实验报告一、实验目的1)掌握遗传算法的基本原理和程序流程。
2)理解TSP问题的基本概念。
3)能利用遗传算法求解TSP问题。
二、实验环境与设备实验由1个学生独立完成，实验环境：笔记本电脑（Eclipse /Android Studio IDE）。
三、预备知识1、TSP问题基本概念TSP问题即旅行商问题（Traveling Salesperson Problem）。
该问题给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。
其图论描述为：给定图G=(V, A)，其中V为顶点集，A为各顶点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短回路。
2、遗传算法的基本原理遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有信息来指导搜索有希望改善优化质量的状态。
标准遗传算法主要步骤可描述如下：①随机产生一组初始个体构成初始种群。
②计算每一个体的适配值（fitness value，也称为适应度）。
适应度值是对染色体(个体)进行评价的一种指标，是GA进行优化所用的主要信息，它与个体的目标值存在一种对应关系。
③判断算法收敛准则是否满足，若满足，则输出搜索结果；否则执行以下步骤。
④根据适应度值大小以一定方式执行复制操作（也称为选择操作）。
⑤按交叉概率p c执行交叉操作。
⑥按变异概率p m执行变异操作。
⑦返回步骤②。
标准遗传算法流程图下图所示。
图2.1 标准遗传算法流程图四、实验内容1、设计算法的编码方式路径编码是描述TSP 解的最常用的一种策略。
所谓路径编码，即直接采用城市在路径中的位置来构造用于优化的状态。
例如：设九城市TSP 问题的路径为5-4-1-7-9-8-6-2-3， 对应的路径编码为：(5 4 1 7 9 8 6 2 3)。
这种编码形式自然直观，易于加入启发式信息，也有利于优化操作的设计。
2、设计遗传算法的适应度函数对个体i ，计算与路径编码相对应的距离，设为d i 。
显然距离值d i 越大，适应度值应越小。
因此，适应度函数可定义为：1iFit d 。
这里我们在算法程序中个体适应度函数定义为：tempf[k] = 10.0 / fitness[k]。
3、设计遗传算法的选择操作选择是用来确定交叉个体，以及被选个体将产生多少个子代个体。
它是基于适应度值计算基础上进行的。
在实现算法的程序中，挑选种群中适应度最高的个体。
挑选函数为NN计算各个体的适配值（适应度）算法收敛准则满足？Y random[0,1]<P c ?复制（选择）输出搜索结果交叉Y random[0,1]<P m ?变异N随机产生初始种群 YselectBestGh()。
挑选策略为赌轮选择策略。
函数实现：public void select() { int k , i , selectId ; float ran1;for (k = 1; k < scale ; k ++) {ran1 = (float ) (random .nextInt(65535) % 1000 / 1000.0);// 产生方式for (i = 0; i < scale ; i ++) { if (ran1 <= Pi [i ]) { break ; } }selectId = i ;// System.out.println("选中" + selectId); copyGh(k , selectId ); }}在被选集中，每个个体都有一个选择概率，这个概率由种群中个体的适应度及其分布决定。
若某个个体i ，其适应度为f i ，则其被选取的概率表示为：1Mi iii P f f==∑。
函数实现：计算种群中各个个体的累积概率，前提是已经计算出各个个体的适应度fitness[max]，作为赌轮选择策略一部分，Pi[max] void countRate() { int k ;double sumFitness = 0;// 适应度总和 double [] tempf = new double [scale ]; for (k = 0; k < scale ; k ++) { tempf [k ] = 10.0 / fitness [k ]; sumFitness += tempf [k ]; }Pi [0] = (float ) (tempf [0] / sumFitness ); for (k = 1; k < scale; k++) {Pi[k] = (float ) (tempf[k] / sumFitness + Pi[k - 1]); }}为了选择交叉个体，需要进行多轮选择，每一轮产生一个[0, 1]均匀随机数，将该随机数作为选择指针来确定被选个体。
4、设计遗传算法的交叉操作在选择操作的基础上，根据一定的概率（称为交叉概率）进行交叉操作。
交叉的目的是为了能够在下一代产生新的个体，它是遗传算法获取新的优良个体的最重要的手段。
交叉操作中，把两个父个体的部分结构进行替换重组，生成新个体。
根据个体编码方法的不同可以有不同的算法。
TSP问题中，交叉操作可设计如下：遗传算法交叉操作的函数实现：void OXCross(int k1, int k2) {int i, j, k, flag;int ran1, ran2, temp;int[] Gh1 = new int[cityNum];int[] Gh2 = new int[cityNum];ran1 = random.nextInt(65535) % cityNum;ran2 = random.nextInt(65535) % cityNum;while (ran1 == ran2) {ran2 = random.nextInt(65535) % cityNum;}if (ran1 > ran2) // 确保ran1<ran2{temp = ran1;ran1 = ran2;ran2 = temp;}flag = ran2 - ran1 + 1;// 删除重复基因前染色体长度for (i = 0, j = ran1; i < flag; i++, j++) {Gh1[i] = newPopulation[k2][j];Gh2[i] = newPopulation[k1][j];}// 已近赋值i=ran2-ran1个基因for (k = 0, j = flag; j < cityNum;) // 染色体长度{Gh1[j] = newPopulation[k1][k++];for (i = 0; i < flag; i++) {if (Gh1[i] == Gh1[j]) {break;}}if (i == flag) {j++;}}for (k = 0, j = flag; j < cityNum;)// 染色体长度{Gh2[j] = newPopulation[k2][k++];for (i = 0; i < flag; i++) {if (Gh2[i] == Gh2[j]) {break;}}if (i == flag) {j++;}}for (i = 0; i < cityNum; i++) {newPopulation[k1][i] = Gh1[i]; // 交叉完毕放回种群newPopulation[k2][i] = Gh2[i];}}遗传算法中并不是所有被选择的个体，都要进行交叉操作。
交叉概率用于控制交叉操作的频率。
概率太大时，种群中串的更新很快，使高适应度值的个体很快被破坏掉。
概率太小时，交叉操作很少进行，使搜索停滞不前。
5、设计遗传算法的变异操作同交叉操作一样，并不是所有被选择的个体，都要进行变异操作。
变异概率是加大种群多样性的重要因素，但是概率太小就很难产生新个体，概率太大会使GA成为随机搜索。
基于二进制编码的GA中，通常一个较低的变异率足以防止整个群体中任一位置的基因一直保持不变。
TSP问题中，变异操作可设计如下：利用上面实现的交叉操作，根据变异运算示意图，定义进化函数：public void Evolution() {int k;selectBestGh(); // 根据遗传算法的特点，挑选某代种群中适应度最高的个体select(); //挑选下一代的个体（赌轮选择策略）float r;// 交叉方法for (k = 0; k < scale; k = k + 2) {r = random.nextFloat();// /产生概率if (r < Pc) {OXCross1(k, k + 1);} else {r = random.nextFloat();// /产生概率// 变异if (r < Pm) {OnCVariation(k);}r = random.nextFloat();// /产生概率// 变异if (r < Pm) {OnCVariation(k + 1);}}}}6、编写基于遗传算法的TSP问题求解程序1) 采用遗传算法解决27城市TSP问题。
27个城市的坐标为：41 94；37 84；53 67；25 62；7 64；2 99；68 58；71 44；54 62；83 69；64 60；18 54；22 60；83 46；91 38；25 38；24 42；58 69；71 71；74 78；87 76；18 40；13 40；82 7；62 32；58 35；45 21。
这27个城市的坐标数据位于文件cityLocations.txt文件中，在程序中对其读取并进行处理.算法的关键函数及参数说明（Java）：算法的全部逻辑位于GATest.java文件中。
public GATest(int s, int n, int g, float c, float m) { //构造函数scale = s; //种群规模cityNum = n; //城市数量MAX_GEN = g; //繁衍代数Pc = c; //交叉概率Pm = m; //变异概率}程序的入口函数及初始参数：public static void main(String[] args) throws IOException {GATest gaTest = new GATest(50, 27, 3000, 0.8f, 0.9f);gaTest.init("C://Users/HaohaoChang/Desktop/data/cityLocations.txt"); //初始化数据gaTest.solve(); //执行算法}}算法运行结果：================================================================== 最佳长度出现所繁衍的代数：2788最佳长度：143最佳路径：11-22-21-16-15-26-25-24-23-14-13-7-6-10-8-2-17-18-9-20-19-0-1-5-4-12-3.Eclipse运行结果图（1）Eclipse运行结果图（2）2）利用实验数据，分析讨论以下问题。