基于状态矩阵的降阶算法的自动化药房发药模式设计
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于状态矩阵的降阶算法的自动化药房发药模式设计范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：介绍一种常见的自动化药房系统模式，设计一种提高发药效率的状态矩阵降阶算法。分析自动化药房系统的运动时间算式并确定优化目标。基于状态压缩矩阵，利用降阶算法解决集合覆盖问题给出降阶切入点与具体流程。结合分支界限法解决一个问题实例。利用Matlab仿真分析该算法在自动化药房发药过程中的优化作用。计算该算法的时间复杂度和空间复杂度，结合实际问题与其他算法对比优劣性。
关键词：状态压缩矩阵；降阶算法；集合覆盖问题；自动化药房
中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2013）28-6392-06
自动化药房是一种能够利用软件分析电子处方，控制电机运动，从而驱动自动化药房设备自动发放药品的装置。该发药设备共有15层，每层35～42个储药槽。设备前侧的升降机平台运行到某一层后，该层的待出药品会自动由电磁铁弹出。药品储位布局如图1所示。
由于不同药品的需求量有差异，对于经常使用的药品，可以分配多个储位以保证库存量足够，从而减少上药作业的频率。在这种情况下，对一种药品就可以有多个储位可以选取，为快速出药算法的优化提供了可能。
1 优化目标的确定
1.1 自动化药房运行模式
药品出库时，出药模式程序会不断访问数据库的处方表，该表存有待处理的处方药品信息。一旦数据库接收到新的处方，出药模式程序就会读取处方中的药品信息，再根据用户选择的出药模式和各储位药品库存，计算出一个出药拣选路径，其中包含待出药的储位和每个储位的出药数量，并将这些信息写入出药表中。工控机上的出药运行程序根据出药表中的信息，控制出药升降机、电磁铁、出药口翻版电机和传送带电机运动，从而将药品按储药层依次打出，最后由传送带送至出药口。
出药拣选路径的设计由出药模式程序计算得出。出药程序对每种药品依次进行拣选计算：从储位信息表中获取该药品的所有储位及各储位库存，然后从储位号最小的储位开始取药，一个储位药品不够时会继续取下一个储位的药，直到药品全部取完。全部药品选好储位后将储位信息写入数据库。出药运行程序根据出药数据库中所有要出的储位及其出药数量，控制升降机从高层到低层逐层出药，升降机平台运行到某一层后，该层不同的储药口可同时出药。升降机启动前和停止后都在第5层，即出药口的位置。
1.2 优化目标
根据上述运行模式建立模型：忽略升降机平台的加减速过程和储药层高的微小差异，即认为升降机运行任一层时间均为Tlayer，设出每盒药的时间为Tmed，则一个处方出药的总时间为
由公式（1）可以看出，出药时间的长度取决于Lmax和Lmin的取值，以及对应每一个L的MLn的最大值。在快速发药系统中，由于药品的使用频率不同，用户会给使用频率高的药品分配更多的储位，这使得出药过程有多种拣选路径可选择。算法优化前，任何一种药品都会优先拣选储位号最小的储位。根据公式分析，可以从以下方面进行优化：
1）应尽量使Tlayer的因子更小：如果一种药品在第5层有储位，从第5层拣选将是最优的选择，可以省去升降机平台为该药品做额外的运动。
2）应尽量使L的取值更少，即减少总拣选行数。如果多种药品同时在某一层有分配，从这一层拣选可以使升降机停留更少的储药层。
3）应尽量使同一层中MLn的最大值更小，如果某种药的出药数量较大，则应将这种药分散到多个储位同时出。
该文将介绍选取最少的发药层数的算法。
2 状态压缩矩阵的降阶
2.1 集合覆盖问题的提出
最小拣选层数策略要求对于一个处方的药品，尽量从更少的层拣选，这样可以使同一层同时出尽量多的药品。根据公式（1），减小其中的表达式（2）可以使设备拣选更少的层数。当L的值越小，在每种药品只出一盒的情况下，表达式（2）值就会越小。
这个问题可以描述为：对于给定的若干种药品，选中最少的储药行，在这些行中可以包含所有药品。该问题可以抽象成集合覆盖问题，即给定一个实例[]，X为一个有限集，F为X的一个子集族且覆盖了有限集X，即[X=S∈FS]。对于F中的一个子集[C?F]，如果[X=S∈CS]，则称C覆盖了X。集合覆盖问题的目标是找到F中覆盖X的最小子集Cmin，使[Cmin=min{C|C?F，X=S∈CS]。该抽象模型对应到原问题：集合F的元素是各储药层，每个储药层是一个集合，其元素是该层所含的待出药品；集合X为所有待出药品的集合。
集合覆盖问题（SCP，Set Covering Problem）是运筹学和计算机科学领域的NP难解问题，对此问题，目前已有的算法如启发式算法[4]，近似算法[3]，穷举法等，这两种算法的软件实现较为复杂，尤其是穷举法，其算法复杂度为O（n！）级，随着药品数量增大，程序复杂度的增长速度极快，很容易造成工控机卡死，不适用于自动化设备控制软件设计。该文提出了状态压缩矩阵的降阶算法结合分支界限法。充分利用了状态压缩矩阵利于软件实现的特性，将有效缩小算法复杂度和实现难度。
首先将该问题转化成状态压缩矩阵来表示。转化方法为：将集合覆盖问题[]中的F的所有元素记录成矩阵的行，X中的元素记录成矩阵的列。当某一行包含待出药品X中的元素时，矩阵中这一行和这一列对应的值为1，否则为0。
2.2 状态压缩矩阵的降阶算法
例如公式（3）所示矩阵，可以看成是具有10层储药层的快速发药系统，第一行的第一列和第三列为1，表示储药层第1层中包含了处方中的第1、3种药品，取得第一行则可以得到1、3两种药品。第五列的第二、七、八行均为1，表示若要取得第5种药品，从第二、七、八任意一行取都可以。解题目标是从所有行F中选中最少的行，使得对于每一列，这些行中至少有一行的值为1。
1）如果第j列仅在第i行处为1，在其余行均为0，则第i行必选；
证明：由于第j列所代表的药品必须被某一行选取到，而该药品仅仅属于第i行，因此要得到该种药品，第i行一定在最少选行中。
2）如果对于行i1、i2，i1行完全覆盖i2行，即对任意行，如果在i2处为1，则该行在i1处也为1。此时将i2行删除不选，并不影响最少选行问题的求解。
证明：由于i1行完全覆盖i2行，则i2的覆盖作用完全可以有i1行代替。代替后的覆盖作用相同或更强，不会减弱。
3）如果对于第j列，任意行都不能覆盖，则断定该问题无解。
证明：这是一种极特殊的情况，严格来讲这种问题不属于集合覆盖问题。因为集合覆盖问题的前提是给定一个实例[]，X为一个有限集，F为X的一个子集族且覆盖了有限集X。这种情况下，F的全部子集都无法覆盖有限集X。但在软件实现的过程中，以及自动化药房运行过程中，如果处方发错或药品库存不够，确实会遇到这种问题。因此该文将这个规则也视作软件实现中的降阶规则。
对于降阶过程中的任意矩阵，如果遇到某一行完全覆盖所有列或未覆盖任何列的情况，按规则4、5来降阶。
4）对于降阶过程中的任意矩阵，如果第i行的所有列均为0，则第i行必不选，将第i行删除；
证明：因为第i行无法覆盖任何列，选不选此行对覆盖作用毫无影响，因此可以直接删除此行。
5）对于降阶过程中的任意矩阵，如果第i行的所有列均为1，则第i行必选，将其余所有行删除；
证明：对于降阶过程中的任意矩阵，我们都希望找到最少的行将其完全覆盖，如果某一行能完全覆盖所有列，则只选择这一行即可。由于覆盖所有列所需的行数至少为1，所以不会找到另一种覆盖方式，比只选这一行的解更优。
6）如果确定第i行必选，则该行中值为1的列删除。
证明：缩小矩阵规模不仅要从行入手，也要从列入手。如果第i行必选，则这一行覆盖的所有列都可以被选到。再选择其余行时不必再考虑这些列，删除它们对所求结果无任何影响。
2.3 利用分支界限法得到最优解
经过第1）到第6）步，如果已经能求得结果则可以结束。如果不能，则按以下方法继续进行。将缩小规模后的矩阵按贪心法得到一个选取结果。贪心规则为每一次都选取能覆盖最多个列的行，选取一个行后将这个行覆盖的所有列删除。再次循环使用贪心规则，直到得到一个次优解。（贪心法得到的并非最优解。）
可以知道，当贪心法得到的不是最优解且行数为k时，如果有最优解，其行数[k']必然满足[0
3 举例分析
接下来，通过一个实例来演示状态矩阵压缩算法的应用。
此时可得，用贪心法需在B中选取的i=1、8两行，选取行数量为2。
步骤六：使用分支界限法，设贪心法得到的次优解行数为k=2，如果有最优解，其行数[k']必然满足[0
矩阵B是一个4×5的矩阵。对于每个结点设定的属性（p， q， r），广度优先搜索的约束条件为p≤5，限界条件为0≤q≤1和r≤4。由此建立的遍历树图2所示：
灰色结点为达到限界条件边界值的结点，无法再继续向下执行，成为死结点。限界条件中对属性q的限制可以保证得到的结果必须由于贪心法所得的结果。否则贪心法的结果即为最优解，无需再使用分支界限法。这样的设计降低了算法复杂度，缩小了分支界限法中遍历树的规模。当所有结点都成为死结点时，p的值均未能等于5，说明在这样的限界条件下该算法无解，也即没有更优于贪心法的算法。
4 仿真结果与性能分析
为了仿真模拟上述算法的性能，该文采用java语言进行算法仿真，进而用Matlab将仿真结果绘制出来。
仿真中，设定自动化药房总储药层数为15，对随机产生1000组数据做统计平均。利用初始算法与优化后的算法进行对比。其中，药品密度的定义为：对于任意一种药品，在满足至少有一个储药层包含该药品的前提下，其他储药曾包含该药品的概率（用百分比表示）。
通过仿真结果中初始算法与优化算法的对比分析可见：
1）药品种类数越大，优化算法的优势越明显；
2）药品密度越大，优化算法的优势越明显；
3）一般来说，优化后的算法比初始算法选层上少50%左右。
5 总结
对于集合覆盖问题，启发式算法的优点是能够快速得到可行解，缺点是得到的解并非最优解；如果采用精确算法，例如只使用分枝定界法、回溯法等，其优点是能得到最优解，但时间复杂度都呈指数级增长，一旦药房规模较大、出药数量较大，或药品密度大，都很容易造成工控机死机。
本文给出的状态压缩矩阵的降阶算法结合优化后的分支界限法的优点在于可缩小原问题规模，且规模可缩小的幅度较大，效果较好。这样便大大简化了程序复杂度。同时，计算机对于矩阵的处理可以直接利用数组存储，大大减小空间复杂度，同时能达到较高的软件实现效率，状态压缩矩阵也有利于编程实现。在矩阵降阶之后，先采用贪心法得到一个解，将这个解作为分支界限法的限界条件，可以充分有效地简化遍历树的规模，同时也保证了得到的解是最优的。
参考文献：
[1] 王秋芬，吕聪颖，周春光.算法分析与设计[M].北京：清华大学出版社，2011.
[2] 刘彦明，荣政.计算机软件技术基础——高级程序设计[M].北京：人民邮电出版社，2005. （下转第6401页）
（上接第6397页）
[3] Cui P，Liu HJ. Deep approximation of set cover greedy algorithm for test set[J].Journal of Software，2006，17（7）：1494-1500.
[4] 陈端兵.黄文奇.一种求解集合覆盖问题的启发式算法[J].计算机科学，2007，34（4）：133-136.
[5] 赵贤，张志强，黄民，王磊.基于最小时间算法的自动化药房系统优化设计[J].北京信息科技大学学报，2013，28（3）：39-42.
[6] 付波.自动化药房设备的动态特性分析与管理系统实现[D].北京：北京航空航天大学，2012.