第3期 高玮：新型智能仿生模型蚁群模型 ·275 比较著名的组合问题QAP问题和JSP问题，对 是集中分布，利用蚁群算法所得呼叫拒绝率和平均 典型蚁群算法作相应调整就可以比较好地解决问 路径长度均小于最小负载法结果，在呼叫符合集中 题.除此以外，蚁群算法在其他实际问题的解决中也 分布时，蚁群算法所得呼叫拒绝率低于最短路径法 取得一定的进展.如大规模集成电路中的综合布线 35新应用领域的开发 以及电信网络中的路由布置问题等方面得到了大量 在传统的应用领域得到大量应用后，近年来，蚁 应用 群算法已经被应用到大量其他领域，包括经济、人 31QAP问题 文、生物、土木工程等，并表现出了良好的应用前景， QAP问题的目标函数可以用一个对称矩阵来 以下对一些典型应用进行简单介绍.在土木工程领 描述.蚁群算法基于它和TSP问题的相似性来解决 域，高玮等24把蚁群算法引入复杂的土木工程优化 问题2).QAP问题的目标函数矩阵S通过距离向量 问题中，解决了地下洞室群的施工排序问题.在电工 D和流向量F的组合而组成： 领域，赵强等25采用蚁群算法进行配电线网络的优 Sak d;XF 化问题.在经济分析领域，Jiejin Cai等把蚁群算 蚂蚁根据可见度信息n来选择下一个节点.其 法用于发电机系统的经济分配问题.在医学领域领 中几=1S,矩阵S的元素值用作启发式因子 域，W J.Gutjahra等I21把蚁群算法用于澳大利亚的 32JSP问题 护士日程安排，对护理行程进行了合理规划.在生物 JSP问题可以用一个加权图描述：每条边的权 信息学分析中，Christian Blum等I2把蚁群算法用 值用参数对(T,几表示.信息Tx和可见度几是通 于DAN排序分析中.在工程设计领域，L.dos S 过最长进程时间或者最短完成时间等要求决定.蚂 Coetho等2采用蚁群算法及混沌优化的融合算法 蚁遍历节点的顺序就是相应的解决答案2) 解决了工程设计问题.在水资源领域，AC.Zecchi- 在解决10×10和1015的JSP问题中，蚂蚁 na等2把蚁群算法应用于水资源的分配问题.在 算法解与最优解的误差在10%之内，这是一个相当 数据分析方面，Sung-Shun W eng等[o采用蚁群算法 不错的结果 进行了数据挖掘时间序列的分割问题.在工程可靠 33大规模集成电路综合布线问题 度设计领域，Jian-Hua Zhao等IB1把多目标蚁群算法 大规模集成电路中的综合布线可以采用蚁群算 用于工程系统概念设计的可靠度优化问题研究，得 法的思想来进行2在布线过程中，各个引脚对蚂 到了较好的效果.在人文科学领域，肖智等提出 蚁的引力可根据引力函数来计算.各个线网Agent 了一种在我国RD经费投入预测中的应用蚁群算 根据启发策略，象蚁群一样在开关盒网格上爬行.所 法的新方法」 经之处便布上一条金属线.历经一个线网的所有引 以上可以发现，由于蚁群算法的良好性能，使得 脚之后，线网便布通了.给定一个开关盒布线问题， 这种算法已经在众多领域得到了广泛应用」 问题的计算量是固定不变的.主要由算法的迭代次 4蚁群模型的比较研究 数决定，而迭代次数由Agents的智能和开关盒问题 本身的性质确定.蚁群算法本身的并行法使之比较 为了对蚁群模型的特点进行深入分析，有必要 适合于解决布线问题」 把它和其他几种仿生计算模型进行比较研究，这里 34电信网络路由问题 主要研究蚁群算法、粒子群算法、免疫算法及进化算 电信网络中的路由是通过路由表进行的.在每 法等主要仿生算法的相同点及不同点。 个节点的路由表中，对每个目的节点都列出了与该 粒子群算法是美国学者J.Kennedy.R Eber 节点相连的节点.当有数据包到达时，通过查询路由 hart等于20世纪90年代初提出的一种新仿生算 表可知道下一个将要到达的节点.首先对路由表中 法)，它主要来源于对空中鸟群捕食行为的模拟 的信息素强度进行初始化，在节点x,以节点为目 免疫算法是20世纪90年代初H Bersini及 的地址，邻节点为h处的信息素强度为T=1/dm, E Varela提出的一种来源于模拟生物免疫系统的仿 d为从x经节点h到节点路径的最小费用值.然 生优化算法 后周期性地释放蚂蚁来进行路由，并修改相应的信 进化算法[3是最早提出的一种仿生算法，它是 息素值).仿真结果表明，无论呼叫是均匀分布还 模拟生物的遗传进化过程而提出的一种优化算法， 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net比较著名的组合问题 ———QAP问题和 JSP问题 ,对 典型蚁群算法作相应调整就可以比较好地解决问 题. 除此以外 ,蚁群算法在其他实际问题的解决中也 取得一定的进展. 如大规模集成电路中的综合布线 以及电信网络中的路由布置问题等方面得到了大量 应用. 3. 1 QAP问题 QAP问题的目标函数可以用一个对称矩阵来 描述. 蚁群算法基于它和 TSP问题的相似性来解决 问题 [ 20 ] . QAP问题的目标函数矩阵 S通过距离向量 D 和流向量 F 的组合而组成 : Sih = di ×Fh . 蚂蚁根据可见度信息 ηih来选择下一个节点. 其 中 ηih = 1 /Sih ,矩阵 S的元素值用作启发式因子. 3. 2 JSP问题 JSP问题可以用一个加权图描述 :每条边的权 值用参数对 {τk l ,ηk l }表示. 信息 τk l和可见度 ηk l是通 过最长进程时间或者最短完成时间等要求决定. 蚂 蚁遍历节点的顺序就是相应的解决答案 [ 21 ] . 在解决 10 ×10和 10 ×15的 JSP问题中 ,蚂蚁 算法解与最优解的误差在 10%之内 ,这是一个相当 不错的结果. 3. 3 大规模集成电路综合布线问题 大规模集成电路中的综合布线可以采用蚁群算 法的思想来进行 [ 22 ] . 在布线过程中 ,各个引脚对蚂 蚁的引力可根据引力函数来计算. 各个线网 Agent 根据启发策略 ,象蚁群一样在开关盒网格上爬行. 所 经之处便布上一条金属线. 历经一个线网的所有引 脚之后 ,线网便布通了. 给定一个开关盒布线问题 , 问题的计算量是固定不变的. 主要由算法的迭代次 数决定 ,而迭代次数由 Agents的智能和开关盒问题 本身的性质确定. 蚁群算法本身的并行法使之比较 适合于解决布线问题. 3. 4 电信网络路由问题 电信网络中的路由是通过路由表进行的. 在每 个节点的路由表中 ,对每个目的节点都列出了与该 节点相连的节点. 当有数据包到达时 ,通过查询路由 表可知道下一个将要到达的节点. 首先对路由表中 的信息素强度进行初始化 ,在节点 x,以节点 i为目 的地址 ,邻节点为 h处的信息素强度为 τih = 1 / dih , dih为从 x经节点 h到节点 i路径的最小费用值. 然 后周期性地释放蚂蚁来进行路由 ,并修改相应的信 息素值 [ 23 ] . 仿真结果表明 ,无论呼叫是均匀分布还 是集中分布 ,利用蚁群算法所得呼叫拒绝率和平均 路径长度均小于最小负载法结果 ,在呼叫符合集中 分布时 ,蚁群算法所得呼叫拒绝率低于最短路径法. 3. 5 新应用领域的开发 在传统的应用领域得到大量应用后 ,近年来 ,蚁 群算法已经被应用到大量其他领域 ,包括经济、人 文、生物、土木工程等 ,并表现出了良好的应用前景 , 以下对一些典型应用进行简单介绍. 在土木工程领 域 ,高玮等 [ 24 ]把蚁群算法引入复杂的土木工程优化 问题中 ,解决了地下洞室群的施工排序问题. 在电工 领域 ,赵强等 [ 25 ]采用蚁群算法进行配电线网络的优 化问题. 在经济分析领域 , Jiejin Cai等 [ 14 ]把蚁群算 法用于发电机系统的经济分配问题. 在医学领域领 域 ,W J. Gutjahra等 [ 26 ]把蚁群算法用于澳大利亚的 护士日程安排 ,对护理行程进行了合理规划. 在生物 信息学分析中 , Christian B lum 等 [ 27 ]把蚁群算法用 于 DAN排序分析中. 在工程设计领域 , L. dos S. Coelho等 [ 28 ]采用蚁群算法及混沌优化的融合算法 解决了工程设计问题. 在水资源领域 , A. C. Zecchi2 na等 [ 29 ]把蚁群算法应用于水资源的分配问题. 在 数据分析方面 , Sung2Shun W eng等 [ 30 ]采用蚁群算法 进行了数据挖掘时间序列的分割问题. 在工程可靠 度设计领域 , Jian2Hua Zhao等 [ 31 ]把多目标蚁群算法 用于工程系统概念设计的可靠度优化问题研究 ,得 到了较好的效果. 在人文科学领域 ,肖智等 [ 32 ]提出 了一种在我国 R&D经费投入预测中的应用蚁群算 法的新方法. 以上可以发现 ,由于蚁群算法的良好性能 ,使得 这种算法已经在众多领域得到了广泛应用. 4 蚁群模型的比较研究 为了对蚁群模型的特点进行深入分析 ,有必要 把它和其他几种仿生计算模型进行比较研究 ,这里 主要研究蚁群算法、粒子群算法、免疫算法及进化算 法等主要仿生算法的相同点及不同点. 粒子群算法是美国学者 J. Kennedy、R. Eber2 hart. 等于 20世纪 90年代初提出的一种新仿生算 法 [ 33 ] ,它主要来源于对空中鸟群捕食行为的模拟. 免疫算法是 20世纪 90年代初 H. Bersini. 及 F. Varela提出的一种来源于模拟生物免疫系统的仿 生优化算法 [ 34 ] . 进化算法 [ 35 ]是最早提出的一种仿生算法 ,它是 模拟生物的遗传进化过程而提出的一种优化算法. 第 3期 高 玮 :新型智能仿生模型 ———蚁群模型 ·275·