混合遗传变邻域搜索算法求解柔性车间调度问题

针对考虑生产成本的柔性作业车间调度问题(flow job shop scheduling problem, FJSP),以完工时间与加工成本为优化指标,提出一种求解FJSP的混合遗传变邻域搜索算法。根据个体适应度对种群分割,结合自适应交叉概率改进子代种群产生方式;设计两种邻域结构增强算法的局部搜索能力;提出一种基于动态交叉变异概率的优化算法流程提高求解效率。运用提出的算法求解基准实例与实际问题测试,验证了算法的有效性。

基于遗传-变邻域搜索算法的堆垛机作业调度优化

基于缩短自动化立体仓库中堆垛机完成货物出入任务时间的目的,建立了堆垛机作业调度的作业时间模型,通过修补机制、校正机制和遗传-变邻域搜索算法的优化方法,使得在优化的过程中,确保出入库任务序列的长度相等,并能够复用同一批作业任务中因出库作业产生的空货位。12组作业任务的仿真实验结果表明,相较于变邻域搜索算法,遗传-变邻域搜索算法的收敛速度更快,其中3组作业任务解的质量更高,总耗时和相对耗时的优化率分别为11.57%~21.56%和35.85%~68.89%,且复用空货位可以缩短堆垛机的作业时间。

双种群混合遗传算法求解航空复合材料柔性调度问题

考虑航空复合材料柔性车间调度中的运输约束,以最小化完工时间为目标,建立调度模型,提出一种改进的双种群混合遗传算法进行求解。根据问题特点,基于工序排序、机器选择和运输约束3个子问题,设计三层实数编码以及对应解码方案。采用混合初始化提高种群质量,进化过程中采用交叉算子执行全局搜索,为双种群设计基于机器负载平衡和变邻域的局部搜索,提高全局和局部搜索能力。与对比算法相比10个测试算例中BPRD指标取得9个最优,APRD指标全部取得最优,t检验显著性有明显差异,验证算法的优越性。将算法应用于航空复合材料车间中,实现实际生产的调度,验证算法的可行性。

改进遗传算法搜索动态订单下车辆路径最优问题

滚动周期策略是当前学者利用优化算法解决动态车辆路径规划(dynamic vehicle routing planning,DVRP)问题的主要研究策略。预优化算法是基于遗传算法(genetic algorithm,GA)进行改进。GA易早熟和易陷入局部最优的特点,使解的质量往往不能达到最好。针对此问题,在GA算法上提出了贪婪重构策略进行改进。贪婪重构遗传算法(greedy reconstruction genetic algorithm,GRGA)随机剔除每条路径固定数量的客户点,利用贪婪重构策略依次将剔除点插入到各个路径,保留成本最低的解,摒弃了完全随机的策略原则,使解可以跳出局部最优。在每次迭代之后利用变邻域下降搜索算法(variable neighborhood descent,VND)进行深度搜索,完成一次迭代。最后进行三组测试,第一组是在统一平台上采用Solomon数据集测试算法效果,第二组是把预优化改进算法与对比算法得到的数据分别进行保存,利用控制变量法在动态调度周期使用一种动态调度优化算法,分别对每个预优化算法形成的初始路径进行调度,测试改进算法的有效性,第三组是采用实际案例测试预优化算法的效果。

作业车间调度的多工序精确联动邻域结构混合进化算法

针对作业车间调度问题,以最小化最大完工时间为优化目标,提出一种基于多工序精确联动邻域结构的混合进化算法。从理论上给出了关键块中工序无效移动的判定条件,据此设计了3对工序精确联动的邻域结构。为避免算法过早收敛,引入基于邻域惩罚的交叉父本匹配选择算子与基于动态惩罚阈值的种群更新策略。通过与其他先进算法在车间调度问题基准算例上进行对比实验,验证了所提算法的有效性与稳定性。

基于和声搜索遗传算法的桁架结构拓扑优化

为改善传统设计理念和遗传算法优化不足,促进桁架结构离散变量拓扑优化发展与创新,将遗传算法与和声搜索算法混合,同时对遗传交叉和变异分3种情况进行自适应改进,建立了用于桁架结构拓扑优化的新型混合遗传算法——和声搜索遗传算法,利用该方法分别对平面桁架和空间桁架结构进行拓扑优化分析,并与改进遗传算法、拟满应力遗传算法、相对差商法、复合形遗传算法和改进蚁群算法比较,证明了此方法是有效、可行的。

基于混合遗传禁忌搜索算法的多机器人任务分配

为解决传统遗传算法在求解仓储多机器人任务分配问题时,收敛速度慢且容易陷入局部极值的问题,该文提出一种混合遗传禁忌搜索算法。首先以机器人配送成本最小为目标建立数学模型;然后在传统的遗传算法中引入禁忌搜索算法中的禁忌表和藐视准则,来对遗传算法每次迭代后的种群进行优化调整,使得算法能够跳出局部最优且快速收敛。仿真结果表明,混合遗传禁忌搜索算法能有效地改善遗传算法的全局寻优能力,提升仓储的整体运行效率。

