解决面试工作安排中专家资源合理分配问题

陈 香

（湖南外贸职业学院，湖南 长沙410000）

面试是一种经过组织者精心设计，在特定场景下，以考官对考生的面对面交谈与观察为主要手段，由表及里测评考生的知识、能力、经验等有关素质的一种考试活动。面试是公司挑选职工的一种重要方法。面试给公司和应招者提供了进行双向交流的机会，能使公司和应招者之间相互了解，从而双方都可更准确做出聘用与否、受聘与否的决定。

遗传算法GA(genetic algorithm)作为一种解决复杂问题的有效方法，是由美国密执安大学的John Holland教授于1975年首先提出来的，这种算法是以达尔文的生物进化论为启发而创建的，是基于生物进化中自然选择、适者生存和物种遗传思想的搜索算法。特别适合求解非线性整数规划问题。也适用于本文所建立的面试工作安排问题求解。

为了有效求解如何进行面试专家组成员工作安排使面试公正客观的问题，本文对问题进行探讨，建立其数学模型，为复杂的非线性整数规划问题。提出一种装箱编码、多点交叉、领域搜索变异的遗传算法对数学模型进行求解，并用一个30名专家对300名人才进行面试，每个面试组4名专家的例子用遗传算法进行求解计算，表明，改进后的遗传算法能高效求解出问题的近似最优解，求解结果能满足面试工作安排所提出的要求。

1 装箱编码

在遗传算法中，待解问题的一个解从表现型到基因型的映射称为编码，实质是解的一种向量表示方法，最初遗传算法是采用二进制编码方法，该方法操作简便，但不能反映问题的特定知识。针对实际问题可以采用特定编码，以利于问题求解。对于此模型，对编码可以这样设计：把一个学生的面试组专家成员当成一个整体，如同放在一个箱子中一样，作为染色体表示中的一个基因位，则该基因位中有L个元素，值为1—M的不相同的整数，显然第k个基因位确定了第k名学生被面试的L名专家。

2 改进遗传算法求解

遗传算法中一般采用轮盘赌选择方式来选择算子，即根据每个染色体适应值比例来确定该个体的选择概率或生存概率。本文采用父子竞争中加入模拟退火选择操作来进行选择，从父代种群和新生成的种群中选择一部分个体作为下一代种群。即以一个概率值来设置一新个体替换一父个体。设父个体为X，新个体为X’，T为当前温度。则替换概率为

在遗传迭代开始设置一个较大的初温T(t0)，随着迭代次数的增加温度逐渐降低，降温方式有很多种，这里用公式(8)方式进行降温。

其中：k为一个略小于1的正数。在迭代中温度逐渐降低，则当新个体比父个体差时，替换概率逐渐降低，在迭代后期，由于温度很低，选择优秀个体的概率接近于1。设最大迭代次数为N，若温度降低过快，则搜索容易过早陷入局部极值点，有必要设置一个最终的最低温度为Tl，来计算k值，为

并在选择过程中引入最优保持操作，保存历代产生的最优个体，替换新一代群体中的最差个体，这样既可以采用父子竞争来提高收敛速度，又能收敛于全局最优解。

3 交叉算子

遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。在本文的遗传算法中，种群中每个个体的每一个基因位，为一名应聘应考者被面试的老师的分配方案，选中的父代种群中的两个体X、Y进行单点交叉或多点交叉，交换相同基因位对应的所有数据，相当于在两种不同的方案中交换相同学生被面试的老师分配方案，得到两种新的分配方案，对于本模型，由于所计算的数据量较大，故采用多点交叉。这里只给出单点交叉的示意图，设新个体为X’、Y’。

4 算例和计算结果分析

（1）算例。设有30名专家要对300个学生进行面试，每名学生对应一个面试组，每个面试组有四名专家，如何合理安排面试组成员，使达到如下要求：每名专家面试学生数量均衡，任意两面试组不相同，且任意两面试组成员要尽量不同。

（2）遗传算法参数设置。采用遗传算法对问题进行求解，参数设置如下：①群体大小N＝50。②取交叉概率Pc＝0.8，变异概率Pm＝0.1；③终止进化代数E＝3000代。

（3）求解结果分析。由于本文篇幅有限，求解结果专家面试学生对应关系这里不给出，只对求解结果进行讨论。目标值随遗传代数的增加而减少，到遗传后期，目标值基本趋于稳定，即表示已找到近似最优解。对找到的近似最优解进行分析，计算得到表2数据，可以看出，没有两面试组成员完全相同，而且，出现三位以上专家相同的情形也较少。说明求解结果达到数学模型的要求。

5 结语

本文针对如何进行面试专家组成员工作安排使面试公正客观的问题进行探讨，根据面试工作公正客观性要求建立其数学模型，表明，该模型为复杂的非线性整数规划问题，难以找到常规算法对问题进行求解。提出一种装箱编码、模拟退火遗传、多点交叉、领域搜索变异的遗传算法对数学模型进行求解，并用一个30名专家对300名学生进行面试，每个面试组4名专家的例子用遗传算法进行求解计算，表明，改进遗传算法能高效快速求解出问题的近似最优解，求解结果能满足面试工作安排公正性客观性的要求。遗传算法的引进为求解这类问题提供一个好的解决方法和手段。

[1]刘智明,周激流.敖啬.遗传算法交叉算子分析[J].四川大学学报，2002，39(5)：857－860.

[2]G Wirght A.Genetic alogirthm for real parameter opitmization[A].The First Workshop on the Foundations of Geneitc Alogirthms and Classiifer Systems[C].Morgan Kaufmann,Sani Dego:WFGACS，1990_205—218.

[3]谭冠政,刘良敏.基于复数编码遗传算法的竞争性协进化策略[J].中南大学学报(自然科学版),2005,36(3):475-480.

[4]Srinivas M,Patnaik L M.Adaptive Probabilities of Crossover and Mutaiton in Genetic Algorithms[J].IEEE Transactions on systems,man and cybernetics,1994.