《蚁群算法在TSP问题中的参数设定》由会员分享，可在线阅读，更多相关《蚁群算法在TSP问题中的参数设定（4页珍藏版）》请在装配图网上搜索。
1、蚁群算法在TSP问题中的参数设定ParametersSettingofAntColonyAlgorithminTSPProblemHUQing-wan,LIUYong-cai,DIANJun-bao,WUShang(DepartmentofMathematicsandInformationScience,QujingNormalUniversity,Qujing655011,China):Antcolonyalgorithmisanovelsimulatedevolutionaryalgorithmtosolvediscreteoptimizationproblemswithgoodperfo
2、rmance.Thisarticledescribesthebasicidea,theparametersandimplementationofACOalgorithm.AbouttheseveralnumbersofcitiesintheTSPproblem,givesidealparametersoftheantcolonyalgorithmforexperimentalanalysis,theresultscanbesettosimilartothesizeofdiscreteoptimizationproblems.20世纪90年代意大利学者MDorigo等从生物进化的机制中受到启发，
3、通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法蚁群算法(AntColonyOptimization，ACO。用该方法求解TSP问题、分配问题，取得了较好的试验结果。研究显示，蚁群算法在求解复杂优化问题(特别是离散优化问题)方面有一定优势，表明它是一种有发展前景的算法。其中蚁群算法中参数的设置直接影响到算法的性能，对参数设置的研究越来越重要，但是目前对它的研究大多还处于实验分析阶段。1 蚁群算法基本原理蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁能够感知
4、这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下真实蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低。后来的蚂蚁再次碰到这个路口的时候。选择激素浓度较高路径概率就会相对较大。最优路径上的激索浓度越来越大。而其它的路径上激素浓度却会随着
5、时间的流逝而消减。最终整个蚁群会找出最优路径。人工蚁群中把具有简单功能的工作单元看作蚂蚁。它与真实蚂蚁相似之处在于都是优先选择信息素浓度大的路径。人工蚂蚁除了保留真实蚂蚁最重要的特点，还给予人工蚂蚁一种有限形式的记忆存储能力，使得它们可以同时把目前为止所经过的部分路径和已经遍历过的连接上的成本值都储存起来。通过使用记忆存储，蚂蚁可以更高效地构建最小成本路径问题的解。这些行为包括：由信息素导向的概率型解的构造，其中不具有正向信息素更新；带有环路消除和信息素更新的确定性路径返回过程；对生成的解的质量进行评估。此外，把信息素蒸发也考虑到算法中。蚁群优化(antcolonyoptimization,A
6、CO对一种针对难解的离散优化问题的元启发式算法，它利用一群人工蚂蚁的协作来寻找好的解。通俗地说，ACOI法可以想象为三个过程的相互作用：蚂蚁构建解(ConstructAntSolutions)、更新信息素(UpdatePheromones)和后台执行(DaemonActions)。蚂蚁构建解(ConstructAntSolutions)通过使蚂蚁移动到相应构建图上的邻近点，从而使一群蚂蚁并行异步地访问所考虑问题的邻近状态。蚂蚁根据信息素和启发式信息，采用一个随机局部决策方法选择移动的下一步。这样，蚂蚁就可以逐步建立起优化问题的解。一旦蚂蚁建立了一个解，或者是在构建解的期间，蚂蚁将对解进行评估，
7、以便在UpdatePheromones过程使用该解来决定应释放信息素的多少。更新信息素(UpdatePheromones)就是修改信息素浓度的过程。信息素的浓度可能会因蚂蚁在点或连接的边上释放信息素而增加，也可能会由于信息素的蒸发而减少。从实际的角度看，释放新的信息素增加了蚂蚁访问某个点或者某条连接边的概率。信息素的蒸发所起到的遗忘作用是很有用的：它可以避免算法朝着一个并非最佳的解区域过早收敛，从而使得算法有更多的机会探索搜索空间中的新区域。后台执行(DaemonActions)的过程就是执行单一蚂蚁不能完成的集中行动，后台执行包含局部优化过程的执行和全局信息的收集，在非局部的情况下，这个全局
8、信息可以用于决定是否释放某些额外的信息素来调整搜索过程。2 旅行商问题中的蚁群优化算法直观的说，旅行商问题(TravelingSalemanProblem，TSP)就是商人，商人从自己所在的城市出发，希望找到一条既能经过给定顾客所在城市，又能在回家前遍历每一个城市一次的最短路径问题。TSP问题可以用一个带权完全图G=(N,A)来表示，其中N是城市的结点集合，A是所有边的集合。每一条边(i,j)GA都带有一个权值dij,它代表城市i与j之间的距离，其中i,jTSP问题就是要找到图中的最短哈密尔顿回路。一个TSP实例的解可以用城市序号的一个排列来表示。ACCM法可以直接应用到TSP中，它的构建图为G=(C,L),其中，结点集C的成分被边集L完全相连，构建图与描述TSP实例的图形一致，也就是说，C=NlfiL=A;问题的状态集合与所有可能的部分路径集合相对应；约束条件Q要求蚂蚁建立的路径必须是与城市标号的排列相对应的可行路径。这种约束通常是可以达到的，因为构建图是一个完全图，并且任意一条访问了所有结点而且不重复访问任何结点的闭合路径恰好就对应着一条可行路径。
蚁群算法在TSP问题中的参数设定
