1. 研究目的与意义（文献综述）
本次毕业设计的目的是实现使用java算法设计一个路径寻优的算法，编程实现自动路径规划并提供演示程序，主要方法使用蚁群算法实现软件设计。使用这种算法的灵感来源于蚁群的觅食规律。 通过查阅资料发现，蚁群在觅食的时候，总能找到一条从蚁巢到食物之间的一条最短的路径。这个现象引起了生物学家的注意，根据研究，原来是蚂蚁在行进的过程中，会分泌一种化学物质——信息素，而蚂蚁在行进时，总是倾向于选择信息素浓度比较高的路线。这样，在蚁巢和食物之间假如有多条路径，初始的时候，每条路径上都会有蚂蚁爬过，但是随着时间的推迟，单位时间内最短的那条路上爬过的蚂蚁数量会比较多，释放的信息素就相对来说比较多，那么以后蚂蚁选择的时候会大部分都选择信息素比较多的路径，从而会把最短路径找出来。蚁群算法正是模拟这种蚁群觅食的原理，构造人工蚂蚁，用来求解许多组合优化问题。 蚁群算法从1991年提出到现在，只有短短的二十几年，蚁群算法在理论和实际应用上取得了长足的发展，由一维静态优化问题发展到了多维动态优化问题，由离散域问题拓展到了连续域范围内的研究。近几年来，由于它在知识发现、数据挖掘、故障检测、路径舰划等领域的广泛应用，研究逐渐趋热。国内外学者在蚁群算法的模型改进和应用方面做了大量的工作，其共同目的是在合理时间复杂度的限制条件下，尽可能提高蚁群算法在一定空间复杂度下的寻优能力，从而改善蚁群算法的全局收敛性，并拓宽蚁群算法的应用领域。 随着电脑性能的进一步提高，以及智能网络平台的发展，加之蚁群算法其高效的智能计算能力以及在广泛领域的应用，蚁群算法可以在当今时代获得更多的发展空间。
2. 研究的基本内容与方案
本次设计的基本内容是采用蚁群算法完成智能路径规划的软件设计。目标为提供一个演示程序，提供一定的障碍物，并标定多个目标地点，使用蚁群算法的思想设计程序，完成自动寻找路径，实现所有目标点均被走过，并发现其最优路径的算法。目前采用的语言为java，本次设计的核心部分是如何实现蚁群算法的寻找最优路径问题，并结合视图界面演示该算法的完成过程。在蚁群算法部分的程序中，设计了两个类，一个类用来处理文件信息的读入，信息素的更新，路径的计算等；另一个类用来储存蚂蚁的信息。具体操作是：假如蚁群中所有蚂蚁的数量为m，测试编程中蚂蚁数量采用固定数值，在后续完善时改为可变数值；所有目标地点之间的信息素用矩阵表示，在程序设计中采用坐标的形式来表示目标地点。最佳路径为besttour。每只蚂蚁都有自己的内存，内存中用一个禁忌表tabu来存储该蚂蚁已经访问过的地点坐标，表示其在以后的搜索中将不能访问这些地点；还有用另外一个允许访问的目标地点表allowed来存储它还可以访问的地点；在程序中可以使用1和0来分别表示已经达到的目标地点和未达到的目标地点。另外还用一个矩阵delta来存储它在一个循环中给所经过的路径释放的信息素；根据信息素的浓度来判断路径是否最优。还有另外一些数据，例如该蚂蚁行走完全程的总距离，用于统计最优路径；目标地点的总数量。为了实现整个设计目的，还需要设计一个可视界面来演示，做到能够显示障碍物，能够显示蚂蚁的行进路线。障碍物设计为固定障碍物，用简单线条来表示。目标地点用特殊颜色的点坐标显示。将蚂蚁用坐标的形式显示在一个坐标平面上，不断刷新视图来显示移动轨迹。最终结合蚁群算法来显示出最优路线。蚁群算法计算过程如下：（1）初始化在t=0阶段， besttour为空。初始化所有的蚂蚁的delta矩阵所有元素初始化为0，tabu表清空，allowed表中加入所有的目标点。人工指定它们的起始位置。在tabu中加入起始点，allowed中去掉该起始点。（2）为每只蚂蚁选择下一个地点为每只蚂蚁选择下一个起始点，该目标点只能从allowed中以某种概率搜索到，每搜到一个，就将该目标点加入到tabu中，并且从allowed中删除该目标点。该过程重复n-1次，直到所有的目标点都遍历过一次。遍历完所有目标点后，将起始点加入到tabu中。此时tabu表元素数量为n 1（n为目标数量），allowed元素数量为0。接下来计算每个蚂蚁的delta矩阵的路径长度。最后计算最佳路径，并且将其tabu赋予besttour。（3）更新信息素矩阵给定一个控制参数，计算信息素浓度，遗留信息素越多，信息素浓度越高。（4）检查终止条件如果达到最大代数max_gen，算法终止，转到第（5）步；否则，重新初始化所有的蚂蚁的delt矩阵所有元素初始化为0，tabu表清空，allowed表中加入所有的目标点。随机选择它们的起始位置（也可以人工指定）。在tabu中加入起始点，allowed中去掉该起始点，重复执行（2），（3）,(4)步。（5）输出最优值其流程框图如下图1所示：
3. 研究计划与安排
第一周 完成对java语言基础知识的学习第二周 实际操作完成一些基础java程序的编程，主要偏重于本次毕业设计需要用到的方便第三周 通过参考例程基本完成对java语言的学习，获取完成本次毕业设计所需的全部内容第四周 通过查阅资料了解蚁群算法的意义和实现方法，理解其设计思想第五周 对蚁群算法的例子程序阅读学习，尝试对程序进行改进和调试第六周 完成简单的蚁群算法的基本设计思路，算法框图等第七周 设计程序，完成寻找最优路径的算法第八周 调试改进程序，尝试优化算法第九周 完成可视化程序设计，设计障碍物和目标地点第十周 结合蚁群算法，设计完整程序第十一周 调试程序，使之达到设计目的第十二周 初步完成毕业设计报告的设计部分第十三周 初步完成毕业设计报告第十四周 完成程序的最终改进，改动毕业设计报告第十五周 完成程序设计并完成毕业设计报告
4. 参考文献（12篇以上）
[1]李刚，疯狂Java讲义（第三版），电子工业出版社,2014[2]Y.Daniel Liang,Java语言程序设计（基础篇），机械工业出版社，2015[3]徐明远，郑乐，余朝晖，Java常用算法手册，中国铁道出版社，2014[4]胡平，Java程序设计——原理与范例，电子工业出版社，2013[5]Dorigo, Stutzle M. T.,张军译.蚁群优化.北京：清华大学出版社，2007[6]李士勇，陈永强，李研，蚁群算法及其应用[M],哈尔滨工业大学出版社， 2004[7]段海滨，蚁群算法原理极其应用[M]，科学出版社，2007[8]http://www.aco-metaheuristic.org/[9]http://iridia.ulb.ac.be/~mdorigo/HomePageDorigo/[10]http://www.doc88.com/p-9149579222855.html[11]http://blog.csdn.net/fashionxu/article/details/5484864[12]Middendorf，MartinModeling the Dynamics of Ant Colony Optimization，2012[13]Ling Yu;Kang Liu;Kaishi Li，Ant colony optimization in continuous problem，2010[14]Xu,Benlian；Chen，Qinglan;Wang,Zhiquan，Track initiation with ant colony optimization，2009[15]Ouaarab A, Ahiod B, Yang X S；Discrete cuckoo search algorithm for the travelling salesman problem；Neural Computing and Applications，2014
