中国指挥与控制学会会刊 
1 基本概念
1.1 多样化任务通信编组
现代条件下的通信保障任务呈现出任务类型多样化、执行环境复杂化、参与主体多元化等趋势。不限于传统的军用或应急任务,其还包括跨领域、跨行业的通信支持需求,如应对自然灾害、社会公共事件、大型国际会议等场景,并且具有社会影响力大、行动时效性强等特点,需要科学编配通信力量以提供可靠的信息通信保障[4]。通信编组就是在构建通信网络前,运用技术手段将所属以及配属的通信人员匹配到合适的任务岗位上,以最佳的人岗匹配结果支撑信息通信保障效能的有效发挥。
1.2 加权二部图最大匹配
二部图中的顶点集合可以被划分为两个互不相交的子集,使得图中的每一条边都连接两个子集中的顶点,而同一个子集内的顶点之间则不相连。通常用数学表达式G=(U,V,E)表示,其中U={u1,u2,…,un}和V={v1,v2,…,vm}分别表示一类顶点集合,E={eij}表示两个顶点ui和vj之间的连线集合。加权二部图在二部图的基础上引入权重的概念,通过为边eij赋予权重wij,表现顶点之间的关联程度,如图1所示。
匹配表示在二部图中,一个顶点最多只与一条边相连,即任意两条边的顶点不相同。有权最大匹配则是指在一个带有权重的二部图中,找到一个匹配使得该匹配中所有边的权重之和达到最大[5]。
1.3 主动推荐技术
在本研究中,主动推荐技术主要用于为信息通信保障任务中的通信编组提供个性化的岗位匹配建议。通过分析参与者的历史表现、技能水平和任务需求,系统能够主动地推荐最合适的通信人员与特定任务岗位相匹配,从而提高通信编组的科学性和效率。
2 基于改进加权二部图最大匹配的力量编配推荐
2.1 总体构想
运用加权二部图最大匹配的方法,构建通信人员U={u1,u2,…,un}、任务岗位V={v1,v2,…,vm}两个顶点集;基于历次任务进行匹配,将通信人员在不同岗位上的历史胜任度设为wij,构成历史胜任度W={wij}连线集,形成通信人员-任务岗位加权二部图。由此,力量编配问题可以转化为加权二部图的最大匹配问题,即寻找一个匹配,使得f=∑wij最大,如图2所示。
2.2 主要步骤
1)数据采集与处理
在每次人员岗位匹配中,对任务完成情况进行评估,得到通信人员ui在最近一次担负任务岗位vj的评分,记为sij。考虑随着时间的推移,单次匹配形成的能力因遗忘效应而逐渐衰减,根据遗忘机制引入遗忘因子λij来量化最近一次匹配中能力的衰减程度[8]。遗忘因子λij表达如下:
$ \lambda_{i j}=e^{\frac{\ln 2 *\left(t-t_{i j}\right)}{h l}}$
其中:t为当前时间;tij表示最近一次通信人员ui与任务岗位vj匹配的时间;hl为用户的遗忘速率,hl越大则遗忘的速度越慢,hl越小则遗忘的速度越快[9]。由此将该通信人员在该岗位上的当前历史胜任度表示为
$ w_{i j}=\lambda_{i j} s_{i j}$
2)优化改进二部图
在加权二部图最大匹配的算法中,两边顶点的数量保持一致,实际任务中通信人员的数量往往超过任务岗位的数量,因此需要虚设n-m个任务岗位,并将虚设岗位上通信人员的历史胜任度均设为0,从而满足模型要求。考虑到某些特殊岗位对通信人员的能力素质有特殊的要求,比如无人机中继平台操作手,必须具备相应的操作能力,可以将此类能力不匹配的人员岗位历史胜任度调整为0。
3)引入岗位重要度
传统的加权二部图大多只考虑边的影响,对顶点的影响考虑较少,然而在实际任务中,由于节点重要度、业务依赖度、环境适配度等因素的差异,不同任务 同一岗位、同一任务中的不同岗位在重要度上是不一样的,而重要度高的岗位必须优先考虑匹配历史胜任度高的人员,由此增加了顶点对全局的影响。由此,可以通过层次分析法确定任务岗位重要度,将其作为顶点的固有属性引入改进加权二部图中,任务岗位vj的重要度设为pj,于是最大匹配问题的要求转化为使得匹配度函数g=∑wijpj最大,如图4所示。
4)实施匹配与推荐
表1 加权二部图最大匹配算法比较Tab.1 Comparison of weighted bipartite graph maximum matching algorithms |
| 算法 | 基本原理 | 时间复杂度 | 空间复杂度 | 适用场景 | 稳定性 |
|---|---|---|---|---|---|
| HK算法 | 通过不断寻找增广路径来逐步改进当前匹配 | O(sqrt(n)*E) | 较低,仅需存储当前匹配以及一些必要的标记位 | 适用于大规模稀疏图,特别是无权或对匹配效率要求较高的场景 | 在处理大规模数据集时表现稳定 |
| KM算法 | 通过给顶点赋值顶标,调整顶标的值以在相等子图中寻找完备匹配 | O(n3) | 相对较高,需要存储额外的顶标数组和交错树等数据结构 | 适用于顶点数量不多时,特别是权重对匹配结果有重要影响的情况 | 在处理小规模但权重复杂的问题时表现稳定 |
3 算例演示
表2 人员-岗位历史胜任度Tab.2 Historical competency of personnel-posts |
| 历史胜任度wij | ||||||
|---|---|---|---|---|---|---|
| v1 | v2 | v3 | v4 | v5(虚设) | v6(虚设) | |
| u1 | 6 | 9 | 0 | 7 | 0 | 0 |
| u2 | 6 | 0 | 6 | 5 | 0 | 0 |
| u3 | 7 | 7 | 7 | 5 | 0 | 0 |
| u4 | 6 | 6 | 8 | 6 | 0 | 0 |
| u5 | 8 | 7 | 0 | 7 | 0 | 0 |
| u6 | 6 | 6 | 0 | 7 | 0 | 0 |
表3 岗位重要度Tab.3 Post importance |
| 岗位重要度 | ||||||
|---|---|---|---|---|---|---|
| p1 | p2 | p3 | p4 | p5(虚设) | p6(虚设) | |
| 重要度 | 2 | 1 | 3 | 2 | 0 | 0 |
表4 人员-岗位匹配度Tab.4 Matching degree of personnel-posts |
| 匹配度wijpj | ||||||
|---|---|---|---|---|---|---|
| v1 | v2 | v3 | v4 | v5(虚设) | v6(虚设) | |
| u1 | 12 | 9 | 0 | 14 | 0 | 0 |
| u2 | 12 | 0 | 18 | 10 | 0 | 0 |
| u3 | 14 | 7 | 21 | 10 | 0 | 0 |
| u4 | 12 | 6 | 24 | 12 | 0 | 0 |
| u5 | 16 | 7 | 0 | 14 | 0 | 0 |
| u6 | 12 | 6 | 0 | 14 | 0 | 0 |
由此,构建了一个两边均有6个顶点的加权二部图,顶点之间连线的权重为匹配度wijpj,通过KM算法计算最大匹配,具体步骤为:
step1:初始化顶标。对每个顶点ui,设置其顶标为该顶点关联的最大边权max wij;每个顶点vj顶标设为0。
step2:寻找增广路径。逐个从顶点ui出发,尝试在当前的“相等子图”(边权等于两端点顶标之和的边构成的子图)中使用匈牙利算法寻找增广路径。如果找到增广路径,执行step3;如果没有找到,则执行step4。
step3:更新匹配。如果step2中找到增广路径,通过反转路径上的匹配状态来更新当前的匹配结果,沿增广路径的边将会从未匹配状态变为匹配状态,而路径上的匹配边则变为未匹配状态。
step4:调整顶标。如果step2中没有找到增广路径,则根据一定的规则U和V的顶标,以扩大相等子图。具体来说,会寻找一个差值d,使得将U中某些顶标的值减去d,V中某些顶标的值加上d后,至少有一条新的边可以进入相等子图。在此算例中可设定差值d=1。而后回到step2,直至更新匹配。
step5:逐个覆盖。判断是否所有顶点均完成匹配,若是则算法结束,若否则回到step2,为下一个未覆盖的顶点寻找增广路径,直到每个顶点都完成匹配。此时,得到的匹配结果即为加权二部图的最大匹配。
算法流程图如图5所示。
本研究采用python语言进行代码编写,实现KM算法的自动运行,将人员-岗位匹配度wijpj作为输入,可以立即得到匹配结果为[w51,w12,w43,w64],权重总和为63,即通信人员u5担负任务岗位v1、通信人员u1担负任务岗位v2、通信人员u4担负任务岗位v3、通信人员u6担负任务岗位v4时,全局信息通信保障效能最高,为最佳通信编组。
4 结束语
通过利用通信人员与任务岗位匹配的历史数据,引入加权二部图最大匹配思想,采用KM算法,可以有效解决通信编组随意性大、时效性弱、可靠性差等问题,能够较好适应现代多样化任务的特点规律,为提高信息通信筹划的信息化、智能化水平发挥积极作用。