蚁群优化算法讲稿.ppt

1、数学系 凌军,蚁群优化 Ant Colony Optimization,第篇 组合优化问题与元启发式算法 第篇 ACO原理及其实现 第篇 ACO理论及应用,第篇 组合优化问题与元启发式算法,1.1 组合优化问题 1.2 计算复杂度 1.3 组合优化问题求解方法 1.4 元启发式算法 1.5 结语,第篇 组合优化问题与元启发式算法,1.1 组合优化问题 组合优化问题涉及找到一组离散变量的值，使得所给定的目标函数的解达到最优。 从形式化的角度来看，组合优化问题是一个三元组 其中 是候选解（candidate solution）的集合； 是目标函数，对于每一个候选集 都对应着一个目标函数值 ； 是约

2、束条件的集合，集合 中满足约束条件 的解被称为可行解（feasible solution)。优化的目标就是找出一个全局最优的可行解 。求最小值的问题（也就是最小化问题）就是要找到一个具有最小成本代价的解 ，即一个对于所有 都有 而求最大值的问题（也就是最大化问题）就是要找出一个具有最大目标值的解，即一个对于所有的 都有 。,1.2 计算的复杂度 通常，对算法效率在理论上的探讨又称为算法的事前估计，可分为算法的时间复杂度分析和空间复杂度分析。 定义1.1 算法空间复杂度是指算法执行时间内所占用的存储单元的大小。 定义1.2 算法的时间复杂度是指算法执行基本操作的次数。这里我们将求解该问题的所有关

3、键操作（如加、减、乘、除、比较等运算）指定为基本操作。,定义1.3 最差时间复杂度指的是对于每个可能的输入规模为 的问题算法求解该问题时找到一个解所需的最长时间。 一个算法的最差时间复杂度常常采用符号 来表示。给定两个函数 和 ，若存在两个正常数 与 ，对一切的 时有 则称 是以 为界的，那么函数 的最差时间复杂度就为 。换句话说，符号 给出了算法在最差时间复杂度上的渐进上限值，它表示的是一个数量级的概念。 若一个算法对应的时间复杂度为 ，而 是一个多项式函数，则称该算法为多项式时间算法；若 不是多项式则称该算法为指数级时间算法。,P、NP、NP-C、NP-hard问题描述,一种刻画组合问题难

4、度的重要理论就是所谓的NP完全性理论，在NP完全性理论中通常使用图灵机，关于这部分的详细内容请参考Garey和Johnson（1979）的文章。,图灵（A.Turing）1912年出生于伦敦。他1936年的论文论可计算数及其在判定问题中的应用是阐明现代计算与计算机原理的开山之作。论文围绕着一个基础数学问题：只要有足够的计算时间数学函数是否都能经过有限次机械步骤得出解答？为了弄清楚计算机能够解决哪些问题，他提出了后来被称作“图灵机”的可计算性理论。1937年，他的论文基于序数的逻辑系统进一步展开了关于这个问题的逻辑探索。,定义1.4 图灵机 图灵机概念最早由英国数学家Turing提出，其本质是由

5、两部分组成：一部分是一个无限长的磁带，磁带被分割成一个个的小方格，每个小方格装有符号0或1；另一部分是检测头，它能沿着磁带前后移动，一次移动一个小方格，并能读出当前小方格的符号。检测头可以不改变小方格的值，也能将新值写进小方格。在操作的每一步，我们假定检测头处于有限设置中的一个，称其为状态。,检测头可能采取的行动：,1. 向左移动一个小方格 2. 向右移动一个小方格 3. 用1改写当前小方格的值 4. 用0改写当前小方格的值 5. 保持目前的状态 6. 从目前的状态改变到其他状态 7. 停止,例、用图灵机来计算1加2,机器在运行之初，磁带上所有的小方格值均为0， 首先，我们把一个1和另外两个连

6、续的1放在磁带 上，并在它们之间放上0使之分隔，这代表这是两 个独立的数字； 其次，设计一个计算加法的程序，完成这个运算 的机器需要有三个状态A、B、C,这个程序的结果是：当机器停止时，磁带上将会 出现三个连续的1，其他地方全是0。,图灵机是对算法进行分析和研究算法复杂度的 得力工具，可分为确定性单带图 灵（deterministic one-tape Turing machine,DTM）和非确定性单带 图灵机（nondeterministic onetapeTuringmaching NDTM）两大类。,一个DTM程序应包括以下信息：,（1）线性带中所用字符的一个有限集合 。,（2）一个有

