改进的蚁群算法在TSP问题上的应用

《改进的蚁群算法在TSP问题上的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中南民族大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权中南民族大

2、学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密□，在______年解密后适用本授权书。2、不保密□。√（请在以上相应方框内打“√”）作者签名：日期：年月日导师签名：日期：年月日中南民族大学硕士学位论文第1章绪论1.1论文选题背景与意义组合优化问题是运筹学中的一个经典且重要的分支,而在组合优化问题中，旅行商问题（TravelingSalesmanProblem，TSP）是近代组合优化领域的一个典型难题。由于TS

3、P问题形式简单、易于描述、且属于典型的NP难问题，因此其作为算法研究与验证的平台而被广泛研究。在TSP问题上取得的理论或者实验成果，可以应用于其他的NP难解问题。事实上，求解NP难问题的许多方法都源自于TSP问题的研究。TSP问题不但具有很大的理论价值，而且在科学、工程及经济的各方面具有广泛的应用，是诸多领域内出现的多种复杂问题的集中概括和简化形式。如：网络通讯、电路板钻孔、管道铺设、货物配送、交通调度、电网规划等，这些问题或者直接就是TSP问题的原型，或者可以转化为TSP问题。因此，快速、有效地

4、解决TSP问题有着极高的实际应用价值。然而关于TSP问题的完全有效的算法目前尚未找到，这促使人们长期以来不断地探索并积累了大量的算法，如遗传算法、禁忌搜索算法、模拟退火算法、蚁群算法等。本文重点研究的是改进的蚁群算法在TSP问题中的应用。蚁群算法(AntColonyOptimization,ACO)是一种模仿蚂蚁群体行为的新的智[1]能优化算法。1991年，意大利学者DorigoM等人首次提出蚁群算法，开始并没受到国际学术界的广泛关注，直到1996年，DorigoM等人在《IEEETransact

5、ionsonSystems,Man,andCybernetics-PartB》上发表了”Antsystem:optimizationbyacolonyofcooperatingagents”一文,奠定了蚁群算法的基础。从此之后，蚁群算法逐渐引起了国际学术界的广泛关注。1998年，DorigoM组织在比利时布鲁塞尔召开了第一届蚂蚁优化国际研讨会，以后每两年召开一次。2000年，Gutjahr[2]WJ发表了题为“Agraph-basedantsystemanditsconvergence”的学术论[

6、3]文，对蚁群算法的收敛性进行了证明。同年，DorigoM和BonabeauE等在国际顶级学术杂志《Nature》上发表了蚁群算法研究综述，将这一研究推向国际学术界1改进的蚁群算法在TSP问题上的应用的前沿。和遗传算法、禁忌搜索算法等智能优化算法相比，蚁群算法具有正反馈性、并发性、易与其它算法相结合等主要特点。这些特点使得蚁群算法的应用非常广泛。如：英国电信公司的电信网络管理试验是基于电子蚂蚁的；英国联合利华公司的生产计划管理软件、美国太平洋西南航空公司的运输管理软件都是基于蚁群算法的。实际上，蚁

7、群算法在诸多的领域都有不俗的表现，如电子系统、控制参数优化、聚类分析、网络路由问题、布局优化等。总之，蚁群算法已经渗透到多个应用领域，从一维静态优化问题到多维动态优化问题，从离散问题到连续问题。蚁群算法都展现出优异的性能和广阔的发展前景。1.2TSP问题简介TSP问题也称货郎担问题，是一个较古老的问题。最早的记录来自于1759年欧拉研究的骑士周游问题，即对于象棋盘中的64个方格，走访每个方格一次且仅一次。1948年，由于美国兰德公司的推动，TSP问题成为一个知名且流行的问题。它已经被证明属于NP难

8、题。1.2.1TSP问题的定义TSP问题可以简单描述为：给定n个城市(记为：rr,,Lr)和它们两两之间的12,n直达距离(记为：drr(,))，寻找一条闭合的旅程，使得每个城市刚好经过一次且ij总的旅行距离最短。即寻找一条巡回路径R=(,,,)rrLr，使得公式(1.1)所示的12n目标函数最小。n−1f()Rd=+∑(,)(,)riird+11rnr(1.1)i=1用图论的语言描述为：在一个赋权完全图中，找出一个最小权的哈密顿圈。记GVE=(,)为赋权图，Vn={1,2,L,}