解最短路径的遗传算法如下： n

Evaluate[p(h)];表示计算每个个体适应度，h是种群中的一个个体 Repeat roof Generations times;重复下面的操作，直到满足条件为止 Select p(h) from p(n-1);表示从前一代群体中选择一对双亲，用于交叉、变异 操作，P(n)代表第n代群体

Crossover and mutation p(n);进行交叉和变异操作 Learning[p(n)];自学习过程

Evaluate[p(h)];计算新生成的种群中每个个体的适应度 End;

具体流程图如下所示：

Generate[p(n)];表示程序开始时要首先产生一个群体，群体个数为

流程图

5.遗传算法求解不同规模的TSP问题的算法性能

（1） 遗传算法执行方式说明：

? 适应度值计算方法：当前路线的路径长度 ? 个体选择概率分配方法：适应度比例方法 ? 选择个体方法：轮盘赌选择 ? 交叉类型：PMX交叉 ? 变异类型: 两点互换变异 （2）实验模拟结果：

城市个数 时间（ms） 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 16925 16630 18833 22596 24159 30289 35239 38608 40032 43757 47746 58143 59942 64361 71417

图1-1

（3）分析

由图1-1可知，遗传算法执行时间随着TSP问题规模的增大而增

大，并且大致为线性增长。 五、不同参数下的计算结果对比 （1）种群规模对算法结果的影响 实验次数：10 最大迭代步数:100 交叉概率：0.85 变异概率：0.15

表1-1

种群规模 10 20 适应度值 25.264 26.3428 最优路径 4-5-8-7-6-3-1-0-9-2 2-9-1-0-3-6-7-5-8-4 30 50 80 100 150 200 250 300 25.1652 25.1652 25.1652 25.1652 25.1652 25.1652 25.1652 25.1652 1-3-6-7-5-8-4-2-9-0 0-1-3-6-7-5-8-4-2-9 9-0-1-3-6-7-5-8-4-2 1-0-9-2-4-8-5-7-6-3 5-8-4-2-9-0-1-3-6-7 1-3-6-7-5-8-4-2-9-0 3-1-0-9-2-4-8-5-7-6 5-8-4-2-9-0-1-3-6-7 如表1-1所示，显然最短路径为25.1652m,最优路径为1-0-9-1-3-6-7-5-8-4-2或3-1-0-9-2-4-8-5-7-6，注意到这是一圈，顺时针或者逆时针都可以。当种群规模为10，20时，并没有找到最优解。

（2）交叉概率对算法结果的影响 实验次数：15 种群规模：25 最大迭代步数:100 变异概率：0.15 实验结果：

表1-2

交叉概率 最好适应度 最差适应度 平均适应度 最优解 9-2-6-0-5-4-8-0.001 28.0447 36.6567 32.6002 7-3-1 310 运行时间 7-8-3-1-9-2-6-0.01 27.0935 34.9943 32.1495 0-5-4 7-3-1-9-2-6-0-0.1 28.0447 35.3033 31.9372 5-4-8 0-5-4-8-7-3-1-0.15 28.0447 34.1175 31.2183 9-2-6 3-1-9-2-6-5-0-0.2 28.7108 33.9512 30.9035 4-7-8 1-3-7-8-4-5-0-0.25 28.0447 35.1623 30.7456 6-2-9 8-3-1-9-2-6-0-0.3 27.0935 31.9941 29.9428 5-4-7 9-1-3-8-7-4-5-0.35 27.0935 32.8085 30.9945 0-6-2 1-3-8-7-4-5-0-0.4 27.0935 32.5313 30.1534 6-2-9 8-3-1-9-2-6-0-0.45 27.0935 33.2014 30.1757 5-4-7 5-0-2-6-9-1-3-0.5 28.0934 33.6307 30.9026 8-7-4 1-9-2-6-0-5-4-0.55 0.6 27.0935 27.0935 33.5233 33.2512 29.1304 7-8-3 520 546 663 456 279 270 290 260 280 270 300 260 30.7836 3-1-9-2-6-0-5-