Abstract
Generating multiple high-quality, fair test papers from large question banks is a critical challenge for large-scale online education. This paper introduces the Collective Biobjective Optimization (CBO) algorithm, a novel approach that leverages the mathematical properties of submodular functions to solve the Parallel Test Paper Generation ($k$-TPG) problem. Unlike traditional meta-heuristics, CBO provides theoretical performance guarantees and achieves significantly faster runtimes. Experimental results on large-scale datasets demonstrate that CBO can generate up to 20 parallel papers in under 6 minutes, outperforming existing methods in both speed and paper quality.
Introduction
In the era of Massive Open Online Courses (MOOCs), instructors frequently need to generate multiple equivalent versions of an exam to prevent cheating and ensure assessment integrity. This task, known as Parallel Test Paper Generation ($k$-TPG), involves two conflicting objectives: maximizing the Total Quality (Welfare) of all papers and ensuring Fairness (equivalence in difficulty and quality) across the set.
As question databases grow to tens of thousands of items, $k$-TPG becomes an NP-hard problem. Traditional heuristic methods like Ant Colony Optimization (ACO) or Particle Swarm Optimization (PSO) often struggle with scalability or get trapped in local optima, leading to inconsistent paper quality or prohibitive computation times.
The CBO Algorithm
The core innovation of the CBO algorithm is the reformulation of the biobjective problem into a single objective using truncated submodular functions. By recognizing that test paper quality follows the principle of diminishing returns—a property known as submodularity—the authors developed a structured approximation framework.
The algorithm follows a robust 5-step pipeline:
- Optimal Fairness Estimation: Employs binary search to identify the highest achievable target quality ($\phi$).
- Infeasible Allocation Detection: A rapid greedy check to determine if the target quality is feasible under given constraints.
- Total Quality Maximization: A greedy selection process that respects multiple knapsack constraints (e.g., topic distribution, question types).
- Fairness Quality Balancing: A swapping mechanism that redistributes high-quality questions from over-performing to under-performing papers.
- Local Constraint Improvement: A final refinement step using local search to satisfy strict constraints like total exam time and average difficulty.
Experimental Evaluation
The authors evaluated CBO using four large-scale synthetic datasets ($D_1$ to $D_4$), ranging from 20,000 to 50,000 questions. These datasets simulated various real-world distributions (Uniform and Normal) for question attributes.
Performance and Scalability
CBO was compared against three popular meta-heuristics: $k$-TS (Tabu Search), $k$-PSO, and $k$-ACO. The results highlight a dramatic improvement in computational efficiency.
As shown in the performance metrics, CBO maintains a nearly linear and low runtime even as the number of parallel papers ($k$) increases. While competing algorithms often required 30 to 45 minutes to generate 20 papers, CBO consistently completed the task in under 6 minutes.
Quality and Constraint Satisfaction
Beyond speed, CBO produced superior results in terms of paper quality and fairness. It achieved a higher Mean Discrimination Degree and a lower Deviate Discrimination Degree, indicating that the papers were both higher quality and more uniform than those produced by heuristics. Furthermore, CBO showed significantly lower constraint violation scores, especially as the number of required papers grew.
Conclusion
The CBO algorithm represents a significant advancement in automated test generation. By utilizing submodularity, it moves beyond the randomness of traditional heuristics to provide a framework with provable performance guarantees ($1/2$ approximation for quality and $1/6$ for fairness). While the current implementation relies on local search for certain constraints, the overall efficiency and quality make it a powerful tool for modern educational platforms.
Summary updated