基于SA－KM 算法的毕业设计选题分配

2014-12-06罗乐霞

长春工程学院学报（自然科学版） 2014年4期

罗乐霞

（福建船政交通职业学院信息工程系，福州350007）

0 前言

传统的毕业设计选题分配是将试题随机分配给学生，或者是让学生在众多选题中选择自己心仪的题目，这往往导致学生分配的题目不理想，难以发挥出其真正的实力，同时选题与学生一对一的关系，一个选题被一个学生选择后其他学生不能再次选择，这就导致其他学生选择题目的范围越来越窄，有悖于公平、公正评估学生学习效果的意愿。因此，本文对毕业设计选题分配算法进行研究与设计，提出根据教师评定的课题难易程度与课题类型的权重分配及学生成绩与学生自我评价值的权重分配［1］，采用优化后的高维数据［2］的SA－KM聚类算法［3］，根据教师评估和学生意愿进行分配，大大提高了学生毕业设计的水平。

1 设计构思

本文所设计的毕业设计选题分配系统算法采用二分图数学理论，将教师赋予学生期望值课题与学生志愿选择课题分别设为X、Y2个集合，如图1所示。

将教师赋予学生期望值课题与学生志愿选择课题数学转化为一个带权的二分图，其中X值为教师赋予学生期望值，Y值为学生志愿选择值，采用最优匹配算法对权值进行优化，获得最大权值，即为毕业设计选题分配最优结果。

图1 教师赋予学生期望值课题X与学生志愿选择Y二分图

该算法描述了以权重分配为基础的二分搜索条件查找，为实现教师为学生所设置的课题与学生擅长或者是与学生兴趣相匹配，符合学生真实能力评测要求的毕业设计选题分配算法，建立教师出题与学生选题之间的逻辑关系，如图2所示。

图2 教师出题与学生选题的逻辑关系

算法数据库主要包含2大类数据项：一是以学生为主体的学生信息表，二是以选题为主体的课题信息表。学生信息表主要包括：兴趣爱好、技巧能力、考试成绩评估、自我评价；课题信息表主要包括：课题介绍、课题要求、课题类型、课题难度。

2 KM选题分配算法

采用KM算法［4］进行选题分配计算，该算法为求完备匹配下的最大权匹配问题［5］。

对于具有二部划分（X1，Y2）的加权完全二分图，其中 X1＝｛x1，x2，x3，…，xn｝，Y2＝｛y1，y2，y3，…，yn｝，边＜xi，yj＞具有权值Wi，j。该带权的二分图中一个与总权值最大的完美匹配，就是最佳匹配设计。

设L（x）表示结点x的标记量，如果对于二部图中的任何边＜x，y ＞，都有L（x）＋L（y）＞＝Wx，y，我们称L为二部图的可行顶标。

设G（V，E）为二部图，G′（V，E′）为二部图的子图。如果对于G′中的任何边＜x，y＞满足L（x）＋L（y）＝＝Wx，y，我们称G′（V，E′）为G（V，E）的等价子图。

定理：设L是二部图G的可行顶标。若L等价子图GL有完美匹配M，则M是G的最佳匹配。

证明：由于GL是G的等价子图，M是GL的完美匹配，所以，M也是G的完美匹配。又由于对于匹配M的每条边e，都有e∈E（GL），而且M中每条边覆盖每个顶点正好一次，所以W（M）＝˚aW（e），e∈M＝˚aL（x），x∈V。另一方面，对于G的任何完美匹配 M′有W（M′）＝˚aW（e），e∈M′＜＝˚aL（x），x∈V，于是W（M）＞＝W（M′），即M是G的最优匹配。

由上述定理，我们可以通过不断修改可行顶标，得到等价子图，从而求出最佳匹配。设X为毕业设计题目，Y 值为学生，题目集合X ＝｛X1，X2，...，Xm｝，学生集合Y ＝｛Y1，Y2，...Yn｝，根据教师赋予学生课题期望值与学生志愿选择课题意愿值建立权值二分图，其中权值为二维矩阵W［m］［n］的值，教师赋予学生课题期望与学生志愿选择课题意愿不相关联权值等于0，相关联权值的试题显示给学生进行筛选。

3 选题分配算法优化

KM算法进行选题分配计算不足之处在于全局搜索能力较弱，其在初始聚类中随机选择选题，并没有对初始聚类进行优化，局限于部分选题最优匹配。同时KM算法收敛时间较长，在试题分类中无法达到最优的选题分类效果。因此，本文提出SA－KM选题分配算法，首先对聚类初始中心进行全局智能搜索，再通过KM算法进行聚类，进而能够获得全局搜索的最优聚类划分，从而提高毕业选题的快速搜索速度，减少利用KM算法进行选题搜索的盲目性，提高毕业设计选题分配的聚类划分质量。

3.1 SA－KM算法思想

SA－KM算法在搜索过程中如果发现新的最优匹配结果则无条件地替换原来的搜索结果，如果未发现最优匹配结果则接受原有的搜索结果。在毕业设计选题分配算法中，该算法跳出了教师与学生的选题分配权重的交集，丰富了选题内容。SAKM算法核心思想如图3所示。

图3 SA－KM算法思想

在毕业设计选题分配系统中，教师出题与学生选题可根据权重建立初始聚类中心，进而提高了学生选题的效率，避免了学生选题的盲目性，并减少了KM算法的迭代次数，提高了算法的计算效率。SA－KM算法跳出了KM算法只在权重交集中搜索毕业设计选题的局部框架，面向全局搜索获取最佳选题，当学生在全局搜索中找到新的最优解，则将最新解作为新的权重交集。SA－KM算法扩大了毕业设计选题的搜索范围，并提高了选题的搜索能力，当产生最新解时，更换权重匹配结果，提高学生自主选择的能力。