细菌觅食算法的优化及其在车间调度中的应用研究

摘要

车间调度问题是一系列比较复杂的NP-hard问题，随着其问题规模的不断扩大，问题的复杂度也不断提高，传统的常规优化方法已经很难甚至无法有效地求解出问题的最优解。本文重点研究BFO算法的优化策略和理论分析，以及改进BFO算法在车间调度类问题中的应用。文章详细地阐述了BFO算法的生物学基础和算法的搜索机制，分析了现有的趋向因子的局限性并指出其所存在的缺点，提出了一种改进的BFO算法。基于随机过程理论，从数学角度证明改进的BFO算法种群进化过程具有马尔科夫性且是全局收敛的。使用国际标准的连续问题函数进行对比实验，检验改进算法在连续问题求解时的性能。然后将改进BFO算法用于求解作业车间调度问题，测试改进算法在求解离散问题中的能力。通过引入LOV规则完成连续空间的位置信息和离散加工工件序列之间的映射转化，使用标准的Job Shop测试问题对改进算法进行测试。最后将混沌搜索因子作为邻域搜索算子引入改进的BFO算法中，提出了一种基于混沌领域搜索的BFO算法，进一步增强了BFO算法的局部搜索能力。再通过引入SPV规则，完成连续解空间到离散解空间的流水车间工件顺序的映射转换。将改进的算法应用到求解置换流水车间调度问题中，并将其与其它一些智能算法进行实验对比，说明了BFO算法在求解车间调度类的问题时是有效的，并且具有进一步开发的潜力。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 引言

1．2 课题研究背景及意义

1．2．1 车间调度问题的研究现状

1．2．1 BFO算法及其国内和国外的研究现状

1．3 本文的研究内容和文章结构

第2章 标准BFO算法及其特征分析

2．1 标准BFO算法的执行流程

2．2 算子的描述和运算特性

2．3 两种启发式仿生智能算法

2．3．1 差分进化算法

2．3．2 粒子群优化算法

2．4 本章小结

第3章 改进BFO算法及其理论分析

3．1 标准BFO算法趋向性操作存在的问题

3．2 优化趋向性操作的设计

3．2．1 差分变异因子的引入

3．2．2 改进后的细菌觅食算法趋向性操作的性能分析

3．2．3 AIBFO算法流程

3．3 AIBFO算法的收敛性分析

3．4 实验仿真

3．4．1 实验环境和测试函数

3．4．2 参数设置

3．4．3 仿真实验数据对比和分析

3．5 本章小结

第4章 基于改进BFO算法的作业车间调度

4．1 Job Shop问题描述

4．2 算法的编码和解码

4．3 AIFBO求解JSP问题

4．2 本章小结

第5章 基于改进BFO算法的置换流水车间调度

5．1 改进BFO算法在置换Flow Shop问题中的应用

5．1．1 置换Flow Shop问题的描述

5．1．2 PFSP问题的数学模型描述

5．1．3 置换Flow Shop调度问题的编码和解码

5．2 基于混沌领域搜索的细菌觅食优化算法(CLS-BFO)

5．2．1 混沌优化搜索因子

5．2．2 引入了混沌领域搜索的趋向性操作的分析

5．2．3 CLS-BFO算法流程

5．3 CLS-BFO算法求解连续问题的仿真实验

5．4 CLS-BFO算法求解Flow Shop问题的实验和分析

5．5 本章小结

总结与展望

研究总结

未来工作展望

参考文献

致谢

附录A 硕士期间所完成的学术论文