Exploring Multiple-Objective Optimization for Efficient and Effective Test Paper Design with Dynamic Programming Guided Genetic Algorithm

Han Wang; Qingfeng Zhuge; Edwin Hsing-Mean Sha; Jianghua Xia; Rui Xu; Han Wang; Qingfeng Zhuge; Edwin Hsing-Mean Sha; Jianghua Xia; Rui Xu

doi:10.3934/mbe.2024162

Mathematical Biosciences and Engineering

2024, Volume 21, Issue 3: 3668-3694. doi: 10.3934/mbe.2024162

Previous Article Next Article

Research article Special Issues

Exploring Multiple-Objective Optimization for Efficient and Effective Test Paper Design with Dynamic Programming Guided Genetic Algorithm

1.
School of Computer Science and Technology, East China Normal University, Shanghai 200062, China
2.
Shanghai Institute of AI for Education, East China Normal University, Shanghai 200062, China
3.
Department of Computer Science, City University of Hong Kong, Hong Kong, China

Received: 05 December 2023 Revised: 17 January 2024 Accepted: 29 January 2024 Published: 18 February 2024

Automatic test paper design is critical in education to reduce workloads for educators and facilitate an efficient teaching process. However, current designs fail to satisfy the realistic teaching requirements of educators, including the consideration of both test quality and efficiency. This is the main reason why teachers still manually construct tests in most teaching environments. In this paper, the quality of tests is quantitatively defined while considering multiple objectives, including a flexible coverage of knowledge points, cognitive levels, and question difficulty. Then, a model based on the technique of linear programming is delicately designed to explore the optimal results for this newly defined problem. However, this technique is not efficient enough, which cannot obtain results in polynomial time. With the consideration of both test quality and generation efficiency, this paper proposes a genetic algorithm (GA) based method, named dynamic programming guided genetic algorithm with adaptive selection (DPGA-AS). In this method, a dynamic programming method is proposed in the population initialization part to improve the efficiency of the genetic algorithm. An adaptive selection method for the GA is designed to avoid prematurely falling into the local optimal for better test quality. The question bank used in our experiments is assembled based on college-level calculus questions from well-known textbooks. The experimental results show that the proposed techniques can construct test papers with both high effectiveness and efficiency. The computation time of the test assembly problem is reduced from 3 hours to 2 seconds for a 5000-size question bank as compared to a linear programming model with similar test quality. The test quality of the proposed method is better than the other baselines.
- automated test paper design,
- multiple objectives optimization,
- linear programming,
- dynamic programming,
- genetic algorithm
Citation: Han Wang, Qingfeng Zhuge, Edwin Hsing-Mean Sha, Jianghua Xia, Rui Xu. Exploring Multiple-Objective Optimization for Efficient and Effective Test Paper Design with Dynamic Programming Guided Genetic Algorithm[J]. Mathematical Biosciences and Engineering, 2024, 21(3): 3668-3694. doi: 10.3934/mbe.2024162

Related Papers:

Abstract

Automatic test paper design is critical in education to reduce workloads for educators and facilitate an efficient teaching process. However, current designs fail to satisfy the realistic teaching requirements of educators, including the consideration of both test quality and efficiency. This is the main reason why teachers still manually construct tests in most teaching environments. In this paper, the quality of tests is quantitatively defined while considering multiple objectives, including a flexible coverage of knowledge points, cognitive levels, and question difficulty. Then, a model based on the technique of linear programming is delicately designed to explore the optimal results for this newly defined problem. However, this technique is not efficient enough, which cannot obtain results in polynomial time. With the consideration of both test quality and generation efficiency, this paper proposes a genetic algorithm (GA) based method, named dynamic programming guided genetic algorithm with adaptive selection (DPGA-AS). In this method, a dynamic programming method is proposed in the population initialization part to improve the efficiency of the genetic algorithm. An adaptive selection method for the GA is designed to avoid prematurely falling into the local optimal for better test quality. The question bank used in our experiments is assembled based on college-level calculus questions from well-known textbooks. The experimental results show that the proposed techniques can construct test papers with both high effectiveness and efficiency. The computation time of the test assembly problem is reduced from 3 hours to 2 seconds for a 5000-size question bank as compared to a linear programming model with similar test quality. The test quality of the proposed method is better than the other baselines.

References

