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

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