蚁群算法基本知识

智能算法第七章：蚁群算法谷俊峰工业装备结构分析国家重点实验室工程力学系运载工程与力学学部7.1蚁群优化算法概述7.2蚁群优化算法的实现7.3蚁群优化算法的研究现状7.4蚁群优化算法——技术问题7.5蚁群优化算法应用现状提纲„蚂蚁属于群居昆虫„单个蚂蚁的行为极其简单,但由这样的单个简单的个体所组成的蚁群群体却表现出极其复杂的行为,能够完成复杂的任务。7.1蚁群优化算法起源7.1蚁群优化算法起源„蚂蚁觅食„蚂蚁没有发育完全的视觉感知系统，甚至很多种类完全没有视觉，他们在寻找食物的过程中是如何选择路径的呢？„蚂蚁往往像军队般有纪律、有秩序的搬运食物，他们是通过什么方式进行群体间的交流协作呢？„大部分的蚂蚁都是按照途中的昀近的路线走，小小的蚂蚁是如何有这么高的智能的呢？7.1蚁群优化算法起源20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。Dorigo„1991年意大利米兰理学院M.Dorigo提出AntSystem,用于求解TSP等组合优化问题。„1995年Gramdardella和Dorigo提出Ant-Q算法，建立了AS和Q-learning的联系。„1996年二人又提出AntColonySystem„1997年有人提出Max-MinAntSystem„1999年Dorigo等人把先前各种算法归结为AntColonyOptimizationmeta-heuristic的统一框架下，给出抽象而规范的算法描述.„目前，被较广泛的应用7.1蚁群优化算法应用领域„蚁群优化算法自1991年由Dorigo提出并应用于TSP问题以来，已经发展了近20年。„具有鲁棒性强、全局搜索、并行分布式计算、易与其他问题结合等优点„应用领域不断扩张，如车间调度问题、车辆路径问题、分配问题、子集问题、网络路由问题、蛋白质折叠问题、数据挖掘、图像识别、系统辨识等。„这些问题大都是NP难的组合优化问题，用传统算法难以求解或者无法求解，各种蚁群算法及其改进版本的出现，为这些难题提供了有效而高效的手段。7.1蚁群算法原理„蚁群是如何完成这些复杂的任务的呢?人们经过大量研究发现,蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递.从而能相互协作,完成复杂的任务.„蚁群之所以表现出复杂有序的行为,个体之间的信息交流与相互协作起着重要的作用.„蚂蚁在运动过程中,能够在它所经过的路径上留下外激素,而且蚂蚁在运动过程中能够感知外激素的存在及其强度,并以此指导自己的运动方向,蚂蚁倾向于朝着外激素强度高的方向移动.„由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大.蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。7.1蚁群算法原理7.1简化的蚂蚁寻食过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。7.1简化的蚂蚁寻食过程本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。7.1简化的蚂蚁寻食过程假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，昀终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。7.1简化的蚂蚁寻食过程食物食物食物巢穴巢穴巢穴7.1简化的蚂蚁寻食过程7.1自然蚁群与人工蚁群算法„基于以上蚁群寻找食物时的昀优路径选择问题，可以构造人工蚁群，来解决昀优化问题，如TSP问题。„人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够昀终被所有蚂蚁选择，也就是昀终的优化结果。„人工蚁群和自然蚁群的区别：„人工蚁群有一定的记忆能力，能够记忆已经访问过的节点；„人工蚁群选择下一条路径的时候是按一定算法规律有意识地寻找昀短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。7.1自然蚁群与人工蚁群算法蚁群觅食蚁群优化算法蚁群蚁群搜索空间的一组有效解（表现为种群规模N）觅食空间觅食空间问题的搜索空间（表现为维数D）信息素信息素信息素浓度变量蚁巢到食物的一条路径蚁巢到食物的一条路径一个有效解找到的昀短路径找到的昀短路径问题的昀优解7.2蚁群优化算法的基本流程„蚂蚁系统是以TSP作为应用实例提出的，是昀基本的ACO算法，比较易于学习和掌握。„本节将以AS求解TSP问题的基本流程为例描述蚁群优化算法的工作机制。蚂蚁系统（AntSystem,AS）TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离目标函数为，其中为城市1,2，…n的一个排列，。{1,2,...,}{(,)|,}NnAijijN==∈nnijd×)(∑=−=nliilldwf11)(),,,(21niiiw=11iin=+7.2蚁群优化算法的基本流程„TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1信息素值也称信息素痕迹。2可见度，即先验值。„信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。„蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近昀优解。„蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。7.2蚁群优化算法的基本流程7.2蚁群优化算法的基本流程AS算法对TSP的求解有两大步骤：路径构建和信息素更新1.路径构建每个蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。•随机比例规则[][]()()()()()0kijijkkikikijkallowedttifjallowedttPtothersαβαβτητη∈⎧⎡⎤⎡⎤×⎣⎦⎣⎦⎪∈⎪×=⎨⎪⎪⎩∑ijijd/1=η)(tijτβα,zi、j分别为起点和终点；z为能见度，是两点i、j路距离的倒数；z为时间t时由i到j的信息素强度；zallowedk为尚未访问过的节点集合；z为两常数，分别是信息素和能见度的加权值。7.2蚁群优化算法的基本流程7.2蚁群优化算法的基本流程2.信息素更新初始化信息素浓度如果C太小，算法容易早熟，蚂蚁会很快的全部集中到一条局部昀优的路径上。反之，如果C太大，信息素对搜索方向的指导作用太低，也会影响算法性能。AS中：jiCij,,∀=τ/nnCmC=1()(1)mkijijijktτρττ==−+Δ∑为了模拟蚂蚁在较短路径上留下更多的信息素，当所有蚂蚁到达终点时，必须把各路径的信息素浓度重新更新一次，信息素的更新也分为两个步骤m为蚂蚁个数，0ρ=1为信息素的蒸发率，在AS中通常设置为0.5，为第k只蚂蚁在路径i到j所留下來的信息素kijτΔ„首先，每一轮过后，问题空间中的所有路径上的信息素都会发生蒸发„然后，所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素7.2蚁群优化算法的基本流程„的定义Ck是第k只蚂蚁走完整条路径后所得到的总路径长度kijτΔ1()(,)0thkkijCifthekanttraversesijothersτ−⎧Δ=⎨⎩7.2蚁群优化算法的基本流程信息素更新的作用1.信息素挥发（evaporation）信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，这个挥发过程主要用于避免算法过快地向局部昀优区域集中，有助于搜索区域的扩展。2.信息素增强（reinforcement）增强过程是蚁群优化算法中可选的部分，称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂蚁无法实现的集中行动。基本蚁群算法的离线更新方式是在蚁群中的m只蚂蚁全部完成n城市的访问后，统一对残留信息进行更新处理。7.2蚁群优化算法的基本流程ProcedureASforeachedgesetinitialpheromonevaluet0endforwhilenotstopforeachantkrandomlychooseaninitialcityfori=1tonchoosenextcityjwithprobabilityendforendforcomputethelengthCkofthetourconstructedbythekthantforeachedgeupdatethepheromonevalueendforendwhileprintresultendprocedureTSP问题的蚁群算法伪代码7.2蚁群优化算法的基本流程四个城市的TSP问题，距离矩阵和城市图示如下：03123054()15022420ijDd⎛⎞⎜⎟⎜⎟==⎜⎟⎜⎟⎝⎠应用举例ACDB7.2蚁群优化算法的基本流程假设共m=3只蚂蚁，参数α=1，β=2，ρ=0.500.30.30.30.300.30.3(0)((0))0.30.300.30.30.30.30ijττ⎛⎞⎜⎟⎜⎟==⎜⎟⎜⎟⎝⎠步骤1初始化首先使用贪婪算法得到路径的(ACDBA),则Cnn=1+2+4+3=10，求得τ0=m/Cnn=0.37.2蚁群优化算法的基本流程步骤2为每个蚂蚁随机选择出发城市，假设蚂蚁1选择城市A，蚂蚁2选择城市B，蚂蚁3选择城市D7.2蚁群优化算法的基本流程步骤3.1为每个蚂蚁选择下一访问城市，仅以蚂蚁1为例当前城市i=A，可访问城市集合J1(i)={B,C,D}计算蚂蚁1访问各个城市的概率121212:0.3(1/3)0.033:0.3(1/1)0.300:0.3(1/2)0.075()0.033/(0.0330.30.075)0.081()0.3/(0.0330.30.075)0.74()0.075/(0.0330.30.075)0.18aABABaACACaADADBACDpBpCpDβββτητητη⎧×=+=⎪⇒×=+=⎨⎪×=+=⎩=++==++==++=用轮盘赌法选择下一个访问城市。假设产生的随机数q=0.05，则蚂蚁1会选择城市B同样，假设蚂蚁2选择城市D，蚂蚁3选择城市A。7.2蚁群优化算法的基本流程步骤3.2为每个蚂蚁选择下一访问城市，仅以蚂蚁1为例当前城市i=B，路径记忆向量Rl=(AB),可访问城市集合J1(i)={C,D}计算蚂蚁1访问C,D城市的概率:1212:0.3(1/5)0.012:0.3(1/4)0.019()0.012/(0.0120.019)0.39()0.019/(0.0120.019)0.61aBCBCaBDBDCBDpCpDββτητη⎧×=+=⎪⇒⎨×=+=⎪⎩=+==+=用轮盘赌法选择下一个访问城市。假设产生的随