混沌遗传算法在自动组卷中的应用研究

徐新华

(泰州师范高等专科学校，江苏 泰州 225300)

遗传算法作为一种随机优化算法在多目标优化等众多领域取得广泛的应用，尤其适用于处理非线性问题求解和最优化问题.遗传算法同时具有内在的并行性、全局寻优和收敛速度快的特点，这些都适宜于处理自动组卷的问题.魏平[1]等采用传统的遗传算法(SGA)来实现试题库的自动组卷，取得了较好的实际效果.

但标准遗传算法(SGA)有它的局限性.算法初期，模式集中在适应度较低的个体上，若采用较小的交叉率和变异率，种群很难产生出优秀新个体.算法后期，模式开始朝适应度高的个体集中，倘若采用较大的交叉率和变异率，容易破坏优良模式，使算法陷入局部收敛.基本遗传算法通常只有一个种群，且交叉概率和变异概率这两个参数是固定的，存在早熟及收敛速度缓慢等问题，对于复杂的优化问题通常难以获得高质量的解；并且要为某个特定的优化问题设置好交叉概率和变异概率需要经过反复试验.

目前已经有很多研究人员对遗传算法进行改进并应用到组卷中，以提高组卷运行效率.王淑佩[2]等将自适应遗传算法与小生境技术相结合提出了一种自适应调整种群适应值分布的基于小生境技术的遗传算法；刘彬[3]等对题型确定过程中的知识进行改进，相对于简单遗传算法均取得了较好的结果；魏平[4]等采用稳态策略的单亲遗传算法求解组卷问题，通过突变算子的引入，使整个种群保持在最有可能获得成功的状态，加快了算法向全局最优值的逼近速度.

本文提出一种基于混沌序列的改进型遗传算法，来解决计算机组卷中约束优化问题.通过模拟实验，结果表明该方法有效解决了自动组卷中的约束优化问题，具有很好的性能和实用性.

1 自然数编码策略

按照一定的编码方法和编码策略，科学、合理、准确地为每道试题进行编码是高效组卷的首要工作，完整的试题编码能大大提高组卷算法的效率和成功率.在确定编码方案时，本系统采用了分段的自然数编码策略.每一段编码反映一种题型，各个题型各自进行自然数编码，题型组之间的编码是独立的.另外，由于在自动组卷过程中不是对试题信息进行操作，而是操作试题的编码.试题编码代表一道试题的特性.

一般题库中试题的属性项有：试题编号、试题类型、考查知识点、难度、区分度、认知层次、试题内容、操作说明、答题时间、建议分值、已使用次数、最近使用时间等.其中最重要的是知识点、认知层次、试题类型、试题难度和试题区分度等五个基本特征，故取这五个基本特征组成试题编码.

用两位编码(00-99)表示100个知识点.认知层次则按了解、理解、掌握和综合分类，分别编码1-4.表征题型的编码有相对随意性，本系统如下编码：“单项选择题(A1)”赋1，“多项选择题(A2)”赋2，“配对题”赋3，“填空题”赋4等.试题难度编码将分为五个等级，依次为：易赋1，较易赋2、中赋3、较难赋4和难赋5.试题区分度是指对学生学科能力的鉴别力，亦分五级，差赋1、较差赋2、中赋3、良赋4和优赋5.

将上述知识点、认知分类、试题类型、试题难度和试题区分度等五维特征编码结合起来，同时考虑到相同特征的试题有多个，需加上相同特征题目的顺序号，就构成每道试题的7位编号.如编码“5221231”表示该试题属于知识点“52”、认知层次是“了解”、题型是“填空题”、难度系数“较易”、试题区分度“中”、同知识点同题型试题编号“1”.

我们将一份试卷映射为一个染色体，染色体采用变长编码策略进行处理，组成试卷的各个试题映射为基因，染色体中基因的个数就是试卷中试题的个数，基因的值直接用试题编码表示.如图1表示两张试卷的染色体，染色体的长度为7*试题数.

图1 两份试卷的染色体信息图

以上编码策略优点体现如下：

(1)对试题进行自然数编码所表达的变量意义清楚、明确，可以克服传统的采用二进制编码搜索空间过大和编码长度过长的缺点，同时取消了个体的解码时间，有效改善了遗传算法的复杂性，提高了算法的运算效率.

(2)使用了分段的思想，把各类题型放在同一段，在进行遗传操作时，保持在段内进行，这样个体就不会进化到其它段，组卷时保证了优化目标中题型的正确匹配.

2 采用混沌机制控制遗传操作

早熟收敛是遗传算法在实际应用中经常遇到的一个疑难问题，它主要表现为种群中最优个体的适应度值得不到提高，种群在经过若干次迭代后仍不能找到全局最优解.引起早熟收敛的因素很多，比如选择、交叉和变异算子的使用不当或者控制参数的选择不当都会导致早熟收敛的发生.其实，从本质上来讲，早熟收敛主要是由于群体中有效基因的缺失[5]，或者只要群体中有效基因的浓度减少到一定程度时，就会引起早熟收敛的发生，使得群体处于停滞状态.

因此，为了预防早熟收敛，在有效基因未知的情况下，变异算子必须有能力保持同一基因位上的等位基因的多样性，这样才能有助于防止有效基因的缺损，从而能够最大限度地避免早熟收敛.本文提出了基于混沌序列的动态遗传操作，使遗传操作具有内在的规律性，克服了简单遗传算法中纯随机所带来的缺点，充分发挥了遗传算法和混沌理论的各自优点.

