社会性动物的群集活动往往能产生惊人的自组织行为,如个体行为显得盲目的蚂蚁在组成蚁群后能够发现从蚁巢到食物源的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“外激素”的物质进行间接通讯、相互协作来发现最短路径。受其启发,意大利学者M. Dorigo,V. Maniezzo和A. Colorni通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。该算法的出现引起了学者们的极大关注,在过去短短十多年的时间里,已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛的应用,并取得了较好的效果。本论文围绕蚁群优化的原理、理论及其应用,就如何改进基本蚁群优化算法、蚁群优化的并行实现,蚁群优化算法在组合优化、机器人路径规划等领域的应用进行了较为深入、系统的研究。本文的主要研究成果包括:1、提出了一种自适应蚁群算法。该算法根据平均节点分支数动态调整转移概率以使其在“探索”和“利用”之间总能保持平衡,从而使算法在保持较高搜索能力的同时,避免出现停滞现象。仿真实验结果表明,该算法不仅有效地克服了基本蚁群优化算法中的停滞现象,而且即使在运行的后期,仍然能以极大的概率搜索较好解。2、提出了一种基于混合行为的蚁群算法。分析了蚂蚁行为对蚁群优化算法性能的影响,给出了蚂蚁行为的定义,设计了算法的模型。根据蚂蚁行为的定义,设计了四种具体的蚂蚁行为,通过调整不同行为蚂蚁数量的比例,使该算法在具有较高搜索能力的同时避免停滞现象。仿真实验首先对算法的参数进行了研究,然后与AS算法进行对比,实验结果显示其性能优于AS算法。3、提出了一种蚁群优化的并行实现。该算法利用TSP问题所具有的聚类特征,从数据域上将其分解成许多小规模的子问题,对每个子问题分别采用蚁群优化算法并行求解,最后再将所有子问题的解按一定规则合并为待求解问题的解。对带聚类特征TSP问题的仿真实验结果表明,该算法能以极快的速度收敛到问题的最优解(近优解)。当TSP问题的聚类数越多,则该算法的性能就越高,但当TSP问题的聚类特征不明显,则该算法退化为一般的蚁群优化算法。4、提出了一种求解K-TSP问题的蚁群算法。该算法将所有蚂蚁平均分成m组,每组k只,并采用每组中的k只蚂蚁共同构造问题的一个可行解。在算法中,m组蚂蚁相互协作最终达到搜索最优解的目的。实验结果显示,该算法是一种求解K-TSP问题的有效算法。 <WP=6>5、提出了一种求解0-1背包问题的蚁群优化算法。设计了0-1背包问题的构造图,针对构造图为蚂蚁设计了两种状态转移公式并定义了其优先级,蚂蚁以不同的优先级按照这两个状态转移公式在构造图中移动直到死亡,此时,蚂蚁走过的路径即构成0-1背包问题的一个可行解。仿真实验首先对该算法的参数进行了讨论,然后与遗传算法进行了比较,实验结果显示该算法具有较高的性能。6、提出了一种求解迷宫问题的蚁群优化算法。该算法首先将蚁群平均分成两组,分别从迷宫的起点和终点出发,每只蚂蚁按路径上的信息素独立地选择前进的道路。根据蚂蚁在迷宫中的行走状态,定义了三种不同类型的生命周期。根据蚂蚁每次移动后所处的状态,生成问题的可行解。仿真实验证实了本算法的有效性。7、提出了一种求解空间机器人路径规划的蚁群优化算法。该算法首先将机器人所在位置(源点)与将要到达的位置(目的点)之间的空间划分成立体网格,同时定义了源点与目的点之间的有效路径。蚁群从源点出发,独立地选择有效路径,最终到达目的点,从而求出从源点到目的点之间的最优路径。实验结果表明,该算法不仅有效,而且具有极快的速度。在该算法中,网格的稠密程度决定了算法解的精度,即网格越稠密,算法的精度越高,但所需时间也越长;反之则越低,所花时间越短。最后,对全文的研究工作进行了总结,并展望了蚁群优化进一步还要研究的课题。