《智能信息处理实验报告（精编版）》由会员分享，可在线阅读，更多相关《智能信息处理实验报告（精编版）（9页珍藏版）》请在金锄头文库上搜索。
1、智能信息处理实验报告一、实验目的1) 掌握遗传算法的基本原理和程序流程。2) 理解 TSP 问题的基本概念。3) 能利用遗传算法求解TSP 问题。二、实验环境与设备实验由 1 个学生独立完成，实验环境：笔记本电脑（Eclipse /Android Studio IDE）。三、预备知识1、TSP 问题基本概念TSP 问题即旅行商问题（Traveling Salesperson Problem ）。该问题给定n 个城市和两两城市之间的距离， 要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为： 给定图G=(V, A) ，其中 V 为顶点集， A 为各顶点相互连接组成的边集，已知各顶点间的连
2、接距离，要求确定一条长度最短的Hamilton 回路，即遍历所有顶点当且仅当一次的最短回路。2、遗传算法的基本原理遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有信息来指导搜索有希望改善优化质量的状态。标准遗传算法主要步骤可描述如下：随机产生一组初始个体构成初始种群。计算每一个体的适配值（ fitness value ，也称为适应度） 。适应度值是对染色体(个体 ) 进行评价的一种指标，是 GA 进行优化所用的主要信息，它与个体的目标值存在一 种对应关系。判断算法收敛准则是否满足，若满足，则输出搜索结果；否则执行以下步骤。根据
3、适应度值大小以一定方式执行复制操作（也称为选择操作）。按交叉概率pc 执行交叉操作。按变异概率pm 执行变异操作。返回步骤。标准遗传算法流程图下图所示。随机产生初始种群计算各个体的适配值（适应度）算法收敛准则满足？NY输出搜索结果复制（选择）Nrandom0,1 Pc?Y交叉Nrandom0,1 Pm?Y变异图 2.1 标准遗传算法流程图四、实验内容1、设计算法的编码方式路径编码是描述TSP 解的最常用的一种策略。所谓路径编码，即直接采用城市在路径中的位置来构造用于优化的状态。例如：设九城市TSP 问题的路径为5-4-1-7-9-8-6-2 -3， 对应的路径编码为：(5 4 1 7 9 8
4、6 2 3) 。这种编码形式自然直观，易于加入启发式信息，也有利于优化操作的设计。2、设计遗传算法的适应度函数对个体 i ，计算与路径编码相对应的距离，设为di。显然距离值di 越大，适应度值应越小。因此，适应度函数可定义为：Fit1。这里我们在算法程序中个体适应度函数定义di为： tempfk = 10.0 / fitnessk 。3、设计遗传算法的选择操作选择是用来确定交叉个体，以及被选个体将产生多少个子代个体。它是基于适应度值计算基础上进行的。在实现算法的程序中，挑选种群中适应度最高的个体。挑选函数为selectBestGh()。挑选策略为赌轮选择策略。函数实现：public void
5、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，其适应
6、度为fi ，则其被选取的概率表示为：MPifif i 。i 1函数实现：计算种群中各个个体的累积概率，前提是已经计算出各个个体的适应度fitnessmax ，作为赌轮选择策略一部分，Pimaxvoid countRate() int k;double sumFitness = 0; / 适应度总和double tempf = new double scale; for (k = 0; k scale; k+) tempf k = 10.0 / fitness k; sumFitness += tempfk;Pi0 = ( float ) (tempf 0 / sumFitness); for
7、(k = 1; k ran2)/ 确保 ran1ran2temp = 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 =
8、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;遗传算法中并不是所
9、有被选择的个体，都要进行交叉操作。交叉概率用于控制交叉操作 的频率。概率太大时，种群中串的更新很快，使高适应度值的个体很快被破坏掉。概率太小时，交叉操作很少进行，使搜索停滞不前。5、设计遗传算法的变异操作同交叉操作一样，并不是所有被选择的个体，都要进行变异操作。变异概率是加大种群 多样性的重要因素，但是概率太小就很难产生新个体，概率太大会使GA 成为随机搜索。 基于二进制编码的GA 中，通常一个较低的变异率足以防止整个群体中任一位置的基因一直保持不变。TSP 问题中，变异操作可设计如下：利用上面实现的交叉操作，根据变异运算示意图，定义进化函数：publicvoid Evolution() in
10、t 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) OnCV
11、ariation( 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； 1840； 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(Stringargs) throws IOException GATest gaTest = new GATest(50, 27, 3000, 0.8f
