面向师生感知满意度的双边匹配决策模型

2020-10-24周永务曹策俊

运筹与管理 2020年3期

刘桔，杨琴，周永务，曹策俊

(1.华南理工大学工商管理学院，广东广州 510641； 2.四川师范大学商学院，四川成都 610101； 3.重庆工商大学商务策划学院，重庆 400067)

0 引言

导师与研究生间的合理匹配关系在高校科研工作和人才培养中起着举足轻重的作用。通常情况下，导师与研究生间存在信息不对称情况，一方面，导师对研究生所属类型(如能力、态度等)未知；另一方面，研究生对导师所属类型(如能力、性格等)也未知，这导致了现实生活中出现系统整体效率(或产出)不理想的结果。对高校管理者而言，在同时兼顾导师与研究生(互为供给主体和需求主体)意愿的前提条件下，如何设计合理的师生匹配方案使得系统产出最大化，成为当前教育管理工作中的重要课题。

师生互选过程属于典型的双边匹配问题，故不可避免地需要梳理双边匹配问题的研究现状。目前，学术界关于双边匹配问题进行了大量的探索，并取得了较为丰硕的研究成果。本文在文献综述方面的主要贡献包括三个部分，即实际应用、理论研究和求解方法。在实际应用方面的贡献，Lien[1]等研究了大学录取中的一对多匹配问题，发现在未知分报考录取机制下波士顿机制具有较高的效率和公平性。Lin[2]针对企业和学校合作系统中的个人与工作匹配问题，通过构建混合整数规划模型获取了匹配结果。Gudmundsson[3]探究了室友匹配问题中稳定匹配存在的条件。Biró[4]等借助增量算法对稳定婚姻匹配问题进行了研究。梳理上述文献可知，现有文献主要聚焦于婚姻、室友、大学录取、个人与岗位匹配等问题。这些现实问题的提炼丰富了双边匹配理论的应用领域，而该理论在师生互选领域的应用研究成果非常有限(本文讨论的问题)。基于此，本文试图扩展双边匹配理论的应用领域，在充分吸收前人研究成果的基础上，将师生互选过程描述为一对多双边匹配问题，进而将其转化为一对一双边匹配问题进行求解。

在理论研究方面的贡献，Serratosa和Cortés[5]引入一种活动查询策略对交互式的图形匹配问题进行了研究。Boyle[6]等开展了对一对多双边匹配市场连续竞价机制的研究。Sethuraman[7]等以大学录取中的匹配问题为研究对象，运用几何结构设计出一种稳定匹配机制。Chen[8]等提出中值稳定匹配存在于多对多匹配市场。李铭洋[9]等针对基于序值偏好信息的一对多双边匹配问题，以每方序值之和最小为目标，构建了多目标优化模型。根据上述文献可知，已有的文献从稳定匹配、策略行为、几何多面体视角等对双边匹配问题进行了有意义的探索。然而，文献中考虑多元主体感知满意度的成果相对较少，但已有学者开始研究此类问题。例如，孔德财[10]等在双边匹配模型构建中考虑了感知满意度，稳定性和公平性三个因素。陈希和樊治平[11]提出一种最大化求职者和岗位双方匹配满意度的多目标优化模型。但这些文献中往往基于匹配主体是完全理性的假设，不能真实地反映多元主体的心理感知。前景理论作为行为运作管理领域的研究成果能够较好地刻画人行为的“敏感性递减”和“损失规避”特征，特别适用于在建模过程中体现主观情绪指标。目前，已有学者结合前景理论构建行为主体对时间、干扰等因素的感知满意度函数。王旭坪[12]等将行为科学理论融入了突发事件发生后的应急物资优化调度问题研究中,提出应急物资调度决策应注意考虑公众的心理因素。姜洋[13]等在前景理论的基础上,通过融合模糊理论,提出考虑行为主体的扰动度量方法。据此，本文基于有限理性假设，结合前景理论，提出一种考虑师生感知满意度的双边匹配决策模型。

