改进的蚁群算法在移动Agent路径选择中的应用研究

1、河北科技大学 2010 年研究生考试试卷学号：20081041 姓名：徐韩 学院：信息学院 专业及研究方向：通信与信息系统 网络管理技术 考试科目：智能优化算法及其应用 考试时间： 2010-5-20 学时及学分： 36 学时 2 学分 2010 年 6 月 3 日摘要移动Agent迁移过程中路径选择的一个经典的、代表问题旅行Agent问题(TAP)，是一个复杂的组合优化问题。蚁群算法(ant colony algorithm)作为一种新的生物进化算法，具有并行、正反馈和启发式搜索等特点，在求解该问题上具有一定的优势，但搜索时间长，易陷入局部最优是其突出缺点。本文结合现有的蚁群算法和移动Age

2、nt本身的特点，提出了基于任务权重和算法迭代次数来修改路径上信息素更新规则和信息素挥发系数这两种新方法，来更好的提高蚁群算法的求解性能。关键词：移动Agent，蚁群算法，任务权重一 移动Agent路径选择问题的概述近年来，随着人工智能和网络技术的飞速发展，国内外众多的研究学者对移动Agent技术的研究和发展也更加关注。移动Agent技术的迁移策略是该技术的基础技术核心，而移动Agent路径选择问题，正是移动Agent迁移策略的主要研究对象，所以求解移动Agent路径选择问题具有重要的意义。移动Agent的迁移策略，受到了学术界和工业界广泛的关注，并进行了大量探索和研究，取得了一定的成绩。旅行A

3、gent问题(TAP)是移动Agent路径选择问题中的一个经典例子。该问题是根据移动Agent的任务、网络的软硬件环境和其他约束条件为移动Agent规划出最佳的迁移路径。很多研究学者对该问题都进行了大量的研究和实验，提出了很多有效的方法和思想，如遗传算法，模拟退化算法等等，在该问题上取得的一定的效果。旅行Agent问题(TAP)是一个NP完全问题，其时间度、空间复杂度都高，这就要求求解该问题的方法一般需要具备自适应、自学习、分布式、并行化等特点。蚁群算法是意大利学者Dorigo等人在20世纪90年代，首先提出的一种基于种群的启发式仿生算法。该算法不仅仅具有以上特征，而且还具有正反馈、引入与问题

4、相关领域的知识等特点，所以蚁群算法求解该问题是非常合适。蚁群算法在求解该问题上具有很强的优势，但是随着问题规模的增大和一些不确定性因素的存在，它会表现出全局搜索能力不强，易于陷入局部最优等缺陷，因此，本文在基本蚁群算法的基础上，理解和掌握现有的其他改进思想和方法，提出了基于任务权重和算法迭代次数的自适应蚁群算法来求解该问题，对仿真实验结果进行了分析和比较。实验结果表明，本文两种改进方法使该算法的性能有了一定的提高。1.2蚁群算法蚁群算法的研究背景在当今社会中，随着人工智能(AI)和网络技术的飞速发展，科学技术与其他的多种学科相互交叉，相互渗透和融合，不仅给人们的生活、学习和工作等方面带了便利，

5、而且也从根本上改变了人类的生活和生产。与此同时，随着人类生活空间的不断扩大和对世界认识水平的不断提高，人们又对科学技术的发展提出了更高、更多的要求，期待着更多的研究学者对它进行不断的研究和提高，其中高效的优化技术和智能计算的要求也进一步的迫切需求。为了提高优化技术水平和智能计算的发展，近些年来有很多的研究学者，特别是在生物方面的研究专家和学者，通过对大自然中很多生物的生活现象和规律进行了大量的研究和探讨，提出了很多的群体智能算法。它们是一种基于生物信息系统的智能仿生算法，学者们是对社会性昆虫相互合作进行工作的研究，从生物进化和仿生学角度受到启发而提出的。众所周知，社会性昆虫如蜜蜂，蚂蚁等，虽然

