资源描述：
《基于蚁群算法解决旅行商问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、武汉理工大学计算机科学与技术学院《能力拓展训练》课程设计学号：能力拓展训练题目基于蚁群算法解决tsp问题学院计算机科学与技术学院专业班级姓名指导教师2011——2012学年第2学期29武汉理工大学计算机科学与技术学院《能力拓展训练》课程设计目录一.介绍-2-二详细设计说明-3-2.1模块描述-3-2.2性能-3-2.3算法-3-2.4流程逻辑-7-2.5接口-8-三程序-9-四.结果-20-五.程序设计心得与体会-21-六.参考文献-22-29武汉理工大学计算机科学与技术学院《能力拓展训练》课程设计基于蚁群算法解决tsp问题摘要
2、：TSP问题是典型的NP-hard组合优化问题,蚁群算法是一种求解此类问题的优化算法,通过模拟蚂蚁觅食行为来解决NP问题。文章使用蚁群算法求解TSP问题,并结合TSP问题的特点选择了一种合适的蚁群更新策略。关键词：TSP问题,蚁群算法,群集智能,信息素一、介绍旅行商问题(TravelingSalesmanProblem,简称TSP)是一个经典的NP难题,也是组合优化中研究最多的问题之一,它解决如何找到一条从一个城市出发经过若干个城市后又返回原城市的最短路径。城市管道铺设优化、物流业的车辆调度、制造业中的切割路径优化等,现实生活中
3、的优化问题都可以归结为TSP问题进行求解。寻找一种有效的解决该问题的算法,具有重要的现实意义。蚁群算法是DorigoM等提出的,该算法采用了分布式并行计算机制,易于与其他方法结合,而且具有强的鲁棒性,是求解TSP问题的一种理想方法。算法的主要思想为:模拟蚂蚁觅食行为。蚂蚁在运行过程中会释放一种特殊的分泌物-信息素来寻找路径。信息素会随着时间消减,后面的蚂蚁选择信息素多的路径,这样便形成了一个正反馈机制。在整个寻径过程中,虽然单只蚂蚁的选择能力有限,但它们的行为具有非常高的自组织性,相互之间交换路径,最终寻找到最优路径。29武汉理
4、工大学计算机科学与技术学院《能力拓展训练》课程设计二、详细设计说明2.1模块描述本程序共有voidaddcity();voidClear();voidUpdateResult();voidmove();voidmove2last();voidshucout()；voidproject::initmap()；voidproject::GetAnt()；voidproject::StartSearch()；voidproject::UpdateTrial()。１０子程序模块和intmain()一个主程序。voidshucout()
5、 显示欢迎信息模块voidant::move2last()只剩下一个城市没走过时才调用，直接移动到最后一个城市voidant::Clear()清空数据，蚂蚁周游完各个城市后，要重新开始周游各个城市时调用voidant::addcity(intcity)增加一个城市到走过的城市数组中，并改变没走过的城市数组中的标志voidant::UpdateResult()计算周游完城市后，走过的路径长度voidant::move()移动到下一个城市voidproject::initmap()初始化voidproject::GetAnt()初始
6、化随机种子voidproject::StartSearch()开始寻找最好的解决方法voidproject::UpdateTrial()更新环境信息素，每只蚂蚁周游完城市后才更新2.2性能本程序按原理来说迭代次数越大，程序得出的结果越精确，但当数值超过1000以后，结果基本不变。要求城市数量/蚂蚁数量=1.5左右29武汉理工大学计算机科学与技术学院《能力拓展训练》课程设计dbMin=100000000.0;叠迭中的最小路径长度。2.3算法本程序是基于蚁群算法求解ＴＳＰ问题，设为城市，之间的几何距离，。设表示时刻位于城市的蚂蚁的个
7、数，蚂蚁总数，表示时刻在连线上残留的信息量，初始时刻各条路径上的信息量为（为常数）。用参数表示信息量的保留度，则经过个时刻后，路径上的信息量根据下式作调整：①②表示第只蚂蚁在本次循环中留在路径上的信息量，表示本次循环所有经过的蚂蚁留在上的信息量。＝ ③定义。蚂蚁（＝１，２，…，）在运动过程中，表示在时刻蚂蚁由位置转移到位置的概率：＝④我们用tabu[N_CITY_COUNT]记录蚂蚁目前已经走过的城市集合，AllowedCity[N_CITY_COUNT]表示蚂蚁下一步允许选择的城市集合，它等于全部的城市集合除去第只蚂蚁已走过的
8、集合tabu[N_CITY_COUNT]。定义为第29武汉理工大学计算机科学与技术学院《能力拓展训练》课程设计只蚂蚁在本次循环中走过的路径和。用蚁群算法解决ＴＳＰ问题是一个递推过程，当时，将蚂蚁放在各城市，设定每条路径上的信息量初值，每只蚂蚁根据公式④决定的概率
