改进蚁群算法在职业技能鉴定题库管理系统中的应用

潘海云+彭英慧+彭友

摘要：该项目针对职业技能鉴定考核中不同专业、不同工种及不同等级，开发职业技能鉴定题库综合管理系统。利用改进蚁群算法智能组合技能鉴定试卷，解决了组题过程中多目标问题，满足不同群体的职业技能鉴定考核需求；考试试题二次组卷，体现了考试的公平性和公正性。

关键词：职业技能鉴定；自动组题；多目标优化问题

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）08-0007-03

Abstract： this project is aimed at the different profession， the different type of work and the different grade in the appraisal of the professional skill appraisal， and develops the comprehensive management system. Using improved ant colony algorithm intelligent combination of skills identification papers， to solve the multi-objective problem set of problems in the process， meet different groups of vocational skills appraisal and assessment requirements； test second generation， reflecting the test of fairness and justice.

Key words： occupation skill identification； automatic group problem； multi-objective optimization problem

当前，智能组卷系统在教育系统中的应用，为各类用户减少了大量的工作量，解决了许多实际问题。而教育工作者不断提出更高的要求，组卷速度快、试卷题型多样，难度系数适中、涵盖的知识面广，注重考查学生的实践技能和综合素质等。在职业技能鉴定题库管理系统中组卷时间长、速度慢仍是普遍存在的问题，还不能满足职业技能鉴定考核中的需求。所以笔者提出一种基于改进蚁群算法自动组卷策略在职业技能鉴定题库中应用。

1 智能组卷理论研究

任何系统都有一定的指标体系，职业技能鉴定题库也不例外，每个指标体系都有一定的作用，每个参数都有一定的意义，每个指标参数的构建都是为试卷分析、自动组卷、题库管理服务的，这些指标参数实现了优化，基于指标参数的系统也就有一定的优化功能。智能组卷指标参数如下：

1）试卷题型：试卷题型因不同专业、不同工种的用户需求而变化，通常设为5种题型：判断题、单选题、多选题、填空题、综合应用题（或大题）；

2）章节：课程的章节与题库中各种类型的试题间存在对应关系，便于考核和管理；

3）知识点：教学大纲要求需要考核的知识点；

4）答题时间：完成某道试题所占用的时间，指大多数学生做完并检查该题耗费的时间，出题者根据教学经验综合客观情况适当调整；

5）难度系数：难度系统计算公式Pi=1-Ri/n，其中，Ri为该题得分的平均值，pi为试题i的难度系数， n为该题的满分值[1]。在命题时，试题的难度随着考试所针对的对象不同而不同，组卷时，按照组卷设定的难度系数得到符合难度要求的试卷。

由于被测对象不同、工种不同等因素变化对难度系统影响较大，所以不同对象、不同工种考核时更要科学、客观地确定难度系数。除了参考以上算式，还要结合出题人员的教学经验、考核对象进行调整，将难度系数模糊为下表列出的三个等级。一般情况下，试卷的平均难度系数大约控制在0.5，只有这样试卷分数的分布才基本呈正态分布，符合自然规律，考试成绩才具有参考价值[1]。

[难度等级＼&简单题＼&中等题＼&较难题＼&难度区间＼&0.0-0.3＼&0.3-0.7＼&0.7-1.0＼&模糊化＼&0.2＼&0.5＼&0.8＼&]

2 职业技能鉴定题库管理系统功能模块介绍

职业技能鉴定题库管理系统中应开发的功能为：

1）人员管理模块：主要用来对用户信息、各种角色以及系统使用权限等进行管理。

2）试卷管理模块：主要根据考核大纲要求，设置题型、数量、难度系数并结合相关智能组卷算法自动组卷，并对生成的试卷进行编辑等操作。

3）题库管理模块：对历年来生成的试卷进行评估。分析考试情况，对题库中的试题类型、数量、难度系数等信息进行修正，为以后的智能组卷提供依据。

4）考试模块：主要实现考生根据考号和密码登录系统进行考试等功能，为了体现考试的公平性，对同一试卷在保证答题结构、顺序合理的情况下进行二次组卷。

5）阅卷管理模块：主要实现考生提交试卷的评阅功能，包括对客观题系统自动评判和主观题人工评判两部分。

6）成绩管理模块：该模块中，学生可以查询分数，管理人员可以查看、分析、汇总、导入、导出成绩等操作功能。

3 职业技能鉴定题库自动组卷问题的数学建模