6、其单个个体的力量很小，行为方式很简单、随机，但是它们却可以凭借集体的力量进行一些复杂的社会性活动，来更好的完成单个个体很难甚至不能完成的行为或活动，如它们可以通过社会分工等方式来更快的找到食物，共同的建造巢穴和防止外敌入侵等等。这种群体所表现出来的“智能”，就可以称之为群体智能5(Swarm Intelligence SI)。群体智能中的群体(Swarm)是指“一组相互之间可以进行间接通信(Stigmergy)的主体，这组主体能够合作进行分布式问题求解”。而所谓群体智能是指“无智能的主体通过合作表现出智能行为的特性”。群体智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解

7、决方案提供了基础。在很多专家和研究学者的共同努力下，有很多的群体智能算法得以提出并有了很好的发展和应用。虽然有些智能算法有了成熟的理论基础，但是把它们能够很好的应用到现实生活中还有一定的差距，需要我们共同的参与，进行不断的探索、尝试和研究。蚁群算法正是群体智能算法中的一个重要分支。在对一些生物昆虫，如蜜蜂、蚂蚁等进行大量的观察和研究后，生物学家发现了像蚂蚁这样弱小的昆虫，在觅食的时候，通过群体的力量，经过多次的探索和寻找，最终能够找得到一条从巢穴到食物源的最短路径。为了进一步的研究，生物学家就在蚂蚁寻找食物的路径上，设置一些障碍物来影响蚂蚁寻找路径，经过一段时间的搜寻，最终蚂蚁还是找到了从巢穴

8、到食物源的最短路径。经过各种实验，生物学家进一步的研究表明，蚂蚁在寻找食物的探索过程中，会在所经过的路径上释放一种挥发的化学物质，这种特殊的物质被称之为信息素(Pheromone)。信息素可以沉积在路径上，并随着时间逐步的挥发。当蚂蚁选择路径的时候，它们倾向于沿着信息素气味较浓的路径上前进。因此信息素可以引导蚂蚁来更快的，更有可能的找到离巢穴最近的食物。实验结果表明，正是这种特殊的物质，能够使蚂蚁找到从巢穴通向食物的最短路径。也可以说，当蚂蚁的巢穴和食物之间存在较多路径时，整个蚁群可以通过搜索各个个体蚂蚁留下的信息素的痕迹来找到往返于蚁穴和食物之间的最短的路径。蚁群算法的历史和科学意义蚁群算法

9、（ant colony algorithm）是由意大利学者M.Dorigo等在20世纪90年代初期研究蚂蚁寻找从巢穴到食物源的路径时，从生物进化的机制中受到启发，提出了一种新型的模拟进化算法。该算法具有稳健性（鲁棒性）、正反馈性和分布式计算等优点，在求解复杂的组合优化问题上有更强的优势，在分配问题、Job-shop调度等问题上，都有了较好的实验结果。在求解计算机算法中经典的“旅行商问题 (Traveling SalesmanProblem.TSP)”时，众多的研究学者根据算法基本原理，在算法中设计出了虚拟的“蚂蚁”来搜索不同的路线，还有虚拟的“信息素”，它会随着时间逐渐的消失。当每只蚂蚁每次随

10、机选择要走的路径，它们会尽可能的倾向于选择路径较短、信心素浓度较高的路径，根据“信息量较浓的路线更近”的原则，即可选择出最佳的路径。由于该算法利用了正反馈的机制，使得较短的路径能够有较大的机会得到选择，并且采用了概率算法，来选择下一步要走的路径，所以它能够不局限于局部最优解。虽然对蚁群算法的研究时间并不长，远不如像遗传算法，模拟退火等算法那样形成系统的分析方法和坚实的数学基础和理论基础，但是它的提出，能够为解决一些复杂的系统优化问题提供了一种新的，更好的求解算法，特别是在求解离散型组合优化的问题上，蚁群算法表现出了其他进化算法无法比拟的优越性。蚁群算法不仅具有鲁棒性、分布式计算、正反馈性、易于

11、和其他的智能算法相结合的特点，而且还能够智能搜索、全局优化等优势。该算法已经引起了众多专家和学者的注意，现在正被越来越多的研究者关注和探讨，算法的理论得到不断的完善，应用范围也普及到许多的科学技术及工程领域，是一种有良好发展前景的模拟进化算法。1.3移动Agent技术移动Agent的简介20世纪90年代初，由General Magic公司在推出系统TeleScript时提出了移动Agetn的概念。移动Agent是一个能在异构的网络中，自主的从一台主机迁移到另一台主机，并可与其他Agent或主机上的资源交互的实体，实际上它是分布式计算机技术与Agen技术的相互结合的产物。传统的服务器和RPC客户

