改进的多目标演化算法在护理路径问题的应用

Application of Improved Many-Objective Evolutionary Algorithm to Home Health Care Scheduling and Routing

摘要: 在传统的护理路径规划中，向病人分配护士这一阶段大多由经验丰富的护士进行手动分配，并且分配的原则是双方技能和时间匹配，但是较少关注双方满意度问题。在全面考虑了护理机构的盈利需求、护士的任务量和收入平衡问题以及病人的满意度等多角度问题后，建立了一个包含四个目标函数的数学模型，扩大了问题的规模，对传统护理规划问题更加敏感；并对传统的多目标优化算法Two_Arch2进行了改进，对收敛性档案和多样性档案分别加入了提升多样性的指标和措施。改进后的算法称为D-TA2算法，经过与其他多目标优化算法实验对比，验证了D-TA2算法的有效性。

Abstract: In the traditional nursing pathway planning, most of the nurses assigned to patients are manually assigned by experienced nurses, and the principle of assignment is to match the skills and time of nurses and patients, but less attention is paid to the satisfaction of both of them. After comprehen-sively considering the profitability needs of nursing institutions, nurses’ tasks and income balance issues, and patient satisfaction, a new mathematical model that includes four objective functions is established, which expands the scale of the problem, and is more sensitive to traditional issues. The traditional multi-objective optimization algorithm Two_Arch2 is improved, and indicators and measures to improve diversity are added to the convergence arch and diversity arch. The improved algorithm is D-TA2 algorithm, which is compared with other multi-objective optimization algo-rithms to verify the effectiveness of D-TA2 algorithm.

1. 引言

家庭保健安排和路由问题(HHCSRP)的目的是为几名护理人员建立具体的工作安排，以便为所需要的家庭提供护理服务。许多患有慢性病或者其他身体活动不自由的老人更愿意待在家里接受护理和治疗，因为这种护理和治疗往往是需要长期进行的，在家里进行护理治疗一方面尊重病人的意愿并且提供了方便，另一方面也减轻了医院很大的护理负担。随着人口老龄化的发展，在发达国家中，家庭健康护理(HHC)得到了快速的发展，在英法等发达国家中，越来越多的护理机构都有提供此类服务，智能手机数据的发展也为家庭医疗提供了极大的便利 [1] 。HHC的任务主要是集合机构内的护理人员，接收病人的需求，根据相应的需求分配符合要求的护理人员或者护理人员分队，并且规划护理人员的护理顺序以及出行。国内外有关HHCSRP的研究开始的较晚，并且多为小样本数据，近年来获得了较多关注。如何根据一定的要求合理安排医护人员照顾患者是HHCSRP的重点。

一些研究关注了HHCSRP中的调度和路由，如 [2] 。Nikzad等人 [2] 提出了一个考虑护士分配和路线规划的两阶段随机混合整数模型。通过考虑护士与患者需求之间的技能匹配和护理连续性等约束条件，首先对患者和护士进行划分，然后进入第二阶段，即分配人员和具体路径。为了提高模型的收敛速度，提出了PH-FW模型，该模型在大规模测试案例中取得了良好的效果。徐等人 [3] 对大数据时代中国智能家居护理模式存在的问题进行了详细研究，并从多个角度给出了相应建议。如何提高路由规划类问题的效率和准确性是关键 [4] 。

一些研究考虑了HHCSRP问题的不确定性。 [5] 考虑了护理过程中的一些不确定因素，从鲁棒优化(RO)的角度，建立了考虑不确定行程和服务时间的HHC路由与调度问题模型。 [6] 做出的行程规划考虑了护理时间与旅行时间的不确定性，以最小化护理人员的出行成本、因患者服务延误和护理人员超时工作所带来的期望追索权。但该模型并没有考虑病人需求的多样性，因此还有很多的探索空间。 [7] 与 [6] 考虑的问题相同，都是护理人员的出行时间和病人服务时间的随机性，但 [7] 由于引入了保证客户的准时服务概率的机会约束，所以变得更加复杂，并且通过分支价格(B&P)算法和离散逼近方法相结合，设计具有尖端加速策略的标签算法和层次分支方案解决了这一问题。在 [8] 中，核心问题是病人需要多种护理，这些护理可能需要多个护理人员来完成，因此如何安排相对应的护理人员以及对应的护理顺序成了本文关注的问题。

