遗传算法在面试问题方面的应用

1 关于面试方面的问题的应用

1.1 叙述问题

某校在今年自主招生中, 经过初选合格进入面试的考生有N人, 拟聘请老师M人。每位学生要分别接受4位老师 (简称该学生的“面试组”) 的单独面试。为了保证面试工作的公平性, 组织者提出如下要求:每位老师面试的学生数量应尽量均衡;面试不同考生的“面试组”成员不能完全相同;两个考生的“面试组”中有两位或三位老师相同的情形尽量的少;被任意两位老师面试的两个学生集合中出现相同学生的人数尽量的少。

需要解决如下问题:设考生数N已知, 在满足面试不同考生的“面试组”成员不能完全相同条件下, 说明聘请老师数M至少分别应为多大, 才能做到任意两位学生的“面试组”都没有两位以及三位面试老师相同的情形。

1.2 模型建立及求解

在满足面试不同考生的“面试组”成员不能完全相同的条件下, 要想找出考生数为N时, 至少聘请多少老师, 必须求出考生数N和要聘请老师M之间的函数关系, 所以我们首先通过数值模拟的手段, 求出N和M的函数关系, 从而求出考生数为N时, 至少要聘请的老师数。因为题目的解法主要是用数值模拟, 所以改变优化变量, 即当老师数M一定的时候, 最多可以面试学生的个数N。

建模中所用符号和表示内容如下:

1.2.1 任两位学生的“面试组”都没有两位面试老师相同的情形

由于M是未知数, 所以没有办法使用优化算法求出具体的N值, 这里我们采用数值模拟的方法, 通过列举一定的M值, 求出相应的最优的N值, 然后通过曲线拟合的方法求出M和N的近似表达式, 从而求出考生数为N时, 至少需要聘请的老师数M。

列举M值, 求相应的最优的N值的算法:

Setp1:首先求出的所有组合项, 所有项按递增方式排列成序列S0;

Setp2:从S0第一项开始, 逐次扫描后面所有项, 如果后面项同第一项有超过两个数字相同的就将其删除, 这样形成了一个新的序列S 1;

Setp3:从S1的第二项开始, 逐次扫描后面所有项, 如果后面项同第二项有超过两个数字相同的就将其删除, 这样形成了一个新的序列S 2, 然后在从S 2的第三项开始, 逐次扫描后面所有项, 如果后面项同第三项有超过两个数字相同的就将其删除, 这样形成了一个新的序列S 4, 依次类推, 直到搜索完成。

通过Matlab编程实现, 求的如下数据:

通过对以上数据的拟合得到M和N的关系式:

这种算法不能保证得到全局最优解, 但是全搜索时间复杂度又比较高, 所以对于上述的算法, 我们做了一次调整, 即在形成S2之后, 删除S 2的第三项, (因为产生两组没有两位相同得数的组至少需要7个元素, 所以调整从S2的第三项开始) , 然后重新回到S1序列, 进行删除, 即从S1的第二项开始, 逐次扫描后面所有项, 如果后面项同第二项有超过两个数字相同的就将其删除, 这样形成了一个新的序列S2, 然后从S2开始, 重新按照上面的方法进行。

依照这种调整, 我们不断替换各行, 得到多组结果, 合并取较优结果。求的如下数据:

从得到的数据上看, 在14个老师时, 居然能够面试的学生数变少了, 所以算法在这里陷入局部最优, 因此我们手动修正将14个老师时能够面试的学生数改为13个老师时能够面试的学生数, 即1 3。

通过对以上数据的拟合得到M和N的关系式:

1.2.2 任两位学生的“面试组”都没有三位面试老师相同的情形

本问的算法同上, 只是扫描的时候将同开始项有超过三个数字相同的项删除。通过Matlab编程实现, 求的如下数据:

通过对以上数据的拟合得到M和N的关系式:

同样这种算法不能保证得到全局最优解, 但是全搜索时间复杂度又比较高, 所以对上述的算法进行一些调整, 调整方法完全同上的调整算法。

不断替换各行, 得到多组结果, 合并取较优结果。

通过对以上数据的拟合得到M和N的关系式:

2 对于建模和算法应用的小结

本模型首先按顺序从第一行开始逐行向下两两比较, 在得到一组解后, 重新按顺序从第一行开始逐行向下两两比较, 但在比较过程中替换一些行, 从而得到多组解, 最后将各组解进行比较, 在老师数相同的情况下, 取学生数最多的解, 从而修正结果, 使结果更加趋近于最优解。

摘要：本文针对遗传算法在面试方面的问题, 研究了算法、数学模型的应用, 建立了相关数学的模型, 给出了相关的算法, 并利用MATLAB优化工具箱进行求解, 获得了很好的结果。

关键词：遗传算法,数学建模,Matlab

参考文献

[1] Salem Benferhat:Conference Paper Assignment.IRIT, University Paul Sabatier, 31062Toulouse Cedex, France.

[2] 李海涛, 邓樱.Matlab程序设计教程[M].北京:高等教育出版社, 2004.

[3] 张文修, 梁怡.遗传算法的数学基础[M].西安:西安交通大学出版社, 2000.

[4] 卢开澄, 卢华明.组合数学 (第3版) [M].北京:清华大学出版社, 2002.

[5] (日) 玄光男, 程润伟.遗传算法与工程设计[M].北京:科学出版社, 2000.