CA型邻域遗传算法求解柔性作业车间调度问题

针对以批量小、品种多为主要生产模式的加工制造型企业,分析以最小化最大完工时间为优化目标的柔性作业车间静态调度问题。首先,建立单目标整数规划模型,提出一种基于元胞自动机(cellular automata,CA)型邻域的遗传算法对模型进行求解。其次,为了改善初始解的质量,采用选择剩余工序最多的工件编码和随机选择编码结合的种群初始化方式,使算法在较优的解空间内迭代搜索,提高算法的收敛速度;为了优化求解质量,在算法中引入CA型邻域搜索,有效探索解空间,提高算法的寻优能力。最后,用基准实例进行测试,通过算法改进成分有效性检验以及与其他改进算法对比实验验证所提算法的可行性与有效性。

基于邻域搜索的混合遗传算法及其在对称TSP中的应用

基于邻域搜索的混合遗传算法是综合了遗传算法和邻域搜索算法各自优势的全局搜索算法。它既有遗传算法的全局搜索能力,又有高效的局部搜索能力。该算法较好地解决了两种不同算法结合所产生的矛盾。通过对对称TSP的实验表明,算法具有良好的全局寻优性能并得到很好的结果。

混合禁忌搜索的车间调度遗传算法研究

针对以最小化最大完工时间为目标的作业车间调度问题,提出一种混合禁忌搜索的遗传算法。禁忌搜索是一种能有效跳出局部最优解的元启发式算法,在每次迭代过程中通过搜索当前解的邻域来获得一个新解,通过评价新解的优越性来优化求解结果;加入多种交叉方式随机选择来扩大种群多样性;同时加入局部邻域搜索来改善解的质量,加快算法收敛速度。将提出的改进算法用于求解若干基准问题,算法具有一定的改良性,能优化求解结果。

遗传算法与变邻域搜索混合模型在护士排班中的应用

目的在探讨基于层级管理的护士APN排班模型的基础上,引入具有精确的全局搜索能力的遗传算法与变邻域搜索混合模型来解决护士排班过程中人员层级复杂、不同班次人员需求量不同等问题。方法首先,初始化排班表,然后利用遗传算法对初始化的排班表进行搜索,得到一个初步的排班表,最后利用变邻域搜索优化排班表,得到满足要求的排班表。结果使用该混合模型得到的排班表,能满足每日护士的人数需求和每名护士的工作量要求。同时,基于层级管理,各层级护士分开排班,能降低排班难度,在增加护士人员时,效率仍然较高。结论遗传算法与变邻域搜索的混合模型能解决护士排班中的各种复杂问题,是一种符合实际需求的模型。基于此模型来编制护士排班软件,能提升护理工作效率和满意度,便于对护理人员进行量化考核统计分析。

基于遗传变邻域搜索算法的农机跨区调度优化研究

智慧农业的快速发展促使多区域互联农机的调度追求更高的实时性,为更合理配置农机资源,农机跨区作业已成为完成“三夏”机收任务的主要服务模式。基于小麦收获机跨区作业真实场景,研究了带时间窗的多库、多机型的农机跨区调度问题,同时考虑经济成本和环境成本,建立以最小调度成本为目标的跨区调度模型。根据问题特征,设计遗传变邻域搜索算法(Genetic algorithm variable neighborhood search,GAVNS),该方法通过交叉、随机扰动、自适应邻域选择等操作,使解的搜索更加高效和灵活。对我国黄淮海平原72个小麦生产区县的作业需求进行计算与分析:不同算法相比,本文设计的算法得到最优解的迭代次数更低、收敛速度更快,求得的目标函数值较遗传算法、变邻域搜索算法分别降低16.41%、11.15%;对比不同调度模式,开放路径模式更有利于提升跨区调度服务效率,较闭合路径模式,调度成本降低17.76%。

资源受限项目调度中基于邻域搜索的混合遗传算法

分析了资源受限项目调度问题,针对其具有NP hard的特点,提出了一种基于邻域搜索的混合遗传算法,将启发式算法与遗传算法相结合,用邻域搜索的思想进行变异操作.结果表明,该算法不仅保证了算法的全局收敛性、而且提高了算法的收敛速度和解的稳定性.

基于混合变邻域遗传算法的柔性车间调度研究

针对柔性作业车间调度的问题,以最大完工时间为目标建立数学模型,提出一种混合变邻域遗传算法。采用三种初始化方法保证初始解的质量,用遗传算法进行初步搜索,将搜索的结果通过迭代贪婪策略进一步搜索,以提高解的质量,再对关键路径进行邻域搜索,设计“跨机器工序搜索邻域”、“同机器工序搜索邻域”、“次优工序搜索邻域”三种邻域结构,加强局部搜索能力。引入迭代贪婪策略和改进的邻域结构可显著提高算法的稳定性与迭代速度。通过对国际通用的柔性作业车间调度基准算例进行测试,实验结果表明所提改进算法能够有效求解柔性作业车间调度问题。

