本科毕业设计说明书（论文）
的结果对比。
第 22 页 共 32 页
最优，但是种群过大会减慢程序的运算速度，导致算法效率的低下。下面是2个模块
本文采用网络上已有的城市距离矩阵来验证所写程序的正确性: int length[10][10]=
{
0, 23, 93, 18, 40, 34, 13, 75, 50, 35,
23, 0, 75, 4, 72, 74, 36, 57, 36, 22, 93, 75, 0, 64, 21, 73, 51, 25, 74, 89, 18, 4, 64, 0, 55, 52, 8, 10, 67, 1, 40, 72, 21, 55, 0, 43, 64, 6, 99, 74, 34, 74, 73, 52, 43, 0, 43, 66, 52, 39, 13, 36, 51, 8, 64, 43, 0, 16, 57, 94, 75, 57, 25, 10, 6, 66, 16 , 0, 23, 11, 50, 36, 74, 67, 99, 52, 57 ,23, 0, 42, 35, 22, 89, 1, 74, 39, 94 ,11 ,42, 0,
};
其最优距离已被求解为226
下表为交叉率Pc=0.9，变异率 Pm=0.01,初始种群分别为10,100，最大遗传代数分别为100,200的实验结果对比：
表3.1 不同初始种群的算法结果对比表
次数 遗传代数 初始种群大 小 100 最优解代数 1 10 100 2 10 100 3 10 100 4 10 40 11 60 24 71 94 27 最优解路径 最优解 6318247950 246 7810639542 232 4278931065 238 6058139742 229 2781395604 245 7819360542 226 6247931850 229 200 最优解代数 100 131 193 50 74 30 102 最优解路径 最优解 9310654278 238 5063918724 226 8193605427 226 3918724506 226 2601395874 233 0542781936 226 5427601398 240 本科毕业设计说明书（论文）
100 5 10 100 6 10 100 7 10 100 8 10 100 9 10 100 10 10 100 11 10 100 12 10 100 13 10 100 14 10 100 15 10 100 91 55 54 14 35 43 80 90 30 40 30 50 18 25 62 80 25 18 34 30 100 50 87 1936054278 226 6319587240 247 4506391872 226 7936018542 233 4260581397 229 4793185062 229 4278913605 235 3105897426 252 3954278106 232 4581930672 247 0593187426 228 0639187245 226 6059318742 228 3972458106 233 5813906724 229 6058139742 229 4781395062 228 8593106247 233 9360542781 226 2450631987 235 7245063198 235 247601395 249 124 94 161 95 57 100 78 193 75 129 78 171 77 123 140 119 50 50 67 150 100 100 100 第 23 页 共 32 页 5063918724 226 6013958742 233 9360542781 226 6013958742 233 2450639187 226 4793185062 229 9360187245 232 2450639187 226 9360542781 226 7931850624 229 8724593601 232 0624781395 228 1872450639 226 4260593187 228 5063918724 226 2458931067 240 5813974260 229 3958742601 233 7813950624 228 7931850624 229 8106395427 232 2479318506 229 3918724506 226 5936018724 232 初始种群为10，遗传代数为100的平均最优解为:
(246+238+245+229+247+233+229+252+247+226+233+229+233+235+249)/15=238.1 初始种群为10，遗传代数为200的平均最优解为:
(238+226+233+240+233+233+229+226+229+228+228+240+233+229+229)/10=231.6 初始种群为100，遗传代数为100的平均最优解:
(232+229+226+226+226+229+235+232+228+228+229+228+226+235+232)/10=229.4 初始种群为100，遗传代数为200的平均最优解:
本科毕业设计说明书（论文）
第 24 页 共 32 页
(226+226+226+226+226+226+232+226+232+226+226+229+228+232+226)/10=227.5
以上结果非常显然的表示出了当初始种群个数增加后，获得的平均解更接近全局最优解。但增加初始种群的同时增加的算法的循环次数，从而降低了算法的效率。10个城市的TSP问题初始种群应取50-200为宜。
在上述结果中，选取初始种群为10，遗传代数为100的个体（除去获得全局最优解的个体）。然后计算获得最优解的代数的平均值：
(40+60+71+27+55+14+43+90+40+25+80+18+30+50)/14=45.9
计算结果表现出了：算法在没有获得全局最优解的前提下过早的确定了解。原因：初始种群个数过少。导致陷入局部最优解。理论上可以通过改变交叉率和变异率来改善。
3.2.2 不同交叉率和变异率的对比
（1）下面是初始种群为10的模块。相同的交叉率、不同的变异率来观察两组计算的对比结果。
下面列出的运算次数为那些到达遗传代数后，依旧没有找到最优解，但是过早获得局部最优解得次数 。
表3.2 相同交叉率、不同变异率的算法结果对比表
条件 遗传代数 运算次数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Pc=0.9 Pm=0.001 300 最优解代数 30 108 147 83 66 270 98 163 144 117 70 55 69 140 88 500 Pc=0.9 Pm=0.1 300 最优解 最优解代数 229 232 229 238 228 232 228 228 232 229 228 228 233 232 228 233 241 181 152 218 196 200 278 258 197 273 264 170 150 154 500 最优解 最优解代数 240 244 235 232 240 232 248 232 238 232 238 232 257 233 240 317 290 365 212 301 350 242 276 295 313 189 348 250 200 290 最优解 249 233 233 228 232 241 233 229 232 232 233 232 232 229 233 最优解 最优解代数 246 229 241 233 238 228 233 240 228 233 228 228 229 228 240 63 76 311 82 37 450 198 256 87 79 200 160 122 99 120 本科毕业设计说明书（论文）
状态1 Pc=0.9 Pm=0.001
初始种群300 平均最优解代数为109.9 初始种群500 平均最优解代数156 状态2 Pc=0.9 Pm=0.1
初始种群 300 平均最优解代数为211 初始种群 500 平均最优解代数为282.5
第 25 页 共 32 页
从上述结果可观察到。在众多计算结果中，未得到全局最优解得计算中，状态1比起状态2来，过早收敛。
状态2往往可以通过增加种群大小来得到最优解。但是状态1则很难通过增加种群个体来突破局部收敛的限制。
（2）接下来分别选择交叉率为0.3和0.9、变异率为0.1、初始种群为10、来作为运行参数。运算结果中当交叉率从0.9变为0.3时，在获取最优解的同时，遗传代数也随之大大增加。
从此可以看出，交叉是产生新个体的主要方式，交叉率过小会导致产生新个体过慢，而导致收敛速度降低。但是也不能取太大。太大可能会破坏群体中的优秀个体。
以上几个对比，进一步证明了以下几个结论：
(1) 初始种群的大小决定了种群的多样性。种群个体过少会导致算法过早收敛，从而陷入局部最优解，难以获得全局最优解。但是种群过大导致了一次遗传操作要进行的循环过多，大大加大了机器开销，算法效率低下。一般的10个点城市，初始种群取50到100为好。
（2）变异率取值过小，就会导致算法容易陷入局部收敛。从而降低了其抑制早熟的能力。但也不能过大，否则会破坏群体中的优秀个体，导致算法效率低下，甚至有时可能找不到最优值。在本算法中变异率因取0.01到0.1为宜。
（3）交叉概率过小会导致产生新个体的速度变慢，而导致收敛速度降低。但也不能过大，过大可能会破坏种群中的优秀个体。本算法中交叉率取0.7到0.9为宜。
3.3 程序计算过程截图
程序主模块：供用户选择初始种群的两种大小：10和100。
本科毕业设计说明书（论文）
第 26 页 共 32 页
图3.2程序主界面图
初始种群为10的模块。遗传代数为200，交叉率为0.9、变异率为0.01的运行图。
图3.2 初始种群为10的算法运行图
初始种群为10的模块。遗传代数为200、交叉率为0.9、变异率为0.01结果图。
图3.3 初始种群为10的算法运行结果图