一些研究关注的是HHCSRP不同规划周期。Nickel等人 [9] 考虑的是中短期(一般是一周甚至更短的周期)的HHC的不同方面，采用改进的(元)启发式算法计算可行解，通过真实世界数据的验证，该方法在HHC的医疗、经济等方面具有一定的优势。在 [10] 中，作者将HHCSRP视作动态路径规划问题，该方案旨在设计路线，确保病人每次需要护理时都由同一护理人员完成，因此不涉及资源分配的问题，只考虑如何规划合理的路径。动态预测患者的护理请求，降低了规划成本，并且在患者请求未知的情况下，该方法要优于每周规划的效果。

一些研究考虑具有很多约束的问题，并将约束条件转化为数学公式加以限制。 [11] 中关注的内容是护士名册问题，重点在于如何合理的分配护理人员以满足护理连续性，即为每个病人分配尽可能少的护士，指派护士每周重复的探访病人。在真实数据的实验验证中表明与传统的手工分配护士名册相比，该方法的护理连续性得到了大大的提高。 [12] 考虑了较多现实生活中的约束，优化的目的是为了提高护理人员和病人的满意度。为周期内的每一天生成一个MILP，每次迭代中添加新的约束，并检查原有约束有没有被违反，最后通过综合每一天的迭代结果生成周期性的护理计划，该方法在护理人员规模较大时可以快速得到一个可行方案。 [13] 考虑的约束条件是加班费用、护理连续性以及偏好问题，其中护理人员的加班费用在HHCSRP问题中较少提到。

一些研究关注多个目标优化的问题， [14] 提出了一种双目标模型，既考虑了护士降级护理的成本问题，也就是护士潜在的技能与实际病人所需要的技能之间的差异带来的成本问题，又考虑了护士的最小化出行时间。基于此双目标模型，提出了一种基于ε约束的求解方法，并对ε参数进行了灵敏度分析。在 [15] 中，作者提出的模型中有护理机构的成本与客户偏好两个相互冲突的目标，同时考虑了硬时间窗、护理人员的等级、加班费、出行的交通费等约束，通过在多向局部搜索框架中嵌入大型邻域搜索启发式算法，解决了实际问题的测试算例。

一些研究关注的重点是护理人员和患者的满意度。 [16] 关注的是所有利益相关者的满意度，并将其作为主要的研究目标，在此基础上，根据患者的需求和护理人员的偏好进行护理工作的分配，以此来平衡护理人员的工作量。建立了一个基于元启发式数学公式的系统来处理该问题，并利用模拟退火算法验证了计算得到的任务表和整体满意度的可行性。

在本文中，我们建立了一个包括最小化护理机构成本、护士收入和工作量平衡以及最大化患者满意度的四目标数学模型。并改进了传统的演化算法，成功地将其用于求解这个数学模型。

本文的主要贡献如下：

重点研究了护士的分配问题，提出了一种新的护士分配模式。在研究护士的分配问题的时候考虑了多方面的利益和满意度平衡问题，建立了一个四目标的数学模型，使得护理机构成本最低、护士工作量和工资水平达到平衡以及病人满意度达到最大。

提出了基于Two_arch2算法的改进算法D-TA2，对Two_arch2算法的改进体现在两个方面：CA集合的选择增加了基于偏移的密度估计指标，并且用随机排序法(SRA)对两指标进行了平衡，提高了种群的收敛性；在DA集合的选择中加入了一种重复分析方法来过滤冗余解，通过去除集合中的重复解，提高了解集合的搜索效率，促进了种群多样性的发展。经过与其他算法对比HV和极坐标等指标，展示了D-TA2算法的有效性。

2. 相关工作

2.1. 超多目标优化问题

