遗传算法组卷的研究与设计

2024年5月10日发(作者：)

·研究探讨·

遗传算法组卷的研究与设计

中国人民解放军78020部队 倪雪飞 孙吉花

【摘要】在线考试系统中的自动组卷技术是系统的核心，是近年来的一门综合新兴学科，它是根据每次的考试要求通过

系统来实现自动生成考试试卷，从而克服传统的一些弊端。本系统考试的要求包括：考试人员类被，考试方向，考试试

题类别，试题数量，试卷分值，试题分值，考试时间等参数。通过考试了解当前阶段的任务完成情况和存在的不足。自

动组卷能够避免考试中因为人为主观因素造成的影响，自动组卷技术已经被越来越多的在线考试系统采用。

【关键词】自动组卷 遗传算法 在线考试

当今社会工作节奏的加快，为了能够增强自己在社会中的

竞争力，学习充电是必须的，但是繁琐的异地资格考试很是浪

费时间和精力，在线考试系统就应运而生，在线考试系统需要

做到能够真实有效的考察一个人的知识掌握情况，这就需要在

组卷上算法上做到尽量智能化。特别是要避免人工组卷带来的

不安全性和不客观性，所以在线考试系统采用的组卷技术一般

都是自动组卷。其中常见的组卷技术有随机组卷、回溯组卷和

遗传算法组卷等，下面我们详细讲解遗传算法组卷。

遗传算法

遗传算法概述

遗传算法

[1]

（Genetic Algorithm，简称GA）是一类借鉴生物

界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随

机化搜索方法，由美国的d教授1975年首先提出。遗传

算法是一种模拟达尔文的生物进化理论物竞天择的计算模型，

通过对自然界生物进化的模拟来解决多约束条件下的最优解。

算法实施流程图如图1所示

单选题 多选题 判断题 论述题

在遗传算法的开始，一般采取的是随机生成初代种群，以

达到遍历所有状态的目的。但是这样会一定程度上延长进化的

时间，本文针对系统的使用对象和问题的实际情况，采用不完

全的随机初始化种群的方法，初始化种群的时候就设定试卷的

考试方向、各个题型的数量、分数以及考试时间，这样生成的

种群就已经满足了试卷的一大部分要求，加快了算法的收敛和

减少了迭代次数，同时取消了个体解码时间，提高了求解速度。

适应度函数设计

适应度函数是遗传算法寻求最优解的依据，一般来说是由

目标函数直接转化而来，通过它来对群体中的个体的优劣程度

进行评估，指导算法的搜索方向，因此适应度函数的好还是至

关重要的，因此，一份试卷的适应度

[3]

越高，那么它就越接近算

法的最优解，本文在初始化种群中就已经约束了试题方向、分

数、考试时间等辅助信息，只需要考虑试卷的难度系数就行了，

所以本文中所用的适应度函数是由试卷的难度系数公示转换而

成的。试卷的难度系数为公式1：

∑

D

1

n

1

n

i

×S

i

i

(1)

∑

S

其中Di 为第i道题的难度系数，Si为第i道题的分数 ，n

为试卷中试题的总数目。用户的期望难度EP与试卷的难度P之

间的差

f=|EP−P|

越小越好。如果一份试卷中期望含有

N个知识点，而一个个体试卷中含有M个知识点，那么该份试

卷中知识点覆盖率为

M/N(M≤N)

,上面说到EP和P之

间的差值越小越好，知识点覆盖率则越大越好，本文中遗传算

法的适应度函数为公式2：

图1 遗传算法流程图

基于遗传算法的自动组卷

编码方案和种群初始化

遗传算法是对种群中的个体进行操作，问题空间的参数通

过基因链的形式表示出来，编码的好坏对算法解决问题的能力

有直接影响。目前，存在的编码方式包括二进制编码、动态编

码、格雷码编码

[2]

、十进制编码和实数编码等多种方式。在本系

统的组卷应用中，在组卷过程中对数据库的存取访问速度受到

试题数据结构的影响较大，为了能够在组卷过程中减少数据访

问的时间开销，直接以题号作为基因的值，每种题型的题号放

在一起，这样就能快速的获得指定类型的试题。因此，本系统

