计算机软件与理论硕士论文-蚁群算法及其应用研究

《计算机软件与理论硕士论文-蚁群算法及其应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北京工业大学硕士学位论文蚁群算法及其应用研究姓名：黄振申请学位级别：硕士专业：计算机软件与理论指导教师：冀俊忠20080401摘要!!!!!!!!!!!!!!!!!!!!!!!!!!!!!，!，·_I—，_■I—-—I·———_I—mm_—_·-—I————l_——一生物学家研究发现自然界的蚂蚁个体可以分泌一种称为“信息素"的化学物质，蚂蚁群体通过“信息素”进行间接的通讯、协作来寻找从巢穴到食物的最短路径。受其启发，意大利学者Dorigo等对蚂蚁的觅食行为进行仿真研究，提出了蚁群算法。在随后的十多年时间里，蚁群算法已经在组合优化、网络路由、函数优化、数

2、据挖掘、机器人路径规划等领域获得广泛的应用，显示出蚁群算法在求解复杂问题方面的优越性，有广阔的发展前景。然而，蚁群算法仍然存在一些缺陷：如算法的收敛速度较慢，易陷入停滞等。本文围绕蚁群优化的原理及应用，就如何改进基本蚁群算法以及蚁群算法在旅行商问题TSP(TravelingSalesmanProblem)、多维背包问题MKP(MultidimensionalKnapsackProblem)qb的应用进行了研究，并基于标准的数据集对一些已有算法和提出的算法进行了效率和精度的比较和分析。首先，提出一种基于信息素增量和扩散模型的蚁群算法。算法在已有信息素更新

3、机制的基础上给出了新的基于能量守恒的信息素更新机制，融合解的全局信息和路径的局部信息对信息素的影响，以客观体现蚂蚁在不同路径上行走时产生的信息素量的差异。同时，算法将已有的基于点的信息素扩散模型改进为基于路径的信息素扩散模型，强化了蚁群个体间的影响和协作。另外，针对随机搜索机制，采用高效率、低计算复杂度的变异策略，加强了局部寻优能力。其次，针对传统蚁群算法在求解大规模TSP问题耗时过长且求解精度欠佳的问题，给出一种基于聚类和分段优化的蚁群算法。算法采取多阶段寻优策略，先对TSP问题的城市位置进行聚类处理，抽取出TSP问题的区域分布的知识，然后进行区域级

4、的路径寻优和区域内的路径寻优，最后按区域连接顺序合成完整的解路径，并通过分段策略进行局部优化。在此基础之上，引入粒度的概念，形成多粒度的TSP问题描述模型，即粗粒度可以继续划分为细的粒度，“粗”区域也可以进一步划分为更“细”的区域，从而借鉴粒度的概念将问题划分为多个层面子问题，对各个层面进行处理后再合成完整的解。最后，对蚁群算法在多维背包问题求解中的应用进行了研究，提出了一种新算法，算法利用Top．k策略获取每次迭代中最优的k个解，从中挖掘出对象间的“关联距离"，然后借助“关联距离”建立基于对象的信息素扩散模型，最后辅以简单的变异策略进行局部优化。大量

5、实例上的实验表明，这些改进的算法不仅加速了蚁群算法的收敛速度，而且提高了所得解的质量。关键词蚁群算法；扩散模型；变异策略；旅行商问题；多维背包问题Abstract●___Il●●●l，I—_●I——I——_·lII··_l_l●__●IlIl___l·_I·AbstractBiologists’studyfoundthatnaturalantscouldreleaseachemicalsubstanceknownaspheromonethroughwhichantcolonyconductindirectcommunicationandcooperat

6、ioninordertofindashortestpathfromnesttofood．Inspiredbytheant’sbehavior，ItalyscholarDorigoandhiscolleaguesdidsomesimulationresearchbycomputer．Forthefirsttime，theyproposedantcolonyalgorithm．Inthefollowing10years，antcolonyalgorithmwasappliedtoCombinatorialoptimization,networkroutin

7、g，functionoptimization，datamining，robotpathplanningandSOon,whichshowsthegreatadvantageofantcolonyalgorithminsolvingcomplexproblemsandabrightfutureforfurtherdevelopment．However，therearestillsomedefectsinantcolonyalgorithmsuchascostingtoomuchtimeandeasytodropintostagnation．Thispap

8、erfocusesontheprincipleofantcolonyoptimizationa