·30。 智能系统学报 第11卷 1.3信息素更新机制 定义1（适应值划分）给定一个有限的搜索空 当算法完成一次迭代之后，路径上的信息素将 间S,不失一般性，假设函数f:S→R最小化，考虑函 会更新。信息素更新的目的是使得较优路径上的信 数f的所有可能的不同的函数值A。,A1,…,4m,对于 息素增加，同时模拟一种挥发的方式削弱较差路径 Ha∈A,和b∈A,如果f代a)<fb),则记为A,<Ao 上的信息素。通常根据挥发因子p(0≤p≤1)的不 若有A。<A<A:…<A,定义 同，信息素值会减少不同的数量。假设更新之前的 A:={x∈Slfx)=f},i=0,1,2,…,m。则称{Ao,A1, 边(u,)∈E上的信息素值为Ta,在第一步，其值 …,A}为基于适应值的划分。 减少到(1-p)T。这意味着，在算法的运行过程 对于AC0,算法每次接受优于当前最好的解， 中，路径上的信息素将会有一定程度的挥发，避免信 算法每次运行都朝着最优解的方向前进，如图1所 息素的无限积累，这样也有利于算法逃脱局部最优。 示。下面给出一个简单AC0算法的期望运行时间 各路径上的信息素根据以下方式进行更新： 估计的定理，其由Gutjahr和Sebastiani提出。 n-(1-p)To +Ar 以概率p转移 式中：△r,表示蚂蚁k在边(u,v)上释放的信息素 A 浓度，m为蚂蚁的数量。 4 根据信息素更新方式的不同，也就产生具有不 同信息素更新机制的蚁群算法)。为了防止算法 图1适应值划分 的早熟，Stutzle和Hoos[)提出了最大最小蚂蚁系 Fig.1 Fitness values partition 统。在信息素的更新过程中，将其限制在一个最大 定理2给定一个适应值划分{A。,A1,…,Am。 最小信息素范围内[T,T]。根据边 令X,(t=1,2,.)为AC0算法的解序列， e=(u,v)∈E是否包含在至今最好的解x中，其信息 P,(i=1,2,…,m)为算法运行所得适应值所在集合 素更新规则如下： 从A,跳转到A-1U…UA,的概率下界，并且集合Ao |min(1-p)rao+p,rs},if(u,）∈x 包含最优解。则ACO算法求解函数∫的期望时间 (nmax{(1-p)re,ran},其他 上界为：宫（化+），其中为算法每次迭代时信息 Pi (1) 称使用上述信息素更新规则的(1+1)AA算法 素达到饱和的时间，也就是信息素值达到r或Tm。 为(1+1)MMAA。类似的(1+1)MMAA在文献[28,34] 根据文献[34]知道≤”。因此，对于AC0 中分别叫做MMAS·和MMAS p 理论分析，最关键的是计算一步转移概率P:。一般 2 理论分析方法及数学工具 来说，由该方法获得的时间上界不是紧界。 2.2期望倍增距离减少 对于一个确定的优化问题，蚁群算法找到一个 函数适应值个数非常大（指数级）的情况，适应 最优解的迭代次数用随机变量t表示。在蚁群算法 值划分技术已经不再适用。期望倍增减少距离(x- 的理论分析中通常需要估计最好情况、平均情况、最 坏情况下，以什么样的概率P(t≤T)在什么样的期 pected multiplicative distance decrease)的方法正好能 够应对函数适应值数量非常大的情况，该方法如图 望运行时间E(t)内，找到什么样的解（近似解）。本 2所示。 节介绍一些蚁群算法的理论分析方法和基本的数学 工具。不失一般性，考虑最小化问题。 从搜索点s开始，经过个可 2.1适应值划分 接受的操作后到达搜索点S S 对于给定的优化问题，感兴趣的是算法找到最 Doh/≤d. 优解的平均迭代次数。这里介绍适应值划分技术， -)D (1-I)D 该技术在演化算法的理论分析中得到了成功运用。 其原理是种群中最好的个体适应值一直都确保不会 是过1步 经过步 变差。因此通过估计最好的个体适应值变好的期望 图2期望倍增距离减少 时间界来获得优化时间。这种方法称为基于适应度 Fig.2 Expected multiplicative distance decrease 划分的方法(fitness-based partitions)或者适应度等 给定一个具有操作序列0p={叩o,叩1，叩2，… 级方法[4。 叩，…}，每一操作发生的概率相同，假设为１．３ 信息素更新机制 当算法完成一次迭代之后，路径上的信息素将 会更新。 信息素更新的目的是使得较优路径上的信 息素增加，同时模拟一种挥发的方式削弱较差路径 上的信息素。 通常根据挥发因子 ρ (０≤ρ≤１) 的不 同，信息素值会减少不同的数量。 假设更新之前的 边（ｕ，ｖ）∈Ｅ 上的信息素值为 τ（ｕ，ｖ） ，在第一步，其值 减少到（１－ρ） τ（ｕ，ｖ） 。 这意味着，在算法的运行过程 中，路径上的信息素将会有一定程度的挥发，避免信 息素的无限积累，这样也有利于算法逃脱局部最优。 各路径上的信息素根据以下方式进行更新： τ′（ｕ，ｖ） ＝ （１ － ρ）τ（ｕ，ｖ） ＋ ∑ ｍ ｋ ＝ １ Δτ ｋ （ｕ，ｖ） 式中：Δτ ｋ （ｕ，ｖ）表示蚂蚁 ｋ 在边（ｕ，ｖ）上释放的信息素 浓度， ｍ 为蚂蚁的数量。 根据信息素更新方式的不同，也就产生具有不 同信息素更新机制的蚁群算法［８］ 。 为了防止算法 的早熟， Ｓｔüｔｚｌｅ 和 Ｈｏｏｓ ［９］ 提出了最大最小蚂蚁系 统。 在信息素的更新过程中，将其限制在一个最大 最 小 信 息 素 范 围 内 ［ τｍｉｎ ， τｍａｘ ］。 根 据 边 ｅ ＝ （ｕ，ｖ）∈Ｅ是否包含在至今最好的解 ｘ 中，其信息 素更新规则如下： τ（ｕ，ｖ） ′ ＝ ｍｉｎ｛（１ － ρ）τ（ｕ，ｖ） ＋ ρ，τｍａｘ｝，ｉｆ （ｕ，ｖ） ∈ ｘ {ｍａｘ｛（１ － ρ）τ（ｕ，ｖ） ，τｍｉｎ｝，其他 ． （１） 称使用上述信息素更新规则的（１＋１）ＡＡ 算法 为（１＋１）ＭＭＡＡ。 类似的（１＋１）ＭＭＡＡ 在文献［２８，３４］ 中分别叫做 ＭＭＡＳ ∗和 ＭＭＡＳｂｓ。 ２ 理论分析方法及数学工具 对于一个确定的优化问题，蚁群算法找到一个 最优解的迭代次数用随机变量 ｔ 表示。 在蚁群算法 的理论分析中通常需要估计最好情况、平均情况、最 坏情况下，以什么样的概率 Ｐｒ（ｔ≤Ｔ）在什么样的期 望运行时间 Ｅ（ｔ）内，找到什么样的解（近似解）。 本 节介绍一些蚁群算法的理论分析方法和基本的数学 工具。 不失一般性，考虑最小化问题。 ２．１ 适应值划分 对于给定的优化问题，感兴趣的是算法找到最 优解的平均迭代次数。 这里介绍适应值划分技术， 该技术在演化算法的理论分析中得到了成功运用。 其原理是种群中最好的个体适应值一直都确保不会 变差。 因此通过估计最好的个体适应值变好的期望 时间界来获得优化时间。 这种方法称为基于适应度 划分的方法（ ｆｉｔｎｅｓｓ⁃ｂａｓｅｄ ｐａｒｔｉｔｉｏｎｓ） 或者适应度等 级方法［１４］ 。 定义 １ （适应值划分）给定一个有限的搜索空 间 Ｓ，不失一般性，假设函数 ｆ：Ｓ→Ｒ 最小化， 考虑函 数 ｆ 的所有可能的不同的函数值 Ａ０ ，Ａ１ ，…，Ａｍ ，对于 ∀ａ∈Ａｉ 和∀ｂ∈Ａｊ，如果 ｆ（ａ）＜ｆ（ｂ），则记为 Ａｉ ＜ｆＡｊ。 若 有 Ａ０ ＜ｆＡ１ ＜ｆＡ２ ＜ｆ … ＜ｆＡｍ ， 定 义 Ａｉ ＝ ｛ｘ∈Ｓ ｜ ｆ（ｘ）＝ ｆ ｉ｝，ｉ ＝ ０，１，２，…，ｍ。 则称｛Ａ０ ，Ａ１ ， …，Ａｍ ｝为基于适应值的划分。 对于 ＡＣＯ，算法每次接受优于当前最好的解， 算法每次运行都朝着最优解的方向前进，如图 １ 所 示。 下面给出一个简单 ＡＣＯ 算法的期望运行时间 估计的定理，其由 Ｇｕｔｊａｈｒ 和 Ｓｅｂａｓｔｉａｎｉ ［３４］提出。 图 １ 适应值划分 Ｆｉｇ．１ Ｆｉｔｎｅｓｓ ｖａｌｕｅｓ ｐａｒｔｉｔｉｏｎ 定理 ２ 给定一个适应值划分｛Ａ０，Ａ１，…，Ａｍ ｝。 令 Ｘｔ （ ｔ ＝ １， ２，．．．） 为 ＡＣＯ 算 法 的 解 序 列， ｐｉ（ｉ ＝ １，２，…，ｍ）为算法运行所得适应值所在集合 从 Ａｉ 跳转到 Ａｉ－１∪…∪Ａ０ 的概率下界，并且集合 Ａ０ 包含最优解。 则 ＡＣＯ 算法求解函数 ｆ 的期望时间 上界为：∑ ｍ ｉ ＝ １ （ｔ ∗ ｉ ＋ １ ｐｉ ），其中 ｔ ∗ ｉ 为算法每次迭代时信息 素达到饱和的时间，也就是信息素值达到 τｍａｘ或 τｍｉｎ 。 根据文献［３４］知道 ｔ ∗ ｉ ≤ ｌｎｎ ρ 。 因此，对于 ＡＣＯ 理论分析，最关键的是计算一步转移概率 ｐｉ。 一般 来说，由该方法获得的时间上界不是紧界。 ２．２ 期望倍增距离减少 函数适应值个数非常大（指数级）的情况，适应 值划分技术已经不再适用。 期望倍增减少距离（ｅｘ⁃ ｐｅｃｔｅｄ ｍｕｌｔｉｐｌｉｃａｔｉｖｅ ｄｉｓｔａｎｃｅ ｄｅｃｒｅａｓｅ）的方法正好能 够应对函数适应值数量非常大的情况，该方法如图 ２ 所示。 图 ２ 期望倍增距离减少 Ｆｉｇ．２ Ｅｘｐｅｃｔｅｄ ｍｕｌｔｉｐｌｉｃａｔｉｖｅ ｄｉｓｔａｎｃｅ ｄｅｃｒｅａｓｅ 给定一个具有操作序列 Ｏｐ ＝ ｛ ｏｐ０ ，ｏｐ１ ，ｏｐ２ ，…， ｏｐｔ， …｝， 每 一 操 作 发 生 的 概 率 相 同， 假 设 为 ·３０· 智 能 系 统 学 报 第 １１ 卷