改进免疫遗传算法及其在优化调度问题中的应用研究

论文摘要

随着生产社会化的不断深入,生产规模及物资流通量越来越大,复杂性也越来越高,优化调度问题已经渗透到科研及工程应用的各个领域。近代人工智能技术的飞速发展对于解决优化调度问题提供了有力的理论基础保障。因此,在该领域的研究具有重要的理论意义和实用价值。传统优化调度方法存在着种种不足,已经不能很好地适用于大规模复杂问题。近年来,多学科交叉研究为解决此类问题提供了新的思路。其中以模仿生物免疫机理为理论基础的人工免疫优化算法在各领域的研究与应用中表现出优异的性能,已成为人工智能领域一个新的研究热点。免疫遗传算法隶属于人工免疫优化算法范畴,该算法将免疫思想融入遗传进化流程中,使其有选择、有目的地利用特征信息来促进种群向优化趋势发展,同时抑制优化过程中的退化现象。本文在归纳了基本免疫遗传算法的原理与特点的基础上,总结其不足之处,综合运用多种免疫学和遗传学思想,从多种角度对算法进行改进,并将改进算法应用于几种典型的优化调度问题。通过实例仿真,验证改进算法的有效性和实用价值。本文的主要研究内容和成果如下：(1)深入研究人工免疫系统及其算法,系统地介绍了人工免疫系统的生物学原理及其仿生机理,详细阐述了人工免疫系统的具体研究内容和范围。在剖析基本免疫遗传算法原理、框架及特点基础上,着重分析了基本免疫遗传算法解决大规模复杂问题时,在稳定性、收敛性及适应性等方面的不足,提出了相应的改进思路。(2)针对基本免疫遗传算法存在的局部搜索能力差、早熟收敛等问题,借鉴生物免疫系统的克隆选择思想及记忆理论,提出了一种免疫克隆算法。该算法通过引入克隆算子来改善基本免疫遗传算法局部搜索能力差的缺点。通过克隆增殖和超变异算子加大种群的搜索范围,保持了种群的多样性。并把该算法用于求解物流配送调度问题,通过计算不同规模、不同类型的Benchmark问题,验证了算法的稳定性和有效性。(3)针对基本免疫遗传算法存在易陷入平衡态和丢失优势基因等不良现象,提出了一种多种群、双倍体免疫遗传算法。该算法一方面采用多种群同时进化,交换种群之间优势个体所携带的遗传信息,以打破种群内平衡态达到更高的平衡态；另一方面通过双倍体编码方式延长了有用基因块的寿命,显著提高了算法的局部搜索效率,保持了种群的多样性,有利于算法跳出局部最优解。并将该算法应用于求解单级多资源限制生产批量计划问题。通过仿真实例证明,多种群双倍体免疫遗传算法不但具有良好的全局和局部搜索能力,并且具有很好的逼近精度和搜索速度。(4)针对基本免疫遗传算法由于静态地指定交叉、变异概率和疫苗而带来的搜索过程缓慢甚至停滞不前等缺点,提出了一种自适应免疫遗传算法。该算法通过自适应调整交叉、变异概率,动态生成疫苗等方式,改善了基本免疫遗传算法收敛速度缓慢、疫苗失效等缺点。并将该算法应用于求解柔性作业车间调度问题,应用不同算法对实例进行仿真,将自适应免疫遗传算法的仿真结果同遗传算法、免疫遗传算法进行对比分析,证明改进算法有良好的收敛性和鲁棒性。本文通过以上的研究工作和仿真结果分析,对改进的免疫遗传算法进行综合性地概括、归纳和总结。在处理复杂优化调度问题方面提出了一些改进的思想,并进行了算法实现和仿真。对有待进一步深入研究的问题进行了设想,对免疫遗传算法解决相关优化调度问题进行了展望。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 优化问题
• 1.2.1 优化问题及其分类
• 1.2.2 调度优化问题研究概述
• 1.3 智能优化算法
• 1.4 人工免疫算法研究
• 1.4.1 生物免疫学与人工免疫系统研究
• 1.4.2 人工免疫算法研究概述
• 1.5 本文的主要研究内容
• 1.5.1 本文的主要工作
• 1.5.2 论文组织结构
• 第二章 人工免疫系统理论与免疫遗传算法研究
• 2.1 引言
• 2.2 生物免疫系统
• 2.2.1 免疫学基本概念
• 2.2.2 生物免疫系统组成与功能
• 2.2.3 生物免疫应答与免疫记忆
• 2.2.4 免疫系统克隆选择理论
• 2.2.5 独特性免疫网络理论
• 2.3 人工免疫系统的研究内容和范围
• 2.4 人工免疫算法研究
• 2.4.1 人工免疫算法原理及特点
• 2.4.2 人工免疫算法流程
• 2.4.3 人工免疫算子设计
• 2.5 免疫遗传算法
• 2.5.1 遗传算法的原理及存在的问题
• 2.5.2 免疫遗传算法基本原理
• 2.5.3 免疫算子的机理与构造
• 2.5.4 免疫遗传算法收敛性分析
• 2.5.5 免疫遗传算法与进化算法的比较
• 2.6 小结
• 第三章 免疫遗传算法的改进研究
• 3.1 引言
• 3.2 基本免疫遗传算法的不足
• 3.3 基于克隆选择的免疫遗传算法
• 3.3.1 克隆选择原理
• 3.3.2 克隆选择算子
• 3.3.3 免疫克隆算法实现
• 3.3.4 改进算法特点
• 3.4 基于多种群、双倍体免疫遗传算法
• 3.4.1 多种群免疫遗传算法
• 3.4.2 双倍体免疫遗传算法
• 3.4.3 多种群、双倍体免疫遗传算法实现
• 3.4.4 改进算法特点
• 3.5 基于自适应的免疫遗传算法
• 3.5.1 自适应策略
• 3.5.2 疫苗动态自适应提取策略
• 3.5.3 自适应免疫遗传算法实现
• 3.5.4 改进算法特点
• 3.6 小结
• 第四章 免疫克隆算法求解CVRP
• 4.1 引言
• 4.2 物流配送问题描述
• 4.3 物流配送问题数学模型
• 4.3.1 前提假设
• 4.3.2 数学模型
• 4.4 物流配送问题的求解方法
• 4.5 免疫克隆算法解决CVRP的算法实现
• 4.6 仿真实例与分析
• 4.6.1 中小规模Benchmark实例仿真与分析
• 4.6.2 中大规模Benchmark实例仿真与分析
• 4.7 小结
• 第五章 多种群、双倍体免疫遗传算法求解CLSP
• 5.1 引言
• 5.2 生产批量计划问题描述
• 5.3 生产批量计划问题数学模型
• 5.3.1 前提假设
• 5.3.2 数学模型
• 5.4 生产批量计划问题的求解方法
• 5.5 MPDIGA算法解决SLCLSP的算法实现
• 5.5.1 抗体编码
• 5.5.2 模型转换
• 5.5.3 评价函数选取
• 5.5.4 算法流程
• 5.6 仿真实例与分析
• 5.6.1 数值算例
• 5.6.2 实际应用算例
• 5.7 小结
• 第六章 自适应免疫遗传算法求解FJSP
• 6.1 引言
• 6.2 柔性作业车间调度问题描述
• 6.3 柔性作业车间调度问题数学模型
• 6.3.1 前提假设
• 6.3.2 数学模型
• 6.3.3 确定目标函数
• 6.4 作业车间调度问题的求解方法
• 6.5 自适应免疫遗传算法解决FJSP的算法实现
• 6.5.1 抗体编码解码
• 6.5.2 算法流程
• 6.6 仿真实例与分析
• 6.6.1 小规模Benchmark实例仿真与分析
• 6.6.2 大规模Benchmark实例仿真与分析
• 6.7 小结
• 第七章 结论与展望
• 附录一 CVRP BENCHMARK
• 附录二 FJSP BENCHMARK
• 参考文献
• 致谢
• 攻读博士期间发表的论文