拥有两个或者三个优化目标问题的称为多目标优化问题，当优化目标的个数增加到四个及以上时就变成了超多目标优化问题，超多目标优化问题可能是最大化目标函数，可能是最小化目标函数，也可能是最小化部分目标函数并且最大化部分目标函数，为了方便处理，一般可以将各个目标的优化统一为最大化目标函数或者最小化目标函数。如以最小化目标函数为例，问题的一般描述如下所示：

$\min F\left(x\right)={\left(f_1\left(x\right),f_2\left(x\right),\cdots ,f_r\left(x\right)\right)}^{\text{T}}$ (1)

约束条件为：

$g_i\left(x\right)\ge 0,\left(i=1,2,\cdots ,k\right)$ (2)

$h_i\left(x\right)=0,\left(i=1,2,\cdots ,l\right)$ (3)

其中， $x={\left(x_1,x_2,\cdots ,x_n\right)}^{\text{T}}$ 为决策变量，n是决策变量的个数。 $g_i\left(x\right)$ 代表了k个不等式约束， $h_i\left(x\right)$ 代表了l个等式约束。 $f_i\left(x\right)$ 代表了r个相互矛盾的目标函数， $F\left(x\right)$ 代表了决策变量满足约束条件 $g_i\left(x\right)$ 和 $h_i\left(x\right)$ 的可行域，超多目标优化的目的就是找出可行域 $F\left(x\right)$ 中能够解决问题的最优解。

2.2. 超多目标优化算法

MOEAs的原理流程为：首先随机生成一组初始种群，而后对种群中的个体执行交叉、变异、选择等操作形成新种群，通过多次迭代计算，种群中个体适应度随之提高，达到迭代次数后，最终种群近似于多目标优化问题的Pareto最优解集。大部分的MOEAs采用基于Pareto排序的适应度评价方法，以发挥算法的群体搜索优势。为了得到质量更好的Pareto最优解，还可以在计算过程中采用精英策略、小生境和设置外部集等方法。多目标优化算法得到的最优解需要满足三个特性，分别是：尽可能接近PF (收敛性)、分布均匀(多样性)、得到的解尽可能覆盖整个PF (覆盖性)。

MOEAs的求解过程首先从初始化种群开始，但初始种群的规模大小一般是有对应要求的，且一般都采用随机初始化的方法，因此不需要在初始化中做改动。得到初始种群后，需要对种群进行模拟二进制的交叉变异处理，交叉处理是选定种群中的两两交叉的个体，将个体中的信息按照某种方式进行交换，从而形成两个新个体。交叉处理后形成的新个体将以一定概率发生基因变异，交叉变异完成后形成的新种群通过环境选择策略进行优胜劣汰，环境选择策略是其中最重要的一环，应用一种或多种适当的选择机制在MOEAs中占据着十分重要的位置。

3. 数学模型

一般来说，在家庭保健和路由安排的研究中，研究者关注的更多的是护理机构如何在降低成本的同时为病人提供更好的服务，有些研究从工资或者休息时间的角度上关注护士的满意度，这些研究要么将护士满意度与病人满意度以罚函数的形式并入目标函数中，要么则将其作为约束加入到约束公式中。绝大部分的研究将护士拜访病人期间所产生的问题与成本作为了研究重点，从而忽略了为护士分配病人这个阶段，而这个阶段更能体现护理机构对病人与护士双方的关注与重视，当护理需求与任务使双方满意后，护理顺序反而并不重要。本文的重点是如何在考虑护理机构、护士和病人各自需求的基础上解决护理患者分配问题，同时将护理机构、护士和患者的满意度和成本作为目标函数。下面将详细介绍分配问题的数学模型。

3.1. 问题假设

假设所有护士都从同一个护理机构离开，最终回到这里。所有患者的等级和所需的护理时间都是事先知道的，不存在随机性。计划周期为一天。所有低级别的患者都可以由同级别和高级别的护士护理，但低级别的护士不允许护理高级别的患者，护士级别高于患者级别会增加患者满意度。护士照顾所有患者的总时间不得超过其最大工作时间。

3.2. 目标函数

