《蚁群算法应用.docxVIP

大连理工大学研究生必修课作业课程名称：现代物流管理研究生姓名：徐静学号 作业成绩：任课教师(签名)交作业日时间： 2016 年6 月1日蚁群算法在TSP问题上的应用摘要蚁群算法是受现实蚂蚁群体行为启发而得出的一类仿生算法。本文以解决TSP问题为基础,系统地介绍了蚁群算法从诞生到成熟过程中几个代表性的算法。在阐述算法基本思想的前提下，着重论述算法的创新之处。关键词蚁群算法，TSP问题，蚁群优化1引言蚁群算法也称作蚁群优化(Ant Colony Optimization，ACO)，最早是由Dorigo及其研究同伴所提出，用于求解诸如旅行商问题之类的组合优化问题。自然界蚂蚁在其经过的路径上会留下某种生物信息物质(信息素)，该物质会吸引蚁群中的其它成员再次选择该段路径；食物与巢穴之前较短的路径容易积累较多的信息素，因而使得更多的蚂蚁选择走该段路径，最终几乎所有的蚂蚁都集中在最短路径上完成食物的搬运。Dorigo等从此现象中抽象出路径选择和信息素积累的数学模型，作为蚁群算法的核心，并通过对蚂蚁寻找最短路径的计算机模拟，实现了对TSP问题的求解。自此，蚁群算法越来越多地被用于求解其它的组合优化问题，也被推广到工业工程上应用。蚁群算法特点是并发性、鲁棒性、正反馈性等。在蚁群算法求解问题的过程中，利用蚁群在问题空间中同时构造问题的多个解体现了算法的并发性。蚁群不会因为单个蚂蚁寻找到较差的解或者因为问题空间发生改变而使得算法丧失作用，这体现了算法的鲁棒性。在蚂蚁构造问题解的过程中，以蚁群觅食行为为例，会在经过的解路径上释放信息素，而解空间中获得信息素越多的路径，对蚂蚁的吸引力就越大，使更多的蚂蚁经过该路径并进一步在上面释放信息素，这体现了算法的正反馈性。TSP问题代表一类组合优化问题，在实际工程中有许多应用，如计算机联网、电子地图、交通诱导、电气布线、VLSI单元布局、ATM分组交换网等。鉴于其重要的工程与理论价值，TSP常作为算法性能研究的典型算例。求其最优解的代价是指数级的，因此对其近似解的研究一直是算法设计的一个重要课题。TSP问题是典型的NP完全问题，许多算验证法及算法效率测试都以TSP问题为基础。在蚁群算法研究中，第一个蚁群算法，蚂蚁系统,就是在TSP问题的基础上提出来的。而后，依据TSP问题，又提出了蚁群算法系列中具有代表性的蚁群系统、最大——最小蚂蚁系统。本文以TSP问题为基础,对蚁群算法的基本问题及典型的蚁群算法进行了综述。涉及到算法的基本问题、算法描述、算法改进及意义。通过研究总结了蚁群算法的发展历程和实现思想。2蚁群行为和TSP问题2.1蚁群行为蚁群的行为是整体协作，相互分工，以一个整体去解决一些对单个蚂蚁看上去是不可能完成的任务。就目前来讲，蚁群至少有三个方面的行为特征对算法研究有很好的启发意义，分别是觅食行为、任务分配、死蚁堆积阁。蚁群的觅食行为指蚂蚁从巢穴出发寻找食物并且将食物搬回巢穴的行为，当蚂蚁出外寻找食物时，会在自己走过的路径上释放一种称为信息素的物质，后续的蚂蚁一般更愿意走那些信息素强度更高的路径。这样，较短路径上单位时间内通过的蚂蚁数目较多，留下的信息素也较多（浓度更高），对妈蚁产生了更强的吸引，使得更多的蚂蚁走较短的路径。这就形成了一个正反馈机制，使得最终所有的蚂蚁都走蚁穴到食物源的最短路径。蚁群的任务分配指蚁群内部能根据所需要完成的任务合理分配蚂蚁数t。研究表明，从事不同任务的蚂蚁之间的比例是会变动的，也就是说从事任务A的蚂蚁可能会根据需要而从事任务B。在基于这种蚁群行为的模型中，规定了每只妈蚁的反应阈值，同时每一个任务都有一个相关的激励（task-related stimuli）。反应阈值与激励间的关系是：当某个任务的激励数值比蚂蚁的反映阈值大，那么这只蚂蚁就会加人到该任务执行者的行列中。蚁群中，如果一群蚂蚁在执行某任务时出现执行滞后情况，那么该任务的激励数值就会变大，直到其数值大于某些未执行该任务的蚂蚁的反映阈值，从而吸引更多的蚂蚁来完成该任务，由此实现了任务的自动分配。死蚁堆积与蚁穴清理行为：在蚁群的巢穴中，工蚁会对死蚂蚁进行搬运，使得那些死蚂蚁堆积到一起。在这一堆积行为中，死蚁堆越大对工蚁的吸引力越大，使得更多的死蚂蚁被堆积到该蚁堆中，这样同样也形成了一个正反馈现象。但是，并不是说所有的死妈蚁都会堆积到一起，而是最终会形成几个规模较大的蚁堆。研究者对蚁群的这3种行为特征进行了深入的研究，并应用于最短路径优化、任务分配调度以及数据聚类等问题领域，得到了效率较高的许多启发式算法。2.2TSP问题TSP问题是给定一个城市的集合以及城市之间的旅行代价,寻找经过每个城市一次且仅一次而最终回到起始城市旅行代价最小的路径。如果构造一个图如下：图中的顶点为城市，顶点间的边表示城市间