文档介绍：中文摘要蚁群优化算法及其应用摘要组合优化问题是运筹学的~个重要分支,许多现实中的优化问题都可以描述为组合优化问题进行求解,其应用范围涵盖了诸如生产布局、交通运输、能源开发、最优设计、经济决策、企业管理、都市建设、公用事业、农业规划、资源分配、信息处理、军事决策等诸多领域,因此对于组合优化问题求解方法的研究具有非常重要的现实意义。计算复杂性理论证明了大多数组合优化『ⅡJ题是~≯.难『口J题,即求解这一类问题所需要的计算时问随着问题规模的增大而呈现指数性增长。由于当今社会信息化的高度发展,现实中需要求解的组合优化问题的难度和规模迅速扩大,以往传统的运筹学求解方法已经无法在可接受的时间范围内给出这一类Ⅳ≯.难问题的解,由此对多项式时间近似算法的研究提出了现实的迫切需求。目前,对于多项式时问近似算法的研究已经形成了一系列富有成效的现代优化方法,这一类方法又称为现代启发式算法,包括禁忌搜索算法、模拟退火算法、神经网络、蚁群优化算法、粒子群优化算法等等。本文的土要研究对象是蚁群优化算法。蚁群优化算法是近年来发展起来的一种群体智能优化方法,来自于对自然界中蚂蚁寻找食物的整体性能力的模仿,因此它又是一种人工智能方法。自然科学的研究表明,蚂蚁在行走时会在所经过的路径上释放一种称为信息素的化学物质。蚂蚁就是通过释放和追随信息索的方式达到交流和协作的日的,并从整体上体现为一种涌现现象。事实上,这种信息素表示蚂蚁在问题求解过程中的一种分布式的信息,是蚂蚁在问题求解过程中的一种经验累积。蚁群优化算法就是通过模仿蚂蚁这种信息素放置和追随的方式建立了自己独特的寻优机制。蚁群优化算法从诞生之日起就得到了广泛的关注,大量的研究文献充分证明了蚁群优化算法的优越性和受关注程度。日前,蚁群优化算法已经被成功地应用到了多个组合优化问题中。但是在蚁群优化算法的研究过程中还存在着些明显的不足,上要体现为:(1)数学模型的建立和相关理论性的研究还有待于完善;(2)整体求解质量还有待于提高;上海变通大学博士学位论文(3)蚁群优化算法的应用深度和广度都还有待于进一步拓展;(4)蚁群优化算法的影响力和研究力量还有待于加强。本文对于蚁群优化算法的研究主要包括三个方面的内容:(1)算法模型和收敛性理论;(2)算法的改进和创新;(3)算法应用深度和广度的拓展。在算法模型和收敛性理论方面,本文将蚁群优化算法的迭代过程描述为一种时齐的马尔可夫过程,并运用稳态分布极限概率的理论证明了蚁群优化算法的收敛性,并对影响收敛性能的一些参数设置和方法进行了讨论。在算法改进和创新方面,本文提出了三种创新的算法:首先,本文将模拟退火机制引入蚁群优化算法中,设计了一种新型的混合算法SACO;其次,本文提出了一种应用于二进制空问的二进制蚁群优化算法BAS;最后,本文设计了一种应用于连续空间的蚁群优化算法DACO。在算法应用领域,本文成功提高了蚁群优化算法在旅行商问题和多维背包问题中的求解能力,首次将蚁群优化算法应用于二进制函数优化问题,并突破了蚁群优化算法在连续空间中的应用限制和乏力现象。具体来说,本文的主要研究_[作和研究成果包括:】.简要介绍了组合优化问题及其求解方法,利用计算复杂性理论论证了使用多项式近似算法求解Ⅳ≯一难问题的必要性,并总结了处理^rP一难问题的一些土要的现代肩发式方法。、发展和应用倩况,提出了目前研究中的一些不足以及一些可行的研究方向。,并证明了蚁群优化算法的有条件收敛性:即在无限次迭代次数的前提下,具有精英蚂蚁策略和防止信息素扩散机制的蚁群优化算法能够以概率1收敛到问题的最优解。在此基础上,本文讨论了蚁群优化算法收敛速度的影响因素,提出:(1);(2)在蚁群优化算法的过程中使用局部搜索方法可以显著地提高算法的收敛速度;(3)信息素的更新规jl【lJ和参数设置可以显著地影响算法的收敛速度,但影响方向不可确定。,引入模拟退火算法中的退火机制,设计了一种新型的混合型算法SACO。SACO能够以一定的中文摘要概率接受非最优解进行信息素的更新,从而显性增加了算法跳出局部晟优的机制,扩展了算法在迭代初期的搜索范围。旅行商问题的实验证明,SACO显著提高了蚁群优化算法在求解该类『口J题时的效果。,本文设计了一种二进制的蚁群优化算法BAS,并讨论了该算法的收敛性能。BAS将信息素直接放置于每一个变量的选择路径上,通过特殊设计的信息素更新规则,使得信息素可以直接代表选择概率,从而减少了算法的计算时间。通过在二进制函数问题和多维背包问题中的成功应用,充分说明了BAS算法的有效性和实用性。