在求解方法方面的贡献，Gale和Shapley[14]最早提出一种Gale-Shapley算法用于求解婚姻中的匹配问题。Bando[15]提出一种改进的延迟接受算法对一对多的双边匹配问题进行了研究。Kormaz[16]等采用层次分析法和改进的Gale-Shapley算法对军事人员和工作岗位进行匹配。Alpern和Katrantzi[17]基于博弈论，探讨了双边主体有共同偏好的匹配问题，并给出了匹配博弈均衡解。根据上述文献可知，已有研究主要运用匹配算法、精确算法等对此类双边匹配问题进行求解。综合考虑本文研究问题的特性及方法适用规模两个因素，本文采用启发式算法(即遗传算法)求解师生双边匹配模型。

综上所述，在充分吸收前人研究成果的基础上，本文通过梳理师生双方对匹配方案的心理感知因素，基于前景理论构建了考虑师生双方心理感知的双边匹配决策模型，从而实现系统整体感知满意度最大化的目标。具体地，①对师生双向选择过程进行描述，将其定义为一对多双边匹配问题。②参考文献[9]的求解思路，将一对多双边匹配问题转化为一对一双边匹配问题求解；③借助前景理论，选择双方主体心理最高可接受偏好序作为参考点，绘制双方感知满意度曲线，构建双方主体的感知满意度函数；④以最大化导师和研究生各自感知满意度之和为目标，构建师生双边匹配的多目标优化模型；⑤根据问题特性，设计合理的遗传算法，对问题进行求解。并通过数值算例仿真验证所提出模型及设计算法的可行性和有效性。

1 问题描述

图1 导师和研究生的一对多双边匹配示意图

2 一对多转化为一对一双边匹配问题

(1)

(2)

(3)

(4)

综上，导师与研究生一对一双边匹配示意图见图2。

图2 导师与研究生一对一双边匹配示意图

3 考虑师生心理感知的双边匹配决策模型

3.1 基于前景理论的师生感知满意度函数构建

通过上述分析可知，师生互选系统中主要包括管理者、导师、研究生三个行为主体，属于典型的基于“人”的系统。师生匹配方案对的优劣对师生心理感知产生直接影响，这种感知是人的主观感受和认知的结果。此时，系统中的“人”是非完全理性的，故已有完全理性假设条件下的研究成果难以直接用于求解本文讨论的问题。Kahneman[19]等提出的前景理论在描述人的主观行为上具有独特的优势，能够较好地刻画师生双方对匹配方案的心理感知。据此，运用前景理论的价值函数描述或刻画师生对匹配方案的感知满意度。

(1)参考点的确定

在实际匹配过程中，匹配主体对所有可行匹配对方主体排序后，存在一个心理最高可接受偏好序，最高可接受偏好序能够较好地反映该匹配主体的心理感知。具体地，若匹配主体与最高可接受偏好序对应的对方主体相匹配，匹配主体表现为既不“偏好”，也不“厌恶”；若匹配主体与最高可接受偏好序之前的对方主体相匹配，匹配主体表现为“偏好”；若匹配主体与最高可接受偏好序之后的对方主体相匹配，匹配主体表现为“厌恶”。因此，本文将匹配主体给出的最高可接受偏好序设定为参考点。

(2)导师与研究生感知满意度函数构建

对导师而言，实际匹配方案存在以下三种情况。

图3 导师对与之匹配研究生的感知满意度曲线

图4 研究生对与之匹配导师的感知满意度曲线

g∈{1,2,3,…,d},j∈{1,2,3,…,n}

(5)

同理，对研究生Sj而言，实际匹配方案也存在三种情况，这里不再赘述。研究生感知满意度函数曲线见图4。

g∈{1,2,3,…,d},j∈{1,2,3,…,n}

(6)

3.2 建立考虑师生心理感知的双边匹配决策模型

结合上述分析，在满足硬约束和软约束的条件下，构建以最大化导师和研究生感知满意度为目标函数的0-1整数规划模型。综上，面向师生感知满意度的双边匹配决策模型可描述为：

(O1)

g∈{1,2,3,…,d},j∈{1,2,3,…,n}

(C1)

g∈{1,2,3,…,d},j∈{1,2,3,…,n}

(C2)