本文的目标函数分别从HHC护理机构、不同等级的护士以及病人的角度出发，同时考虑了三方面的利益需求，构造了四个目标函数，以最小化护理机构的成本、最小化不同等级护士的收入差异、最小化同等级护士之间的工作量差异和最大化病人的满意度为优化目标分别构建对应的目标函数，即建立了护士分配的四目标优化模型。其中，不同等级的护士集和病人集分别为 $N_i$ 与 $P_i$ ，护士i对病人j的护理时间为 $t_{ij}$ ，不同等级护士的收入标准和数量分别为 $a_i$ 和 $n_i$ ，g代表不同的等级集合，护士i照顾的病人集合为 $b_{ip}$ 。四个目标函数分别为：

1) 最小化护理机构的成本

HHC护理机构是盈利机构，因此在进行人员分配时首先考虑的一定是成本问题，在人员分配时，用简单直接的指标计算出总成本；等级的护士所需要的成本是 $Cos{t}_k$ ，

$Cos{t}_k={\displaystyle \underset{i\in N_k}{\sum }{\displaystyle \underset{j\in b_{ip}}{\sum }{t}_{ij}\times a_k}}$ (4)

其中， $N_k$ 表示k等级的护士集合。

总成本 $Total\text{\_}Cost$ 为所有等级的护士所需成本之和，表示如下：

$Total\text{\_}Cost={\displaystyle \underset{k\in g}{\sum }Cos{t}_k}$ (5)

2) 最小化不同等级护士的收入差异

不同等级病人所需的护理人员等级也不同，高等级的护士可以护理和自己同等级或者低于自己等级的病人，但较低等级的护士不可以护理需求等级比自己高的病人；高等级护士的工资等级相对低等级护士更高一些，因此很容易出现不同等级的护士之间的收入差距过大的状况，为避免不同等级护士之间的矛盾，本目标函数致力于最小化不同等级护士的收入差距；所有护士的平均收入为 $Ave\text{\_}Cost$ ，

$Ave\text{\_}Cost=\frac{Total\text{\_}Cost}{{\displaystyle \underset{i\in g}{\sum }{n}_i}}$ (6)

其中， $n_i$ 表示i等级护士的数量。

所有护士的收入差异为 $Dif\text{\_}Cost$ ，

$Dif\text{\_}Cost=\frac{{\displaystyle \underset{k\in g}{\sum }{\displaystyle \underset{i\in N_k}{\sum }{\displaystyle \underset{j\in b_{ip}}{\sum }{\left(t_{ij}\times a_i-Ave\text{\_}Cost\right)}^2}}}}{{\displaystyle \underset{i\in g}{\sum }{n}_i}}$ (7)

3) 最小化同等级护士的工作量差异

同等级的护士护理的病人等级是相同的，并且工资等级也是相同的，在考虑护士满意度的情况下，希望同一等级的护士的工作量也是相差不大的；保证同等级的护士的收入相近，并且不会出现有些护士很忙，而有些护士很清闲的情况，对于同等级的护士而言是相对公平的；k等级的护士的总工作量为 $Sum\text{\_}Loa{d}_k$ ，

$Sum\text{\_}Loa{d}_k={\displaystyle \underset{i\in N_k}{\sum }{\displaystyle \underset{j\in b_{ip}}{\sum }{t}_{ij}}}$ (8)

k等级的护士的平均工作量为 $Ave\text{\_}Loa{d}_k$ ，

$Ave\text{\_}Loa{d}_k=\frac{Sum\text{\_}Loa{d}_k}{n_k}$ (9)

k等级的每个护士i的工作量差异为 $Dif\text{\_}Loa{d}_i$ ，

$Dif\text{\_}Loa{d}_i=\frac{\left|{\displaystyle \underset{j\in b_{ip}}{\sum }{t}_{ij}-Ave\text{\_}Loa{d}_k}\right|}{Ave\text{\_}Loa{d}_k}$ (10)

4) 最大化病人的满意度