12、之间的交互需要连续的通信，但是移动的Agent可以迁移到目标服务器上，与之本地进行高速通信，这种本地通信节省了网络资源。移动Agent迁移的内容包括其代码和运行的状态。运行的状态可分为数据和执行这两种状态：数据状态是指与移动Agent运行情况相关的数据堆内容；执行的状态是指移动Agent当前运行时的状态和情况。如运行栈内容、程序计数器等。移动Agent与远程执行不同，移动Agent可以能够不断的从一个网络主机迁移到另一个主机，能够根据自己的需要自主的进行移动。移动Agent也不同进程迁移，一般来说，进程迁移的系统不允许进程迁移到哪里和选择什么时候，而移动Agent可以带有状态，所以，移动Age

13、nt可以根据应用的需要随时可以移动到它想去的地方。移动Agent与Applet存在差异，Applet只能从服务器向客户端单方向的移动，然而移动Agent却可以在服务器和客户之间进行自由双向的移动。移动Agent还有很多的优点，移动Agent技术通过将服务请求Agent状态迁移到目标服务器端执行，所以Agent可以较少通过网络传输这一中间环节，而直接面对要访问的服务器资源，从而有效的避免了大量数据的网络传输，大幅度的降低了系统对网络带宽的依赖。移动Agent可以不需要统一调度，经过用户创建的Agent可以异步的在不同的结点上工作，等到任务完成后再将相应的结果传送给用户。为了完成某项复杂的任务，用

14、户可以创建多个Agent，同时在一个或若干个主机或服务器上运行，形成并行的求解能力。此外，它还有很好的自治性和智能路由等特性。gent的历史意义及应用Agent是人工智能领域中的一部分。简单的说，Agent是指模拟人类行为与关系、具有一定智能，并能够自主运行和提供相应服务的实体。Agent与现在流行的软件实体(如对象、构件)相比，粒度较大，自主性强，智能化较高。随着现代网络技术的发展，我们可以让Agent在网络中移动并执行，完成某些功能，把任务的结果带回来。这就是移动Agent(MobileAgent)的思想。Agent技术的诞生和发展是人工智能技术(AI)和网络技术发展的必然结果。随着人工智

15、能和计算机技术的发展以及万维网(WWW，World Wide Web)和互联网(Internet)的出现及发展，集中式的系统已经不能很好的适应科学技术的发展需要。针对这样的情况，分布式处理等技术(包括分布式人工智能)和并行计算应运而生，并在过去的20多年中飞速的发展。近10年来，Agent技术和多Agent系统与人工智能领域有着密切的关系，它们的研究成为分布式人工智能研究的一个热点。网络化和智能化的发展促进了Agent技术和多Agent系统的发展。Agent技术在不断的发展，同时可以应用到电子商务、智能决策、空袭目标模型系统和远程教育等方面，显示出Agent技术的优越性，能够更好的为我们提供便

16、利，具有很好的研究和发展前景。二 基本蚁群算法及其应用蚁群算法(ant colony algorithm)又称为人工蚁群算法，是受到真实蚂蚁行为研究的启发而提出来的，是一种模拟进化算法。该算法具有稳健性(鲁棒性)、正反馈性和分布式计算等优点，在求解复杂的组合优化问题上有其优势，该方法求解二次分配问题、TSP问题和作业调度等问题，取得了较好的成果。该算法已经显示出它在求解复杂优化问题，特别是离散优化问题方面的优势，是一种很有发展前景的智能计算方法。2.1蚁群算法的基本原理20世纪90年代初期，意大利学者M.Dorigo等人从生物进化和仿生学角度出发，研究蚂蚁寻找路径的自然行为，通过大量的观察和研

