1. A Divide-and-Conquer Tabu Search Approach for Online Test Paper Generation
- Author
-
Minh Luan Nguyen, Siu Cheung Hui, and Alvis C. M. Fong
- Subjects
Divide and conquer algorithms ,Optimization problem ,business.industry ,Computer science ,Constraint satisfaction ,Machine learning ,computer.software_genre ,Swarm intelligence ,Multi-objective optimization ,Tabu search ,Dynamic programming ,Constraint (information theory) ,Artificial intelligence ,business ,computer - Abstract
Online Test Paper Generation (Online-TPG) is a promising approach for Web-based testing and intelligent tutoring. It generates a test paper automatically online according to user specification based on multiple assessment criteria, and the generated test paper can then be attempted over the Web by user for self-assessment. Online-TPG is challenging as it is a multi-objective optimization problem on constraint satisfaction that is NP-hard, and it is also required to satisfy the online runtime requirement. The current techniques such as dynamic programming, tabu search, swarm intelligence and biologically inspired algorithms are ineffective for Online-TPG as these techniques generally require long runtime for generating good quality test papers. In this paper, we propose an efficient approach, called DAC-TS, which is based on the principle of constraint-based divide-and-conquer (DAC) and tabu search (TS) for constraint decomposition and multi-objective optimization for Online-TPG. Our empirical performance results have shown that the proposed DAC-TS approach has outperformed other techniques in terms of runtime and paper quality.
- Published
- 2011