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