基于蚁群算法的TSP问题.doc

基于蚁群算法的TSP问题求解 1引言 1.1 问题描述 设计求解以下两个TSP问题的蚁群优化（ACO）算法。其中城市的坐标见附件（kroA100.tsp和kroB100.tsp）。 1.2 理论基础 1.2.1 蚁群算法简介 蚁群算法是由意大利学者M.Dorigo等人于20世纪90年代初提出的一种新的模拟进化算法，其真实地模拟了自然界蚂蚁群体的觅食行为。M.Dorigo等人将其用于解决旅行商问题（traveling salesman problem, TSP），并取得了较好的实验结果。 近年来，许多专家学者致力于蚁群算法的研究，并将其应用于交通、通信、化工、电力等领域，成功解决了许多组合优化问题，如调度问题（job–shop scheduling problem）、指派问题（quadratic assignment problem）、旅行商问题（traveling salesman problem）等。 1.2.2 蚁群算法基本思想 生物学家研究发现，自然界中的蚂蚁觅食是一种群体性行为，并非单只蚂蚁自行寻找食物源。蚂蚁在寻找食物源时，会在其经过的路径上释放一种信息素，并能够感知其它蚂蚁释放的信息素。信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。通常，蚂蚁会以较大的概率优先选择信息素浓度较高的路径，并释放一定量的信息素，以增强该条路径上的信息素浓度，这样会形成一个正反馈。最终，蚂蚁能够找到一条从巢穴到食物源的最佳路径，即是最短距离。值得一提的是，生物学家同时发现，路径上的信息素浓度会随着时间的推进而逐渐衰减。 将蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。较短的路径上蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上积累的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。 1.2.3 蚁群算法解决TSP问题的基本原理 为不失一般性，设整个蚂蚁群体中蚂蚁的数量为，城市的数量为，城市与城市之间的距离为，时刻城市与城市连接路径上的信息素浓度为。初始时刻，各个城市连接路径上的信息素浓度相同，不妨设为。 蚂蚁根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设表示时刻蚂蚁从城市的概率，其计算公式为： （1-1） 其中为启发函数，，表示蚂蚁从城市转移到城市的期望程度；为蚂蚁待访问城市的集合，开始时，中有个元素，即包括除了蚂蚁出发城市的其它所有城市，随着时间的推进，中的元素不断减少，直至为空，即表示所有的城市均访问完毕；为信息素重要程度因子，其值越大，表示信息素的浓度在转移中起的作用越大；为启发函数重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁会以较大的概率转移到距离短的城市。 如前文所述，在蚂蚁释放信息素的同时，各个城市间连接路径上的信息素逐渐消失，设参数表示信息素的挥发程度。因此，当所有蚂蚁完成一次循环后，各个城市间连接路径上的信息素浓度需进行实时更新，即： （1-2） 其中，表示第只蚂蚁在城市与城市连接路径上释放的信息素浓度；表示所有蚂蚁在城市与城市连接路径上释放的信息素浓度之和。 针对蚂蚁释放信息素问题，M.Dorigo等人曾给出了种不同的模型，分别称之为nt cycle system，Ant quantity system和nt density system，其计算公式 Ant cycle system模型 A的计算公式为： （1-3） 其中，为常数，表示蚂蚁循环一次所释放的信息素总量；为第只蚂蚁经过路径的长度。 Ant quantity system模型 Ant quantity system的计算公式为： （1-4） Ant density system模型 Ant density system模型的计算公式为： （1-5） 上述3种模型中，nt cycle system模型利用蚂蚁经过路径的整体信息（经过路径的总长）计算释放的信息素浓度；nt quantity system模型则利用蚂蚁经过路径的局部信息（经过各个城市间的距离）计算释放的信息素浓度；而nt density system模型则更为简单地将信息素释放的浓度取为恒值，并没有考虑不同蚂蚁经过路径长短的影响。因此，一般选用nt cycle sy