生物启发式算法及其改进研究

摘要

自然界一直是人类创造力的丰富源泉，人类认识事物的能力大部分都来源于与自然界的相互作用之中。自然界中的许多自适应优化现象不断给人以启示:生物体和自然生态系统可以通过自身的演化就使许多在人类看起来极其复杂的优化问题得到完美的解决。近些年来，一些与经典的数学规划原理截然不同的、试图通过模拟自然生态系统机制以求解复杂优化问题的生物启发式算法相继出现(如进化算法、粒子群优化算法、人工免疫算法、蚁群优化算法等)，大大丰富了现代优化技术，也为那些传统最优化技术难以处理的NP难问题提供了切实可行的解决方案。因其高效的优化性能，无需问题特殊信息等优点，已广泛应用于工程优化设计、计算机科学、组合优化、优化调度等领域。因此生物启发式算法也越来越受到众多学者们的关注。本文主要研究了其中的进化算法、蚁群算法、粒子群算法和人工免疫算法。
　　 全文共分六章，第一章为绪论，主要介绍了生物启发式算法的发展历史，以及目前的一些发展现状，并分别介绍了进化算法、蚁群算法、粒子群算法和免疫算法的产生背景和发展现状。并对本论文研究的主要内容和研究方法进行了简单的介绍。
　　 第二章在介绍了进化算法的基本原理的基础上，分别对遗传算法、进化规划、进化策略、遗传编程的不同方面的特点进行了研究，然后从编码策略，选择方式，遗传算子等在不同算法的操作过程中所具有的不同点与侧重点，以及对性能可能带来的影响进行了对比分析；最后讨论了进化算法中两种最主要的操作算子：变异操作算子和交叉操作算子各自的优缺点。
　　 第三章首先介绍了蚁群算法的基本原理，并介绍了旅行商问题——这一典型的组合优化问题的特点。针对进化策略收敛速度快但容易陷入早熟收敛以及最大最小蚂蚁系统求解能力强但收敛速度较慢的特点，将进化策略与最大最小蚂蚁系统融合，利用最大最小蚂蚁系统求出每一步迭代的最优解，再对迭代出最优解进行进化策略中的变异操作来加快解的收敛速度。最后将所提出的改进算法应用到中国旅行商问题(CTSP)的实际应用中，来验证算法的优越性。
　　 第四章介绍了粒子群算法的基本原理以及解决旅行商问题的基本步骤，并针对基本粒子群算法易陷入局部极小值的缺点，分别将进化算法中的变异因子和模拟退火算法引入粒子群算法中，结合粒子群算法全局搜索能力强和模拟退火算法局部搜索能力强的优点，提出了一种混合算法。最后将混合算法应用于解决中国旅行商问题中，并将实验结果与基本的模拟退火算法、基本的粒子群算法以及带有变异因子的粒子群算法进行了对比研究。
　　 第五章首先对人工免疫算法的起源，基本原理，以及解决实际优化问题的基本步骤进行了介绍，并着重介绍了基于信息熵和基于欧式距离的免疫算法。针对上述两种免疫算法存在的不足，提出了一种基于新的浓度计算方法的改进人工免疫算法，最后将该算法应用在中国旅行商问题的求解中，并针对旅行商问题的实际特点提出了一种新的免疫疫苗的提取和注射的方法，通过对比实验验证了改进算法有着更高的求解效率。
　　 第六章对本论文的一些研究成果进行了归纳总结，并指出了目前生物启发式算法的研究中还存在一些问题，最后对下一步研究的内容和方向进行了展望。