多种群蚁群算法研究.pdf

宁波大学硕士学位论文
多种群蚁群优化算法的研究

摘要

蚁群优化算法是一种模仿真实蚁群觅食时表现出来的行为的仿生类算法,在
多个经典组合优化问题的应用中取得了良好的效果,从而发展成为求解复杂问
题的一种有潜力的演化算法。
本文首先阐述了几种真实蚁群的觅食行为,这些是启发蚁群优化算法的灵感
之源。之后用“Stigmergy”理论解释了蚁群在群体上表现出来的觅食行为,并叙
述了如何将真实蚂蚁的行为抽象为蚁群优化算法中人工蚂蚁的行为。最后详细
介绍了基本蚁群优化算法(Ant System,AS)模型及几种具有代表性的改进算法。
针对连续域上的优化问题(如函数优化),本文从搜索空间与解空间分离的角
度提出二元蚁群优化算法,并在路径控制中引入了拥塞控制,以此达到改进算
法性能的目的。同时分析了该策略对算法性能的影响并对带拥塞控制的二元蚁
群优化算法作了收敛性证明,最后通过实验证明了拥塞控制策略引入后算法性
能的改善。
理论研究中及实际的工程问题中,有非常多问题在本质上属于多峰多模态问
题。本文通过数学证明指出现有蚁群优化算法很难在多峰多模态优化问题中同
时找到多个极值,之后根据协同进化理论,将多种群的思想引入蚁群优化算
法,提出了带拥塞控制的多种群二元蚁群优化算法。实验表明,该算法能很好
地搜索到被测试多峰函数的全部最优解,具有很好的多峰求解能力。
最后将带拥塞控制的多种群二元蚁群优化算法应用于经典 NP 难问题—背包
问题,并在算法中加入了局部搜索算子。实验结果表明其搜索能力优于原有的
背包问题优化算法,并且能同时得到大量的最优解。
关键词:蚁群优化算法, 拥塞策略, 多种群, 多峰函数, 背包问题
宁波大学硕士学位论文
On the Multi-population Ant Colony Optimization Algorithm

Abstract

Ant colony optimization algorithm is the biological modelling algorithm which imitates the
real ant's foraging behavior. It has good performance in many bination optimization
problems and es one potential evolutional algorithm plex optimization problems.
First, this paper gives the elaboration of the biological inspiration of ant colony optimization
algorithm. Then introduce the term “stigmergy” to explain the biological ant’s behavior and show
how this biological inspiration can be transferred into artificial ant's behavior in the ant colony
optimization algorithm. Finally the model of the original ant colony optimization algorithm (Ant
System, AS) and several representative improved algorithms are described detailed.
Aiming at optimization problems in continuous spaces (such as Function Optimization),and
according to the explanation of separating the solution space and the search space,this paper
introduced the binary ant colony optimization algorithm (BACO) which bined with binary
coding the Congestion Control strategy was proposed and introduced to the BACO
to improve the algorithm’s performance. Then th