在职业技能鉴定题库管理系统自动组卷算法中，设试卷总分为M，试题总数为N，每套试卷的考试时间为T分钟，试卷内容由n部分组成，各部分内容试题分数比为n1n2...nn；试卷中要考核的知识点包括m类，各类知识点所包含试题的分数比是m1m2...mm；题库中试题的难度级别共有P个，试卷中每个难度级别试题的分数比为p1p2...pp；试卷中包含q种题型，则各个题型的分数比为q1q2...qq，具体数学模型如下：

3.1 改进的蚁群算法基本思想

蚁群算法主要是模拟蚂蚁群落寻找食物过程，蚂蚁之间的协作是蚁群算法中最关键的因素。蚁群算法依据蚁群的集体寻优特征搜索食物和蚁穴之间的路径，在寻找食物时蚂蚁会在路径上散发信息素，这些信息素会被陆陆续续经过本路径的蚂蚁获取到，然后蚂蚁根据不断获取到的信息素选择最佳路径。每只蚂蚁简单的散发信息素、自行选择路径，随着信息素的不断积累，通过蚁群之间的协作多次寻找最后可选择一条最优路径[2]。目前，蚁群算法解决了最优解问题，但职业技能鉴定题库组卷问题是一个多目标寻优问题，同时还要保证试题题型多样、涵盖的知识面广、重复性不能过高，因此，根据职业技能鉴定题库管理系统的实际需求，改进和优化蚁群算法，将信息素的积累从被考试过的题目次数转移到降低被考过试题的信息素来增加其他试题的信息素，从而增加未考过的试题被选中的概率[3]。

3.2 改进后的蚁群算法实现

在基于蚁群算法的职业技能鉴定题库自动组卷算法中，在试题库中，每只蚂蚁从一个试题节点移动到另一个试题节点，不断地寻找路径，当蚁群中的所有蚂蚁都能够走到路径的终点时，相应的就组成了一套试卷。我们可以把组卷过程构造为一个有向图，假设试题库中有N道题，则该问题可以看成一个有N个节点和N*（N-1）边的完全有向图，记作G（V，E），其中V表示试题库中的试题节点（试题库中试题的数量），E表示连接节点的边[2]。

3.3 蚂蚁选择路径的方法

随机生成试题节点M个并放置蚂蚁M只，给出路径的信息素量以及启发因子，每只蚂蚁会根据路径上的信息素量自主选择合适的有向线段并移动到下一个试题节点。按上述过程不断地重复，直到约束条件满足为止，在t时刻，蚂蚁k（k=1，2，…m）从节点i（i=1，2，…，L）经过路径a[i，j]到节点i+1的转移概率Pkij（t）为：

JK（i）表示位于节点i的蚂蚁k当前能选择的有向线段组合，ηij表示蚂蚁选择有向线段a[i，j]的期望程度，α和β表示蚂蚁k在进行路径选择时，有向线段a[i，j]上的信息素量和启发因子的重要程度[2]。

3.4 信息素的更新

表示本次循环中有向线段a[i，j]上信息素的增量，也即第k只蚂蚁在a[I，j]上留下的信息素量。

3.5 二次组卷功能的实现

为了保证在线考试的公平性，本文还采用一种二次组卷分发策略，将原始试卷中的试题在保证答题结构顺序合理的情况下随机打乱进行二次重组后分发给考生。这样使得考生考试内容虽相同但试卷试题顺序不同。从而避免抄袭现象，进而体现了考试的公正和公平。

对于一份n道试题组成的试卷，将试卷按题型顺序打乱，程序流程图1所示。

对原始试卷的不同题型下的试题顺序打乱并重新组卷分发在考试中的作用非常重要，既保证了同一时间参加考试的全部考生同一试卷，又保证了试卷的题型结构合理、答题顺序符合做题习惯，更重要的是整个考场内相邻考生的试题顺序截然不同，充分体现了考试的公平性和公正性[4]。

4 系统实现

在Microsoft visual studio 2010环境下，采用Sql server 2005数据库管理系统存储数据信息，实现了职业技能鉴定题库管理系统，对机械钳工、机械车工、汽车维修工、汽车装配工等多种工种的职业技能鉴定试卷的生成。其中试题库中有判断题、单选题、填空题、多选题和综合题每种题型各50答题，经过具体的实验模拟，发现该算法能够在一定时间内找到最优解，能够自动生成难易适中，学生考试成绩比较理想的试卷。

参考文献：

[1] 韩英慧. 改进的遗传算法在智能组卷系统中的应用[J].长春教育学院学报，2015（4）.

[2] 刘燕茹，李丽娜. 蚁群算法在计算机自动组卷中的应用研究[J].研究与开发，2014（5）.

[3] 廖金权. 一种基于改进蚁群算法的考试系统的研究[J].软件杂志，2014（5）.

[4] 贺荣，陈爽. 在线组卷策略的研究与设计[J].计算机工程与设计，2011（12）.