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