7、限状态集 ，它包括初始状态 和 两个特有的停机状态 或 。,（3）一个转移函数 。,非确定性单带图灵机NDTM完全是一种假象的机 器，通常多用猜想模块来对其进行描述。,猜想模块： （1）猜想模块起作用时检测头内的状态模块不起作用。 （2）在被扫描的带格中写下某一字符并左移一格。 （3）停止。若停止则猜想模块不在起作用。,定义1.5 实例 实例是问题的特殊表现，是确 定了描述问题特性的所有参数的问题，其中参数 值称为数据，这些数据占用计算机的空间称为数 据实例的输入长度。,定义1.6 P类问题 所有可用DTM在多项式时间 内求解的判定问题 的集合，简记为 。 即,其中 表示程序 所识别的语言。,

8、P类问题的每个实例只有“是”或“否”两种回答， 并称肯定回答为“是”实例；称否定回答为“否”实例。,定义1.7 NP(non-deterministic poly-nominal)类问题 若存在一个多项式函数 和一个验证算法 ，对一 类判定问题 的任何一个“是”回答，满足其输入长度 不超过 ，其中 为 的输入长度，且验证 算法中 为 的“是”回答的计算时间不超过 ，则 称判定问题 为非多项式确定问题，简称NP类问题。 NP类问题是所有可用NDTM在多项式时间内求解的 判定问题 的集合。,判定问题是否属于NP类问题的关键是对“是”的 判定实例是否存在满足上述条件的一个字符串和 算法，其中字符串在

9、此可理解为问题的一个解， 而定义中没有强调字符串和算法是如何得到的。 能用DTM在多项式时间内解决的P类问题，也一 定能用NDTM在多项式时间内加以解决，这个关 系可表示为 。,然而，在当前的计算复杂度理论中，尚没有 解决是否兼属P类或NP类的问题，即证明 的难度和证明 的难度同样大。,归纳和转换是描述问题特性的常用方法，若 能将几类问题归结为一个问题，这样一旦解决 了一类归结后的问题，其他几类问题也就相当 于解决了。,定义1.8 给定问题 和 ，若存在一个多项式 函数 和一个字符串满足： （1）对于 的任何一个实例 ，在其输入长 度的多项式时间 内构造 的一个实例 ， 使其长度不超过 ; （

10、2）由此构造使得实例 和 的解一一对应 且 为 的“是”回答的充要条件为 对应的解是 的一个“是”回答。 则称 可以转换为 。,定义1.9 给定判定问题 和 ，若存在多项 式函数 和 ，使得对 的任何一个实例 在多项式时间内构造 的一个实例，其输入长度 不超过 ，并对 的任何一个算法 ，都存 在问题 的一个算法 ，使得计算时间满足： 则称 可多项式归纳为 。,由此可见，若问题 存在多项式时间算法， 则问题 一定存在多项式时间算法。且对 的 一个算法 ，可以按照如下步骤构造 的算法： （1）对问题 的任何一个实例 ，先用多项式 时间 构造问题 的一个实例 ； （2）调用算法 求解 ，此步计算时间

11、为 如此构造的算法对问题 的任何一个实例 的 计算时间不超过,定义1.10 NP-C(NP-comlete)类问题 它是NP 类问题中最困难的一类问题。所有的NP-C问题是 同等困难的，每一个NP类问题都可以用多项式算 法转换至NP-C。因此，如果NP-C类问题中有一个 问题能用多项式确定性算法解决，则其他所有的 NP-C类问题都能用多项式确定性算法来解决。,NP-C类问题具有重要的实际意义和工程背景， 许多问题被证明为NP-C类问题，如TSP、VRP QAP、GCP等。此外，NP-C类问题也是检验仿 生优化算法有效性和可靠性的有效平台。,定义1.11 NP-hard类问题 若 且NP类问题

12、中的任何一个问题可多项式归约为问题 ，称判定 问题 -C；只要上述第二个条件成立，就称问 题为NP-hard类问题。,由此可见NP-C NP-hard，而且两者之间的区别 仅在于NP-C必须判断问题属于NP类。同时，若已知 一个问题A为NP-C或NP-hard，当遇到一个新问题B 时，若已知问题可多项式归约为新问题B，则B为 NP-hard类问题，进而若可验证新问题B属于NP类， 则B为NP-C类问题。,P、NP、NP-C、NP-hard类问题之间的逻辑关系图,1.3 组合优化问题求解方法,对于组合优化问题的求解存在两种类型的方法：确定性算法和近似算法。 确定性算法（exact algorit

