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