研究生面试分组问题的新法解决

蒋思维 王欢

摘 要：本文利用遗传算法对给定约束条件的面试老师和参与面试学生进行合理组合分配，根据的要求建立了多目标非线性0-1整数规划模型，解决了研究生面试分组问题。根据题目给定的M、N、T的值，根据建立老师面试学生的关联矩阵，由四个要求，首先将要求数学化，得到各个要求的约束条件，然后建立了多目标非线性0-1整数规划模型，结合遗传算法的特点，解得最优分配方案。

关键词：矩阵编码;多目标规划;非线性规划;遗传算法

一、问题背景

研究生面试时衡量大学生学习情况和其他综合能力的重要手段。假设某学校某学院有M个考生经过了初试进入了面试阶段，学院准备聘请面试老师N人。面试程序为：每位研究生分别接受T位老师（为该学生的“面试组”）的单独面试。为了保持面试的公平性，每位老师要独立的根据学生问题回答情况和综合各方面进行评分，并且分组应该满足如下要求：1、每位老师面试的研究生数量应尽量均衡;2、面试不同研究生的“面试组”成员不能完全相同; 3、两个研究生的“面试组”中有三位老师相同的情形尽量得少;4、被任意两位老师面试的两个学生集合中出现相同学生的人数尽量少;

设研究生数M已知，每位研究生分别接受位老师的面试，说明聘请老师数至少分别为多大，才能做到两位研究生的“面试组”没有三位面试老师相同的情形。

二、基本假设

假设模型中面试老师人数小于学生人数，每个学生面试时间相等，老师和学生严格遵守分配方案，老师性别及其其他环境因素不影响面试结果且每个老师面试评分都公平公正，老师本身情况不影响面试情况。

三、问题

3.1问题的模型建立

3.1.1量化定性条件。C1、每位老师面试的研究生数量应尽量均衡;

根据问题一建立的关联矩阵，表示学生和老师的面试关系，为，即 =1为第i个老师面试第j个学生，=0表示第i个老师不面试第j个学生，该关联矩阵为A

要求每位老师面试的研究生书尽量均衡，即：该矩阵A各行之和的方差等于0时，每个老师面试研究生数量相等，接近于零时，数据波动不大，即为均衡。

将各行求和则各行和方差：

即时，分配均衡。

C2、面试不同研究生的“面试组”成员不能完全相同;

C3、两个研究生的“面试组”中有三位老師相同的情形尽量得少;

本文认为C2、C3条件相似，故予捆绑讨论。

当要求有三位老师相同尽量少，引入符号函数=1（x=0时），=0（x≠0时）

当有三位老师相同时，得到：

C4、被任意两位老师面试的两个学生集合中出现相同学生的人数尽量得少;

因为要使两个学生集合相同的学生数尽量少，即为关联矩阵A中，行为面试老师要面试的学生，列表示每个学生被老师面试人数，则当两行相减的绝对值取值尽量小时，相同学生数达到最小。

3.1.2目标函数的建立。根据对约束条件的定量分析，结合问题一的分析过程，建立多目标非线性0-1规划模型：

目标函数为：

3.2问题的模型的分析与求解

3.2.1遗传算法理论介绍。问题是一个多目标规划问题，一般整数规划算法解决起来比较困难，故本文选用遗传算法来求解。

遗传算法是根据达尔文的自然选择学说提出来的，通过模拟进化过程来寻找最优解。从代表问题可能存在潜在解集的一个种群开始的，而个体通过基因编码组成种群，基因存在于染色体上，染色体携带的基因为该个体的特征，决定了每个个体的特征遗传，作为遗传的载体。多个基因结合，决定外部表现。所以，基因的编码决定表现型。

、初始化、确定矩阵编码方式。该类组合问题是非线性的多峰的较为复杂的问题，常规的进制编码方式难以解决，根据问题二建立的模型，面试老师和面试学生的分组，约束条件等，用矩阵可以表示出满足合理分组及约束条件的复杂信息，所以，本文考虑使用基于矩阵的染色体编码方式。

根据题目要求的四个要求，确定的三个目标约束函数，为其适应度函数。第一个适应度函数为，为方差，是每一行老师指导学生的个数状况，为老师面试学生数目的和的方差，反应分组均衡情况，该适应度函数越小，分配越均衡。该值越小，越容易被选到。第二个适应度函数为，为三个老师相同的情况，该函数的值越小，有三位老师的情况越少，选取结果越优。该值越小，越容易被选到。

2、筛选。根据适应度函数来筛选，适应度越大，被选中的概率越大，筛选结果作为父代。可以根据适应度轮盘，即根据每个适应度函数的重要性来确定最终适应度函数的所占的概率来确定。

3、交叉变异。进行交叉变异得到相应的子代。该项操作增大种群的多样性，扩大搜索得到最优解的可能性。本文基于矩阵交叉变异，即父代互换其行或者列，可得到新的矩阵，即交叉变异的子代个体。

根据遗传算法的迭代步骤，根据流程图用编程可以得到。

四、模型的评价与推广

本文通过建立非线性0-1规划模型，采用该模型能够较好地对问题进行求解，并且能取得最优解，且结果的误差不会随数据的增加而增加。在考虑每位老师面试学生数量均衡的条件下，假定M已知，通过建立的模型，可以得到最小的N。改变M的值，得到相应的最优解N，充分利用了拟合思想，反复多次进行拟合比较，找到了较优的N与M的函数关系，并通过将得到的拟合函数与随机产生的结果进行对比，说明结果是较优的。

采用遗传算法求解没有太多的数学要求，对于任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的均可处理。进化算子的各态历经性使得遗传算法能够非常有效地进行概率意义地全局搜素，而不会陷入局部最优解的快速下降陷阱。

该模型也具有缺点，第一问的搜索算法，如果不进行优化，要进行很多次搜索，运算量过大。采用遗传算法求解时，交叉率、变异率等这些参数的选择大部分是依靠经验，使得这些参数的选择严重影响解的品质。

本文基于研究生复试时安排面试老师的要求，坚持公开、公平、公正和科学选拔的原则，切实做到以人为本，尊重考生，服务考生的原则。重视做好研究生的招生录取工作，推动研究生教育的发展。

参考文献

[1] 邢焕来，潘炜，邹喜华.一种解决组合优化问题的改进型量子遗传算法[J].电子学报，2007（10）：1999-2002.

[2] 纪树新.遗传算法解决组合优化问题的可行性研究[J].汽车科技，1999（01）：37-39.

[3] 吴值民，邹赟波，康兴挡，卢厚清.学生面试问题[J].数学的事件与识，2007（14）：138-144.

作者简介：蒋思维（1998-02-），女，汉族，四川简阳人，本科，四川轻化工大学管理学院，2017级工程管理专业，研究方向：多目标规划，遗传算法。

王欢（1999-04-），女，汉族，四川凉山，本科生，四川轻化工大学管理学院2017级工程管理专业，研究方向：多目标规划，遗传算法。