第１章绪论

调度问题（Ｊｏｂ－ｓｈｏｐＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍ，简称ＪＳＰ）四１。Ｃｏｓｔａ和Ｈｅｒｚ提出增强的Ａｓ算法跚１并用它来求解图的着色问题，得到了完全可以和其它启发式算法相媲美的结果。Ｂｕｌｉｎｅｉｍｅｒ，Ｈａｒｔｌ和Ｓｔｒａｕｓｓ用基于蚂蚁等级的蚁群算法来求解车辆路径问题（ＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍｓ，简称ＶＲＰ）∞¨。由于网络中信息的分布性、动态性、随机性和异步性与蚁群算法非常相似，蚁群算法在网络通讯领域的应用受到很多学者的关注，ＤｉＣａｒｏ和ＤｏｒｉｇｏＭ将蚁群算法应用于网络路由问题，提出了ＡｎｔＮｅｔ算法口别。除了各种组合优化问题外，蚁群算法在函数优化㈨、系统辨识㈨、数据挖掘口５‘３８１、配电网规划ｂ引、化学工业ｍ１、生命科学等领域的应用Ｈ订也取得了引人注目的成果。

１．２课题的主要研究内容

围绕蚁群算法的改进及其应用，本文的研究工作集中在两个方面：

首先是对蚁群算法的运行机制进行研究，主要体现在信息素更新机制的改进上。本文在原有信息素更新机制的基础上给出了一种新的基于能量守恒的信息素更新机制，融合了解路径的全局信息和局部信息对信息素的影响，以客观体现蚂蚁在不同路径上行走时产生的信息素量的差异。同时，我们也针对已有的点扩散的信息素扩散模型改进为路径扩散的信息素扩散模型，更客观地强化了蚁群个体间的影响和协作。另外，通过使用效率高且计算复杂度小的变异策略，随机搜索机制，以加强局部寻优能力。

其次是对蚁群算法的应用研究，针对蚁群算法在求解有大规模的ＴＳＰ问题时表现出时间和精度方面的不足，提出了多阶段的处理方法，先对问题先进行基于密度的聚类处理，从区域的角度看待问题从而大大降低问题规模的复杂度，然后进行区域级的路径寻优和区域内的路径寻优，最后按区域连接顺序合成完整的解路径。在此基础之上，我们引入多粒度的概念，给出更具一般性的多粒度ＴＳＰ问题描述及其蚁群算法。随后，对蚁群算法在求解多维背包问题中的应用进行了研究，提出一种新的基于信息素扩散和变异策略的多维背包问题的蚁群算法。１．３本文的组织结构

第一章：绪论。对课题的研究现状和研究意义进行了介绍，并详细阐述了蚁群算法的产生及发展过程，随后简要介绍了本课题的研究内容。

第二章：基本蚁群优化算法及一些已有的改进算法。详细描述了基本蚁群算法ＡｎｔＳｙｓｔｅｍ的模型与实现。并进一步介绍了一些已有的改进蚁群算法，如蚁群系统ＡｎｔＣｏｌｏｎｙＳｙｓｔｅｍ、最大一最小蚂蚁系统ＭＡＸ—ＭＩＮＡｎｔＳｙｓｔｅｍ、基于变异特征的蚁群算法、基于信息素扩散的蚁群算法。