13、hm）可以保证找到问题的最优解，而且事实已经证明对于任何规模有限的组合优化问题实例来说，算法都可以在一个与问题有关的运行时间内得到最优解。但是往往对于一个比较复杂的问题确定性算法需要指数级的时间来寻找最优解。这就有点不太实际。 如果在实际应用中不能有效地得到最优解，唯一可行的方法就是降低最优值的精度以换取计算效率的提高。换句话说，为了可以在多项式时间内求得比较好的解，可以以牺牲找到最优解的保证作为代价。,1.3 组合优化问题求解方法,近似算法（approximate algorithm）是寻求在相对较低的计算成本下找到好的或接近最优解的解答，但是算法并不保证一定能够找到最优解。而近似算法在非严

14、格定义下被称作启发式算法（heuristic methods）。,基于算法使用的基本技巧，近似算法可以分为构建性算法和局部搜索算法 构建性算法（construction）是从最初的空解开始，迭代地添加解成分到解中去，直到完全构建解。例如在TSP中，解的构建性就是通过逐个添加城市而达到的。尽管在近似算法中，构建性算法是典型的快速算法，然而在大多数情况下算法生成的解要比由局部搜索算法找到的解要差。,最常用的构建性算法是贪婪构建性启发式算法其在每一构建步上添加由启发式函数评估得出的具有最大近似利益的解来构建完整解。针对TSP的一个贪婪构建性算法的例子就是最近邻算法，它把城市看做是解的成分，整个工作过

15、程的第一步就是随机选择一个起始城市，然后再构建过程中迭代地从余下的城市中选择出最靠近的城市添加到解中，如果存在两个或多个最靠近的城市距离相同，则任意选择一个,例、TSP的最近邻过程,从城市A出发，依次添加城市B,C,D,E和F,局部搜索（local search）最初从某些解开始，不断通过局部调整来尝试改进当前解。应用局部搜索的第一步就是定义候选集上的领域结构，实际上，领域结构所定义的是每一个当前解通过局部搜索算法可以到达的可能解的集合，一种比较常用的方法就是通过 -交换移动得到的，即把解中的 个成分与另外 个不同的成分进行交换。 局部搜索算法是在当前解的领域中搜索更好的改进解，如果找到一个更

16、好的改进解，它将会取代当前解并继续执行局部搜索。这些步骤不断重复，直到在邻域中再也找不到更好单改进解时算法就终止于一个局部最优解上。局部搜索的一个缺点就是算法可能会终止在一个非常差单局部最优上。,例、TSP中的2-交换,给定一个候选解 ，TSP候选解 的2-交换邻域由使用所有可能的方法交换 中的两条边而得到的所以候选解 的集合组成。,显然，-交换域就是用 条边取代原有的 条边的生成过程。,边（B,C）与边（A,F）交换的2-交换,1.4 元启发式算法,1.4.1 元启发式算法的产生背景与定义 构建性算法和迭代算法这些单运行算法的缺点是它们或者只生成数量非常有限的不同解（如贪婪构建启发式），或者

17、终止在非常差单局部最优上（如迭代改进方法）；而且，即使是对局部搜索算法进行复杂的扩展，在实际中也没有产生什么明显单改进。关于此的综述文章请参考JohnsonGlover Holland,1975,1.4.2 元启发式算法实例,贪婪随机自适应搜索过程（greedy randomized adaptive search procedures, GRASP） Feo&Resende,1985,1995 蚁群优化算法（ant colony optimization ACO） Dorigo&Stutzle,1992,1999,2002 全面介绍元启发式算法的文献请参考Glover和Kochenberge

18、r(2002)的文章。,所有的元启发式算法都具有一个共同点，就是它们都通过引入一些惯用的机制来避免生成很差的解，这些可用的元启发式算法之间的不同之处就在于避免陷入局部最优所使用的技巧不同，以及部分或者完全解所形成的轨迹不同。 不同的元启发式算法中的首要差别在于它们是基于构建性的还是基于局部搜索的。其中ACO和GRASP属于第一种其它的都是属于第二种。另一个重要差别是在每一次迭代过程中这些元启发式算法是处理单独一个解还是处理整个群体的解，除了ACO和EC其它算法都只是处理单一的解。,尽管构建性和基于群体的元启发式算法可以不使用局部搜索，然而在很多情况下如果扩展使用局部搜索它们的性能将会得到很大的

