数学建模B题走遍全中国(共17页)

《数学建模B题走遍全中国(共17页)》由会员分享，可在线阅读，更多相关《数学建模B题走遍全中国(共17页)（17页珍藏版）》请在装配图网上搜索。

1、精选优质文档-倾情为你奉上B题：走遍全中国摘要走遍全中国问题是一个旅行商问题，我们通过借助多种数学软件的优势挖掘出大量数据潜在的信息，并将其合理运用，建立模型，使用蚁群算法等来解决问题。本文主要解决旅行商问题，应用蚁群算法，通过MATLAB 编写程序，最终计算出浙江旅行商最短路径。最后画出最短路线图，以直观方式展现在读者面前。旅行商问题(TSP)是一种典型的组合最优化问题，可描述为某旅行商欲往n 个城市推销货物，从某个城市出发，沿途经过各个城市一次后返回出发城市，要确定一条行走的路线，计算途径个城市的最短距离，即给定n 个城市和两两城市之间的距离，确定一条经过每个城市并且仅经过一次的路线，要求

2、总路径最短。对于城市数目为n 的地图, 共有n 种不同的路径，城市越多,可能的路径也越多。而且路径的增加速度非常快且是非线形的。当n 很大时，去尝试每一种可能的路径是不可能的，所以需要设计一个有效的算法去寻找最短的路径1,2。蚁群算法原理基于蚁群算法，首先引入TSP 中常用符号：m 为蚁群中蚂蚁数量；bi(t)为t 时刻位于城市i 的蚂蚁个数，且m=ni = 1bi(t)； dij 为城市i 和j 之间的距离； nij 为边（i,j）的能见度，反映由城市i转移到城市j 的启发程度；ij 为边（i,j）上的信息素轨迹强度；tij 为蚂蚁k 在边（i,j）上留下的单位长度轨迹信息素量；Pkij 为

3、蚂蚁k 的转移概率；j 是尚未访问的城市。在初始时刻，各条路径上的信息素量相等，设ij(0)=C，（C 为常数），蚂蚁k(k=1,2,，m)被随机放到某个城市，然后根据各条路径上的信息素量选择下一个城市。在t 时刻，的城市； 和 为2 个参数，分别反映蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。为了阻止蚂蚁重复访问，为每只蚂蚁都设计一个被称为禁忌表（tabu list）的数据结构。经过n 个时刻，蚂蚁完成一次循环，各路径上信息素“蒸发”和增加的量根据下式调整：式中： 表示信息素蒸发后的剩余，则（1-）为衰减系数，表示信息素的减少； 表示信息素增加的量，在式（1）中表示第

4、k 只蚂蚁在时刻dij 留在路径(t,t+1)上的信息素量；，Q 为常数，L（k）为第k个蚂蚁爬过路径(i， j)的长度，等于dij 的值。至此，一个蚂蚁的循环过程结束，由此反迭代多次，最终得出优化结果。关键词：旅行商问题 蚁群算法 经纬度 MAYTLAB程序 层次分析 综合评价问题重述周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：1按地理位置（经纬度）设计最短路旅行方案；2如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；3 要综合考虑省钱、省时又

5、方便，设定你的评价准则，建立数学模型，修订你的方案；4对你的算法作复杂性、可行性及误差分析；5关于旅行商问题提出对你自己所采用的算法的理解及评价。一、问题的分析组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等。这类问题通常随着问题规模的扩大，问题空间呈现组合爆炸特征，无法用常规的方法求解。旅行商问题 (TSP)就是一个经典的组合优化问题，问题要求求得一条遍历所有城市的最短回路，属于NP 难问题。随着城市数目增多，求解问题的空间、时间复杂度将呈指数级增长，若使用穷举搜索法求解，在现有条件下是无法实现的。20世纪90年代，欧洲学者 Dorigo Mac

6、ro等人从生物进化论中得到启发，通过模拟自然界中蚂蚁集体寻找食物源的行为(群集智能)提出了蚁群算法(Ant Colony Optimization)，该算法最早成功地应用于求解 TSP 问题。后来又用于解决其他组合优化问题，并取得了较好的效果。然而，蚁群算法本质上和模拟退火算法、遗传算法等随机搜索算法一样，存在扩大搜索空间与寻找最优解之间的矛盾(尤其是针对大规模问题)，这意味着蚂蚁要选择的下一个移动的点的可选范围很大，计算时间自然也要增加，而构造候选集就可以把运算时间控制在一定的范围。目前一般都采用最近邻居表(Nearest Neighbor List)来构造候选集，但这种方法没有考虑问题的几

