蚁群算法的分析与其在网络路由优化上的应用

《蚁群算法的分析与其在网络路由优化上的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名：雅浓．日期．妒譬．譬．1J关于论文使用授权的说明本学位论文作者完全了解江南大学有关保留、使用学位论文的规定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查

2、阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。签名：猿’／亥·导师签名：El期：侧·3·f，第一章绪论1课题的研究背景及意义最优化是一个重要的数学分支，也是--I'7应用相当广泛的学科，最优化的目的是对于给出的实际问题，从众多方案中选择出最优方案。在最近的二、三十年中，伴随着计算机技术的高速发展和优化计算方法的进步，各种优化问题的理论研究发展迅速，新方法

3、不断出现，实际应用同益广泛。研究群居性昆虫行为特性的科学家发现，昆虫在群落级上的合作基本上是白组织的，在许多场合中尽管这些合作可能很简单，但是它们却可以解决复杂的问题，这种由群居性生物产生出来的一种集体行为，即产生的群集智能引起了包括计算机科学家在内的众多研究人员的兴趣。蚁群算法(antcolonyalgorithm)就是利用群集智能解决优化问题的典型例子。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等启发式搜索算法之后的一种新型的基于种群的启发式仿生类进化算法。该算法首先由意大利学者M．

4、Dorigo等人提出，有时也称为蚁群系统【¨】。蚂蚁在寻找食物的运动过程中，能在其经过的路径上分泌一定数量具有气味的被称为信息素的物质来进行信息传递，并指导自己的运动方向。某一路径上走过的蚂蚁越多，此路径上蚂蚁留下的信息素也越多，则后来蚂蚁选择该路径的概率也越大，从而更加增加了该路径被选择的可能性。随着时问的推移，蚂蚁就会找到由蚁巢至0食物源的最短路径。通过仿真模拟实际蚂蚁行为，蚁群算法在许多相当困难的组合优化问题的求解中体现了极强的寻优能力和较好的性质。蚁群算法在过去短短十多年的时间里，己在TSP问趔2

5、4】、分配问题l"J、路径规划问题f361、网络路由【251、函数优化、数据挖掘、机器人路径规划等领域获得了广泛的应用，并取得了较好的效果。蚁群算法特别适合求解规模较大的或问题状态随时间变化的组合优化问题，如著名的TravelingSalesmanProblem(TSP)，QuadraticAssignmentProblem(QAP)，Job．shopSchedulingProblem(JSP)等复杂组合优化问题。尽管目前对蚁群优化算法的研究刚刚起步，一些思想尚处于萌芽时期，但人们己隐隐约约认识到，人类诞

6、生于大自然，解决问题的灵感似乎也应该来自大自然，因此，越来越多的学者丌始关注和研究蚁群优化算法，初步的研究结果已显示出该算法在求解复杂优化问题(特别是离散优化问题)方面的优越性。虽然蚁群优化算法的严格理论基础尚未确立，国内外有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种模仿自然生物的新型系统寻优思想无疑具有十分光明的前景。1．2蚁群算法的国内外研究现状(1)模型改进江南人学硕士学位论文人们针对不同的具体问题提出了许多不同类型的蚁群算法改进模型，但这些蚁群算法模型通用性不强，同时基本蚁群算法模型

7、也不能直接应用于解决具体的优化问题。另外，自然界中的真实蚁群还有许多其他智能行为，因此开发设计不同的蚁群算法模型是一条新的发展思路。基于此，可从以下几个方面对其模型进行改进。1)设计一种通用的蚁群算法通用性模型i5_11】。首次提出蚁群算法是用于解决TSP问题，后来的一些蚁群算法改进基本是针对某一类问题而设计的，而现实中的问题干差万别，并不是每一个问题都能够很容易化归到这样一个拥有高度社会性的蚁群智能模型中，而且系统高层次的行为是通过低层次昆虫之间简单行为的交互涌现而产生的。在算法的通用性研究方面，应进一

8、步探索蚁群算法模型的高层次统一机制，并结合复杂性系统展开研究，提出更通用的蚁群算法模型。蚁群算法的正反馈机制就是一个很好的通用性模型。2)研究自然界真实蚁群行为，提出更加智能化的蚁群混合行为模型【121。从深度上说，虽然蚁群算法是基于蚂蚁觅食行为而发展起来的，但是自然界中的真实蚂蚁觅食机理并不那么简单，仍有许多借鉴之处，今后应继续挖掘蚂蚁觅食中一些未知的行为，得到新的蚁群算法模型；从广度上说，蚂蚁等昆虫除了寻找食物之外，还有着