基于改进的遗传蚁群混合算法的TSP问题求解研究.pdf

《基于改进的遗传蚁群混合算法的TSP问题求解研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分类号UDC密级单位代码!Q151基于改进的遗传蚁群混合算法的TSP问题求解研究吴兴健大7≮‘I)c￡指导教师蒋波职称学位授予单位教授大连海事大学申请学位级别-r-学eid：学科(专业)计算机科学与技术论文完成日期2011年5月答辩日期2011年7月答辩委员会主席垒查量AStudyofApproachtoSolvetheTSPBasedonanImprovedGeneticandAntColonyAlgorithmthesisSubmittedtoDalianMaritimeUniversityInpartial

2、fulfillmentoftherequirementsforthedegreeofMasterofEngineeringByWuXingjian(ComputerScienceandTechnology)ThesisSupervisor：ProfessorJiangBoMay，2011大连海事大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成博／硕士学位论文：基王邀遂的遣笾壑登湿金篡选丝I墨￡间逐盛鲤婴究：：。除论文中已经注明引用的内容外，对

3、论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果。本声明的法律责任由本人承担。学位论文作者签名：萎茎壁学位论文版权使用授权书本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论

4、文。同意将本学位论文收录到《中国优秀博硕士学位论文全文数据库》(中国学术期刊(光盘版)电子杂志社)、《中国学位论文全文数据库》(中国科学技术信息研究所)等数据库中，并以电子出版物形式出版发行和提供信息服务。保密的论文在解密后遵守此规定。本学位论文属于：保密口在——年解密后适用本授权书。不保密口(请在以上方框内打“√’’)论文作者签名：曩爱乡篷导师签名：构恢日期：20lj年7月2日中文摘要摘要TSP问题是一个典型的组合优化问题，也是一个易于描述却难以处理的NP难题。针对TSP问题的研究，长期以来，人们一直在寻求一种

5、高效、快速的近似算法，以便在合理的计算时间范围内准确地求解一个规模较大问题，其中，典型的智能优化算法有蚁群算法和遗传算法以及两者的混合算法等。本文主要研究一个改进的遗传蚁群混合算法并用于求解TSP问题，其主要研究工作如下：(1)结合TSP问题的特点，在求解初期，应用Delaunay三角剖分的候选集策略来减少求解问题的搜索空间，以加快搜索速度，并以此作为运用改进算法求解TSP问题的基础。(2)重点分析了蚁群、遗传及其传统的混合算法的不足，针对这些缺陷提出了一些改进：1)引入动态融合的策略以确保两种算法的最佳融合时机

6、；2)引入灰预测模型对最大最小蚁群算法信息素限界进行估计；3)引入云关联规则，实现混合算法的参数自适应调节。经过这些改进，使得遗传算法与蚁群算法更好地的动态融合在一起，充分发挥各自优势，更高效地用于求解TSP问题。为了验证改进算法的性能，本文利用TSPLIB提供的实验数据，对比分析了本文所提出的改进算法与最大最小蚁群算法、改进前的遗传蚁群混合算法的运行结果。结果表明，本文所提出的改进算法的性能相对较优。关键词：TSP问题；Delaunay三角剖分；遗传蚁群动态融合算法；灰预测：云关联英文摘要AbstractTSP

7、isnotonlyatypicalcombinatorialoptimizationproblem，butalsoaNP—hardproblem，whichiseasy．to．describebutdifficulttodealwith．Foralongtime，peoplehavebeenlookingforanefficient，fastapproximationalgorithmtosolveaLarge。scaleproblemaccuratelyinareasonabletime．Amongthem，t

8、ypicalofintelligentoptimizationalgorithmshaveAntColonyalgorithmandGeneticalgorithmaswellasmixofbothalgorithmsandSOon．ThispapermainlystudythesolutionofTSPbasedononeImprovementofGeneticandA