7、何结构，而且存在着一些风险会阻止最优解的生成，出现解的退化。本文在蚁群算法的基础上，针对以上不足和 TSP问题的几何特点，提出了象限近邻表构造候选集的方法，限定了每只蚂蚁下一步移动所能选择的城市，并且利用所构造的候选集，初始化信息素数量，从而大大缩减了解空间，使蚂蚁搜索空间集中于最优解附近。本文算法在对 TSPLIB 的实验结果表明其搜索精度和搜索时间都有较好表现。目前， 蚁群算法己有多种模型， 应用较多的有Ant System(AS)1，Ant Colony System(ACS) 1.2，MAXM1NAS(MMAS)3,其主要思想都是模拟蚂蚁觅食的群集智能。蚂蚁运动时会在路径上释放一种可称

8、之为“信息素”(Pheromone)的物质，通过信息素来交换“路径信息”使整个蚁群的行为具有很高的自组织性，蚂蚁运动形成一个正反馈机制，最终通过蚁群的集体催化行为找出最优路径。蚁群算法主要包括两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息素不断调整自身结构：路上经过的蚂蚁越多，信息素数量越大，则该路径越容易被选择；时间越长，信息素数量越少。在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。这里以ACS作为蚁群算法的一个代表，其结果可普及到其他蚁群算法二、问题的提出周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定

9、出行方案：1按地理位置（经纬度）设计最短路旅行方案；2如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；4 要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；4对你的算法作复杂性、可行性及误差分析；5关于旅行商问题提出对你自己所采用的算法的理解及评价三、模型的假设，符号说明（1） 市场的情况，所以只能从有限的市场调查数据中来获取，另外其他类学科的统计信息对整个市场的影响很微小，所以我们可以将其忽略，以减少分析的复杂度；（2） 在求解不同性质的问题时，蚁群算法的模型也有所不同，但主要思想都是

10、生成一定数量的蚂蚁，通过每只蚂蚁搜索路径建立可行解。先将蚂蚁随机放置在若干节点上，每只蚂蚁从初始节点出发，根据路径上信息素浓度和启发信息以某种概率策略选择下一个节点，直到建立可行解；（3） 每只蚂蚁根据解的优劣程度，更新路径上的信息素。如此周而复始，直到蚁群找到最优解；（4） 以n个城市的旅行商问题(Traveling Salesman Problem,TSP)为例来说明基本蚁群算法(Ant Colony System，ACS)8。TSP是指旅行商按一定顺序访问每一个城市，每个城市仅能访问一次，最后回到起点，且路径最短；（5） TSP的实质是在n个节点的完全图上找到一条最短的哈密顿(Hamil

11、ton)路径，是一个易于描述却难于处理的NP难题；（6） 设m是蚁群中蚂蚁的数量，dij(i，j=1，2，n)表示城市i和城市j之间的距离， 表示时刻在城市i与城市j路径上信息素的浓度。初始时刻，各条路径上信息素的浓度相等， (C为常数)。蚂蚁通过概率策略选择下一个要访问的城市，令表示在时刻蚂蚁k从城市i转移到城市j的概率；（7） 假设周先生自带充足食物，并不考虑住宿问题；四、模型的建立各城市经纬度分布：城市经度纬度北京e11628n3954上海e12129n3114天津e11711n3909重庆e10632n2932哈尔滨e12641n4545长春e12519n4352沈阳e12324n41

12、50呼和浩特e11148n4049石家庄e11428n3802太原e11234n3752济南e117n3638郑州e11342n3448西安e10854n3416兰州e10349n3603银川e10616n3820西宁e10145n3638乌鲁木齐e8736n4348合肥e11718n3151南京e11850n3202杭州e12009n3014长沙e113n2811南昌e11552n2841武汉e11421n3037成都e10405n3039贵阳e10642n2635福州e11918n2605台北e12131n2503广州e11315n2308海口e11020n2002南宁e10820n224

