蚁群算法

《蚁群算法》由会员分享，可在线阅读，更多相关《蚁群算法（15页珍藏版）》请在金锄头文库上搜索。

1、蚁群算法的改进与应用蚁群算法的改进与应用 摘要：蚁群算法是一种仿生优化算法，其本质是一个复杂的智能系统，它具有较强的 鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。但是现在蚁群算法还是存 在着缺点和不足,需要我们进一歩改进,如：搜索时间长、容易出现搜索停滞现象、数学基 础还不完整。本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点，其 次讨论如何利用遗传算法选取蚁群算法的参数，然后结合对边缘检测的蚁群算法具体实现 过程进行研究分析，最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后 要继续研究学习的工作内容。 关键词：蚁群算法;边缘检测;阈值;信息素;遗传算

2、法;1 1 前言前言蚁群算法是近年来提出的一种群体智能仿生优化算法，是受到自然界中真实的蚂蚁群 寻觅食物过程的启发而发现的。蚂蚁之所以能够找到蚁穴到食物之间的最短路径是因为它 们的个体之间通过一种化学物质来传递信息，蚁群算法正是利用了真实蚁群的这种行为特 征，解决了在离散系统中存在的一些寻优问题。该算法起源于意大利学者 Dorigo M 等人 于 1991 年首先提出的一种基于种群寻优的启发式搜索算法，经观察发现，蚂蚁在寻找食 物的过程中其自身能够将一种化学物质遗留在它们所经过的路径上，这种化学物质被学者 们称为信息素。这种信息素能够沉积在路径表面，并且可以随着时间慢慢的挥发。在蚂蚁 寻觅食物

3、的过程中，蚂蚁会向着积累信息素多的方向移动，这样下去最终所有蚂蚁都会选 择最短路径。该算法首先用于求解著名的旅行商问题（Traveling Salesman Problem，简 称 TSP）并获得了较好的效果，随后该算法被用于求解组合优化、函数优化、系统辨识、 机器人路径规划、数据挖掘、网络路由等问题。 尽管目前对 ACO 的研究刚刚起步，一些思想尚处于萌芽时期，但人们已隐隐约约认识 到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此越来越多人开始关 注和研究 ACO，初步的研究结果已显示出该算法在求解复杂优化问题（特别是离散优化问 题）方面的优越性。虽然 ACO 的严格理论基础尚

4、未奠定，国内外的有关研究仍停留在实验 探索阶段，但从当前的应用效果来看，这种自然生物的新型系统寻优思想无疑具有十分光 明的前景。但该算法存在收敛速度慢且容易出现停滞现象的缺点，这是因为并不是所有的 候选解都是最优解，而候选解却影响了蚂蚁的判断以及在蚂蚁群体中，单个蚂蚁的运动没 有固定的规则，是随机的，蚂蚁与蚂蚁之间通过信息素来交换信息，但是对于较大规模的 优化问题，这个信息传递和搜索过程比较繁琐，难以在较短的时间内找到一个最优的解。 由于依靠经验来选择蚁群参数存在复杂性和随机性,因此本文最后讨论如何利用遗传算 法选取蚁群算法的参数。遗传算法得到的蚁群参数减少了人工选参的不确定性以及盲目性。2

5、2 基本蚁群算法基本蚁群算法2.12.1 蚁群算法基本原理蚁群算法基本原理根据仿生学家的研究结果表明,单只蚂蚁不能找到从巢穴到食物源的最短路 径,而大量蚂蚁之间通过相互适应与协作组成的群体则可以,蚂蚁是没有视觉的,但是是通过 蚂蚁在它经过的路径上留下一种彼此可以识别的物质,叫信息素,来相互传递信息,达到协作 的。蚂蚁在搜索食物源的过程中,在所经过的路径上留下信息素,同时又可以感知并根据信 息素的浓度来选择下一条路径,一条路径上的浓度越浓,蚂蚁选择该条路径的概率越大,并留 下信息素使这条路径上的浓度加强,这样会有更多的蚂蚁选择次路径。相反,信息素浓度少的路径,蚂蚁选择的概率小,该路径随着时间的推

