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

河北科技大学2010年研究生考试试卷学号：20081041姓名：徐韩学院：信息学院专业及研究方向：通信与信息系统网络管理技术考试科目：智能优化算法及其应用考试时间：2010-5-20学时及学分：36学时2学分2010年6月3日摘要移动Agent迁移过程中路径选择的一个经典的、代表问题——旅行Agent问题(TAP)，是一个复杂的组合优化问题。蚁群算法(antcolonyalgorithm)作为一种新的生物进化算法，具有并行、正反馈和启发式搜索等特点，在求解该问题上具有一定的优势，但搜索时间长，易陷入局部最优是其突出缺点。本文结合现有的蚁群算法和移动Agent本身的特点，提出了基于任务权重和算法迭代次数来修改路径上信息素更新规则和信息素挥发系数ρ这两种新方法，来更好的提高蚁群算法的求解性能。关键词：移动Agent，蚁群算法，任务权重一移动Agent路径选择问题的概述近年来，随着人工智能和网络技术的飞速发展，国内外众多的研究学者对移动Agent技术的研究和发展也更加关注。移动Agent技术的迁移策略是该技术的基础技术核心，而移动Agent路径选择问题，正是移动Agent迁移策略的主要研究对象，所以求解移动Agent路径选择问题具有重要的意义。移动Agent的迁移策略，受到了学术界和工业界广泛的关注，并进行了大量探索和研究，取得了一定的成绩。旅行Agent问题(TAP)是移动Agent路径选择问题中的一个经典例子。该问题是根据移动Agent的任务、网络的软硬件环境和其他约束条件为移动Agent规划出最佳的迁移路径。很多研究学者对该问题都进行了大量的研究和实验，提出了很多有效的方法和思想，如遗传算法，模拟退化算法等等，在该问题上取得的一定的效果。旅行Agent问题(TAP)是一个NP完全问题，其时间度、空间复杂度都高，这就要求求解该问题的方法一般需要具备自适应、自学习、分布式、并行化等特点。蚁群算法是意大利学者Dorigo等人在20世纪90年代，首先提出的一种基于种群的启发式仿生算法。该算法不仅仅具有以上特征，而且还具有正反馈、引入与问题相关领域的知识等特点，所以蚁群算法求解该问题是非常合适。蚁群算法在求解该问题上具有很强的优势，但是随着问题规模的增大和一些不确定性因素的存在，它会表现出全局搜索能力不强，易于陷入局部最优等缺陷，因此，本文在基本蚁群算法的基础上，理解和掌握现有的其他改进思想和方法，提出了基于任务权重和算法迭代次数的自适应蚁群算法来求解该问题，对仿真实验结果进行了分析和比较。实验结果表明，本文两种改进方法使该算法的性能有了一定的提高。1.2蚁群算法1.2.1蚁群算法的研究背景在当今社会中，随着人工智能(AI)和网络技术的飞速发展，科学技术与其他的多种学科相互交叉，相互渗透和融合，不仅给人们的生活、学习和工作等方面带了便利，而且也从根本上改变了人类的生活和生产。与此同时，随着人类生活空间的不断扩大和对世界认识水平的不断提高，人们又对科学技术的发展提出了更高、更多的要求，期待着更多的研究学者对它进行不断的研究和提高，其中高效的优化技术和智能计算的要求也进一步的迫切需求。为了提高优化技术水平和智能计算的发展，近些年来有很多的研究学者，特别是在生物方面的研究专家和学者，通过对大自然中很多生物的生活现象和规律进行了大量的研究和探讨，提出了很多的群体智能算法。它们是一种基于生物信息系统的智能仿生算法，学者们是对社会性昆虫相互合作进行工作的研究，从生物进化和仿生学角度受到启发而提出的。众所周知，社会性昆虫如蜜蜂，蚂蚁等，虽然其单个个体的力量很小，行为方式很简单、随机，但是它们却可以凭借集体的力量进行一些复杂的社会性活动，来更好的完成单个个体很难甚至不能完成的行为或活动，如它们可以通过社会分工等方式来更快的找到食物，共同的建造巢穴和防止外敌入侵等等。这种群体所表现出来的“智能”，就可以称之为群体智能[5](SwarmIntelligenceSI)。群体智能中的群体(Swarm)是指“一组相互之间可以进行间接通信(Stigmergy)的主体，这组主体能够合作进行分布式问题求解”。而所谓群体智能是指“无智能的主体通过合作表现出智能行为的特性”。群体智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。在很多专家和研究学者的共同努力下，有很多的群体智能算法得以提出并有了很好的发展和应用。虽然有些智能算法有了成熟的理论基础，但是把它们能够很好的应用到现实生活中还有一定的差距，需要我们共同的参与，进行不断的探索、尝试和研究。蚁群算法正是群体智能算法中的一个重要分支。在对一些生物昆虫，如蜜蜂、蚂蚁等进行大量的观察和研究后，生物学家发现了像蚂蚁这样弱小的昆虫，在觅食的时候，通过群体的力量，经过多次的探索和寻找，最终能够找得到一条从巢穴到食物源的最短路径。为了进一步的研究，生物学家就在蚂蚁寻找食物的路径上，设置一些障碍物来影响蚂蚁寻找路径，经过一段时间的搜寻，最终蚂蚁还是找到了从巢穴到食物源的最短路径。经过各种实验，生物学家进一步的研究表明，蚂蚁在寻找食物的探索过程中，会在所经过的路径上释放一种挥发的化学物质，这种特殊的物质被称之为信息素(Pheromone)。信息素可以沉积在路径上，并随着时间逐步的挥发。当蚂蚁选择路径的时候，它们倾向于沿着信息素气味较浓的路径上前进。因此信息素可以引导蚂蚁来更快的，更有可能的找到离巢穴最近的食物。实验结果表明，正是这种特殊的物质，能够使蚂蚁找到从巢穴通向食物的最短路径。也可以说，当蚂蚁的巢穴和食物之间存在较多路径时，整个蚁群可以通过搜索各个个体蚂蚁留下的信息素的痕迹来找到往返于蚁穴和食物之间的最短的路径。1.2.2蚁群算法的历史和科学意义蚁群算法（antcolonyalgorithm）是由意大利学者M.Dorigo等在20世纪90年代初期研究蚂蚁寻找从巢穴到食物源的路径时，从生物进化的机制中受到启发，提出了一种新型的模拟进化算法。该算法具有稳健性（鲁棒性）、正反馈性和分布式计算等优点，在求解复杂的组合优化问题上有更强的优势，在分配问题、Job-shop调度等问题上，都有了较好的实验结果。在求解计算机算法中经典的“旅行商问题(TravelingSalesmanProblem.TSP)”时，众多的研究学者根据算法基本原理，在算法中设计出了虚拟的“蚂蚁”来搜索不同的路线，还有虚拟的“信息素”，它会随着时间逐渐的消失。当每只蚂蚁每次随机选择要走的路径，它们会尽可能的倾向于选择路径较短、信心素浓度较高的路径，根据“信息量较浓的路线更近”的原则，即可选择出最佳的路径。由于该算法利用了正反馈的机制，使得较短的路径能够有较大的机会得到选择，并且采用了概率算法，来选择下一步要走的路径，所以它能够不局限于局部最优解。虽然对蚁群算法的研究时间并不长，远不如像遗传算法，模拟退火等算法那样形成系统的分析方法和坚实的数学基础和理论基础，但是它的提出，能够为解决一些复杂的系统优化问题提供了一种新的，更好的求解算法，特别是在求解离散型组合优化的问题上，蚁群算法表现出了其他进化算法无法比拟的优越性。蚁群算法不仅具有鲁棒性、分布式计算、正反馈性、易于和其他的智能算法相结合的特点，而且还能够智能搜索、全局优化等优势。该算法已经引起了众多专家和学者的注意，现在正被越来越多的研究者关注和探讨，算法的理论得到不断的完善，应用范围也普及到许多的科学技术及工程领域，是一种有良好发展前景的模拟进化算法。1.3移动Agent技术1.3.1移动Agent的简介20世纪90年代初，由GeneralMagic公司在推出系统TeleScript时提出了移动Agetn的概念。移动Agent是一个能在异构的网络中，自主的从一台主机迁移到另一台主机，并可与其他Agent或主机上的资源交互的实体，实际上它是分布式计算机技术与Agen技术的相互结合的产物。传统的服务器和RPC客户之间的交互需要连续的通信，但是移动的Agent可以迁移到目标服务器上，与之本地进行高速通信，这种本地通信节省了网络资源。移动Agent迁移的内容包括其代码和运行的状态。运行的状态可分为数据和执行这两种状态：数据状态是指与移动Agent运行情况相关的数据堆内容；执行的状态是指移动Agent当前运行时的状态和情况。如运行栈内容、程序计数器等。移动Agent与远程执行不同，移动Agent可以能够不断的从一个网络主机迁移到另一个主机，能够根据自己的需要自主的进行移动。移动Agent也不同进程迁移，一般来说，进程迁移的系统不允许进程迁移到哪里和选择什么时候，而移动Agent可以带有状态，所以，移动Agent可以根据应用的需要随时可以移动到它想去的地方。移动Agent与Applet存在差异，Applet只能从服务器向客户端单方向的移动，然而移动Agent却可以在服务器和客户之间进行自由双向的移动。移动Agent还有很多的优点，移动Agent技术通过将服务请求Agent状态迁移到目标服务器端执行，所以Agent可以较少通过网络传输这一中间环节，而直接面对要访问的服务器资源，从而有效的避免了大量数据的网络传输，大幅度的降低了系统对网络带宽的依赖。移动Agent可以不需要统一调度，经过用户创建的Agent可以异步的在不同的结点上工作，等到任务完成后再将相应的结果传送给用户。为了完成某项复杂的任务，用户可以创建多个Agent，同时在一个或若干个主机或服务器上运行，形成并行的求解能力。此外，它还有很好的自治性和智能路由等特性。1.3.2Agent的历史意义及应用Agent是人工智能领域中的一部分。简单的说，Agent是指模拟人类行为与关系、具有一定智能，并能够自主运行和提供相应服务的实体。Agent与现在流行的软件实体(如对象、构件)相比，粒度较大，自主性强，智能化较高。随着现代网络技术的发展，我们可以让Agent在网络中移动并执行，完成某些功能，把任务的结果带回来。这就是移动Agent(MobileAgent)的思想。Agent技术的诞生和发展是人工智能技术(AI)和网络技术发展的必然结果。随着人工智能和计算机技术的发展以及万维网(，WorldWideWeb)和互联网(Internet)的出现及发展，集中式的系统已经不能很好的适应科学技术的发展需要。针对这样的情况，分布式处理等技术(包括分布式人工智能)和并行计算应运而生，并在过去的20多年中飞速的发展。近10年来，Agent技术和多Agent系统与人工智能领域有着密切的关系，它们的研究成为分布式人工智能研究的一个热点。网络化和智能化的发展促进了Agent技术和多Agent系统的发展。Agent技术在不断的发展，同时可以应用到电子商务、智能决策、空袭目标模型系统和远程教育等方面，显示出Agent技术的优越性，能够更好的为我们提供便利，具有很好的研究和发展前景。二基本蚁群算法及其应用蚁群算法(antcolonyalgorithm)又称为人工蚁群算法，是受到真实蚂蚁行为研究的启发而提出来的，是一种模拟进化算法。该算法具有稳健性(鲁棒性)、正反馈性和分布式计算等优点，在求解复杂的组合优化问题上有其优势，该方法求解二次分配问题、TSP问题和作业调度等问题，取得了较好的成果。该算法已经显示出它在求解复杂优化问题，特别是离散优化问题方面的优势，是一种很有发展前景的智能计算方法。2.1蚁群算法的基本原理20世纪90年代初期，意大利学者M.Dorigo等人从生物进化和仿生学角度出发，研究蚂蚁寻找路径的自然行为，通过大量的观察和研究，提出了蚁群算法[20-22]。为了更好的说明蚁群算法的基本原理，针对蚁群搜索食物的过程进行分析。像蜜蜂、飞蛾、蚂蚁等群居昆虫，尽管单个昆虫的行为很简单，但正是由这些简单的个体所组成的群体，却能表现出复杂的行为。蚂蚁这类群居的昆虫，尽管没有视觉，经过一段时间后，却能找到由蚁穴到食物源的最优路径，原因是什么呢？国内外的仿生学家经过大量细致的观察研究后发现，蚂蚁个体之间是通过一种称之为信息素(pheromone)的特