蚁群算法的改进研究与应用.doc

中图分类号：O224论文编号：学科分类号：110.7480密级：公开安徽理工大学硕士学位论文蚁群算法的改进研究与应用作者姓名：弓英瑛专业名称：应用数学研究方向：优化理论与应用导师姓名：许峰教授导师单位：安徽理工大学理学院答辩委员会主席：论文答辩日期：年月日安徽理工大学研究生处年月日ADissertationinAppliedMathematicsResearchandApplicationofImprovedAntColonyAlgorithmCandidate:GongYingyingSupervisor:XuFengSchoolofScienceAnhuiUniversityofScienceandTechnologyNo.168,ShungengRoad,Huainan,232001,P.R.CHINA独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得安徽理工大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：___________日期：年月日学位论文版权使用授权书本学位论文作者完全了解安徽理工大学有保留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于安徽理工大学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权安徽理工大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书）学位论文作者签名：签字日期：年月日导师签名：签字日期：年月日摘要PAGE\*MERGEFORMATI摘要蚁群优化算法是一种群体智能算法，是自然界中蚂蚁群落在寻找食物过程的模拟，是一种新兴的智能进化算法，是专门解决离散的棘手的问题，在许多应用中，充分展示了其优点，在算法的改进方面也取得了很好的成果。与积极的反馈、自组织、分布式、强健、易与其他算法相结合的优势，蚁群算法往往陷入局部最优解，收敛速度慢，对初始解的要求比较高。从理论上讲，适当转换后改进的蚁群算法可以使任何组合优化问题得到更快地解决。本文在蚁群算法和模拟退火算法的基础上对他们进行混合改进，并考虑目标函数梯度的因素，促使算法快速全局收敛；另外，在夹角优化方面也作了相关改进，考虑方向夹角对算法的影响程度，都得到了很好的结果。根据蚁群算法的特点，本文提出了基于目标函数梯度的模拟退火蚁群算法和夹角优化的蚁群算法。数值分析和实验表明：改进的新算法不仅具有原算法的优点，而且提高了算法的速度。新算法应用于旅行商及路径规划问题，新算法的优越性得到了验证。本文所做工作如下：简要介绍了蚁群算法的产生背景意义及研究现状，归纳论文所研究的内容与意义。简要介绍了蚁群算法的基本原理、算法步骤及流程，最后分析了算法的优缺点等。首先简要介绍了模拟退火算法的基本原理和算法的过程，然后介绍了一种基于目标函数的梯度模拟退火蚁群算法的基本原理和算法流程，最后给出新算法对问题优化的实验结果。首先简要介绍路径规划问题，然后介绍夹角优化的蚁群算法的基本原理和算法流程，最后给出新算法对路径规划问题优化的结果。图13表1参33关键词：蚁群算法；模拟退火算法；梯度；夹角优化分类号：O224AbstractPAGE\*MERGEFORMATIXAbstractAntcolonyalgorithmisakindofswarmintelligenceoptimizationalgorithm.Itisanewintelligentevolutionaryalgorithmwhichisasimilartotheprocessofantcommunitiesinsearchoffoodinnature.Anditisanidealmethodforsolvingdifficultdiscreteproblems.Itfullydemonstrateditsadvantagesinmanyapplicationsandobtainedgoodresultsintermsofimprovedalgorithms.Antcolonyalgorithmhastheadvantageofpositivefeedback,self-organization,distributed,robust,easytocombinewithotheralgorithms.Butoftentrappedinlocaloptimalsolution,convergenceisslow