基于循环神经网络与强化学习的动态二分图分配长度决策方法与流程

1.本发明涉及动态任务分配技术领域，尤其涉及一种基于循环神经网络与强化学习的动态二分图分配长度决策方法。


背景技术：

2.动态二分图在匹配过程中需要对分配长度进行决策的原因是：在动态情况下工人和任务随机到达、离开，并且任务有不同难度，工人有不同能力使用工人能力与任务难度计算任务完成率；如果贪婪地在工人或任务到达时就直接分配难以最大化总完成率，而如果等待工人和任务达到固定的数量再进行分配可能导致工人和任务大量过期影响结果。
3.目前最接近的技术为wang y等
1.于2019年提出的基于q learning的rql(restricted q
‑
learning)方法于动态二分图情况下对分配长度进行动态决策。具体方法为根据当前工人任务状态选择不同动作得到的奖励使用贝尔曼方程持续更新q值，将这些q值保存到一个q表上。在某一状态下q值最大的动作即为当前最优动作。对状态于动作的定义如下：状态为工人和任务的时间和难度、能力等信息，但这样会使状态空间大到q表无法记录的程度，因此减小状态空间，使用当前工人、任务各自的数量组成二元组作为当前的状态。动作即为目标分配长度，在当前工人任务达到目标分配长度时进行分配。分配的奖励为使用匈牙利算法进行分配得到的总完成率作为奖励。状态转移，当前状态加上下一个时刻到达的工人任务的数量。
4.使用以往的方法可以进行分配长度决策，但还存在许多的不足：工人和任务有时间约束，超过则会过期，但很少有研究能够直接有效地将其应用到动态二分图匹配中。在rql方法中计算奖励时没有考虑过期工人任务应该对奖励计算进行惩罚以防止过长的分配长度。此外只考虑工人、任务且没有过期惩罚的情况下，该方法在可选的分配长度范围内会更倾向于选择较长的分配长度，难以对不同的情况做出动态的决策。
5.工人能力与任务难度参数只应用于确定进行分配后使用匈牙利算法分配的阶段，而实际上在进行分配长度的决策过程中工人能力与任务难度同样有很大的影响。考虑在一种情况下，工人任务距离过期时间较长，此使工人能力普遍较低而任务难度普遍较高，这种情况下如果进行分配其总完成率明显会较低，因此分配长度应当加长。


技术实现要素：