13、8昆明e10241n25拉萨e9110n2940香港e11410n2218全国各大城市所处位置中国当前火车车次普快16:1800:1300:2807:51空调普快12:1501:0901:2106:52普快12:2701:1801:3607:11快速13:0002:1302:2405:42普快19:2002:1502:3109:45空调普快13:3302:2202:5121:40空调快速12:3803:2503:4509:07空调普快11:5103:1703:5211:08普快15:5803:4404:0313:27普快20:5804:2204:2204:22空调快速12:5104:2204:

14、3711:41普客04:0504:2004:4011:58普客04:1404:2904:4921:28空调普快10:0304:4805:0318:24空调特快17:0805:0005:1607:54空调快速16:3305:1805:3412:41普客05:1205:2705:3806:21空调快速20:4605:2805:4409:10快速19:4605:3605:5306:08空调普快16:3505:5705:5705:57空调普快19:4405:5705:5705:57空调快速21:2505:5805:5805:58快速18:1205:3606:0006:25普快21:1005:4206:

15、0206:17普快20:0006:0506:0506:05普快20:1005:4706:1021:15空调特快20:4806:0306:1907:41快速06:2306:0706:2407:00普快11:0306:2906:2906:29普客06:3606:3606:3610:55空调快速13:0506:3806:3806:38普快06:0006:1506:4119:34空调快速20:3006:2506:4707:20普快14:3106:5706:5706:57空调快速06:2006:3507:0012:53空调快速19:0006:3807:0307:18空调直达21:2007:0407:04

16、07:04快速20:2006:5107:0707:26普客07:0807:0807:0807:45空调直达21:1407:1007:1007:10普客05:3507:1907:1907:19空调快速20:2607:2107:2107:21空调特快21:5407:2807:2807:28空调特快07:3007:3007:3009:57空调快速21:1807:2607:3807:58快速05:5507:3807:3807:38空调特快18:2007:4207:4207:42普客07:4507:4507:4510:03空调快速07:4607:4607:4610:49普快19:5007:4408:04

17、08:25普客06:5208:0908:0908:09空调快速07:2708:0008:1512:55空调特快07:2208:0508:1810:38空调特快21:2608:2608:2608:26空调快速21:2008:0708:2808:52空调特快08:3408:3408:3412:09空调特快08:4508:4508:4507:54空调普快05:1008:3808:5414:50动车组08:5808:5808:5817:10快速08:1708:3708:5912:37快速04:5608:4309:0216:53动车组09:0609:0609:0617:44空调普快19:5708:570

18、9:1621:38普快05:3409:1809:1809:18空调普快17:2009:2809:2809:28普快18:1009:1809:3010:00快速21:0409:2009:3209:47空调普快09:3309:3309:3313:22空调普快16:0809:3509:3509:35普快09:3809:3809:3818:07空调普快10:2109:4209:4209:42空调快速09:4709:4709:4717:43普客05:1009:2709:5010:15空调特快07:2909:5709:5709:57普客06:3509:4010:0010:35普快10:0010:0010:

19、0018:18普客08:4009:5510:0310:18空调特快10:2010:2010:2012:47空调普快10:3110:3110:3107:25普客07:0510:2010:3510:50快速20:2910:4810:4810:48空调快速11:4511:4511:4515:57快速20:3711:3011:5012:05普快06:3311:4012:0520:27空调快速07:4312:0512:0512:05普快08:1811:5012:1018:55空调特快10:2212:5012:5012:50普快07:1112:5212:5212:52动车组08:5513:0213:021

20、3:02快速06:3312:4113:0218:48快速01:0112:4013:0405:32空调快速09:0412:4013:0405:32空调特快13:1013:1013:1015:36动车组13:1813:1813:1817:24空调快速07:2913:2013:2013:20空调特快11:0413:2513:2513:25快速08:1913:1313:2817:10空调快速13:3013:3013:3017:52普快13:3313:3313:3309:05空调快速13:4413:4413:4419:33空调特快13:4613:4613:4616:06快速06:4213:3914:03

21、20:07空调快速07:4914:0514:0514:05空调快速14:2714:2714:2719:54普快14:3514:3514:3519:53普快12:3614:3614:3614:36空调普快14:4014:4014:4010:03空调快速19:4414:2514:4314:58普快07:1714:2414:4818:28空调快速14:5314:5314:5308:31空调普快13:5814:5614:5614:56快速11:1114:4615:0220:23空调快速23:0014:4915:1018:37快速23:0014:4915:1003:05动车组07:1515:1915:1