6、移信息素逐渐挥发,而导致以后蚂蚁选择的 可能性更小。最终蚂蚁找出了最优路径同时当运动的路径出现障碍物时,蚂蚁可以很快的适 应环境的变化,绕过障碍物重新找到最优路径。蚂蚁就是通过群体间相互交换信息,自催化 行为来实现正反馈过程找到当前最短路径的。 自然界的觅食行为可以通过下图来模拟,并且说明了蚁群群体的搜索原理。图 2.1 蚂蚁从巢穴到食物源的搜索过程 如图 1,A 是食物源,F 是巢穴,AB、BD、DE、EF 长度都为 1,BC、CE 长度为 2,假设蚂蚁 爬行速度为 1,一个时间单位蚂蚁在经过的路径上残留信息素为 1,所有的路径上的信息素浓 度一开始都初始化为 0。 当 t=0 时,在巢穴

7、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

8、和 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

9、,从而最终的结果是所有蚂蚁选择了路 径 DE,找到了最短路径 ABDEF。蚂蚁通过群体间的协作来寻找食物源的行为过程表现出正反 馈现象:一条路径上蚂蚁经过的越多,留下的信息素也就越多,后来的蚂蚁选择该条路径的概 率也就越大,从而又促进了该条路径的信息素浓度,最终蚂蚁找到了最短的路径。2.22.2 蚁群算法数学模型蚁群算法数学模型旅行商问题(traveling salesman problem, TSP)是经典的组合优化问题,也是蚁群优化算法最早应用和最为成功的一个例子,并且最初该算法的提出也是在 TSP 问题上进行了描 述。所以我们这里也以 TSP 问题为应用背景进行描述。 所谓旅行商问题是指

10、单个旅行商由起点出发,经过连通图中的所有节点并回到出发点所 用的最小路径代价。Dantzig 等人于 1959 年最早提出了旅行社问题的数学模型。 AS (Ant System)是 Dorigo 等人提出的最早的也是最基础的蚁群算法模型,该算法在 TSP 问题的描述如下:设有 m 只蚂蚊并将它们放在具有 n 个节点的连通图上,表示 t 时刻在 i,j 连线上的信息素,是与问题相关的启发式信息,一般情况下。 初始时刻,各个连通图的边信息素相同,即(C 为常数)。表示第 k 只蚂蚁 目前的路径选择集合。t 时刻蚂蚁 k 在位置 i 转移到 j 的概率表示为:(1)其中,表示第 k 只蚂蚁当前还能选

11、择的路径总和;和分别表示信息素和启发式信息的相对重要程度。 当经过 n 个时刻后,蚂蚁将完成一次节点的遍历,为了防止信息过多的堆积而造成对蚂 蚁选择的影响,这时应该对各个路径上的信息素进行调整,如下:(2)(3)其中表示信息素的保留率,表示信息素的挥发率,一般设置在 0 到 1 之间,够-1防止信息的无限积累;表示蚂蚁 k 在一次循环中在路径 i, j 留下的信息素浓度;表 示本次循环中路径 i, j 上信息素的总增量,它包含所有蚂蚁在当前循环下在该路径上留下 的信息素。根据信息素更新策略的不同,又可将基本蚁群优化算法分为三类： (1) ant-cycle 模型:（4）(2) ant-dens

12、ity 模型:（5） (3) ant-quantity 模型:（6）其中 Q 为一个和蚂蚁留在路径上的路径总量相关的一个常数,表示第 k 只蚂蚁在当kL前循环中的遍历路径总和。2.32.3 蚁群算法步骤蚁群算法步骤具体步骤为:步骤 1：参数初始化，设置 NC 为迭代次数，令 t=0, NC=0;步骤 2：将 m 只蚂蚁随机放在 n 个节点，令，设置 NC+ ; 00ij步骤 3：建立禁忌表，计算蚂蚁 k 的转移概率，选择并移动到下一节点 j，同时将 j 加 入到 tabuk 中; 步骤 4：tabuk 是否满足条件。若为否，回到步骤 3，否则，继续步骤 5; 步骤 5：依据信息素更新公式进行信

