一种具有半动态候选列表的蚁群算法

摘要

蚁群算法是受到真实蚁群的觅食机制的启发而提出的一种新的进化计算方法。研究者们根据不同的改进策略对蚂蚁系统进行改进并开发了不同版本的蚁群算法，并成功地应用于优化领域。目前国内外的许多研究者和研究机构都开展了对蚁群算法理论和应用的研究。比利时布鲁塞尔自由大学的IRIDIA实验室，瑞士的IDSIA等都是目前在蚁群算法研究领域较为活跃的机构。总的来说，蚁群算法已成为国际计算智能领域关注的热点课题。 本文在ACS算法使用的最近邻候选列表的基础上，应用受限生成思想，设计了一种半动态的候选列表生成机制，使得蚁群对于所求解问题产生一定程度的记忆与环境识别能力。运用该方法改进了基本蚁群算法，优化了AS算法的搜索过程。同时，通过仿真实验对比具有半动态候选列表的AS算法与基本AS算法在计算TSP问题时的结果，验证了算法优化的有效性。通过对仿真实验数据的分析，使用λ-分支因子法分析了基本蚁群算法与改进算法在不同的参数设置下的搜索行为的差异，验证了候选列表对于算法搜索行为的优化。

目录

文摘

英文文摘

论文说明：图表目录

声明

致谢

第一章引言

1.1蚁群算法概述

1.1.1蚁群算法的仿生学原理

1.1.2蚁群算法的系统学特征

1.1.3蚁群算法与其它算法的比较

1.2课题的国内外研究现状

1.2.1蚁群算法理论研究现状

1.2.2蚁群算法的应用研究

1.3本文的主要研究工作

第二章蚁群优化算法

2.1蚁群优化算法的基本机制

2.2人工蚂蚁的行为

2.3基本蚁群算法的算法模型

2.4几种主要的扩展蚁群算法

2.4.1使用精华策略的蚂蚁系统

2.4.2基于排列的蚂蚁系统

2.4.3最大最小蚂蚁系统

2.4.4蚁群系统

2.4.5近似非确定性树搜索

2.5组合优化问题

2.5.1组合优化问题

2.5.2组合优化问题的计算复杂度

2.5.3 NP-完全性理论

2.5.4旅行商问题

第三章具有半动态候选列表的蚁群算法

3.1ACS算法的最近邻候选列表方法

3.2半动态候选列表的设计思想与生成方法

3.2.1算法设计思想

3.2.2通过贝叶斯网络解释算法改进的原理

3.2.3算法设计

3.2.4算法的计算复杂度

3.3算法实现

第四章仿真试验与分析

4.1仿真实验

4.2实验数据分析

4.3算法行为分析

4.3.1ACO算法行为的分析方法

4.3.2AS的行为

4.3.3具有半动态候选列表的蚁群算法的行为

第五章结束语与展望

参考文献

个人简历