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