Collective Biobjective Optimization Algorithm for Parallel Test Paper Generation

Minh Luan Nguyen, Siu Cheung Hui, Alvis Cheuk Ming FongIJCAI 2015

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 5-step pipeline of the CBO algorithm for parallel test paper generation.

The algorithm follows a robust 5-step pipeline:

  1. Optimal Fairness Estimation: Employs binary search to identify the highest achievable target quality ($\phi$).
  2. Infeasible Allocation Detection: A rapid greedy check to determine if the target quality is feasible under given constraints.
  3. Total Quality Maximization: A greedy selection process that respects multiple knapsack constraints (e.g., topic distribution, question types).
  4. Fairness Quality Balancing: A swapping mechanism that redistributes high-quality questions from over-performing to under-performing papers.
  5. 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.

Average time to generate parallel test papers across different algorithms.

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

BibTeX
@inproceedings{nguyen2015collective,
  author = {Minh Luan Nguyen and Siu Cheung Hui and Alvis Cheuk Ming Fong},
  title = {{Collective Biobjective Optimization Algorithm for Parallel Test Paper Generation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure