基于蚁群算法解决了旅游业务问题.docVIP

学 号： 能力拓展训练 题 目 基于蚁群算法解决tsp问题 学 院 计算机科学与技术学院 专 业 班 级 姓 名 指导教师 2011——2012学年 第2学期 目录TOC \o 1-3 \h \u HYPERLINK \l _Toc27432 一.介绍 PAGEREF _Toc27432 - 2 - HYPERLINK \l _Toc20696 二 详细设计说明 PAGEREF _Toc20696 - 3 - HYPERLINK \l _Toc11222 2.1模块描述 PAGEREF _Toc11222 - 3 - HYPERLINK \l _Toc25707 2.2性能 PAGEREF _Toc25707 - 3 - HYPERLINK \l _Toc30179 2.3算法 PAGEREF _Toc30179 - 3 - HYPERLINK \l _Toc15749 2.4流程逻辑 PAGEREF _Toc15749 -7- HYPERLINK \l _Toc8497 2.5接口 PAGEREF _Toc8497 - 8 - HYPERLINK \l _Toc17292 三 程序 PAGEREF _Toc17292 - 9 - HYPERLINK \l _Toc22228 四.结果 PAGEREF _Toc22228 - 20 - HYPERLINK \l _Toc12273 五.程序设计心得与体会 PAGEREF _Toc12273 - 21 - HYPERLINK \l _Toc2919 六.参考文献 PAGEREF _Toc2919 - 22 - 基于蚁群算法解决tsp问题 摘 要： TSP问题是典型的NP - hard组合优化问题,蚁群算法是一种求解此类问题的优化算法,通过模拟蚂蚁觅食行为来解决NP问题。文章使用蚁群算法求解TSP问题,并结合TSP问题的特点选择了一种合适的蚁群更新策略。关键词：TSP问题,蚁群算法,群集智能,信息素一、介绍 旅行商问题( Traveling Salesman Problem, 简称TSP)是一个经典的NP难题,也是组合优化中研究最多的问题之一,它解决如何找到一条从一个城市出发经过若干个城市后又返回原城市的最短路径。城市管道铺设优化、物流业的车辆调度、制造业中的切割路径优化等,现实生活中的优化问题都可以归结为TSP问题进行求解。寻找一种有效的解决该问题的算法,具有重要的现实意义。蚁群算法是DorigoM等提出的,该算法采用了分布式并行计算机制,易于与其他方法结合,而且具有强的鲁棒性,是求解TSP问题的一种理想方法。算法的主要思想为:模拟蚂蚁觅食行为。蚂蚁在运行过程中会释放一种特殊的分泌物- 信息素来寻找路径。信息素会随着时间消减,后面的蚂蚁选择信息素多的路径,这样便形成了一个正反馈机制。在整个寻径过程中,虽然单只蚂蚁的选择能力有限,但它们的行为具有非常高的自组织性,相互之间交换路径,最终寻找到最优路径。二、详细设计说明 2.1模块描述 本程序共有void addcity(); void Clear(); void UpdateResult(); void move(); void move2last(); void shucout()；void project::initmap()；void project::GetAnt()；void project::StartSearch() ；void project::UpdateTrial() 。１０子程序模块和int main()一个主程序。 void shucout()　　显示欢迎信息模块 void ant::move2last() 只剩下一个城市没走过时才调用，直接移动到最后一个城市 void ant::Clear() 清空数据，蚂蚁周游完各个城市后，要重新开始周游各个城市时调用 void ant::addcity(int city) 增加一个城市到走过的城市数组中，并改变没走过的城市数组中的标志 void ant::UpdateResult() 计算周游完城市后，走过的路径长度 void ant::move() 移动到下一个城市 void project::initmap() 初始化 void project::GetAnt() 初始化随机种子 void project::StartSearch() 开始寻找最好的解决方法 void project::UpdateTrial() 更新环境信息素 ，每只蚂蚁周游完城市后才更新 2.2性能 本程序按原理来说迭代次数越大，程序得出的结果越精确，但当数值超过1000