基于改进遗传算法的自动组卷研究(1)

    自动组卷就是根据用户的要求，采用一定的算法自动地从试题库中抽取一定数量的试题组成试卷。自动组卷算法的好坏直接影响到试卷的质量，如何从试题库中选出试题组成符合用户要求的试卷，并使组卷具有较高的效率和成功率是当前研究的热门课题。现有的自动组卷算法一般有三种：随机选取法、回溯试探法和遗传算法。遗传算法是一种新发展起来的并行优化算法，它很适合解决自动组卷问题。

    在自动组卷系统中，一些试题库设置了试题的各类属性，如章节、层次、要求、题型、难度系数、难度级别、各章节分值等属性，其实过多的属性会增加实际组卷的难度，降低效率。以教育学理论为指导，选择以下属性作为试题的核心属性。

    (1)     题号。试题的编号，用来唯一标识试题。

    (2)     题型。试题的类型。

    (3)     知识点。某道题属于某门课程的哪个知识点，知识点的设置不以章节为依据，从而可以避免教材的不同对组卷造成影响。

    (4)     难度系数。难度系数^[1]是表示某一试题的难易程度，通常用未通过率来表示，即一次考试中未答对某道试题的考生数在其总体中所占的比例。一般来说，难度系数值为0.5时，是中等难度，如果小于0.3试题太简单，如果大于0.7试题太难，对考生都会做或都不会做（难度系数为0或为1）的试题，属于无意义的试题，必须淘汰。

    (5)     区分度。区分度^[2]是指某道题对不同水平考生加以区分的能力。区分度高的试题，对学生水平有较好的鉴别力。区分度的计算公式为：

    其中，B表示试题的区分度，H表示样本中高分组在某题上所得的平均分，L表示样本中低分组在某题上所得的平均分，K表示某题满分。高分组和低分组一般各占样本的25%～30%，最好取27%。一般来说，试题的区分度在0.4以上就被认为是很好的。在0.3～0.39之间，认为良好；在0.2～0.29之间，认为可以；在0.19以下，认为差，必须淘汰或加以修改。对在校学生的达标考试，试卷的区分度不宜太高，因为它不是选拔性质的考试。但也不能过低，否则对学生的鉴别效果差，不能很好的达到考试的目的。一般区分度控制在0.2～0.3之间为宜。

    (6)     分值。某小题的分数。

    (7)     答题时间。完成某题估计所需的时间。

    自动组卷中决定一道试题，其实就是决定一个包含题号、题型、知识点、难度系数、区分度、分值、答题时间的七维向量（a₁，a₂，a₃，_a4，a₅，a₆，a₇）。假设一套试卷中包含n道试题，一套试卷就决定了一个n×7的矩阵S：

    这就是问题求解中的目标矩阵，其中a_i1 、a_i2、 a_i3 、a_i4、a_i5、 a_i6 、a_i7分别表示试卷中第i道题的题号、题型、知识点、难度系数、区分度、分值、答题时间。从矩阵S可以看出组卷问题是一个多重约束目标的问题求解，且目标状态不是唯一的。

    在实际组卷时，用户会对试卷提出多方面的要求，用户的每一个要求对应试卷的一个约束条件。要组成一份符合要求的、高质量的试卷，目标矩阵的分布要满足以下试卷约束条件。

    (1) 试卷中包含的题型以及每种题型的题量要与用户的设置相符。

k种题型的题量=                   

    (2) 试卷中包含知识点即考核知识点以及各考核知识点所占分数的比例要与用户设置相符。

K种考核知识点所占分数=    

     (3) 试卷的难度系数要满足用户的要求，试卷的难度系数一般用试卷中每道试题的难度系数的加权平均来计算。

即：试卷的难度系数= /总分

    (4) 试卷的区分度要满足用户的要求，试卷的区分度一般用试卷中每道试题的区分度的加权平均来计算。

即：试卷的区分度=/总分

    (5) 试卷的总分要与设置相符。

即：试卷的总分=

    (6) 试卷的总答题时间要与用户设置相符。

即：试卷的总答题时间=

    在实际组卷时，试卷的总分、考核知识点、各题型每小题分值、试卷中包含的题型、各题型的题量都应该是精确达到的。试卷中各考核知识点所占的分数、试卷的难度系数、区分度和试卷的总答题时间这四个约束条件可以存在一定的误差。误差的大小由用户的期望值和各约束条件的重要性决定。在实际应用中，各约束条件的重要性是不同的，因此，目标函数就取各项误差的加权和。目标函数f可以表示为：

    为了不至于各项误差相互抵消，实际值与用户要求值的误差都取绝对值。其中，试卷中各考核知识点所占的分数和试卷的总答题时间这两项的误差为实际值与用户要求值的误差绝对值与用户要求值的比，试卷的难度系数和区分度这两项的误差为实际值与用户要求值的误差的绝对值。w_i表示第i个约束条件的权值，w_i通常由专家经验或试验给出，0≤w_i

≤1， 。由上式可知，目标函数f的值越小，即误差

越小，问题的解越优，即生成的试卷越接近用户的需求。

    遗传算法^[3，4，5]是以适应度函数（或目标函数）为依据，通过对群体中的个体进行遗传操作实现群体内个体结构重组的迭代处理过程。在这一过程中，群体中的个体一代一代地得以优化，并逐渐地逼近最优解，最终获得最优解。传统遗传算法的主要步骤包括初始染色体群体生成、适应度评估和检测、选择操作、交叉操作和变异操作。传统遗传算法流程图如图1所示（其中t为进化代数，t0为最大进化代数）。