基于自适应大邻域搜索的遗传算法求解VRPTW研究

针对传统遗传算法在求解带时间窗的车辆路径问题(vehicle routing problems with time window,VRPTW)上存在的易陷入局部最优及求解质量不高等问题,本文主要对基于自适应大邻域搜索的遗传算法求解带时间窗车辆路径问题进行研究。通过将自适应大邻域搜索算法与遗传算法相结合,称为ALNS-GA设计了3个移除算子和2个重插算子,以提高遗传算法的局部搜索能力,并优化了初始种群生成策略。同时,为了验证算法的有效性,分别对比了传统遗传算法和基于大规模邻域搜索的遗传算法(LNS-GA、LNS*-GA),并选取Solomon数据库上VRPTW测试算例,在Matlab R2016b上进行实验验证。实验结果表明,当终止条件为迭代100次时,ALNS-GA的求解质量高于传统遗传算法,大部分案例中,ALNS-GA所求的最好值优于LNS-GA和LNS*-GA,且ALNS-GA平均用时均小于LNS-GA和LNS*-GA,特别是当顾客规模为100时,ALNS-GA的平均用时更少,虽然小部分案例的平均值略高于LNS-GA和LNS*-GA,但从整体上看,ALNS-GA的寻优速度和质量均优于LNS-GA和LNS*-GA,说明经过改进后,遗传算法的局部搜索能力明显提高,可以有效改善遗传算法在带时间窗车辆路径问题上的应用。该研究具有一定的创新。

混合进化算法求解多环节资源配置优化问题

资源配置优化问题是制造业价值链管理的基础问题。然而,现有研究多集中在生产环节,对制造全生命周期的整体考虑不足。研究考虑多环节的制造全生命周期资源配置优化问题(MLCRAOP),旨在通过优化研发设计、生产制造、运维服务和配套设备供应环节的服务资源,提升全生命周期的资源配置客户满意度。将时间、成本、质量指标纳入目标函数构建整数规划模型,提出一种混合进化算法用于求解MLCRAOP。通过在设计案例上的对比实验,验证了混合进化算法具有优异的性能。

求解复杂混合流水车间调度的改进NSGAII算法

针对砂型铸造车间调度问题中同时存在单机处理、并行处理与批处理的情形,构建复杂混合流水车间调度问题并提出一种改进非支配排序遗传算法求解上述问题。首先,以最小化最大完工时间和总能量消耗为优化目标建立线性规划模型,针对工序特征提出启发式解码规则。其次,提出了基于非支配的交叉对象匹配机制提升可行解的多样性,提出了基于区域中心的贪婪变邻域搜索机制提升可行解质量。最后,对改进算法进行了仿真,证明了算法的有效性。

基于改进遗传算法的舾装件托盘多载具协同拣选方法

为提升舾装件托盘的拣选效率,建立拣选过程的数学模型,提出一种基于改进遗传算法(Improved Genetic Algorithm, IGA)的舾装件托盘多载具协同拣选方法。针对遗传算法(Genetic Algorithm, GA)流程与实际拣选过程的差异,改进GA的初始化过程和染色体交叉方式,并对变异过程进行更贴近实际生产的修改。针对GA难以得到全局最优解的问题,采用变邻域搜索(Variable Neighborhood Search, VNS)策略降低陷入局部最优解的可能性。采用实例计算验证该算法的有效性,可优化传统舾装件托盘拣选方法。

基于混合遗传算法的城市固体废弃物运输路径优化研究

针对城市固体废弃物运输成本不确定的特点,文章在车辆路径问题的基础上对带时间窗的城市固体废弃物运输问题进行研究。考虑到遗传算法存在局部搜索能力不足的缺陷,在遗传算法的基础上结合变邻域搜索算法的思想提出了混合遗传算法。(1)采用三种邻域搜索算子用于改进遗传算法的变异算子;(2)采用模拟退火算法中的Metropolis判别法则来更新邻域搜索最优解;(3)采用自适应交叉变异概率和最优个体保留策略提高算法的运算效率。采用Solomen算例中的7个标准例题对算法性能进行测试,实验结果表明,混合遗传算法能够求得质量更高的解。最后通过算例来验证该模型的可行性,在满足时间窗和载重约束下缩短行驶距离。

基于粒子群优化和变邻域搜索的混合调度算法

提出了用于解决作业车间调度问题的离散版粒子群算法。该算法采用基于工序的编码和新的位置更新策略,使具有连续本质的粒子群算法直接适用于调度问题。同时,针对粒子群算法容易陷入局部最优的缺陷,利用粒子群算法和变邻域搜索算法的互补性能,设计了粒子群-变邻域搜索算法、改进的粒子群算法、粒子群-变邻域搜索交替算法和粒子群-变邻域搜索协同算法4种混合调度算法。仿真结果表明,混合算法能够有效地、高质量地解决作业车间调度问题。