数学建模B题走遍全中国.doc

《数学建模B题走遍全中国.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

5、、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；3．要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；4．对你的算法作复杂性、可行性及误差分析；5．关于旅行商问题提出对你自己所采用的算法的理解及评价。一、问题的分析组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等。这类问题通常随着问题规模的扩大，问题空间呈现组合爆炸特征，无法用常规的方法求解。旅行商问题(TSP)就是一个经典的组合优化问题，问题要求求得一条遍历所有城市的最短回路，属于NP难问题。随着城市数目增多，求解问题

6、的空间、时间复杂度将呈指数级增长，若使用穷举搜索法求解，在现有条件下是无法实现的。20世纪90年代，欧洲学者DorigoMacro等人从生物进化论中得到启发，通过模拟自然界中蚂蚁集体寻找食物源的行为(群集智能)提出了蚁群算法(AntColonyOptimization)，该算法最早成功地应用于求解TSP问题。后来又用于解决其他组合优化问题，并取得了较好的效果。然而，蚁群算法本质上和模拟退火算法、遗传算法等随机搜索算法一样，存在扩大搜索空间与寻找最优解之间的矛盾(尤其是针对大规模问题)，这意味着蚂蚁要选择的下一个移动的点的可选范围很大，计算时间自然也要

7、增加，而构造候选集就可以把运算时间控制在一定的范围。目前一般都采用最近邻居表(NearestNeighborList)来构造候选集，但这种方法没有考虑问题的几何结构，而且存在着一些风险会阻止最优解的生成，出现解的退化。本文在蚁群算法的基础上，针对以上不足和TSP问题的几何特点，提出了象限近邻表构造候选集的方法，限定了每只蚂蚁下一步移动所能选择的城市，并且利用所构造的候选集，初始化信息素数量，从而大大缩减了解空间，使蚂蚁搜索空间集中于最优解附近。本文算法在对TSPLIB的实验结果表明其搜索精度和搜索时间都有较好表现。目前，蚁群算法己有多种模型，应用较多

8、的有AntSystem(AS)[1]，AntColonySystem(ACS)[1.2]，MAXM1NAS(