22、915:19快速07:0514:5915:2219:40普快10:4015:2915:2915:29普快07:3515:1715:3520:13动车组15:3815:3815:3823:33空调特快17:4716:1016:1016:10空调普快08:4515:5916:1921:59普快16:2916:2916:2921:18空调特快14:0416:3216:3216:32普快15:5716:1216:3506:49普客15:3016:2216:3617:47空调特快10:5816:1616:4320:27空调特快16:5516:5516:5519:22普客16:1416:5017:0520

23、:56快速17:0817:0817:0807:08空调特快18:0517:1117:1117:11空调普快11:0217:0117:1605:23普客16:5317:1217:2019:00普客16:4517:0017:2320:53普快17:2917:2917:2916:23快速17:0617:2117:4808:04快速17:5117:5117:5119:35空调快速15:5917:5217:5217:52普快17:5817:5817:5807:56普客16:2517:4317:5918:28普客14:3818:0018:0018:00空调快速09:2718:0318:0318:03空调快

24、速17:0817:4018:0805:30普快08:4218:1618:1618:16普客18:1818:1818:1821:29空调快速13:3918:1318:2218:37空调普快10:5518:0018:2410:28空调特快15:5618:2418:2418:24快速14:4018:4218:4218:42空调快速11:2818:2718:4410:16空调特快16:2918:5018:5018:50空调快速18:5218:5218:5223:14快速18:2118:3618:5507:10普快18:5618:5618:5622:32快速18:1518:4118:5906:16空调特

25、快15:4219:0519:0519:05空调特快19:0919:0919:0908:08快速19:1519:1519:1517:31空调特快19:1619:1619:1617:50普客18:1719:2319:2319:23空调快速16:2819:3119:3119:31普快18:4719:0819:3308:08空调快速13:5019:2019:4010:37普客19:4719:4719:4721:07普客15:1519:5319:5319:53空调快速12:3019:3919:5509:08空调快速16:0719:5020:0607:02空调快速14:0019:5220:0720:22普

26、快20:1520:1520:1506:37空调快速20:2220:2220:2207:47普快07:3620:0320:2320:48普快05:4720:1220:3006:10空调快速18:2020:3220:3220:32空调普快07:3420:2020:3310:04普快10:3820:2020:4008:58空调普快20:4720:4720:4706:53空调普快20:5520:5520:5522:58空调普快17:0020:5720:5720:57快速20:2720:4220:5707:07空调快速20:1320:3320:5806:56空调特快21:1021:1021:1008:3

27、1空调快速20:0720:4921:1509:04空调特快21:1821:1821:1806:33空调快速20:5221:0721:2707:06空调直达21:3621:3621:3607:20空调直达21:4221:4221:4207:26空调普快15:2221:2421:4823:59动车组13:5021:5821:5821:58空调快速21:1521:3021:5818:29空调快速22:0022:0022:0006:42普客14:1021:3422:0122:16空调特快18:5421:4322:0409:13空调普快17:1821:4722:1005:05空调特快20:2721:56

28、22:1407:31快速21:3921:5422:2209:40普快12:1222:2022:3520:14普客06:2022:0922:3622:51普快06:4322:3722:3722:37普快15:1022:1922:3809:00动车组14:0522:4922:4922:49空调普快22:5322:5322:5313:31普快22:1922:3422:5506:08空调普快15:2422:2923:0008:50普快17:0222:3823:0711:16空调普快12:5822:5723:1406:10快速19:2423:0523:2011:43普快23:2123:2123:2115

29、:02普快11:0923:1023:2506:48普快21:5022:5423:2809:40空调特快20:5223:3023:4507:08MTSP 数学模型以点0 表示旅行商的出发城市,称为源点,点1 ,2 , , l表示m 个旅行商需访问的城市。定义变量xij k = 1 , 旅行商k 通过弧段( i , j) ;0 , 否则yki = 1 , 旅行商k 访问城市i ;0 , 否则cij 表示旅行商经过对应弧段( i , j) 所需的费用, 如时间、距离、花费等。则得到以下模型:目标函数为Z = min (max ( z1 , z2 , , zm ) ) (1)式中zk = li =0