19、提高。ACO和EC就是这种情况，而GRASP在一开始的定义中就包含了局部搜索。 ACO具有的某些特征之间的特殊组合使它成为一种独特的方法：ACO通过使用蚂蚁群体以及一种称为人工信息素（artificial pheromones）的间接记忆载体来构建问题的解。,第一篇结语,一、组合优化 组合优化是一个被广泛研究的领域，目前已经出版了多种教科书和大量的研究文献。其中一本标准参考书由Papadimitriou和Steiglitz于1982年出版的入门读物以及DellAmico,Maffioli和Ausiello在1997年主编的带评注的文献汇编。 有关NP-完全性理论的标准参考书是Garey和Joh

20、nson于1979年的。 近似算法的计算复杂度：Hochbaum(1997)和Ausello,Crescenzi,Gambosi,Kann等1999年的专著。,局部搜索的复杂性理论：Johnson,Papadimitriou和Yannakakis(1988) 二、元启发式算法 元启发式算法自身的会议系列-元启发式算法国际会议从1995年开始每半年召开一次。 最近关于元启发式算法的较有影响的著作有：Michalewicz和Fogel 2000出版 综述性文章由Blum与Roli发表于2003年；以及Glover和Kochenberger(2002)主编的Handbook of Metaheuri

21、stics。,三、 ACO元启发式算法 第一个满足ACO元启发式算法框架的是蚂蚁系统（ant system AS）由Dorig在1991年提出。 Ant System： Optimization by a colony of cooperating agents 有关ACO的最新信息请见 关于蚁群算法的国际系列研讨会“蚁群：从蚁群到人工蚂蚁（ANTS:From Ant Colonies to Artificial Ants）”每两年召开一次，今年9月份将在比利时召开，详情请参考iridia.ulb.ac.be/ants,第篇 蚁群优化算法原理及

22、其实现,2.1 蚁群优化（ACO）基本原理（从真实蚂蚁到人工蚂蚁） 2.1.1 引言 2.1.2 有关的系统学概念 2.1.3 蚂蚁的觅食行为及双桥实验 2.2 蚁群优化算法的建立 2.2.1 旅行商（TSP）问题 2.2.2 蚂蚁系统（AS）模型的建立 2.2.3 蚂蚁系统（AS）模型的改进 2.3 蚁群优化算法的实现,第篇 蚁群优化算法原理及其实现,2.1 蚁群优化（ACO）基本原理,2.1.1 引言 前面提到，对于大规模的组合优化问题来说，很多确定性算法根本就无法解决，因此，寻找好的近似算法就成了研究组合优化问题的热点。而自然界一直是人类创造力的丰富源泉，人类认识事物的能力来源于自然界的

23、相互作用之中。自然界中的许多自适应优化现象不断给人以启示：生物体和自然生态系统可通过自身的演化就使许多在人类看起来高度复杂的优化问题得到完美的解决。,近些年来，一些与经典的数学规划原理截然不同的、试图通过模拟自然生态系统机制以求解复杂优化问题的仿生优化算法相继出现（如：遗传算法、蚁群算法、微粒群算法、人工免疫算法、人工鱼群算法、混合蛙跳算法等）。这些算法的出现大大丰富了现代优化技术，也为那些传统最优化技术难以处理的组合优化问题提供了切实可行的解决方案。,生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智商并不高，看起来没有集中的指挥，但它们却能协同工作，集中食物，依靠群体能力发挥出超出个体的智

24、能。,而蚁群优化算法（ACO）是最新发展的一种模拟蚂蚁群体智能行为的一种仿生优化元启发式算法，它具有较强的鲁棒性、优良的分布式计算机制、易于与其他算法相结合等优点。尽管蚁群算法的严格理论基础尚未奠定，国内外的相关研究还处于实验探索和初步应用阶段，但目前人们对蚁群算法的研究已经由当初单一的旅行商问题领域渗透到了多个应用领域（如路由、分配、调度、子集、机器学习、网络路由等）,ACO由解决一维静态优化问题发展到解决多维动态组合优化问题、由离散域范围内的研究逐渐扩展到连续域范围内的研究，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的发展前景。,自1991年意大利学者Dorigo提出蚁群算法后的近5