采用分段的实数编码方案，比如要组一份“后勤理论”的试卷6

道单选，5道多选，3道判断，2道论述，其染色体的编码为：

(10,12,3,5,9,40) (25,32,21,6) (16,51,11) (7,26)

M

)×f

1

−|EP−P|×f

2

（2）

N

公式2中f1为知识点分布权重，f2为难度系数所占权重，

其中f1为零时，那么只考虑难度系数；f2为零时，只考虑知识

点覆盖率，由于本系统使用对象的特点，只考虑难度系数。

遗传算子

1．选择算子

选择算子

[4]

的主要作用是根据个体的适应度大小决定个体

是被选中还是淘汰，这样适应度高的个体生存机会就要高一些，

为了让遗传算法在组卷中发挥更好，本文采用的是轮盘赌方法，

根据个体的适应度的不同，个体被选中的概率为公式5-1所示，

通过公式可以看出，个体的适应度越高，被选中的概率就越大，

这样优秀的个体就能够得到保留。

2．交叉算子

本文在对个体进行染色题编码的时候采用的是分段实数编

（下转第236页）

f=1−(1−

234

·研究探讨·

密码与加密

计算机应设置密码，不同用户设置不同密码，严格保护密

码。密码安全性由高到低分别为系统启动密码、用户密码、BIOS

密码。其中系统启动密码在【开始】【运行】中输入“SYSKEY”

设置，用户密码在【控制面板】【用户账户】中点击该用户设置，

BIOS密码在CMOS设置的“Advanced BIOS Features”里设置。

设置密码是第一道防线，计算机内重要信息需建立第二道

防线，即加密。常见方法有4种：一是使用组策略工具把存放

重要信息的硬盘分区设置为不可访问；二是设置注册表，在

HKEY_CURRENT_USERSoftwareMicrosoftWindowsCurrentVersi

onPoliciesExplorer中新建一个DWORD值，命名为NoDriv并赋

上相应驱动器的值，隐藏该驱动器。三是使用WinRAR 数据加

密，把想要隐藏的文件和文件夹【添加压缩文件】，选择【高级】

【设置密码】加密。四是使用专业的加密软件，如：《文件夹加

密超级大师》、《文件保护3000》、《超级秘密文件夹》等。

操作权限管理

按照权限最小原则为不同用户分别配属权限，合理使用系

统资源。计算机默认用户组比较多，实际有Administrators和Users

两个用户组就足够了，建议删除Guests组。关闭计算机用户不

使用的系统服务，特别是可以远程控制计算机的服务，如

RemoteDesktop、RealVNC和NetBIOS等。

安全防护软件

给计算机安装一些安全防护软件，也可提高计算机安全性。

常见的有：

1.防病毒软件。为局域网每台计算机安装杀毒软件。

2.防火墙。安装个人防火墙并正确设置它，指定可信程序连

接网络，阻止其它计算机、网络和网址连接计算机。

3.保密管理程序。对保密要求较高的计算机安装专业保密管

理程序，监测该计算机的所有行为，并对数据流出进行限制。

（上接第234页）

码，所以交叉就采用了分段单点交叉策略，具体实现过程为：

随机选择个体使其两个为一组，通过交叉概率Pc和适当的条件

进行交换，产生两个新的个体，其中Pc的选择会影响到算法的

收敛性，如果Pc过大，产生新个体的速度就越快，但是容易使

得优秀个体遭到破坏，而Pc过小，则会使的搜索过程缓慢。

3．变异算子

在对个体进行交叉后，对个体的基因进行基于概率Pm进行

基因变异，这个概率一般较小，对Pm的设置不能过小，如果过

小不易产生新个体，如果过大就变成了纯粹的随机搜索。本文

在交叉的时候采用了分段单点交叉，这里就不进行分段变异了，

而是对整个基因的某段上的某个基因进行变异。通过随机生成

一个[1，n]的随机数r，r作为一个变异位置，然后从题库中选取

一个变异基因，在选取的时候要保证新选择的基因要与原基因

具有相同的题型，相同的分数，相同的考试方向。

遗传算法控制参数设置

[5]

遗传算法的多个参数中交叉概率Pc和变异概率Pm对算法

的影响较大，其中Pc的选择会影响到算法的收敛性，如果Pc

过大，产生新个体的速度就越快，但是容易使得优秀个体遭到

破坏，而Pc过小，则会使的搜索过程缓慢。而Pm的取值的大

小同样影响算法的性能，在保持群体保持多样性的前提下Pm不

能设置过大，如果Pm取值过大，会使算法变为随机搜索，Pm

取值过小，个体的多样性就无法得到满足，从而使得算法陷入

局部最优的状态，而过早收敛。为了避免因为交叉概率和变异

概率取值造成算法性能受到影响，加快遗传算法收敛和有效的

避免其陷入局部最优状态，同时保持较为优良的试卷个体，本

文采取交叉概率 Pc 和变异概率 Pm 的自适应策略，即使得交

定期安全检测

定期对计算机做以下9方面的安全检查可以让用户了解计

算机存在哪些安全隐患。

1．上网记录：检查计算机访问过的网址和访问时间；

2．近期处理过的文件：检查计算机近期处理过的文件；

3．操作系统和补丁信息：检查计算机的操作系统信息和已

安装的补丁包信息；

4．系统用户：检查操作系统的用户、用户权限、用户描述；

5．共享目录：检查操作系统共享的文件夹名称和路径；

6．开放端口：检查操作系统开放的网络端口情况，包括协

议、地址、端口号、状态等；

7．运行进程：检查系统当前运行的进程、进程ID等；

8．系统服务：检查系统的服务名称，服务当前的状态等；

9．USB存储设备：检查系统使用过的所有USB存储设备名

称、类型和硬件编号。

局域网安全是一个很有意义的研究方向，可以解决国家企

事业单位、政府机构、军队、公司企业等内部信息需要保密的

单位对局域网安全的担忧。本文分析了局域网面临哪些安全风

险，从如何设置网络安全策略和局域网计算机安全防护两个方

面研究局域网安全策略，对保护局域网安全提供参考。但是网

络技术飞速发展，黑客攻击手段层出不穷，要筑牢局域网的安

全防线，网络安全技术的发展也要与时俱进。未来发展还有很

多新变化，网络安全的前路还很漫长。

【参考文献】

[1]Yan Ye. Text Image Compression Based on Pattern

Matching[D]. University of California,2002

[2]Kia Omid E, Doermann David S, Rosenfeld Azriel, et al.

Symbolic Compression and Processing of Document Images[J].

Computer Vision and Image Understanding, 1998,70(3):335-349

叉概率 Pc 和变异概率 Pm能够随适应度自动改变，当种群的

个体趋于一致或者陷于局部最优时，交叉概率Pc和变异概率

Pm就增加，当群体适应度比较分撒时，交叉概率 Pc 和变异概

率 Pm就减小。

可以通过实验对Pc和Pm的值进行设定从而取最佳值，通

过实验可以Pc取值范围在0.2～1.0之间时，组卷的成功次数多，

而迭代次数少，在组卷方面呈现先增后减，在迭代次数上呈现

先减后增。Pm取值过大时，组卷的成功率较低，迭代次数增加，

这是由于变异造成的群体中优良的个体遭到了破坏，但是取值

过小产生新个体的速率就会降低，导致种群不能实现多样性。

当种群规模较小时，组卷成功率很低，因为种群的规模本身就

小，这样就不具备多样性的特点，使得算法的搜索空间局限性

很强，出现了未成熟收敛的情况。随着种群规模的提高，算法

的搜索空间加大，这样组卷的成功率也提高，但是平均迭代次

数也会随着种群的提高而提高，这样也会影响算法的效率。

【参考文献】

[1]陈国良、王熙发等，遗传算法及其应用，北京:人民邮电

出版社，2001，1~400

[2]李华山;格雷码的代数结构和分形生成的递归算法[J];北

方工业大学学报;1996年01期

[3]Holland J. Adaptation in Natural and Artifical

Systems[M]．AnnArbor：The University of Michigan Press，1975，

1~50

[4]王小平，曹立明．遗传算法一理论、应用与软件实现

[M]．西安：西安交通大学出版社，2002

[5]刘学增,周敏. 改进的自适应遗传算法及其工程应用[J].

同济大学学报(自然科学版). 2009(03)

236