《一条狗的使命》内地票房破三亿再放原片片段

　　卢嘉轩，李 晋，周 延

　　（上海大学 机电工程与自动化学院 工程训练国家级教学实验示范中心，上海 200444）

　　摘要：针对一种物联网医疗箱系统，提出了一套使用机器学习和蚁群算法的药物调度方法。该方法使用阈值划分的方式，对取药记录建立了岭回归、随机森林回归和神经网络的混合模型，以预测不同医疗箱中各类药物的需求量。之后，根据硬件检测的药物实际数量，计算出各药物的偏差值，在将调度问题转换为旅行商问题以后，分别使用基本蚁群算法和最大最小蚁群算法对调度问题进行了求解和对比。实验表明，该方法能较好地预测药物的需求量，规划出一条合理的药物调度路径，为物联网医疗箱系统的药物调度提供了一种数据驱动的解决方案。

　　关键词：蚁群算法；机器学习；物联网医疗箱；调度；旅行商问题

　　0 引言

　　随着智能医疗概念的兴起，自动售药机和自助医疗箱在英美等国得到了广泛推广，在我国也逐渐普及。然而，传统自动售药机在日常运营中需要进行人为的药物检查和补给，在药物的调度上也没有一套较为合适的方案。除此之外，由于地理限制和宣传力度欠佳，售药机常常无人问津，使用率较低。为此，一种基于物联网的校园医疗箱系统应运而生，该系统由若干放置在学校不同位置的联网的医疗箱所组成，可以在短时间内为师生突发的创伤提供及时有效的救治药物及必要的救援器具。该药物箱系统已在某高校进行了试运营，用户可以通过微信小程序的终端查看附近的药物箱位置和药物余量，所有取药记录也将上传至服务器，保存在数据库中。

　　本文基于该新型物联网医疗箱系统，提出了一种根据历史取药记录和药物余量进行调度的通用方法。该方法分为药物需求量预测和药物调度路径规划两大步骤。在需求量预测的实验中，针对历史取药记录，建立了岭回归、随机森林回归和神经网络的混合模型，以预测各医疗箱中药物的需求量。在调度路径规划的实验中，将预测的药物需求量与实际数量进行比较，将偏差量定义为药物实际数量与预测需求量之差。该方法将药物的调度问题转化为多个供应商和多个需求者之间的特殊旅行商问题(Traveling Salesman Problem,TSP)，并分别使用基本蚁群算法(Ant System,AS) ^[2] 和最大-最小蚁群算法(Max-Min Ant System,MMAS) ^[2-5] 进行了求解和对比。该方法能为新型物联网医疗箱系统的药物分配与调度提供解决方案，有效降低日常运营成本。

　　1 需求量预测

　　由于物联网医疗箱具有药物检测、数据上传的特点，因此所有的取药记录和药物余量都会保存在云服务器中，这也为模型的建立提供了必要的数据支持。对于某类存放于医疗箱中的药品，影响其需求量的因素可以大致概括为3类：所处时间，医疗箱地理位置和药物自身特性。针对医疗箱系统而言，取药记录间接地反映了特定时间、特定地理位置上各类药品的需求量。为此，可以通过历史取药记录的数据，建立上述3类因素到药品需求量的映射关系。

　　具体地，所处时间包括历史取药日期以及对应的月份和星期；地理位置包括医疗箱所处的经纬度数值和地理画像，如地图兴趣点(Point of Interest,POI)密度、是否位于宿舍、食堂、运动场、体育馆、实验室等特殊场所等；药物自身特性，包括药物所属的类别以及由行业认可的药物评审数据库提供的药物评分等。在获取并整合上述数据以后，即可以使用机器学习算法构建药品需求量与各因素之间的模型，即通过输入上述特征来预测特定日期、特定地理位置下某药品的日需求量或多日需求量。本文使用的模型包括岭回归、随机森林回归和神经网络。