25、年时间里并没有在国际学术界引起广泛关注，到了1996年Dorigo等在IEEE上发表了Ant System： Optimization by a colony of cooperating agents，在这篇文章中，Dorigo等不仅更加系统地阐述了蚁群算法的基本原理和数学模型，还将其与遗传算法、禁忌搜索算法模拟退火算法等进行了仿真实验比较，并把单纯地解决对称TSP扩展到解决非对称TSP问题、指派问题、以及车间作业调度问题上。这是蚁群算法发展史上的一篇奠基性文章。,2.1.2 简单的系统学概念,系统学是一门较新的学科，其基本特点是强调整体性。 定义2.1 如果一个对象 满足以下两个条件： （

26、1） 中至少包含两个不同的子对象 （2） 中的子对象按照一定的方式互相联系在一起。 则称 为一个系统，同时定义 中的个体对象为系统的元素。,即系统可以确定为处于一定的相互关系中并与环境发生关系的各组成部分（要素）的综合体。 系统的三个基本特征,自然界中的蚁群就具备了这三个基本特征，从而构成了一个系统。蚂蚁的个体行为是系统的元素，蚂蚁间的行为相互影响体现了系统的相关性，而蚁群可以完成个体完成不了的任务则体现了系统的整体性。这也显示了系统整体大于部分之和的整体实现原理。,分布式行为,定义2.2 分布式行为 系统中很多元素相互独立完成同一项工作，当某一个元素出现问题或停止工作后整体功能不会因此受到影

27、响。,（a）,（b）,（a）是一个由非分布式行为形成的链，其中ABCD四个过程出现任何差错都得不到最终的结果；与之相对应的（b）图采用了分布式行为形成的链，当其中的一个连接出现错误中断时不会影响最终结果。,（a）,（b）,从上面的例子我们可以看到分布式系统带来强适应能力，它依赖于个体行为但并不单独依赖于每一个个体的行为。不过分布式系统的缺点也很明显即需要有很多个体来完成同样的过程，即需要个体行为的冗余。,蚁群算法的分布式特征,不难想象，自然界中的真实蚂蚁群体是一个分布式系统，当蚁群需要完成某项工作时其中的许多蚂蚁都为共同的目的进行着同样的工作，而最终任务的完成不会由于某些个体的缺陷而受到影响。

28、蚁群算法作为对蚁群觅食行为的抽象，也体现了群体行为的分布式特征。每只仍蚂蚁在问题空间的多个点同时开始互相独立地构造问题的解，而整个问题的求解不会因为某人工蚂蚁无法成功获得可行解而受到影响。,定义2.3 组织行为 系统中的元素通过一定的指令或关系相互作用的行为叫做组织行为。,如果系统在获得时间的、空间的或者功能的结构 过程中没有外界的特定干预，则称系统是自组织的。,基本蚁群算法的另一个重要特征是自组织，这 也是遗传算法、人工神经网络、微粒群算法、人 工免疫算法等仿生优化算法的共有特征。自组织 大大增强了算法的鲁棒性，传统的算法都是针对 某一具体问题而设计的，这往往建立在对该问题 有了全面清晰认识

29、的基础上，通常很难是一个其 它问题，而自组织的蚁群算法不需要对待求解问 题的所有方面都需十分了解，因而较容易应用到 一类问题中。,定义2.4 反馈机制 反馈是控制论中的重要概念 它代表信息输入对输出的反作用。在系统学上认为 反馈就是把系统现在的行为作为影响系统未来行为 的原因。,由自然界中真实蚂蚁的觅食行为可见，蚂蚁 能够最终找到最短路径，直接依赖于最短路径 上信息素的堆积，而信息素的堆积是一个正反 馈的过程。对应基本蚁群算法而言，初始时在 环境中存在完全相同的信息量，给系统一个微 小的扰动，使得各个边上的信息量大小不同蚂 蚁构造的解就存在了优劣，算法采用的反馈机 制是在较优解经过的路径上留下