(C3)

(C4)

(C5)

g∈{1,2,3,…,d},j∈{1,2,3,…,n}

(C6)

xgj={0,1},g∈{1,2,3,…,d},j∈{1,2,3,…,n}

(C7)

模型中，式(O1)～(O2)为目标函数，式(C1)～(C7)为约束条件。式(O1)表示最大化所有导师关于研究生的感知满意度总和，式(O2)表示最大化所有研究生关于导师的感知满意度总和。式(C1)～(C2)给出了匹配双方总体的感知满意度函数；式(C3)描述了每个研究生必须且只能与某位导师进行匹配；式(C4)描述了每位导师至少与某位研究生进行匹配；式(C5)表示转化或虚拟化后的导师其所能匹配的研究生数量不超过1个；式(C6)给出了稳定约束条件(参考文献[10])；式(C7)定义了决策变量的取值范围。

4 算法设计

一方面，考虑师生感知满意度的双边匹配问题属于一对多匹配型，且导师具有能力约束限制(即可匹配的研究生数量不同)；另一方面，资源受限广义指派问题(RGAP)关注的是m台机器/人员与n项任务的匹配问题，且机器受到某些约束条件的限制[20，21]。显然，本文关注的面向师生感知满意度的双边匹配问题属于RGAP。文献[20，21]已证明资源受限广义指派问题(RGAP)为 NP-hard，同时本文还考虑了多目标和稳定匹配等约束条件，使问题更为复杂。

针对小规模问题可采用诸如LINGO、CPLEX等和Matlab中intlinprog函数优化软件包求解此类问题；然而，针对大规模问题，其局限性凸显，可设计诸如遗传算法、粒子群算法和模拟植物生长算法等启发式算法求解此类问题[9]。借鉴并拓展文献[10，22]的求解策略，本文设计遗传算法求解考虑师生感知满意度的双边匹配决策模型。同时，为了验证算法的有效性，在算例仿真部分，对采用遗传算法与精确算法获得的结果进行的比较分析(此处不赘述)。遗传算法是借鉴自然界“优胜劣汰，适者生存”的仿生类优化算法[22]。在这样的情形下，通过实数编码方式将导师与研究生的匹配方案刻画为染色体，进而构建适应度函数，并对染色体进行选择、复制、交叉和变异等操作，以期实现师生匹配方案迭代寻优的过程。

4.1 编码

本文关注了m个导师(d个虚拟导师)与n个研究生的一对多双边匹配问题，且m≤n≤d。编码原理是将研究生Sj的编号j表示为染色体上的基因位置，其按照自然数递增顺序排列1⟹2⟹…⟹n；将与研究生Sj匹配的导师Taj的编号aj(aj∈{1,2,3,…,m})表示为染色体上的基因值。故染色体可表示为：yh=[a1,a2,a3,…,aj,…,an]，aj表示与研究生Sj相匹配的导师Taj的编号:yh∈Y(Y=[y1,y2,y3,…,yh,…,yH])，yh表示个体h，Y表示种群规模为H的群体。

4.2 初始种群产生

步骤1从n个基因座上随机选取m个基因座，并任意地填充1-m个连续且不重复的自然数，从而保证每位导师都至少能与一位研究生匹配；

步骤2根据每位导师实际可匹配的研究生数目，从可匹配两位及以上研究生的导师编号中随机选取n-m个，并填充至剩余的n-m个基因座中，进而保证每位研究生都只能与某位导师相匹配。

4.3 适应度函数构建

根据所构建模型的目标函数可知，其为多目标优化问题，目标函数值不具有非负特征，故本文采用以下步骤构建适应度函数。

①根据公式(1)，将染色体上的基因值(实际研究生导师的编号)转化为对应虚拟导师的编号；

②借鉴文献[23]的思路，运用隶属函数的加权和方法将多目标转化为单目标问题；两个目标的隶属函数可分别定义为：

③将转化后的目标函数作为遗传算法中的适应度函数，适应度函数可记为：f(yh,l)=Z3=θ1Z1+θ2Z2；f(yh,l)表示适应度函数，l为任意一次迭代，L为迭代的总次数，l∈[1,L]。

