4 系统详细设计
4 系统详细设计
4.1 设计方案
代码结构如图4-1。
图4.1 代码结构图
其中src包中存放所有Java程序的源码，resources包中存放表示层相关的velocity页面、图片和组件的config.xml配置文件。src包、resources包结构如图4.2、图4.3。
16
4 系统详细设计
图4.2 resources包结构 图4.3 src包结构
4.2 算法详细介绍 4.2.1 遗传算法的概述
自1960年以来，人们对于模拟生物以及由此开发的针对复杂优化问题的有效算法产生了浓厚的兴趣。当前在该领域中常常引用的术语就是进化计算。它包含以下一些主要算法：遗传算法、进化策略、进化规划和遗传程序设计。当然还存在若干将上述算法的各种特点加以结合而形成的混合算法。
同时，遗传算法(Genetic Algorithm, GA)作为近几年发展起来的一种崭新的全局优化算法，借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。这一点体现了自然界中\物竞天择、适者生存\进化过程。1962年Holland教授首次提出了GA算法的思想，从而吸引了大批的研究者，迅速推
17
4 系统详细设计
广到优化、搜索、机器学习等方面，并奠定了坚实的理论基础。 用遗传算法解决问题时，首先要对待解决问题的模型结构和参数进行编码，一般用字符串表示，这个过程就将问题符号化、离散化了。同时，也有在连续空间定义的遗传算法(Genetic Algorithm in Continuous Space, GACS)。
作为强有力而且应用广泛的随机搜索和优化方法，遗传算法可能是当今影响最为广泛的进化计算方法之一。一般认为，遗传算法有五个基本组成部分：
? 问题的解的遗传表示 ? 创建解的初始种群的方法
? 根据个体适应值对其进行优劣判定的评价函数
? 用来改变复制过程中产生的子个体遗传组成的遗传算子 ? 遗传算法的参数值
遗传算法维持有一群个体组成的种群P(t)（t代表遗传代数）。每一个解均代表问题的一个潜在的解答。每一个个体都被评价优劣并得到其适应值。某些个体要经历称作遗传操作的随机变换，由此产生新的个体。主要有两种变化方法：变异（mutation）的方法是将一个个体改变从而获得新的个体；杂交（crossover）的方法是将两个个体的有关部分组合起来形成新的个体。新产生的个体（称作后代（offspring）C(t)）继续被评价优劣。从父代种群和子代种群中选择比较优秀的个体就形成了新的种群。在若干代以后，算法收敛到一个最优个体，该个体很有可能代表着问题的最优或次优解。
4.2.2 遗传多目标优化
近来，遗传算法作为多目标优化问题的新求解方法收到了相当程度的关注，这就诞生了进化或多目标遗传优化。这个主题已经由Fonseca和Fleming、Horn、Tamaki、Kita和Kobayashi进行了综述。
遗传算法的内在特征说明了为何遗传搜索适合用于多目标优化问题。遗传算法的基本特征是通过在代与代之间维持由潜在解组成的种群来实现多向性和全局搜索。这种从种群到种群的方法在搜索Pareto解时是有用的。
遗传算法不需要许多数学上的必备条件，可以处理所有类型的目标函数和约束。由于算法的进化本质，遗传算法可以在不考虑问题特定内部工作方式的前提下用于搜索解。因此能够用遗传算法求解的复杂问题的数量可能比能够用传统算法求解的复杂问题的数量大得多。
由于遗传算法作为一种超启发式的算法，可以灵活地将传统方法结合进其主框架，因此可以利用遗传算法和传统方法两方面的优势来建立对问题更有效地求解方
18
[6]
4 系统详细设计
法。
4.2.3 遗传算法在本系统中的应用
在本系统中，运用遗传算法作为组卷的策略。采用非优超排序法对染色体进行评价，在选择算子的设计上，既能够复制一部分较好的个体，又体现了选择的概率性。变异概率和交叉概率能随个体的不同适应度自适应改变，同时变异概率随种群多样性自适应变化。采用数据仓库的最优解保存策略，使得搜索结果呈现出丰富的Pareto解集。
根据本系统的组卷要求，可知试卷构成基于如下元素：总分、难度、区分度、章节百分比、题型百分比、能力层次百分比等参数。由此可推知组卷策略的遗传算法是多目标优化模型范畴中的典型问题。而遗传算法的群体优化策略恰好为多目标优化提供了最为合适的解决方案。
1.数学约束的确定
选择试题组成试卷主要由试题库中的试题类型、题型分数、教学要求层次、章节、试题难度、试题区分度、答题时间四个属性决定，即取决于一个四维向量（a1,…,a4）。通过选题而组成一份试卷。试题数为n，则由此形成了一个4n维的试卷属性矩阵PAM，其定义如下：
其中，aij表示试卷中第j题中第i个属性值，且个约束条件：
约束1：约束2：约束3：约束4：时间。
2.染色体编码方式的选择
在染色体的编码设计上，有多种方式可供选择：
若采用定长符号编码方式，则可认为每一条染色体即一份试卷，代表种群中的一个个体。染色体中的每个基因代表试卷的一道试题，以该实体存储于数据库
19
，。
如果生成的试卷合乎要求，则在该试卷的试卷属性矩阵中，应该满足以下几
，P为试卷要求的总分，a2i为第i题的分数。
, Nt为t题型要求的试题分数，当试题分数
，dml为第ml难度级要求的分数比例，当
,TIME为试卷要求的答题时间，a4i为第i题的估计
a1i为t时，typet为1，否则为0。
难度a5i属于难度级ml时，difml为1，否则为0。
4 系统详细设计
中的ID来表示。根据用户输入的总分值和各题型占总分值的百分比来确定各个题型所占的分值，再根据题库里该题型试题的分值种类来确定染色体中该题型试题的百分比来确定各个题型所占的分值，再根据题库里该题型试题的分值种类来确定染色体中该题型试题的数目。
另外还有SGA方法，它采用HOLLAND的标准二进制编码方式，定义如下：CH∈Bp，B∈{0,1}，p表示二进制位串的长度，在这里表示试题库中试题的数目。染色体上的每一个基因代表对应的试题是否被挑选：1为该试题被挑选，0为该试题没有被挑选，每一个染色体代表一组选题结果。这种方法表达清晰，易于实现交叉与变异，但是在试题库很大时，占据存储空间大而且计算量也大，性能会随之下降；除此之外，分段的浮点数编码也是非常常用的编码方式之一。
在比较了多种编码方法，并结合本系统的规模详细分析之后，最终本系统选择了分段的浮点数编码，染色体形如（a1，a2，…，an）,其中ai表示试题库中试题的题号，n为试卷要求的试题数。基因按照题型有序排序，并且将同类型的试题放在同一个区间内。染色体编码示意图如下图4.4所示：
图4.4染色体编码示意图
在串种群中，串长度都是相同的，即题库中的试题数，保证基因位为1的数目为n，即试卷要求的试题数。在本系统所使用的组卷算法中，依据组卷要求，从每一类题型中随机产生相应数目的题号，按题型有序地存入个体的染色体中。保证同种题型的各题号严格相异的要求以解决题目重复的问题。每个题号都在相应题型的题号定义域中产生。 3．适应度函数的确定
适应度函数也称为评价函数，可用于评价个体的好坏，适应度函数的设计合理性对遗传算法的性能有很大影响，因此适应度函数必须是计算量比较小，通用性比较强，而且必须是单值、连续的合理函数。有很多，假设
为目标函数，
20
[12]
常用的适应度函数映射方法
表示对于个体的适应度函数，例如：