蚁群算法.doc

蚁群算法的改进与应用
摘要:蚁群算法是一种仿生优化算法,其本质是一个复杂的智能系统,它具有较强的鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。但是现在蚁群算法还是存在着缺点和不足,需要我们进一歩改进,如:搜索时间长、容易出现搜索停滞现象、数学基础还不完整。本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点,其次讨论如何利用遗传算法选取蚁群算法的参数,然后结合对边缘检测的蚁群算法具体实现过程进行研究分析,最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后要继续研究学习的工作内容。
关键词:蚁群算法;边缘检测;阈值;信息素;遗传算法;
1 前言
蚁群算法是近年来提出的一种群体智能仿生优化算法,是受到自然界中真实的蚂蚁群寻觅食物过程的启发而发现的。蚂蚁之所以能够找到蚁穴到食物之间的最短路径是因为它们的个体之间通过一种化学物质来传递信息,蚁群算法正是利用了真实蚁群的这种行为特征,解决了在离散系统中存在的一些寻优问题。该算法起源于意大利学者 Dorigo M 等人于 1991 年首先提出的一种基于种群寻优的启发式搜索算法,经观察发现,蚂蚁在寻找食物的过程中其自身能够将一种化学物质遗留在它们所经过的路径上,这种化学物质被学者们称为信息素。这种信息素能够沉积在路径表面,并且可以随着时间慢慢的挥发。在蚂蚁寻觅食物的过程中,蚂蚁会向着积累信息素多的方向移动,这样下去最终所有蚂蚁都会选择最短路径。该算法首先用于求解著名的旅行商问题(Traveling Salesman Problem,简称 TSP)并获得了较好的效果,随后该算法被用于求解组合优化、函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由等问题。
尽管目前对 ACO 的研究刚刚起步,一些思想尚处于萌芽时期,但人们已隐隐约约认识到,人类诞生于大自然,解决问题的灵感似乎也应该来自大自然,因此越来越多人开始关注和研究 ACO,初步的研究结果已显示出该算法在求解复杂优化问题(特别是离散优化问题)方面的优越性。虽然 ACO 的严格理论基础尚未奠定,国内外的有关研究仍停留在实验探索阶段,但从当前的应用效果来看,这种自然生物的新型系统寻优思想无疑具有十分光明的前景。但该算法存在收敛速度慢且容易出现停滞现象的缺点,这是因为并不是所有的候选解都是最优解,而候选解却影响了蚂蚁的判断以及在蚂蚁群体中,单个蚂蚁的运动没有固定的规则,是随机的,蚂蚁与蚂蚁之间通过信息素来交换信息,但是对于较大规模的优化问题,这个信息传递和搜索过程比较繁琐,难以在较短的时间内找到一个最优的解。
由于依靠经验来选择蚁群参数存在复杂性和随机性,因此本文最后讨论如何利用遗传算法选取蚁群算法的参数。遗传算法得到的蚁群参数减少了人工选参的不确定性以及盲目性。
2 基本蚁群算法
蚁群算法基本原理
根据仿生学家的研究结果表明,单只蚂蚁不能找到从巢穴到食物源的最短路
径,而大量蚂蚁之间通过相互适应与协作组成的群体则可以,蚂蚁是没有视觉的,但是是通过蚂蚁在它经过的路径上留下一种彼此可以识别的物质,叫信息素,来相互传递信息,达到协作的。蚂蚁在搜索食物源的过程中,在所经过的路径上留下信息素,同时又可以感知并根据信息素的浓度来选择下一条路径,一条路径上的浓度越浓,蚂蚁选择该条路径的概率越大,并留下信息素使这条路径上的浓度加强,这样会有更多的蚂蚁选择次路径。相反,信息素浓度少的路径,蚂蚁选择的概率小,该路径随着时间的推移信息素逐渐挥发,而导致以后蚂蚁选择的可能性更小。最终蚂蚁找出了最优路径同时当运动的路径出现障碍物时,蚂蚁可以很快的适应环境的变化,绕过障碍物重新找到最优路径。蚂蚁就是通过群体间相互交换信息,自催化行为来实现正反馈过程找到当前最短路径的。
自然界的觅食行为可以通过下图来模拟,并且说明了蚁群群体的搜索原理。
蚂蚁从巢穴到食物源的搜索过程
如图1,A是食物源,F是巢穴,AB、BD、DE、EF长度都为1,BC、CE长度为2,假设蚂蚁爬行速度为1,一个时间单位蚂蚁在经过的路径上残留信息素为1,所有的路径上的信息素浓度一开始都初始化为0。
当t=0时,在巢穴F处放置40只蚂蚁,它们开始寻找食物源A,当时,它们都到达E处,有两侧道路可以选择,因为CE和DE上没有信息素,所以它们选择左侧道路或右侧道路的概率是一样的,20只蚂蚁走左侧,20只走右侧。
当t=4时,选择了BDE路径的蚂蚁到达食物源,并立即返回,而此时选择了BCE路径的蚂奴正在BC中点处。
当t=5时,正在返回的蚂蚁和正赶往食物源的蚂蚁正好在B处相遇,此时BC和BD路径上的信息素浓度是一样的。所以返回的20只蚂蚁中,有10只将选择BD,10只选择路径BC。
当t=7时,有20只蚂蚁在B处,因为BC和BD路径