实验六 遗传算法实验II
实验目:
熟悉掌握遗传算法原理流程编码策略利遗传求解函数优化问题理解求解TSP问题流程测试参数结果影响
二实验原理:
旅行商问题TSP问题(Traveling Salesman Problem)数学领域中著名问题假设旅行商拜访n城市必须选择走路径路限制城市拜访次回原出发城市路径选择目标求路径路程路径中值TSP问题组合优化问题该问题证明具NPC计算复杂性该问题求解简化方法受高度评价关注
遗传算法基思想正基模仿生物界遗传学遗传程问题参数基代表问题解染色体代表(计算机里二进制码表示)具染色体体组成群体群体问题特定环境里生存竞争适者机会生存产生代代机化继承父代特征生存环境控制支配继续程群体染色体逐渐适应环境断进化收敛族适应环境类似体问题优解求利遗传算法求解TSP问题短路径
三实验容:
1参考实验系统出遗传算法核心代码遗传算法求解TSP优化问题分析遗传算法求解规模TSP问题算法性
2TSP问题分析种群规模交叉概率变异概率算法结果影响
3增加1种变异策略1种体选择概率分配策略较求解TSP问题时变异策略体选择分配策略算法结果影响
4交源代码
四实验报告求:
1画出遗传算法求解TSP问题流程图
2 分析遗传算法求解规模TSP问题算法性
规模越算法性越差时间越长
3TSP问题分析种群规模交叉概率变异概率算法结果影响
(1) 种群规模算法结果影响
x
0
11
35
3
7
8
4
45
9
2
y
11
3
2
4
51
8
4
45
9
2
实验次数:10
迭代步数100
交叉概率:085
变异概率:015
种群规模
均适应度值
优路径
10
25264
4587631092
20
263428
2910367584
30
251652
1367584290
50
251652
0136758429
80
251652
9013675842
100
251652
1092485763
150
251652
5842901367
200
251652
1367584290
250
251652
3109248576
300
251652
5842901367
表示显然短路径251652m优路径109136758423109248576注意圈时针者逆时针种群规模1020时没找优解种群规模越越
(2) 交叉概率算法结果影响
x
9
11
35
35
7
8
4
45
3
2
y
11
3
1
4
51
3
1
85
9
1
实验次数:15
种群规模:25
迭代步数100
变异概率:015
实验结果:
交叉概率
适应度
差适应度
均适应度
优解
0001
280447
366567
326002
9260548731
001
270935
349943
321495
7831926054
01
280447
353033
319372
7319260548
015
280447
341175
312183
0548731926
02
287108
339512
309035
3192650478
025
280447
351623
307456
1378450629
03
270935
319941
299428
8319260547
035
270935
328085
309945
9138745062
04
270935
325313
301534
1387450629
045
270935
332014
301757
8319260547
05
280934
336307
309026
5026913874
055
270935
335233
291304
1926054783
06
270935
332512
307836
3192605478
065
280447
337003
309371
5487319260
07
270935
320927
299502
9138745062
075
280447
324488
303699
0548731926
08
270935
321551
299382
7450629138
085
270935
345399
303594
5062913874
09
270935
326273
3069
6054783192
095
270935
324672
29919
6291387450
(注红色表示非优解)
该情况交叉概率低搜索陷入迟钝状态优解
(3) 变异概率算法结果影响
x
9
11
35
35
7
8
4
45
3
2
y
11
3
1
4
51
3
1
85
9
1
实验次数:10
种群规模:25
迭代步数100
交叉概率:085
实验结果:
变异概率
适应度
差适应度
均适应度
优解
0001
294717
34732
324911
0621938745
001
290446
346591
323714
8450269137
01
280934
34011
309417
5026913874
015
270935
32093
302568
6054783192
02
270935
322349
303144
8745062913
025
270935
32718
301572
4506291387
03
270935
324488
302854
0547831926
035
270935
333167
307748
1387450629
04
290446
343705
313041
2054873196
045
270935
31374
296816
2605478319
05
270935
323752
302211
2913874506
055
270935
333819
306623
1387450629
06
280934
332512
3036
1387450269
065
270935
327491
300201
3192605478
07
287108
324238
30785
1387405629
075
270935
318928
302451
1926054783
08
280934
316135
303471
9138745026
085
29662
332392
311585
2913784056
09
280447
320387
304152
0548731926
095
280447
313036
300067
9137845062
该表知变异概率低导致法优解
4增加1种变异策略1种体选择概率分配策略较求解TSP问题时变异策略体选择分配策略算法结果影响
变异策略体选择分配策略影响算法运行时间会影响适应度
五实验心体会
通实验更加深入体会参数设置算法结果影响算法参数值获结果会完全
时通次实验遗传算法更进步解遗传算法种智优化算法较似求解TSP问题问题规模较时候遗传算法优势明显体现出然完全保证优解
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
该内容是文档的文本内容,更好的格式请下载文档