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

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

1、学位论文独创性声明：本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。如不实，本人负全部责任。论文作者(签名)：睦堕鱼力哨年弓月zg日学位论文使用授权说明河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊(光盘版)电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档

2、的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。论文全部或部分内容的公布(包括刊登)授权河海大学研究生院办理。论文作者(签名)：匪堡建z呓年弓月?g日河海大学颂士学位论文第一章绪论自然界的许多自适应优化现象不断地给人类以启示：生物体和自然生态系统可以通过自身的演化就使许多在人类看起来高度复杂的优化问题得到完美的解决。近十几年来一些与经典的数学规划原理截然不同的、试图通过模拟自然生态系统机制求解复杂优化问题的新型智能计算方法相继出现，大大丰富了最优化技术，也为那些传统最优化技术难以处理的组合优

3、化问题提供了切实可行的解决方案。这些通过模拟人、自然及其它生物种群的结构特点、进化规律、行为方式及思维结构而发展起来的，用于求解各类规划优化问题的计算技术和方法称为元启发式(Mcta．heuristic)算法，如遗传算法(GeneticAlgorithm，GA)、模拟退火算法(SimulatcdAnnealing，SA)、进化规划(EvolutionaryProgramming，EP)、禁忌搜索算法(TabuSearch，TS)、蚁群算法(AntColonyAlgorithm，ACA)等。元启发式算法已经在一些经典的组合

4、优化问题的求解和实际运用中显示出了强大的生命力和潜力。它具有与传统优化算法(如数学规划、动态规划等)不同的如下特点：一、它是一类不确定性的方法。不确定性体现了自然界的生理机制，并且在求解某些特定问题方面优于确定性算法。二、它是一类概率型的全局最优搜索方法。非确定性算法的优点在于算法能有更多机会求得全局最优解。三、它在优化过程中不依赖于优化问题本身的严格数学性质，如连续性、可导性及目标函数和约束条件的精确数学描述。四、它是一类基于多个智能体的智能算法。各智能体通过自学习不断提高自身的适应性，同时通过相互之间的协作来更好地适

5、应环境。五、它具有潜在的并行性。搜索过程不是从一个点出发，而是同时从多个点同时进行。这种分布式的多个智能体的协作过程是异步并发进行的，分布并行模式将大大提高整个算法的运行效率和收敛速度。本文所研究的内容就是一种新型的启发式仿生算法一蚁群算法，及其在最优化问题方面的应用研究。1．1最优化问题及其分类最优化问题有三个基本要素：变量、约束和目标函数。在求解过程中选定的基本参数称为变量，对变量取值的种种限制称为约束，表示可行方案衡量标准的函数称为目标函数。最优化问题可分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定

6、区间内的连续变量，而组合优化的对象是解空间中的离散状态。下面分别加以介绍。蚁群算法的研究及在刚络路由优化上的应用函数优化问题通常可描述为：令S为R“上的有界子集(即变量的定义域)，，．5—根为n为实值函数，所谓函数，在S域上全局最小化就是寻求点工。∈s，使得f(x。。)在s域上全局最小，即橱ES：f(x。i。)sf(x)。组合优化问题通常可描述为：令Q。{SI,S：，⋯S。)为所有状态构成的解空间，c(s；)为状态s，对应的目标函数值，要求寻找最优解S+，使得协j∈Q，C(s‘)iminC(s，)。组合优化往往涉及排序、

7、分类、筛选等问题，它是运筹学的一个重要分支。典型的组合优化问题有旅行商问题(TravelingSalesmanProblem，TSP)、加工调度问题(SchedulingProblem，如flow—shop，job·shop)、0-1背包问题(KnapsackProblem)、装箱问题(BinPackingProblem)、图着色问题(GraphColoringProblem)、聚类问题(ClusteringProblem)等。最优化的主要内容是研究最优化问题的计算方法，把可解决某个问题的计算方法称为适用于该问题的算法。

8、算法的性能比较通常是基于一些称为Benchmark的典型问题展开的。优化问题的一些Benchmark问题见附录。1．2算法的复杂性与NP问题1．2．1算法的复杂性由于有些优化算法所需的计算时间和存储空间难以承受，因此算法可解的问题在实践中并不一定可解。如对称TSP问题(规模为Ⅳ)，可能路径为(Ⅳ_1)!／2，若以路径