细菌觅食算法的优化及其在车间调度中的应用研究
The research on the bacterial foraging optimization and its application in the job scheduling problems作者单位:兰州理工大学
学位级别:硕士
导师姓名:赵付青
授予年度:2014年
页 码:52页
学科分类:08[工学] 081104[工学-模式识别与智能系统] 0802[工学-机械工程] 0811[工学-控制科学与工程]
主 题:细菌觅食算法 差分进化算子 作业车间调度 置换流水车间调度 混沌领域因子
摘 要:车间调度问题是一系列比较复杂的NP-hard司题,随着其问题规模的不断扩大,问题的复杂度也不断提高,传统的常规优化方法已经很难甚至无法有效地求解出问题的最优解。本文重点研究BFO算法的优化策略和理论分析,以及改进BFO算法在车间调度类问题中的应用。文章详细地阐述了BFO算法的生物学基础和算法的搜索机制,分析了现有的趋向因子的局限性并指出其所存在的缺点,提出了一种改进的BFO算法。基于随机过程理论,从数学角度证明改进的BFO算法种群进化过程具有马尔科夫性且是全局收敛的。使用国际标准的连续问题函数进行对比实验,检验改进算法在连续问题求解时的性能。然后将改进BFO算法用于求解作业车间调度问题,测试改进算法在求解离散问题中的能力。通过引入LOV规则完成连续空间的位置信息和离散加工工件序列之间的映射转化,使用标准的Job.Shop测试问题对改进算法进行测试。最后将混沌搜索因子作为邻域搜索算子引入改进的BFO算法中,提出了一种基于混沌领域搜索的BFO算法,进一步增强了BFO算法的局部搜索能力。再通过引入SPV规则,完成连续解空间到离散解空间的流水车间工件顺序的映射转换。将改进的算法应用到求解置换流水车间调度问题中,并将其与其它一些智能算法进行实验对比,说明了BFO算法在求解车间调度类的问题时是有效的,并且具有进一步开发的潜力。