基于蚁群算法的旅行商问题（TSP）实现

《基于蚁群算法的旅行商问题（TSP）实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于蚁群算法的旅行商问题（TSP）实现一．问题分析旅行商问题，即TSP问题（TravellingSalesmanProblem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得到的路径路程为所有路径之中的最小值。旅行商问题是一个经典的NP难题，也是组合优化中研究最多的问题之一。城市管道铺设优化、物流业的车辆调度、制造业中的切割路径优化等，现实生活中的优化问题都可以归结为TSP问题进行求解。寻找一种有效的

2、解决该问题的算法，具有重要的现实意义。蚁群算法是一种求解TSP问题的优化算法。二．算法选择蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法的主要思想为：模拟蚂蚁觅食行为。蚂蚁在运行过程中会释放一种特殊的分泌物-信息素来寻找路径。信息素会随着时间消减，后面的蚂蚁选择信息素多的路径，这样便形成了一个正反馈机制。在整个寻径过程中，虽然单只蚂蚁的选择能力有限，但它们的行为具有非常

3、高的自组织性，相互之间交换路径，最终寻找到最优路径。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。通过建立适当的数学模型，基于故障过电流的配电网故障定位变为一种非线性全局寻优问题。蚁群算法是一种求解TSP问题的优化算法，采用了分布式并行计算机制，易于与其他方法结

4、合，而且具有强的鲁棒性，是求解TSP问题的一种理想方法。同时，由于以前我在学习《现代智能优化算法》这门课中对蚁群算法进行过初步的学习，做过相关的Matlab仿真，所以决定在本次的TSP问题实现中采用蚁群算法。一．方案设计1.蚁群算法需要模仿蚂蚁的觅食行为，所以需要设计一个蚂蚁类来进行模仿蚂蚁的各种行为，如路径的判断、选择等。2.蚂蚁类只是代表一只蚂蚁的行为。蚁群算法是多只蚂蚁的并行算法，同时考虑到要解决城市的点坐标更新问题、环境信息素的初始化以及蚁群整体对环境信息素的影响等问题，还需要设计一个类来控制蚁群整体活动并进行环境信息素的更新、最近路线的统计、最短

5、路径的计算。3.蚁群算法是通过多次的迭代来获取最终的最优路径，为了能够动态显示求解过程，及实现暂停和继续功能，需要设计多线程来实现一边进行算法的多次迭代，一边将每次的迭代结果进行更新。4.我们设计在客户区进行结果的显示，客户区左边进行信息的显示包括城市个数、迭代次数、最短距离、最佳路线，客户区右边显示城市模型及每次的迭代过程，方便观看相关参数及运行过程。5.由于客户区用来显示结果信息，因此我们设计在子菜单中进行命令的输入选择，包括：重新设置城市坐标：当前城市数量不变，给每个城市随机产生新的坐标并显示开始：开始运行算法暂停：暂停算法继续：暂停后继续算法停止：

6、停止算法设置参数：可以设置城市的数量和迭代次数，并随机产生城市的坐标然后显示6.为相应的菜单项设计了工具栏按钮快捷方式，方便操作。7.为了实现保存功能，并且在打开保存过的文件后继续运行，需要将城市个数、最佳路线、迭代次数、最短距离及城市的坐标以及当前的环境信息素等进行保存。一．编程实现1.对于蚂蚁个体的行为，我们设计了一个CAnt类，它包括5个成员变量：prob[]：选择下一个城市的时候，保存各个城市被选中的概率值m_nCityCount：蚂蚁已经走过的城市数目AllowedCity[]：蚂蚁没有走过的城市，数组索引对应城市编号m_dLength：蚂蚁本次

7、迭代中走过的路径总长度tabu[]：记录走过的城市，数组索引表示走的顺序，里面存的是城市的编号，用来寻址最佳路径6个成员函数：intChooseNextCity()：选择下一个城市，返回该城市的编号voidAddCity(intcitynumber)：增加一个城市到走过的城市数组中voidMove()：移动到下一个城市voidMoveToLast()：最后一个城市的移动voidUpdateResult()：计算周游完城市后，走过的路径长度voidClear()：蚂蚁周游完各个城市后清空数据，为下次周游做准备2.设计一个CTravel类，主要包括4个成员函数

8、：voidInitMap()：初始化voidUpdateTrial