算法分析
M为符合 条件题量
1、将符合条件 V1
Ｖ2
Ｖ3
Ｖ4 …… Ｖm
的题目加载到
向量vector
2、将题目“洗牌” 实现随机效果
FOR (i= m ;i >1 ; i--){ int j = Random(m-1); 交换Vi 和Vj;
}
3、按顺序取出组卷的题量
并发到考试试卷中
V1 Ｖ2 …… Ｖk
F(x)的值越小说明个体的适应度越高，越符合组卷期望。
遗传算法
选择概率
个体在遗传操作中被选择的概率，适应度越大被选中的概率越大，即 适应度值越小被选中的概率越大
1 / F(xi) P(xi) = ----------------
N
∑ 1 / F(xj)
j=0
遗传算法
流程图
遗传算法
传统遗传算法的不足：
遗传算法
基本的遗传算法可定义为一个8元组：
SGA = （C，E，P0，M，Ф，Г，ψ，Τ）
其中：C为个体的编码；E为个体适应度评价函数； P0为初始种群；M为群体的大小； Ф为选择算子； Г 为交叉算子； ψ为变异算子； Τ为终止条件。
遗传算法
适应度函数：
n
F(x) = ∑ wigi
i=1
n：表示约束条件的维度，如题型、题量、知识点、曝光度等 wi：表示第i个约束维度所占的权重 gi：表示第i个约束维度值与期望值的误差
缺点：相对前面两种算法来说速度慢，不适用于组卷 需求中的第三种情况。
遗传算法
概念 简称GA（Genetic Algorithms），是1962年由美国 Michigan大学的Holland教授提出，是一种模拟自然 界遗传机制和生物进化论而成的一种并行随机搜索最 优方法。主要包括三个方面内容：适者生存、遗传、 变异。
组卷需求
题目相同，出现顺序也相同
1）在一场考试中，所有的考生均使用同一份考卷（或AB卷），且考卷的题目出现的顺序相同。 2）约束条件通常包括：题型、题量、分布章节、知识点、总分、曝光度等
题目相同，出现顺序不相同
1）在一场考试中，所有的考生均使用同一份考卷，但每个考生的考卷题目出现的顺序不同。 2）约束条件通常包括：题型、题量、分布章节、知识点、总分、曝光度等
Step2：move
selectVector
While selectVector 数量不足{ int j = random(m); 将Vj取出放入selectVector中 if（j < m){ 将 Vm值放入Vj中； m --;
}
}
遗传算法
常见的应用场景
约束条件整卷要求多，需要智能均衡参数指标功能， 适合于一场考试组几份试卷，即适合于组卷需求中的 前两种需求。
属于人工智能领域
遗传算法
基本概念
个体：模拟生物个体而对问题中对象的一种称呼，一个个 体也就是搜索空间中的一个点。 种群：就是模拟生物种群而由若干个体组成的群体，它一 般是整个搜索空间的一个很小的子集。 适应度：就是借鉴生物个体对环境的适应程度，而对问题 中的个体对象所涉及的表征其优劣的一种测度。 适应度函数：就是问题中的全体个体与其适应度之间的一 个对应关系。它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数（或目标函数）。
遗传算法
遗传操作
也称为遗传算子（genetic operator)，包括三种遗传 操作： 1）选择-复制（selection-reproduction) 2）交叉(crossover，也称为交互、交配或杂交） 3）变异（mutation，也称为突变）
遗传算法
传统遗传算法流程：
（1）编码 ：将事物编成01的二进制字串 （2）初始化种群：初始化一定数量的种群，该种群不一定要非常的精确，可在进化中优化； 种群中个体的数量是不变的； （3）设计个体种群适应度函数；各个模型函数不一样 （4）选择： 在种群中根据轮盘赌算法 选出初始化种群规模（N）的个体，即选择N次。情况 分析：可能在选择的过程中会重复选择到同一个个体；不是选中概率大的就一定会被选中， 也不是选中概率小的就一定选不中。经过选择过程得到新的种群（S‘）。 （5）交叉（交配）：根据交叉率Pc从S’种群中选择一定数量个体进行两两交叉，遍历种群选 出待交叉的个体，两个进行选出的1,2个体交叉，3,4个体交叉，若最后存在落单，则最后一个 个体放弃交叉。用交叉后的个体替换原来的个体。 这样经过交叉遗传后得到新的种群S‘’。 （6）变异：根据变异率Pm从S''种群中选择一定数量个体进行变异，并用变异后的个体替换 原来的个体，这样形成一个新的种群S'''; （7）这样一个循环下来就形成了新的一代种群，然后用适应性函数进行判断是否符合要求。
洗牌算法
组卷约束条件
单选题 容易（10），中等（5），难（5） 题量：20 知识点范围
多选题 容易（15），中等（2），难（3） 题量：20 知识点范围
判断题 容易（10），中等（10），难（5） 题
……
……
1、试卷结构 2、知识分布 3、上述条件强制性要求符合
洗牌算法
根据不同的应用场合，常见组卷算法主要包括：
1）洗牌算法 2）随机算法 3）遗传算法
洗牌算法
常见的应用场景
约束条件较多、较细化、较明确，在某一定范围（M） 内抽取一定数量（N，N<=M）的题目。
缺点：没有智能均衡参数指标功能。如不能较容易的 实现只给定试卷的整卷难度自动根据每道题的难度系 数智能均衡。
4、批量写入到数据库表中 每次批量50条题目
随机算法
常见应用场景
同洗牌算法，原理也大体相同
随机算法
算法分析
1、将符合条件 V1
Ｖ2
Ｖ3
Ｖ4 …… Ｖm
的题目加载到
向量vector
2、随机从向量
中抽取试题放入 已选题目中，反
V1
复直到满足数量
Ｖ2
Step1：random
已选的试题 V1
Ｖ2
Ｖ3 Ｖ4 …… Ｖm
题目不相同
1）在一场考试中，所有的考生使用的试卷题目均不相同（相对，随机）。 2）约束条件通常包括：题型、题量、分布章节、知识点、总分。 3）此种由于在一场考试中要求组卷的数量较多，通常情况下不要求曝光度，否则会由于题库题目数 量有限导致各题目的曝光频率均衡，因此曝光度约束没有实质性意义
组卷算法
“早熟”现象 随着种群多样化，部分高适应度个体的指数级增长比 如使得种群中大部分个体各基因位上的基因趋于一致， 种群的多样性逐渐减小。