病人的满意度是HHC护理机构与病人双方都需要考虑的问题，只有提高病人的满意度才会给HHC护理机构带来更大的收益，病人也会享有更高的服务质量；高等级护士护理低等级需求的病人会提高病人的满意度，但是如果一昧的让高等级护士护理需求等级较低的病人的话，又会造成护士之间收入差异、工作量差异过大的状况，因此本目标函数与前三个目标函数是相矛盾的，多目标优化的意义就在于如何兼顾多个相互矛盾的目标从而达到均衡状态；将病人的满意度定义为Fit，为了便于计算，使四个目标函数值均保持最小化，因此特意取满意度的倒数作为最终的函数值，具体定义如下：

$Fit=\frac{1}{{\displaystyle \underset{k\in g}{\sum }{\displaystyle \underset{i\in N_k}{\sum }{\displaystyle \underset{j\in b_{ip}}{\sum }\left|g_j-g_i\right|}}}}$ (11)

4. 算法设计

Two_arch2 [17] 算法在原始的Two_arch [18] 算法的两个存档的基础上，将CA和DA的更新策略进行了有效的分离，在CA中引入了IBEA [19] 算法中的 $I_{\epsilon +}$ 指标以促进CA的收敛性，而DA则利用Pareto优势促进多样性。并且在繁殖过程中，对CA和DA进行交叉，但只对CA进行变异，利用CA将种群快速收敛到Pareto平面上，利用DA增加种群的多样性，并且最终摒弃了多样性较差的CA，输出DA。在本文中，引入了SRA [20] 算法对CA的更新策略进行了改进，在原本利用 $I_{\epsilon +}$ (I₁)指标进行更新的基础上增加了 [21] 中提出的基于位移的密度估计指标(I₂)，在CA促进收敛性的基础上增加了促进多样性的指标，使得CA兼备收敛性和多样性，更好地应用于Maop中。并且为了平衡两个指标对种群中个体更新的影响，引入了随机排序技术(SRA)来解决MaOEAs中的指标排序问题。在DA的更新中，使用帕累托优势来促进多样性在高维空间中可能会失败，并且随着决策变量的数量增加，群体中个体具有重复的可能性越高，基于此问题，添加了重复分析方法来过滤冗余解，并通过删除重复解来促进群体多样性 [22] 。首先，根据给定的种群规模随机初始化种群，然后计算每个种群的目标函数值。接下来，使用交叉和突变产生后代，根据不同的策略更新CA和DA。最后输出DA集合。整个过程是：首先初始化群体，变异CA集，交叉CA和DA，然后分别更新CA集和DA集，重复上述过程，直到满足停止标准，最后输出最终种群。

4.1. 初始化种群

根据种群规模对种群中需要的病人和护士进行初始化，并按照要求将护士分配给病人，所以一个病人就是一个决策变量，病人的全体集合就是种群，同时检查护士的分配是否是按照等级进行匹配的，不匹配的进行重新分配。

4.2. 计算目标函数

计算个体的目标函数值用于评价个体的质量，根据每个个体的不同分配方案与护士等级、病人数量等，计算对应个体的目标函数值，在更新阶段根据目标函数值的大小进行个体的选择。

4.3. 选择与繁殖

因为CA和DA分别针对种群的收敛性和多样性，因此在繁殖过程中，只对CA进行变异，对CA和DA进行交叉，并且交叉和变异两个过程独立进行，变异的概率设为 $p_m$ ，交叉的概率设为 $p_c$ 。

4.4. 更新CA和DA

1) 基于双指标的随机冒泡排序更新CA

在原有 $I_{\epsilon +}$ 指标更新CA的基础上引入了促进多样性的指标 $I_D$ ，过早收敛致使算法多样性较差，而引入促进多样性的指标后，运用了随机排序对双指标进行了动态平衡；双指标在排序时所占比重根据具体的问题进行调整，而后根据双指标对整个种群进行排序，选择前N个最优个体完成更新；在促进收敛性的同时维持了CA的多样性，有效提高了CA中的个体性能，具体过程如下：

