基于蚁群算法的TSP问题研究-毕业论文开题报告

南京航空航天大学金城学院南京航空航天大学金城学院 毕业设计（论文）开题报告毕业设计（论文）开题报告 题题目目基于蚁群算法的 TSP 问题研究 系系部部XXXX 系 专专业业XXXX 学生姓名学生姓名XXXX学号学号XXXX 指导教师指导教师XXXX职称职称讲师 毕设地点毕设地点XXXX 年月日 填写要求 1开题报告只需填写“文献综述”、 “研究或解决的问题和拟 采用的方法”两部分内容，其他信息由系统自动生成，不需要手 工填写。 2为了与网上任务书兼容及最终打印格式一致，开题报告采 用固定格式，如有不适请调整内容以适应表格大小并保持整体美 观，切勿轻易改变格式。 3任务书须用 A4 纸，小 4 号字，黑色宋体，行距 1.5 倍。 4使用此开题报告模板填写完毕，可直接粘接复制相应的内 容到毕业设计网络系统。 1.结合毕业设计结合毕业设计（论文论文）课题任务情况课题任务情况，根据所查阅的文献资料根据所查阅的文献资料，撰写撰写15002000 字左右的文献综述字左右的文献综述： 1.11.1蚁群算法的发展和应用蚁群算法的发展和应用 在计算机自动控制领域中, 控制和优化始终是两个重要问题。使用计算机进行 控制和优化本质上都表现为对信息的某种处理。随着问题规模的日益庞大, 特性上 的非线性及不确定性等使得难以建立精确的“数学模型” 。人们从生命科学和仿生学 中受到启发, 提出了许多智能优化方法, 为解决复杂优化问题(NP- hard 问题) 提 供了新途径。 蚁群算法(Ant Colony Algorithm, ACA) 是 Dorigo M 等人于 1991 年提出的。 经观察发现, 蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的。在运 动过程中, 蚂蚁能够在它所经过的路径上留下该种信息素, 而且能够感知信息素的 浓度, 并以此指导自己的运动方向 。蚁群的集体行为表现出一种信息正反馈现象: 某一路径上走过的蚂蚁越多, 则后来者选择该路径的概率就越大。蚂蚁个体之间就 是通过这种信息的交流达到搜索食物的目的。它充分利用了生物蚁群通过个体间简 单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征，以及该过程与旅行 商问题求解之间的相似性。同时，该算法还被用于求解二次指派问题以及多维背包 问题等，显示了其适用于组合优化问题求解的优越特征。 蚁群算法应用于静态组合优化问题, 其典型代表有旅行商问题( TSP) 、二次分 配问题(QAP) 、车间调度问题、车辆路径问题等。在动态优化问题中的应用主要集 中在通讯网络方面。这主要是由于网络优化问题的特殊性, 如分布计算, 随机动态 性, 以及异步的网络状态更新等。例如将蚁群算法应用于 QOS 组播路由问题上, 就 得到了优于模拟退火(SA)和遗传算法(GA)的效果。蚁群优化算法最初用于解决 TSP 问题，经过多年的发展，已经陆续渗透到其他领域中，如图着色问题、大规模集成 电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法 在若干领域获得成功的应用，其中最成功的是在组合优化问题中的应用。 1.21.2蚁群算法求解蚁群算法求解 TSPTSP 问题问题 （1） TSP 问题的描述 TSP 问题的简单形象描述是:给定 n 个城市,有一个旅行商从某一城市出发,访问 各城市一次且仅有一次后再回到原出发城市,要求找出一条最短的巡回路径。 （2） TSP 问题的理论意义 该问题是作为所有组合优化问题的范例而存在的。它已经成为并将继续成为测 试新算法的标准问题。这是因为，TSP 问题展示了组合优化的所有方面。它从概念上 来讲非常简单，但是其求解的难度是很大的。如果针对 TSP 问题提出的某种算法能 够取得比较好的实算效果，那么对其进行修改，就可以应用于其他类型的组合优化 问题并取得良好的效果。 （3） 蚁群算法求解 TSP 的算法流程 步骤 1: nc=0(nc 为迭代步数或搜索次数); 每条边上的 Tj(0)=c(常数), 并且 Tj=0; 放置 m 个蚂蚁到 n 个城市上。 步骤 2: 将各蚂蚁的初始出发点置于当前解集 TABUk(s)中; 对每个蚂蚁 k(k=1, ,m), 按概率 Pij(t)移至下一城市 j; 将城市 j 置于 TABUk(s)中。 步骤 3: 经过 n 个时刻, 蚂蚁 k 可走完所有的城市, 完成一次循环。计算每个 蚂蚁走过的总路径长度 Lk, 更新找到的最短路径。 步骤 4: 更新每条边上的信息量 Tij(t+n) 步骤 5: 对每一条边置Tij=0; nc=nc+1 步骤 6: 若 nc预定的迭代次数 Ncmax, 则转步骤 2; 否则, 打印出最短路径, 终止整个程序。 1.31.3蚁群算法优缺点蚁群算法优缺点 蚁群算法是一种分布式的本质并行算法，蚁群算法是一种正反馈算法，蚁群算 法具有较强的鲁棒性，易于与其它方法结合。但蚁群算法收敛速度慢、计算时间长， 易于过早陷入局部最优，不利于解决连续问题。 1.41.4蚁群算法的展望蚁群算法的展望 （1） 目前大部分改进的蚁群算法都是针对于特定问题, 普适性不强, 同时蚁 群算法模型也不能直接应用于实际优化问题。虽然正反馈机制就是一个很好的普适 性模型, 但还远远不够。因此, 急需设计一种通用的蚁群算法普适性模型。 （2） 现阶段的蚁群算法只是模拟了自然蚂蚁很少一部分社会性, 例如信息素 机制。仍然有很大的空间去提出更加智能化的蚁群行为。 （3） 蚁群算法目前还带有明显的经验性, 很多结果只是建立在实验的基础之 上, 需要逐步奠定其理论基础。 因此，根据 TSP 问题的特点，建立蚁群算法的模型，可以较好的解决此类组合 优化问题（NP 问题） 。 参考文献参考文献 1 Dorigo MAnt algorithms and atigmergyJFuture Generation Computer System.2000,16（8） ：851-871 2 Dorigo MGambardella LMAnt colony system：a cooperative learning approach to the traveling salesman problemJ IEEE Trans on Evolutionary Computation，1997，1（1） ：5366 3 Dorigo MLuca MThe ant colony algorithm applied to the nuclear reload problemAnnals ofNuclear Energy2009，29（12） ：14551470 4 Dorigo MAnt colony system：optimizationby a colony of cooperating agentsIEEE Trans on Systems, Man，and Cybernetics， Part B，1996， 26（1） ：2941 5 杨海，王洪国，徐卫志蚁群算法的应用研究与发展J科学和技术信息学报， 2007， （28） ：13-14 6 张宗永， 孙静， 谭家华 蚁群算法的改进及其应用J 上海交通大学学报， 2002， 36（11） ：1564-1567 7 尹晓峰，刘春煌基于 MATLAB 的混合型蚁群算法求解旅行商问题J铁路计 算机应用，2005，14（9） ：4-7 8 刘志硕，申金升，柴跃廷一种求解车辆路径问题的混合多蚁群算法J系统 仿真学报，2007，19（15） ：3513-3520 9 董萍基于蚁群算法求解 TSPJ无锡职业技术学院学报，2008，7（5） ：34-36 10 王果，戴冬基于蚁群算法的 TSP 问题求解J河南机电高等专科学校学报， 2008，16（5） ：42-43 2.毕业设计任务要研究或解决的问题和拟采用的方法：毕业设计任务要研究或解决的问题和拟采用的方法： （1）毕业设计任务要研究或解决的问题 研究基于蚁群算法的 TSP 问题，要求 阅读蚁群算法相关的论文和书籍， 系统地了解蚁群算法相关知识和原理的目的。 掌握旅行商问题的基本原理和常用解决方面。 掌握 MATLAB 软件平台的应用和操作，学习蚁群算法模型在不同的 NP 问题中的 模型建立。 通过蚁群算法的仿真和分析，实现蚁群算法解决 TSP。 （2）预期成果： 通过研究和分析各种蚁群算法模型，掌握蚁群算法的基本原理和实现步骤，并在 MATLAB 环境中进行仿真，分析蚁群算法中各关键参数对算法性能的影响。 针对旅行商问题，掌握经典算法的基本思想和解决方法，并应用性能优异的蚁群 算法得出旅行商问题的最佳解。 （3）拟采用的研究方法 在蚁群算法解决 TSP 问题中，采用以下研究方法： （1）研究蚁群算法的基本原理，通过仿真结果分析蚁群算法关键参数对算法的 影响。 （2）通过理论分析和仿真实验，讨论蚁群算法的收敛性。 （3）分析旅行商问题的经典解决方法，并和蚁群算法解决旅行商问题的结果进 行比较分析。 指导教师意见（对课题的深度、广度及工作量的意见和对毕业设计（论文）结