　　岭回归(Ridge Regression) ^[9] 是线性回归问题中一种改良的最小二乘估计法，即在最小二乘估计法的损失函数中加上L2正则项，通过放弃最小二乘法的无偏性为代价以获得更合适的回归系数，防止过拟合。岭回归由于可供训练的参数较少，在数据量不太大、线性可分性强的问题上表现较优。

　　随机森林回归(Random Forest Regression) ^[9-11]是一种针对分类与回归树(CART,Classification AndRegression Tree)进行集成的方法，通过取每棵CART回归树叶子结点的均值来得到预测值。相比于使用最小化基尼系数来选择特征的CART树，随机森林往往拥有更强的泛化能力，在处理回归问题上也具有较好的通用性。

　　神经网络(Neural Networks,NNs) ^[9,10,12] 也称人工神经网络，是一种模仿大脑神经突触联接的结构进行信息处理的数学模型。该网络使用大量基本神经元进行计算，并能通过反馈机制来优化网络参数，拥有学习的能力。深度神经网络在拥有大规模训练数据的任务上表现突出，但由于可供训练的参数数量庞大，在数据量过小的任务中可能逊于普通的机器学习算法。

　　由于不同医疗箱中的药品索取量和需求量可能不在同一个量级上，使用单一模型进行预测并不合适。为此，本文采用阈值划分的方式，针对数据量小于某个阈值的药品，采用简单的岭回归模型进行预测；而针对数据量大于该阈值的药品，采用较为复杂的随机森林回归和神经网络共同进行预测，并把这两个模型输出的均值作为最终的预测值。实验表明，这种方式能获得比单一模型更高的准确率。

　　2 调度路径规划

　　2.1 问题描述与建模

　　物联网医疗箱的药品调度是医疗箱系统日常运营中的关键问题，主要包括数量和路径两大难题，即需要向各医疗箱投放多少药品以及如何规划投放和调度的路径。在传统的自动售药机模式中，运营方需要事先预估各售药机的药品需求规模，并人为地对药品的余量进行检查和补充，是一种基于经验的方法。而在数据驱动的物联网医疗箱系统之下，由于所有的药品需求量可以由已训练的网络计算得出，因此可以将预测值与硬件检测的实际药品数量进行比对，确定各类药物的供需关系。

　　为此，本文假设医疗箱中的药品数量需要满足该药品N日内的需求，并定义医疗箱k中药品的偏差量β _k,i 为当前该药品的实际数量与该药品N日需求总量之差，即

其中，r _k,i 为医疗箱k中当前药品i的实际数量，可以由硬件检测并上传数据库获取得到；p _k,i 为预测的医疗箱k中药品i的日平均需求量。若β _k,i 大于0，表明该医疗箱中的这类药品处于供大于求的状态，可以调出；若β _k,i 小于0，则表明该药品处于紧缺状态，希望调入。由此，医疗箱系统的药物调度问题即可转化为一个特殊的旅行商问题(TSP)，即派一辆小车从特定站点出发，访问各医疗箱和药房、医院、仓库等药物供应站点，寻找出总路程最短的Hamilton圈，并在这个过程中完成药物的调度。