在完成交叉变异的繁殖阶段过后，CA的父代种群大小为N，子代种群大小为2N，而在进行CA的更新过程时，需要将子代种群和父代种群进行拼接，形成2N大小的种群，再从中选出前N个个体组成种群作为输出结果；此时需要从子代种群中挑选出大小为N的性能较好的个体去与父代种群进行拼接，因此在进行拼接之前，需要先计算CA的子代种群中的个体适应度的值，并从中挑选前N个适应度值较小的值作为子代种群与父代种群进行了拼接，形成了大小为2N的种群POP，进入更新阶段；

首先提取出POP种群的目标函数值得到obj，计算种群的适应度值以得到第一个指标的值I₁， $I_{\epsilon +}$ 描述了一个解支配另一个解的最小距离， $F\left(x\right)$ 是计算适应度值的公式，I₁是 $F\left(x\right)$ 包含所有个体和所有目标函数的函数的集合，具体计算公式如下：

$I_{\epsilon +}\left(x_1,x_2\right)=\min \left\{f_i\left(x_1\right)-\epsilon \le f_i\left(x_2\right)\right\}i\in \left(1,2,\cdots ,m\right)$ (12)

$F\left(x_1\right)={\displaystyle \underset{x_2\in POP\backslash \left\{x_1\right\}}{\sum }-{\text{e}}^{I_{\epsilon +}\left(x_2,x_1\right)/0.05}}$ (13)

$I_1=\left\{F_i\left(x_1\right),F_i\left(x_2\right),\cdots ,F_i\left(x_N\right)\right\}i\in \left(1,2,\cdots ,m\right)$ (14)

其中， $x_1$ 和 $x_2$ 分别代表种群POP中的两个不同个体 $f\left(x\right)$ 表示目标函数的计算，m表示目标函数的个数。

然后选择在同一个目标中在obj中的索引值位于一前一后的两个个体y和x，计算基于平移密度估计的 $I_D$ 指标，取距离矩阵的每一行的最小值形成列向量得到第二个指标值I₂， $I_D$ 指标不仅可以衡量种群的收敛性，还能度量种群的多样性，其计算公式如下：

$I_D\left(x_1,x_2\right)=\sqrt{{\displaystyle \underset{1\le i\le m}{\sum }sd{\left(f_i\left(x\right),f_i\left(y\right)\right)}^2}}$ (15)

$I_2\left(x\right)=\min \left(I_D\left(x,y\right)\right),y\in obj$ (16)

其中， $f_i\left(x\right)$ 与 $f_i\left(y\right)$ 分别代表个体x与个体y在第i个目标函数 $f\left(x\right)$ 中的计算结果。

最后，两个指标计算完成后，进入随机排序阶段，采用的方法是随机排序算法，首先选定指标值 $p_c$ ，即两个指标之间的权重，然后对整个POP种群进行排序：生成 $\left(0,1\right)$ 之间的随机数p，如果 $p_c<p$ ，则比较种群中个体的I₁指标，将指标值较小的个体前置，反之则比较种群中个体的I₂指标，将指标值较小的个体前置，即最终选择排名前N的个体完成更新。

2) 基于冗余分析更新DA

使用帕累托优势来促进多样性在高维空间中可能会失败，并且随着决策变量的数量增加，群体中个体具有重复的可能性越高，基于此问题，添加了重复分析方法来过滤冗余解，并通过删除重复解来促进群体多样性。

重复分析的主要思想是使用决策空间中的解之间的曼哈顿距离来评价解的不相似度，以便决定应该删除目标空间中的哪些重复解；解的不相似度是通过其与决策空间中所有其他解的最小曼哈顿距离来计算的，其值应在0和1之间；两个决策向量之间的曼哈顿距离实际上揭示了它们之间的差异度；首先根据目标函数个数和决策变量数设定移除阈值 $\delta$ ，通过计算解与决策空间中其他解的最小曼哈顿距离确定解的不相似度；然后将这些重复解根据其不相似度分为两组，一组是不相似度高于或等于移除阈值 $\delta$ 的远程解决方案，另一组是不相似度低于移除阈值 $\delta$ 的集群解决方案；所有的远程解决方案被保留，而只有一个集群解决方案被保留，需要从所有的集群解决方案中随机选择一个解，移除其余所有解；因此，移除阈值 $\delta$ 越大，重复解越可能被移除。

