基于遗传算法的CAT组卷问题研究
摘要
基于项目反应理论的计算机自适应测试兴起于上世纪八十年代中期，它是计算机辅助测试及现代测量研究中的一个重要领域，它的特点是能够根据考生能力不同而由计算机从题库中智能选取难度与其能力相匹配的试题施测，考试成绩与样本(题目)的选择无关，能更准确客观地反应考生的实际能力，而且达到一定测量精度需要的时间更短，但CAT组卷时如何将IRT理论的信息量等计量指标与题型、知识点等非计量指标有机地结合起来，为测量学界提出了一个新的课题。
本文首先在对当前计算机自适应测试系统的现状和发展趋势进行了分析后，系统介绍了计算机自适应测试的理论基础-项目反应理论及计算机自适应测试系统的基本原理，并完成了一个基于项目反应理论的CAT系统的总体结构、功能模块及数据库设计。
然后对最大信息量模型和WDM模型进行分析，发现最大信息量模型运算时间长，且可能出现无解的情况，而WDM模型对于CAT组卷问题中既有题型分布、知识点分布，又有信息量等约束条件时，由于各约束条件的量纲不同，根据约束条件计算出的离差值不可比，因此本文对WDM模型进行了改进，为CAT组卷问题建立了分步WDM模型，有效解决了计量指标—信息量与非计量指标—题型分布、知识点分布等约束条件量纲不同的问题，并很好地体现了CAT组卷问题中测试项目信息函数值最高的目标。
最后，针对遗传算法容易出现早熟和收敛速度慢的问题，本文对基本遗传算法进行了多处改进，如采用了整数分段编码和自适应的交叉、变异概率等。然后将改进的自适应遗传算法用于CAT组卷问题，实验结果表明本文设计实现的组卷算法不仅避免了遗传算法中经常出现的“早熟现象”，而且有效地解决了CAT组卷中的约束优化问题，具有较高的组卷成功率和效率。
Computerized Adaptive Test bases on Item Response Theory arose in the middle of1980's, it is an important part of the computer-based testing and modern measurementresearch, it's trait is to construct an optimal test for each examinee, this is realized byestimating the examinee's ability after administration of each item and selecting the next itembased on the current ability estimate. The final grade will be independent of examinationitems (questions). CAT can measure the real capacities of the examinees more exactly, moreimpersonality and quickly. But, it brings about a problem in psychometrics how to combineinformation quantity with content and other non-psychometrics characteristics.
Firstly, the author analyzes present situation and development of CAT. Then the authorintroduces IRT-the theory basis of CAT, and briefly explains the implement method of CATsystem, and designs a framework, modules and database of a CAT system.
Secondly the author analyses Max-Min Model and Weighted Deviation Model. It isfound that Max-Min Model needs a long running time and probably has no solution. Whenthe constraints are made up of question type distributing, knowledge point distributing andinformation with different dimensions, the calculated deviations of WDM cannot becompared. To deal with these problems, this paper establish a step-by-step WDM, whichsolves question of different dimensions, and stands out the target of information maximum.
Finally, to deal with the prematurely and the low convergence speed of genetic algorithm,this paper improves some aspects of genetic algorithms, such as coding strategy, selectionoperation, crossover operation and mutation operation etc. then this paper designs andimplements a new algorithm of test papers generation based on adaptive genetic algorithm.The simulation shows that it could solve constraint optimization problems with goodperformance and practicability. Furthermore, the success rate and efficiency is high.
本文首先在对当前计算机自适应测试系统的现状和发展趋势进行了分析后，系统介绍了计算机自适应测试的理论基础-项目反应理论及计算机自适应测试系统的基本原理，并完成了一个基于项目反应理论的CAT系统的总体结构、功能模块及数据库设计。
然后对最大信息量模型和WDM模型进行分析，发现最大信息量模型运算时间长，且可能出现无解的情况，而WDM模型对于CAT组卷问题中既有题型分布、知识点分布，又有信息量等约束条件时，由于各约束条件的量纲不同，根据约束条件计算出的离差值不可比，因此本文对WDM模型进行了改进，为CAT组卷问题建立了分步WDM模型，有效解决了计量指标—信息量与非计量指标—题型分布、知识点分布等约束条件量纲不同的问题，并很好地体现了CAT组卷问题中测试项目信息函数值最高的目标。
最后，针对遗传算法容易出现早熟和收敛速度慢的问题，本文对基本遗传算法进行了多处改进，如采用了整数分段编码和自适应的交叉、变异概率等。然后将改进的自适应遗传算法用于CAT组卷问题，实验结果表明本文设计实现的组卷算法不仅避免了遗传算法中经常出现的“早熟现象”，而且有效地解决了CAT组卷中的约束优化问题，具有较高的组卷成功率和效率。
Computerized Adaptive Test bases on Item Response Theory arose in the middle of1980's, it is an important part of the computer-based testing and modern measurementresearch, it's trait is to construct an optimal test for each examinee, this is realized byestimating the examinee's ability after administration of each item and selecting the next itembased on the current ability estimate. The final grade will be independent of examinationitems (questions). CAT can measure the real capacities of the examinees more exactly, moreimpersonality and quickly. But, it brings about a problem in psychometrics how to combineinformation quantity with content and other non-psychometrics characteristics.
Firstly, the author analyzes present situation and development of CAT. Then the authorintroduces IRT-the theory basis of CAT, and briefly explains the implement method of CATsystem, and designs a framework, modules and database of a CAT system.
Secondly the author analyses Max-Min Model and Weighted Deviation Model. It isfound that Max-Min Model needs a long running time and probably has no solution. Whenthe constraints are made up of question type distributing, knowledge point distributing andinformation with different dimensions, the calculated deviations of WDM cannot becompared. To deal with these problems, this paper establish a step-by-step WDM, whichsolves question of different dimensions, and stands out the target of information maximum.
Finally, to deal with the prematurely and the low convergence speed of genetic algorithm,this paper improves some aspects of genetic algorithms, such as coding strategy, selectionoperation, crossover operation and mutation operation etc. then this paper designs andimplements a new algorithm of test papers generation based on adaptive genetic algorithm.The simulation shows that it could solve constraint optimization problems with goodperformance and practicability. Furthermore, the success rate and efficiency is high.
引文
[1] 漆书青，戴海崎，丁树良．现代教育与心理测量学原理．北京：高等教育出版社，2002．
[2] Hambleton R K, Swaaminathan H. Item response theory: principles and applications. Boston:Kluwer Nijhoff Publishing. 1985.
[3] 余民宁．IRT学理与应用．台湾：教育测验出版社，1994．
[4] Rasch G. Probabilistic models for some intelligence and attainment tests. Chicago: The University of Chicago Press, 1980.
[5] Bock R D. Estimating item parameters and latent ability when responses are scored in two or more nominal categories. Psychometrika, 1972,37(1):29-51.
[6] Samejima F. Estimation of latent ability using a response pattern of graded scores. Psychometrika Monograph Supplement, 1969,34(4):100-114.
[7] Andrich D. An extension of the rasch model for ratings providing both location and dispersion parameters. Psychometrika, 1982,47(1):105-113.
[8] Thissen D, Steinberg L. h taxonomy of item response models. Psychometrika, 1986,51(4):567-577.
[9] Birnbaum A. Some latent trait models and their use in inferring an examinee's ability.In: Lord F M, Novick M R. Statistical Theories of Mental Test Scores. New York: Addison-Wesley, 1968:397-472.
[10] Lord F M. Applications of item response theory to practical testing problems. New Jersey:Lawrence Erlbaum Associates, 1980.
[11] Green D R, Yen W M, Burket G R. Experiences in the application of item response theory in test construction. Applied Measurement in Education, 1989,2(4):297-312.
[12] 章竞思，李梦霞．当代智力测验研究的现状与发展趋势．科技情报开发与经济，2002，12(5)：93-94．
[13] 顾海根．一种新的测验形式-计算机自适应测验．上海教育科研，1999，137(5)：31-33．
[14] 余嘉元．项目反应理论及其应用．江苏：江苏教育出版社，1992．
[15] 程艳．计算机自适应考试的理论模型研究．计算机与现代化，2006，133(9)：24-27．
[16] 薜理银．教育信息处理原理．北京：北京师范大学出版社，1996．
[17] 林健，闫华，武兵．计算机自适应考试理论分析．太原理工大学学报，2004，35(2)：221-224．
[18] 罗芬，丁树良，胡小松等．基于IRT若干参数估计方式的比较．江西师范大学学报(自然科学版)，2003，27(1)：56-60．
[19] 漆书青．项目反应理论及其应用研究．江西：江西高校出版社，1992．
[20] 毕忠勤，陈光喜，徐安农．计算机自适应测试系统的算法．桂林电子工业学院学报，2004，24(6)：50-53．
[21] 郑珂，申瑞民．基于Web的自适应考试系统．微型电脑应用，2000，16(1)：3-6．
[22] 普措才仁．基于B／S体系结构开发应用系统．西南民族大学学报(自然科学版)，2005，31(3)：447—451．
[23] 张震，张曾科．一种新的WEB数据库系统结构．小型微型计算机系统，2001，22(5)：559—561．
[24] Van der Linden W J, Boekkooi-Timminga E. A maximin model for test design with practical constraints. Psychometrika, 1989,54(2):237-247.
[25] Swanson L, Stocking M L. A model and heuristic for solving very large item selection problems. Applied Psychological Measurement, 1993,17(2):151-166.
[26] 陈国良，王煦法，庄镇泉等．遗传算法及其应用．北京：人民邮电出版社，1999．
[27] 杨路明，陈大鑫．改进遗传算法在试题自动组卷中的应用研究．计算机与数字工程，2004，32(5)：76—79．
[28] Tamine L, Chrisment C, Boughanem M. Multiple query evaluation based on an enhanced genetic algorithm. Information Processing and Management, 2003,39(2):215-231.
[29] Hello J C, Barbosa, Afonso C C et al. A new adaptive penalty scheme for genetic algorithms. Information Sciences, 2003,156(3):215-251.
[30] Potts J C, Giddens T, Yadav S B. The development and evaluation of an improved genetic algorithm based on migration and artificial selection. IEEE Transactions on Systems, Man and Cybernetics, 1994,24(1):73-86.
[31] 王小平，曹立明．遗传算法-理论、应用与软件实现．西安：西安交通大学出版社，2002．
[32] Zalzala A M S, Fleming P J. Genetic algorithms in engineering systems. London: The Institution of Electrical Engineers, 1997.
[33] 吴斌，吴坚，涂序彦．快速遗传算法．电子科技大学学报，1999，28(1)：49-53．
[34] Michalewica Z. Genetic algorithms + data structure = evolution programs. New York:Springer Yerlag, 1996.
[35] Antonisse J. A new interpretation of schema notation that overturns the binary encoding constrain. In: Schaffer J D. Proceedings of the Third International Conference on Genetic Algorithms. CA: Morgan Kaufmann Publishers Inc.,1989:86-91.
[36] 陈国良，王煦法．遗传算法及其应用．北京：国防出版社，2001．
[37] 陈晓东，王宏宇．一种基于改进遗传算法的组卷算法．哈尔滨工业大学学报，2005，37(9)：1174—1176．1248．
[38] 郝琳，马长林改进的自适应遗传算法及其性能研究．中国控制与决策学术年会，哈尔滨，2005：895-898．
[39] Yip P P C. Yoh-Han P. Combinatorial optimization with use of guided evolutionary simulated annealing. IEEE Transactions on Neural Networks, 1995,6(2):290-295.
[40] Schaffer J D, Caruana R A, Eshelman L J et al. A study of control parameters affecting online performance of genetic algorithms for function optimization. In: Schaffer J D. Proceedings of the Third International Conference on Genetic Algorithms. CA: Morgan Kaufmann Publishers Inc.,1989:51-60.
[41] 陆亿红，柳红．基于整数编码和自适应遗传算法的自动组卷．计算机工程，2005，31(23)：232-233．
[42] 肖成林，徐清振．基于遗传算法的成卷策略的设计与实现．现代计算机，2003，169(8)：39-41．
[2] Hambleton R K, Swaaminathan H. Item response theory: principles and applications. Boston:Kluwer Nijhoff Publishing. 1985.
[3] 余民宁．IRT学理与应用．台湾：教育测验出版社，1994．
[4] Rasch G. Probabilistic models for some intelligence and attainment tests. Chicago: The University of Chicago Press, 1980.
[5] Bock R D. Estimating item parameters and latent ability when responses are scored in two or more nominal categories. Psychometrika, 1972,37(1):29-51.
[6] Samejima F. Estimation of latent ability using a response pattern of graded scores. Psychometrika Monograph Supplement, 1969,34(4):100-114.
[7] Andrich D. An extension of the rasch model for ratings providing both location and dispersion parameters. Psychometrika, 1982,47(1):105-113.
[8] Thissen D, Steinberg L. h taxonomy of item response models. Psychometrika, 1986,51(4):567-577.
[9] Birnbaum A. Some latent trait models and their use in inferring an examinee's ability.In: Lord F M, Novick M R. Statistical Theories of Mental Test Scores. New York: Addison-Wesley, 1968:397-472.
[10] Lord F M. Applications of item response theory to practical testing problems. New Jersey:Lawrence Erlbaum Associates, 1980.
[11] Green D R, Yen W M, Burket G R. Experiences in the application of item response theory in test construction. Applied Measurement in Education, 1989,2(4):297-312.
[12] 章竞思，李梦霞．当代智力测验研究的现状与发展趋势．科技情报开发与经济，2002，12(5)：93-94．
[13] 顾海根．一种新的测验形式-计算机自适应测验．上海教育科研，1999，137(5)：31-33．
[14] 余嘉元．项目反应理论及其应用．江苏：江苏教育出版社，1992．
[15] 程艳．计算机自适应考试的理论模型研究．计算机与现代化，2006，133(9)：24-27．
[16] 薜理银．教育信息处理原理．北京：北京师范大学出版社，1996．
[17] 林健，闫华，武兵．计算机自适应考试理论分析．太原理工大学学报，2004，35(2)：221-224．
[18] 罗芬，丁树良，胡小松等．基于IRT若干参数估计方式的比较．江西师范大学学报(自然科学版)，2003，27(1)：56-60．
[19] 漆书青．项目反应理论及其应用研究．江西：江西高校出版社，1992．
[20] 毕忠勤，陈光喜，徐安农．计算机自适应测试系统的算法．桂林电子工业学院学报，2004，24(6)：50-53．
[21] 郑珂，申瑞民．基于Web的自适应考试系统．微型电脑应用，2000，16(1)：3-6．
[22] 普措才仁．基于B／S体系结构开发应用系统．西南民族大学学报(自然科学版)，2005，31(3)：447—451．
[23] 张震，张曾科．一种新的WEB数据库系统结构．小型微型计算机系统，2001，22(5)：559—561．
[24] Van der Linden W J, Boekkooi-Timminga E. A maximin model for test design with practical constraints. Psychometrika, 1989,54(2):237-247.
[25] Swanson L, Stocking M L. A model and heuristic for solving very large item selection problems. Applied Psychological Measurement, 1993,17(2):151-166.
[26] 陈国良，王煦法，庄镇泉等．遗传算法及其应用．北京：人民邮电出版社，1999．
[27] 杨路明，陈大鑫．改进遗传算法在试题自动组卷中的应用研究．计算机与数字工程，2004，32(5)：76—79．
[28] Tamine L, Chrisment C, Boughanem M. Multiple query evaluation based on an enhanced genetic algorithm. Information Processing and Management, 2003,39(2):215-231.
[29] Hello J C, Barbosa, Afonso C C et al. A new adaptive penalty scheme for genetic algorithms. Information Sciences, 2003,156(3):215-251.
[30] Potts J C, Giddens T, Yadav S B. The development and evaluation of an improved genetic algorithm based on migration and artificial selection. IEEE Transactions on Systems, Man and Cybernetics, 1994,24(1):73-86.
[31] 王小平，曹立明．遗传算法-理论、应用与软件实现．西安：西安交通大学出版社，2002．
[32] Zalzala A M S, Fleming P J. Genetic algorithms in engineering systems. London: The Institution of Electrical Engineers, 1997.
[33] 吴斌，吴坚，涂序彦．快速遗传算法．电子科技大学学报，1999，28(1)：49-53．
[34] Michalewica Z. Genetic algorithms + data structure = evolution programs. New York:Springer Yerlag, 1996.
[35] Antonisse J. A new interpretation of schema notation that overturns the binary encoding constrain. In: Schaffer J D. Proceedings of the Third International Conference on Genetic Algorithms. CA: Morgan Kaufmann Publishers Inc.,1989:86-91.
[36] 陈国良，王煦法．遗传算法及其应用．北京：国防出版社，2001．
[37] 陈晓东，王宏宇．一种基于改进遗传算法的组卷算法．哈尔滨工业大学学报，2005，37(9)：1174—1176．1248．
[38] 郝琳，马长林改进的自适应遗传算法及其性能研究．中国控制与决策学术年会，哈尔滨，2005：895-898．
[39] Yip P P C. Yoh-Han P. Combinatorial optimization with use of guided evolutionary simulated annealing. IEEE Transactions on Neural Networks, 1995,6(2):290-295.
[40] Schaffer J D, Caruana R A, Eshelman L J et al. A study of control parameters affecting online performance of genetic algorithms for function optimization. In: Schaffer J D. Proceedings of the Third International Conference on Genetic Algorithms. CA: Morgan Kaufmann Publishers Inc.,1989:51-60.
[41] 陆亿红，柳红．基于整数编码和自适应遗传算法的自动组卷．计算机工程，2005，31(23)：232-233．
[42] 肖成林，徐清振．基于遗传算法的成卷策略的设计与实现．现代计算机，2003，169(8)：39-41．