30、lj =0cij x ij k , k = 1 ,2 , , m (2)约束条件mk =1yki = m , i = 01 , i = 1 ,2 , , l(3)li =0xij k = ykj , j = 0 ,1 , , l ; k = 1 ,2 , , m (4)lj =0xij k = yki , i = 0 ,1 , , l ; k = 1 ,2 , , m (5)X = ( xij k ) S (6)式中, S 为支路消去约束, 即消去构成不完整路线的解, 具体含义可参见文献6 。在该模型中, 式(1) 表示使m 个旅行商中的旅行费用最大的那个最小化;式(2) 表示各个旅行商的费用

31、;式(3) 表示从指定城市0 出发, 所有城市只有某一个旅行商严格访问一次;式(4) 表示任意一条弧的终点城市仅有一个起点城市与之相连;式(5) 表示任意一条弧的起点城市仅有一个终点城市与之相连;式(6) 表示消去构成不完整线路的解。2 递阶遗传算法在生物学领域,染色体的结构是一系列基因按层次排列而成的,一些基因控制着另一些基因。染色体可表示为包括控制基因和参数基因的递阶结构, 参数基因处于最低级,控制基因处于上级,下级基因串受上级基因的控制。在基因编码时,控制基因常采用整数编码,不同整数信息表示对应的基因处于不同的激活状态, 而与该基因相联系的低级基因串则处于对应的状态。为计算方便和加强遗传

32、算法在解空间的搜索能力,参数基因采用实数编码,每个基因用一个实数代表。这样定义染色体结构的遗传算法称为递阶遗传算法,它比传统遗传算法包含更多的信息,因而能处理更复杂的问题。目前,递阶遗传算法已在神经网络、模糊系统、车间调度等方面得到了较好的应用729 。3 递阶遗传算法设计基于MTSP 的特点,可以设计成二级递阶染色体结构描述其结构和参数,控制基因中的每一个等位基因表示城市,参数基因中的每一个等位基因表示所路过的旅行商。对于给定问题,其控制基因和参数基因个数是确定的,都为不含源点的城市个数l , 控制基因取值为1 l 中互不相等的整数, 参数基因取值为1 m 中的整数, m 为旅行商个数,因此

33、优化MTSP 只需确定基因信息。例如,对于有8 个城市(含源点城市) 、旅行商数上限为3 的MTSP ,假设城市0 为源点,本文采用二级递阶染色体结构描述如图1 所示。如控制基因中第1 个等位基因取值为4 ,对应的参数基因取值为2 时,表示城市4 由旅行商2 访问;控制基因中第2 个等位基因取值为5 ,对应的参数基因取值为3 ,表示城市5由旅行商3 访问,其余以此类推。图1 染色体的递阶结构设计3. 1 群体规模选择合适的群体规模对遗传算法的收敛具有重要意义。群体太小难以求得满意的结果,群体太大则计算复杂。根据经验,群体规模一般取10160 。3. 2 适值函数遗传算法在进行选择操作时会出现欺

34、骗问题 10 :在遗传进化的初期,通常会产生一些超常的个体,若按照比例选择法,这些异常个体因竞争力太突出而控制了选择过程,影响算法的全局优化性能;在遗传进化的后期,即算法接近收敛时,由于种群中个体适值差异较小,继续优化的潜能降低,可能获得某个局部最优解。适值函数设计不当有可能造成这种问题的出现。由于优化目标为最小化路程或费用值,因此令目标函数作指数变换得到适值函数f = exp ( - Z) (7)式中,为正实数。3. 3 选择选择是用来确定重组或交叉个体, 以及备选个体将产生多少个子代个体。选择的第一步是计算适值, 采用按比例的适值分配,是利用各个个体选择的概率决定其子孙的遗留可能性。若某个

35、个体i ,其适值为f i ,则其被选择的概率表示为Pi = f i Mk =1f k (8)然后计算各个染色体的累积概率qi = Mi =1pi (9)第二步用轮盘赌选择法进行选择。为了选择交配个体, 需要进行多轮选择,每一轮产生一个0 , 1 均匀随机数, 将该随机数作为选择指针来确定备选个体。3. 4 交叉与变异递阶遗传算法的交叉与变异操作分为控制基因交叉与变异以及参数基因交叉与变异。2632 系统工程与电子技术第31 卷交叉在遗传操作中起核心作用, 交叉概率较大可增强遗传算法开辟新搜索空间的能力, 但性能好的基因串遭到破坏的可能性较大, 算法收敛速度降低, 且不稳定;若交叉概率较小,则遗

