·276· 智能系统学报 第3卷 一般包括4种算法，分别为美国学者Hooland提出 以来，它已经得到了很大的发展，在短短10年时间 的遗传算法(genetic algorithm),Fogel提出的进化规 里己发展出一个庞大的算法体系，己被应用于几乎 划(evolutionary pogrmming)6),Koza提出的遗传 科学的各个领域.尽管研究及应用的时间不长，但它 程序设计（genetic programm ing)及德国学者 己表现了非常良好的应用前景 Schwefe提出的进化策略(evoution stratey)). 参考文献： 通过对算法机理及运行过程的研究39)，可以 发现4种算法的异同点可以归纳如下 [1李衍达.信息科学与生物之谜[J小世界科技研究与发 相同点： 展，2000,21(3)：26-30 1)均为概率全局优化算法，2)均为随机优化算 LI Yanda Infomation science and the mystery of biology [J ]Study and Development ofWorld Science and Technol- 法；3)均为协同优化算法；4)均与求解问题的数学 0y,2000,21(3):26-30 性质无关，5)均为本质并行算法；6)均为很强的鲁 [2 ]DOR IGO M,MAN IEZZO V,COLORNI A.Ant system: 棒算法」 optm ization by a cobny of cooperaing Agents [J ]IEEE 不同点： Trans on9MC,1996,26(1):29-41. 1)问题的表示不同.进化算法中问题的表示必 [3 ]DOR IGO M,MAN IEZZ0 V,COLORNIA Positive feed- 须采用编码的形式，而其他几种算法无须编码；2) back as a search strategy[R]91016,Politecnico diMila- 求解操作过程不同.进化算法中求解过程一般需要 no,ay,1991 交叉、变异等基因操作；而蚁群算法的操作为概论移 [4 ]DOR IGO M,DICARO G The ant colony opti ization me- 动及信息素挥发等，信息素操作；粒子群算法则采用 ta-heuristic C ]//New keas in Opti ization England: McGraw-Hill,1999:11-32 粒子概论移动等粒子操作：免疫算法则采用抗体及 [5 ]DENEUBOURG JL,OSS C.Collective pattems and deci 抗原操作；3)数学基础不同.作为最早的仿生优化 sion making [J ]Ethobgy,Ecology and Evolution,1989 算法，进化算法的数学理论研究较多，既有证明优化 (1):295-311 原理的“积木块理论”，又有证明收敛性的马尔可夫 [6 ]LUMER E D,FA IETA B.D iversity and adaptation in popu- 链理论.而蚁群算法的理论研究不多，仅有的就是对 latons of clustering ants[C]//Proc of 3 rd Confon Simula- 算法收敛性的研究【2).粒子群算法的数学基础非常 tion of Adaptive Behavior Cambridge:M Ir Press,1994: 薄弱，目前还没有具有普遍意义的理论研究.免疫算 501-508 法尽管有简单的数学模型，但该模型的功能很差： [7张铃，程军盛.松散的脑袋—群体智能的数学模型 4)提出的初衷不同.进化算法中的遗传算法及进化 [J]模式识别与人工智能，2003,16(1)：1-5 规划提出的初衷是解决自适应系统问题及自动机预 ZHANG L ing,CHENG Junsheng Losing brainsthe math- ematic model of swam intelligence [J].Pattem Recognition 测问题.而蚁群算法的提出目的是解决如TSP一类 and Artificial Intelligence,2003,16(1):1-5. 的组合优化问题.粒子群算法及免疫算法是解决一 [8 ]DENEUBOURGL,GOSS C,FRANKS N,et al The dy- 般优化问题 nam ics of collective sorting robot-like ants and ant-like ro- 5结束语 bots[C]//Proceedings of the first intemational conference on smulation of adaptive behavor on from anmals to ani- 蚂蚁是一种人们常见的昆虫，它的特点是单个 mates Cambridge:MIT Press,1991:356-367 个体的行为极其简单，而整个群体却能表现非常复 [9]BONABEAU E,THERAULAZ G,DENEUBOURG J L 杂的智能行为.通过研究可以发现蚁群的集成智能 Quantitative study of the fixed threshold model or the regu- 来自于个体间的信息正反馈，它们可以解决非常复 lation of division of labour in insect societies [C]//Pro- 杂的路径优化问题.向大自然学习是人们解决实际 ceedings of Biobgical Sciences London:The Royal Socie- y,1996:1565-1569 问题的一条很好的途径.组合优化问题是自然界常 「10许剑，吕志民，徐金栋.带有侦察子群的蚁群算法 见的一种复杂问题之一.而路径优化又是一种最典 [J]北京科技大学学报，2006,28(8)：794-798 型的组合优化问题，因此，向蚁群学习可以提出解决 XU Jian,LU'Zhi in,XU J indong An ant system with 复杂组合优化问题的理想途径.蚁群模型的提出就 scouting subgroup [J ]Joumal ofUniversity of Science and 是这种思想的具体实现.自从1991年蚁群模型提出 Technobgy Beijing.2006,28(8):794-798 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net一般包括 4种算法 ,分别为美国学者 Hooland提出 的遗传算法 ( genetic algorithm) , Fogel提出的进化规 划 ( evolutionary p rogramm ing) [ 36 ] , Koza提出的遗传 程序 设 计 ( genetic p rogramm ing) [ 37 ] 及 德 国 学 者 Schwefel提出的进化策略 ( evolution strategy) [ 38 ] . 通过对算法机理及运行过程的研究 [ 39241 ] ,可以 发现 4种算法的异同点可以归纳如下. 相同点 : 1)均为概率全局优化算法 ; 2)均为随机优化算 法 ; 3)均为协同优化算法 ; 4)均与求解问题的数学 性质无关 ; 5)均为本质并行算法 ; 6)均为很强的鲁 棒算法. 不同点 : 1)问题的表示不同. 进化算法中问题的表示必 须采用编码的形式 ,而其他几种算法无须编码 ; 2) 求解操作过程不同. 进化算法中求解过程一般需要 交叉、变异等基因操作 ;而蚁群算法的操作为概论移 动及信息素挥发等 ,信息素操作 ;粒子群算法则采用 粒子概论移动等粒子操作 ;免疫算法则采用抗体及 抗原操作 ; 3)数学基础不同. 作为最早的仿生优化 算法 ,进化算法的数学理论研究较多 ,既有证明优化 原理的“积木块理论 ”,又有证明收敛性的马尔可夫 链理论. 而蚁群算法的理论研究不多 ,仅有的就是对 算法收敛性的研究 [ 42 ] . 粒子群算法的数学基础非常 薄弱 ,目前还没有具有普遍意义的理论研究. 免疫算 法尽管有简单的数学模型 ,但该模型的功能很差 ; 4)提出的初衷不同. 进化算法中的遗传算法及进化 规划提出的初衷是解决自适应系统问题及自动机预 测问题. 而蚁群算法的提出目的是解决如 TSP一类 的组合优化问题. 粒子群算法及免疫算法是解决一 般优化问题. 5 结束语 蚂蚁是一种人们常见的昆虫 ,它的特点是单个 个体的行为极其简单 ,而整个群体却能表现非常复 杂的智能行为. 通过研究可以发现蚁群的集成智能 来自于个体间的信息正反馈 ,它们可以解决非常复 杂的路径优化问题. 向大自然学习是人们解决实际 问题的一条很好的途径. 组合优化问题是自然界常 见的一种复杂问题之一. 而路径优化又是一种最典 型的组合优化问题 ,因此 ,向蚁群学习可以提出解决 复杂组合优化问题的理想途径. 蚁群模型的提出就 是这种思想的具体实现. 自从 1991年蚁群模型提出 以来 ,它已经得到了很大的发展 ,在短短 10年时间 里已发展出一个庞大的算法体系 ,已被应用于几乎 科学的各个领域. 尽管研究及应用的时间不长 ,但它 已表现了非常良好的应用前景. 参考文献 : [ 1 ]李衍达. 信息科学与生物之谜 [J ]. 世界科技研究与发 展 , 2000, 21 (3) : 26230. L I Yanda. Information science and the mystery of biology [J ]. Study and Development ofWorld Science and Technol2 ogy, 2000, 21 (3) : 26230. [ 2 ] DOR IGO M, MAN IEZZO V, COLORN I A. Ant system: op timization by a colony of cooperaing Agents[ J ]. IEEE Trans on SMC, 1996, 26 (1) : 29241. [ 3 ]DOR IGO M, MAN IEZZO V, COLORN I A. Positive feed2 back as a search strategy[ R ]. 912016, Politecnico diM ila2 no, Italy, 1991. [ 4 ]DOR IGO M, D I CARO G. The ant colony op tim ization me2 ta2heuristic [ C ] / /New Ideas in Op timization. England: McGraw2H ill, 1999: 11232. [ 5 ]DENEUBOURG J L, GOSS C. Collective patterns and deci2 sion making [ J ]. Ethology, Ecology and Evolution, 1989 (1) : 2952311. [ 6 ]LUMER E D, FA IETA B. D iversity and adap tation in popu2 lations of clustering ants[C ] / /Proc of 3 rd Conf on Simula2 tion of Adap tive Behavior. Cambridge: M IT Press, 1994: 5012508. [ 7 ]张 铃 , 程军盛. 松散的脑袋 ———群体智能的数学模型 [J ]. 模式识别与人工智能 , 2003, 16 (1) : 125. ZHANG Ling, CHENG Junsheng. Losing brains—the math2 ematic model of swarm intelligence[J ]. Pattern Recognition and A rtificial Intelligence, 2003, 16 (1) : 125. [ 8 ]DENEUBOURG L, GOSS C, FRANKS N, et al. The dy2 namics of collective sorting robot2like ants and ant2like ro2 bots[ C ] / /Proceedings of the first international conference on simulation of adap tive behavior on from animals to ani2 mates. Cambridge: M IT Press, 1991: 3562367. [ 9 ] BONABEAU E, THERAULAZ G, DENEUBOURG J L. Quantitative study of the fixed threshold model for the regu2 lation of division of labour in insect societies[ C ] / / Pro2 ceedings of Biological Sciences. London: The Royal Socie2 ty, 1996: 156521569. [ 10 ]许 剑 , 吕志民 , 徐金栋. 带有侦察子群的蚁群算法 [J ]. 北京科技大学学报 , 2006, 28 (8) : 7942798. XU Jian, LU¨Zhimin, XU Jindong. An ant system with scouting subgroup [J ]. Journal ofUniversity of Science and Technology Beijing, 2006, 28 (8) : 7942798. ·276· 智 能 系 统 学 报 第 3卷