基于遗传算法的自动组卷系统研究与实现

【作者】 周文举；

【导师】 刘希玉；

【作者基本信息】 山东师范大学 ， 管理科学与工程， 2006， 硕士

【摘要】 组卷问题是一个在一定约束条件下的多目标参数优化问题,采用传统的数学方法求解十分困难,自动组卷的效率和质量完全取决于试题库设计以及抽题算法的设计。如何设计一个算法从试题库即快又好的抽出一组最符合考试要求的试题,是本文研究的目的。在对国内外大量相关文献分析研究的基础上,本文选择遗传算法作为组卷算法,设计了一种具有通用性的组卷系统。该系统能够按照试题类型、试题数量、知识点、难度系数、区分度、曝光度、最近出题时间、答题时间等约束条件进行快速搜索,从而找到最佳组卷方案,组出理想的试卷。 在组卷系统研究的过程中,本文对传统组卷过程进行了分析,形成了组卷问题的数学模型,并在教育测量和教育统计理论的基础上设计了试题库结构。基于该数学模型,本文建立了按试题类型分组的组卷思想,经试验比较,分组组卷算法搜索速度明显优于不分组时的情况,本文给出了试验的数据。在组卷系统研究的过程中,本文对经典遗传算法从多方面进行改进,并利用C#编程将算法应用于实践。通过实践不仅验证了本文提出的理论的正确性,还对具体组卷实际中遇到的困扰进行了较为合理的解决,使系统可以在实际中应用。总之,本研究主要的工作可以归纳为以下几点: 1.通过分析组卷策略,建立了组卷问题数学模型,并对模型进行简化处理。 2.采用ADO.NET技术,将试题库按题型分割为几个分库表,并将分库表存放于计算机内存中,组卷时既减小了算法的搜索范围,又减少了访问硬盘的时间。 3.改进遗传算法采用分组自然数编码,减少了染色体长度空间,编码直接采用试题编号,省去了编码和解码的繁琐。 4.运用自适应理论改进交叉概率及变异概率,算法本身总能找到适合于自己得交叉概率和变异概率。引入“遗传——灾变”算法使变异概率在监测到染色体有“早熟”倾向时,会自动突变其值,发生灾变,增加变异的机会,使种群跳出“早熟”。 5.选择算子采用模拟小生境的方法,其基本做法是:当新产生的子代个体的适应度超过其父代个体的适应度时,所产生的子代个体才能代替其父代个体而遗传到下一代种群中,否则父代个体仍保留在下一代种群中。由于子代个体和父代个体之间编码结构具有相似性,所以替换掉的只是一些编码结构相似的个体,故它能够有效地维持种群的多样性,从而避免产生局部最优解,改善未成熟收敛。 6.解决了在实际组卷中遇到的试卷中试题的分值分配问题,研究了对选择题、填空题和问答题的难度和答题时间的调整策略。 7.利用C#.net编程实现了基于上述改进的遗传算法自动组卷系统,文中给出了主要界面和部分关键源代码。更多还原

【Abstract】 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.更多还原