13、息素的全局更新; 步骤 6-保存最短路径，重复执行步骤 2 到步骤 5，直到执行次数 NC 达到指定的最大迭 代次数或连续若干代内没有更好的解出现为止。图 2.2 蚁群算法基本流程3 3 利用遗传算法处理蚁群算法参数利用遗传算法处理蚁群算法参数3.13.1 遗传算法基本原理遗传算法基本原理遗传算法作为一种求解问题的随机高效全局搜索方法,对其搜索空间无需有先验知识。 而是通过在搜索空间随机产生初始种群,然后在目标函数的作用下,经过个体之间信息的交 换,一步步地逼近最优解。 (1)算法设计 编码编码 把需要解决的问题进行相应的编码,由于图像灰度值在 0-255 之间,故将各个染色 体编码为 8 位

14、二进制码。 人口模型人口模型 若人口数过多,则每一代适应度值的计算量大,但如果人口数过少,又难以体现物种的多样性。因此人口数设置应该合理。对于蚁群参数设置人口数为 10,最大遗传代 数为 100。 解码解码 染色体解码为 2 个 0-255 之间的值。 适应度函数适应度函数 适应度函数是评价各个体的标准,一定要选择能体现进化的趋势。在此, 选择适应度函数作为蚁群参数选取的依据。 选择遗传算法选择遗传算法 选择那些适应度高的个体作为产生下一代种群的个体。 交叉交叉 交叉是产生新个体的主要方法。蚁群边缘检测参数分别在前 8 位和后 8 位进行 单点交叉。在此设置交叉概率为 0.6。 变异变异 变异

15、决定了遗传操作的局部搜索能力。在此,设置变异概率为 0.5。 终止准则终止准则 规定当算法执行到最大遗传代数时终止。图 3.1 遗传算法流程图 （2）蚁群算法图像边缘检测方法 基于蚁群算法的边缘检测方法进行图像边缘检测的基本思想:首先边缘检测问题可以转 化成基本蚁群算法模型的改进,即将图像抽象为一幅由像素点组成的无向图,其次将设置的 人工蚂蚁随机放置在此二维的无向图中,根据各个蚂蚁在其 4 邻域或者 8 邻域内可行的像素 点上的移动情况计算信息素矩阵,完成设置的迭代次数之后,利用选取的阈值判断边缘点。 其中移动的转移概率根据可行像素点的信息素强度和信息素启发引导函数共同影响求得,蚂 蚁的移动方

16、向由其允许移动领域内的像素值的变化决定。 蚁群算法的根本目的旨在通过指导性的探索迭代找到问题的最优解。基于蚁群算法的 边缘检测的核心思想可描述如下: k 只蚂蚁被放置在由个像素点组成的空间矩阵上。 随机放置 k 只蚂蚁在初始信息素矩阵上。 初始化迭代步数 N。根据转移概率公式计算出蚂蚁移动的下个像素点。根据信息素的更新规则更新像素点信息素。根据最终信息素矩阵选取阈值,确定图像边缘像素点。具体过程如下所示:A.初始化:初始化设置在系统搜索的幵始。在这个步骤中,进行必要的初始过程。例如:设参数和分配 初始信息的值。首先放置 k 个蚂蚁于图像 I 上(图像由像素点构成),每个像素点被看成是蚂蚁将要爬行的一个无向图中的结点,开始时信息素矩阵被设为。B.初步构建: 从 k 个蚂蚁中随机选择一只,令其在图像矩阵(由像素点组成的图像矩阵)上移动规定移动步数。计算从像素点(l,m)到像素点(i,j)的转移概率值像素点(i,j)为相邻的允许范围内的像素点,搜索过程中的状态转移概率公式表示如下:（7）这里表示第 n-1