蚁群算法
来源:用户上传
作者: 付欣 李静
摘 要： 在自然界中，蚂蚁群体表现出高度的结构化组织，蚂蚁种群所表现出的能力远远超出单一的个体，科学家们通过对蚂蚁种群觅食、构建巢穴、任务分配等行为能力的研究发现蚂蚁所特有的控制自身周围环境的能力，早在1989年Cross S等通过著名的双桥实验确定信息素对于蚂蚁觅食过程的指导作用，也为后来蚁群算法的模型建立奠定基础。
关键词： 蚁群算法；研究；发展
中图分类号：TN911 文献标识码：A 文章编号：1671－7597（2012）0210183－01
1 蚂蚁个体的抽象
蚁群算法的起源是模拟自然界中蚂蚁群体行为，但与真实的蚂蚁个体还存在一定的差别，将自然界中的蚂蚁个体进行抽象的目的就是更方便的刻画蚁群的自然行为，同时抛除与问题建模无关的因素。通过这种方式得到的蚂蚁个体可以视为一些智能体，它们之间可以通过一定的机制互相通信、影响，同时也可以共同完成所求问题的简单解的构造过程。
2 问题空间的抽象
蚁群算法是建立在对自然界三维空间的抽象基础之上，通常是用一个二维的平面来代替现实中的蚂蚁觅食三维空间。同时自然界中蚂蚁觅食的空间是一个连续的二维空间，而在计算机模拟的问题模型中多数属于离散事件，因此还需要将所需求解的问题离散化为点组成的解空间。这个抽象过程的可行性在于：尽管蚂蚁是在连续平面中运动，但其运动过程是由离散点所组成，因此对问题空间的抽象过程仅提高了离散化的粒度，与蚂蚁自身的觅食机理没有任何冲突。在多数应用问题中经常使用图（Graph）结构来对问题空间进行描述。
3 觅食路径的抽象
觅食过程中蚁群会在食物和巢穴之间构造一个特定的空间，在这一空间中存在大量的蚁群所固有的信息，这些信息可以指引蚂蚁在此空间中的运动方向，在解决优化问题时，人工蚂蚁在平面节点上搜寻路径的过程就对应了解的构造过程；在人工蚂蚁的运动过程中由平面节点间边上的轨迹提供指导信息，即相当于信息素；人工蚂蚁根据路径上信息素的浓度大小按照一定的概率决定下一步前进的方向，以此类推，经过一定时间之后到达目标节点，这样便可以得到可行解。
4 信息素模型的抽象
自然界中，蚂蚁信息素的挥发是一个连续过程，是与时间相关的连续函数，而在计算机中需要对这个过程进行离散化处理，一般来讲在蚁群算法中以经过一定步长的时间或者完成一次迭代的时间作为固定的时间参数，信息素累积后也会随着时间单位按照一定的比例衰减，因此通过这种离散点间的信息素模型可以完全模拟出自然界中蚂蚁觅食的机理。
5 启发因子模型
通过前文对蚂蚁觅食过程各个因素的抽象，可以对蚂蚁的群体行为进行一个高度的模拟，但这种模拟在演化过程中需要经过一定的迭代，消耗了大量的时间。而在实际应用中往往对算法执行的时间会提出一定的要求，因此在蚂蚁选择离散点空间中的下一步时会用一个随机过程作为诱导，引入了启发因子或称为启发函数。在利用蚁群算法求解的过程中，通常都会根据最终解的特征设定一个初始的指导信息，通过启发函数可以加速蚁群算法的收敛，在解决工程实际问题中更能体现其优越性。
通过对蚂蚁个体、问题空间、觅食路径、信息素模型以及启发因子的抽象，我们可以建立起一个完整的蚁群算法基本模型，通常对蚁群算法的问题空间描述都通过图结构来实现，利用蚁群算法的求解过程是一个自组织过程，任意一个蚂蚁个体都没有全局信息的指导。
蚂蚁个体是蚁群算法中的基本单元，这些个体具有自适应性，并且能够对知识进行动态的积累，这些知识可以通过蚂蚁个体间的相互通讯或者通过在所行走路径上对周围环境的感知来获得。蚁群算法的核心内容是个体的协作与分布规律，在求解过程中，蚂蚁个体的选择通常是由随机决策机制和相互协调机制所引导的。
在蚁群算法中，蚂蚁个体能够根据经验知识以及环境信息不断地组织和学习，对自身的知识库进行重构，因此蚁群算法能够实现自然进化，具有很强的自学能力，环境的变化与算法的学习能力是一对相互作用的因素，这种环境变化的不确定性也加强了算法执行过程中结果的不可预测性。
6 蚁群算法发展
从1996年起的5年时间里，蚁群算法收到了学术界的极大关注，进入了一个飞速发展的时期，1998年，由Dorigo M主持的第一届蚁群算法研讨会在比利时召开，这次会议推动了蚁群算法的研究热潮，2000年，Dorigo M等人总结了蚁群算法已取得的成果以及应用，并发表了第一篇关于蚁群算法的综述研究[31]，为后续的研究奠定了基础。Gutjahr WJ于1999年和2000年对蚁群算法的收敛性进行了证明，Gutjahr WJ将蚁群算法简化为在有向图上行走的过程，以此为基础对图搜索蚁群算法（graph-based ant system，GBAS）的收敛性进行了理论分析。
国内对蚁群算法的研究开始于上世纪末期，最早于1997年东北大学的张纪会博士，徐心和教授对蚁群算法进行了初步的研究。进入了二十一世纪后，更有大量的学者投入到了蚁群算法的研究之中，国内外学者针对蚁群算法已在多个领域应用到实际工作。
综上所述主要对基本蚁群算法进行简单说明。介绍了蚁群算法对个体、问题空间、路径、信息素挥发等一系列问题，蚁群算法源于人们对生物界蚁群觅食行为的观察和模拟，相较于传统的优化方法，蚁群算法在解决各类优化问题时具有很强的适应性和鲁棒性，适用于各类组合优化问题。蚁群算法在使用过程中参数设置简单，易于实现，因此在众多科学研究以及生产制造领域得到了广泛的应用。
参考文献：
[1]邓伟、杨小帆、吴中福，面向系统级故障诊断的高效遗传算法[J].计算机学报，2007，vol30，No.7,1115-1123.
[2]Cross S, Aron S, Deneubourg J L.et al. Self-organized shortcut in the argentine ant[J]. Naturwissenschaften,1989,76:579-581.
[3]Colorni A, Dorigo M, Maniezzo V, et al. Distributed optimization by ant colonies[C].Proceedings of the 1st European Conference on Artificial Life, 1991:134-142.
作者简介：
付欣（1980-），汉族，研究生，吉林工商学院电子信息工程分院；李静（1980-），双学士学位，通信工程师，研究方向：通信或计算机相关方面。
转载注明来源:https://www.xzbu.com/8/view-1601530.htm
