基于遗传算法智能组卷的研究与应用
|
摘要
近几年，智能优化算法倍受人们关注，如人工神经网络、遗传算法，为解决复杂问题提供了新的方法，并在诸多领域取得了成功。组卷问题是一个在一定约束条件下的多目标参数优化问题，针对传统的组卷算法具有组卷速度慢、成功率较低、试卷质量不高等缺点。本文着重研究遗传算法在组合优化中的应用，为了避免简单遗传算法收敛速度慢以及局部收敛的问题，引入了一种改进遗传算法。该算法利用不断淘汰相似个体，并不断补充新个体的方法，达到了扩大搜索空间，稳定群体的个体多样性目的。通过详细分析试卷的各项约束条件如知识点、难度系数、区分度，建立了一个智能组卷数学模型，利用改进的遗传算法实现了智能组卷。改进后的遗传算法采用分段实数编码，把同一题型的试题放在同一段，组成试卷的各道试题的题号直接映射为基因，用实数编码避免解码过程，提高了运算效率，而且交叉和变异操作都在各段内部进行，因此可以保证组卷过程中各题型题量的正确匹配，还要保证同一题型知识点不重复。对适应度函数设计，调整了强度约束的权值。
根据需求分析，对系统进行了四个功能模块的设计。这四个功能模块分别是题库管理模块、试卷生成模块、成绩分析模块和系统维护模块。组卷模块是系统的核心，在组卷模块中组卷方式有三种：人工组卷、自动组卷、向导组卷。可以直接生成的Word形式试卷以及试卷答案，在Word中可以对试卷以及试卷答案进行编辑修改并打印出来。成绩分析模块除具有学生成绩进行统计分析功能外，还能通过成绩分析结果对题库中试题属性进行更新。实验结果表明，新方法的组卷成功率和收敛速度都得到明显提高，并且较好地克服了未成熟收敛现象，只要试题库中的试题数量适中，试题类型完备，分布合理，由该算法产生的试卷就能满足用户的各项需求指标。
The optimization algorithm becomes popular in the recent years, such as theartificial neural network and genetic algorithms etc. It provides as a new method toresolve complicated problems and gains success in lots of fields, auto-generatingexamination paper is a constrained multi-object optimization problem. Traditionalalgorithms of composing test paper have the disadvantages of slow convergence,lowsuccess rate and quality. This paper mainly studies the use of GA in the Combinationoptimization. In order to avoid slow convergence and local convergence of simplegenetic algorithm (SGA)for intelligent test paper generation, a kind of improvedgenetic algorithm (IGA) has been proposed in this paper. This algorithm usesunceasing elimination of similar individual method to quickly enlarge the searchspace and to stabilize the individual diversity of the group, n this article a new methodof composing test paper based on the improved genetic algorithm is given.. After acareful Analysis of each binding condition in the test paper, we have set up amathematical model for automatic test paper-making based on knowledge point,difficulty factor, distinguishing degree, etc. and have realized automatic testpaper-making with improved genetic algorithm. Improved genetic algorithm adoptssegment real number code, putting the question of the same type on the same section,and then the question number maps gene directly. Real number code avoid decodingprocedure, it may enhance operation efficiently. In addition, crossover and mutationoperation conduct in the interior of each section, it may guarantee the quantity of eachtype correct matching and different knowledge point of the question of the same typein the process of test paper-making. The fitness function is designed, the weights ofstronger Constraint conditions are enlarged.
According to the functional demand of intelligent Test Paper system, we havedesigned four functional modules: examination database, test paper-generation, gradeanalysis and system setup. Test paper generation module is the core of the system, itincludes three ways of test paper-making: manual, guide and automatic. Test paper aswell as its answers can be sent directly into Microsoft Office Word,in which testpaper as well as its answers are edited, revised and printed out. Grade analysis modulecan analyze the student grades statistically and update each binding condition thequestion in examination database by analyzing grade. The new method is moreefficient and easier to get over premature convergence than the traditional algorithms. It is proved by a number of experiments provided by this article, the test paper formed by the algorithm meets all the users' requirements if the quantity of test questionsis moderate and reasonable.
根据需求分析，对系统进行了四个功能模块的设计。这四个功能模块分别是题库管理模块、试卷生成模块、成绩分析模块和系统维护模块。组卷模块是系统的核心，在组卷模块中组卷方式有三种：人工组卷、自动组卷、向导组卷。可以直接生成的Word形式试卷以及试卷答案，在Word中可以对试卷以及试卷答案进行编辑修改并打印出来。成绩分析模块除具有学生成绩进行统计分析功能外，还能通过成绩分析结果对题库中试题属性进行更新。实验结果表明，新方法的组卷成功率和收敛速度都得到明显提高，并且较好地克服了未成熟收敛现象，只要试题库中的试题数量适中，试题类型完备，分布合理，由该算法产生的试卷就能满足用户的各项需求指标。
The optimization algorithm becomes popular in the recent years, such as theartificial neural network and genetic algorithms etc. It provides as a new method toresolve complicated problems and gains success in lots of fields, auto-generatingexamination paper is a constrained multi-object optimization problem. Traditionalalgorithms of composing test paper have the disadvantages of slow convergence,lowsuccess rate and quality. This paper mainly studies the use of GA in the Combinationoptimization. In order to avoid slow convergence and local convergence of simplegenetic algorithm (SGA)for intelligent test paper generation, a kind of improvedgenetic algorithm (IGA) has been proposed in this paper. This algorithm usesunceasing elimination of similar individual method to quickly enlarge the searchspace and to stabilize the individual diversity of the group, n this article a new methodof composing test paper based on the improved genetic algorithm is given.. After acareful Analysis of each binding condition in the test paper, we have set up amathematical model for automatic test paper-making based on knowledge point,difficulty factor, distinguishing degree, etc. and have realized automatic testpaper-making with improved genetic algorithm. Improved genetic algorithm adoptssegment real number code, putting the question of the same type on the same section,and then the question number maps gene directly. Real number code avoid decodingprocedure, it may enhance operation efficiently. In addition, crossover and mutationoperation conduct in the interior of each section, it may guarantee the quantity of eachtype correct matching and different knowledge point of the question of the same typein the process of test paper-making. The fitness function is designed, the weights ofstronger Constraint conditions are enlarged.
According to the functional demand of intelligent Test Paper system, we havedesigned four functional modules: examination database, test paper-generation, gradeanalysis and system setup. Test paper generation module is the core of the system, itincludes three ways of test paper-making: manual, guide and automatic. Test paper aswell as its answers can be sent directly into Microsoft Office Word,in which testpaper as well as its answers are edited, revised and printed out. Grade analysis modulecan analyze the student grades statistically and update each binding condition thequestion in examination database by analyzing grade. The new method is moreefficient and easier to get over premature convergence than the traditional algorithms. It is proved by a number of experiments provided by this article, the test paper formed by the algorithm meets all the users' requirements if the quantity of test questionsis moderate and reasonable.
引文
[1] 田生伟，禹龙．智能组卷与评价系统在高校重点课程建设的应用[J]．计算机工程，2004，(4)173-175
[2] 赵化桥，尹香莲．高等化学试题库应用于教学质量评估初探[J]．教育与现代化，1996，27(2)：56—58
[3] 周明，孙树东．遗传算法原理及应用[M]．北京：国防工业出版社，1999
[4] 陈国良，王煦法．遗传算法及其应用[M]．北京：人民邮电出版社，1999
[5] NMS J W, SMITH R E. Application of a genetic algorithm to power transformer design[J]. Electric Machines and Power Systems, 1995, 24(10): 669-680
[6] Gal ante M. Genetic algorithms as an approach to optimize real-world trusses[J] .International Journal for Numerical Methods in Engineering, 1996,39(1):124-129
[7] A. Sena Giuseppe, D.Megherbi, I.Germinal. Implementation of a Parallel Genetic Algorithm on a Cluster of Workstations:Traveling Salesman Problem[J]. a Case Study,2001,17:477-488
[8] H.Barbosa, C C.Lemonge Afonso. A New Adaptive Penalty Scheme for Genetic Algorithms[J].Information Sciences, 2003,156(3-4):215-251
[9] 张铃，张博．遗传算法机理的研究[J]．软件学报，2000，11(7)：945-952
[10] 杨路明，陈大鑫．改进遗传算法在试题自动组卷中的应用研究[J]．计算机与数字工程，2004，(5)76-79
[11] 文忠林，蔡清万，李元香．试题库智能组卷的遗传算法[J]．湖北民族学院学报(自然科学版)2000(8)：53-55
[12] 金惠云，范围闯，赵霆雷．基于遗传算法的试题库智能组卷系统研究[J]．武汉大学学报：自然科学版，1999；56(5)：58—60
[13] 梁春媚．自动绢卷系统的优化及智能实现[J]．科技论坛，2005，(15)：94-95
[14] 董敏，霍剑青，王晓蒲．基于自适应遗传算法的智能组卷研究[J]．小型微型计算机系统，2004，1：82-85
[15] 魏平，张元．一种求解组卷问题的遗传算法[J]．宁波大学学报：理工版，2002；15(2)：47—50
[16] 毛秉毅．一种计算试卷中试题难度分布的有效方法[J]．计算机工程，2002；28(6)：280—281
[17] 刘彬，李勇，糜长军．智能组卷系统中专家知识的表示与实现[J]．计算机工程与应用，2002：38(17)：229—231
[18] 魏平，干海光，熊伟清．基于进化稳定策略的单亲遗传算法求解组卷问题[J]．微电子学与计算机，2005；22(1)：105—109
[19] 袁慧梅．具有自适应交换率和变异率的遗传算法[J]．首都师范大学学报：自然科学版，2000，21(3)：14-20．
[20] 石中盘，韩卫．基于概率论和自适应遗传算法的智能抽题算法[J]．计算机工程，2002(1)：141-143
[21] 袁锋．遗传算法在自动组卷系统中的应用[J]．山东师范大学学报(自然科学版)．2006，1：53-56
[22] 李莉，陈未如，王翠青等．通用试题库管理系统的研究与实现[J]．沈阳华工学院学报，2005，19(3)：236-240
[23] Mashhadi H,Shane chi H M, Lucas C A. New genetic algorithm with Lamarckian individual learning for generation scheduling [J]. IEEE Transactions on Power Systems,2003,18(3): 1181-1186
[24] 周红晓．试题库组卷系统的研究与实现[D]．金华市：浙江师范大学，2003．
[25] 许艳．试卷辅助生成系统的设计与实现[D]．武汉市：华中科技大学，2006．
[26] 蒋丽芳．基于Web的网络考试系统的设计与实现[D]．广州市：华南理工大学，2005。
[27] 杨小萍．基于JavaXML的三级网络教学平台下网络考试系统的研究与实现[D]．兰州市：西北师范大学，2005
[28] 王友仁，张砦，崔江等．智能组卷系统的建模与算法研究[J]．系统工程理论与实践，2004(9)：85-89．
[29] A. Sena Giuseppe, D.Megherbi, I.Germinal. Implementation of a Parallel Genetic Algorithm on a Cluster of Workstations [J]: Traveling Salesman Problem, a Case Study,2001.17(4):477-488
[30] H.Barbosa, C C.Lemonge Afonso. A New Adaptive Penalty Scheme for Genetic Algorithms [J]. Information Sciences, 2003,156(3-4): 215-251
[31] C.Smith Greg, S.Smith Shana. An Enhanced Genetic Algorithm for Automated Assembly planning [J]. Robotics and Computer Integrated Manufacturihg,2002,18 (5-6):355—364
[32] Louis, J.Sushil, Li Gong. Case Injected Genetic Algorithms for Traveling Salesman Problems [J]. Information Sciences, 2000,122(2-4): 201-225
[33] T.Lynda, C.Chrisment,Boughanem Mohand. Multiple Query Evaluation Based on Enhanced Genetic Algorithm [J]. Information Processing and Management, 2003, 39(2):215 231
[34] J.Andre, P.Siarry, T.Dognon. An Improvement of the Standard Genetic Algorithm Fighting Premature Convergence in Continuous Optimization [J]. Advances in Engineering Software, 2001,32(1): 49-60
[35] A Tuson,P Ross.Adapting Operator Setings in Genetic Algorithms [J]. Evolutionary Computation, 1998,6(2): 161-184
[36] Mashhadi H R ,Shane chi H M, Lucas C A. New genetic algorithm with Lamarckian individual learning for generation scheduling [J]. IEEE Transactions on Power Systems,2003,18(3): 1181-1186
[37] Radolph G. Convergence analysis of canonical genetic algorithms [J]. IEEE Transactions on Neural Network, 1994,5 (1): 96-101
[38] 陆亿红，柳红．基于整数编码和自适应遗传算法的自动组卷[J]．计算机工程，2005(12)：232-233
[39] 闭应洲，苏德富，陈宁江．基于矩阵编码的遗传算法及其在自动组卷中的应用[J]．计算机工程，2003，29(6)：73-76
[40] 钟求喜，解涛，陈火旺．任务分配与调度中的遗传算法：知识表示与遗传算子研究．计算机科学．，2000，27(6)：46-49
[41] 于洋，查建中，唐晓君．基于学习的遗传算法及其在布局中的应用．计算机学报．，2001，24(12)：1242-1249
[42] 王煦法．张显俊等．一种基于免疫原理的遗传算法[J]小型微型计算机系1999，20(2)：117-120．
[43] 徐金梧,刘纪文。基于小生境技术的遗传算法[J]。模式识别与人工智能.1999,12(1):104-107
[44] M. Srinivas, L. M. Patnaik. Adaptive probabilities of crossover and mutation in genetic algorithm[J]. IEEE Transaction on Systems, Man and Cybernetics.1994,24(4):656-666.
[45]. Herrera, M. Lozano, J.L. Verdegay, Fuzzy Connectives Based Crossover Operators to Model Genetic Algorithms Population Diversity[J]. Fuzzy Sets and System, 1997.
[2] 赵化桥，尹香莲．高等化学试题库应用于教学质量评估初探[J]．教育与现代化，1996，27(2)：56—58
[3] 周明，孙树东．遗传算法原理及应用[M]．北京：国防工业出版社，1999
[4] 陈国良，王煦法．遗传算法及其应用[M]．北京：人民邮电出版社，1999
[5] NMS J W, SMITH R E. Application of a genetic algorithm to power transformer design[J]. Electric Machines and Power Systems, 1995, 24(10): 669-680
[6] Gal ante M. Genetic algorithms as an approach to optimize real-world trusses[J] .International Journal for Numerical Methods in Engineering, 1996,39(1):124-129
[7] A. Sena Giuseppe, D.Megherbi, I.Germinal. Implementation of a Parallel Genetic Algorithm on a Cluster of Workstations:Traveling Salesman Problem[J]. a Case Study,2001,17:477-488
[8] H.Barbosa, C C.Lemonge Afonso. A New Adaptive Penalty Scheme for Genetic Algorithms[J].Information Sciences, 2003,156(3-4):215-251
[9] 张铃，张博．遗传算法机理的研究[J]．软件学报，2000，11(7)：945-952
[10] 杨路明，陈大鑫．改进遗传算法在试题自动组卷中的应用研究[J]．计算机与数字工程，2004，(5)76-79
[11] 文忠林，蔡清万，李元香．试题库智能组卷的遗传算法[J]．湖北民族学院学报(自然科学版)2000(8)：53-55
[12] 金惠云，范围闯，赵霆雷．基于遗传算法的试题库智能组卷系统研究[J]．武汉大学学报：自然科学版，1999；56(5)：58—60
[13] 梁春媚．自动绢卷系统的优化及智能实现[J]．科技论坛，2005，(15)：94-95
[14] 董敏，霍剑青，王晓蒲．基于自适应遗传算法的智能组卷研究[J]．小型微型计算机系统，2004，1：82-85
[15] 魏平，张元．一种求解组卷问题的遗传算法[J]．宁波大学学报：理工版，2002；15(2)：47—50
[16] 毛秉毅．一种计算试卷中试题难度分布的有效方法[J]．计算机工程，2002；28(6)：280—281
[17] 刘彬，李勇，糜长军．智能组卷系统中专家知识的表示与实现[J]．计算机工程与应用，2002：38(17)：229—231
[18] 魏平，干海光，熊伟清．基于进化稳定策略的单亲遗传算法求解组卷问题[J]．微电子学与计算机，2005；22(1)：105—109
[19] 袁慧梅．具有自适应交换率和变异率的遗传算法[J]．首都师范大学学报：自然科学版，2000，21(3)：14-20．
[20] 石中盘，韩卫．基于概率论和自适应遗传算法的智能抽题算法[J]．计算机工程，2002(1)：141-143
[21] 袁锋．遗传算法在自动组卷系统中的应用[J]．山东师范大学学报(自然科学版)．2006，1：53-56
[22] 李莉，陈未如，王翠青等．通用试题库管理系统的研究与实现[J]．沈阳华工学院学报，2005，19(3)：236-240
[23] Mashhadi H,Shane chi H M, Lucas C A. New genetic algorithm with Lamarckian individual learning for generation scheduling [J]. IEEE Transactions on Power Systems,2003,18(3): 1181-1186
[24] 周红晓．试题库组卷系统的研究与实现[D]．金华市：浙江师范大学，2003．
[25] 许艳．试卷辅助生成系统的设计与实现[D]．武汉市：华中科技大学，2006．
[26] 蒋丽芳．基于Web的网络考试系统的设计与实现[D]．广州市：华南理工大学，2005。
[27] 杨小萍．基于JavaXML的三级网络教学平台下网络考试系统的研究与实现[D]．兰州市：西北师范大学，2005
[28] 王友仁，张砦，崔江等．智能组卷系统的建模与算法研究[J]．系统工程理论与实践，2004(9)：85-89．
[29] A. Sena Giuseppe, D.Megherbi, I.Germinal. Implementation of a Parallel Genetic Algorithm on a Cluster of Workstations [J]: Traveling Salesman Problem, a Case Study,2001.17(4):477-488
[30] H.Barbosa, C C.Lemonge Afonso. A New Adaptive Penalty Scheme for Genetic Algorithms [J]. Information Sciences, 2003,156(3-4): 215-251
[31] C.Smith Greg, S.Smith Shana. An Enhanced Genetic Algorithm for Automated Assembly planning [J]. Robotics and Computer Integrated Manufacturihg,2002,18 (5-6):355—364
[32] Louis, J.Sushil, Li Gong. Case Injected Genetic Algorithms for Traveling Salesman Problems [J]. Information Sciences, 2000,122(2-4): 201-225
[33] T.Lynda, C.Chrisment,Boughanem Mohand. Multiple Query Evaluation Based on Enhanced Genetic Algorithm [J]. Information Processing and Management, 2003, 39(2):215 231
[34] J.Andre, P.Siarry, T.Dognon. An Improvement of the Standard Genetic Algorithm Fighting Premature Convergence in Continuous Optimization [J]. Advances in Engineering Software, 2001,32(1): 49-60
[35] A Tuson,P Ross.Adapting Operator Setings in Genetic Algorithms [J]. Evolutionary Computation, 1998,6(2): 161-184
[36] Mashhadi H R ,Shane chi H M, Lucas C A. New genetic algorithm with Lamarckian individual learning for generation scheduling [J]. IEEE Transactions on Power Systems,2003,18(3): 1181-1186
[37] Radolph G. Convergence analysis of canonical genetic algorithms [J]. IEEE Transactions on Neural Network, 1994,5 (1): 96-101
[38] 陆亿红，柳红．基于整数编码和自适应遗传算法的自动组卷[J]．计算机工程，2005(12)：232-233
[39] 闭应洲，苏德富，陈宁江．基于矩阵编码的遗传算法及其在自动组卷中的应用[J]．计算机工程，2003，29(6)：73-76
[40] 钟求喜，解涛，陈火旺．任务分配与调度中的遗传算法：知识表示与遗传算子研究．计算机科学．，2000，27(6)：46-49
[41] 于洋，查建中，唐晓君．基于学习的遗传算法及其在布局中的应用．计算机学报．，2001，24(12)：1242-1249
[42] 王煦法．张显俊等．一种基于免疫原理的遗传算法[J]小型微型计算机系1999，20(2)：117-120．
[43] 徐金梧,刘纪文。基于小生境技术的遗传算法[J]。模式识别与人工智能.1999,12(1):104-107
[44] M. Srinivas, L. M. Patnaik. Adaptive probabilities of crossover and mutation in genetic algorithm[J]. IEEE Transaction on Systems, Man and Cybernetics.1994,24(4):656-666.
[45]. Herrera, M. Lozano, J.L. Verdegay, Fuzzy Connectives Based Crossover Operators to Model Genetic Algorithms Population Diversity[J]. Fuzzy Sets and System, 1997.