基于LSTM-GA混合模型的患者预约排队策略优化

魏若楠, 江 驹, 徐海燕

(1.南京航空航天大学 自动化学院,江苏 南京 211106; 2.南京航空航天大学 经济与管理学院,江苏 南京 211106)

0 引言

在国内外部分地区，患者通过预约进行身体检查或治疗。部分发达国家的预约就诊已经普及多年，然而排队现象依然常见，在公立医院尤为严重。虽然我国预约就诊尚未普及，但预约住院、手术、检查等已有所实施。部分预约项目排队现象十分严重，排队时间少则半个月，多则一年[1]。对病情很轻的患者而言，他们有能力接受一定程度的等待；对病情严重的患者而言，等待可能会加速病情恶化甚至死亡[2]。国外许多医院摒除先来先服务排队规则，目前我国部分医院也开始效仿此措施，2019年5月起，北京20家设有急诊的市属三甲医院启动了急诊预检的分级就诊[3]。在资源有限的情况下，将患者分配到怎样的位置，才能降低总体等待时间，合理服务各类患者，排队策略是解决以上问题的关键。

国内外对预约排队策略均有研究，卢林发等[4]将患者分为普通患者和预约患者，预约患者直接享有插队式服务，但是此方法只适合预约患者远少于普通患者的情况。刘鹏[5]对患者优先级、等待时间等因素加权求和，根据权重决定就诊顺序。权重按经验给出，并且只分了两个优先级，不能很好地描述现实情况。Wang等[6]结合患者类型和数量特点，动态调整每天的预约患者和当日来诊患者占有的资源比例。He等[7]研究了患者优先级提升的问题，给出了相邻优先级跨越所需的等待时间。Jiang[8]综合考虑患者的等待时间和优先级，利用网格法确定排队策略中的参数，但排队策略还有待进一步优化。

产生能反映真实情况的数据是排队系统仿真的关键一步。大多数研究遵循经典排队理论，将到达过程视为泊松分布，到达率为一个常值[9～11]。Bockstal等[12]进一步对泊松达到的两类病人分别给出了不同的到达率。周杰等[13]为CT室的常规患者建立了Gemo/NB/1排队模型。章顺悦等[14]为眼科患者建立了G/Ek/c排队模型。由此可见，到达过程并不能用统一的分布去描述。神经网络在学习与预测方面具有优势[15,16]。相比于其它神经网络，LSTM神经网络能够循环传递神经细胞的时域关联信息，更适合处理时间序列[17,18]。

借鉴上述研究成果，针对现有策略缺乏系统的优化、数据泛化能力不足的问题，本文建立了LSTM-GA的混合模型：以医疗大数据和深度学习技术为背景，首先，提出用LSTM神经网络学习历史规律，提高模型的对实际问题的描述能力。其次，利用智能优化算法对排队策略进行更深更广的优化。结合模拟退火算法和自适应交叉概率改进传统遗传算法，使全局搜索能力更强[19]。最后，将历史结果同优化结果对比，分析优化算法的有效性和策略的敏感性。

1 基于LSTM神经网络的数据预测

图1 LSTM神经网络结构

神经网络的训练过程如下

1)参数初始化

对神经元之间的权重系数随机赋予初始值。

2)前向传播

循环层内部结构如图2所示,t时刻的输出由内部模块的输出、t时刻输入以及偏置共同决定,循环层输出ht计算如下

图2 循环层内部结构

ht=ot×tanh(Ct)

(1)

(6)

(7)

式中，Wd是全连接层的权重矩阵，bd是全连接层的偏置项。

3)误差计算，计算样本输出与期望输出的偏离程度，误差L计算如下

(8)

式中y为样本的期望输。

4)反向传播,通过梯度下降法迭代更新所有参数，权重Wf的梯度如下所示

(9)

其余变量的梯度以此类推。

2 基于改进GA的排队策略优化

2.1 排队策略及目标函数设计

患者经医护人员预诊断,根据自身的病情轻重被分为不同优先级，病情越严重优先级越高，所期望的等待时间也越短。表1给出了某医院为患者划分的优先级和期望等待天数，优先级为1的患者级别最高，表示病情最严重，期望等待天数最短。

表1 患者优先级与预期等待天数

排队策略给每位患者赋予不同权重，按照权重大小给患者分配就诊顺序，权重越大，越优先占用医疗资源。若出现权重相同的情况，则预约申请时间更早的患者在前。权重w与优先级和等待天数相关，计算如下

w=a×Pi+b(t-Targeti),(i=1,2,3,4)

(10)

其中，a和b是决策变量，决定了优先级和等待时间对权重的影响程度；Pi是优先级i的初始系数；t是患者的等待天数，Targeti是优先级的期望等待天数，对应关系如表1。a、b、P1、P2、P3和P4为待优化参数，共同决定了患者-资源的分配原则。

将目标函数E设定为平均超出时间，对不同优先级患者的超出等待时间做加权处理。目标函数E如下

