遗传算法求解TSP问题

人工智能实验求解TSP问题的实验6遗传算法一、实验目的熟悉和掌握w遗传算法的原理、过程和编码策略，了解利用遗传解决方案功能优化问题和解决TSP问题的过程，并测试关键参数对结果的影响。二、实验内容1、参考实验系统提供的遗传算法核心代码、利用遗传算法解决TSP的优化问题，分析遗传算法解决不同规模TSP问题的算法性能。2、针对相同的TSP问题，分析群体规模、交叉概率和变异概率对算法结果的影响。3、增加一个变分策略和一个单独选择概率分配策略，比较解决同一TSP问题时不同变分策略和不同单独选择分配策略对算法结果的影响。4、提交源代码。三、遗传算法流程图解决TSP问题四、遗传算法解决不同规模TSP问题的算法性能(1)解释如何运行遗传算法：l适应性值计算方法：当前路线的路径长度l个体选择概率分布方法：适宜性比例法l选择单独的方法：选择轮盘l交集类型：PMX交集l变分类型：两点交换变分(2)实验模拟结果：城市数量时间(毫秒)51692510166301518833202259625241593030289353523940386084540032504375755477466058143655994270643617571417图1-1(3)分析如图1-1所示，TSP问题规模越大，遗传算法运行时间越长，大致呈线性增长。五、比较不同参数计算结果(1)人口规模对算法结果的影响实验次数：10最大重复步骤3336100相交概率：0.85转移概率：0.15表1-1人口规模自适应值最佳路径1025.2644-5-8-7-6-3-1-0-9-22026.34282-9-1-0-3-6-7-5-8-43025.16521-3-6-7-5-8-4-2-9-05025.16520-1-3-6-7-5-8-4-2-98025.16529-0-1-3-6-7-5-8-4-210025.16521-0-9-2-4-8-5-7-6-315025.16525-8-4-2-9-0-1-3-6-720025.16521-3-6-7-5-8-4-2-9-025025.16523-1-0-9-2-4-8-5-7-630025.16525-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人口规模为10，20时，没有发现最佳解决方案。(2)交叉概率对算法结果的影响实验次数：15人口大小：25最大重复步骤3336100转移概率：0.15实验结果：表1-2交叉概率最佳适应能力最差的适应能力平均适应能力最佳解决方案执行时间0.00128.044736.656732.60029-2-6-0-5-4-8-7-3-13100.0127.093534.994332.14957-8-3-1-9-2-6-0-5-42600.128.044735.303331.93727-3-1-9-2-6-0-5-4-83000.1528.044734.117531.21830-5-4-8-7-3-1-9-2-62700.228.710833.951230.90353-1-9-2-6-5-0-4-7-82800.2528.044735.162330.74561-3-7-8-4-5-0-6-2-92600.327.093531.994129.94288-3-1-9-2-6-0-5-4-72900.3527.093532.808530.99459-1-3-8-7-4-5-0-6-22700.427.093532.531330.15341-3-8-7-4-5-0-6-2-92790.4527.093533.201430.17578-3-1-9-2-6-0-5-4-74560.528.093433.630730.90265-0-2-6-9-1-3-8-7-46630.5527.093533.523329.13041-9-2-6-0-5-4-7-8-35200.627.093533.251230.78363-1-9-2-6-0-5-4-7-85460.6528.044733.700330.93715-4-8-7-3-1-9-2-6-05960.727.093532.092729.95029-1-3-8-7-4-5-0-6-25710.7528.044732.448830.36990-5-4-8-7-3-1-9-2-65590.827.093532.155129.93827-4-5-0-6-2-9-1-3-83580.8527.093534.539930.35945-0-6-2-9-1-3-8-7-43600.927.093532.627330.696-0-5-4-7-8-3-1-9-23750.9527.093532.467229.9196-2-9-1-3-8-7-4-5-0476(注意：红色表示非最佳解决方案)在这种情况下，如果相交概率太低，搜索可能会变慢，无法获得最佳解决方案。(3)变异概率对算法结果的影响实验次数：10人口大小：25最大重复步骤3336100相交概率：0.85实验结果：表1-3变异概率最佳适应能力最差的适应能力平均适应能力最佳解决方案执行时间0.00129.471734.73232.49110-6-2-1-9-3-8-7-4-52450.0129.044634.659132.37148-4-5-0-2-6-9-1-3-72740.128.093434.01130.94175-0-2-6-9-1-3-8-7-42500.1527.093532.09330.25686-0-5-4-7-8-3-1-9-22460.227.093532.234930.31448-7-4-5-0-6-2-9-1-32820.2527.093532.71830.15724-5-0-6-2-9-1-3-8-72450.327.093532.448830.28540-5-4-7-8-3-1-9-2-62520.3527.093533.316730.77481-3-8-7-4-5-0-6-2-92660.429.044634.370531.30412-0-5-4-8-7-3-1-9-63620.4527.093531.37429.68162-6-0-5-4-7-8-3-1-94380.527.093532.375230.21122-9-1-3-8-7-4-5-0-64310.5527.093533.381930.66231-3-8-7-4-5-0-6-2-94920.628.093433.251230.361-3-8-7-4-5-0-2-6-94170.6527.093532.749130.02013-1-9-2-6-0-5-4-7-84340.728.710832.423830.7851-3-8-7-4-0-5-6-2-94320.7527.093531.892830.24511-9-2-6-0-5-4-7-8-34750.828.093431.613530.34719-1-3-8-7-4-5-0-2-63270.8529.66233.239231.15852-9-1-3-7-8-4-0-5-63140.928.044732.038730.41520-5-4-8-7-3-1-9-2-63960.9528.044731.303630.00679-1-3-7-8-4-5-0-6-2436此外，表1-3表明，如果波动概率太大或太低，则无法获得最佳解决方案。注：(2)(3)的实验数据与(1)的实验数据不同，附录详细介绍。六、不同变异策略和个体选择概率分布策略对算法结果的影响(1)两点交换变异与插入变异的比较：l尝试次数(casnum): 10l城市数(POINTCNT):10l人口规模(POPSIZE):100l最大重复步骤3360100l相交概率(PC): 0.85l变化概率(PM):0.15l选择单独的方法：选择轮盘l交集类型：PMX交集l个体选择概率分布方法：适宜性比例法A.变异类型：两点交换变异表1-4两点交换变异程序结果序号最佳适应能力最差的适应能力平均适应能力最佳解决方案执行时间128.093430.422929.08916-2-0-5-4-7-8-3-1-91199227.093531.141728.98414-5-0-6-2-9-1-3-8-71678327.093530.422829.06040-5-4-7-8-3-1-9-2-61940427.093530.370328.87871-3-8-7-4-5-0-6-2-91756527.093531.061929.07553-1-9-2-6-0-5-4-7-81885627.093531.158929.39422-6-0-5-4-7-8-3-1-91936728.044731.061929.76486-2-9-1-3-7-8-4-5-01772829.044631.347529.84154-5-0-2-6-9-1-3-7-81980927.093530.614329.0590-6-2-9-1-3-8-7-4-519401027.093530.558529.08119-2-6-0-5-4-7-8-3-118721127.093531.017129.42640-5-4-7-8-3-1-9-2-615171227.093531.303629.24141-9-2-6-0-5-4-7-8-315411327.093532.025529.07890-6-2-9-1-3-8-7-4-515171427.093531.51628.89060-6-2-9-1-3-8-7-4-513451527.093530.422829.02266-0-5-4-7-8-3-1-9-213771627.093530.408128.90810-6-2-9-1-3-8-7-4-518531727.093530.408129.33167-8-3-1-9-2-6-0-5-415221827.093530.020328.52431-3-8-7-4-5-0-6-2-916011928.044731.140429.5672-9-1-3-7-8-4-5-0-616092027.093531.141729.53597-4-5-0-6-2-9-1-3-81311平均值27.336130.878229.18771657B.插入过渡类型：过渡表1-5插入转换程序结果序号最佳适应能力最差的适应能力平均适应能力最佳解决方案执行时间127.093531.475328.84532-6-0-5-4-7-8-3-1-91388227.093529.66228.91685-0-6-2-9-1-3-8-7-41355327.093529.663128.9021-9-2-6-0-5-4-7-8-31637428.044730.52