　　设G=(C,L)是一个有向图，其中 C ={ c ₁ , c ₂ ,?，c _m }为m个医疗箱或供应站点的集合，L={l _ij |c _i ,c _j ∈C为集合C中元素两两连线构成的边集， d _i,j ( i,j =1,2,..., m )为医疗箱 i 和j 之间 l ij 的行车距离，可以通过调用地图软件API接口获取其数值。在传统的TSP问题中，所有的站点是没有区分性的，即可以任意选择站点作为路径的延续。而在本问题中，由于需要进行药物的调度，因此对于候选站点k的选择有如下的约束条件：

其中，a _i 为当前货车上已有药物i的数量，β _k,i 为医疗箱k中药品i的偏差量，Maxload为货车的负载量上限。当结点k的偏差量大于等于0，即该药品供大于求时，需要将其移上货车，要求移上货车后药品总数量不超过货车的最大负载量；当结点k的偏差量小于0，即该药品供不应求时，要求货车上有足够多的该类药物以补给医疗箱。

　　如果一个医疗箱中所有药品都满足上述约束条件，且该站点还未访问，则称该站点为该时刻的有效候选站点。

　　调度路径搜索的目标就是不断选择有效候选站点，直到所有站点都已被访问。

　　2.2 基本蚁群算法

　　蚁群算法(Ant System,AS)是一种模拟进化的算法，由意大利学者多里科(Marco Dorigo)于1991年提出，通过模拟蚂蚁在觅食过程中释放信息素优化路径的行为，构建了一套人工的蚂蚁系统。蚁群算法在求解TSP问题中得到了广泛应用，也因此作为本文医疗箱药物调度问题的基本求解算法。

　　在算法的开始，将q只蚂蚁随机地置于m个医疗箱站点上。对于每只蚂蚁，都拥有一张属于自己的禁忌表tabu _k ，用来表示蚂蚁k已经访问过的医疗箱站点。在本问题中，由于候选站点的约束条件限制，因此需要额外设置一张无效候选站点表invalid _k 作为不满足公式(2)的候选站点的集合。

　　在t时刻，在医疗箱 i 处的蚂蚁 k 需要根据该时刻的有效候选站点集J _k (i)，依据某一概率函数选择下一个站点j。其中，有效候选站点集J _k (i)为去除了禁忌表中元素和无效候选站点表invalid _k 中所有元素的站点集合，即

蚂蚁从站点转移到站点的转移概率定义为：

否则其中， α 为信息启发式因子，表示轨迹的相对重要性；β 为期望启发式因子，表示能见度的相对重要性； η _ij (t)是启发函数，表示蚂蚁 k 从站点 i 转移到站点 j 的期望程度，这里取站点 i 和站点 j 实际行车距离的倒数，即

式中，站点 i 到站点 j 实际行车距离 d _i,j 越小，则 η _ij (t) 越大，因此 η _ij (t) 可以表示为蚂蚁从站点i转移到站点j的期望程度。

　　在算法的起始阶段，所有边上的信息素量是相等的，即 τ _ij (0)=C ( C 为常数)。当所有蚂蚁都寻找到一条Hamilton回路后，各路径的信息素量根据下式来更新：

其中， ρ 为信息素的蒸发系数， Δτ _ij (t) 为本次迭代中边 l _ij上信息素的增量， Δ 为蚂蚁 k 在本次迭代中留在边l _ij 上的信息素。在Ant-Cycle模型中，定义为：

式中， Q 为正常数，表示信息素的强度； L _k 为蚂蚁 k 在本次迭代中所经路径的总长度。在每一轮迭代中，所有的蚂蚁都去寻找一条Hamilton回路，并更新信息素，开始下一轮迭代。当迭代轮次达到最大进化次数时，算法结束，当前的最优Hamilton回路即为算法寻找到的最优调度路径。

　　2.3 最大最小蚁群算法

　　基本蚁群算法提供了一种求解TSP问题的方案，但是其存在收敛速度较慢、易陷于局部最优的缺点。为此，Stutzle和Hoos提出了最大-最小蚂蚁系统(Max-MinAnt System, MMAS)。相较于基本蚁群算法(AS)，最大最小蚁群算法做了如下改进：

　　1)采用全局信息素更新，即在每一轮迭代结束后，仅更新本轮或全局最优解路径上的信息素，以加强最优解的影响力，即将式(6)和(7)修改为：

其中，为本次迭代中最优路径或全局最优路径上信息素的增量，其值等于最优路径的总长度 L _best 的倒数。

　　2) 限制每条边上的信息素在固定范围[τ _min ,τ _max ]内，避免某条路径上的信息素量远大于其他路径，造成算法过早收敛于局部最优解。

