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