毕业论文

打赏
当前位置: 毕业论文 > 计算机论文 >

基于遗传算法的题库自动组卷系统的设计与实现(3)

时间:2020-11-17 10:19来源:毕业论文
2.1.2 遗传算法的基本操作步骤源]自{优尔~论\文}网www.youerw.com/ (1)初始化操作:设置一个初始值,该值表示最多允许遗传繁殖多少代,如果超过这个值,

2.1.2  遗传算法的基本操作步骤源]自{优尔·~论\文}网·www.youerw.com/

(1)初始化操作:设置一个初始值,该值表示最多允许遗传繁殖多少代,如果超过这个值,就认为遗传算法是失效的。

(2)计算适应度(AdaptionDegree)操作: 我们先建立一个遗传算法的模型,模型的重点就是适应度公式的推导,有了这个公式后,我们就利用公式指导遗传方向

(3)选择操作:选择操作说的通俗一点,就是在一大堆种群个体里面选出指定数量的个体,由于种群个体的数量可能会很多,考虑到计算的复杂度,我们不会让所有的个体都参与选择,我们只能选择部分个体,当然,这部分个体可以随机选择出来,也可以设定自己的优化算法有目的去选择,这样选择出来的种群一开始就具备优化的“基因”。通常的用的选择算法是轮盘赌选择算法。

(4)交叉操作:说的通俗一点,交叉操作就是“父亲”和“母亲”的基因进行交叉,因此产生的基因肯定带有父代的信息。

(5)变异操作:在进化论里面,变异是指部分基因小概率的变化,遗传算法的变异操作也一样,它是指新生代的部分基因发生变化,当然这种变化的概率是很小的,不过正是因为这种变异,才有了种群的多样性,你总不希望世界上有很多人长的像你吧。

2.2  遗传算法在自动组卷系统中的应用设计

自动组卷是出卷者给出一些约束条件,比如试卷的难度系数、试卷的总分、题目总量、题型比例、知识点覆盖率,然后根据这些约束条件,从题库里面搜索出符合要求的题目,它的本质上是一个有多重约束的组合问题,因此适合用遗传算法来解决。

在掌握了传统的遗传算法后,我们会发现它一般搜索后期效率低。因此,我对遗传算法做了优化,初始种群时也是要满足一定的约束条件,并非随机初始,在种群个体交叉后多加入一次判断适应度的过程,还有其他细节的优化,这些优化都能帮助遗传算法快速向最优解迭代,避免了陷入局部解的困局。具体优化方案如下。

染色体编码和初始群体的设计:遗传算法最关键的步骤之一就是建模——将问题的解空间映射成一组字符代码串是建模的关键过程。传统的遗传算法一般采用二进制编码,但是这样解空间太大,不容易搜索,效率也不高。因此还是实数编码更优,具体操作为:将一份试卷映射为一个染色体,把每道题目的题号作为基因,如下所示:

(2、16、2 | 29、33、36、39  | 63、47、234 | 42、58、55  |  88、96、56)

   判断题    填空题             单选题        多选题         问答题

初始种群时也是要有条件的产生,比如一开始就必须强制满足总分、难度比、知识点覆盖率等等要求,如果一开始都满足不了,以后肯定也不会生产出符合约束条件的试卷。这就正如父亲和父亲都是A型血,他们肯定是生不出B型血的孩子的道理一样。

设计适应度函数:在遗传算法中,有两点最重要,一是模型的建立,如何将解空间映射为字符串,二是适应度函数的设计。适应度函数就像是一个指明灯,就是引导遗传算法的“光明方向”。话不多说,我们先看看在自动组卷系统中怎么样设计适应度函数的:

f=1-(1-M/N)*f1-|EP-P|*f2

参数说明:f1为知识点分布的权重,f2为难度系数所占权重。当f1=0时,其含义表示不关注知识点的分布,当f2=0时其含义表示不关注难度系数。M/N的含义是代表知识点覆盖率,|EP-P|的含义是代表实际难度系数与期望难度系数的差距。 基于遗传算法的题库自动组卷系统的设计与实现(3):http://www.youerw.com/jisuanji/lunwen_64957.html

------分隔线----------------------------
推荐内容