(11)

其中，N是仿真期间到达的患者总数；T是仿真天数；d是超出等待时间，即患者的等待时间减去其优先级对应的期望等待时间；ki是优先级的超出等待时间加权系数，分别取4,3,2,1;是超出等待时间为d天的患者人数。

本文结合该科室实际情况做出以下合理假设：

1)患者预约后会在队列中等待直到就诊。

2)患者的就诊时长与优先级无关。

3)患者一次的就诊时长不超过一天。

2.2 改进GA优化流程

遗传算法对优化问题没有太多的数学上的限制，对于多种形式的目标函数和约束，比如线性或者非线性，离散或者连续都可处理。由于算子具备各态历经性，因此算法能进行概率层面的全局搜素。

改进GA算法具体步骤如下

1)初始化

设置交叉概率、变异概率、种群的个体数目和最大迭代次数,给种群的染色体随机赋值。

2)编码与解码

采用二进制编码，解的精度为delta。对于第i个变量x，给出解的上边界Xi+和下边界Xi-，第i个变量的编码长度Li的计算如下

(12)

若第n个变量的染色体长度为n，其二进制编码Xi=bn-1bn-2,…,b0,要将二进制的编码解析为数学解，解码的计算方法如下

(13)

3)计算个体适应度

本文期望目标函数取得最小值，为满足当目标函数值减小时适应度值增大的要求，设计适应度函数与目标函数成反比。

4)选择

个体被选中的概率如下

(14)

其中Pi是第i个个体被选中的概率,indvi是第i个个体对应的解，M是种群的规模。

5)自适应交叉

简单遗传算法中交叉概率为常数，这使得算法的收敛能力和寻优能力不能相互协调。自适应交叉概率旨在实现搜索和收敛的平衡[21]。当种群多样性变高时，种群中最大适应度和平均适应度之间的差是增大的，交叉概率应当减小。交叉概率的计算如下

(15)

其中,Fmax和Favg是最大适应度和平均适应度,k1和k2是0到1之间的常数,F′是两个交叉个体中较大的适应度值。

6)模拟退火变异

模拟退火变异方法旨在跳出局部最优，寻找全局最优解[22]，以一定概率接受差的变异，概率按照Metropolis准则[23]计算如下

(16)

ΔE是能量的改变，应用于遗传算法即是变异前后目标函数的差值,Titer是系统的温度,iter是当前种群的迭代次数，T0是系统的初始温度。

7)重复上述步骤2)～6),直到迭代次数达到最大。

3 LSTM-GA混合模型优化系统

将LSTM神经网络与改进GA相结合，对策略进行优化，LSTM-GA混合模型结构如图3所示，其过程如下:

图3 LSTM-GA混合模型结构

Step1LSTM神经网络通过对历史数据的学习，产生四类患者的每日到达数量。四类患者分别为濒危、危重、急症和非急症。

Step2根据排队策略分配患者占有资源的先后顺序，权重大的患者排在队列前。

Step3LSTM神经网络产生每日服务患者的数量。完成治疗的患者离开队列，未完成治疗的患者更新自身属性。

Step4在仿真时长内不断重复Step1～Step3。

Step5策略优化模块统计患者的优先级、等待情况等属性，计算出目标函数值。利用改进GA算法不断迭代优化决策变量，降低患者等待时间。

本文待优化的参数是a、b、P1、P2、P3和P4，利用分层优化的思想将a、b定义为外部参数，P1～P4定义为内部参数。先对内部参数进行优化，然后基于此组内部参数再对外部参数进行优化。

4 案例计算与分析

4.1 数据预处理

为验证本文方法的有效性，获取了国外某医院某科室近五年患者预约检查的医疗数据，共包含55354条患者就诊信息，每条信息描述了病人申请治疗日期、优先级、期望等待天数和实际治疗日期等。

4.2 数据预测与对比分析

建立LSTM神经网络模型预测一年的患者每日到达量和每日服务量。为了验证本文LSTM神经网络预测的效果，本文建立经典排队理论的随机型输入过程与之对比。

结合经验公式以及反复试验[24],设计网络拓扑结构为7×16×32×1，分别为输入层、循环层、全连接层和输出层。为避免网络出现过拟合，一方面采用Hinton等[25]提出的Dropout技术，Dropout率为0.2，随机切断20%的神经元之间的连接；另一方面在循环层增加正则化方法，惩罚项系数0.001，应用于循环层的非偏置项。

假设每日患者到达量和服务量服从表2所列分布，对其进行非参数检验。服务阶段的泊松分布的渐进显著性略微高于0.05，其余分布的渐进显著性都低于0.05，说明了实际数据的特征不适合用上述经典分布描述。

表2 每日患者到达量与服务量分布检验

