智能信息处理实验报告

1、智能信息处理实验报告一、实验目的1) 掌握遗传算法的基本原理和程序流程。2) 理解TSP问题的基本概念。3) 能利用遗传算法求解TSP问题。二、实验环境与设备实验由1个学生独立完成，实验环境：笔记本电脑（Eclipse /Android Studio IDE）。三、预备知识1、TSP问题基本概念TSP问题即旅行商问题（Traveling Salesperson Problem）。该问题给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为：给定图G=(V, A)，其中V为顶点集，A为各顶点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条长度最短的H

2、amilton回路，即遍历所有顶点当且仅当一次的最短回路。2、遗传算法的基本原理遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有信息来指导搜索有希望改善优化质量的状态。标准遗传算法主要步骤可描述如下： 随机产生一组初始个体构成初始种群。 计算每一个体的适配值（fitness value，也称为适应度）。适应度值是对染色体(个体)进行评价的一种指标，是GA进行优化所用的主要信息，它与个体的目标值存在一种对应关系。 判断算法收敛准则是否满足，若满足，则输出搜索结果；否则执行以下步骤。 根据适应度值大小以一定方式执行复制操作（也称为

3、选择操作）。 按交叉概率pc执行交叉操作。 按变异概率pm执行变异操作。 返回步骤。标准遗传算法流程图下图所示。NN计算各个体的适配值（适应度）算法收敛准则满足？Yrandom0,1<Pc?复制（选择）输出搜索结果交叉Yrandom0,1<Pm?变异N随机产生初始种群Y图2.1 标准遗传算法流程图四、实验内容1、设计算法的编码方式路径编码是描述TSP解的最常用的一种策略。所谓路径编码，即直接采用城市在路径中的位置来构造用于优化的状态。例如：设九城市TSP问题的路径为5-4-1-7-9-8-6-2-3，对应的路径编码为：(5 4 1 7 9 8 6 2 3)。这种编码形式自然直观，易

4、于加入启发式信息，也有利于优化操作的设计。2、设计遗传算法的适应度函数对个体i，计算与路径编码相对应的距离，设为di。显然距离值di越大，适应度值应越小。因此，适应度函数可定义为：。这里我们在算法程序中个体适应度函数定义为：tempfk = 10.0 / fitnessk。3、设计遗传算法的选择操作选择是用来确定交叉个体，以及被选个体将产生多少个子代个体。它是基于适应度值计算基础上进行的。在实现算法的程序中，挑选种群中适应度最高的个体。挑选函数为selectBestGh()。挑选策略为赌轮选择策略。函数实现： public void select() int k, i, selectId; f

5、loat ran1; for (k = 1; k < scale; k+) ran1 = (float) (random.nextInt(65535) % 1000 / 1000.0); / 产生方式 for (i = 0; i < scale; i+) if (ran1 <= Pii) break; selectId = i; / System.out.println("选中" + selectId); copyGh(k, selectId); 在被选集中，每个个体都有一个选择概率，这个概率由种群中个体的适应度及其分布决定。若某个个体i，其适应度为fi，

6、则其被选取的概率表示为：。函数实现： 计算种群中各个个体的累积概率，前提是已经计算出各个个体的适应度fitnessmax，作为赌轮选择策略一部分，Pimax void countRate() int k; double sumFitness = 0;/ 适应度总和 double tempf = new doublescale; for (k = 0; k < scale; k+) tempfk = 10.0 / fitnessk; sumFitness += tempfk; Pi0 = (float) (tempf0 / sumFitness); for (k = 1; k < s

7、cale; k+) Pik = (float) (tempfk / sumFitness + Pik - 1); 为了选择交叉个体，需要进行多轮选择，每一轮产生一个0, 1均匀随机数，将该随机数作为选择指针来确定被选个体。4、设计遗传算法的交叉操作在选择操作的基础上，根据一定的概率（称为交叉概率）进行交叉操作。交叉的目的是为了能够在下一代产生新的个体，它是遗传算法获取新的优良个体的最重要的手段。交叉操作中，把两个父个体的部分结构进行替换重组，生成新个体。根据个体编码方法的不同可以有不同的算法。TSP问题中，交叉操作可设计如下：遗传算法交叉操作的函数实现： void OXCross(int k1

8、, int k2) int i, j, k, flag; int ran1, ran2, temp; int Gh1 = new intcityNum; int Gh2 = new intcityNum; 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 =

9、ran2; ran2 = temp; flag = ran2 - ran1 + 1;/ 删除重复基因前染色体长度 for (i = 0, j = ran1; i < flag; i+, j+) Gh1i = newPopulationk2j; Gh2i = newPopulationk1j; / 已近赋值i=ran2-ran1个基因 for (k = 0, j = flag; j < cityNum;) / 染色体长度 Gh1j = newPopulationk1k+; for (i = 0; i < flag; i+) if (Gh1i = Gh1j) break; if

10、(i = flag) j+; for (k = 0, j = flag; j < cityNum;)/ 染色体长度 Gh2j = newPopulationk2k+; for (i = 0; i < flag; i+) if (Gh2i = Gh2j) break; if (i = flag) j+; for (i = 0; i < cityNum; i+) newPopulationk1i = Gh1i; / 交叉完毕放回种群 newPopulationk2i = Gh2i; 遗传算法中并不是所有被选择的个体，都要进行交叉操作。交叉概率用于控制交叉操作的频率。概率太大时，种

11、群中串的更新很快，使高适应度值的个体很快被破坏掉。概率太小时，交叉操作很少进行，使搜索停滞不前。5、设计遗传算法的变异操作同交叉操作一样，并不是所有被选择的个体，都要进行变异操作。变异概率是加大种群多样性的重要因素，但是概率太小就很难产生新个体，概率太大会使GA成为随机搜索。基于二进制编码的GA中，通常一个较低的变异率足以防止整个群体中任一位置的基因一直保持不变。TSP问题中，变异操作可设计如下：利用上面实现的交叉操作，根据变异运算示意图，定义进化函数： public void Evolution() int k; selectBestGh(); / 根据遗传算法的特点，挑选某代种群中适应度最

12、高的个体 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、编

13、写基于遗传算法的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文件中。

14、 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/HaohaoC

15、hang/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）利用实验数据，分析讨论以下问题。a) 在其他条件不变的情况下，只改变变异概率的取值，对求解结果有何影响？实验次数：10种群规模：27交叉概率：0.8试验结果：变异概率最佳长度最佳路径0.0010.010.10.30.40.50.60.70.90.95b) 在其他条件不变的情况下，只改变交叉概率的取值，对求解结果有何影响？c) 在其他条件不变的情况下，只改变种群规模的取值，对求解结果有何影响？d) 在其他条件不变的情况下，采用不同的算法终止