基于Matlab的蚁群算法的仿真开题报告

全文总字数：2314字

1. 研究目的与意义

蚁群算法(ant colony algorithm,ACA)是最新发展的一种模拟昆虫王国中蚂蚁群体智能行为的仿生优化算法，是由意大利学者M.Dorigo等人首先提出来的，他们充分利用蚁群搜索食物的过程与旅行商问题（TSP）之间的相似性，解决了TSP问题，取得了很好的结果。它的提出，能够为解决一些复杂的系统优化问题提供了一种新的、更好的求解算法，特别是在求解离散型组合优化的问题上，蚁群算法显示出了其他进化算法无法比拟的优越性。蚁群算法不仅具有鲁棒性、分布式计算、正反馈性、易于和其他的智能算法相结合的特点，而且还能够智能搜索、全局优化等优势。该算法已经引起了众多专家和学者的注意，现在正被越来越多的研究者关注和探讨，算法的理论得到不断的完善，应用范围也普及到许多的科学技术及工程领域，是一种有良好发展前景的模拟进化算法。目前蚁群算法已被用来求解分配问题、图论问题、指派问题、电力系统故障诊断等NP完全问题，显示出蚁群算法在求解复杂优化问题方面的优越性，而且在蚁群算法的硬件实现上也取得了很多突破性的研究进展，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的发展前景。

2. 国内外研究现状分析

1991年，m.dorigo等人提出了第一个aco算法蚂蚁系统(as)并成功用于求解tsp问题。实验结果表明as算法具有较强的鲁棒性和发现较好解的能力，但同时也不可避免的存在一些缺点，例如收敛速度慢、易出现停滞现象等。该算法的提出引起了学者们的广泛关注，并在此基础上提出了一些改进算法。随后，l.m.gambardella，m.dorigo用伪随机比例状态转移规则(pseudo random proportional state transition rule)替换as算法中的随机比例选择规则(stochastic proportional choice rule)，从而提出了改进的antq算法，该算法使antq算法在构造解的过程中能够更好地保持知识利用(exploitation)与知识探索(exploration)之间的平衡。m. dorigo等人又在antq算法的基础上提出了蚁群系统(ant colony system，简称acs)，该算法作为antq算法的特例实现起来更为简单。后来，sttitzle和hoos通过为信息素设置上下限提出了最大一最小蚂蚁系统(maxmin ant system，简称mmas)，以此来避免算法出现停滞现象。之后，bullnheimer等人又提出了基于排序的蚂蚁系统(rank-based version of ant system)，在该算法中，完成一次迭代后，将蚂蚁所经路径的长度按从小到大的顺序排列并根据路径长度赋予不同的权重，路径越短权重越大。

国内直到20世纪末才有学者开始关注aco算法，目前我国学者对该算法的研究主要停留在算法的改进和应用方面。吴庆洪和张纪会等通过向基本蚁群算法中引入变异机制，充分利用交换法简洁高效的特点，提出了具有变异特征的蚁群算法。吴斌和史忠植首先在蚁群算法的基础上提出了相遇算法，提高了蚁群算法蚂蚁一次周游的质量，提出一种基于蚁群算法的问题相遇算法。实验结果表明该算法有较好的有效性。王颖和谢剑英通过自适应地改变算法的挥发度等系数，提出一种自适应的蚁群算法以克服限于局部最小的缺点。覃刚力和杨家本根据人工蚂蚁所获得解的情况，动态地调整路径上的信息素，提出了自适应调整信息素的蚁群算法。

回顾蚁群算法自创立以来十多年的发展历程，尽管理论尚不算完备，目前人们对蚁群算法的研究已由当初单一的tsp领域渗透到了多个应用领域。由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范围内研究逐渐拓展到了连续域范围内研究，而且在蚁群算法的硬件实现上取得了突破性进展，同时在蚁群算法的模型改进及其与其他仿生优化算法的融合方面也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未有的勃勃生机，并已经成为了一种完全可与遗传算法相媲美的仿生优化算法。

3. 研究的基本内容与计划

本次毕设将从了解蚁群算法的思想起源和它的历史发展入手，结合国内外同类研究现状，深刻理解蚁群算法原理，学习基本蚁群算法的数学模型及其实现步骤，画出算法流程图并利用matlab实现蚁群算法。同时，用蚁群算法进行建模并应用于多局部最优的最优化问题，如旅行商问题，最后验证算法并得出结论。

时间安排：

一～二月份查阅十篇以上相关文献，了解蚁群算法原理，完成开题报告和文献综述；

4. 研究创新点

蚁群算法采用分布式并行计算机制，易与其他方法结合，具有较强的鲁棒性。与其它优化算法相比，蚁群算法具有正反馈、分布式计算以及启发式搜索等主要特点，目前蚁群算法已成功应用到许多实际问题上，其应用前景非常广阔。从提出到现在，仅短短十余年的时间，但其在离散型组合优化问题、Job-Shop问题、二次分配、集成电路设计、图着色问题、车辆调度、以及通信网络负载问题的处理中，表现得很突出，显示出蚁群算法在求解复杂优化问题方面的优越性。而Matlab作为一种强大的计算工具软件，利用其进行蚁群算法的仿真研究也是行之有效的。本次毕设，我将用Matlab完成对蚁群算法的仿真，并且深入理解该算法的优点并用于解决一些组合优化问题（旅行商问题等）。