下载文档原格式
蚁群算法目录1 蚁群算法基本思想 (1)1.1蚁群算法简介 (1)1.2蚁群行为分析 (1)1.3蚁群算法解决优化问题的基本思想 (2)1.4蚁群算法的特点 (2)2 蚁群算法解决TSP问题 (3)2.1关于TSP (3)2.2蚁群算法解决TSP问题基本原理 (3)2.3蚁群算法解决TSP问题基本步骤 (5)3 案例 (6)3.1问题描述 (6)3.2解题思路及步骤 (6)3.3MATLB程序实现 (7)3.1.1 清空环境 (7)3.2.2 导入数据 (7)3.3.3 计算城市间相互距离 (7)3.3.4 初始化参数 (7)3.3.5 迭代寻找最佳路径 (7)3.3.6 结果显示 (7)3.3.7 绘图 (7)1 蚁群算法基本思想1.1 蚁群算法简介蚁群算法（ant colony algrothrim ，ACA ）是由意大利学者多里戈（Dorigo M ）、马聂佐（ Maniezzo V ）等人于20世纪90初从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来的一种新型的模拟进化算法。
该算法用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些系统优化中的困难问题，其算法的基本思想是模仿蚂蚁依赖信息素，通过蚂蚁间正反馈的方法来引导每个蚂蚁的行动。
蚁群算法能够被用于解决大多数优化问题或者能够转化为优化求解的问题，现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS 管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面。
蚁群算法是群智能理论研究领域的一种主要算法。
1.2 蚁群行为分析EABCDF d=3d=2 m=20 t=0AB C Dd=3d=2 m=10 m=10t=11.3 蚁群算法解决优化问题的基本思想用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。
路径较短的蚂蚁释放的信息量较多，随着时间的推进，较短路径上积累的信息浓度逐渐增高，选择该路径的蚂蚁个数愈来愈多。
蚁群算法基本原理
蚁群算法（Ant Colony Algorithm）是一种基于模拟蚁群行为的优化算法，用于解决复杂的优化问题。
其原理是模拟蚂蚁寻找食物的行为，在寻找过程中通过信息素来引导蚂蚁探索最优解。
基本流程：
1. 初始化：将蚂蚁随机分散在问题空间中，每只蚂蚁都随机选择一个起点。
2. 蚂蚁搜索：每只蚂蚁根据一定的概率选择下一个节点，概率与当前节点的信息素有关，如果信息素较高则该节点被选中的概率较大。
3. 信息素更新：每只蚂蚁在搜索过程中会留下一定的信息素，当搜索完成后，信息素会根据一定的规则进行更新，具体规则可以为：信息素浓度与路径长度成反比例关系，或者信息素挥发速度固定。
4. 最优解记录：当所有蚂蚁完成搜索后，从它们所走过的路径中选择获得最优解，并将该路径上的信息素浓度进行更新。
5. 重复搜索：重复上述所有步骤，直到达到设定的迭代次数或者满足终止条件。
蚁群算法基本原理就是通过模拟蚁群行为，通过信息素的引导来搜索最优解。
在
实际应用中，蚁群算法可以用于解决诸如旅行商问题、作业调度问题、路径规划问题、图像分割问题等优化问题。
蚁群算法公式蚁群算法(AntColonyAlgorithm)是一种基于自然生态的数学优化模型，是一个迭代的搜索算法，用来解决动态规划问题。
这种算法是在蚂蚁群体行为的理论的基础上发展出来的，通过模拟蚂蚁如何寻找最佳的路径来寻找最优解。
它是一种用于解决复杂优化问题的自然计算算法，它可以分析解决复杂系统中大量变量和限制条件所建立的非线性优化问题。
蚁群算法是一种基于概率的搜索算法，它采用“相互学习”的方式，通过种群间的信息共享，形成一个多维度的相互关联的搜索空间。
由于蚁群算法可以获得更多关于搜索空间的信息，它比传统的优化算法更有效地搜索最优解。
蚁群算法是一种非治疗性的优化算法，它可以用来解决多种复杂的优化问题，如全局优化、组合优化、最佳化框架优化以及机器学习等。
蚁群算法是基于规则的智能算法，它包括四个主要部分：蚁群、时间、规则和变量。
在运行蚁群算法的过程中，先生成一组初始解，再根据算法的规则（也可称为搜索引擎）进行蚁群迭代，每次迭代会更新解的模型和搜索空间的参数，直到达到最优解。
蚁群算法的核心公式如下：第一步：更新ij：ρij = (1-ρ)*ij +*Δρij其中，ρji表示节点i到j转移的概率ρ为一个参数，表示蚂蚁搜索行为的一致性Δρji为一个参数，表示节点i到j路径的通过数量第二步：更新ρij：Δρij = q/Lij + (1-q)*Δρij其中，Lij表示节点i到j路径的长度q为一个参数，表示蚂蚁搜索行为的一致性Δρji为一个参数，表示节点i到j路径的通过数量第三步：更新tij：tij = (1-ρ)*tij +*Δtij其中，tji表示节点i到j转移的概率ρ为一个参数，表示蚂蚁搜索行为的一致性Δtij为一个参数，表示节点i到j路径的通过次数以上就是蚁群算法的核心公式，它结合了蚂蚁的行为，通过迭代的方式，找到最佳的路径，路径的长度由节点之间转移的概率决定，路径的变化则由节点之间通过的次数来决定。
蚂蚁是自然界中常见的一种生物，在昆虫世界，蚂蚁是一种群居的世袭大家庭，我们称之为蚁群（ant colony）。
蚁群具有高度组织的社会性，彼此间的沟通不仅可以借助触觉、视觉的联系，在大规模的协调行动上可以借助外激素（pheromone）之类的生产化信息介质。
蚁群的觅食行为是最易观察的，每只蚂蚁具有如下的职能：平时在巢穴附近作无规则行走，一旦发现食物，如果独自能搬的就往回搬，否则就回巢搬兵，一路上它会留下外激素的嗅迹，其强度通常与食物的品质和数量成正比；若其他蚂蚁遇到嗅迹，就会循迹前进，但也会有一定的走失率，走失率与嗅迹的强度成反比，从而相互协作，完成复杂的任务。
1991年意大利学者M.Dorigo等人首先提出了蚁群算法(ant colony algorithm)，人们开始了对蚁群的研究：相对弱小，功能并不强大的个体是如何完成复杂的工作的，因此在此基础上，蚁群算法从对蚁群行为的研究中产生且逐渐发展起来。
蚁群算法是一种随机搜索算法。
诸多研究证明，蚁群算法具有很强的寻优能力，不仅利用正反馈原理，在一定程度上加快了寻优过程，而且是一种本质并行算法，不同个体之间进行信息交流和传递，从而相互协作，有利于发现更好解。
它具有以下优点[3]：（1）较强的通用性：对基本蚁群算法模型稍加修改，便可以应用于其他问题。
（2）分布式计算：蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。
（3）易于与其它方法结合：蚁群算法很容易与多种启发式算法结合，以改善算法的性能。
蚁群算法也有一些缺陷：（1）需要较长的搜索时间：由于蚁群中多个个体的运动是随机的，虽然通过信息的交流能够向着最优路径进化，但是当群体规模较大时，很难在短时间内从复杂无章的路径中找出一条较好的路径。
（2）容易出现停滞现象（stagnation behavior）：即在搜索进行到一定程度后，所有个体所发现的解完全一样，不能对解空间进一步进行搜索，不利于发现更好的解。
蚁群算法的改进与应用摘要：蚁群算法是一种仿生优化算法，其本质是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。
但是现在蚁群算法还是存在着缺点和不足,需要我们进一歩改进,如：搜索时间长、容易出现搜索停滞现象、数学基础还不完整。
本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点，其次讨论如何利用遗传算法选取蚁群算法的参数，然后结合对边缘检测的蚁群算法具体实现过程进行研究分析，最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后要继续研究学习的工作内容。
关键词：蚁群算法;边缘检测;阈值;信息素;遗传算法;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上(图像由像素点构成),每个像素点被看成是蚂蚁将要爬行的一个无向图中的结点,开始时信息素矩阵被设为。