[1]	K. Naik, S. Sule, S. Jadhav, S. Pandey, Automatic question paper generation system using randomization algorithm, Int. J. Eng. Tech. Res. (IJETR), 2 (2014), 192–194.
[2]	W. J. Linden, Linear models for optimal test design, Springer, (2005). https://doi.org/10.1007/0-387-29054-0_3
[3]	W. J. Linden, Review of the shadow-test approach to adaptive testing, Behaviormetrika, (2021), 1–22. https://doi.org/10.1007/s41237-021-00150-y doi: 10.1007/s41237-021-00150-y
[4]	K. Zhang, L. Zhu, Application of improved genetic algorithm in automatic test paper generation, in 2015 Chinese Automation Congress (CAC), (2015), 495–499. https://doi.org/10.1109/cac.2015.7382551
[5]	T. N. T. A. Rahim, Z. A. Aziz, R. H. A. Rauf, N. Shamsudin, Automated exam question generator using genetic algorithm, in 2017 IEEE Conference on e-Learning, e-Management and e-Services (IC3e), (2017), 12–17. https://doi.org/10.1109/ic3e.2017.8409231
[6]	T. Nguyen, T. Bui, H. Fujita, T.-P. Hong, H. D. Loc, V. Snasel, et al., Multiple-objective optimization applied in extracting multiple-choice tests, Eng. Appl. Artif. Intell., 105 (2021), 104439. https://doi.org/10.1016/j.engappai.2021.104439 doi: 10.1016/j.engappai.2021.104439
[7]	Z. Wu, T. He, C. Mao, C. Huang, Exam paper generation based on performance prediction of student group, Inform. Sci., 532 (2020), 72–90. https://doi.org/10.1016/j.ins.2020.04.043 doi: 10.1016/j.ins.2020.04.043
[8]	M. Aktaş, Z. Yetgin, F. Kılıç, Ö. Sünbül, Automated test design using swarm and evolutionary intelligence algorithms, Expert Syst., 39 (2022). https://doi.org/10.1111/exsy.12918 doi: 10.1111/exsy.12918
[9]	N. H. I. Teo, N. A. Bakar, M. R. A. Rashid, Representing examination question knowledge into genetic algorithm, in 2014 IEEE Global Engineering Education Conference (EDUCON), (2014), 900–904. https://doi.org/10.1109/educon.2014.6826203
[10]	Z. Jia, C. Zhang, H. Fang, The research and application of general item bank automatic test paper generation based on improved genetic algorithms, in 2011 IEEE 2nd International Conference on Computing, Control and Industrial Engineering, 1 (2011), 14–18. https://doi.org/10.1109/ccieng.2011.6007945
[11]	M. Yildirim, A genetic algorithm for generating test from a question bank, Computer Appl. Eng. Educ., 18 (2010), 298–305. https://doi.org/10.1002/cae.20260 doi: 10.1002/cae.20260
[12]	M. Shao, W. Li, J. Du, The research and implementation of technology of generating test paper based on genetic algorithm, in Intelligence Computation and Evolutionary Computation: Results of 2012 International Conference of Intelligence Computation and Evolutionary Computation (ICEC), (2013), 657–663. https://doi.org/10.1109/mines.2012.232
[13]	L. Han, X. Li, The analysis of exam paper component based on genetic algorithm, in 2014 Fourth International Conference on Communication Systems and Network Technologies, (2014), 561–564. https://doi.org/10.1109/csnt.2014.118
[14]	Y. Zhang, J. Zhang, P. Wang, Research and implementation of intelligent test paper composition based on genetic algorithm, in 2018 9th International Conference on Information Technology in Medicine and Education (ITME), (2018), 552–556. https://doi.org/10.1109/itme.2018.00128
[15]	D. Liu, J. Wang, L. Zheng, Automatic test paper generation based on ant colony algorithm, J. Softw., 8 (2013), 2600–2606. https://doi.org/10.4304/jsw.8.10.2600-2606 doi: 10.4304/jsw.8.10.2600-2606
[16]	T. Nguyen, T. Bui, B. Vo, Multi-swarm single-objective particle swarm optimization to extract multiple-choice tests, Vietnam J. Computer Sci., 6 (2019), 147–161. https://doi.org/10.1142/s219688881950009x doi: 10.1142/s219688881950009x
[17]	K. O. Jones, J. Harland, J. M. Reid, R. Bartlett, Relationship between examination questions and bloom's taxonomy, in 2009 39th IEEE frontiers in education conference, (2009), 1–6. https://doi.org/10.1109/fie.2009.5350598
[18]	S. Bloxham, P. Boyd, Developing effective assessment in higher education: A practical guide, McGraw-Hill Education (UK), (2007).
[19]	N. Utaberta, B. Hassanpour, Aligning assessment with learning outcomes, Procedia-Social Behav. Sci., 60 (2012), 228–235. https://doi.org/10.1016/j.sbspro.2012.09.372 doi: 10.1016/j.sbspro.2012.09.372
[20]	A. Smith, S. L.-Munk, A. Shelton, B. Mott, E. Wiebe, J. Lester, A multimodal assessment framework for integrating student writing and drawing in elementary science learning, IEEE Transact. Learn. Technol., 12 (2018), 3–15. https://doi.org/10.1109/tlt.2018.2799871 doi: 10.1109/tlt.2018.2799871
[21]	A. Alammary, LOsMonitor: A machine learning tool for analyzing and monitoring cognitive levels of assessment questions, IEEE Transact. Learn. Technol., 14 (2021), 64–652. https://doi.org/10.1109/tlt.2021.3116952 doi: 10.1109/tlt.2021.3116952
[22]	A. J. Swart, Evaluation of final examination papers in engineering: A case study using bloom's taxonomy, IEEE Transact. Educ., 53 (2009), 257–264. https://doi.org/10.1109/te.2009.2014221 doi: 10.1109/te.2009.2014221
[23]	B. S. Bloom, M. D. Englehard, Committee of College and University Examiners, Taxonomy Educ. Object., Longmans, 2 (1964).
[24]	L. W. Anderson, D. R. Krathwohl, A taxonomy for learning, teaching, and assessing: A revision of Bloom's taxonomy of educational objectives, Addison Wesley Longman, (2001).
[25]	L. Smith, J. King, A dynamic systems approach to wait time in the second language classroom, System, 68 (2017), 1–14. https://doi.org/10.1016/j.system.2017.05.005 doi: 10.1016/j.system.2017.05.005
[26]	M. Riojas, S. Lysecky, J. Rozenblit, Educational technologies for precollege engineering education, IEEE Transact. Learn. Technol., 5 (2011), 20–37. https://doi.org/10.1109/tlt.2011.16 doi: 10.1109/tlt.2011.16
[27]	F. K. Gangar, H. G. Gori, A. Dalvi, Automatic question paper generator system, Int. J. Computer Appl., 166 (2017), 42–47. https://doi.org/10.5120/ijca2017914138 doi: 10.5120/ijca2017914138
[28]	V. S. Rao, V. C. Sai, S. S. Sandeep, MV Jayadeep, Automated exam paper process based on schedule and authenticity, in International Conference of Advance Research & Innovation(ICARI), (2020). https://doi.org/10.2139/ssrn.3643880
[29]	M. S. R. Chim, G. V. Kale, Automatic question paper generation using parametric randomization, J. Gujarat Res. Soc., 21 (2019), 444-451.
[30]	S. A. El-Rahman, A. H. Zolait, Automated test paper generation using utility based agent and shuffling algorithm, Int. J. Web-based Learn. Teach. Technol. (IJWLTT), 14 (2019), 69–83. https://doi.org/10.4018/ijwltt.2019010105 doi: 10.4018/ijwltt.2019010105
[31]	J. H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, MIT press, (1992).
[32]	M. Dorigo, V. Maniezzo, A. Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Transact. Syste. Man Cybernet., 26 (1996), 29–41. https://doi.org/10.1109/3477.484436 doi: 10.1109/3477.484436
[33]	J. Kennedy, R. Eberhart, Particle swarm optimization, in Proceedings of ICNN'95-international conference on neural networks, 4 (1995), 1942-1948.
[34]	S. Mirjalili, S. M. Mirjalili, A. Lewis, Grey wolf optimizer, Adv. Eng. Software, 69 (2014), 46–61. https://doi.org/10.1016/j.advengsoft.2013.12.007 doi: 10.1016/j.advengsoft.2013.12.007
[35]	A. A. Heidari, S. Mirjalili, H. Faris, I. Aljarah, M. Mafarja, H. Chen, Harris hawks optimization: Algorithm and applications, Future Gener. Comput. Syst., 97 (2019), 849–872. https://doi.org/10.1016/j.future.2019.02.028 doi: 10.1016/j.future.2019.02.028
[36]	B. Abdollahzadeh, F. S. Gharehchopogh, S. Mirjalili, African vultures optimization algorithm: A new nature-inspired metaheuristic algorithm for global optimization problems, Comput. Indust. Eng., 158 (2021), 107408. https://doi.org/10.1016/j.cie.2021.107408 doi: 10.1016/j.cie.2021.107408
[37]	X. Bao, H. Jia, C. Lang, A novel hybrid harris hawks optimization for color image multilevel thresholding segmentation, IEEE Access, 7 (2019), 76529–76546. https://doi.org/10.1109/access.2019.2921545 doi: 10.1109/access.2019.2921545
[38]	Y. Xiao, Y. Guo, H. Cui, Y. Wang, J. Li, Y. Zhang, IHAOAVOA: An improved hybrid aquila optimizer and african vultures optimization algorithm for global optimization problems, Math. Biosci. Eng., 19 (2022), 10963–11017. https://doi.org/10.3934/mbe.2022512 doi: 10.3934/mbe.2022512
[39]	J. Liu, Y. Wang, N. Fan, S. Wei, W. Tong, A convergence-diversity balanced fitness evaluation mechanism for decomposition-based many-objective optimization algorithm, Integr. Computer-Aided Eng., 26 (2019), 159–184. https://doi.org/10.3233/ica-180594 doi: 10.3233/ica-180594
[40]	J. Liu, Y. Wang, Y. Cheung, A c$\alpha$-dominance-based solution estimation evolutionary algorithm for many-objective optimization, Knowledge-based Syst., 248 (2022), 108738. https://doi.org/10.1016/j.knosys.2022.108738 doi: 10.1016/j.knosys.2022.108738
[41]	W. Li, H. Pu, P. Schonfeld, J. Yang, H. Zhang, L. Wang, et al., Mountain railway alignment optimization with bidirectional distance transform and genetic algorithm, Computer-Aided Civil Infrastruct. Eng., 32 (2017), 691–709. https://doi.org/10.1111/mice.12280 doi: 10.1111/mice.12280
[42]	M. Wei, S. Zhang, T. Liu, B. Sun, The adjusted passenger transportation efficiency of nine airports in China with consideration of the impact of high-speed rail network development: A two-step DEA-OLS method, J. Air Transport Manag., 109 (2023), 102395. https://doi.org/10.1016/j.jairtraman.2023.102395 doi: 10.1016/j.jairtraman.2023.102395
[43]	J. L. Gordon, Creating knowledge maps by exploiting dependent relationships, in Appl. Innovat. Intell. Syst. VII, (2000), 64–78. https://doi.org/10.1007/978-1-4471-0465-0_5
[44]	N. Henze, W. Nejdl, Logically characterizing adaptive educational hypermedia systems, in International Workshop on Adaptive Hypermedia and Adaptive Web-based Systems (AH 2003), (2003), 20–24. https://doi.org/10.1080/13614560410001728128
[45]	M. Nickel, K. Murphy, V. Tresp, E. Gabrilovich, A review of relational machine learning for knowledge graphs, Proceed. IEEE, 104 (2015), 11–33. https://doi.org/10.1109/jproc.2015.2483592 doi: 10.1109/jproc.2015.2483592
[46]	Q. Liu, Z. Huang, Y. Yin, E. Chen, H. Xiong, Y. Su, et al., Ekt: Exercise-aware knowledge tracing for student performance prediction, IEEE Transact. Knowledge Data Eng., 33 (2019), 100–115. https://doi.org/10.1109/tkde.2019.2924374 doi: 10.1109/tkde.2019.2924374
[47]	J. D. L. Torre, Dina model and parameter estimation: A didactic, J. Educ. Behav. Statist., 34 (2009), 115–130. https://doi.org/10.3102/1076998607309474 doi: 10.3102/1076998607309474
[48]	T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, MIT press, (2009).
[49]	Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual, (2023).
[50]	D. H. Hallett, A. M. Gleason, W. G. McCallum, Calculus: Single and multivariable, John Wiley and Sons Inc, (1998).
[51]	D. C. Webb, Bloom's Taxonomy in Mathematics Education, Encyclopedia of Mathematics Education, Springer Netherlands, (2014), 63–68. https://doi.org/10.1007/978-94-007-4978-8_17

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)