17、究，提出了蚁群算法20-22。为了更好的说明蚁群算法的基本原理，针对蚁群搜索食物的过程进行分析。像蜜蜂、飞蛾、蚂蚁等群居昆虫，尽管单个昆虫的行为很简单，但正是由这些简单的个体所组成的群体，却能表现出复杂的行为。蚂蚁这类群居的昆虫，尽管没有视觉，经过一段时间后，却能找到由蚁穴到食物源的最优路径，原因是什么呢？国内外的仿生学家经过大量细致的观察研究后发现，蚂蚁个体之间是通过一种称之为信息素(pheromone)的特殊物质进行信息传递和交流。在搜索较好路径的过程中，蚂蚁能够在它所经过的路径上留下该物质，而且其他蚂蚁在运动过程中能够感知这种物质，并以此确定自己的运动方向。所以，这些大量的蚂蚁组成的蚁群

18、集体的行为便表现出一种信息正反馈的现象：某一条路径上走过的蚂蚁越多，后来蚂蚁选择该路径的概率就越大。蚂蚁个体之间就是通过这种特殊物质进行信息的交流，达到搜索食物的目的。本文用比较形象化的图示，来说明蚂蚁群体的路径搜索原理和机制。下面用M.Dorigo所举的例子来说明蚁群系统的原理。如图2-1所示，蚁群系统的初始状态。设A是蚂蚁的巢穴，E是食物源，H、C是两个绕过障碍物的节点。由于障碍物的存在，蚂蚁只能绕过C或H由E到达A，或由A到达E。各节点之间的距离如图所示。设每个时间单位，有30只蚂蚁由E到达D点和有30只蚂蚁由A到达B，蚂蚁在经过的路径上留下的外激素为1。设外激素的停留时间为1。图2-1

19、蚁群系统的初始状态图2-2蚁群系统的t=0时刻的状态如图2-2所示，蚁群系统在开始时刻的状态。由于路径DH，DC，BH,BC信息存在，位于D和B的蚂蚁可以随机选择路径。从统计学的角度考虑，可以认为它们以相同的概率选择DH，DC，BH,BC。经过一段时间后，路径BCD和BHD上蚂蚁数目的差距越来越大，直至大多数蚂蚁选择较短的路径BCD。图2-3蚁群系统t=1时刻的状态如图2-3所示，蚁群系统在t=1时刻的状态。此时将有20只蚂蚁由D和B到达C，有10只蚂蚁由D和B到达H。经过一段时间，大量的蚂蚁将会以越来越大的概率选择路径BCD，最终完全选择路径BCD，从而找到由蚁巢到食物源的最短的路径。由此可

20、见，蚂蚁个体之间的信息交换是一个正反馈机制的过程。在相同的时间和区域内，较短的路径就会有更大的机率被选择。蚁群算法是一种随机搜索，智能的仿生算法，与其他的进化算法一样，通过群体的候选解进行进化，来筛选出全局最优解，此过程包括两个阶段：适应阶段与协调阶段。在适应阶段中，各候选解就会根据积累的信息不断的调整自身的结构；在第二阶段，候选解之间通过信息素的交流，希望产生性能更好的解。蚁群算法作为一种通用型优化方法，与遗传算法一样，不需要任何先验知识，开始只是随机的选择搜索路径，经过一段时间对算法解的空间的“了解”，搜索变得的有规律，并发挥其正反馈的性能，直至最终取得全局最优解。蚁群算法对搜索空间的“了