36、传算法搜索可能陷入迟钝状态。对于控制基因串交叉可以采用基于路径表示部分匹配交叉(partiallymatched crossover , PMX) 、顺序交叉(ordered crossover ,OX) 、循环交叉(cycle crossover ,CX) 等 10 ;对于参数基因串采用单点交叉。PMX是Goldberg 等于1985 年针对TSP 提出的基于路径表示的交叉操作,其操作要求随机选取两个交叉点,以便确定一个匹配段,根据两个父个体中两个交叉点之间的中间段给出的影射关系生成两个子个体。OX 是Davis 等针对TSP 提出的基于路径表示的交叉操作,该操作能保留排列并融合不同排列的有

37、序结构单元。两个父个体交叉时,通过选择父个体1 的一部分,保存父个体2 中代码的相对顺序生成子个体。CX 是Oliver 等针对TSP 提出的交叉操作,循环交叉操作中子个体中的代码顺序根据任一父个体产生。变异在遗传操作中属于辅助性的搜索操作,主要目的是维持群体的多样性。较低的变异概率可以防止群体中重要的单一基因丢失,但降低了遗传算法开辟新搜索空间的能力;较高的变异概率将使遗传操作趋于纯粹的随机搜索,降低了算法的收敛速度和稳定性。对于控制基因串采用交换变异,即交换两个随机位置上的基因;对于参数基因串采用整数变异,即对每一基因以一定概率用1 , m区别于该基因的整数加以替代。3. 5 解码图1 所

38、示为染色体递阶结构,由以上介绍的染色体递阶结构的含义可知,旅行商1 访问城市6 、7 ;旅行商2 访问城市1 、4 ;旅行商3 访问城市2 、3 、5 。这里,规定控制基因串从左至右为城市被访问的先后顺序。因此,可以得到:旅行商1 访问的城市及顺序为0 6 7 0 ;旅行商2 访问的城市及顺序为0 4 1 0 ;旅行商3 访问的城市及顺序为0 5 2 3 0 。由于该问题为8 个旅行城市(包含源点城市0) ,所以城市之间的距离矩阵为8 8 的矩阵,设该矩阵为D。为了避免某个旅行商出现0 0 0 的行走路径,如图2 所示的一条染色体递阶结构。图2 其中一条染色体递阶结构根据递阶结构的含义, 可得

39、到3 个旅行商的行走路径分别为0 4 6 7 0 ;0 0 0 ;0 5 1 2 3 0 。如上所示,旅行商2 出现了0 0 0 的路径,因此在矩阵D 中,要将城市0 0 的距离设为很大的正数M ,这样可以使出现这种情况的染色体在选择复制过程中被淘汰。这里,先设矩阵D 为对称距离矩阵,并设城市0 0 的距离为10 000 ,对于非对称距离矩阵下面的解码方法同样适用。城市0 城市7 D =10 000 13 10 11 9 8 18 2113 0 5 9 14 11 21 710 5 0 13 6 21 16 1711 9 13 0 11 13 19 129 14 6 11 0 14 16 18

40、8 11 21 13 14 0 8 1918 21 16 19 16 8 0 2221 7 17 12 18 19 22 0城市0城市7在应用计算机具体编程时可采用如下解码步骤:步骤1 由旅行商1 的访问路径可得: x061 = 1 , x671 =1 , x701 = 1 。因此,旅行商1 的可达矩阵为城市0 城市7 X1 =0 0 0 0 0 0 1 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 11 0 0 0 0 0 0 0城市0城市7同理,旅行商2 、

41、3 的可达矩阵分别为X2 =0 0 0 0 1 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 1 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0, X3 =0 0 0 0 0 1 0 00 0 0 0 0 0 0 00 0 0 1 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 1 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0步骤2 每个旅行商的行走路程为:对于旅行商1 将矩阵X1 与矩阵D 点乘得到矩阵

42、D1 ,矩阵D1 中不为0 的数值之和即为旅行商1 所访问城市的距离。设旅行商1 、2 、3 所访问城市的距离为分别为z1 、z2 、z3 。D1 = X1 DD1 =0 0 0 0 0 0 18 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 2221 0 0 0 0 0 0 0z1 = 18 + 22 + 21 = 61同理z2 = 9 + 14 + 13 = 36z3 = 8 + 21 + 13 + 11 = 53步骤3 最后求得所有旅行商中最大的行走路程Z

