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

    传统的遗传算法采用二进制编码，用1表示某题被选中，0表示某题没有被选中，这种编码非常简单，但在进行交叉和变异操作时，各题型的题量很难控制，而且当试题库题量很大时编码很长。传统的遗传算法以进化代数等于最大进化代数作为终止条件，但是在实际组卷过程中并不知道种群进化到第几代就能得到试卷的最优组合。因此用遗传算法实现自动组卷时，要对传统遗传算法进行一些改进。

4.1.1  染色体编码

    通过对编码的大量分析，提出了一种分段实数编码机制，首先将染色体分成若干段，每一段对应一种题型，组成试卷的各道试题题号直接映射为基因，编码时将同一题型的试题放在同一段，同一段内题号各不相同。以题号编码的方法所表达的意义清楚、明确、不需解码，从而可以提高算法性能，提高运算效率。而且交叉和变异操作都在各段内部进行，因此可以保证组卷过程中各题型题量的正确匹配。

4.1.2  适应度函数设计

    遗传算法在进化搜索中仅以适应度函数为依据，利用种群中每个个体的适应度值来进行搜索。因此，适应度函数的选择至关重要，一般而言，适应度函数是由目标函数变换而成的。上面提出的自动组卷模型是最小化问题，采用如下方法可将目标函数f转换成适应度函数F。                               

    由上式可知，F的取值范围为0～1，适应度函数F的值越大，说明个体越好，个体越接近问题的最优解。

4.1.3  初始化染色体群体

    随机生成初始染色体群体，在初始染色体群体中，染色体的长度为n，群体的大小为m，m太小时，难以求出最优解，太大时则增长收敛时间。群体的大小一般根据需要，按经验或试验给出，一般m=30～160。

4.1.4  遗传算子

(1) 选择算子

    在遗传操作中，为了保留较优的个体，以概率1完全地复制每一代群体中按适应度值从大到小依次排列的前面2个个体。为了保持群体大小不变，同时删除适应度排列的后面的2个个体。然后从排列在前面的m-2个个体中随机抽取p(p≤m-2)个个体进行交叉和变异操作。这种选择策略使得适应度小的个体也有可能被选中，这样有助于增加下一代群体的多样性。

(2) 交叉算子

    在遗传操作中，采用了分段的思想，交叉的时候按题型段进行交叉，因此交叉后不存在段内试题重复的问题，也不会改变每种题型的题量。交叉概率p_c太小时难以向前搜索，太大时则容易破坏高适应度的结构。一般p_c=0.4～0.6。

(3)变异算子

    在遗传操作中，变异在染色体的题型段内进行。变异概率p_m太小时难以产生新的基因结构，太大时使遗传算法成了单纯的随机搜索。一般p_m=0.01～0.2。

4.1.5  终止条件

    在改进的遗传算法中，设置了期望适应度值，把每一代计算出来的最高适应度个体的适应度值与期望适应度值相比较，当适应度最高的个体的适应度值大于或等于期望适应度值时则停止进化，否则继续进行遗传操作、计算适应度值、反复迭代直到组卷成功。

    基于改进遗传算法的自动组卷的主要算法描述如算法1所示。

算法1：

    int GJGA(p_c，p_m，m，f0)

    {

        t=0；

        initialize(p(t))；//随机产生初始染色体群体

        计算初始染色体群体的适应度值；

        while (maxf<f0) //当适应度最高的染色体的适应度值小于期望适应度值时

    {

        selection(p(t))；//选择操作

        crossover(p(t))；//交叉操作

        mutation(p(t))；//变异操作

        得到下一代染色体群体q(t+1)，计算下一代染色体群体的适应度值；

        t++；

    }

        输出当前染色体群体中适应度最高的染色体；

    }

    在遗传算法中，绝大部分处理都集中在适应度的计算上，因此可以用计算个体适应度操作的时间复杂度作为算法的时间量度。遗传算法的时间复杂度为O(t*m*n)。因为试题库中的题量一般都很大，所以改进后的遗传算法的时间复杂度一般要比传统遗传算法的时间复杂度小。遗传算法的空间复杂度可以用初始染色体群体所占的空间来衡量，遗传算法的空间复杂度为O(m*n)。因为改进后的遗传算法的染色体的长度远比传统遗传算法的染色体的长度小，所以改进后的遗传算法的空间复杂度远比传统遗传算法空间复杂度小。

    算法的改进往往不能顾及问题每一个方面，如果算法设计的核心是提高解的精度，则算法可能在搜索范围和搜索精度上花去更多的时间，如果算法的设计主要在于尽快收敛，得到结果，则在解的精度上考虑很少，算法往往侧重于减少进化代数。改进后的遗传算法使生成试卷的质量得到了保证，但要使组卷的收敛速度得到进一步改进，还需进一步研究。

[1] 文海英. 智能型试卷自动生成系统中试卷难度控制技术的研究(J).湖南科技学院学报，2005，26(5)：153-156

[2] 常振江. 学生成绩分布与一种简便的评估试卷命题质量的方法(J). 辽宁师范大学学报：自然科学版，2003，26(1)：109-112

[3] 丁卫平. 基于遗传算法的智能组卷应用研究.电气电子教学学报(J)，2005，27(2)：93-95

[4] 朱黎明. 基于单亲遗传算法的试题生成及其应用研究(D). 长沙：湖南大学，2005

[5] T.Lynda，C.Chrisment，Boughanem Mohand. Multiple Query Evaluation Based on Enhanced Genetic Algorithm. Information Processing and Management，2003，39(2)：215-231