蚁群算法的改进与应用摘要：蚁群算法是一种仿生优化算法，其本质是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。

但是现在蚁群算法还是存在着缺点和不足,需要我们进一歩改进,如：搜索时间长、容易出现搜索停滞现象、数学基础还不完整。

本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点，其次讨论如何利用遗传算法选取蚁群算法的参数，然后结合对边缘检测的蚁群算法具体实现过程进行研究分析，最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后要继续研究学习的工作内容。

关键词：蚁群算法;边缘检测;阈值;信息素;遗传算法;1 前言蚁群算法是近年来提出的一种群体智能仿生优化算法，是受到自然界中真实的蚂蚁群寻觅食物过程的启发而发现的。

蚂蚁之所以能够找到蚁穴到食物之间的最短路径是因为它们的个体之间通过一种化学物质来传递信息，蚁群算法正是利用了真实蚁群的这种行为特征，解决了在离散系统中存在的一些寻优问题。

该算法起源于意大利学者 Dorigo M 等人于 1991 年首先提出的一种基于种群寻优的启发式搜索算法，经观察发现，蚂蚁在寻找食物的过程中其自身能够将一种化学物质遗留在它们所经过的路径上，这种化学物质被学者们称为信息素。

这种信息素能够沉积在路径表面，并且可以随着时间慢慢的挥发。

在蚂蚁寻觅食物的过程中，蚂蚁会向着积累信息素多的方向移动，这样下去最终所有蚂蚁都会选择最短路径。

该算法首先用于求解著名的旅行商问题（Traveling Salesman Problem，简称 TSP）并获得了较好的效果，随后该算法被用于求解组合优化、函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由等问题。

尽管目前对 ACO 的研究刚刚起步，一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此越来越多人开始关注和研究 ACO，初步的研究结果已显示出该算法在求解复杂优化问题（特别是离散优化问题）方面的优越性。

虽然 ACO 的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种自然生物的新型系统寻优思想无疑具有十分光明的前景。

但该算法存在收敛速度慢且容易出现停滞现象的缺点，这是因为并不是所有的候选解都是最优解，而候选解却影响了蚂蚁的判断以及在蚂蚁群体中，单个蚂蚁的运动没有固定的规则，是随机的，蚂蚁与蚂蚁之间通过信息素来交换信息，但是对于较大规模的优化问题，这个信息传递和搜索过程比较繁琐，难以在较短的时间内找到一个最优的解。

由于依靠经验来选择蚁群参数存在复杂性和随机性,因此本文最后讨论如何利用遗传算法选取蚁群算法的参数。

遗传算法得到的蚁群参数减少了人工选参的不确定性以及盲目性。

2 基本蚁群算法2.1 蚁群算法基本原理根据仿生学家的研究结果表明,单只蚂蚁不能找到从巢穴到食物源的最短路径,而大量蚂蚁之间通过相互适应与协作组成的群体则可以,蚂蚁是没有视觉的,但是是通过蚂蚁在它经过的路径上留下一种彼此可以识别的物质,叫信息素,来相互传递信息,达到协作的。

蚂蚁在搜索食物源的过程中,在所经过的路径上留下信息素,同时又可以感知并根据信息素的浓度来选择下一条路径,一条路径上的浓度越浓,蚂蚁选择该条路径的概率越大,并留下信息素使这条路径上的浓度加强,这样会有更多的蚂蚁选择次路径。

相反,信息素浓度少的路径,蚂蚁选择的概率小,该路径随着时间的推移信息素逐渐挥发,而导致以后蚂蚁选择的可能性更小。

最终蚂蚁找出了最优路径同时当运动的路径出现障碍物时,蚂蚁可以很快的适应环境的变化,绕过障碍物重新找到最优路径。

蚂蚁就是通过群体间相互交换信息,自催化行为来实现正反馈过程找到当前最短路径的。

自然界的觅食行为可以通过下图来模拟,并且说明了蚁群群体的搜索原理。

图2.1 蚂蚁从巢穴到食物源的搜索过程如图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路径上的信息素一样,所以将有10只选择BC,10只选择BD。

另外此时有10只蚂奴在C处,10蚂蚁在E处。

当t=8时,在巢穴上的有10只妈蚁,同时CE的中点处、BC的中点处和D点上也各有10只蚂蚁。

当t=9时,已返回巢穴的10只蚂蚁到达E处,此时,CE上的信息素浓度是30，而DE上是40,因此将有较多的蚂蚁选择右侧道路DE,从而增强了该路径上的信息素,使得DE上的信息素浓度比CE的差值变大,直接导致后来的蚂奴选择DE的概率更大,进而又促进它们的信息素浓度差异越来越大,越来越多的蚂蚁选择路径DE,从而最终的结果是所有蚂蚁选择了路径DE,找到了最短路径ABDEF。

蚂蚁通过群体间的协作来寻找食物源的行为过程表现出正反馈现象:一条路径上蚂蚁经过的越多,留下的信息素也就越多,后来的蚂蚁选择该条路径的概率也就越大,从而又促进了该条路径的信息素浓度,最终蚂蚁找到了最短的路径。

2.2蚁群算法数学模型旅行商问题(traveling salesman problem, TSP)是经典的组合优化问题,也是蚁群优化算法最早应用和最为成功的一个例子,并且最初该算法的提出也是在TSP问题上进行了描述。