43、 = max ( z1 , z2 , z3 ) = 61第11 期周辉仁等:基于递阶遗传算法的一类多旅行商问题优化2633 4 实例仿真以上介绍了递阶遗传算法优化MTSP 的步骤,本节通过TSPL IB 中的距离非对称的数据进行仿真。4. 1 17 个城市( br17. atsp) 的MTSPbr17. at sp 数据总共有17 个城市,并且其距离矩阵是非对称的。设旅行商数为3 ,进行仿真。对于控制基因串分别采用CX、OX和PMX,交叉概率为0. 55 ,变异采用交换变异且变异概率为0. 25 ;对于参数基因串采用单点交叉且交叉概率为0. 55 ,变异采用整数变异且变异概率为0. 005 ;

44、种群规模为100 ;最大迭代次数为100。用Matlab 语言编程,随机运行10 次,所得结果如表1 所示。表1 br17. atsp 的仿真结果递阶遗传算法交叉算子最优解最差解平均解CX 28 28 28OX 28 28 28PMX 28 28 28本文所求最优解的路线分别为:1 8 9 17 11 13 12 1 ;1 7 16 6 4 5 15 1 ;1 3 14 10 2 1 。其中,3 个旅行商的路程分别为13 、28 和11 。为了便于比较,对该实例用标准遗传算法进行仿真。交叉算子同样分别采用CX、OX 和PMX ,交叉概率为0. 55 ,变异采用交换变异且变异概率为0. 25 ;

45、种群规模为100 ;最大迭代次数为100 。用Matlab 语言编程,随机运行10 次,所得结果如表2 所示。表2 br17. atsp 的仿真结果( 标准遗传算法)交叉算子最优解最差解平均解OX 28 31 28. 9CX 28 31 28. 3PMX 28 31 28. 9本实例是一个小规模的MTSP ,通过表1 和表2 数据比较可以看出,递阶遗传算法所求的结果是比较稳定的,优于标准遗传算法的结果。4. 2 124 个城市( kro124p) 的MTSPkro124p 数据总共有100 个城市,并且其距离矩阵是非对称的。设旅行商数分别为4 ,8 ,12 ,进行仿真。对于控制基因串分别采用C

46、X、OX 和PMX ,且交叉概率为0. 55 ,变异采用交换变异且变异概率为0. 25 ;对于参数基因串采用单点交叉且交叉概率为0. 55 ,变异采用整数变异且变异概率为0. 005 ;种群规模为100 ;最大迭代次数为500 。用Matlab 语言编程,旅行商数分别为4 ,8 ,12 时,各随机运行10 次,所得结果如表3 所示。为了便于比较,对该实例用标准遗传算法进行仿真。交叉算子同样分别采用CX、OX 和PMX ,交叉概率为0. 55 ,变异采用交换变异且变异概率为0. 25 ;种群规模为100 ;最大迭代次数为500 。用Matlab 语言编程,随机运行10 次,所得结果如表4 所示。

47、表3 kro124p 的仿真结果( 递价遗传算法)旅行商数交叉算子最优解最差解平均解4CX 22 665 25 422 24 421OX 22 482 27 692 25 863PMX 21 454 25 418 23 3778CX 14 040 16 167 14 754OX 14 154 16 533 15 461PMX 13 810 14 930 14 48412CX 10 118 11 496 10 680OX 10 913 12 040 11 398PMX 10 026 11 738 10 653表4 kro124p 的仿真结果( 标准遗传算法)旅行商数交叉算子最优解最差解平均解4C

48、X 24 174 26 084 25 251OX 24 610 29 936 26 297PMX 21 652 25 966 23 6638CX 15 091 17 154 16 054. 5OX 15 022 17 134 16 333. 9PMX 14 157 16 211 14 894. 612CX 11 436 13 192 12 196. 5OX 11 891 13 604 12 707. 8PMX 10 965 13 272 11 974. 9本实例是一个大规模的MTSP。从表3 可以看出,在上述参数设定情况下,递阶遗传算法中控制基因串采用基于路径表示PMX 无论是在最优解和平均解方面都要优于CX 和OX;从表3 和表4 的比较可以看出,对于给定的旅行商数和交叉算子,在最优解和平均解方面,递阶遗传算法要优于标准遗传算法。五、模型的求解按照模型求解得按图示所标路线依次旅游，即可花最少的钱，走最短的路，走遍全中国。专心-专注-专业