智能计算理论在网络试题库中的应用
|
摘要
网络试题库是基于Web的题库系统,该系统由各学科的试题集、题库管理、智能组卷等几部分组成。建设网络试题库的目的是为学校提供一个网络化的题库管理和智能组卷系统。智能组卷是在指定要求下,由计算机从试题库中按照各种约束条件自动组成试卷。
如何设计一个好的组卷算法和试题库模型将影响智能组卷的质量和效率。智能组卷系统的目的是智能生成试卷,并能满足或尽可能接近用户预定的目标。因此如何设计一个算法从试题库中高效快速地组成试卷,是文章的研究目的。文章首先分析了试卷的评价指标、各项指标的作用,建立了智能组卷的数学模型;接着论述了通用试题库组卷系统的设计思想及其实现方法并介绍了遗传算法的实现过程。然后,详细介绍了基于传统编码的遗传算法与基于题号编码的遗传算法,在基于题号整数编码遗传算法的基础上提出了基于无重复知识点的遗传算法。该算法将无重复知识点这一刚性约束条件融于遗传算子中,可以简化适应度函数中的约束条件,减少多目标问题中各约束条件之间的竞争,该算法速度更快,组卷质量更好。为验证文章提出的基于无重复知识点遗传算法的可行性,通过改变遗传参数进行了大量的组卷实验,找到了最优参数组合,并验证了算法的有效性。文章还对基于pareto序的多目标优化算法进行了初步的尝试,实现了基于NSGA-Ⅱ的智能组卷算法,取得较满意的效果,同时也验证了NSGA-Ⅱ算法的适用范围。
The network item bank is based on the item pool system in the Web form, which consists of question bank of various disciplines , the item pool management ,intelligent group volume. Its goal is to provide a network to the school the question bank management and the intelligent group volume system. The intelligent group volume is under certain request, from tries in the question bank by the computer to be composed the examination paper automatically according to each kind of constraint condition. The group volume question essence is one under the multiple constraint condition multi-objective optimization question.
The intelligent group volume efficiency and the quality are decided completely in try the question bank design as well as the group volume algorithm design. Because the intelligent group volume request production examination paper must the greatest degree satisfy the user the different need, therefore how designs an algorithm from to try in the question bank fast to compose the examination paper highly effective, is the article research goal. The article has first analyzed the examination paper appraisal target, each target function, has established the intelligent group volume mathematical model; Then elaborated has tried the question bank group volume system general the design concept and the realization method and introduced the genetic algorithm realization process. Then, introduced in detail based on the traditional code genetic algorithm with based on the topic number code genetic algorithm, in proposed based on in the topic number integer code genetic algorithm foundation based on not duplicates the knowledge genetic algorithm. This algorithm not will duplicate the knowledge this rigidity constraint condition to melt in the heredity operator, might simplify in the sufficiency function the constraint condition, will reduce in the multi-objective question between each constraint condition competition, this algorithm speed will be quicker, the group volume quality will be better. For confirms the article to propose based on not duplicates the knowledge genetic algorithm the feasibility, the article has carried on the massive group volume experiment through the change heredity parameter, has found the most superior parameter combination, and has confirmed the algorithm validity. The article has made an attempt on multi-objective optimization based on non-dominated sorting,realized intellgent test paper generation based on NSGA-II,acquired satisfying effect. At the same time,it validated applying extension of NSGA-II algorithm.
如何设计一个好的组卷算法和试题库模型将影响智能组卷的质量和效率。智能组卷系统的目的是智能生成试卷,并能满足或尽可能接近用户预定的目标。因此如何设计一个算法从试题库中高效快速地组成试卷,是文章的研究目的。文章首先分析了试卷的评价指标、各项指标的作用,建立了智能组卷的数学模型;接着论述了通用试题库组卷系统的设计思想及其实现方法并介绍了遗传算法的实现过程。然后,详细介绍了基于传统编码的遗传算法与基于题号编码的遗传算法,在基于题号整数编码遗传算法的基础上提出了基于无重复知识点的遗传算法。该算法将无重复知识点这一刚性约束条件融于遗传算子中,可以简化适应度函数中的约束条件,减少多目标问题中各约束条件之间的竞争,该算法速度更快,组卷质量更好。为验证文章提出的基于无重复知识点遗传算法的可行性,通过改变遗传参数进行了大量的组卷实验,找到了最优参数组合,并验证了算法的有效性。文章还对基于pareto序的多目标优化算法进行了初步的尝试,实现了基于NSGA-Ⅱ的智能组卷算法,取得较满意的效果,同时也验证了NSGA-Ⅱ算法的适用范围。
The network item bank is based on the item pool system in the Web form, which consists of question bank of various disciplines , the item pool management ,intelligent group volume. Its goal is to provide a network to the school the question bank management and the intelligent group volume system. The intelligent group volume is under certain request, from tries in the question bank by the computer to be composed the examination paper automatically according to each kind of constraint condition. The group volume question essence is one under the multiple constraint condition multi-objective optimization question.
The intelligent group volume efficiency and the quality are decided completely in try the question bank design as well as the group volume algorithm design. Because the intelligent group volume request production examination paper must the greatest degree satisfy the user the different need, therefore how designs an algorithm from to try in the question bank fast to compose the examination paper highly effective, is the article research goal. The article has first analyzed the examination paper appraisal target, each target function, has established the intelligent group volume mathematical model; Then elaborated has tried the question bank group volume system general the design concept and the realization method and introduced the genetic algorithm realization process. Then, introduced in detail based on the traditional code genetic algorithm with based on the topic number code genetic algorithm, in proposed based on in the topic number integer code genetic algorithm foundation based on not duplicates the knowledge genetic algorithm. This algorithm not will duplicate the knowledge this rigidity constraint condition to melt in the heredity operator, might simplify in the sufficiency function the constraint condition, will reduce in the multi-objective question between each constraint condition competition, this algorithm speed will be quicker, the group volume quality will be better. For confirms the article to propose based on not duplicates the knowledge genetic algorithm the feasibility, the article has carried on the massive group volume experiment through the change heredity parameter, has found the most superior parameter combination, and has confirmed the algorithm validity. The article has made an attempt on multi-objective optimization based on non-dominated sorting,realized intellgent test paper generation based on NSGA-II,acquired satisfying effect. At the same time,it validated applying extension of NSGA-II algorithm.
引文
[1]徐守萍,试题库系统及组卷策略[J],科学技术与工程,2007,7(14),363 1-3634
[2]顾洪博,智能化网络试题库系统的研究与实现[D],2004年.
[3]刘彬,糜长军,李勇,智能组卷系统试题库结构的研究[J],信息技术,2003.3:2-4
[4]毛秉毅,基于遗传算法的智能组卷系统数据库结构的研究[J],计算机工程与应用,2003,28(6):230-232
[5]孙勇,柏云,基于遗传算法的试题组卷策略[J],淄博学院学报,2002,4(3):27-28
[6]石中盘,韩卫,基于概率论和自适应遗传算法的智能抽题算法[J],计算机工程,2002,28(1):141-143
[7]张爱文,樊红莲,自适应遗传算法用于自动组卷中的数学模型设计[J],哈尔滨理工大学学报,2006,11(5),18-20
[8]Win J.van der Linden,Bemard P.etal.An integer programming approach to item bank design[J],Applied Psychologieal Measuremeni,2000,24(2):139-150
[9]Huub Verstralen,Timo Beehger,Gunter Maris,The combined use of classical test and item response theory[EB/OL],http://www.cito.nl/pok/eind_fr.htm
[10]De Jong K,Spears W,Using genetic algoritms to solve NP-complete problems[C],Proeeedings of the Third International Conference on Genetic Algorithms,1989
[11]李敏强,寇纪淞,遗传算法的基本理论与应用[M],科学出版社,2003年3月
[12]余胜泉,姚顾波,何克抗.通用试题库组卷策略算法[M],1999年6月
[13]雷英杰,张善文,李续武,周创明,Mmlab遗传算法工具箱及应用[M],2005年.
[14]王力发,杨丽敏.教育统计与测量[M],哈尔滨工程大学出版社,1994年.
[15]宋兆鸿,刘世表,张才美,现代教育测量[M],北京,教育科学出版社,1986年.
[16]文娴,试题库系统智能组卷与试卷分析的研究[D],2007年.
[17]刘韶丽,基于智能组卷策略的网上考试系统的设计与实现[D],东南大学,2006年
[18]詹泽美,基于Web的网上测试系统的设计与实现[J],《荆州师范学院学报(自然科学版)》2003年4月,53-55
[19]郑刚,基于B/S模式的网上教学系统研究与设计[J],计算计工程与应用,2001,(6):33-37
[20]Wim J.vander Linden & Bernard P.&Veldkam R An integer Programming approaeh to item bank design[J].Applied Psyeho- Logieal Measurement,June2000,24(2):139-150.
[21]刘勇,康立山等,非数值并行算法-遗传算法[M],北京,科学出版社,1997.
[22]尹红卫,刘云如,易叶青一种改进的遗传算法及其在组卷系统中的应用[J].现代计算机,总第235期:66-70.
[23]李茂军,童调生,单亲遗传算法编码方式的研究[J],长沙电力学院学报(自然科学版),2000年.
[24]王淑佩,基于改进的遗传算法组卷系统应用研究[D],2005年.
[25]任世军,陈亮,遗传算法中交叉操作的改进策略[J],哈尔滨商业大学学报(自然科学版) 2006年1 0月,22(5),60-63
[26]吴晓琴,基于遗传算法的智能组卷研究[J],合肥学院学报(自然科学版),2007年5月,17(2),48-50
[27]丁卫平;管致锦;沈学华,基于遗传算法的智能组卷应用研究[J],电子电气教学学报,2005年4月,27(2),93-95
[28]贾海鹏,郑丽英,解决TSP的遗传算法初始种群改进方法研究[J],中国科技论文在线
[29]Peter J.Bentley,Jonathan P.Wakefield.An Analysis of Multiobjective optimization within Genetic Algorithms.Technical Report.1996,96:1-14.
[30]E.Zitzler,K.Deb,and L.Thiele.Comparison of multiobjective evolutionary algorithms:Empiricalresults.Evol.Comput.June 2000,2(8):173-195.
[31]N.Srinivas and Kalyanmoy Deb.Multiobjective Optimization Using the Nondominated Sorting in Genetic Algorithms.Evolutionary Computation.Feb.1994,3(2):221-248.
[32]谢涛,陈火旺.多目标优化与决策问题的演化算法.中国工程科学.Feb.2002,4:59-68.
[33]Kalvanmoy Deb,Samir Agrawal,Amrit Pratab,etc.A Fast and Elitist Multi-Objective Genetic Algorithm:NSGA-Ⅱ.IEEE Transanctions on Evolutionary Computation.April 2002,6(1):186-197.
[34]M.P.Fourman.Compaction of symbolic layout using genetic algorithms.Proceedings of the First International Conference on Genetic Algoritlums.1985,141-153
[35]公茂果,焦李成,杨咚咚,马文萍.进化多目标优化算法研究.软件学报,2009,20(2):271-289.
[36]王汉谰,教育测量学[M],河南大学出版社,1986年.
[37]刘斌,吴思和,网络题库的构建[J],现代计算机(专业版),2004年第04期.
[38]陈文伟,黄金才,赵新显.数据挖掘技术[D],北京工业大学出版社,2002
[39]王学友等.模拟电子技术试题库智能组卷算法研究与系统实现[J],电子电气教学学报,2004,26(1):85-89
[40]姜华,胡欣,李明革,题库设计与成卷系统[J],东北师大学报自然科学版,2000年9月,32(3),23-25
[41]林雪明,张钧良,蒋伟钢,基于知识点的试题库组卷算法的建立[J],微机发展,2001年2期,77-78
[42]毛秉毅,智能组卷系统的研究[J],计算机科学,2002年6月,28(6),278-279
[43]王雍钧,黄毓瑜,基于知识点题型分布和分值的智能组卷算法研究[J],计算机应用与软件,2004年8月,2l(8),111-113
[44]刘仁金,基于粒度合成计算的智能组卷策略研究[J],广西师范大学学报(自然科学版),2005年12月,23(4),32-34
[45]李长荣,杨欣宇,曲伟建,高校智能题库建设与管理研究[J],齐齐哈尔大学学报,2006年9月,22(5),84-85
[46]肖洋,王骁,刘风新,在线考试组卷算法研究[J],北京化工大学学报,2006年,33(4)
[47]周文举,基于遗传算法的自动组卷系统研究与实现[D],山东师范大学,2006年
[48]陈锋,基于遗传算法的智能组卷研究与应用[D],北方工业大学,2007年
[49]J.H.Holland.Adaption in Natural and Artificial Systems.MIT Press.1992:6-24
[50]熊辉,赵英凯,丁瑶君,基于神经网络的遗传算法优化及其应用[J],南京化工大学学报,2000年7月,22(4),21-23
[51]陈霁威,乐慧丰,黄道,基于神经网络和遗传算法的在线优化软件设计与实现[J],华东理工大学学报,2002年8期,419-420
[52]姜雷,基于遗传算法的模糊神经网络控制器设计[D],哈尔滨理工大学,2005年
[53]石中盘,韩卫,基于概率论和自适应遗传算法的智能抽题算法[J],计算机工程,2002年,28(1),141-143
[54]董敏,霍剑青,王晓蒲,基于自适应遗传算法的智能组卷研究[J],小型微型计算机系统,2004.25(1).82-85
[55]C.S.Li,P.Syu,V.Castel.li.Hierarchy Scan:A hierarchical Similari tySearch Algorithm for Databases of Long Sequences,Proc.21st Int'l Conf.Data Eng.,1996:156-189
[56]M.Lothar.Theory of Genetic Algorithms.Theoretical Computer Science,2001,259(1-2):1-61
[57]Lee,W.Cheol,C.Yung.Construction of Fuzzy Systems UsingLeast-squares Method and Genetic Algorithm.Fuzzy Se ts andSystems,2003,137(3):297-2323
[58]T.Lynda,C.Ch risment,Boughanem Moh and.Multip le Query EvaluationBased on Enhanced Genetic Algorithm.Info rmation Processing and Management,2003,39(2):215-231
[59]Louis,J.Su sh il,Li Gong.Case Injected Genetic Algorithms for Traveling Salesman Problems.Information Sciences,2000,122(2-4):201-225
[60]H.Barbosa,C C.Lemonge Afonso.A New Adaptive Penalty Scheme for Genetic Algorithms.Information Sciences,2003,156(3-4):215-251
[61]J.Andre,P.Siarry,T.Dognon.An Improvement of the Standard Genetic Algorith m Fighting Pre ma ture Convergence in Continuous Optimization.Advances in Engineer-ing Software,2001,32(1):49-60
[62]C.Smith Greg,S.Smith Shana.An Enhanced Genetic Algorithm forAutomated Assembly planning.Ro botics and Computer IntegratedManufacturing,2002,18(5-6):355-364
[2]顾洪博,智能化网络试题库系统的研究与实现[D],2004年.
[3]刘彬,糜长军,李勇,智能组卷系统试题库结构的研究[J],信息技术,2003.3:2-4
[4]毛秉毅,基于遗传算法的智能组卷系统数据库结构的研究[J],计算机工程与应用,2003,28(6):230-232
[5]孙勇,柏云,基于遗传算法的试题组卷策略[J],淄博学院学报,2002,4(3):27-28
[6]石中盘,韩卫,基于概率论和自适应遗传算法的智能抽题算法[J],计算机工程,2002,28(1):141-143
[7]张爱文,樊红莲,自适应遗传算法用于自动组卷中的数学模型设计[J],哈尔滨理工大学学报,2006,11(5),18-20
[8]Win J.van der Linden,Bemard P.etal.An integer programming approach to item bank design[J],Applied Psychologieal Measuremeni,2000,24(2):139-150
[9]Huub Verstralen,Timo Beehger,Gunter Maris,The combined use of classical test and item response theory[EB/OL],http://www.cito.nl/pok/eind_fr.htm
[10]De Jong K,Spears W,Using genetic algoritms to solve NP-complete problems[C],Proeeedings of the Third International Conference on Genetic Algorithms,1989
[11]李敏强,寇纪淞,遗传算法的基本理论与应用[M],科学出版社,2003年3月
[12]余胜泉,姚顾波,何克抗.通用试题库组卷策略算法[M],1999年6月
[13]雷英杰,张善文,李续武,周创明,Mmlab遗传算法工具箱及应用[M],2005年.
[14]王力发,杨丽敏.教育统计与测量[M],哈尔滨工程大学出版社,1994年.
[15]宋兆鸿,刘世表,张才美,现代教育测量[M],北京,教育科学出版社,1986年.
[16]文娴,试题库系统智能组卷与试卷分析的研究[D],2007年.
[17]刘韶丽,基于智能组卷策略的网上考试系统的设计与实现[D],东南大学,2006年
[18]詹泽美,基于Web的网上测试系统的设计与实现[J],《荆州师范学院学报(自然科学版)》2003年4月,53-55
[19]郑刚,基于B/S模式的网上教学系统研究与设计[J],计算计工程与应用,2001,(6):33-37
[20]Wim J.vander Linden & Bernard P.&Veldkam R An integer Programming approaeh to item bank design[J].Applied Psyeho- Logieal Measurement,June2000,24(2):139-150.
[21]刘勇,康立山等,非数值并行算法-遗传算法[M],北京,科学出版社,1997.
[22]尹红卫,刘云如,易叶青一种改进的遗传算法及其在组卷系统中的应用[J].现代计算机,总第235期:66-70.
[23]李茂军,童调生,单亲遗传算法编码方式的研究[J],长沙电力学院学报(自然科学版),2000年.
[24]王淑佩,基于改进的遗传算法组卷系统应用研究[D],2005年.
[25]任世军,陈亮,遗传算法中交叉操作的改进策略[J],哈尔滨商业大学学报(自然科学版) 2006年1 0月,22(5),60-63
[26]吴晓琴,基于遗传算法的智能组卷研究[J],合肥学院学报(自然科学版),2007年5月,17(2),48-50
[27]丁卫平;管致锦;沈学华,基于遗传算法的智能组卷应用研究[J],电子电气教学学报,2005年4月,27(2),93-95
[28]贾海鹏,郑丽英,解决TSP的遗传算法初始种群改进方法研究[J],中国科技论文在线
[29]Peter J.Bentley,Jonathan P.Wakefield.An Analysis of Multiobjective optimization within Genetic Algorithms.Technical Report.1996,96:1-14.
[30]E.Zitzler,K.Deb,and L.Thiele.Comparison of multiobjective evolutionary algorithms:Empiricalresults.Evol.Comput.June 2000,2(8):173-195.
[31]N.Srinivas and Kalyanmoy Deb.Multiobjective Optimization Using the Nondominated Sorting in Genetic Algorithms.Evolutionary Computation.Feb.1994,3(2):221-248.
[32]谢涛,陈火旺.多目标优化与决策问题的演化算法.中国工程科学.Feb.2002,4:59-68.
[33]Kalvanmoy Deb,Samir Agrawal,Amrit Pratab,etc.A Fast and Elitist Multi-Objective Genetic Algorithm:NSGA-Ⅱ.IEEE Transanctions on Evolutionary Computation.April 2002,6(1):186-197.
[34]M.P.Fourman.Compaction of symbolic layout using genetic algorithms.Proceedings of the First International Conference on Genetic Algoritlums.1985,141-153
[35]公茂果,焦李成,杨咚咚,马文萍.进化多目标优化算法研究.软件学报,2009,20(2):271-289.
[36]王汉谰,教育测量学[M],河南大学出版社,1986年.
[37]刘斌,吴思和,网络题库的构建[J],现代计算机(专业版),2004年第04期.
[38]陈文伟,黄金才,赵新显.数据挖掘技术[D],北京工业大学出版社,2002
[39]王学友等.模拟电子技术试题库智能组卷算法研究与系统实现[J],电子电气教学学报,2004,26(1):85-89
[40]姜华,胡欣,李明革,题库设计与成卷系统[J],东北师大学报自然科学版,2000年9月,32(3),23-25
[41]林雪明,张钧良,蒋伟钢,基于知识点的试题库组卷算法的建立[J],微机发展,2001年2期,77-78
[42]毛秉毅,智能组卷系统的研究[J],计算机科学,2002年6月,28(6),278-279
[43]王雍钧,黄毓瑜,基于知识点题型分布和分值的智能组卷算法研究[J],计算机应用与软件,2004年8月,2l(8),111-113
[44]刘仁金,基于粒度合成计算的智能组卷策略研究[J],广西师范大学学报(自然科学版),2005年12月,23(4),32-34
[45]李长荣,杨欣宇,曲伟建,高校智能题库建设与管理研究[J],齐齐哈尔大学学报,2006年9月,22(5),84-85
[46]肖洋,王骁,刘风新,在线考试组卷算法研究[J],北京化工大学学报,2006年,33(4)
[47]周文举,基于遗传算法的自动组卷系统研究与实现[D],山东师范大学,2006年
[48]陈锋,基于遗传算法的智能组卷研究与应用[D],北方工业大学,2007年
[49]J.H.Holland.Adaption in Natural and Artificial Systems.MIT Press.1992:6-24
[50]熊辉,赵英凯,丁瑶君,基于神经网络的遗传算法优化及其应用[J],南京化工大学学报,2000年7月,22(4),21-23
[51]陈霁威,乐慧丰,黄道,基于神经网络和遗传算法的在线优化软件设计与实现[J],华东理工大学学报,2002年8期,419-420
[52]姜雷,基于遗传算法的模糊神经网络控制器设计[D],哈尔滨理工大学,2005年
[53]石中盘,韩卫,基于概率论和自适应遗传算法的智能抽题算法[J],计算机工程,2002年,28(1),141-143
[54]董敏,霍剑青,王晓蒲,基于自适应遗传算法的智能组卷研究[J],小型微型计算机系统,2004.25(1).82-85
[55]C.S.Li,P.Syu,V.Castel.li.Hierarchy Scan:A hierarchical Similari tySearch Algorithm for Databases of Long Sequences,Proc.21st Int'l Conf.Data Eng.,1996:156-189
[56]M.Lothar.Theory of Genetic Algorithms.Theoretical Computer Science,2001,259(1-2):1-61
[57]Lee,W.Cheol,C.Yung.Construction of Fuzzy Systems UsingLeast-squares Method and Genetic Algorithm.Fuzzy Se ts andSystems,2003,137(3):297-2323
[58]T.Lynda,C.Ch risment,Boughanem Moh and.Multip le Query EvaluationBased on Enhanced Genetic Algorithm.Info rmation Processing and Management,2003,39(2):215-231
[59]Louis,J.Su sh il,Li Gong.Case Injected Genetic Algorithms for Traveling Salesman Problems.Information Sciences,2000,122(2-4):201-225
[60]H.Barbosa,C C.Lemonge Afonso.A New Adaptive Penalty Scheme for Genetic Algorithms.Information Sciences,2003,156(3-4):215-251
[61]J.Andre,P.Siarry,T.Dognon.An Improvement of the Standard Genetic Algorith m Fighting Pre ma ture Convergence in Continuous Optimization.Advances in Engineer-ing Software,2001,32(1):49-60
[62]C.Smith Greg,S.Smith Shana.An Enhanced Genetic Algorithm forAutomated Assembly planning.Ro botics and Computer IntegratedManufacturing,2002,18(5-6):355-364