4.4 选择与复制

4.5 交叉

1)经过交叉后，aj中相同值的个数num小于或等于对应导师可实际匹配的数目，且染色体中的基因值存在缺失1-m不重复自然数中的一个或几个的情况如下。

2)经过交叉后，aj中相同值的个数num大于对应导师可实际匹配的数目，且染色体中的基因值存在缺失1-m不重复自然数中的一个或几个的情况如下。

其中，符号“⋮”表示交叉点的位置；符号“-” 表示交叉后的个体中需要修正的位；符号“=” 表示修正后值的位。

4.6 变异

下面举例说明本文采用的变异方法，沿用4.5中的例子表述如下：

1)经过变异后，aj中相同值的个数num小于或等于对应导师可实际匹配的数目，且染色体中的基因值存在缺失1-m不重复自然数中的一个或几个的情况如下。

变异前个体为：y3=[22⋮33⋮14]，变异后的新个体为：y3″=[22⋮33⋮44]，变异后经过修正的个体:y3″=[22⋮33⋮41]。

2)经过变异后，aj中相同值的个数num大于对应导师可匹配的实际数目，且染色体中的基因值存在缺失1-m不重复自然数中的一个或几个的情况如下。

其中，符号“-” 表示需要变异或修正的位；符号“=” 表示变异或修正后值的位。

4.7 步骤

结合遗传算法模型与双边匹配问题特征，其迭代步骤如下：

步骤1令l=0，随机产生H个初始个体作为初始种群；

步骤2计算初始种群中各个体的适应度函数值(fitness value)；

步骤3判断是否满足算法终止条件。若满足则输出结果；否则执行以下步骤；

步骤4根据适配值大小以轮盘赌方式执行复制操作；

步骤5按交叉变异概率rc，rm对选中个体按上述的方法执行交叉，变异操作；

步骤6若l≤L，则l=l+1，转到步骤2；若l>L，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。

5 数值算例

新生入学时，研究生根据偏好选择自己满意的导师，导师根据意愿选择满意的研究生。假设某学校某专业招收研究生8名，S={S1,S2,S3,…,S8},Sj∈S；导师有6名，T={T1,T2,T3,…,T6},Ti∈T；特别地，导师T4,T5,T6均可招生两名研究生，其他三名导师仅能招收一名研究生。研究生Sj结合自身情况，根据导师的专业方向、学术水平、对学生的培养模式等综合指标对6位导师进行综合评价，给出偏好序向量Kj=(k1j,k2j,k3j,…,k6j)，j={1,2,3,4,5,6,7,8}；研究生给出其最高可接受的偏好序集合q，具体见表1。

表1 研究生偏好序和最高可接受偏好序

导师Ti结合自身偏好，根据学生专业课成绩、外语、科研能力等指标对每位研究生进行综合评价，并给出偏好序向量Ui=(ui1,ui2,ui3,…,ui8)，i∈{1,2,3,4,5,6}；导师给出其最高可接受的偏好序集合p，具体见表2。

表2 导师偏好序和最高可接受偏好序

导师与研究生的一对多双边匹配过程可描述为：首先，根据公式(1)～(4)将此问题转化为一对一双边匹配问题，见表3和表4。

表3 转化后的研究生偏好序和最高可接受偏好序

表4 转化后的导师偏好序和最高可接受偏好序

接着，根据公式(5)～(6)得出导师对研究生的感知满意度矩阵V，以及研究生对导师的感知满意度矩阵W。

5.1 不同主体视角下的仿真结果比较分析

根据上述的初始数据，建立导师与研究生的双边匹配决策模型，结合所设计的遗传算法对其进行求解。算法均采用Matlab(R2016b)软件，在Windows 8.1系统、酷睿i5-5200双核处理器的计算机上实现所有仿真实验。遗传算法的基本参数设置如下：最大迭代次数gen为100代，种群规模N为100，交叉概率pc为0.65，变异概率pm为0.05，获得不同主体视角下的满意匹配方案，见表5。

表5 不同主体视角下的导师与研究生匹配方案

