第1期 夏小云，等：蚁群优化算法的理论研究进展 ·35. 4 结束语 [3]DORIGO M,BLUM C.Ant colony optimization theory:a survey J].Theoretical computer science,2005,344 (2- 本文从蚁群算法框架、理论分析方法以及理论 3):243-278. 「4]段海滨，王道波，于秀芬.蚁群算法的研究现状及其展 研究结果等方面出发，对蚁群优化算法的理论研究 望[J].中国工程科学，2007,9(2)：98-102 进展进行了归纳和介绍。此外，还对蚁群优化算法 DUAN Haibin,WANG Daobo,YU Xiufen.Ant colony algo- 理论研究中的若干问题进行了分析讨论。当前蚁群 rithm:survey and prospect[].Engineering science,2007, 9(2):98-102. 算法的理论研究成果仍然有限，其理论分析方法和 [5]NOCEDAL J,WRIGHT S J.Numerical optimization[M] 数学工具有待进一步完善和探索。蚁群算法理论研 New York:Springer,2000. 究中还有许多亟待解决的问题。 [6]VAZIRANI V V.Approximation algorithms[M].Berlin Hei- 1)蚁群算法理论分析工具还非常有限，这也是 delberg:Springer,2003. [7]GAREY M R,JOHNSON D S.Computers and Intractability- 阻碍其向前发展的一个主要因素。现有的理论分析 A Guide to the Theory of NP-Completeness[M].New York: 方法主要是马尔可夫链理论、适应值划分技术及漂 Freeman W H and Company,1979. 移分析等方法。这些工具或者本身比较复杂，或者 [8]COLORNI A,DORIGO M,MANIEZZO V.An investigation 只是适应一些特殊情形的分析，甚至还需要满足一 of some properties of an "Ant algorithm"[C]//Proceedings of Parallel Problem Solving from Nature II PPSN 92). 些严格的条件才能使用。因此寻求新的方法和工具 Brussels,Belgium,1992:515-526. 也是未来的一个方向。 [9]STUTZLE T,HOOS HH.MAX-MIN ant system[J].Future 2)当前蚁群优化算法理论研究局限于一些简 generation computer systems,2000,16(8):889-914. 化的算法模型，基于种群的、更加复杂的构造过程还 [10]GUTJAHR W J.Mathematical runtime analysis of ACO al- 有待于进一步深入研究。对于n-ANT算法的有效 gorithms:survey on an emerging issue[J].Swarm intelli- gence,2007,1(1):59-79. 性如何，是否蚂蚁的数量与算法的时间复杂度存在 [11]DROSTE S,JANSEN T,WEGENER I.On the analysis of 某种关系还未知。通过研究群体规模、构造过程、算 the (1+1)evolutionary algorithm[].Theoretical comput- 法参数等对算法性能的影响，深入挖掘蚁群优化算 er science,2002,276(1-2):51-81. [12]WEGENER I,WITT C.On the analysis of a simple evolu- 法的潜能，更好地指导算法设计及应用。对于一个 tionary algorithm on quadratic pseudo-boolean functions NP难解组合优化问题，蚁群算法能否获得比已有算 [J].Journal of discrete algorithms,2005,3(1):61-78. 法更好的近似比？如何获得更紧的时间界等，这些 [13]WEGENER I.Towards a theory of randomized search heu- 问题都有待于深入研究。 ristics[M]//ROVAN B,VOJTAS P.Mathematical Foun- 3)将现有蚁群优化算法的理论分析结果扩展 dations of computer science 2003.Berlin Heidelberg: Springer,2003:125-141. 到更多的智能算法中。目前在差分进化算法、分布 [14]WEGENER I.Methods for the analysis of evolutionary al- 评估算法、粒子群算法以及Memetic算法等随机启 gorithms on pseudo-boolean functions[M]//Evolutionary 发式搜索的理论研究还非常有限，可以尝试将现有 Optimization.Dordrecht:Kluwer Academic Publishers, 2002,48：349-369 的理论分析结论进行有效扩展。此外，当前蚁群算 [15]BEYER H G.SCHWEFEL H P,WEGENER I.How to 法主要关注离散空间优化，可以向连续优化做进一 analyse evolutionary algorithms[.Theoretical computer 步扩充。通过对更多算法、更多问题的研究，从中找 science,2002,287(1):101-130. 出一些共性的东西，进一步丰富和增强群智能搜索 [16]HE J,YAO X.Towards an analytic framework for analy- 算法的理论基础。 sing the computation time of evolutionary algorithms[J]. Artificial intelligence,2003,145(1-2):59-97 蚁群优化算法理论研究中涉及到的问题很多， [17]HE J,YAO X.Drift analysis and average time complexity 本文不可能做到面面俱到，希望能够起到一个抛砖 of evolutionary algorithms [J].Artificial intelligence, 引玉的作用，对于今后更加深人的研究能够有所帮 2001,127(1):57-85. 助和启发。 [18]HE J,YAO X.From an individual to a population:an a- nalysis of the first hitting time of population-based evolu- 参考文献： tionary algorithms[J].IEEE transactions on evolutionary computation,2002,6(5):495-511. [1]DORIGO M,MANIEZZO V,COLORNI A.Theantsystem: [19]GUTJAHR W J.A graph-based ant system and its conver- An autocatalytic optimizing process Technical Report 91-016 gence[J].Future generation computer systems,2000,16 [R].Milan,Italy:Dipartimento di Elettronica,Politecnico (8):873-888. di Milano,1991. [20]STUTZLE T,DORIGO M.A short convergence proof for a [2]DORIG0M,STUTZLE T.蚁群优化[M].张军，胡晓敏， class of ACO algorithms[J].IEEE transactions on evolu- 罗旭耀，译.北京：清华大学出版社，2007：110-246. tionary computation,2002,6(4):358-365.４ 结束语 本文从蚁群算法框架、理论分析方法以及理论 研究结果等方面出发，对蚁群优化算法的理论研究 进展进行了归纳和介绍。 此外，还对蚁群优化算法 理论研究中的若干问题进行了分析讨论。 当前蚁群 算法的理论研究成果仍然有限，其理论分析方法和 数学工具有待进一步完善和探索。 蚁群算法理论研 究中还有许多亟待解决的问题。 １）蚁群算法理论分析工具还非常有限，这也是 阻碍其向前发展的一个主要因素。 现有的理论分析 方法主要是马尔可夫链理论、适应值划分技术及漂 移分析等方法。 这些工具或者本身比较复杂，或者 只是适应一些特殊情形的分析，甚至还需要满足一 些严格的条件才能使用。 因此寻求新的方法和工具 也是未来的一个方向。 ２）当前蚁群优化算法理论研究局限于一些简 化的算法模型，基于种群的、更加复杂的构造过程还 有待于进一步深入研究。 对于 ｎ⁃ＡＮＴ 算法的有效 性如何，是否蚂蚁的数量与算法的时间复杂度存在 某种关系还未知。 通过研究群体规模、构造过程、算 法参数等对算法性能的影响，深入挖掘蚁群优化算 法的潜能，更好地指导算法设计及应用。 对于一个 ＮＰ 难解组合优化问题，蚁群算法能否获得比已有算 法更好的近似比？ 如何获得更紧的时间界等，这些 问题都有待于深入研究。 ３）将现有蚁群优化算法的理论分析结果扩展 到更多的智能算法中。 目前在差分进化算法、分布 评估算法、粒子群算法以及 Ｍｅｍｅｔｉｃ 算法等随机启 发式搜索的理论研究还非常有限，可以尝试将现有 的理论分析结论进行有效扩展。 此外，当前蚁群算 法主要关注离散空间优化，可以向连续优化做进一 步扩充。 通过对更多算法、更多问题的研究，从中找 出一些共性的东西，进一步丰富和增强群智能搜索 算法的理论基础。 蚁群优化算法理论研究中涉及到的问题很多， 本文不可能做到面面俱到，希望能够起到一个抛砖 引玉的作用，对于今后更加深入的研究能够有所帮 助和启发。 参考文献： ［１］ＤＯＲＩＧＯ Ｍ， ＭＡＮＩＥＺＺＯ Ｖ， ＣＯＬＯＲＮＩ Ａ． Ｔｈｅａｎｔｓｙｓｔｅｍ： Ａｎ ａｕｔｏｃａｔａｌｙｔｉｃ ｏｐｔｉｍｉｚｉｎｇ ｐｒｏｃｅｓｓ Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ ９１⁃０１６ ［Ｒ］． Ｍｉｌａｎ， Ｉｔａｌｙ： Ｄｉｐａｒｔｉｍｅｎｔｏ ｄｉ Ｅｌｅｔｔｒｏｎｉｃａ， Ｐｏｌｉｔｅｃｎｉｃｏ ｄｉ Ｍｉｌａｎｏ， １９９１． ［２］ＤＯＲＩＧＯ Ｍ， ＳＴＵＴＺＬＥ Ｔ． 蚁群优化［Ｍ］． 张军， 胡晓敏， 罗旭耀， 译． 北京： 清华大学出版社， ２００７： １１０⁃２４６． ［３］ ＤＯＲＩＧＯ Ｍ， ＢＬＵＭ Ｃ． Ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ｔｈｅｏｒｙ： ａ ｓｕｒｖｅｙ［ Ｊ］． Ｔｈｅｏｒｅｔｉｃａｌ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２００５， ３４４ （ ２⁃ ３）： ２４３⁃２７８． ［４］段海滨， 王道波， 于秀芬． 蚁群算法的研究现状及其展 望［Ｊ］． 中国工程科学， ２００７， ９（２）： ９８⁃１０２． ＤＵＡＮ Ｈａｉｂｉｎ， ＷＡＮＧ Ｄａｏｂｏ， ＹＵ Ｘｉｕｆｅｎ． Ａｎｔ ｃｏｌｏｎｙ ａｌｇｏ⁃ ｒｉｔｈｍ： ｓｕｒｖｅｙ ａｎｄ ｐｒｏｓｐｅｃｔ［Ｊ］． Ｅｎｇｉｎｅｅｒｉｎｇ ｓｃｉｅｎｃｅ， ２００７， ９（２）： ９８⁃１０２． ［５］ＮＯＣＥＤＡＬ Ｊ， ＷＲＩＧＨＴ Ｓ Ｊ． Ｎｕｍｅｒｉｃａｌ ｏｐｔｉｍｉｚａｔｉｏｎ［ Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｓｐｒｉｎｇｅｒ， ２０００． ［６］ＶＡＺＩＲＡＮＩ Ｖ Ｖ． Ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ［Ｍ］． Ｂｅｒｌｉｎ Ｈｅｉ⁃ ｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２００３． ［７］ＧＡＲＥＹ Ｍ Ｒ， ＪＯＨＮＳＯＮ Ｄ Ｓ． Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｉｎｔｒａｃｔａｂｉｌｉｔｙ⁃ Ａ Ｇｕｉｄｅ ｔｏ ｔｈｅ Ｔｈｅｏｒｙ ｏｆ ＮＰ⁃Ｃｏｍｐｌｅｔｅｎｅｓｓ［Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｆｒｅｅｍａｎ Ｗ Ｈ ａｎｄ Ｃｏｍｐａｎｙ， １９７９． ［８］ＣＯＬＯＲＮＩ Ａ， ＤＯＲＩＧＯ Ｍ， ＭＡＮＩＥＺＺＯ Ｖ． Ａｎ ｉｎｖｅｓｔｉｇａｔｉｏｎ ｏｆ ｓｏｍｅ ｐｒｏｐｅｒｔｉｅｓ ｏｆ ａｎ “Ａｎｔ ａｌｇｏｒｉｔｈｍ”［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｐａｒａｌｌｅｌ Ｐｒｏｂｌｅｍ Ｓｏｌｖｉｎｇ ｆｒｏｍ Ｎａｔｕｒｅ ＩＩ （ ＰＰＳＮ ９２）． Ｂｒｕｓｓｅｌｓ， Ｂｅｌｇｉｕｍ， １９９２： ５１５⁃５２６． ［９］ＳＴÜＴＺＬＥ Ｔ， ＨＯＯＳ Ｈ Ｈ． ＭＡＸ⁃ＭＩＮ ａｎｔ ｓｙｓｔｅｍ［Ｊ］． Ｆｕｔｕｒｅ ｇｅｎｅｒａｔｉｏｎ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０００， １６（８）： ８８９⁃９１４． ［１０］ＧＵＴＪＡＨＲ Ｗ Ｊ． Ｍａｔｈｅｍａｔｉｃａｌ ｒｕｎｔｉｍｅ ａｎａｌｙｓｉｓ ｏｆ ＡＣＯ ａｌ⁃ ｇｏｒｉｔｈｍｓ： ｓｕｒｖｅｙ ｏｎ ａｎ ｅｍｅｒｇｉｎｇ ｉｓｓｕｅ［ Ｊ］． Ｓｗａｒｍ ｉｎｔｅｌｌｉ⁃ ｇｅｎｃｅ， ２００７， １（１）： ５９⁃７９． ［１１］ＤＲＯＳＴＥ Ｓ， ＪＡＮＳＥＮ Ｔ， ＷＥＧＥＮＥＲ Ｉ． Ｏｎ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ （１＋１） ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｔｈｅｏｒｅｔｉｃａｌ ｃｏｍｐｕｔ⁃ ｅｒ ｓｃｉｅｎｃｅ， ２００２， ２７６（１⁃２）： ５１⁃８１． ［１２］ＷＥＧＥＮＥＲ Ｉ， ＷＩＴＴ Ｃ． Ｏｎ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ａ ｓｉｍｐｌｅ ｅｖｏｌｕ⁃ ｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍ ｏｎ ｑｕａｄｒａｔｉｃ ｐｓｅｕｄｏ⁃ｂｏｏｌｅａｎ ｆｕｎｃｔｉｏｎｓ ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｄｉｓｃｒｅｔｅ ａｌｇｏｒｉｔｈｍｓ， ２００５， ３（１）： ６１⁃７８． ［１３］ＷＥＧＥＮＥＲ Ｉ． Ｔｏｗａｒｄｓ ａ ｔｈｅｏｒｙ ｏｆ ｒａｎｄｏｍｉｚｅｄ ｓｅａｒｃｈ ｈｅｕ⁃ ｒｉｓｔｉｃｓ［Ｍ］ ／ ／ ＲＯＶＡＮ Ｂ， ＶＯＪＴÁŠ Ｐ． Ｍａｔｈｅｍａｔｉｃａｌ Ｆｏｕｎ⁃ ｄａｔｉｏｎｓ ｏｆ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ ２００３． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２００３： １２５⁃１４１． ［１４］ＷＥＧＥＮＥＲ Ｉ． Ｍｅｔｈｏｄｓ ｆｏｒ ｔｈｅ ａｎａｌｙｓｉｓ ｏｆ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌ⁃ ｇｏｒｉｔｈｍｓ ｏｎ ｐｓｅｕｄｏ⁃ｂｏｏｌｅａｎ ｆｕｎｃｔｉｏｎｓ ［ Ｍ］ ／ ／ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｏｐｔｉｍｉｚａｔｉｏｎ． Ｄｏｒｄｒｅｃｈｔ： Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｓｈｅｒｓ， ２００２， ４８： ３４９⁃３６９． ［１５］ＢＥＹＥＲ Ｈ Ｇ， ＳＣＨＷＥＦＥＬ Ｈ Ｐ， ＷＥＧＥＮＥＲ Ｉ． Ｈｏｗ ｔｏ ａｎａｌｙｓｅ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ］． Ｔｈｅｏｒｅｔｉｃａｌ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２００２， ２８７（１）： １０１⁃１３０． ［１６］ＨＥ Ｊ， ＹＡＯ Ｘ． Ｔｏｗａｒｄｓ ａｎ ａｎａｌｙｔｉｃ ｆｒａｍｅｗｏｒｋ ｆｏｒ ａｎａｌｙ⁃ ｓｉｎｇ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎ ｔｉｍｅ ｏｆ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ］． Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００３， １４５（１⁃２）： ５９⁃９７． ［１７］ＨＥ Ｊ， ＹＡＯ Ｘ． Ｄｒｉｆｔ ａｎａｌｙｓｉｓ ａｎｄ ａｖｅｒａｇｅ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｅｖｏｌｕｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ ］． Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００１， １２７（１）： ５７⁃８５． ［１８］ＨＥ Ｊ， ＹＡＯ Ｘ． Ｆｒｏｍ ａｎ ｉｎｄｉｖｉｄｕａｌ ｔｏ ａ ｐｏｐｕｌａｔｉｏｎ： ａｎ ａ⁃ ｎａｌｙｓｉｓ ｏｆ ｔｈｅ ｆｉｒｓｔ ｈｉｔｔｉｎｇ ｔｉｍｅ ｏｆ ｐｏｐｕｌａｔｉｏｎ⁃ｂａｓｅｄ ｅｖｏｌｕ⁃ ｔｉｏｎａｒｙ ａｌｇｏｒｉｔｈｍｓ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｅｖｏｌｕｔｉｏｎａｒｙ ｃｏｍｐｕｔａｔｉｏｎ， ２００２， ６（５）： ４９５⁃５１１． ［１９］ＧＵＴＪＡＨＲ Ｗ Ｊ． Ａ ｇｒａｐｈ⁃ｂａｓｅｄ ａｎｔ ｓｙｓｔｅｍ ａｎｄ ｉｔｓ ｃｏｎｖｅｒ⁃ ｇｅｎｃｅ［Ｊ］． Ｆｕｔｕｒｅ ｇｅｎｅｒａｔｉｏｎ ｃｏｍｐｕｔｅｒ ｓｙｓｔｅｍｓ， ２０００， １６ （８）： ８７３⁃８８８． ［２０］ＳＴÜＴＺＬＥ Ｔ， ＤＯＲＩＧＯ Ｍ． Ａ ｓｈｏｒｔ ｃｏｎｖｅｒｇｅｎｃｅ ｐｒｏｏｆ ｆｏｒ ａ ｃｌａｓｓ ｏｆ ＡＣＯ ａｌｇｏｒｉｔｈｍｓ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｅｖｏｌｕ⁃ ｔｉｏｎａｒｙ ｃｏｍｐｕｔａｔｉｏｎ， ２００２， ６（４）： ３５８⁃３６５． 第 １ 期 夏小云，等：蚁群优化算法的理论研究进展 ·３５·