改进的混合型蚁群算法及其应用硕士学位论文

《改进的混合型蚁群算法及其应用硕士学位论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：O157单位代码：10110学号：s20110075中北大学硕士学位论文改进的混合型蚁群算法及其应用xxx华北改进的混合型蚁群算法及其应用硕士研究生孙晶指导教师xxx教授学科专业应用数学年月日图书分类号O157密级非密UDC510硕士学位论文改进的混合型蚁群算法及其应用孙晶指导教师（姓名、职称）xxx教授申请学位级别理学硕士专业名称应用数学论文提交日期年月日论文答辩日期年月日学位授予日期年月日论文评阅人答辩委员会主席年月日xxx学位论文摘要旅行商问题（TSP）与车辆路径问题（VRP）自提出以来，许多学者进行了大量的理论研究和实验分析，取得了非常显著的进展，已经成为了运筹

2、学和组合优化问题领域的热点研究问题。求解他们的算法主要有精确型算法、近似算法和启发式算法。在众多求解TSP算法中，蚁群算法具有较好的性能，该仿生智能算法和传统的算法截然不同，具有鲁棒性、正反馈、并行性和易与其他方法相结合等特点。自创立以来，无论理论研究还是在应用方面都取得了突破性的进展，不但在求解以上两种问题上得到了最优解，而且在工件的排序问题、图着色问题、多目标函数等许多领域也取得了相当不错的效果，具有相当广阔的发展前景。本文首先介绍了一种求解TSP问题的算法—改进的混合型蚁群算法，该算法在近邻法构造初始解的基础上，使用2-opt局部搜索法对当前解进行改进，在更新全局信息素时

3、采用基于排序的蚂蚁系统对排在前2名的蚂蚁更新全局信息素，且为全局信息素设置最大值和最小值，并使用MATLAB仿真求解了kroa200等13个经典TSP问题。通过仿真实验可以看出本文改进的算法在求解TSP问题时具有很好的效果，在求解很多问题时已经非常接近最优解或者优于最优解，和最优解相差的百分比基本都在1%以下，并和两种最新改进的蚁群算法以及两种自组织算法进行比较，比较结果充分证明了该改进算法的有效性。其次，本文利用文献提出的统计边数的方法对TSP问题的种群多样性进行了分析，通过实验仿真与基本蚁群算法从平均的边数和、最大的边数以及最小边数和进行了比较分析，从数据上说明了改进的算法

4、具有种群多样性。最后又把改进的混合型蚁群算法应用到VRP问题，使用MATLAB仿真工具对N44K6等10个经典VRP问题进行了求解，得到的结果和已知最优解的误差很小，都在6%以下，并且N33K6问题得到了和已知最优解相同的解。并且与基本蚁群算法做了比较，比较结果充分证明了该改进算法的有效性。关键词：混合型蚁群算法，TSP问题，种群多样性，VRP问题xxx学位论文AbstractManyscholarshavebeenalotoftheoreticalresearchandexperimentalanalysissinceTravelingSalesmanProblem(TSP)

5、andVehicleRoutingProblem(VRP)areproposedandnotableprogressismade.TSPandVRPhavebecomethecentralissueinoperationalresearchandcombinatorialoptimization.Precisealgorithm,approximatealgorithmandheuristicalgorithmareusedtosolvetheproblems.Amongallthealgorithms,antcolonyalgorithmhasbetterperformanc

6、e.Thisbionicintelligencealgorithmisquitedifferentfromthetraditionalones,it’smorerobust,positivefeedback,concurrencyandeasytocombinewithotheralgorithms.Sinceantcolonyalgorithmisproposed,breakthroughprogresshasbeenmadebothintheoreticalresearchandrealisticapplication.Notonlyoptimalresultsareach

7、ievedbutalsoproventobeeffectiveinschedulingjobs,graphcoloring,multi-objectivefunctionandotherscopes.Ithasaverybroadprospect.Inthispaper,amixedantcolonyalgorithmisintroducedfirstly.Thealgorithmisbasedonthetraditionalantcolonysystemalgorithm,construc