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