蚁群算法及其在TSP问题中的应用.pdf

《蚁群算法及其在TSP问题中的应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、题目英文并列目蚁叠簋选区墓垄!墨里间题虫盥廑旦THEAPPLICATIONOFANTCOLoNYALGORITHMINTSP研究生姓名：盐壹生专业：椹式迟别皇蟹篚丕缠研究方向：搓式迟别皇智能丑：篡导师姓名：逊裹一职称：副熬援论文报告提交日期授予单位名称和地址2QQ里笙2且学位授予同期2Q!Q生1日北京工业大学北京市朝阳Ⅸ平乐园100号一独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得j量塞王些太堂或其它教育机构的学位或证书而使用过的材料。与我一同工

2、作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。关于论文使用授权的说明本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被套阅和借阅：学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。(保密的论文在解密后应遵守此规定)签名：塑篁垡导师签名：垒蕉日期：至QQ旦：旦摘要摘要组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等。大多数这类问题通常在多项式时间里无法求解，属于NP完全问题。随着问题规模的扩大，问题空间呈现组合爆炸特征，无法用常规的方法求解。旅行

3、商问题(TSP)就是一个经典的组合优化问题，属于NP完全问题。此类问题目前只能用启发式算法进行求解。自从上世纪50年代中期以来，人们不断地从生物进化的机理中得到启发，提出了许多用于解决复杂优化问题的新方法，比如神经网络、遗传算法、模拟退火算法、进化规划等，并成功应用于解决实际问题。蚁群算法作为一种新的启发式算法，它具有正反馈、分布式计算以及结构性的贪心启发等特点，使其能够成功地解决许多NP-完全组合优化问题。虽然，该研究方法目前处于研究的初级阶段，但是一些研究成果己经显示出蚁群系统在求解复杂优化问题方面的优越性．本文在详细介绍蚁群算法原理的基础上，对蚁群算法在TSP问题中的应用进行分析

4、和研究，对蚁群算法中参数口，∥，P的影响和作用做了分析和研究，同时对最优的参数设置问题做了进一步分析和研究。最后提出了一种改进蚁群算法模型，仿真实验表明：这种改进模型是行之有效的。关键词：蚁群算法组和优化旅行商问题参数设置信息激素北京TjIp大学丁学硕十学位论文ABSTRACTCombinatorialoptimizationproblemisanimportantembranchmentofoperationalresearchThemathematicalmethodscanbeusedtosearchoptimizationarrangegrouping，sequenceorri

5、ddingofthediscreteevenB．TheseproblemsbelongtotheNon-polynomial。complete(NPC)questions，whichcan’tbesolvedinpolynomialtime．Withtheenlargementofthescaleofquestion，thequestionspacemakesthecharacteristicofexplodingup，isunlikelysolvedwithgeneralmethods．AsaNPCproblem，TravelingSalesmanProblem(TSP)isacla

6、ssicalcombinatorialoptimizationquestion，whichnowcanonlybesolvedbymeta—heuristicstogettheapproximatesolution．Sincemiddleperiodof1950’S，peoplearebeinginspiredfromthemechanismofthebiologicalevolutionconstantly．Manynewmethodshadbeenappliedtosolvethecomplicatedoptimizationproblemsareproposed．Suchasne

7、uralnetwork，geneticalgorithm，simulatedannealing，andevolutioncomputation．Thesenewmethodshadbeensuccessfullyappliedtosolvethepracticeproblem．Asanewheuristicalgorithm，AntColonyOptimization(ACO)algorithmwhosemaincharacteristicsa