5. 计算复杂度分析

以一个包含N个个体的种群，m个目标函数的Maop为例计算复杂度。首先，由初始化的父代繁殖产生子代的复杂度为 $O\left(N\right)$ ，将父代和子代合并进行非支配排序的计算复杂度为 $O\left(N{\log }^{m-2}N\right)$ 。其次，在DA更新过程中，基于帕累托优势进行种群去重和多样性选择的更新策略的计算复杂度为 $\max \left\{O\left(m{N}^2\right),O\left(N{\log }^{m-2}N\right)\right\}$ 。在CA的更新过程中， $I_{\epsilon +}$ 指标计算所需的复杂度为 $O\left(m{N}^2\right)$ ， $I_D$ 指标计算所需的复杂度也为 $O\left(m{N}^2\right)$ ，并且基于SRA对两个指标进行平衡的计算复杂度为 $O\left(N^2\right)$ ，计算新的评价指标的计算复杂度为 $O\left(N\right)$ 。因此，总的计算复杂度为 $\max \left\{O\left(m{N}^2\right),O\left(N{\log }^{m-2}N\right)\right\}$ ，与Two_arch2算法的计算复杂度的等级相同。

6. 实验结果和分析

6.1. 实验设置

每个病人需求的护理等级和时间以及护士的护理等级在初始化时随机产生，我们将改进后的算法与Two_Arch2、MOEA/D [23] 、PREA [24] 、PeEA [25] 、DWU [26] 进行了比较，统一设置迭代次数为200次，交叉和变异概率分别为1和0.05，每个算法独立运行20次以求得目标函数的平均值，其他的参数在表1中展示。

Table 1. Parameter settings

表1. 参数设置

6.2. 对比实验和分析

超体积(HV)是广泛用于MOEA的性能评估 [27] 。HV值通过计算非支配解中每个个体与指定参考点之间的m维体积之和来获得。它可以同时评估种群的多样性和收敛性，并且算法计算得到的种群HV值越大，算法的性能越好。将改进算法应用于具有不同数量决策变量的模型进行求解，获得的具体数据结果来自表2。加粗部分为每组数据的最优值，由表中的数据可知，在不同数量的决策变量下，D-TA2算法得到的解集的HV值最大，即算法的性能最优，总体效果更好。

为了更直观和清晰地显示不同算法的比较结果，我们采用了一种可视化方法，将最终迭代种群中的个体映射到二维极坐标图中，为了更好地呈现图像，将决策变量的数量设置为200。所获得的极坐标图

Table 2. HV of D-TA2 with other comparison algorithms

表2. D-TA2与对比算法的HV值

(c) (c) (c) (d) (e) (f)

Figure 1. Comparison of polar coordinate map between AC-TA2 and other algorithms; (a) polar coordinate map of D-TA2; (b) polar coordinate map of NSGA-III; (c) polar coordinate map of Two_Arch2; (d) polar coordinate map of CA-MOEA; (e) polar coordinate map of PeEA; (f) polar coordinate map of PREA

图1. D-TA2与其他算法的极坐标图对比；(a) D-TA2的极坐标图；(b) DWU的极坐标图；(c) Two_Arch2的极坐标图；(d) MOEA\D的极坐标图；(e) PeEA的极坐标图；(f) PREA的极坐标图

越圆，代表种群的性能越好，也就是说，算法具有更好的性能 [28] 。

从图1中可以看出，D-TA2算法得到的解集在极坐标系中映射得到的图形分布均匀，较其他对比算法具有更好的收敛性和多样性。

7. 总结

为了解决护理路径规划中如何给病人分配护士的问题，我们提出了一种新的分配方法。在考虑护理机构的盈利、护士的收入和工作量平衡以及病人满意度等多方面问题的基础上，我们提出了一个四目标模型。为了解决Maop，在Two_Arch2的CA集合的更新中增加了基于偏移的密度估计指标来平衡CA的多样性和收敛性，在DA集合的更新中增加了重复分析方法进行去重处理，并综合考虑多样性评分和拥挤度距离进行了集合的多样性选择，并通过实验验证了算法的有效性。