所以我们这里也以TSP问题为应用背景进行描述。

所谓旅行商问题是指单个旅行商由起点出发,经过连通图中的所有节点并回到出发点所用的最小路径代价。

Dantzig等人于1959年最早提出了旅行社问题的数学模型。

AS (Ant System)是Dorigo等人提出的最早的也是最基础的蚁群算法模型,该算法在TSP 问题的描述如下:设有m只蚂蚊并将它们放在具有n个节点的连通图上,表示t时刻在i,j连线上的信息素,是与问题相关的启发式信息,一般情况下。

初始时刻,各个连通图的边信息素相同,即(C为常数)。

表示第k只蚂蚁目前的路径选择集合。

t时刻蚂蚁k在位置i转移到j的概率表示为:(1)其中,表示第k只蚂蚁当前还能选择的路径总和;α和β分别表示信息素τ和启发式信息η的相对重要程度。

当经过n个时刻后,蚂蚁将完成一次节点的遍历,为了防止信息过多的堆积而造成对蚂蚁选择的影响,这时应该对各个路径上的信息素进行调整,如下:(2)(3)-1表示信息素的挥发率,一般设置ρ在0到1之间,够其中ρ表示信息素的保留率,ρ防止信息的无限积累;表示蚂蚁k在一次循环中在路径i, j留下的信息素浓度;表示本次循环中路径i, j上信息素的总增量,它包含所有蚂蚁在当前循环下在该路径上留下的信息素。

根据信息素更新策略的不同,又可将基本蚁群优化算法分为三类：(1)ant-cycle模型:（4） (2) ant-density模型:（5）(3) ant-quantity模型:（6）L表示第k只蚂蚁在当前其中Q为一个和蚂蚁留在路径上的路径总量相关的一个常数,k循环中的遍历路径总和。

2.3 蚁群算法步骤具体步骤为:步骤1：参数初始化，设置NC为迭代次数，令t=0, NC=0;步骤2：将m只蚂蚁随机放在n个节点，令()00ijτ∆=，设置NC++ ;步骤3：建立禁忌表，计算蚂蚁k的转移概率，选择并移动到下一节点j，同时将j加入到tabuk中;步骤4：tabuk是否满足条件。

若为否，回到步骤3，否则，继续步骤5;步骤5：依据信息素更新公式进行信息素的全局更新;步骤6-保存最短路径，重复执行步骤2到步骤5，直到执行次数NC达到指定的最大迭代次数或连续若干代内没有更好的解出现为止。

图2.2蚁群算法基本流程3 利用遗传算法处理蚁群算法参数3.1遗传算法基本原理遗传算法作为一种求解问题的随机高效全局搜索方法,对其搜索空间无需有先验知识。

而是通过在搜索空间随机产生初始种群,然后在目标函数的作用下,经过个体之间信息的交换,一步步地逼近最优解。

(1)算法设计编码把需要解决的问题进行相应的编码,由于图像灰度值在0-255之间,故将各个染色体编码为8位二进制码。

人口模型若人口数过多,则每一代适应度值的计算量大,但如果人口数过少,又难以体现物种的多样性。

因此人口数设置应该合理。

对于蚁群参数设置人口数为10,最大遗传代数为100。

解码染色体解码为2个0-255之间的值。

适应度函数适应度函数是评价各个体的标准,一定要选择能体现进化的趋势。

在此,选择适应度函数作为蚁群参数选取的依据。

选择遗传算法选择那些适应度高的个体作为产生下一代种群的个体。

交叉交叉是产生新个体的主要方法。

蚁群边缘检测参数分别在前8位和后8位进行单点交叉。

在此设置交叉概率为0.6。

变异变异决定了遗传操作的局部搜索能力。

在此,设置变异概率为0.5。

终止准则规定当算法执行到最大遗传代数时终止。

图3.1 遗传算法流程图（2）蚁群算法图像边缘检测方法基于蚁群算法的边缘检测方法进行图像边缘检测的基本思想:首先边缘检测问题可以转化成基本蚁群算法模型的改进,即将图像抽象为一幅由像素点组成的无向图,其次将设置的人工蚂蚁随机放置在此二维的无向图中,根据各个蚂蚁在其4邻域或者8邻域内可行的像素点上的移动情况计算信息素矩阵,完成设置的迭代次数之后,利用选取的阈值判断边缘点。

其中移动的转移概率根据可行像素点的信息素强度和信息素启发引导函数共同影响求得,蚂蚁的移动方向由其允许移动领域内的像素值的变化决定。

蚁群算法的根本目的旨在通过指导性的探索迭代找到问题的最优解。

基于蚁群算法的边缘检测的核心思想可描述如下:k只蚂蚁被放置在由个像素点组成的空间矩阵上。

①随机放置k只蚂蚁在初始信息素矩阵上。

②初始化迭代步数N。

③根据转移概率公式计算出蚂蚁移动的下个像素点。

④根据信息素的更新规则更新像素点信息素。

⑤根据最终信息素矩阵选取阈值,确定图像边缘像素点。

具体过程如下所示:A.初始化:初始化设置在系统搜索的幵始。

在这个步骤中,进行必要的初始过程。

例如:设参数和分配初始信息的值。

首先放置k个蚂蚁于图像I上(图像由像素点构成),每个像素点被看成是蚂蚁将要爬行的一个无向图中的结点,开始时信息素矩阵被设为。