求解护士分配问题的矩阵编码进化算法

Evolutionary algorithm based on matrix coding for nurse assignment problem

护士分配问题是护理人力资源配置中的一个优化问题,也是计算机科学中的很有挑战性的NP难问题。根据中国实际医院需求日益增加的情况,研究改良了随机规划(SPA)模型,建立了优化的多场景护士分配模型。基于护士与病人的对应关系,设计了0/1矩阵作为算法编码;采用矩阵编码进化算法(EAs with Matrix Coding)框架对矩阵编码进行迭代。基于求同存异的思想,运用随机编码部分介入技术实现了矩阵型染色体的变异算子。实验结果表明,与目前的随机贪心算法、基于Bender's分解的启发式算法和随机扰动遗传算法相比,提出的矩阵编码进化算法在求解护士分配问题时能得到更高质量、更稳定的解;在多场景和多约束前提下,其平均性能优势更加明显。

Nurses assigning problem is an optimization problem in the field of nursing human resources allocation, and is also a very challenging NP-hard problem in computer science. According to actual demand from Chinese hospitals, Stochastic Programming（SPA）model is improved and a multi-scene nurse allocation model is established. To describe the corresponding relationship between nurses and patients, 0/1 matrix is designed as the arithmetic coding and evolutional iterations is carried out to the matrix encoding, using Evolutionary Algorithm（EA）framework based on the idea of seeking common ground while reserving differences, the mutation operator is achieved by adopting the random coding intervening techniques. The experimental result shows that, compared to the random greedy algorithm, the heuristic algorithm based on Bender＇s decomposition and genetic algorithm with random perturbations, this proposed evolutionary algorithm can obtain higher quality and more stable solutions for the nurses assigning problem. Moreover, in the multi-scene and multi-constrained context, the method shows more obvious average performance advantages.