　　3)将初始时刻各条边上的信息素量τ _ij (0)设为τ _max ，而不再是一任意的常数 C ，使算法在初始阶段能拥有较高的随机性，以提高发现全局最优解的概率。

　　3 实验与结果分析

　　3.1 数据描述与预处理

　　本文的实验数据来源于正在上海大学宝山校区试运营的医疗箱系统后台，由于用户需要使用微信小程序进行取药，因而所有的取药记录都会保存在云服务器的MySQL数据库中。取药记录包括取药时间、医疗箱编号、药物编号、药物名称等字段。本实验使用Python访问数据库，读取取药记录，并进行了数据的处理和整合，统计出了各医疗箱中各类药物的平均日索取量。

　　针对取药日期，将其转化为项目开始运营到该日期的偏差天数，并加入该日期所对应的月份和星期作为模型的输入字段；针对医疗箱位置，调用经纬度转换函数将其编码为可以用单个字段反映地理坐标的GeoHash格式 ^[13] ；针对医疗箱所在位置的特殊地理类型，如运动场、游泳馆、实验室、宿舍等，分别进行One-Hot编码将其转化为8个字段；针对药物评分，通过API接口调用了全球药物评审数据库SERMO的相关评分数据。

　　为了更好地刻画医疗箱的地理画像，本实验调用Google地图接口分类统计了各医疗箱地理坐标附近的兴趣点(POI)数量，包括餐饮类数量、公司企业类数量、购物商场类数量、交通设施类数量、道路地名类数量等。最后，将所有上述字段和对应的日索取量进行归一化处理以消除量纲的影响。

　　3.2 需求量预测

　　本文假设历史取药记录中的索取量间接地反映了特定医疗箱中该药品的需求量，希望能够构建一个由上述特征到药物日平均需求量的映射关系。由于经预处理后的特征向量维数过高，本文使用主成分分析(Principalcomponents analysis,PCA)的方法对特征向量进行降维，并以8:2的比例划分训练集和测试集。

　　本实验中，设定划分阈值为 w ，即训练集中数据条目少于的 w 药品，使用岭回归进行建模，否则分别使用随机森林回归和神经网络进行建模与预测。其中，岭回归和随机森林由Python的机器学习库Scikit-learn实现，随机森林的子模型数n_estimators设为30；神经网络使用Keras框架下的反向传播算法(BP)进行实现，包括输入层和输出层共6层，每层的神经元个数分别为[31,100,50,30,10,1]，激活函数使用ReLU函数，梯度优化使用Adam算法，本文使用均方根误差(RMSE)来衡量模型的预测精度，即

式中， p gt,i 为真实的药品平均日需求量， p _model,i 为模型预测出的药品日需求量。本实验根据上述参数设置，调整划分阈值w，针对数据量小于w的药品统一使用岭回归进行建模，针对其他药品分别使用随机森林回归、神经网络、随机森林与神经网络取均值的算法进行了实验，计算出了所有药品的整体均方根误差，如表1所示。

　　3.3蚁群算法路径调度

　　在得到各医疗箱中各类药品的日需求量，即可根据硬件检测的实际数量计算出各类药品的偏差值。实验中假设 N =7，n =5,即每个药物箱中共有5件药品，要求调度结束后每件药品能够满足7日的需求量。由于当前物联网医疗箱仅在上海大学宝山校区试点运营，数量不多，因此本文模拟了50个医疗箱和药品提供商的站点，以检验蚁群算法的调度效果。本实验使用Python的图形化GUI库Tkinter分别编写了基本蚁群算法和最大最小蚁群算法，程序界面如图1所示。

　　图 中 每 个 站 点 上 方 的 五 元 组( β _k,1, β _k,2 ,β _k,3 ,β _k,4 ,β _k,5 )表示当前医疗箱 k 中5件药品的偏差值，其中黑色填充的结点代表货车的起始结点。以使用基本蚁群算法，设置蚂蚁种群数q=50，货车最大负载量 Maxload =800，信息启发因子 α =1.0，期望启发因子 β =1.0，信息素强度 Q =100为例，得到的最优调度总距离为4501，调度路径如图2所示。

