动态蚁群算法求解TSP问题
摘要蚂蚁群体能完成单个蚂蚁所无法完成的工作。它们通过称为信息素的物质交流信息而协同工作。蚂蚁在觅食活动中，在食物与巢穴之间的路径上留下信息素，较短路径信息素相对较浓，而蚂蚁倾向于沿信息素较浓的路径往返于巢穴与食物之间。经过一段时间后，就可发现从巢穴到食物的较短的路径。基于此原理，Marco Dorigo提出了蚁群算法，并首先用于求解TSP问题。该文从更多方面模仿真实自然界中蚂蚁的行为，更为合理地制定信息素动态挥发规则，提出动态蚁群算法并用于解决TSP问题，实验表明了该算法有较好的性能。
关键词蚁群算法旅行商问题组合优化
l 引言
蚂蚁系统是模仿蚁群的行为构建的人工系统。在自然界中蚂蚁几乎是瞎子，却能发现食物与蚁穴之间最短的距离。生态学家的研究表明，蚂蚁是借助信息素(pheromone)来实现这一点的。信息素是蚂蚁分泌的一种化学物质，蚂蚁在寻找食物过程中会分泌这种物质。蚁群在寻找食物时，会有一些蚂蚁四处游荡， 当蚂蚁发现食物并返回巢穴过程中会在途中留下信息素。如果假定所有蚂蚁以相同的速度前进的话，则第一只返回巢穴的蚂蚁发现的路径是当前所有蚂蚁发现的路径中最好的。较短路径上信息素会比较浓一些，而较浓的信息素能吸引更多的蚂蚁走这条路径，从而发现比较好的路径。图1说明了蚂蚁如何发现最短路径的基本原理。图l中两只蚂蚁在同时离开蚁，分别走不同的路径并在各自的路径留下信息素。走较短路径(下面)的蚂蚁会首先返回巢穴。这条路径由于留下比较多的信息素，它会吸引其它蚂蚁走这条路线。这种强化过程使蚁群发现最短路径。基于这种原理，MarcoDorgio等人提出了称为蚂蚁算法一种新的启发式算法。蚁群算法已成功应用于求解TSP问题、调度问题 着色问题。并在大规模集成电路设计，电信路由控制方面表现出较好的性能。蚁群算法是模拟蚂蚁的行为而提出一种启发式算法，该文从更多方面模拟蚁群行为提出了一种改进的蚁群算法，该文称其为动态蚁群算法，并用于求解TSP问题(Traveling SalesmanProblem)。TSP问题，即旅行商问题，是一类已被证明具有NPC计算复杂性的组合优化难题，它的提法是：给定N个城市，
有......
想了解全部内容，请下载附件查看