21、解”机制主要包括以下几方面：(1).蚂蚁的记忆。一只蚂蚁搜索过的路径，当下次搜索时就不会再被选择，由此可以在蚁群算法中建立tabu(禁忌）列表来存储已经访问的节点，进行模拟。(2).蚂蚁利用信息素(pheromone)进行相互通信。蚂蚁在选择的路径上会释放一种叫做信息素的物质，当它们的同伙在进行路径选择的时候，会根据留在路径上的信息素进行选择，这时信息素就成为蚂蚁之间进行通信的媒介。(3).蚂蚁的集群活动。一只蚂蚁的运动很难到达食物源，但是通过整个蚁群进行搜索就完全不同。当某些路径上经过的蚂蚁越来越多的时候，在这些路径上留下的信息素也就越来越多，导致信息素强度增大，所以，该路径被选择的概率随之

22、增大，从而进一步增大该路径的信息素强度，而当其他某些路径上通过的蚂蚁较少时，路径上的信息素就会随时间推移而蒸发。因此，模拟这种现象可利用群体的智能来建立路径选择机制，使蚁群算法的搜索朝向最优解进化。蚁群算法所利用的搜索机制呈现出一种正反馈或自催化特征，可将蚁群算法模型理解成增强型学习系统。步骤：nc0；(nc为迭代步数)对各和进行初始化；将m只蚂蚁随机的置于n个顶点上；步骤：将各个蚂蚁的初始节点置于当前解集中；对每只蚂蚁k(k=1,2,.m)，按概率转移至下一个顶点j；将顶点j置于当前解集；步骤：计算各蚂蚁的目标函数 (k1,2,.m)k=；记录当前的最好的全局最优解；步骤：按相应的更新方程修

23、改轨迹上的信息素强度；步骤：对各边(i,j)，置，ncnc+1；步骤：若nc小于预定的迭代次数，并且没有退化行为(即找到的都是相同的解)则转到步骤；步骤：输出目前最好的解。2.3蚁群算法的研究现状蚁群算法的优点蚁群算法的主要的优点概括如下。(1).蚁群算法是一种结合了贪婪搜索算法、正反馈机制和分布式计算，具有很好的搜索较优解能力。贪婪式搜索有助于在搜索过程中早期找出可接受的解决方案，缩短了搜索时间，正反馈能够快速的发现较优解，分布式计算避免了早熟收敛。(2).蚁群算法具有很强的并行性和鲁棒性，对基本的蚁群算法模型稍加修改，便可应用于其他问题。如车辆路径问题、多任务目标分配、数据挖掘等问题。(3

24、).可以不通过个体之间直接通信，而是有效的通过信息素进行合作，这样的系统具有较好的扩充性。由此，随着系统中个体增加，系统开销将非常小。(4).易于与其他的算法结合，蚁群算法很容易与人工免疫算法、遗传算法等算法结合，以改善算法的性能。蚁群算法的几个缺陷尽管蚁群算法具有很强的全局寻优能力，在很多的领域中得到了广泛的应用，但也存在一些缺点。(1).一般情况下，该算法需要较长的搜索时间。蚁群中各个个体的运动是随机的，尽管通过信息素交换能够朝向最优路径方向进化，但是当群体规模较大时，很难在较短的时间内，从大量杂乱无章的路径中，找出一条较好的路径。这是因为在进化的初级阶段，各条路径上的信息素的差别小。通过

25、信息正反馈机制，使得较好路径上的信息量逐渐增大，经过较长的一段时间，才使那些较好路径上的信息量明显高于其他路径上的信息量，随着这一过程的进行，差别越来越明显，从而最终收敛于比较好的路径。(2).该算法容易出现停滞现象(stagnation behavior)，即搜索进行到一定的程度后，所有的个体发现的解完全一致，不能对解的空间进一步进行搜索，不利于发现更好的解。对于这些问题，已经引起了许多研究学者的注意，并提出了很多改进算法，比如，智能蚁群算法39-40，基于多样信息素的蚁群算法等几种典型的改进算法。2.4蚁群算法的应用随着众多的研究学者对蚁群算法原理的探讨以及对该算法的改进，蚁群算法的应用也

26、不断的深入到其他的新领域中。(1).车辆调度车辆调度问题是一类复杂的组合优化问题，是近年来物流控制优化中的一个研究热点。该问题可描述为：现已知客户的位置坐标和货物需求量，一个车队(有多个车辆)从一个配送中心出发，每个需求点只被一辆车访问，且该车所访问需求点的总需求量不能超过该车辆的负载能力，应如何安排车辆行走路线使得总路线最短。要求每辆车运输完毕后回到出发点(供应点)。目前，除了一些经典的智能算法以外，采用TSP风格的蚁群算法同样可以求解VRP，求解时可以将车辆模拟成蚂蚁。现在，国内外很多得研究学者，在蚁群算法求解VRP方面的研究也取的了不少成果，但是模拟效果跟现实生活中VRP问题的解决还有一定差距。所以，为了更好的解决该问题，对蚁群算法的研究还有待于进一步的深入。(2).网络路由通信问题蚁群算法M.Dorigo于1992年提出的一种组合优化方法，被广泛应用于求解组合优化问题，特别是NP-完全问题。蚁群算法已在通信网络方面中得到了很好的应用和发展。11随着网络技术的发展和多媒体业务的兴起，对网络服务质量提出了更高的要求，Qo