一种基于改进海鸥优化算法的柔性作业车间调度方法

技术领域

本发明涉及柔性车间调度技术领域，特别是涉及一种基于改进海鸥优化算法的柔性作业车间调度方法。

背景技术

作业车间调度问题(Job Shop Scheduling Problem，简称JSP)由来已久，并被定义为NP-hard问题，其主要特点是随着车间机器数量和作业数量的增加，调度解的数目会爆炸式增长，所以JSP是复杂程度非常高的工程化数学问题，柔性作业车间调度问题(Flexible Job Shop Scheduling Problem，简称FJSP)是对JSP的扩展，增加了调度的灵活性和复杂性。FJSP涉及柔性制造，每个生产过程有多台机器与其对应，所以在工序排序的同时，还需要进行机器设备的选择。FJSP是一个选择和优化的过程，即需要在满足加工生产条件和约束的前提下，对加工时间、成本、能耗等生产目标进行优化，进而满足工厂生产的需求。FJSP是企业在实际加工生产中最难以解决的调度问题之一，具有解决难度复杂、问题分类广泛等相关特点，不但是科学研究的重点难题，还在建筑、航空航天、钢铁等诸多行业之中直接关系着车间生产质量，因此一经提出就被研究界和企业所重视。

海鸥优化算法(Seagull Optimization Algorithm，SOA)是一种受海鸥生物学行为启发而提出的一种群智能优化算法。该算法主要模拟了自然界中海鸥迁徙以及迁徙过程中的攻击行为(觅食行为)。迁徙行为即海鸥从一个现阶段不适宜生存的地方飞往另一个适宜生存的地方，迁徙时每只海鸥的所在位置不同，以避免相互碰撞。在一个群体中，海鸥可以朝着最佳位置的方向前进，改变自身所在的位置。迁徙行为影响着SOA算法的全局探索能力。攻击行为即海鸥在飞行过程中对地面、水域内食物的攻击觅食，在进攻时海鸥群体做出螺旋形的运动形态，攻击行为影响着SOA算法的局部开发能力。

强化学习属于机器学习的一种，其大体流程是通过智能体和环境交互获得当前状态，根据当前状态和知识库选择一个决策并作用于环境，收到环境对于该决策的评价奖励并更新关于决策的知识库。通过这种方法，强化学习可以通过不断的“试-错”逐步学会如何可以获得最大奖励值。

发明内容

为了克服上述现有技术中柔性作业车间调度问题的不足，本发明提供了一种融合了强化学习的海鸥优化算法柔性作业车间调度方法，其通过改进初始化种群解决搜索空间小的问题；通过重新设计局部搜索模型解决海鸥优化算法容易陷入局部最优的问题；通过融入强化学习的方式使离线训练后的模型可以快速适应新的问题环境。

为实现上述目的，采用了以下技术方案：

一种融合Q-learning改进海鸥优化算法的柔性作业车间调度方法，应用Logistic混沌映射种群初始化方案、改进的局部搜索模型、在参数选择上融合了强化学习算法来优化柔性作业车间调度问题，以获得更好的排产调度方案，提高生产效率；具体过程包括以下步骤：

