蚁群优化算法,作为一种自然启发的群智能算法,属于元启发式算法的范畴。它源于对自然界中蚁群觅食行为的模拟。蚂蚁在觅食时,会在经过的路径上分泌一种化学激素——信息素,并同时根据附近信息素浓度的高低来判断前进方向。蚁群中的个体行为模式较为简单,其交互行为仅仅通过一个标量的信息素浓度来间接进行。但是多个个体的独立并行行为,却使整个种群表现出了复杂的智能行为。蚁群系统天然具有的分布式、自学习、自组织、鲁棒性和简单性,使得蚁群优化算法在解决最优化问题时,具有较传统数学方法更为强大的求解能力,在生产生活的各个领域都得到了广泛关注和应用。蚁群优化算法的关键是一个参数化的概率模型,称为信息素模型。每次迭代,系统根据信息素模型来生成种群,然后又将生成的种群信息反映在信息素模型中,以影响下一代种群。也就是说,上下代种群是通过信息素模型来进行间接通信的。信息素模型既是引导种群进化方向的先验知识,同时也是保存历史种群信息的后验知识。所以信息素模型的选取直接决定了整个蚁群优化算法的性能优劣。本文致力于探索更好的信息素模型来提升蚁群优化算法的性能。文章从表达能力的角度对信息素模型进行研究,进而讨论了不同问题下的信息素模型描述能力。一个理想的信息素模型应该能够蕴含种群的全部信息。但是实际应用中,对于不同约束强度的组合优化问题,传统信息素模型的表达能力有不同程度的缺失。虽然信息素模型的这种不足可以通过算法的构造机制来进行弥补,但是算法对信息素模型的额外补充并不能彻底弥补信息的丢失。随着问题规模的增大,信息素模型的表达能力会严重制约蚁群优化算法的性能。针对传统信息素模型表达能力的局限性,文本首先推导出了关于问题决策变量的全概率分布模型,并据此提出了一种无信息丢失的全信息素模型。在全信息素模型下,信息素模型能够记录所有的信息,其描述能力达到顶点。然而,全信息素模型虽然能得到理想的结果,却是以超多项式级的空间为代价的。相比之下,实际采用的标准信息素模型在空间上有了极大的简化。但是,这种简化是以牺牲信息量为代价的。信息素模型描述能力的下降,作用到搜索过程中会引起搜索偏向,从而影响整个算法的性能。针对标准信息素模型描述能力的不足和全信息素模型空间代价大的缺点,本文提出了g阶信息素模型。该模型将全信息素模型和传统标准信息素模型(即1阶信息素模型)统一在一个信息素模型框架之下。根据实际需要,g阶信息素模型可以在空间花费和描述能力间做出平衡,既能避免过度的空间花费,同时又可以提供必要的描述能力。文章对这种g阶信息素模型进行了分析和实验,说明了g阶信息素模型较传统标准信息素模型的优势,分析了g阶信息素模型是如何在标准信息素模型的基础上进一步提高蚁群优化算法的性能。在蚁群优化算法中,种群中个体间的竞争是算法向前演化的推动力量。通过对g阶信息素模型的比较分析,本文发现:相较于1阶信息素模型中个体间的独占式竞争,在更高阶信息素模型中,个体间的竞争是相容的。这种相容式竞争很好地弥补了传统1阶信息素模型下蚁群优化算法的全局搜索能力和种群多样性方面的不足,进而增强算法的求解能力。为了更好的描述蚁群优化算法的动态行为,本文从统计学角度提出了采样点和相似度系数方法来分析算法的行为。蚁群优化算法可以看作为一种概率采样技术,而信息素模型则是一个描述解空间的概率分布模型。进而,本文将种群中个体的初始状态视为采样点。在算法运行时,每只蚂蚁都从一个采样点根据信息素模型在解空间上进行一次采样,获得的样本也就是问题的解。在1阶信息素模型中,所有的采样点地位相同。但是在更高阶的信息素模型中,采样点可以分为关键采样点和辅助采样点。g阶信息素模型中采样点的不同分工导致了个体间的相容式竞争,是提升蚁群优化算法性能的关键。而相似度系数,作为一种样本间相似性的量化方法,可以有效地描述蚁群优化算法的种群多样性变化,是一种对算法动态行为进行研究的有效工具。通过对g阶信息素模型的分析,本文提出了关键采样点来解释g阶信息素模型的成功并给出了适宜于g阶信息素模型的信息素更新机制。传统的搜索欺骗有表示型欺骗和结构型欺骗,都可以归咎于蚂蚁间的不公平竞争。而本文提出了一种新的搜索欺骗类型——复合属性欺骗,即使在公平的蚂蚁竞争中,复合属性欺骗仍然无法避免。蚁群优化算法主要用来解决NP问题。算法在搜索过程中,逐渐偏离问题的全局最优解的现象,称之为搜索欺骗。蚁群优化算法在迭代演化过程中,往往会遭受一些搜索偏向的影响。这种搜索偏向就是由欺骗行为导致的。其结果是,算法逐渐偏离最优解方向,而最终收敛为局部最优解。在复合属性中,决策变量对解的作用不是独立的,并且这种共同作用无法拆分。本文主要从信息素模型表达能力的角度研究蚁群优化算法,而正是复合属性导致了信息素模型表达能力的不足。复合属性欺骗广泛存在于NP问题之中,是导致搜索偏向的主要原因。文章讨论了复合属性欺骗对蚁群优化算法的性能影响,并利用g阶信息素模型来解决复合属性引起的欺骗现象。最后。本文对g阶信息素模型下的种群动态行为进行了理论研究。对于蚁群优化算法,其理想行为是每一代种群产生的解集的平均质量都能不断提高。本文证明对应非约束性问题,在g阶信息素模型下,蚁群优化算法的平均期望迭代质量连续不减。这样,算法能通过逐渐提高种群平均质量来对当前最优解进行不断优化。最后,本文对全信息素模型下的算法收敛性进行了证明。