基于蚁群算法解决旅行商问题资料.doc

学 号： 能力拓展训练 题 目 基于蚁群算法解决tsp问题 2011——2012学年 第2学期 目录 一.介绍 - 2 - 二 详细设计说明 - 3 - 2.1模块描述 - 3 - 2.2性能 - 3 - 2.3算法 - 3 - 2.4流程逻辑 -7- 2.5接口 - 8 - 三 程序 - 9 - 四.结果 - 20 - 五.程序设计心得与体会 - 21 - 六.参考文献 - 22 - 基于蚁群算法解决tsp问题摘 要：TSP问题是典型的NP - hard组合优化问题,蚁群算法是一种求解此类问题的优化算法,通过模拟蚂蚁觅食行为来解决NP问题。文章使用蚁群算法求解TSP问题,并结合TSP问题的特点选择了一种合适的蚁群更新策略。关键词：TSP,蚁群算法,群集智能,信息素一、介绍( Traveling Salesman Problem, 简称TSP)是一个经典的NP难题,也是组合优化中研究最多的问题之一,它解决如何找到一条从一个城市出发经过若干个城市后又返回原城市的最短路径。城市管道铺设优化、物流业的车辆调度、制造业中的切割路径优化等,现实生活中的优化问题都可以归结为TSP问题进行求解。寻找一种有效的解决该问题的算法,具有重要的现实意义。蚁群算法是DorigoM等提出的,该算法采用了分布式并行计算机制,易于与其他方法结合,而且具有强的鲁棒性,是求解TSP问题的一种理想方法。算法的主要思想为:模拟蚂蚁觅食行为。蚂蚁在运行过程中会释放一种特殊的分泌物- 信息素来寻找路径。信息素会随着时间消减,后面的蚂蚁选择信息素多的路径,这样便形成了一个正反馈机制。在整个寻径过程中,虽然单只蚂蚁的选择能力有限,但它们的行为具有非常高的自组织性,相互之间交换路径,最终寻找到最优路径。二、详细设计说明① ② 表示第只蚂蚁在本次循环中留在路径 上的信息量，表示本次循环所有经过的蚂蚁留在 上的信息量。 ＝ 　 ③ 定义。蚂蚁（＝１，２，…，）在运动过程中，表示在时刻蚂蚁由位置转移到位置的概率： ＝ ④ 我们用tabu[N_CITY_COUNT]记录蚂蚁目前已经走过的城市集合，AllowedCity[N_CITY_COUNT]表示蚂蚁下一步允许选择的城市集合，它等于全部的城市集合除去第只蚂蚁已走过的集合tabu[N_CITY_COUNT]。 定义为第只蚂蚁在本次循环中走过的路径和。 用蚁群算法解决ＴＳＰ问题是一个递推过程 ，当时，将蚂蚁放在各城市，设定每条路径上的信息量初值，每只蚂蚁根据公式④决定的概率从城市到城市。表示曾经有多少蚂蚁经过路径；说明较近的城市有更大的可能性被选中。用来控制两者对蚂蚁选择的影响力程度。经过一个循环后，根据公式①；②；③计算更新每条路径的信息量。将所有的复原，最后求出本次循环的最短路径。这个过程不断重复，直到所有的蚂蚁都选择同样的路径，或者循环次数达到预先设定的最高次数。 解决个城市的ＴＳＰ问题算法设计如下： ⑴初始化：设定，循环计数器，对每条路径设定初始信息量,将只蚂蚁放在个城市上（为了使问题简化，设定。 ⑵设定集合的索引，对从１到，把第只蚂蚁放在起始位置，对应的设定集合 ⑶重复下面的步骤，直到集合满为止（这一步将重复次）： 设定； 对从１到，根据公式④确定的概率，选择下一步移动的目标城市｛在时间时，第只蚂蚁所在的城市是}; 将第只蚂蚁移到城市； 把加入到集合中。 ⑷对从１到： 将第只蚂蚁从移动到； 计算第ｋ只蚂蚁所走过的路程和，并更新最小路径； 对每条路径：＝ ；　　　　　　 ⑤ ⑸对每条路径根据计算； 设定； 设定； 对每条路径，设定。 ⑹如果， 则清空所有的集合ｔ 转到第二步； 否则，得出最短的路径。 在这儿我们用的是算法，这种算法，每当结束一个循环后，根据公式 ③计算 。 2.4流程逻辑 图1 2.5接口 程序中的子函数： void addcity(int city); void Clear(); void UpdateResult(); void move(); void move2last(); void shucout(); void UpdateTrial(); void initmap(); void GetAnt(); void StartSearch(); 三．程序 #include iostream #include math.h #include time.h using namespace std; const int N_