30、更多的信息素 更多的信息素又吸引更多的蚂蚁，这个正反馈 的过程使得初始值不断的扩大，于是引导整个 系统向着最优解的方向进化。,2.1.3 蚂蚁的觅食行为及双桥实验,很多种类的蚂蚁所具有的视觉感知系统都是发育 不全的，甚至有些种类的蚂蚁是完全没有视觉的， 事实上关于蚂蚁行为的研究表明，群体中的个体之 间以及个体与环境之间的信息传递大部分都是依赖 于蚂蚁产生的一种化学物质进行的，人们把这种化 学物质称为信息素(pheromone)。,蚂蚁用信息素来标记地面上的路径，例如从 食物源到蚁穴之间的路径，蚂蚁正是通过感知 其他蚂蚁释放的路径信息素来沿途找到食物的 所在地，这种根据其他蚂蚁所释放的化学物质

31、信息来影响蚂蚁群体的路径选择的行为方式正 是ACO算法的灵感来源。,当蚂蚁从食物源走到蚁穴，或者从蚁穴走到 食物源时，都会在经过的地面上释放信息素， 从而形成了一条含有信息素的路径，蚂蚁可以 感觉出路径上的信息素的浓度大小，并且以更 高的概率选中信息素浓度最高的路径。,双桥实验,在某一分支上的数量百分比,实验次数的百分比,（a）,实验次数的百分比,在较短分支上的数量百分比,（b）,这个实验结果可以用一下方法进行解释，由于 刚开始时两条分支上都不存在信息素，因此蚂蚁 第这两条分支的选择就不存在任何偏向性，以相 通的概率在这两条分支间进行选择。然而，由于 随机波动的出现，选择某一条分支的蚂蚁数量可

32、 能比另一条的多，正是因为蚂蚁在移动的过程中 会释放信息素，那么蚂蚁多的分支上的信息素就 越浓，从而吸引更多的蚂蚁再次选择这一条分支 这个过程一直进行，直到最后几乎所有蚂蚁都集 中到某一分支上。,双桥实验清晰的显示出蚁群具有一种内在的优化能力， 它们可以通过使用基于局部信息的概率规则找出所在环 境中两点之间的最短路径，这就启发我们能够通过一个 概率函数来设计一种人工蚂蚁，让它们在模拟双桥的图 上移动，找出蚁穴和食物源两点间的最短路径。,信息素,启发式因子,2.2 旅行商问题中的蚁群优化算法,2.2.1 旅行商问题,旅行商问题（traveling salesman problem TSP）是一

33、个为学术界广泛研究的问题，长期以来它吸引了众多学者 对其进行研究，在ACO的研究中，TSP同样起着重要的作 用，第一个ACO算法-蚂蚁系统（ant system AS）以及 随后提出的大量的ACO算法都是首先在TSP上进行测试的。,直观的说，TSP问题就是指一位商人从自己的家乡出发 希望能找到一条最短路径，途经给定的城市集合中的所有 城市，最后返回家乡，并且每个城市都被访问一次且仅一 次。形式上，TSP问题可以用一个带权完全图 来描 述，其中 是城市的节点集合， 是所有边的集合，每一条 边 都分配一个权值（长度） ，它代表城市 与 之 间的距离。,在非对称TSP中，一对节点 之间的距离与该边的

34、 方向有关，也就是说，至少存在一条边 有 在对称TSP中，集合A中的所有边都必须满足,TSP的目标就是寻找图中一条具有最小成本 值的哈密尔顿回路，即一条访问图G中的每一 个节点一次且仅的闭合路径，这样，TSP的一 个最优解就是对应于节点标号的一个排列 ， 并且使长度 最小。其中：,（2.1）,2.2.2 AS模型的建立,ACO中的人工蚂蚁实际上代表的是一个随机 构建过程，在构建过程中通过不断向部分解添加 符合定义的解成分从而构建出一个完整的解。因 此，ACO元启发式算法可以应用到任何能够定义 构建性启发式的组合优化问题中，下面将介绍把 某个问题描述成可以被人工蚂蚁用来构建解的表 达方式。,我们

35、考虑一个最小化问题 ，对每一个 候选解 有 为目标函数值。 是约 束条件的集合，参数 表明目标函数和问题的约 束都与时间 有关。问题的目标就是要找到一个 全局最优可行解 。,给定上述的问题描述，人工蚂蚁就可以在完 全连接图 上通过随机游走来构建解，其 中图上的点是 中的成分，集合 完全连接 中 的成分点。图 称为构建图（construction gra- ph）， 中的元素称为连接（connections），问 题的约束 包含在人工蚂蚁遵循的策略中。,构建图,约束,信息素和启发式信息,解的构建,信息素更新,对TSP问题：,构建图：在这里，构建图与问题描述图是一致的， 成分的集合 对应着点的集合