　　为了比较基本蚁群算法(AS)和最大最小蚁群算法(MMAS)在该问题上的效果，本文分别就不同的货车最大负载量 Maxload ，分别使用两种算法进行了检验，寻找到的最优路径长度如表2所示。

　　可见，最大最小蚁群算法(MMAS)往往能够得到比基本蚁群算法(AS)更优的解；此外，货车最大负载量Maxload 也会在一定程度上影响到最优调度路径。

　　4 结论

　　本文针对一种新型物联网医疗箱系统，提出了一套使用机器学习和蚁群算法的药物调度方法，使用岭回归、随机森林回归和神经网络的混合算法建立了药品需求量的预测模型，并使用基本蚁群算法和最大最小蚁群算法对药品的调度问题进行了求解。该方法为物联网医疗箱系统提供了一种有效的解决方案，简化了日常运营维护的过程。此外，在其他的调度问题中，该方法也提供了一种可参考的解决思路。

　　致谢

　　最后感谢上海大学机电工程与自动化学院“挑战杯”大学生课外学术科技作品竞赛项目对本文的研究所提供的支持。以及上海大学“罗姆杯”大学生机电工程创新设计大赛对本文研究的支持。

　　参考文献：

　　[1] 赵安琪.自动售药机破冰之路[J].中国药店,2010(10):32-32.

　　[2] 陈雷毅,潘荣,许强,等.高校校园自动售药机的再设计[J].大众文艺,2016(11).

　　[3] Zhao G, Luo W, Sun R, et al. A Modified Max-Min Ant System for Vehicle RoutingProblems[C]// International Conference on Wireless Communications. IEEE, 2008.

　　[4]段海滨.蚁群算法原理及其应用[M]. 北京 科学出版社,2005.

　　[5] Stützle T,Hoos H H.MAX–MIN ant system[J]. Future generation computer systems, 2000,16(8): 889-914.

　　[6] 陈昌敏,谢维成,范颂颂.自适应和最大最小蚁群算法的物流车辆路径优化比较[J].西华大学学报（自然科学版）,2011,30(3).

　　[7] 李勇,段正澄.动态蚁群算法求解TSP问题[J].计算机工程与应用,2003,39(17):103-106.

　　[8] 柴宝杰,刘大为.基于粒子群优化的蚁群算法在TSP中的应用[J].计算机仿真,2009,26(8):89-91.

　　[9] Peter Harrington. Machine learning in action [M].2013.

　　[10] Liaw A, Wiener M. Classification and regression by randomForest[J].R news,2002,2(3):18-22.

　　[11] Bose N K, Liang P.Neural Network Fundamentals with Graphs,Algorithms,and Applications(McGraw-Hill Series in Electrical Computer Engineering)[J].1996.

　　[12] Balki? Z, ?o?tari? D, Horvat G. GeoHash and UUID identifier for multi-agent systems[C]//KES International Symposium on Agent and Multi-Agent Systems: Technologies andApplications. Springer, Berlin, Heidelberg, 2012: 290-298.

　　[13] Cassel M, Lima F.Evaluating one-hot encoding finite state machines for SEU reliabilityin SRAM-based FPGAs[C]//On-Line Testing Symposium, 2006. IOLTS 2006. 12th IEEEInternational. IEEE, 2006: 6 pp.

　　作者简介:

　　通信作者：李晋，男，上海大学机电工程学院实验师，硕士，主要从事微控制器技术，人工智能算法应用优化。

　　第一作者：卢嘉轩，男，上海大学计算机学院本科生，主要从事人工智能算法研究。

　　第三作者：周延，男，上海大学计算机学院本科生，主要从事人工智能算法研究。

　　本文来源于科技期刊《电子产品世界》2019年第7期第80页，欢迎您写论文时引用，并注明出处