论文部分内容阅读
生产调度优化是生产过程中经常面临的问题。作为一类经典问题,它具有较大的解空间和极强的复杂性。自上世纪50年代起,许多学者对其进行了系统的研究。对于其求解,人们提出了许多办法,包括运筹学方法、基于规则的启发式算法和智能优化算法等。运筹学方法计算量和储存量较大,只适合小规模问题;基于规则的算法能较快构造出调度解,但在大规模问题上解的质量不高。智能优化算法是调度优化的一个新方向,近年来,基于智能优化方法的调度算法备受关注。
群体智能算法是受群居性生物启发,对其行为习性进行模拟而形成的一类智能算法。它具有并行、高效、概念简单、优化能力强等优点,适合求解复杂问题。自20世纪90年代以来,大量优秀的群体智能算法如蚁群算法、粒子群算法、人工蜂群算法等相继被提出,并应用到各种工程问题中。目前,群体智能算法已经成为人工智能和优化领域的的一个热门方向。
鉴于群体智能算法良好的优化效果及调度问题的实际需要,本文对群体智能算法进行了深入研究,针对一些算法的缺点和不足,给出其改进方法或提出新的优化模型,使之更为高效可靠;另一方面,对经典调度模型和实际调度问题进行研究,尝试采用群体智能算法对其进行有效的求解。
研究的内容包括:自适应萤火虫算法、基于生命周期和社会学习的细菌觅食算法、增强信息交互的混合人工蜂群算法、基于趋化混合人工蜂群算法的置换流水线调度优化、基于分解多目标人工蜂群算法的熔铸作业调度优化。具体的研究内容和创新性成果概括如下:
(1)自适应萤火虫算法
对萤火虫算法(FireflyAlgorithm,FA)进行了分析,指出原始FA算法中参数设计的缺陷致使它在高维、大变量范围问题上因吸引因子失效而优化效果变差的问题。在此基础上,提出了自适应萤火虫算法(AdaptiveFireflyAlgorithm,AFA),对吸引因子、随机因子重新进行了设计,使吸引因子能自适应于问题的维度和变量范围,随机因子随算法的运行线性下降,平衡了前期的勘探能力和后期的开发能力。此外,还对萤火虫的闪光进行了模拟,萤火虫个体在发光和熄灭两个状态间转换,只有当前正在发光的个体才能吸引其他个体,增强了种群的多样性。算法在测试函数上进行了测试,并于粒子群算法、差分算法等进行了比较。实验结果表明AFA明显优于FA算法,并在高维问题上也优于粒子群和差分算法。对飞行轨迹的仿真也证实了FA算法在大变量范围问题上吸引因子的失效,以及AFA算法具备较好的寻优性能。
(2)基于生命周期和社会学习的细菌觅食算法
针对细菌觅食算法(Bacteria Foraging Optimization,BFO)中的一些不足,提出了基于生命周期和社会学习的细菌觅食算法(Bacterial Foraging Optimization with Lifecycle and Social Learning,BFOLS)。在BFOLS中,对细菌的生命演化进行了模拟,细菌在觅食过程中根据营养值动态地分裂、死亡和迁徙,更加符合自然规律;在趋化时依照种群和自身的经验来生成翻转方向,保证前进的方向有较大概率为优化方向;此外,细菌还根据自身的营养值来动态地改变搜索步长,在潜在优化解区域以较小的步长进行更加细致的搜索。实验结果表明BFOLS算法在BFO基础上有重大改进,在高维问题上也优于经典的粒子群算法和遗传算法。此外,还对BFOLS算法中种群大小和趋化分裂进行了仿真。2维和20维函数上种群大小的变化与自然界中拥挤和宽松环境下的种群动态相对应;趋化和分裂的仿真也证实了算法能很快找到优化方向和最优区域。
(3)增强信息交互的混合人工蜂群算法
针对原始人工蜂群算法(Artificial Bee Colony,ABC)中信息交流受限而在高维问题上收敛速度变慢的问题,提出了混合人工蜂群算法(Hybrid Article Bee Colony,HABC)。HABC在跟随蜂阶段之后,引入了遗传算法的交叉操作来增强蜜蜂之间的信息交互。根据4种不同的选择方法和2种交叉方法,组合成了8个版本的HABC算法。算法结果表明,其中的HABC3和HABC6作为单点交叉和算术交叉的代表具备较好的优化能力。为此,对HABC3和HABC6中新参数CR的设置进行了测试。并在10维、30维和50维函数上对这两个版本进行了进一步测试和统计分析。测试和统计分析结果表明,在3种维度上,HABC3和HABC6都优于原始的ABC算法,其中,HABC6具有极强的优化能力,收敛精度和收敛速度明显优于其他经典算法,并在部分函数上能直接找到全局最优。
(4)基于HABCC的置换流水线调度优化
对置换流水线调度问题进行了介绍和综述。为求解该问题,在前几章的基础上提出了基于趋化混合的人工蜂群算法(Hybird Artificial Bee Colony with Chemotaxis,HABCC)。HABCC算法采用优化效果卓越的ABC算法的框架,并引入了细菌的趋化行为来在雇佣蜂和跟随蜂阶段加强其邻域搜索。若发现更好的解,则继续搜索一步,该策略对计算资源进行了动态的分配,在更优解的基础上加强邻域搜索以期发现最优调度方案。除趋化行为外,为适应调度问题,还对个体编码和解的更新策略重新进行了构造。算法在40个Taillard调度实例上进行了测试,测试结果表明HABCC算法优于一些当前较新的调度算法,具备较好的调度优化能力。同时,与原始ABC算法的比较也说明了趋化行为在此过程中是有效的。
(5)基于MOEA/D的铜板带熔铸作业调度优化
对铜加工过程中熔铸作业调度优化问题进行了介绍,以最小化生产周期和最小化总延时惩罚为目标建立了其多目标优化模型。对当前的多目标优化算法进行了综述,结合最新的分解多目标进化算法(Multi-Objective Evolutionary Algorithm Basedon Decomposition,MOEA/D)的框架和ABC算法的邻域搜索,提出了求解该调度优化问题的分解多目标人工蜂群算法(Multi-Objective Artificial Bee Colony/Decomposition,MOABC/D)。对算法采用20个订单和30个订单的模拟数据进行了测试,并与经典的多目标优化算法非支配排序遗传算法2(Non-Dominated Sorting Genetic Algorithm,NSGA-Ⅱ)、未采用ABC邻域搜索的MOEA/D进行了比较。为方便决策,在求得多目标前沿后还根据调度人员的偏好采用了基于模糊集合的Paretao选优方法进行了选优。算法求得的Paretao前沿相互支配度及选优结果表明MOABC/D优于NSGA-Ⅱ,并在大部分实例上优于MOEA/D,能有效地解决铜板带生产过程中熔铸作业调度优化问题。