选择效果相对好的泊松分布和均匀分布与神经网络进行对比。以历史数据作为参考，对每日的患者到达数量进行预测，如图4所示，泊松到达太过平稳，未能体现真实的到达情况，均匀分布的到达过程波动剧烈，远远超出了真实状态，LSTM神经网络预测的到达过程很好地跟随了真实数据的规律。相应地对每日服务患者的数量进行对比，如图5所示，同样LSTM神经网络对趋势有更准确的预测能力。

图4 达到情况对比

图5 服务情况对比

采用表3评价指标评价预测能力，神经网络在各项指标上都明显高于随机分布的结果，说明了LSTM神经网络产生的到达过程和服务过程能更好地反映真实情况。

表3 各模型结果评价指标

利用LSTM神经网络预测每日到达的患者数量，根据历史数据统计各优先级患者的百分比，将预测得到的每日到达患者乘以各优先级百分比，得到每天各个优先级患者的到达数量。由于假设患者的治疗时长与优先级无关，所以每日服务的患者数量与优先级无关，直接以神经网络输出为当日服务数量。

将LSTM神经网络预测的数据输入混合模型，利用改进遗传算法对策略参数分层优化，算法的参数设计如表4所示，Pc是交叉概率，Pm是变异概率T0是初始温度，Acc是编码精度，Len是染色体长度，M是个体数目，Maxlter是最大迭代次数。

表4 优化算法参数设置

4.3 GA优化与对比分析

先优化内部参数，传统GA和改进GA优化内部参数的过程如图6所示。传统GA和改进GA分别将目标函数降到了15.58天和14.01天。将第一次优化得到的参数保存，再加入外部参数并对其优化。传统GA和改进GA优化外部参数过程如图7所示。在前次优化的基础上，目标函数值再次下降，最终分别为11.24天和为8.06天。由此可见，二次优化可以再次降低目标函数，改进GA的寻优能力仍然强于传统GA，得到了更优的解，最终优化参数如表5所示。

图6 内部参数优化过程

表5 最终优化参数

图7 外部参数优化过程

利用改进GA对多个年份进行优化,每个年份都分别仿真50次,将优化后目标函数的平均值与优化前的做对比,得到的结果如表6所示。可以看出优化后的策略给排队系统带来了可观的积极影响,优化后目标函数平均值明显低于优化前的目标函数值,表明了改进GA优化排队策略能够降低患者等待时长。标准差明显低于平均值,体现了优化算法的表现能力比较稳定。

表6 历年排队策略优化结果

4.4 策略敏感性分析

将先来先服务策略、严格优先级策略与本文得到最优累计加权策略对比。三种策略下各优先级超出目标等待天数的百分比如下所示。先来先服务策略是的超出百分比指标在各个优先级都表现不佳，严重阻碍了患者的就诊。严格优先级虽然给予了前三个优先级患者充分的就诊机会，但第四优先级患者的就诊受到了明显的限制，超过90%的第四优先级患者未能在其目标等待时间内就诊，从数量上分析损害了很大一部分患者的治疗。本文的累计加权策略给绝大部分病情严重的第一第二优先级患者及时治疗，对于第三优先级患者，超出百分比略高于严格优先级策略，但第四优先级患者的超出百分比有明显的降低，其分布更较前两种策略加合理。考虑平均超出等待时间，三种策略下该指标分别为11.73天、9.88天、8.06天，本文策略在超出百分比和平均超出等待时间上都取得了良好的效果。

图8 三种策略下超出目标等待时间的比例

为验证排队策略是否在各个时段都发挥作用，对策略进行敏感性分析。将300天的时间跨度平均分割为三个时段，每个时段都采用表5对应的排队策略，仿真得到三个时段优化后的目标函数值，与历史数据下的目标函数值对比。每年还余下65天或66天的数据未参与优化，再将策略应用于未参与优化的时段，对比分析策略发挥的效果。2014年的敏感性分析结果如图9所示，其余年份各时段的敏感性分析如表7所示。

图9 策略敏感性分析

表7 各时段目标函数值

从图9和表7可以看出,在各年各时段中，应用了排队策略的目标函数值都明显低于该时段的历史值，这表明排队策略在仿真各时段内均发挥了效能。因此本文优化的排队策略具有一定的稳定性和时间普适性。

5 结论

本文建立了LSTM-GA混合模型，对预约患者的排队策略进行了优化研究。在数据上,提出用LSTM神经网络预测到达过程和服务过程,提高了数据的泛化能力，增强了策略对未来的指导意义。在排队策略优化上,扩充了可优化参数集，从更广的范围对策略进行了优化；利用改进GA提高了全局搜索能力和收敛能力。本文获得的排队策略从总体上显著降低了患者的等待时长，策略在不同时段均能发挥明显效能，对时间因素具有一定的抗干扰能力。

本文的研究方法和成果对患者预约排队问题有一定的实际意义。虽然我国目前只在部分医院开展分级就诊和预约就诊，但随着探索的深入，这会成为将来就诊的重要手段。本文的研究为合理规划预约排队问题提供了一种有效的方法。同时本文也有待完善，未来可以研究多家医院之间医疗资源与患者相互分配的问题。