蚁群优化(AntColonyOptimization,ACO)是一种模拟自然界真实蚁群集体觅食行为的元启发式方法。现已被广泛用于求解各种工程和科学领域中的复杂优化问题。如网络动态路由问题,各种经典的组合优化难题。ACO算法中蚂蚁个体的规则虽极为简单,但作为整体却能将很复杂的问题解决到令人满意的程度。这使得ACO成为了群体智能的研究热点之一。很多学者研究了ACO的改进、ACO的应用、ACO的理论等问题,然而仍有不少关于ACO的开放性难题有待解决,比如参数该如何设置,信息素向量怎样表示待求解的问题,反馈机制是否一定有益于问题的求解及适合求解什么样的问题。本文系统地分析了ACO领域的研究工作,并围绕ACO的求解效率、质量,确定性模型分析,多群设计,信息素表示等方面开展了研究。具体地说,有以下几点:首先,研究了最大最小蚂蚁系统(Max-MinAntSystem,MMAS)算法的两种加速技术。一是研究了MMAS求解静态组合优化问题的信息素更新规则。新规则在总信息上进行,避免了MMAS在每步迭代中计算总信息和检查信息素是否越界的操作。二是研究了利用小规模实例最优解信息来设计MMAS的构造规则。利用复杂优化问题小规模实例的最优解的信息来设计一种MMAS构造解的三段式伪随机比例规则,能将有限的搜索能力快速集中到大规模实例的某一局部解空间。然而,这个规则弱化了MMAS算法的学习能力。因此研究了一种两段式随机比例规则,以增强算法的学习能力。实验结果表明,采用这些加速技术能显著地减少MMAS算法消耗的时间,增强其求解大规模问题的搜索能力。其次,研究了两种多群ACO算法的群间信息交换技术。一是通过引入粒子群优化(ParticleSwarmOptimization,PSO)中“粒子”移动的规则,研究了基于PSO的信息交换规则。该规则所需要的数据交换量和信息素更新操作均大大减少。二是通过引入中心引力优化(CentralForceOptimization,CFO)中“探测器”移动的规则,研究了基于CFO的信息交换技术。平均而言,该规则所需要的数据交换量和信息素更新操作比原有的方法减少一半。实验结果表明,与使用经典的技术相比,使用这两种新的信息交换方法的多群ACO算法在寻优能力上有明显的优势。再次,研究了ACO求解强NP难的背包问题。一是改进了求解多维背包问题(Multidimensional Knapsack Problem,MdKP)的ACO算法。改进后的算法用简单的信息素向量表示MdKP,使蚂蚁构造一个解的复杂性降低。为了在这种信息素表示中有效使用MdKP的问题知识,设计了新的序启发式信息。实验结果表明,改进后的新算法求解效率和求解质量明显优于文献中的ACO算法。二是设计了多维多选择背包问题(Multidimensional Multichoice KnapsackProblem,MdMcKP)的ACO算法。MdMcKP是MdKP的推广,具有更强的约束条件。ACO算法中的信息素表示使用了MdMcKP的独特结构。与其它启发式算法的比较实验表明,ACO算法是当前求解MdMcKP的最好方法之一。最后,研究了确定性ACO模型的收敛性及时间复杂性。建立了一个求解k最小生成树问题(k-minimum spanning tree,kMST)的竞争平衡的ACO确定性模型。用实验的方法研究了在典型信息素更新技术下模型的收敛性。然后建立求解一般组合优化问题的确定性ACO模型并严格地证明其在典型信息素更新技术下是否收敛。最后讨论了能收敛的ACO模型的时间复杂性,并得出了ACO算法时间复杂性的一个下界。