36、（即 ）， 连接对应着边的集合（即 ），且每一条 边都带有一个权值代表点 和 之间的距离 问题的状态就是旅行商在游历过程中出现的 所有可能的状态的集合。,约束：在TSP中唯一的约束就是在旅行商游历的 过程中，所有城市都要被访问且每一个城 市最多只能被访问一次。 实现：蚂蚁在每一构建步中只能在还没有 被访问过的城市集合中选择下一个城市。 也就是蚂蚁 在城市 的可行解邻域 就是 由所有还没有被访问过的城市组成的。,信息素和启发式信息：,TSP中的信息素 表示在访问城市 后直接访 问城市 的期望度。启发式信息 代表蚂蚁随机 选择城市 的概率，一般直接取 ，实际上 在大部分针对TSP的ACO算法中都是

37、使用这种启 发式信息的表达方式的。,解的构建：,每一只蚂蚁最初都从随机选择出来的起点 城市出发，每经过一次迭代蚂蚁就向解中添加 一个还没有访问过的城市，当所有城市都被蚂 蚁访问过之后，解的构建就终止。,在解的构建过中，蚂蚁都是利用信息素和启发式信息以一定的概率从候选城市中选择。,其中 代表一个预先给定的启发式信息， 和 是两个参数，它们分别决定了信息素和启 发式信息的相对影响力， 代表了位于城市 的 蚂蚁 可以直接到达的相邻城市的集合。,（2.2）,参数 和 的作用如下：如果 ，则最靠近 的城市最有可能被选出，这相当于一种经典的随 机贪心算法；如果 ，那么就只有信息素的放 大系数在起作用，也就

38、是说，算法只使用了信息 素而没有利用任何启发式信息带来的偏向性，特 别是当 时算法很快就会陷入停滞状态。,信息素更新：,当所有蚂蚁都构建好路径后，各边上的信息素将 会被更新。首先，所有边上的信息素都会减少一 个常量因子的大小，然后再蚂蚁经过的边上增加信息素。信息素的蒸发根据下面的式子执行：,其中 是信息素蒸发率，有 。参数 的 作用是避免信息素的无限积累，而且还可以使 算法“忘记”之前较差的路径。,（2.3）,在信息素的蒸发步骤之后，所有蚂蚁都在它们 经过的边上释放信息素：,其中 是第 只蚂蚁向它经过的边释放的信息 素量。 定义为,（2.4）,（2.5）,其中 代表了第 只蚂蚁建立的路径 的长

39、度， 即在 中所有边的长度之和。,根据上式我们可以看到，蚂蚁构建的路径越 好，路径上的各条边就会获得更多的信息素。 一般而言，如果一条边被更多蚂蚁选择，而该 边所在的路径总长度越短，那么这条边就会获 得越多的信息素，在以后的迭代中它就更有可 能被蚂蚁选择。,高层伪代码：,Procedure ACO for TSP InitializeDate while(not terminate)do ConstructSolutions UpdatePheromone UpdateStatistics end-while end-procedure,2.2.3 改进的AS算法,AS算法是一个非常简单的基本

40、算法，随着测试 实验规模的不断扩大，AS算法的性能下降十分严 重，因而，大量关于ACO的研究工作都集中在如 何改进AS上。,下面将简单介绍两个性能最佳的ACO算法,MMAS在AS算法的基础上引入了4项主要改进：,首先，它强调了对最优路径的开发，只有迭代最 优的蚂蚁才被允许释放信息素。（在迭代中构建出 最优路径的蚂蚁，分为当前最优和至今最优）,其次，把信息素大小的取值范围限制在一个区间 内。,第三，信息素的初始值被设定为其取值范围 的上界，并与一个较小的信息素蒸发率相结合 目的是使得算法能在最初的搜索步骤中探索更 多可能的路径。 最后，在MMAS中，每当系统到达了停滞状 态，或者在一定数量的迭代

