毕业设计开题报告范文

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐毕业设计开题报告范文南京航空航天高校金城学院毕业设计（论文）开题报告

题目基于蚁群算法的TSP问题讨论

系部信息工程系

专业信息工程

同学姓名李奇学号2022021237指导老师谭静职称讲师

毕设地点南京航空航天高校金城学院机房

年代日

填写要求

1．开题报告只需填写“文献综述”、“讨论或解决的问题和拟采纳的办法”两部分内容，其他信息由系统自动生成，不需要手工填写。

2．为了与网上任务书兼容及终于打印格式全都，开题报告采纳固定格式，如有不适请调节内容以适应表格大小并保持整体美观，切勿轻易转变格式。

3．任务书须用A4纸，小4号字，黑色宋体，行距1.5倍。

4．使用此开题报告模板填写完毕，可直接粘接复制相应的内容到毕业设计网络系统。

1.结合毕业设计（论文）课题任务状况，按照所查阅的文献资料，撰写1500～2000字左右的文献综述：

1.1蚁群算法的进展和应用

在计算机自动控制领域中,控制和优化始终是两个重要问题。使用计算机举行控制和优化本质上都表现为对信息的某种处理。随着问题规模的日益浩大,特性上的非线性及不确定性等使得难以建立精确的“数学模型”。人们从生命科学和仿生学中受到启发,提出了许多智能优化办法,为解决复杂优化问题(NP-hard问题)提供了新途径。

蚁群算法(AntColonyAlgorithm,ACA)是DorigoM等人于1991年提出的。

经观看发觉,蚂蚁个体之间是通过一种称之为信息素的物质举行信息传递的。在运动过程中,蚂蚁能够在它所经过的路径上留下该种信息素,而且能够感知信息素的浓度,并以此指导自己的运动方向。蚁群的集体行为表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者挑选该路径的概率就越大。蚂蚁个体之间就是通过这种信息的沟通达到搜寻食物的目的。它充分利用了生物蚁群通过个体间容易的信息传递，搜寻从蚁巢至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间的相像性。同时，该算法还被用于求解二次指派问题以及多维背包问题等，显示了其适用于组合优化问题求解的优越特征。

蚁群算法应用于静态组合优化问题,其典型代表有旅行商问题(TSP)、二次分配问题(QAP)、车间调度问题、车辆路径问题等。在动态优化问题中的应用主要集中在通讯网络方面。这主要是因为网络优化问题的特别性,如分布计算,随机动态性,以及异步的网络状态更新等。例如将蚁群算法应用于QOS组播路由问题上,就得到了优于模拟退火(SA)和遗传算法(GA)的效果。蚁群优化算法最初用于解决TSP问题，经过多年的进展，已经间续渗透到其他领域中，如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域获得胜利的应用，其中最胜利的是在组合优化问题中的应用。

1.2蚁群算法求解TSP问题

（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.3蚁群算法优缺点

蚁群算法是一种分布式的本质并行算法，蚁群算法是一种正反馈算法，蚁群算法具有较强的鲁棒性，易于与其它办法结合。但蚁群算法收敛速度慢、计算时光长，易于过早陷入局部最优，不利于解决延续问题。

1.4蚁群算法的展望

（1）目前大部分改进的蚁群算法都是针对于特定问题,普适性不强,同时蚁群算法模型也不能直接应用于实际优化问题。虽然正反馈机制就是一个很好的普适性模型,但还远远不够。因此,急需设计一种通用的蚁群算法普适性模型。

（2）现阶段的蚁群算法只是模拟了自然蚂蚁很少一部分社会性,例如信息素机制。仍然有很大的空间去提出越发智能化的蚁群行为。

（3）蚁群算法目前还带有显然的阅历性,无数结果只是建立在试验的基础之上,需要逐步奠定其理论基础。

因此，按照TSP问题的特点，建立蚁群算法的模型，可以较好的解决此类组合优化问题（NP问题）。

2.毕业设计任务要讨论或解决的问题和拟采纳的办法：

（1）毕业设计任务要讨论或解决的问题

讨论基于蚁群算法的TSP问题，要求

①阅读蚁群算法相关的论文和书籍，系统地了解蚁群算法相关学问和原理的目的。

②把握旅行商问题的基本原理和常用解决方面。

③把握MATLAB软件平台的应用和操作，学习蚁群算法模型在不同的NP问题中的模型建立。

④通过蚁群算法的仿真和分析，实现蚁群算法解决TSP。

（2）预期成绩：

通过讨论和分析各种蚁群算法模型，把握蚁群算法的基本原理和实现步骤，并在MATLAB环境中举行仿真，分析蚁群算法中各关键参数对算法性能的影响。

针对旅行商问题，把握经典算法的基本思想和解决办法，并应用性能优异的蚁群算法得出旅行商问题的最佳解。

（3）拟采纳的讨论办法

在蚁群算法解决TSP问题中，采纳以下讨论办法：

（1）讨论蚁群算法的基本原理，通过仿真结果分析蚁群算法关键参数对算法的影响。

（2）通过理论分析和仿真切验，研究蚁群算法的收敛性。

（3）分析旅行商问题的经典解决办法，并和蚁群算法解决旅行商问题的结果举行比较分析。

指导老师意见（对课题的深度、广度及工作量的意见和对毕业设计（论文）结果的预测）：

毕设主要讨论基于蚁群算法的TSP问题讨论，即在MATLAB软件环境中