基于相似度和种群熵的自适应蚁群遗传算法及其应用研究

论文摘要

在市场激烈竞争下，制造业的生产规模日益增大。实际生产中，待解决的往往是上千台机器，每月上千个订单的大规模调度问题。由于生产调度问题的本质是组合优化问题，而现有的生产调度算法都集中在小规模调度领域，如果将这些调度算法直接用于大规模生产调度，那么绝大多数算法在存储空间和计算时间上，都无法让人接受。如何在已有研究的基础上，针对大规模这一特点，提出一些行之有效的算法，使调度算法更贴近实际应用，已成为近年来生产调度领域研究的一个新热点。本文做的工作如下：本文提出一种基于相似度和种群熵的自适应蚁群遗传算法，用于求解大规模调度问题。该算法将种群分成勘探、开发、勘探开发以及保留四类种群，根据各种群的功能，采用不同的遗传参数和不同进化策略。在算法中，本文用相似度来建立种群熵，最直观的反映种群的多样性，利用与种群熵相关的种群因子动态的调节种群的规模，以保证种群的多样性，加强算法的并行性。同时为了充分利用算法中的反馈信息，在综合考虑蚁群算法和保留种群的特点的基础上，对保留种群实施蚁群寻优，不仅可以防止最优解的丢失，而且可以加快整个算法的收敛速度。上述算法中的勘探种群是算法的一个核心部分，它担负着寻找和开拓问题的解空间的责任，不仅需要有较快的寻优速度，而且算法本身的鲁棒性要强。而算法中的相似度是一个很关键也很重要的参数，所以本文抛弃原有自适应遗传算法的交叉后再变异的一贯策略，将相似度作为要么进行交叉、要么进行变异的分水岭，相似度的阀值通过一个与进化代数相关的函数动态调节，这种策略性的改变不仅提高了勘探种群的勘探能力，而且提高了算法的整体寻优能力。实验研究：本文针对Job-Shop调度问题、Flow-Shop调度问题和某汽车零部件有限责任公司的AAM生产线，设计并实现了一个调度算法实验系统，并应用改进后的算法对这些问题进行求解，得到的结果说明改进算法是可行和有效的。

论文目录

• 摘要
• Abstract
• 目录
• 绪论
• 一.课题研究背景
• 二.本文的意义及主要工作
• 第一章 调度问题研究
• 1.1 调度问题及其分类
• 1.2 调度问题的描述
• 1.3 调度问题的研究方法
• 1.4 大规模调度问题的研究现状
• 本章小结
• 第二章 自适应遗传算法
• 2.1 引言
• 2.2 自适应遗传算法
• 2.2.1 自适应遗传算法的分类
• 2.2.2 标准自适应遗传算法及其收敛性
• 2.3 自适应遗传算法在生产调度中的应用
• 2.3.1 求解调度问题的编码设计
• 2.3.2 求解调度问题的遗传操作
• 2.3.3 求解调度问题的混合式遗传搜索
• 本章小结
• 第三章 算法的并行性和蚁群算法
• 3.1 引言
• 3.2 算法的并行性
• 3.2.1 算法并行性的概念
• 3.2.2 提高并行性的技术途径
• 3.3 遗传算法的并行性
• 3.3.1 遗传算法内含并行性的理论基础
• 3.3.2 遗传算法本质并行性的体现
• 3.4 蚁群算法
• 3.4.1 蚁群算法的基本原理及特点
• 3.4.2 蚁群算法的研究进展
• 3.4.3 蚁群算法的并行策略
• 本章小结
• 第四章 基于相似度和种群熵的自适应蚁群遗传算法
• 4.1 引言
• 4.2 相似度与相似度熵
• 4.2.1 相似度的定义及其计算
• 4.2.2 相似度熵的定义
• 4.2.3 相似度熵的估计方法
• 4.3 改进算法及算法流程
• 4.3.1 算法的整体框架
• 4.3.2 种群因子的自适应调节
• 4.3.3 平衡种群的构建
• 4.3.4 算法流程
• 4.4 算法的遗传操作和参数设计
• 4.4.1 编码与解码
• 4.4.2 建立初始种群
• 4.4.3 交叉与变异
• 4.5 勘探种群的算法设计
• 4.5.1 相似度阀值函数的引入
• 4.5.2 交叉率和变异率自调节公式的改进
• 4.5.3 勘探种群算法的流程
• 4.6 改进算法中的蚁群算法
• 4.6.1 蚁群算法解决车间调度
• 4.6.2 算法中的蚁群算法流程
• 4.7 改进算法性能验证
• 4.7.1 勘探种群算法性能验证
• 4.7.2 单一大规模算例验证
• 4.7.3 典型大规模算例验证
• 4.7.4 结论
• 本章小结
• 第五章 调度算法实验系统
• 5.1 系统开发的目的
• 5.2 系统概要设计
• 5.2.1 系统建模方法
• 5.2.2 系统功能模块组成
• 5.2.3 系统功能模块说明
• 5.3 系统数据库设计
• 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