图5 遗传算法过程收敛图

在表5中，序号为order1的匹配方案表示仅考虑导师感知满意度的满意解，序号为order2的匹配方案表示仅考虑研究生感知满意度的满意解，序号为order3的匹配方案表示综合考虑师生双方感知满意度且权重相同的满意解。根据表5可知，综合考虑师生双方感知满意度的满意匹配方案为{(S1T1),(S2T3),(S3T4),(T4S4),(S5T5),(S6T2),(S7T6),(S8T5)}。在这种情形下，满意匹配方案的适应度函数值为0.8603，导师的感知满意度总和为1.112，学生的感知满意度总和为2.948。获得满意匹配方案的遗传算法过程收敛图见图5，适应度函数值收敛于0.8603。

5.2 考虑与未考虑主体感知满意度的匹配方案对比分析

上述从不同的主体视角对比分析了师生匹配方案，为说明从感知满意度视角制定匹配方案，有利于改善高校管理工作。本节从不同的性能指标对比分析了考虑和未考虑师生感知满意度的匹配方案，仿真结果见表6。

表6 考虑和未考虑感知满意度的师生匹配方案性能指标对比

根据表6可知，性能指标包括适应度函数值，导师感知满意度总和与研究生感知满意度总和。总体而言，考虑感知满意度的匹配方案在各性能指标方面均显著优于未考虑感知满意度的。特别地，适应度函数值增加了0.2302，导师感知满意度增加了2.426，以及研究生感知满意度增加了2.531。仿真结果表明：高校管理者在设计有关招生制度时，应该充分考虑师生的心理感知，以期制定出更合理、更人性化的师生互选制度，进而提高管理效率。

5.3 不同求解策略视角下的匹配方案对比分析

为验证GA在求解质量和时间方面的优越性，采用Matlab(R2016b)自带的以分支定界法为基础的整数规划求解函数intlinprog求解双边匹配决策模型，并将其获得的最优解与本文设计的GA获得的满意解进行对比分析，见表7。需要特别说明，多目标函数值是通过将目标函数O1和O2进行加权求和得到的，权重系数取0.5(与GA的适应度函数设计相同)；程序平均运行时间是十次实验的平均值。

表7 不同求解策略下的匹配方案性能指标比较

表7展示了两种求解策略下的师生匹配方案(满意解/最优解)、导师感知满意度总和、研究生感知满意度总和与程序平均运行时间结果。根据表7可知：①通过GA启发式算法获得的多目标函数满意值为2.03，采用嵌套分支定界算法的intlinprog函数获得的最优值为2.066，intlinprog函数获得的略优于GA，满意值达到了最优值的98.3%，表明GA的求解质量非常好；②但intlinprog函数平均耗时为0.68s，GA平均耗时为0.32s，结果表明GA在求解时间方面明显优于intlinprog函数。因此，GA能在较短的时间内获得高质量的师生匹配满意方案，从而验证了GA在求解本文构建的一对多双边匹配问题中的可行性和有效性。此外，为验证问题规模对仿真结果的影响，将导师数量分别取18、108和300人，对应的研究生数量为24、144与400人。采用intlinprog函数和GA两种方法对其进行求解(求解流程与小规模问题相似，为增加可读性，此处不赘述)，仿真结果见表8。

表8 不同问题规模下的仿真结果比较

在表8中，精确度表示GA获得的满意解与intlinprog函数获得最优解的比值。根据表8可知：随着问题规模的不断增大，①除18～24规模外，导师与研究生感知满意度均呈现出上升趋势，变化幅度先增大后变小；②同时考虑导师和研究生感知满意度的多目标函数值及其变化幅度，与单目标函数值的情况相似；③不同规模下的目标函数值精确度均在85%以上，最小规模下精确度达到了98.3%，表明无论大规模还是小规模问题采用GA获得的解的质量都较高；但其并未呈现出明显的稳定规律；④程序运行时间不断变大，但采用GA平均耗时明显小于intlinprog函数；且两者间的差距逐渐变大；⑥总体而言，与intlinprog函数相比较，GA在求解质量和时间两个指标上都具有较为明显的优势。