·272· 智能系统学报 第3卷 寻找路径的过程便成了蚁群优化算法的基本过程， on 如果，j∈N,则广()= 尽管，蚁群优化算法的人工蚁群同生物蚁群基本原 ∑(w 理相同，但为了具体的优化应用，人工蚁群也有自己 式中：ā表示路径上残留信息的相对重要程度：B表 的一些特点.如，人工蚁群具有一定的记忆能力，它 示期望值的相对重要程度：N表示所有可能的目标 能够记忆己经访问过的节点；另外，人工蚁群在选择 城市集合，即还没有访问的城市集合 下一条路径的时候并不是完全盲目的，而是按一定 由上式可以发现，算法中蚂蚁选中某一个城 的算法规律有意识地寻找最短路径如在以上问题 市的概率是问题本身所提供的启发式信息与从蚂 中，可以预先知道下一个目标的距离). 蚁目前所在城市到目标城市路径上残留信息量的 2蚁群模型的发展 函数】 另外，为了避免对同一个城市的多次访问，每一 21基本蚁群模型 只蚂蚁都保存一个列表abu(),用于记录到目前 由于蚁群优化算法是最典型的蚁群模型，而蚁 为止已经访问的城市 群优化算法最经典的解决问题为T$P问题，因此， 为了避免残留信息素过多引起的残留信息淹没 这里用TSP问题为例来说明算法的实现过程，这里 启发式信息的问题，在每一只蚂蚁完成对所有n个 以最基本的蚁群算法蚂蚁系统AS(ant system) 城市的访问后他即一个循环结束后，必须对残留 为例进行说明 信息素进行更新处理，模仿人类记忆的特点，对旧的 假设将m只蚂蚁放入到n个随机选择的城市 信息素进行削弱.同时，必须将最新的蚂蚁访问路径 中，那么每一只蚂蚁每一步的行动为：根据一定的依 的信息素加入T,从而得到： 据选择下一个它还没有访问的城市：同时在完成一步 从一个城市到达另外一个城市)或者一个循环完 Tg1+m)=prg()+∑A 成对所有个城市的访问)后，更新所有路径上的残 式中：P表示残留信息素的剩余率；1-P表示残留信 留信息浓度选择下一个城市的依据主要有2点： 息素被削弱的部分，即信息素的挥发率.另外，为了 1)τ，()为时刻连接城市和的路径上残留 防止信息素的无限累积，P必须小于1：△表示蚂蚁 信息的浓度，即由算法本身提供的信息：2)1为由 k在时间段到(1+n)内的访问过程中，在到的 城市转移到城市的启发信息，该启发信息是由要 路径上留下的残留信息浓度 解决的问题给出的，由一定的算法实现.在TSP问 另外，关于△的选择，M.Dorig还介绍了3种 题中一般取ng=1/d(d,表示城市i间的距离，ng 不同的实现方法，分别称为Ant Cycle,Ant Density, 在这里可以称为先验知识) Ant Quantity算法.3种算法的具体表达式为 那么，时刻位于城市的蚂蚁k选择城市为 目标城市的概率P广（按以下方法计算 Q,如果第k只妈蚁在时刻和时刻1+1之间经过 0,其他 式中：Q是常数：L表示第k只蚂蚁在本次循环中所走路径的长度 2)△ Q,如果第k只蚂蚁在时刻和时刻t+1之间经过访 0,其他 3)△ ,如果第k只蚂蚁在时刻和时刻1+1之间经过年 d的 (0,其他 在初始时刻，g0)=C 而后2种算法与前一种算法的区别在于，后2种算法中每走一步卿从时间到(1+))都要更 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net寻找路径的过程便成了蚁群优化算法的基本过程. 尽管 ,蚁群优化算法的人工蚁群同生物蚁群基本原 理相同 ,但为了具体的优化应用 ,人工蚁群也有自己 的一些特点. 如 ,人工蚁群具有一定的记忆能力 ,它 能够记忆已经访问过的节点;另外 ,人工蚁群在选择 下一条路径的时候并不是完全盲目的 ,而是按一定 的算法规律有意识地寻找最短路径 (如在以上问题 中 ,可以预先知道下一个目标的距离 ). 2 蚁群模型的发展 2. 1 基本蚁群模型 由于蚁群优化算法是最典型的蚁群模型 ,而蚁 群优化算法最经典的解决问题为 TSP问题 ,因此 , 这里用 TSP问题为例来说明算法的实现过程 ,这里 以最基本的蚁群算法 ———蚂蚁系统 AS( ant system) 为例进行说明. 假设将 m 只蚂蚁放入到 n个随机选择的城市 中,那么每一只蚂蚁每一步的行动为:根据一定的依 据选择下一个它还没有访问的城市;同时在完成一步 (从一个城市到达另外一个城市 )或者一个循环 (完 成对所有 n个城市的访问 )后 ,更新所有路径上的残 留信息浓度. 选择下一个城市的依据主要有 2点 : 1)τij ( t)为 t时刻连接城市 i和 j的路径上残留 信息的浓度 ,即由算法本身提供的信息; 2)ηij为由 城市 i转移到城市 j的启发信息 ,该启发信息是由要 解决的问题给出的 ,由一定的算法实现. 在 TSP问 题中一般取 ηij = 1 / dij ( dij表示城市 i, j间的距离 ,ηij 在这里可以称为先验知识 ). 那么 , t时刻位于城市 i的蚂蚁 k选择城市 j为 目标城市的概率 P k ij ( t)按以下方法计算 : 如果 , j ∈N k i ,则 P k ij ( t) = τα ij ( t)ηβ j j∈∑N k i τ α ij ( t)η β j . 式中 :α表示路径上残留信息的相对重要程度;β表 示期望值的相对重要程度; N k i 表示所有可能的目标 城市集合 ,即还没有访问的城市集合. 由上式可以发现 ,算法中“蚂蚁 ”选中某一个城 市的概率是问题本身所提供的启发式信息与从“蚂 蚁 ”目前所在城市到目标城市路径上残留信息量的 函数. 另外 ,为了避免对同一个城市的多次访问 ,每一 只蚂蚁都保存一个列表 tabu ( k) ,用于记录到目前 为止已经访问的城市. 为了避免残留信息素过多引起的残留信息淹没 启发式信息的问题 ,在每一只蚂蚁完成对所有 n个 城市的访问后 (也即一个循环结束后 ) ,必须对残留 信息素进行更新处理 ,模仿人类记忆的特点 ,对旧的 信息素进行削弱. 同时 ,必须将最新的蚂蚁访问路径 的信息素加入 τ,从而得到 : τij ( t + n) =ρτij ( t) + ∑ m k =1 Δτk ij . 式中 :ρ表示残留信息素的剩余率; 1 -ρ表示残留信 息素被削弱的部分 ,即信息素的挥发率. 另外 ,为了 防止信息素的无限累积 ,ρ必须小于 1;Δτk ij表示蚂蚁 k在时间段 t到 ( t + n) 内的访问过程中 ,在 i到 j的 路径上留下的残留信息浓度. 另外 ,关于 Δτk ij的选择 , M. Dorigo还介绍了 3种 不同的实现方法 ,分别称为 Ant Cycle, Ant Density, Ant Quantity算法. 3种算法的具体表达式为 1)Δτk ij = Q Lk ,如果第 k只蚂蚁在时刻 t和时刻 t + 1之间经过 ij; 0,其他. 式中 : Q是常数; Lk 表示第 k只蚂蚁在本次循环中所走路径的长度. 2) Δτk ij = Q,如果第 k只蚂蚁在时刻 t和时刻 t + 1之间经过 ij; 0,其他. 3)Δτk ij = Q dij ,如果第 k只蚂蚁在时刻 t和时刻 t + 1之间经过 ij; 0,其他. 在初始时刻 ,τij (0) =C. 而后 2种算法与前一种算法的区别在于 ,后 2 种算法中每走一步 (即从时间 t到 ( t + 1) )都要更 ·272· 智 能 系 统 学 报 第 3卷