(1)混沌序列的产生.桂传志在文献[6]提到可以利用logistic映射、立方映射和逻辑自映射函数等三种映射方法产生混沌序列，并通过实验比较论证了三种映射方法产生混沌序列的分布均匀性.结果表明logistic映射的分布很不均匀，它的落点常超过90%；而立方映射和逻辑自映射函数相对来说要均匀一些.所以本文选用逻辑自映射函数产生混沌序列.具体公式如下：

x(n+1)=1-2x2(n)，

n=0，1，2，3…，-1

(1)

在实际工程应用过程中，只要迭代初值不为0，混沌就会发生，此时映射的定义域为[-1，1]，且x≠0，当迭代一定次数时，系统输出将遍历整个解空间.

(2)混沌交叉算子.用混沌序列控制交叉点的选择.设染色体有L位长，先产生一个混沌序列xn，然后把序列xn映射到染色体基因位空间.考虑染色体编码是以试题编码长度7的整数倍，我们要对产生的基因位空间按以下公式做适当调整，然后在相应的位置进行基因串的交叉操作，从而得到两个新的个体.

如果x∈[0，1]，则混沌交叉算子为

site=[(L×xn)/7]×7

(2)

其中，[…]符号表示向上取整.

在本组卷系统中，如有两套试卷(如下)组成配对个体组(假设试卷共有12道试题，则当前染色体的编码长度为12*7)进行单点交叉，其中X1和Y1表示一个试题：

染色体A：X1X2X3X4X5X6X7X8X9X10X11X12

染色体B：Y1Y2Y3Y4Y5Y6Y7Y8Y9Y10Y11Y12

如果式(1)、(2)所产生的一个混沌序列的当前值site1为14，则交叉位置是在第2道试题后面，则产生的下一代个体组为

染色体A'：X1X2Y3Y4Y5Y6Y7Y8Y9Y10Y11Y12

染色体B'：Y1Y2X3X4X5X6X7X8X9X10X11X12

(3)混沌变异算子.用混沌序列控制变异基因位.根据式(1)所产生的一个混沌序列的当前值x(k)，再利用式(3)把混沌变量xi(k)映射到染色体基因位空间，即混沌变异算子为：

Si(k)=[Nxi(k)]i=1，2，…，n(n≪N)

(3)

式中，N表示染色体编码长度，[…]表示取整.对相应基因位上的基因进行变异.结合试卷染色体编码位的取值范围，不能进行简单的变异，即0变为1、1变为0；而是根据试题编码位上每一位的可能取值范围进行变换(如试题编码的第6位表示区分度，其取值是在1～5之间).

结合前面示例，对染色体A'进行上述变异，从而生成新的个体A''=X'1X'2Y'3…Y'12，在试题库中搜索变异得到的试题是否存在，如果不存在则重新进行变异，如果存在则计算新个体的适应度值f(A'').

说明：混沌虽然具有类随机性、遍历性以及初值敏感性，通过迭代混沌映射可以生成统计特性呈随机分布的伪随机序列，但混沌不是随机，混沌具有短期可预测性质[7]，即总存在整数N和映射f，使得混沌序列{xn}可以用映射xn+N=f(xn，xn+1，…，xn+N-1)描述.

3 基于混沌序列的改进型遗传算法的执行流程

{ 设置当前代数计数器t←1；

初始化种群P(0)={X1，X2，…，Xn}；

计算P(0)中各个体的适应度Fi(i=1，2…M)；

while(不满足终止条件) //终止条件与SGA中相同

{ 根据个体适应度以及选择策略，计算种群内个体选择概率Pi；根据Pi从父体P(t)中选择N1(≤N)个个体；

将父辈群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代；

确定基于混沌序列的混沌交叉算子；

按交叉概率Pc对父个体的配对个体组再进行交叉操作，重组新个体组；

基于混沌序列映射产生混沌变异算子；

按变异概率Pm对新个体进行换位，产生下一代个体；

计算新一代群体P(t+1)中各个体的适应度，如果生成的新个体的适应度值大于原个体，则替换原个体，否则原个体保持不变；

t=t+1； //代数增1

}

}

4 小结

本文提出了基于混沌序列的改进型遗传算法，并指出在组卷系统实现的过程.首先对染色体采用分段自然数编码策略；然后，将混沌机制同时引入到遗传算法的交叉和变异阶段，对在交叉阶段交叉基因座由混沌交叉算子来确定，在变异阶段变异个体的变异基因位由混沌变异算子来给出.这种改进型遗传算法将混沌优化的遍历性、规律性与遗传算法的全局性相结合，可以有效地克服遗传算法随机性大、未成熟收敛等不足.

当然，目前我们给出的算法还相当粗糙，其中参数设置调整需要靠经验试凑，对算法实现的收敛性等尚未给出严密的数学分析和证明.相信随着上述问题的解决，将会产生较为精致的全局优化方法，为解决实际问题提供有效的便利工具.

参考文献：

[1]魏平，张元.一种求解组卷问题的遗传算法[J].宁波大学学报，2002，15(2):47-50.

[2]王淑佩，易叶青.基于改进自适应遗传算法的组卷研究[J].科学技术与工程，2006，6(4):468-473.

[3]刘彬，李勇，糜长军.智能组卷系统中专家知识的表示与实现[J].计算机工程与应用，2002，38(17):229-231.

[4]魏平，干海光，熊伟清.基于进化稳定策略的单亲遗传算法求解组卷问题[J].微电子学与计算机，2005，22(1):l05-109.

[5]挥为民，席裕庚.遗传算法的运行机理分析[J].控制理论与应用，1996(3):297-304.

[6]桂传志.混沌序列在优化理论中的应用[D].南京：南京理工大学，2006.

[7]王开.确定性随机理论及在混沌密码学中的应用研究[D].南京：东南大学，2004.