遗传算法解决10城市TSP问题方案设计.docVIP

应用遗传算法解决10城市TSP问题 的方案设计 姓 名： 学 号： 2010-12-27 一、问题描述 ××计划近期在北京、天津、武汉、深圳、长沙、成都、杭州、西安、拉萨、南昌10个城市间进行一次自驾周游旅行，为了尽量节省旅行开支，××希望能通过某种方法，找到一条使自驾选择路线里程数最少或相对较少的旅行路线。 对于以上问题，若给定已知10个城市之间的公路里程如表1所示，并要求应用遗传算法编程实现求解，该如何处理？ 表1 城市间公路里程表（单位：km） 北京 天津 武汉 深圳 长沙 成都 杭州 西安 拉萨 南昌 北京 0 118 1272 2567 1653 2097 1425 1177 3947 1574 天津 118 0 1253 2511 1633 2077 1369 1157 3961 1518 武汉 1272 1253 0 1462 380 1490 821 856 3660 385 深圳 2567 2511 1462 0 922 2335 1562 2165 3995 993 长沙 1653 1633 380 922 0 1700 1041 1135 3870 456 成都 2097 2077 1490 2335 1700 0 2311 920 2170 1920 杭州 1425 1369 821 1562 1041 2311 0 1420 4290 626 西安 1177 1157 856 2165 1135 920 1420 0 2870 1290 拉萨 3947 3961 3660 3995 3870 2170 4290 2870 0 4090 南昌 1574 1518 385 993 456 1920 626 1290 4090 0 二、算法设计 根据任务要求，本文采用遗传算法实现编程求解。在具体求解之前，还需确定以下几点：编码方法，种群规模，选择算子，交叉概率和变异概率。 ①编码方法 常用的遗传算法编码方法有：二进制编码、Gray编码、实数编码、有序串编码等。采用二进制编码在求解中容易导致Hamming悬崖，并且要求给出求解精度以确定位串长度；Gray编码虽然能较好地克服Hamming悬崖，但在进行交叉变异时，交叉和变异位的选择也会使得问题复杂。 综合分析，本文中选择实数编码方法，分别用数字0—9表示北京、天津、武汉、深圳、长沙、成都、杭州、西安、拉萨、南昌10个城市。 图1 代价数组 这样，城市间的距离信息就可以用如图1所示二维数组表示：即对于编号分别为a、b的两个城市，它们之间的距离在代价数组中表示为元素Cost_table[a][b]的值。 ②种群规模 遗传算法中，初始种群的生成、选择、交叉以及变异都是随机进行的，因此，对于同一个问题，种群规模的大小将直接影响到算法的进化速度。这是因为，当种群规模较大时，在每一代中通过交叉、变异产生以往没有出现过的个体的概率会大大增加，这样也会使得在下一代中出现靠近最优解个体的概率增加，再通过合适的选择算法，就能达到加快进化的目的。 本文中选择种群规模为100。 ③选择算子 最常用的选择算子是“轮盘赌”法，其次还有“确定性”法和最佳个体保存方法。 若采用“轮盘赌”法，则需要计算每个个体被选中的概率，考虑到本文中种群规模取为100，因此平均每个个体被选中的概率相对较小，实际进行“轮盘赌”效果不一定会很好，本文中不选该方法。而“确定性”法在实际编程中发现实现起来比较复杂。 综合考虑，本文选择最佳个体保存法的一种变异方法。即预先定义进行选择时种群中优秀个体的保存比例（本文中），然后在每次进行选择前将种群中的个体按代价值从小到大排序，然后删除种群中排序在后40%的个体，用排序在前40%的优秀个体替代。这样，每一轮选择后种群中存大的都是相对优秀的个体。 ④交叉概率和变异概率 由于本文采用的是最佳个体保存法的变异方法，从“③选择算子”的分析可以看出，该方法在选择时总是将排序靠后的个体直接删除，这样必然会导致种群多样性受到损失，导致种群进化有向纯种发展的趋势。 因此，本文中交叉概率取得稍大为90%，目的是想通过交叉弥补因为选择而损失的个体多样性。需要注意的是，在实际交叉时，为了避免因为交叉而导致排序靠前、相对优秀的个体因为交叉而偏离最优解，交叉只发生在种群中按代价排序后的后90%。 遗传算法中，变异的主要作用是防止种群早熟，也即陷入局部最优。因此，与上面分析的原因类似，本文中的变异概率在种群进化的前100代取10%，在种群进化的后100代，为了更多地补充种群个体的多样性，变异概率取50%。 三、运行结果分析 多次重复运行编写好的程序可以发现，对于本文中给出的城市间公路里程信息，近似最优解的路线累计里程数为12055km，解路径不唯一。从运行结果上看