已知有n个工件(J

步骤1：采用整数编码方式对生产序列进行编码处理。海鸥种群中的个体x

步骤2：初始化算法参数。主要包括种群大小numAgent、最大迭代次数maxIteration、上界ub、下界lb、采取改进局部搜索的比例P_Ipatical、维度dim；其中令numAgent＝50，maxIteration＝1000，ub＝1，lb＝0，P_Ipatical＝0.5。本发明中以柔性作业车间最大完工时间最小为优化目标，算法达到最大迭代次数终止。

步骤3：采用改进的Logistic混沌映射初始化每只海鸥的位置，使初始种群具有一定的质量和多样性；

步骤4：计算所有初始化种群内每个海鸥的适应度，即所求模型的目标函数值，取目标函数值最小的海鸥位置作为本代最佳海鸥位置；

步骤5：使用强化学习算法根据本代最优适应度值和本代最佳海鸥位置对决策变量的计算公式进行确定；

步骤6：根据海鸥迁徙模型公式驱使种群内每个海鸥个体靠近最佳海鸥位置；

步骤7：采用轮盘赌方式选择海鸥攻击模型公式或改进的局部搜索模型更新种群内每个海鸥的新位置；

步骤8：记录根据适应度值更新第t次迭代后每个个体的位置和全局最优解；若第t次迭代后全局最优解xi的适应度值小于第t-1次的适应度值，则更新xi的位置，否则保持上一代海鸥个体位置；

步骤9：判断迭代次数t是否达到最大迭代次数maxIteration，若是，则输出海鸥个体最优解既最优调度方案；否则，t＝t+1，并转至步骤5，并返回本次迭代奖励值以评价本次决策的优劣性。

所述的采用Logistic混沌映射初始化海鸥种群方案为：

随机产生一个每维均为0到1的d维向量作为第一个个体，之后用混沌映射表达式对第一个个体的每一维进行迭代得到剩余(M-1)个个体，最后使用海鸥初始化公式将Logistic映射产生的变量值映射到海鸥个体上。

Logistic混沌映射表达式为：

X

其中μ为映射参数，μ∈[0,4]，X为映射变量，X∈[0,1]。

海鸥初始化公式为：

其中LB为海鸥搜索空间的下界，UB为海鸥搜索空间的上界，X

所述的强化学习算法具体为：

在海鸥优化算法中通过一参数A平衡全局搜索和局部搜索，但在优化过程中，海鸥算法无法获得关于A取值的先验经验，只能通过固定的函数对A进行改变，这会导致算法能力无法完全开发出来。为此，将强化学习中的Q-learning算法融入海鸥算法中，将海鸥种群的位置作为状态输入Q-learning算法；根据当前状态，Q-learning算法按照Q表选择一个适合当前状态的动作a，即函数调整A值；观察本次动作执行的结果，即获得下一状态s’，同时得到一个奖励值r；最后对当前状态、动作、奖励、下一状态组成的状态传递矩阵[s,a,r,s’]进行学习，并更新Q表。强化学习得到目标时获得最大的累计奖励，在本发明中奖励值r被设置为负的最大完工时间。融合Q-learning的海鸥优化算法实施步骤如下：

Step 1：初始化Q表或读取已有的Q表；

Step 2：将海鸥种群作为状态s输入Q-learning算法；

Step 3：根据当前Q表和状态s，采用ε-greedy策略在动作集中选择一个动作a；

Step 4：执行动作a，海鸥种群位置更新为s’，并获得奖励r；

Step 5：智能体根据状态传递矩阵[s,a,r,s’]，并更新Q表；

Q(s，a)←Q(s，a)+α*[r+γ*max

Step 6：更新海鸥种群位置，s←s′；

Step 7：判断状态s是否为终止状态或迭代次数达到最大值，若不是，则转到Step3。

其中：

ε-greedy策略——表示以ε的几率随机选择动作，(1-ε)的几率选择Q表中奖励值最高的动作；

α——表示强化学习的学习率；

γ——表示对未来reward的衰减值.；

具体来说，对于本发明所述融合Q-learning的海鸥优化算法来说，其选择的动作集是针对全局探索和局部开发的平衡参数A的计算函数，在迭代第t次时：

(1)采用线性下降策略

(2)采用sigmoid下降策略

(3)采用非线性微分变化策略

(4)三次函数变化策略

所述的改进的局部搜索模型具体为：

鉴于海鸥算法开发性能差，迭代前期收敛缓慢的缺点，额外设计了改进的局部搜索模型。其局部搜索模型公式为：

其中

与现有技术相比，本发明的有益效果在于：

本发明在种群初始化阶段采用Logistic混沌映射初始化种群，与原始的随机初始化种群策略相比，能够获得具有一定质量和多样性的初始种群，有利于加快算法收敛速度。

本发明在海鸥算法搜索和更新种群个体位置时，引入了强化学习中的Q-learning算法，使算法可以自适应的进行学习，并且可以通过离线学习的方式完善自身知识库，有利于加快调度问题的求解速度，使种群个体快速达到最优状态。

本发明为平衡算法性能设计了4种参数迭代函数，丰富了海鸥算法的探索手段，并通过强化学习平衡海鸥优化算法全局探索和局部开发的能力，克服算法容易陷入局部最优的问题，从而能够得到更好的调度方案。

本发明改进了海鸥优化算法的迁徙过程，增加了新的局部搜索模型，可以提高跳出局部最优的能力，避免种群过早陷入局部最优解，提高收敛精度。

通过本发明，可以解决海鸥优化算法在迭代后期存在种群多样性减少，算法容易陷入局部最优的问题；加快了算法收敛速度并且在精确性上得到提升，可以使柔性作业车间的加工效率得到有效提升，并提高工厂的经济效益。

附图说明

图1为本发明的算法流程图；

图2为本发明Q-learning训练示意图；

图3为本发明35×6实例图；

图4为本发明中最大完工时间收敛曲线对比图；

图5为本发明中方法得到的最优调度方案甘特图。

具体实施方式

下面结合附图对本发明进一步说明。

针对柔性作业车间问题的特点，本发明提出一种柔性作业车间调度问题的融合Q-learning海鸥优化方法，解决以最小化完工时间为目标的柔性作业车间调度问题，该方法把Logistic初始化种群、强化学习Q-learning算法、局部强化策略融合进海鸥优化算法中，优化柔性作业车间调度问题。

1.柔性作业车间调度问题

1.1.问题描述

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,FJSP)是经典JSP的拓展，该问题中每个工序允许在一组可用机器中的任何一个上进行处理。

n个工件(J

调度目标是为每道工序选择最合适的机器，确定每台机器上各道工序的最佳加工顺序及开工时间，使整个系统的最大完工时间达到最优。

1.2.数学模型

假设有n个工件(J

C

式中：

C

c

c

c

s

p

v

取值为0表示其他情况；

L——一个非常大的正数。

在(1)-(5)式的递推关系中，式(1)(2)分别规定了最大完工时间和工件完工时间的取值约束；式(3)规定了工序在确定机器上加工的时间约束；式(4)规定了同一工件工序加工的顺序约束；式(5)规定了每一个工序仅可以在一个机器上加工。通过上述约束条件，最终得到调度问题的目标——最大完工时间最小：

minC

2.融合Q-learning海鸥优化算法解决柔性作业车间调度问题

该算法中种群显示海鸥个体的位置，并由一下矩阵考虑：

种群矩阵X为n行d列，其中n为海鸥总数，d为决策维度即工序数p×机器数m，每一行代表海鸥种群的一个个体的位置信息，x

2.1.编码方式

海鸥种群每一维x

然后找到其中按从小到大的顺序匹配工序与机器，本实施例加工工序与机器匹配情况为：O2在M2加工→O1在M2加工→O3在M1加工。

2.2.参数初始化

对算法用到的参数进行初始化。主要包括海鸥优化算法相关的种群大小numAgent、最大迭代次数maxIteration、上界ub、下界lb、采取改进局部搜索的比例P_Ipatical、维度dim；其中令numAgent＝50，maxIteration＝1000，ub＝1，lb＝0，P_Ipatical＝0.5。以及Q-learning算法相关的学习率lr、衰减系数γ、ε-greedy参数ε、目标值target、初始奖励值reward；其中lr＝0.01，γ＝0.9，ε＝0.9，target＝60，reward＝-999。

2.3.种群初始化

采用改进的Logistic混沌映射初始化每只海鸥的位置，使初始种群具有一定的质量和多样性。采用Logistic混沌映射初始化海鸥种群方案如下：

首先随机产生一个每维均为0到1的d维向量作为第一个个体；然后使用混沌映射表达式对第一个个体的每一维进行迭代得到第二个个体，以此方法依次迭代剩余个体，直到个体数量达到种群大小numAgent；最后使用海鸥初始化公式将Logistic映射产生的变量值映射到海鸥个体上。

Logistic混沌映射表达式为：

X

其中μ为映射参数，μ∈[0,4]，X为映射变量，X∈[0,1]。

海鸥初始化公式为：

其中LB为海鸥搜索空间的下界，UB为海鸥搜索空间的上界，X

2.4.计算海鸥种群最佳位置和适应度值

根据海鸥种群位置，依照编码方式，每一个海鸥个体都会得到一组加工工序与机器的匹配结果，其中最大完工时间最小的个体即为初代海鸥最佳位置，其适应度值即为本代海鸥最小的最大完工时间。

2.5.根据Q-learning算法选择海鸥种群收敛策略

Q-learning算法属于强化学习的一种，强化学习是智能体以“试错”的方式进行学习，通过与环境进行交互获得的奖赏指导行为，目标是使智能体获得最大的奖赏。其具体使用方法如下：

在海鸥优化算法中通过一参数A平衡全局搜索和局部搜索，但在优化过程中，海鸥算法无法获得关于A取值的先验经验，只能通过固定的函数对A进行改变，这会导致算法能力无法完全开发出来。为此，将强化学习中的Q-learning算法融入海鸥算法中，将海鸥种群的位置作为状态输入Q-learning算法；根据当前状态，Q-learning算法按照Q表选择一个适合当前状态的动作a，即函数调整A值；观察本次动作执行的结果，即获得下一状态s’，同时得到一个奖励值r；最后对当前状态、动作、奖励、下一状态组成的状态传递矩阵[s,a,r,s’]进行学习，并更新Q表。强化学习得到目标时获得最大的累计奖励，在本发明中奖励值r被设置为负的最大完工时间。

融合Q-learning的海鸥优化算法实施步骤如下：

Step 1：初始化Q表或读取已有的Q表；

Step 2：将海鸥种群作为状态s输入Q-learning算法；

Step 3：根据当前Q表和状态s，采用ε-greedy策略在动作集中选择一个动作a；

Step 4：执行动作a，海鸥种群位置更新为s’，并获得奖励r；

Step 5：智能体根据状态传递矩阵[s,a,r,s’]，并更新Q表；

Q(s，a)←Q(s，a)+α*[r+γ*max

Step 6：更新海鸥种群位置，s←s′；

Step 7：判断状态s是否为终止状态或迭代次数达到最大值，若不是，则转到Step3。

其中：

ε-greedy策略——表示以ε的几率随机选择动作，(1-ε)的几率选择Q表中奖励值最高的动作；

α——表示强化学习的学习率；

γ——表示对未来reward的衰减值.；

具体来说，对于本发明所述融合Q-learning的海鸥优化算法来说，其选择的动作集是针对全局探索和局部开发的平衡参数A的计算函数，在迭代第t次时：

(1)采用线性下降策略

(2)采用sigmoid下降策略

(3)采用非线性微分变化策略

(4)三次函数变化策略

2.6.更新海鸥个体位置

海鸥优化算法得到数学模型主要包括迁徙过程和攻击过程，其中迁徙过程主导了海鸥种群全局开发探索能力，而攻击模型主导了海鸥种群局部搜索能力。

2.6.1.迁徙模型

迁徙模型是根据海鸥生物学行为而设计的，在这个过程中，海鸥个体需要满足三个条件：

(1)防止个体碰撞

A＝f

x＝0，1，2，…，MAX

其中，

x——当前的迭代次数；

A——搜索代理在目标空间内所搜的移动参数；

f

MAX

(2)向最佳邻居方向移动

B＝2×A

其中，

B——随机数，增强算法全局优化和局部优化的平衡性；

rd——一个随机数，取值范围为[0，1]；

(3)靠近最优个体

其中，

2.6.2.攻击模型

海鸥种群在三位平面内的螺旋上升攻击模型描述如下：

x′＝r×cos(k)

y′＝r×sin(k)

Z'＝r×k

r＝u×e

2.6.3.改进的局部搜索模型

鉴于海鸥算法开发性能差，迭代前期收敛缓慢的缺点，本发明额外设计了改进的局部搜索模型。其局部搜索模型公式为：

其中

否则，海鸥个体根据如下公式更新位置：

2.7.融合Q-learning海鸥优化算法执行流程

步骤一：参数初始化；

步骤二：种群初始化并Logistic混沌映射；

步骤三：计算种群适应度值与最佳位置；

步骤四：强化学习代理选择动作；

步骤五：更新海鸥位置；

步骤六：强化学习代理学习本次策略；

步骤七：更新种群位置、适应度值与最佳位置；

步骤八：是否满足停止条件，满足则转至步骤九；否则迭代次数加一，并转至步骤四；

步骤九：根据种群最佳位置匹配加工工序与机器并输出。

3.实验与结果分析

本发明公开了一种柔性作业车间调度问题的融合Q-learning海鸥优化方法，该发明的效果通过以下实验进一步说明。

本实验在CPU为i5-7300U CPU@2.60GHz、运行内存为16.0GB的Windows10系统中使用PyChram 2020.1(Professional Edition)平台与Python 3.8进行了仿真。仿真实验调度采用了一个工件数为7、机器数为6，工序总数为35的柔性作业车间调度实例为研究对象，具体加工数据如图3所示。

仿真实验设计的参数设置如下：种群大小numAgent＝50、最大迭代次数maxIteration＝300、上界ub＝1、下界lb＝0、采取改进局部搜索的比例P_Ipatical＝0.5、维度dim＝210；以及Q-learning算法相关的学习率lr＝0.05、衰减系数γ＝0.9、ε-greedy参数ε＝0.9、目标值target＝60、初始奖励值reward＝-999。

将未经训练的融合Q-learning海鸥优化算法(QSOA_0)、,经过一千次训练后的融合Q-learning海鸥优化算法(QSOA_1000)、海鸥优化算法(SOA)和遗传算法(GA)进行对比测试，分别在仿真实例上独立运行十次，结果如表1所示。

表1 QSOA_0、QSOA_1000、SOA和GA计算结果

更好的调度方案可以实现节约生产时间、提高生产效率的目的。根据表1所得的实验数据可知，对提出的工件数为7、机器数为6，工序总数为35的柔性作业车间实例进行排产调度，未经训练的QSOA_0算法和经过一千次训练的QSOA_1000算法相比于SOA和GA算法，均取得较好结果；其中经过训练的QSOA_1000效果最好，十次调度结果最优值和平均调度结果均优于其他算法。

综上所述，本发明所提出的QSOA算法可以有效解决柔性作业车间调度问题，实现提高产线生产效率的目的。未经训练的QSOA算法已可以实现优于其他算法的性能，经过离线训练学习后，算法效果将会逐步提升，并且随着学习时间的增加，算法的收敛范围、收敛深度和收敛速度都将逐步提升。。