基于遗传算法的自动组卷系统研究与实现
摘要
组卷问题是一个在一定约束条件下的多目标参数优化问题,采用传统的数学方法求解十分困难,自动组卷的效率和质量完全取决于试题库设计以及抽题算法的设计。如何设计一个算法从试题库即快又好的抽出一组最符合考试要求的试题,是本文研究的目的。在对国内外大量相关文献分析研究的基础上,本文选择遗传算法作为组卷算法,设计了一种具有通用性的组卷系统。该系统能够按照试题类型、试题数量、知识点、难度系数、区分度、曝光度、最近出题时间、答题时间等约束条件进行快速搜索,从而找到最佳组卷方案,组出理想的试卷。
在组卷系统研究的过程中,本文对传统组卷过程进行了分析,形成了组卷问题的数学模型,并在教育测量和教育统计理论的基础上设计了试题库结构。基于该数学模型,本文建立了按试题类型分组的组卷思想,经试验比较,分组组卷算法搜索速度明显优于不分组时的情况,本文给出了试验的数据。在组卷系统研究的过程中,本文对经典遗传算法从多方面进行改进,并利用C#编程将算法应用于实践。通过实践不仅验证了本文提出的理论的正确性,还对具体组卷实际中遇到的困扰进行了较为合理的解决,使系统可以在实际中应用。总之,本研究主要的工作可以归纳为以下几点:
1.通过分析组卷策略,建立了组卷问题数学模型,并对模型进行简化处理。
2.采用ADO.NET技术,将试题库按题型分割为几个分库表,并将分库表存放于计算机内存中,组卷时既减小了算法的搜索范围,又减少了访问硬盘的时间。
3.改进遗传算法采用分组自然数编码,减少了染色体长度空间,编码直接采用试题编号,省去了编码和解码的繁琐。
4.运用自适应理论改进交叉概率及变异概率,算法本身总能找到适合于自己得交叉概率和变异概率。引入“遗传——灾变”算法使变异概率在监测到染色体有“早熟”倾向时,会自动突变其值,发生灾变,增加变异的机会,使种群跳出“早熟”。
5.选择算子采用模拟小生境的方法,其基本做法是:当新产生的子代个体的适应度超过其父代个体的适应度时,所产生的子代个体才能代替其父代个体而遗传到下一代种群中,否则父代个体仍保留在下一代种群中。由于子代个体和父代个体之间编码结构具有相似性,所以替换掉的只是一些编码结构相似的个体,故它能够有效地维持种群的多样性,从而避免产生局部最优解,改善未成熟收敛。
6.解决了在实际组卷中遇到的试卷中试题的分值分配问题,研究了对选择题、填空题和问答题的难度和答题时间的调整策略。
7.利用C#.net编程实现了基于上述改进的遗传算法自动组卷系统,文中给出了主要界面和部分关键源代码。
The test paper generating is an optimized problem to multi-objective parameter with certain restriction. The optimization is implemented very difficultly by traditional method. The quality and efficiency of auto-generating test paper is all determined by the test questions-database designs and get problems-terms algorithm. The aim of the research is to design an algorithm that can get a group of test problems terms quickly, which fit the restriction of test requirement. A great deal of articles from inside and outside analyzed, Genetic Algorithm is selected as the way to produce test paper, and a general-purpose system of auto-generating test paper is designed. The system can search for the best answer according to such restriction conditions as test question types, terms scalar, knowledge points, difficulty degree, distinguish, exposition, the latest time and answer time. Finally, it can find the best answer and get ideal test paper.In this research, traditional test generate steps is analyzed, and a suitable mathematics model about generating test paper is formed, and the structure of test questions-database base on education measure theory is designed and education statistics is built. According to the mathematics model, a producing test idea that the test questions are grouped base on their types has been built. Through testing proved, the grouping method is more advantage than that of no-grouping method, some relation data about these testing have been provided. In this thesis, the traditional genetic algorithm have been improved at many aspects, and the author made a program of testing system using c#. The testing system not only proved that the article's theory is correct, but also many practical problems in generating test paper have been resolved perfectly. These work make the generating test paper system have a good effect in practice. In a word, the main work of the research can be show as follows:1. Establish a model of generating test paper problem and simplify it.2. Using ADO.NET technique, the test library will be divided into several tables base on different types so that searching scope can be decreased and reading hard-disk time can be cut down.
3. The national code is used in the improved genetic algorithm in order to decrease space of chromosomes.4. The crossover probability and mutation probability are improved on self-proper theory, so that the proper numbers of crossover probability and mutation probability can be found. The Genetic-Mutation Algorithm is introduced. When the premature phenomena trend has been detected, the number of mutation probability can be changed to enhance mutation chances, and to run out premature.5. Simulated Niche is introduced in the selection operator, its rules as follow: when the filial generation's fitness is better than those of their father generation, the filial generation instead of their father generation, otherwise, the father generation is remained. It can maintain multi-seeds effectively and avoid to run into the trap of the part best value.6. The problem of test questions' mark in application has been resulted, the timing adjusted strategy has been researched about selection terms, blank terms and ask terms.7. The auto-generating test paper system based on improved genetic algorithm has been achieved using C#. In this thesis, some main interfaces and code are provided.
在组卷系统研究的过程中,本文对传统组卷过程进行了分析,形成了组卷问题的数学模型,并在教育测量和教育统计理论的基础上设计了试题库结构。基于该数学模型,本文建立了按试题类型分组的组卷思想,经试验比较,分组组卷算法搜索速度明显优于不分组时的情况,本文给出了试验的数据。在组卷系统研究的过程中,本文对经典遗传算法从多方面进行改进,并利用C#编程将算法应用于实践。通过实践不仅验证了本文提出的理论的正确性,还对具体组卷实际中遇到的困扰进行了较为合理的解决,使系统可以在实际中应用。总之,本研究主要的工作可以归纳为以下几点:
1.通过分析组卷策略,建立了组卷问题数学模型,并对模型进行简化处理。
2.采用ADO.NET技术,将试题库按题型分割为几个分库表,并将分库表存放于计算机内存中,组卷时既减小了算法的搜索范围,又减少了访问硬盘的时间。
3.改进遗传算法采用分组自然数编码,减少了染色体长度空间,编码直接采用试题编号,省去了编码和解码的繁琐。
4.运用自适应理论改进交叉概率及变异概率,算法本身总能找到适合于自己得交叉概率和变异概率。引入“遗传——灾变”算法使变异概率在监测到染色体有“早熟”倾向时,会自动突变其值,发生灾变,增加变异的机会,使种群跳出“早熟”。
5.选择算子采用模拟小生境的方法,其基本做法是:当新产生的子代个体的适应度超过其父代个体的适应度时,所产生的子代个体才能代替其父代个体而遗传到下一代种群中,否则父代个体仍保留在下一代种群中。由于子代个体和父代个体之间编码结构具有相似性,所以替换掉的只是一些编码结构相似的个体,故它能够有效地维持种群的多样性,从而避免产生局部最优解,改善未成熟收敛。
6.解决了在实际组卷中遇到的试卷中试题的分值分配问题,研究了对选择题、填空题和问答题的难度和答题时间的调整策略。
7.利用C#.net编程实现了基于上述改进的遗传算法自动组卷系统,文中给出了主要界面和部分关键源代码。
The test paper generating is an optimized problem to multi-objective parameter with certain restriction. The optimization is implemented very difficultly by traditional method. The quality and efficiency of auto-generating test paper is all determined by the test questions-database designs and get problems-terms algorithm. The aim of the research is to design an algorithm that can get a group of test problems terms quickly, which fit the restriction of test requirement. A great deal of articles from inside and outside analyzed, Genetic Algorithm is selected as the way to produce test paper, and a general-purpose system of auto-generating test paper is designed. The system can search for the best answer according to such restriction conditions as test question types, terms scalar, knowledge points, difficulty degree, distinguish, exposition, the latest time and answer time. Finally, it can find the best answer and get ideal test paper.In this research, traditional test generate steps is analyzed, and a suitable mathematics model about generating test paper is formed, and the structure of test questions-database base on education measure theory is designed and education statistics is built. According to the mathematics model, a producing test idea that the test questions are grouped base on their types has been built. Through testing proved, the grouping method is more advantage than that of no-grouping method, some relation data about these testing have been provided. In this thesis, the traditional genetic algorithm have been improved at many aspects, and the author made a program of testing system using c#. The testing system not only proved that the article's theory is correct, but also many practical problems in generating test paper have been resolved perfectly. These work make the generating test paper system have a good effect in practice. In a word, the main work of the research can be show as follows:1. Establish a model of generating test paper problem and simplify it.2. Using ADO.NET technique, the test library will be divided into several tables base on different types so that searching scope can be decreased and reading hard-disk time can be cut down.
3. The national code is used in the improved genetic algorithm in order to decrease space of chromosomes.4. The crossover probability and mutation probability are improved on self-proper theory, so that the proper numbers of crossover probability and mutation probability can be found. The Genetic-Mutation Algorithm is introduced. When the premature phenomena trend has been detected, the number of mutation probability can be changed to enhance mutation chances, and to run out premature.5. Simulated Niche is introduced in the selection operator, its rules as follow: when the filial generation's fitness is better than those of their father generation, the filial generation instead of their father generation, otherwise, the father generation is remained. It can maintain multi-seeds effectively and avoid to run into the trap of the part best value.6. The problem of test questions' mark in application has been resulted, the timing adjusted strategy has been researched about selection terms, blank terms and ask terms.7. The auto-generating test paper system based on improved genetic algorithm has been achieved using C#. In this thesis, some main interfaces and code are provided.
引文
[1] 马华东.《多媒体媒体计算机技术原理》.北京:清华大学出版社.1999:1-55.
[2] 宋云娴,白鹏.《智能教学系统设计与实现》[M].北京:电子工业出版社.1995:24-45
[3] 李更明,卢伟清.计算机公共课机考软件的设计与实现.《福建师范大学学报》(自然科学版)第19卷第2期2003.6 106-109.
[4] 毛秉毅.基于遗传算法的智能组卷系统数据库结构的研究.《计算机工程与应用》.2003.6:230-232
[5] 吴泽晖.基于ASP开发的网上组卷考试系统.《微型机与应用》.2000年19卷9期:51-53
[6] 金汉均,郑世珏,吴明武.分段随机抽选法在智能组卷中的研究与应用.《计算机应用研究》 2003年20卷9期:102-103,126
[7] 张国才,徐效美。基于分割策略的快速抽题组卷算法《微计算机应用》.2003年24卷4期:197-199
[8] 陈华光,周铁山,张晓清.通用试题库系统的设计与实现.《湖南工程学院学报》.自然科学版.2002年12卷3期:32-34
[9] 林健,闫华,武兵计算机自适应考试理论分析.《太原理工大学学报》.2004年35卷2期:221-224
[10] 吴锦林,吴清锋.分布式计算机应用水平考试系统的设计与实现.《计算机工程与设计》.2003年24卷3期:52-54
[11] 张亮,陆剑峰,张浩.基于PHP平台的网络考试系统开发与研究.《微型电脑应用》.2003年19卷7期:26-28
[12] 戴亚非,李晓明.计算机自动组卷算法分析.《小型微型计算机系统》.1995年16卷9期:51-55
[13] 朱明,王俊普.一种智能组卷方法的研究与实现.《微小型计算机开发与应用》.1997年4期:5-9
[14] 刘彬,糜长军.智能组卷系统试题库结构的研究《信息技术(哈尔滨)》2002年3期:2-4,18
[15] 谢平.基于框架模式的试题库智能组卷系统《华东交通大学学报》1998年15卷4期:58-63
[16] 华如海,王俊普.基于约束满足的智能组卷方法的研究与实现《计算机应用研究》2000年17卷11期:20-22
[17] 汪德顺,顾学春,马立兴.基于知识的成卷方法及在MATBAS系统中的实现.《西安交大学报》.1988,23(1):3539
[18] Hall PAV, Papasogoulos S. Hypertext system and application. Information and software Technology. 1990, 32(7):447490
[19] 卢开澄.《组合数学》.北京:清华大学出版社.1991:10-100
[20] I.R.Foulds.《组合最优化》.上海:上海翻译公司.1988:30-50
[21] 刘方爱.一种通用试题库模型及试卷生成算法《计算机应用与软件》1998年15卷4期:52-56
[22] 余胜泉,何克抗.网络题库系统的设计与实现《中国远程教育》.2000.9:53-57
[23] 于忠敏.刘延华.选题组卷策略研究.《电脑开发与应用》.2001,14(3):32
[24] 林雪明,张钧良,蒋伟钢.基于知识点的试题库组卷算法的建立.《微机发展》.2001年第2期:77-80
[25] 魏平,熊伟洁.用遗传算法解组卷问题的设计与实现.《微电子学与计算机》.2002年第4期:48-50
[26] 闭应洲,苏德富,陈宁江.基于矩阵编码的遗传算法及其在自动组卷中的应用.《计算机工程》.第29卷第6期2003年4月:73-75,182
[27] 李小勇,王瑛.题库管理系统中的自动化组卷算法[J].《西北师范大学学报》(自然科学版),2002,38(4):41-43.
[28] 刘彬,金涛,陈大平.遗传算法在试题组卷中的应用.《燕山大学学报》.第26卷第三期2002.7:193-195
[29] 张桂娟,武兆慧,刘希玉.一种基于学习机制的并行遗传算法.《计算机应用》.第25卷第2期.2005.2:374-376
[30] R. Agrawal R. Srikant Fast Algorithms for Mining Association Rules in Large Databases Proceedings of the 20th International Conference on Very Large Data Bases 1994:487-499
[31] J Spark. An Effective Hash based Algorithm for Mining Association rules Proc. ACM. SIGMOD. 1995:175-186
[32] Savasers A, Omiecinski E, Navathe S. An efficient algorithm for mining association rules in large database[C]. VLDB, 1995 : 432-443.
[33] H Mannila, H Toivonen, Inkeri Verkamo. A Efficient algorithm for discovering association rulers. In Processing of AAAI Workshop on Knowledge Discovering in Database. 1994:181-192
[34] 郭述平,王景英.《教育测量》.东北师范大学出版社.1988.12:3-16
[35] 黄光扬主编,《教育测量与评价》,华东师范大学出版社,2002:65-82
[36] 张敏强,《教育测量学》,人民教育出版社,1998:73-106
[37] 胡中锋,李方.《教育测量与评价》[M].广州:广东高等教育出版社,1999:193-196
[38] 顾明远,申杲华.《学校考试与命题管理运作全书》[M].北京:开明出版,1995:497-499
[39] 于信凤.《考试学引论》.辽宁人民出版社,1987:77-92
[40] 王汉澜.《教育测量学》[M].河南大学出版社,1987:26-118
[41] 周谦.《教育评价与统计》[M].北京:科学出版社,1998:224-252
[42] 全惠云,范国闯,赵霆雷.基于遗传算法的试题库智能组卷系统研究[J].《武汉大学学报》(自然科学版),1999,(5):758-760.
[43] 张志尧,张彤评.估考试质量的数学模型.《天津医科大学学报》2001年7卷2期:192-194
[44] 吕文达.《精通C#程序设计》清华大学出版社.2004年11月第一版:473-508
[45] Jason Price,Mike Gunderloy[美].《Visual C#.NET从入门到精通》.电子工业出版社2003年3月第一版:691-748
[46] 国家教委考试中心编.《题库建设理论与实践》,光明日报出版社 1990:p213-219
[47] 应暑儒,胡立新.试题库随机选题数学模型及实现[J].《计算机应用》.2000.20(1):46-47.
[48] 林复华.智能成卷系统的数学模型算法及其应用.《华南理土大学土学硕士论文》.1992:21-36
[49] 华如海,王俊普,郑全,徐杨.基于约束满足的智能组卷方法的研究与实现[J].《计算机应用研究》.2000,(11):20-22
[50] 徐宗本,张讲社,郑亚林.《计算智能中的仿生学:理论与算法》.科学出版社.2003. 5:4-11
[51] 肖成林,徐清振.基于遗传算法的成卷策略的设计与实现.《现代计算机》(总第一六九期)2003.8:39-41.
[52] 阎平凡,张长水.《人工神经网络与模拟进化计算》.清华大学出版社.2000.11:396-451
[53] C. Smith Greg, S. Smith Shana. An Enhanced Genetic Algorithm for Automated Assembly planning. Robotics and Computer Integrated Manufacturing, 2002 18(5-6):355-364
[54] 陈国良,王煦法,庄镇泉等.《遗传算法及其应用》.人民邮电出版社 1999:11-34
[55] T. Lynda, C. Chrisment, Boughanem Mohand. Multiple Query Evaluation Based on Enhanced Genetic Algorithm. Information Processing and Management. 2003. 39(2):215-231
[56] H. Barbosa, C. Lemonge Afonso. A New Adaptive Penalty Scheme for Genetic Algorithms. Information Sciences, 2003, 156 (3-4) : 215-251
[57] J C. Pons, T. Giddens, B. Yadav Surya. The Development and Evaluation of an Imprved Genetic Algorithm Based on Migration and Artificial Selection [J]. IEEE Transactions on Systems, Man and Cybernetics. 1994, 24(1):73-86
[58] 杨路明,陈大鑫.改进遗传算法在试题自动组卷中的应用研究.《计算机与数字工程》.第32卷第5期2004:76-79
[2] 宋云娴,白鹏.《智能教学系统设计与实现》[M].北京:电子工业出版社.1995:24-45
[3] 李更明,卢伟清.计算机公共课机考软件的设计与实现.《福建师范大学学报》(自然科学版)第19卷第2期2003.6 106-109.
[4] 毛秉毅.基于遗传算法的智能组卷系统数据库结构的研究.《计算机工程与应用》.2003.6:230-232
[5] 吴泽晖.基于ASP开发的网上组卷考试系统.《微型机与应用》.2000年19卷9期:51-53
[6] 金汉均,郑世珏,吴明武.分段随机抽选法在智能组卷中的研究与应用.《计算机应用研究》 2003年20卷9期:102-103,126
[7] 张国才,徐效美。基于分割策略的快速抽题组卷算法《微计算机应用》.2003年24卷4期:197-199
[8] 陈华光,周铁山,张晓清.通用试题库系统的设计与实现.《湖南工程学院学报》.自然科学版.2002年12卷3期:32-34
[9] 林健,闫华,武兵计算机自适应考试理论分析.《太原理工大学学报》.2004年35卷2期:221-224
[10] 吴锦林,吴清锋.分布式计算机应用水平考试系统的设计与实现.《计算机工程与设计》.2003年24卷3期:52-54
[11] 张亮,陆剑峰,张浩.基于PHP平台的网络考试系统开发与研究.《微型电脑应用》.2003年19卷7期:26-28
[12] 戴亚非,李晓明.计算机自动组卷算法分析.《小型微型计算机系统》.1995年16卷9期:51-55
[13] 朱明,王俊普.一种智能组卷方法的研究与实现.《微小型计算机开发与应用》.1997年4期:5-9
[14] 刘彬,糜长军.智能组卷系统试题库结构的研究《信息技术(哈尔滨)》2002年3期:2-4,18
[15] 谢平.基于框架模式的试题库智能组卷系统《华东交通大学学报》1998年15卷4期:58-63
[16] 华如海,王俊普.基于约束满足的智能组卷方法的研究与实现《计算机应用研究》2000年17卷11期:20-22
[17] 汪德顺,顾学春,马立兴.基于知识的成卷方法及在MATBAS系统中的实现.《西安交大学报》.1988,23(1):3539
[18] Hall PAV, Papasogoulos S. Hypertext system and application. Information and software Technology. 1990, 32(7):447490
[19] 卢开澄.《组合数学》.北京:清华大学出版社.1991:10-100
[20] I.R.Foulds.《组合最优化》.上海:上海翻译公司.1988:30-50
[21] 刘方爱.一种通用试题库模型及试卷生成算法《计算机应用与软件》1998年15卷4期:52-56
[22] 余胜泉,何克抗.网络题库系统的设计与实现《中国远程教育》.2000.9:53-57
[23] 于忠敏.刘延华.选题组卷策略研究.《电脑开发与应用》.2001,14(3):32
[24] 林雪明,张钧良,蒋伟钢.基于知识点的试题库组卷算法的建立.《微机发展》.2001年第2期:77-80
[25] 魏平,熊伟洁.用遗传算法解组卷问题的设计与实现.《微电子学与计算机》.2002年第4期:48-50
[26] 闭应洲,苏德富,陈宁江.基于矩阵编码的遗传算法及其在自动组卷中的应用.《计算机工程》.第29卷第6期2003年4月:73-75,182
[27] 李小勇,王瑛.题库管理系统中的自动化组卷算法[J].《西北师范大学学报》(自然科学版),2002,38(4):41-43.
[28] 刘彬,金涛,陈大平.遗传算法在试题组卷中的应用.《燕山大学学报》.第26卷第三期2002.7:193-195
[29] 张桂娟,武兆慧,刘希玉.一种基于学习机制的并行遗传算法.《计算机应用》.第25卷第2期.2005.2:374-376
[30] R. Agrawal R. Srikant Fast Algorithms for Mining Association Rules in Large Databases Proceedings of the 20th International Conference on Very Large Data Bases 1994:487-499
[31] J Spark. An Effective Hash based Algorithm for Mining Association rules Proc. ACM. SIGMOD. 1995:175-186
[32] Savasers A, Omiecinski E, Navathe S. An efficient algorithm for mining association rules in large database[C]. VLDB, 1995 : 432-443.
[33] H Mannila, H Toivonen, Inkeri Verkamo. A Efficient algorithm for discovering association rulers. In Processing of AAAI Workshop on Knowledge Discovering in Database. 1994:181-192
[34] 郭述平,王景英.《教育测量》.东北师范大学出版社.1988.12:3-16
[35] 黄光扬主编,《教育测量与评价》,华东师范大学出版社,2002:65-82
[36] 张敏强,《教育测量学》,人民教育出版社,1998:73-106
[37] 胡中锋,李方.《教育测量与评价》[M].广州:广东高等教育出版社,1999:193-196
[38] 顾明远,申杲华.《学校考试与命题管理运作全书》[M].北京:开明出版,1995:497-499
[39] 于信凤.《考试学引论》.辽宁人民出版社,1987:77-92
[40] 王汉澜.《教育测量学》[M].河南大学出版社,1987:26-118
[41] 周谦.《教育评价与统计》[M].北京:科学出版社,1998:224-252
[42] 全惠云,范国闯,赵霆雷.基于遗传算法的试题库智能组卷系统研究[J].《武汉大学学报》(自然科学版),1999,(5):758-760.
[43] 张志尧,张彤评.估考试质量的数学模型.《天津医科大学学报》2001年7卷2期:192-194
[44] 吕文达.《精通C#程序设计》清华大学出版社.2004年11月第一版:473-508
[45] Jason Price,Mike Gunderloy[美].《Visual C#.NET从入门到精通》.电子工业出版社2003年3月第一版:691-748
[46] 国家教委考试中心编.《题库建设理论与实践》,光明日报出版社 1990:p213-219
[47] 应暑儒,胡立新.试题库随机选题数学模型及实现[J].《计算机应用》.2000.20(1):46-47.
[48] 林复华.智能成卷系统的数学模型算法及其应用.《华南理土大学土学硕士论文》.1992:21-36
[49] 华如海,王俊普,郑全,徐杨.基于约束满足的智能组卷方法的研究与实现[J].《计算机应用研究》.2000,(11):20-22
[50] 徐宗本,张讲社,郑亚林.《计算智能中的仿生学:理论与算法》.科学出版社.2003. 5:4-11
[51] 肖成林,徐清振.基于遗传算法的成卷策略的设计与实现.《现代计算机》(总第一六九期)2003.8:39-41.
[52] 阎平凡,张长水.《人工神经网络与模拟进化计算》.清华大学出版社.2000.11:396-451
[53] C. Smith Greg, S. Smith Shana. An Enhanced Genetic Algorithm for Automated Assembly planning. Robotics and Computer Integrated Manufacturing, 2002 18(5-6):355-364
[54] 陈国良,王煦法,庄镇泉等.《遗传算法及其应用》.人民邮电出版社 1999:11-34
[55] T. Lynda, C. Chrisment, Boughanem Mohand. Multiple Query Evaluation Based on Enhanced Genetic Algorithm. Information Processing and Management. 2003. 39(2):215-231
[56] H. Barbosa, C. Lemonge Afonso. A New Adaptive Penalty Scheme for Genetic Algorithms. Information Sciences, 2003, 156 (3-4) : 215-251
[57] J C. Pons, T. Giddens, B. Yadav Surya. The Development and Evaluation of an Imprved Genetic Algorithm Based on Migration and Artificial Selection [J]. IEEE Transactions on Systems, Man and Cybernetics. 1994, 24(1):73-86
[58] 杨路明,陈大鑫.改进遗传算法在试题自动组卷中的应用研究.《计算机与数字工程》.第32卷第5期2004:76-79