龙源期刊网
蚁群算法
作者：付欣 李静
来源：《硅谷》2012年第03期
摘 要： 在自然界中，蚂蚁群体表现出高度的结构化组织，蚂蚁种群所表现出的能力远远超出单一的个体，科学家们通过对蚂蚁种群觅食、构建巢穴、任务分配等行为能力的研究发现蚂蚁所特有的控制自身周围环境的能力，早在1989年Cross S等通过著名的双桥实验确定信息素对于蚂蚁觅食过程的指导作用，也为后来蚁群算法的模型建立奠定基础。
关键词： 蚁群算法；研究；发展
中图分类号：TN911 文献标识码：A 文章编号：1671－7597（2012）0210183－01
1 蚂蚁个体的抽象
蚁群算法的起源是模拟自然界中蚂蚁群体行为，但与真实的蚂蚁个体还存在一定的差别，将自然界中的蚂蚁个体进行抽象的目的就是更方便的刻画蚁群的自然行为，同时抛除与问题建模无关的因素。通过这种方式得到的蚂蚁个体可以视为一些智能体，它们之间可以通过一定的机制互相通信、影响，同时也可以共同完成所求问题的简单解的构造过程。
2 问题空间的抽象
蚁群算法是建立在对自然界三维空间的抽象基础之上，通常是用一个二维的平面来代替现实中的蚂蚁觅食三维空间。同时自然界中蚂蚁觅食的空间是一个连续的二维空间，而在计算机模拟的问题模型中多数属于离散事件，因此还需要将所需求解的问题离散化为点组成的解空间。这个抽象过程的可行性在于：尽管蚂蚁是在连续平面中运动，但其运动过程是由离散点所组成，因此对问题空间的抽象过程仅提高了离散化的粒度，与蚂蚁自身的觅食机理没有任何冲突。在多数应用问题中经常使用图（Graph）结构来对问题空间进行描述。
3 觅食路径的抽象
觅食过程中蚁群会在食物和巢穴之间构造一个特定的空间，在这一空间中存在大量的蚁群所固有的信息，这些信息可以指引蚂蚁在此空间中的运动方向，在解决优化问题时，人工蚂蚁在平面节点上搜寻路径的过程就对应了解的构造过程；在人工蚂蚁的运动过程中由平面节点间边上的轨迹提供指导信息，即相当于信息素；人工蚂蚁根据路径上信息素的浓度大小按照一定的概率决定下一步前进的方向，以此类推，经过一定时间之后到达目标节点，这样便可以得到可行解。 龙源期刊网
蚁群算法
目 录
1 蚁群算法基本思想 ........................................................................................................................................................ 1
1.1 蚁群算法简介 ......................................................................................................................................................... 1
1.2 蚁群行为分析 ......................................................................................................................................................... 1
1.3 蚁群算法解决优化问题的基本思想 ..................................................................................................................... 2
1.4 蚁群算法的特点 ..................................................................................................................................................... 2
蚁群算法的改进与应用
摘要：蚁群算法是一种仿生优化算法，其本质是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。但是现在蚁群算法还是存在着缺点和不足,需要我们进一歩改进,如：搜索时间长、容易出现搜索停滞现象、数学基础还不完整。本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点，其次讨论如何利用遗传算法选取蚁群算法的参数，然后结合对边缘检测的蚁群算法具体实现过程进行研究分析，最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后要继续研究学习的工作内容。
关键词：蚁群算法;边缘检测;阈值;信息素;遗传算法;
1 前言
蚁群算法是近年来提出的一种群体智能仿生优化算法，是受到自然界中真实的蚂蚁群寻觅食物过程的启发而发现的。蚂蚁之所以能够找到蚁穴到食物之间的最短路径是因为它们的个体之间通过一种化学物质来传递信息，蚁群算法正是利用了真实蚁群的这种行为特征，解决了在离散系统中存在的一些寻优问题。该算法起源于意大利学者 Dorigo M 等人于 1991
年首先提出的一种基于种群寻优的启发式搜索算法，经观察发现，蚂蚁在寻找食物的过程中其自身能够将一种化学物质遗留在它们所经过的路径上，这种化学物质被学者们称为信息素。这种信息素能够沉积在路径表面，并且可以随着时间慢慢的挥发。在蚂蚁寻觅食物的过程中，蚂蚁会向着积累信息素多的方向移动，这样下去最终所有蚂蚁都会选择最短路径。该算法首先用于求解著名的旅行商问题（Traveling Salesman Problem，简称 TSP）并获得了较好的效果，随后该算法被用于求解组合优化、函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由等问题。
尽管目前对 ACO 的研究刚刚起步，一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此越来越多人开始关注和研究 ACO，初步的研究结果已显示出该算法在求解复杂优化问题（特别是离散优化问题）方面的优越性。虽然 ACO 的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种自然生物的新型系统寻优思想无疑具有十分光明的前景。但该算法存在收敛速度慢且容易出现停滞现象的缺点，这是因为并不是所有的候选解都是最优解，而候选解却影响了蚂蚁的判断以及在蚂蚁群体中，单个蚂蚁的运动没有固定的规则，是随机的，蚂蚁与蚂蚁之间通过信息素来交换信息，但是对于较大规模的优化问题，这个信息传递和搜索过程比较繁琐，难以在较短的时间内找到一个最优的解。
2.1 蚁群算法的基本原理
蚁群优化算法是模拟蚂蚁觅食的原理，设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的几率也就越高，由此构成的正反馈过程，从而逐渐的逼近最优路径，找到最优路径。
蚂蚁在觅食过程时，是以信息素作为媒介而间接进行信息交流，当蚂蚁从食物源走到蚁穴，或者从蚁穴走到食物源时，都会在经过的路径上释放信息素，从而形成了一条含有信息素的路径，蚂蚁可以感觉出路径上信息素浓度的大小，并且以较高的概率选择信息素浓度较高的路径。
蚁穴食物源AB15cm(a) 蚁穴 12 食物源AB(b)
人工蚂蚁的搜索主要包括三种智能行为：
（1）蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选择，因此在蚁群算法中建立禁忌表进行模拟。
（2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素的物质，当其他蚂蚁进行路径选择时，会根据路径上的信息素浓度进行选择，这样信息素就成为蚂蚁之间进行通信的媒介。
（3）蚂蚁的集群活动。通过一只蚂蚁的运动很难达到事物源，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，路径上留下的信息素数量也就越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度，而通过的蚂蚁比较少的路径上的信息素会随着时间的推移而挥发，从而变得越来越少。3.3.1蚂蚁系统
蚂蚁系统是最早的蚁群算法。其搜索过程大致如下：
在初始时刻，m只蚂蚁随机放置于城市中，各条路径上的信息素初始值相等，设为：0(0)ij为信息素初始值，可设0mmL，mL是由最近邻启发式方法构造的路径长度。其次，蚂蚁(1,2,)kkm，按照随机比例规则选择下一步要转移的城市，其选择概率为：
