蚁群算法概述
- 格式：docx
- 大小：16.67 KB
- 文档页数：3
蚁群算法概述
一、蚁群算法
蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来寻找最优解决方案的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此，由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象：某一条路径走过的蚂蚁越多，后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。
蚁群算法就是根据这一特点，通过模仿蚂蚁的行为，从而实现寻优。这种算法有别于传统编程模式，其优势在于，避免了冗长的编程和筹划，程序本身是基于一定规则的随机运行来寻找最佳配置。也就是说，当程序最开始找到目标的时候，路径几乎不可能是最优的，甚至可能是包含了无数错误的选择而极度冗长的。但是，程序可以通过蚂蚁寻找食物的时候的信息素原理，不断地去修正原来的路线，使整个路线越来越短，也就是说，程序执行的时间越长，所获得的路径就越可能接近最优路径。这看起来很类似与我们所见的由无数例子进行归纳概括形成最佳路径的过程。实际上好似是程序的一个自我学习的过程。
3、人工蚂蚁和真实蚂蚁的异同
ACO是一种基于群体的、用于求解复杂优化问题的通用搜索技术。与真实蚂蚁通过外激素的留存/跟随行为进行间接通讯相似，ACO中一群简单的人工蚂蚁（主体）通过信息素（一种分布式的数字信息，与真实蚂蚁释放的外激素相对应）进行间接通讯，并利用该信息和与问题相关的启发式信息逐步构造问题的解。
人工蚂蚁具有双重特性：一方面，他们是真实蚂蚁的抽象，具有真实蚂蚁的特性，另一方面，他们还有一些在真实蚂蚁中找不到的特性，这些新的特性，使人工蚂蚁在解决实际优化问题时，具有更好地搜索较好解的能力。
人工蚂蚁与真实蚂蚁的相同点为：
1．都是一群相互协作的个体。与真实蚁群一样，ACO由一群人工蚂蚁组成，人工蚂蚁之间通过同步/异步协作来寻找问题的最优解。虽然单只人工蚂蚁可以构造出问题的解，但只有当多只人工蚂蚁通过相互协作，才能发现问题的最优（次优）解。人工蚂蚁个体间通过写/读问题的状态变量来进行协作。
2．都使用外激素的迹和Stigmergy机制。如真实蚂蚁一样，人工蚂蚁通过改变所访问过的问题的数字状态信息（在ACO中被称为信息素）来进行间接的协作。在ACO中，信息素是人工蚂蚁之间进行交流的唯一途径。这种通讯方式在群体知识的利用上起到了至关重要的作用。另外，ACO还用到了蒸发机制，这一点对应于真实蚂蚁中外激素的蒸发现象。蒸发机制使蚁群逐渐忘记过去的历史，使后来的蚂蚁在搜索中较少的受过去较差解的影响，从而更好的指导蚂蚁的搜索方向。
3．搜索最短路径与局部移动。人工蚂蚁和真实蚂蚁具有相同的任务，即以局部移动的方式构造出从原点（蚁巢）到目的点（食物源）之间的最短路径。随机状态转移策略。人工蚂蚁和真实蚂蚁都按照概率决策规则从一种状态转移到另一种相邻状态。其中的概率决策规则是与问题相关信息和局部环境信息的函数。在状态转移过程中，人工蚂蚁和真实蚂蚁都只用到了局部信息，没有使用前瞻策略来预见将来的状态。因此，所使用的策略在时间和空间上是局部的。
人工蚂蚁和真实蚂蚁的不同点
1. 人工蚂蚁生活在离散的时间，从一种离散状态到另一种离散状态；
2. 人工蚂蚁具有内部状态，即人工蚂蚁具有一定的记忆能力，能记住自己走过的地方；
3. 人工蚂蚁释放信息素的数量是其生成解的质量的函数；
4. 人工蚂蚁更新信息素的时机依赖于特定的问题。例如，大多数人工蚂蚁仅仅在蚂蚁找到一个解之后才更新路径上的信息素。
有时，为了提高ACO的效率，可以在算法中加入预测、局部优化以及后退等策略。