41、过程中不再有更优 的路径出现，那么所有的信息素都会被重新初 始化。,信息素的更新：当所有的蚂蚁都构建完一条路径 之和，MMAS算法将按下式进行信息素更新：,其中,（2.6）,蚁群系统（ant colony system ACS）,ACS与AS的不同之处主要体现在3个方面：,第一，它采用了一种更具积极性的行为选择规则 从而能比AS更好地开发蚂蚁所积累的搜索经验。 第二，信息素蒸发和信息素释放动作只在至今最 优路径上进行。 第三，蚂蚁每一次使用边 从城市 移动到城 市 后它就会去掉该边上一定量的信息素，以增加 探索其余路径的可能性。,在ACS中，位于城市 的蚂蚁 根据伪随机比例 规则选择城市 作为

42、下一个访问的城市，这个规则 由下式给出：,（2.7）,也可以这样理解，蚂蚁选择当前可能的最优移动 方式的概率是 ，这种最优的移动方式是根据信息 素的积累量和启发式信息值求出来的（在这种情况 下蚂蚁继续开发已知的知识）。同时，蚂蚁以 的概率有偏向性的探索各条边。通过调整参数 ， 我们可以调节算法对新路径的探索度，从而决定算 法是应该集中搜索至今最优路径附件的区域，还是 应该探索其他区域。,全局信息素更新：,在ACS中，只有一只蚂蚁（至今最优蚂蚁）被 允许在每一次迭代之后释放信息素。这样，ACS 的信息素更新规则由下面式子给出：,（2.8）,其中 。需要特别注意的是，在ACS的信息 素更新规则中，

43、无论是蒸发还是释放都只在 构成的边上执行。,局部信息素更新：,除了全局信息素更新规则外，ACS还采用了一 个局部信息素更新规则，在路径构建过程中，蚂 蚁每经过一条边 ，都将立刻调用这条规则更 新规则更新该边上的信息素：,（2.9）,其中， 和 是两个参数， 满足 ， 是信息 素量的初始值。,2.3 ACO算法的实现,对于不同版本的ACO算法的实现需要考虑的 基本问题是类似的，因此，我们集中讨论AS算 法的实现。,2.3.1 数据结构,第一步，我们先定义算法实现的基本数据结 构，这些数据结构可以存储TSP实例的相关数据 可以记录信息素含量，也可以代表人工蚂蚁。,1、城市间的距离 distnn,2

44、、最近邻列表 nn-listnnn,3、信息素 pheromonenn,4、信息素与启发式因子相结合 choic_infonn,5、蚂蚁的表示 single_ant,%问题中的数据表示 Int distnn %距离矩阵 Int nn_listnnn %长度为nn的最近邻列表矩阵 Double pheromonenn%信息素矩阵 Double choice_infonn%合并了信息素和启发式信息,%蚂蚁的表示 Structure single_ant begin int tour_length %蚂蚁的路径长度 int tourn+1 %蚂蚁保存路径的记忆存储 int visitedn %已经访

45、问过的城市 end single_ant m,空间复杂度：总的存储需求,为了表示待解问题所需的所有数据，我们需要3 个 的矩阵，同时还需要一个 的最近邻列表 此外，对于每只蚂蚁我们还需要2个数组和一个变 量，分别是一个存路径 元数组，一个记录已 访问城市的 元数组和存储路径长度的整型变量。 为了得出对存储需求的一个更具体的估计，我 们假设计算机需要用4个字节表示一个整型数据， 一8个字节表示一个实数数据，同时还假设蚂蚁的 数量为 ，则存储量的估计如下：,待解问题： 距离矩阵为 nn_list矩阵为 信息素矩阵为 choice_info矩阵为 总数为,蚂蚁的存储量：每只蚂蚁需2个长度为 的整型数

46、组 共 只蚂蚁：,因此，总体的存储量需求可以粗略地估算 为 字节。这除了主要的数据结构外，忽略 了算法需要的存储一些中间结果，例如至今 找到的最优路径，算法性能的统计信息量等 这比实际执行所需的存储量要略低，但总体 存储量需求正比于 。,2.3.2 数据的初始化及终止条件,实现ACO算法时，我们主要考虑如下任务： 包括解的构建、信息素的管理以及一些附加技 术（例如局部搜索等）。此外，程序需要初始 化一系列的数据结构和参数，并维持算法执行 期间的统计信息。,高层伪代码：,Procedure ACO for TSP InitializeDate while(not terminate)do ConstructSolutions UpdatePheromone UpdateStatistics end-while end-procedure,数据的初始化：,在数据的初始化步骤中我们需要： （1）算法需要读入TSP实例； （2）计算城市间的距离并保存到距离矩阵中； （3）计算每一个城市的最近