6.根据现有技术存在的问题，本发明公开了一种基于循环神经网络与强化学习的动态二分图分配长度决策方法，具体包括如下步骤：
7.s1：判断当前时刻是否有工人或任务到达，如果没有则直接结束，如果有则进入s2；
8.s2：若到达的是工人则将其加入可用工人集w，如果是任务则将其加入可用任务集t；
9.s3：根据时间信息获取当前可用的工人集w＝{w1,w2,...,w
n
}和可用的任务集t＝{t1,t2,...,t
m
}；
10.s4：读取工人集和任务集的参数信息；
11.其中工人集参数为包含所有工人能力和剩余时间的紧迫程度(紧迫程度公式剩余时间比持续时间)；
12.任务集参数为包含所用任务的难度和剩余时间紧迫程度(紧迫程度公式)；
13.s5：将工人参数和任务参数输入至强化学习网络中，所述强化学习网络输出分配q值和不分配q值，选择其中较大的q值对应的动作在当前时刻进行动作执行；
14.s6：若不进行分配，则直接跳至s8，若分配则进行s7；
15.s7：使用匈牙利算法对当前可用工人集w＝{w1,w2,...,w
n
}和可用任务集t＝{t1,t2,...,t
m
}进行任务分配，并记录分配奖励；
16.s8：将过期的工人和任务从可用工人集w与可用任务集t中除去,并记录过期惩罚；
17.s9：根据得到的奖励与惩罚训练强化学习网络并进入下一时刻，返回至s1等待新到达的工人或任务。
18.进一步的，判断是否有新工人和新众包任务到达，读取工人和众包任务信息，将一个工人采用一个四元组w＝<l
w
,s
w
,e
w
,a
w
>描述，其中l
w
表示工人位置，s
w
表示工人到达的时间，e
w
表示工人的离开时间，a
w
表示工人的能力，一个众包任务采用五元组t＝<l
t
,r
t
,s
t
,e
t
,d
t
>描述，其中l
t
表示任务的位置，s
t
表示任务开始的时间，e
t
表示任务的截止时间，r
t
表示任务分配范围，当距离在此范围内的工人才能执行该任务，d
t
表示任务的难度同时也是完成任务的奖励；
19.设当前时刻为c，若s
w
≤c<e
w
则将该工人或任务在当前时刻可用，当c≥e
w
则工人或任务过期不可分配。同理，若s
t
≤c<e
t
则该任务在当前时刻可用，当c≥e
t
则任务过期不可分配
20.在每个时刻判断是否有工人或任务到达，如果没有则结束，若到达的实体为工人到达则加入可用工人集，否则加入可用任务集，设当前的可用工人集记为w＝{w1,w2,...,w
n
}，当前的可用任务集记为t＝{t1,t2,...,t
m
}；
21.每个时刻进行分配长度的决策，具体方法为根据可用工人集与可用任务集的数据，采用强化学习网络决策是否在当前时刻进行分配，其中决策的目标为最大化总完成率并最小化工人任务过期数量，若在当前时刻进行分配则使用匈牙利算法对当前可用工人任务集进行分配最大化总完成率；
22.根据工人任务集构建二分图b＝<t,w,e>，e代表边，表示可进行分配的工人任务对，边的权值为完成率，采用p
ij
表示，公式如下：
[0023][0024]
当完成分配后记录奖励并除去过期工人任务与分配掉的工人任务进入下一时刻。
[0025]
进一步的，所述强化学习网络的交互环境为mdp模型、所述mdp模型包括环境存在
的状态网络选取的动作执行动作后返回的奖励执行动作后状态的转移函数
[0026]
其中状态定义为目前可用任务集参数与可用工人集参数其中u
w
、u
t
表示时间紧迫程度，计算方法如下
[0027]
动作定义为2个不同的动作，1表示进行分配，0表示不进行分配；
[0028]
奖励其计算公式如下：
[0029][0030]
表示匈牙利分配结果奖励减去分配成本减去过期惩罚，x
ij
表示匈牙利分配结果任务i分配给工人j则为1，否则为0，cost为分配成本，代表是否过期的布尔函数，过期为1，否则为0，若不进行分配则匈牙利分配结果与分配成本均为0；
[0031]
转移函数下一个状态为当前工人任务集减去过期工人任务集减去分配工人任务集再加上下一时刻到达的工人或任务，若未进行分配则分配工人任务集为空集。
[0032]
由于采用了上述技术方案，本发明提供的一种基于循环神经网络与强化学习的动态二分图分配长度决策方法，该方法在进行动态二分图分配长度决策时考虑了工人任务的剩余时间信息与工人能力任务难度这些与完成率有关的信息。因此在决策时可以全面地考虑各种参数，与先前的只考虑工人任务各自数量方法对比可以在各种情况下得到最好的结果；其次使用基于dqn的强化学习方法并使用lstm对数据进行预处理，解决了原本由于状态空间过大导致难以训练难以保存必须减小状态空间的问题；最后在奖励中考虑了过期惩罚的问题，不仅在状态中除去过期工人任务，而且在奖励中会进行惩罚，这就使得我们的方法会在最大化总完成率的同时考虑最小化过期数量。先前的方法中过期工人任务只表现在工人任务数量的减少上，因此其更倾向于较长的分配长度难以应对各种环境。
附图说明
[0033]
为了更清楚地说明本技术实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本技术中记载的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0034]
图1为本发明方法流程图；
[0035]
图2为本发明方法中强化学习模块网络结构示意图；
具体实施方式
[0036]
为使本发明的技术方案和优点更加清楚，下面结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚完整的描述：
[0037]
如图1所示的一种基于循环神经网络与强化学习的动态二分图分配长度决策方法，具体包括如下步骤：
[0038]
s1：判断当前时刻是否有工人或任务到达，如果没有则直接结束，如果有则进入s2；
[0039]
s2：若到达的是工人则将其加入可用工人集w，如果是任务则将其加入可用任务集t；
[0040]
s3：根据时间信息获取当前可用的工人集w＝{w1,w2,...,w
n
}和可用的任务集t＝{t1,t2,...,t
m
}；
[0041]
s4：读取工人集和任务集的参数信息；
[0042]
其中工人集参数为包含所有工人能力和剩余时间的紧迫程度；
[0043]
任务集参数为包含所用任务的难度和剩余时间紧迫程度；
[0044]
s5：将工人参数和任务参数输入至强化学习网络中，所述强化学习网络输出分配q值和不分配q值，选择其中较大的q值对应的动作在当前时刻进行动作执行；
[0045]
s6：若不进行分配，则直接跳至s8，若分配则进行s7；
[0046]
s7：使用匈牙利算法对当前可用工人集w＝{w1,w2,...,w
n
}和可用任务集t＝{t1,t2,...,t
m
}进行任务分配，并记录分配奖励；
[0047]
s8：将过期的工人和任务从可用工人集w与可用任务集t中除去,并记录过期惩罚；
[0048]
s9：根据得到的奖励与惩罚训练强化学习网络并进入下一时刻，返回至s1等待新到达的工人或任务。
[0049]
其中判断是否有新工人和新众包任务到达，读取工人和众包任务信息，将一个工人采用一个四元组w＝<l
w
,s
w
,e
w
,a
w
>描述，其中l
w
表示工人位置，s
w
表示工人到达的时间，e
w
表示工人的离开时间，a
w
表示工人的能力，一个众包任务采用五元组t＝<l
t
,r
t
,s
t
,e
t
,d
t
>描述，其中l
t
表示任务的位置，s
t
表示任务开始的时间，e
t
表示任务的截止时间，r
t
表示任务分配范围，当距离在此范围内的工人才能执行该任务，d
t
表示任务的难度同时也是完成任务的奖励；
[0050]
设当前时刻为c，若s
w
≤c<e
w
则将该工人或任务在当前时刻可用，当c≥e
w
则工人或任务过期不可分配；
[0051]
在每个时刻判断是否有工人或任务到达，如果没有则结束，若到达的实体为工人到达则加入可用工人集，否则加入可用任务集，设当前的可用工人集记为w＝{w1,w2,...,w
n
}，当前的可用任务集记为t＝{t1,t2,...,t
m
}；
[0052]
每个时刻进行分配长度的决策，具体方法为根据可用工人集与可用任务集的数据，采用强化学习网络决策是否在当前时刻进行分配，其中决策的目标为最大化总完成率并最小化工人任务过期数量，若在当前时刻进行分配则使用匈牙利算法对当前可用工人任务集进行分配最大化总完成率；
[0053]
根据工人任务集构建二分图b＝<t,w,e>，e代表边，表示可进行分配的工人任务对，边的权值为完成率，采用p
ij
表示，公式如下：
[0054][0055]
当完成分配后记录奖励并除去过期工人任务与分配掉的工人任务进入下一时刻。
[0056]
进一步的，所述强化学习网络的交互环境为mdp模型、所述mdp模型包括环境存在的状态网络选取的动作执行动作后返回的奖励执行动作后状态的转移函数
[0057]
其中状态定义为目前可用任务集参数与可用工人集参数其中u
w
、u
t
表示时间紧迫程度，计算方法如下
[0058]
动作定义为2个不同的动作，1表示进行分配，0表示不进行分配；
[0059]
奖励其计算公式如下：
[0060][0061]
表示匈牙利分配结果奖励减去分配成本减去过期惩罚，x
ij
表示匈牙利分配结果任务i分配给工人j则为1，否则为0，cost为分配成本，代表是否过期的布尔函数，过期为1，否则为0，若不进行分配则匈牙利分配结果与分配成本均为0；
[0062]
转移函数下一个状态为当前工人任务集减去过期工人任务集减去分配工人任务集再加上下一时刻到达的工人或任务，若未进行分配则分配工人任务集为空集。
[0063]
以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。