蚁群混合遗传算法的研究及应用

论文摘要

蚁群算法是模拟自然界真实蚂蚁在寻食过程中从蚁穴到食物源中最短路径的原理，而提出的一种新型模拟算法。能够很好的解决较复杂的优化问题，它的并行性，协同性，正反馈性和鲁棒性等方面的优点可以进行全局的优化和智能的搜索。它是最近几年才提出来的，有许多优秀的实用价值，是很有潜力的模拟算法。遗传算法是模拟大自然生物在进化过程中随机搜索的算法，通过自然选择，遗传和变异的作用对个体的适应度进行了提高。此算法具有与问题域没有关系的全局搜索能力,并且不宜陷入局部最优,能够使用评价函数作为启发信息。由于蚁群算法在初期容易受到信息素缺乏的原因，引起搜索时间延长，在运行过程中存在过早收敛易陷入局部最优，搜索的最优解不能在最大范围内得到实现。恰好相反，具有快速全局搜索能力的遗传算法，没有得到更好的利用系统中反馈的信息，往往求得的相对解的效率不高，使得产生无为的冗余迭代。本文针对蚁群算法与遗传算法的特点,将两者融合,克服两种算法的各自缺点，利用遗传算法的优化组合能力确定蚁群算法的最优参数组合,利用蚁群算法求得聚类结果,优势互补,提高了算法的寻优效率，使得混合算法在收敛速度和解的全局性上都有较大的改善。本文在查阅了很多国内外的参考资料基础上，根据两种算法的优缺点，将它们结合形成混合算法的策略：在混合算法的前期，使用具有群体性全局搜索能力的遗传算法，迅速得到所需要的相对初始解，遗传算法的终止条件得到满足之后，在后期，蚁群算法所应用到的初始期信息素来源于遗传算法得到的相对较优解，最后通过具有正反馈性和高效性特点的蚁群算法快速的得到最优解。本文的主要工作是，在阐述了两种算法的原理和应用后，提出了一种新的混合算法的数学模型。在求解过程中改进了混合算法中蚁群算法的选择策略，使得算法进入局部解得概率减少，用自适应的信息素更新策略对局部信息素和全局信息素进行动态调整，最大范围的利用当前解。为了评估混合算法的性能，文章将混合算法在经典的组合优化问题旅行商问题（TSP）进行了仿真验证。实验结果表明，该混合算法不但加速了蚁群算法的收敛速度，而且提高了所得优化解的质量。最后针对组卷问题对计算机要求的应用前景，提出了开发组卷系统的想法，并进行了可行性分析和应用。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 课题的研究背景及意义
• 1.1.1 课题的研究背景
• 1.1.2 课题的研究意义
• 1.2 国内外相关的研究状况
• 1.3 本文所做的主要工作
• 2 遗传算法和蚁群算法的基本理论
• 2.1 遗传算法
• 2.1.1 遗传算法的定义及其发展
• 2.1.2 遗传算法的特点
• 2.1.3 遗传算法的基本思想
• 2.1.4 遗传算法的操作步骤
• 2.2 蚁群算法
• 2.2.1 蚁群算法的基本原理
• 2.2.2 蚁群算法的基本流程
• 2.2.3 蚁群算法的特点
• 3 蚁群混合遗传算法的研究
• 3.1 两种算法结合的可行性
• 3.1.1 两种算法混合的可行性分析
• 3.1.2 两种算法混合的基本原理
• 3.2 混合算法的衔接
• 3.2.1 混合算法的流程图
• 3.2.2 混合算法的实现步骤
• 3.2.3 混合算法的衔接及关键环节
• 3.2.3.1 算法的衔接
• 3.2.3.2 混合算法的关键环节
• 4 实验分析及其应用
• 4.1 混合算法在 TSP 上的仿真对比实验
• 4.1.1 实例仿真
• 4.1.2 实验分析
• 4.2 混合算法在组卷系统中的应用
• 4.2.1 组卷问题的简介
• 4.2.2 混合算法在组卷问题中的应用及主要步骤
• 4.2.3 组卷系统的组成和实现
• 4.2.3.1 组卷系统的基本结构
• 4.2.3.2 组卷系统的几个主要基本实现
• 结论
• 参考文献
• 附录 基本遗传算法求解 TSP 源代码
• 在学研究成果
• 致谢