蚁群算法熵收敛性分析与应用

作     者：王崇宝 

作者单位：四川师范大学 

学位级别：硕士

导师姓名：庞朝阳

授予年度：2009年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：蚁群算法 信息熵 最优迭代次数 TSP问题 

摘      要：20世纪80年代以来,通过模拟、揭示某些自然现象或过程而产生了一些新颖的启发式算法,如蚁群算法、模拟退火算法、遗传算法和禁忌搜索算法等。这些算法独特的优点和机制,引起了国内外学者的广泛重视并掀起了全局优化领域的研究热潮,尤其是近十年来发展起来的蚁群算法。因为蚁群算法原理简单、鲁棒性较强、具有分布并行性等特点,吸引了越来越多的人进行研究,并已经成功地应用于诸多复杂的组合优化问题。 目前,蚁群算法的研究成果较为分散,且理论发展还不成熟,本文总结了国内外蚁群算法的研究成果,详细介绍了基本蚁群算法,进行了蚁群算法的熵收敛性分析,并基于蚁群算法的熵收敛性提出了新的改进蚁群算法,给出了详细的代码描述和数据结构说明。本文的主要研究内容及成果如下: (1)本文对蚁群算法的仿生原理、算法抽象建模过程,算法的具体实现步骤进行了总结,并给出了基本蚁群算法的程序结构流程图。 (2)本文采用实验手段,对蚁群算法的统计性质进行了分析和研究。分析发现蚁群算法具有熵收敛性并且蚁群算法的解收敛与信息熵收敛是等价的。以信息熵作为收敛判据的蚁群算法解决了其它蚁群算法不能估计最优迭代次数的问题。实验结果显示,蚁群算法应用信息熵收敛判据能够避免大量的多余计算,很大程度上减少了算法的运行时间。 (3)针对基本蚁群算法存在的缺点,本文提出了基于信息熵的改进蚁群算法。对改进算法的设计思想、算法的实现步骤及程序结构流程图进行了详细的介绍。应用改进算法求解了不同规模的TSP问题并与基本蚁群算法进行了比较,实验结果充分显示了改进算法的优越性和合理性。 (4)为了便于对改进算法的理解,本文给出了改进蚁群算法的具体代码描述和详细的数据结构介绍。