Collective Biobjective Optimization Algorithm for Parallel Test Paper Generation
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 418-423.
© 2015 International Joint Conferences on Artificial Intelligence
Abstract
Parallel Test Paper Generation (k-TPG) is a biobjective distributed resource allocation problem, which aims to generate multiple similarly optimal test papers automatically according to multiple user-specified criteria.Generating high-quality parallel test papers is challenging due to its NP-hardness in maximizing the collective objective functions.In this paper, we propose a Collective Biobjective Optimization (CBO) algorithm for solving k-TPG. CBO is a multi-step greedy-based approximation algorithm, which exploits the submodular property for biobjective optimization of k-TPG.Experiment results have shown that CBO has drastically outperformed the current techniques in terms of paper quality and runtime efficiency.
- [Asadpour and Saberi, 2010] A. Asadpour and A. Saberi. An ap- proximation algorithm for max-min fair allocation of indivisible goods. SIAM Journal on Computing, 39(7):2970-2989, 2010.
- [Asadpour et al., 2008] A. Asadpour, U. Feige, and A. Saberi. Santa claus meets hypergraph matchings. Approximation, Ran- domization and Combinatorial Optimization. Algorithms and Techniques, pages 10-20, 2008.
- [Azar and Gamzu, 2012] Yossi Azar and Iftah Gamzu. Efficient submodular function maximization under linear packing con- straints. In Automata, Languages, and Programming, pages 38- 50. Springer, 2012.
- [Bertsimas et al., 2011] D. Bertsimas, V. F. Farias, and N. Trichakis. The price of fairness. Operations research, 59(1):17-31, 2011.
- [Feige and Vondrak, 2006] U. Feige and J. Vondrak. Approxima- tion algorithms for allocation problems: Improving the factor of 1-1/e. In 47th Annual IEEE Symposium on Foundations of Com- puter Science, pages 667-676, 2006.
- [Feige et al., 2007] U. Feige, V.S. Mirrokni, and J. Vondrak. Max- imizing non-monotone submodular functions. SIAM Journal on Computing, 40(4):1133-1153, 2007.
- [Fujishige, 2005] S. Fujishige. Submodular functions and opti- mization. Elsevier Science, 2005.
- [Ho et al., 2008] T. F. Ho, P. Y. Yin, G. J. Hwang, S. J. Shyu, and Y. N. Yean. Multi-objective parallel test-sheet composition using enhanced particle swarm optimization. Journal of Educational Technology and Society, 12(4):193-206, 2008.
- [Hu et al., 2009] X. M. Hu, J. Zhang, H. S. H. Chung, O. Liu, and J. Xiao. An intelligent testing system embedded with an ant-colony-optimization-based test composition method. IEEE Transactions on Systems, Man, and Cybernetics, 39(6):659-669, 2009.
- [Hwang et al., 2008] G. J. Hwang, H. C. Chu, P. Y. Yin, and J. Y. Lin. An innovative parallel test sheet composition approach to meet multiple assessment criteria for national tests. Computers and Education, 51(3):1058-1072, 2008.
- [Ishibuchi et al., 2008] H. Ishibuchi, N. Tsukamoto, and Y. No- jima. Evolutionary many-objective optimization: A short review. In IEEE World Congress on Evolutionary Computation, pages 2419-2426, 2008.
- [Lovasz, 1983] L. Lovasz. Submodular functions and convexity. Mathematical programming: the state of the art, pages 235-257, 1983.
- [Martin, 2012] F. G. Martin. Will massive open online courses change how we teach? Communication of the ACM, 55(8):26- 28, August 2012.
- [Nedic et al., 2010] A. Nedic, A. Ozdaglar, and P. A. Parrilo. Con- strained consensus and optimization in multi-agent networks. IEEE Transactions on Automatic Control, 55(4):922-938, 2010.
- [Nguyen et al., 2013] M. L. Nguyen, S. C. Hui, and A. C. M. Fong. Large-scale multiobjective static test generation for web-based testing with integer programming. IEEE Transactions on Learn- ing Technologies, 6(1):46-59, 2013.
- [Sviridenko, 2004] M. Sviridenko. A note on maximizing a sub- modular set function subject to a knapsack constraint. Opera- tions Research Letters, 32(1):41-43, 2004.
- [Vondrak, 2008] J. Vondrak. Optimal approximation for the sub- modular welfare problem in the value oracle model. In Proceed- ings of the 40th annual ACM symposium on Theory of comput- ing, pages 67-74, 2008.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
With the rapid growth of the Internet and mobile devices, Webbased education has become a ubiquitous learning platform in many institutions to provide students with online learning courses and materials through freely accessible educational websites such as Khan Academy, or online classes such as Coursera and Udacity. To make learning effective, it is important to assess the proficiency of the students while they are learning the concepts. As there may have many students in an online class [Martin, 2012], to ensure the assessment reliability of large-scale Web-based testing, pedagogical practitioners have suggested that it is necessary to compose multiple tests from a large question pool with equivalent properties. One promising approach to support large-scale Web-based testing is parallel test paper generation (k-TPG), which generates k similarly optimal test papers automatically according to a user specification based on multiple criteria. Specifically, it aims to find k disjoint subsets of questions from a question database to form multiple test papers according to a user specification based on total time, topic distribution, difficulty degree, discrimination degree, and so on.
k-TPG is a challenging problem especially with large number of questions and large number of generated test papers (i.e. large k) due to its NP-hardness. Different from other multiobjective optimization problems, k-TPG has collective Alvis C. M. Fong School of Computing Science University of Glasgow Scotland, UK
objective functions to be defined based on the evaluation objectives of k generated test papers instead of a single test paper. In fact, k-TPG is close to the spirit of optimal distributed allocation problems [Feige and Vondrak, 2006] with collective objective functions. Formally, k-TPG is a biobjective optimal distributed resource allocation problem, which aims to simultaneously maximize two objective functions under a multidimensional Knapsack constraint. The first objective can be formulated as a Welfare Allocation problem [Vondrak, 2008], which aims to maximize the total quality of the generated test papers. The second objective can be formulated as a Fairness Allocation problem [Asadpour and Saberi, 2010; Bertsimas et al., 2011], which aims to maximize the fairness quality of the generated test papers. Traditionally, optimizing these two objectives is NP-hard and considered separately. To the best of our knowledge, there has been no attempt to solve both of the objectives simultaneously.
Submodular-based approximation algorithms, which are polynomial time algorithms that have performance guarantees, have been studied for distributed optimization problems [Nedic et al., 2010]. Inspired by this novel idea, we propose a greedy-based approximation algorithm, called Collective Biobjective Optimization (CBO), for k-TPG. The key idea of CBO is twofold. Firstly, it analyzes the properties of the two collective objectives and reformulates the k-TPG problem such that it can be solved effectively. Secondly, we propose an effective multi-step framework for the reformulated optimization problem. More importantly, we exploit submodular optimization techniques to design greedy-based approximation algorithms for enhancing each step in the proposed framework. In this paper, we will discuss the proposed CBO algorithm for k-TPG and its performance evaluation.
2 RelatedWork
For the past few years, heuristic-based intelligent techniques such as Tabu Search [Hwang et al., 2008], Particle Swarm Optimization [Ho et al., 2008] and Ant Colony Optimization [Hu et al., 2009] have been proposed for k-TPG. However, the quality of the generated parallel test papers is often unsatisfactory [Hwang et al., 2008; Ho et al., 2008; Hu et al., 2009] according to users' test paper specifications. The main issue of the current techniques is the exhaustive search to optimize the biobjective functions simultaneously in the very large space of possible candidates with multicriteria constraints. Although these heuristic-based techniques are straightforward to implement, they suffer from some drawbacks. They tend to get stuck in a local optimum as they are mainly based on traditional weighting parameters for multiobjective optimization [Ishibuchi et al., 2008].
3 Parallel Test Paper Generation
Let Q = {q1, q2, .., qn} be a dataset consisting of n questions, C = {c1, c2, .., cm} be a set of m different topics, and Y = {y1, y2, .., yk} be a set of k different question types. Each question qi ∈ Q, where i ∈ {1, 2, .., n}, has 6 attributes A = {q, e, t, d, c, y} defined as follows:
- Question q: It is used to store the question identity.
- Discrimination degree e: It is a positive integer value to distinguish user proficiency.
- Question time t: It is a positive integer value to indicate the average time in minutes needed to answer.
- Difficulty degree d: It is a positive integer value to indicate the question difficulty.
- Related topic c: It is a set of related topics of a question.
- Question type y: It is the type of a question.
A test paper specification S = 〈N, T,D,C, Y 〉 consists of 5 attributes including the number of questions N, total time T, average difficulty degree D, topic distribution C = {(c1, pc1), (c2, pc2), .., (cM, pcM)} and question type distribution Y = {(y1, py1), (y2, py2), .., (yK, pyK)}, which are defined based on the attributes of the selected questions.
In 1-TPG, it selects an optimal subset of questions to form a test paper P , which maximizes the average discrimination degree f(P) = 1N ∑Ni=1 ei, qi ∈ P while satisfying multiple user-specified criteria in a test paper specification SP = S.
In k-TPG, user specification is given as a pair of 〈k, S〉, where k is an integer parameter in addition to the test paper specification S. The k-TPG aims to select k disjoint subsets of questions P1, P2, .., Pk from the question dataset Q to form k test papers with specification SPi , which satisfies the test paper specification such that SPi = S, ∀i ∈ [1, k]. Apart from maximizing the objective function as in single test paper generation, k-TPG aims to generate the k test papers with similar optimal quality according to the specification. It aims to provide similar quality of test papers for different users. As such, there are two important collective objective functions that need to be maximized in k-TPG: total quality maximization and fairness quality maximization.
Total Quality Maximization. It aims to maximize the sum of discrimination degrees of k test papers ∑ki=1 f(Pi), where f(Pi) is the discrimination degree of test paper Pi, i ∈ [1, k]. Formally, the k-TPG problem is stated as follows:
Fairness Quality Maximization. It aims to maintain the fairness among the generated test papers with equivalent discrimination degrees. However, solely maximizing the total quality objective does not guarantee the fairness quality. According to [Asadpour et al., 2008; Bertsimas et al., 2011] , it is more effective to optimize a fair allocation of the discrimination degrees of k generated test papers as:
subject to the local multicriteria constraints:
4 Proposed CBOApproach
To simultaneously optimize the total quality and fairness quality objective functions is a challenging problem. However, by exploiting the relationship between the two objective functions based on the submodular property [Lovasz, 1983], we can devise an effective and efficient approach.
4.1 ProblemReformulation
Before reformulating the k-TPG problem, we review the fundamental concept of submodular function in optimization.
Definition 1 (Submodular Function Optimization). Given a set X, a non-negative function f : 2X → R+, T ⊆ X, and x ∈ X. Let ∂f(S) ∂x = △f(x|S) = f(S ∪ {x}) - f(S) be the decreasing marginal value of f at S with respect to x. A non-negative function f : 2X → R+ is submodular if for every set S, T ⊆ X, we have:
Although NP-hard, the submodular property has led to the existence of a Greedy-based Approximation Algorithm [Fujishige, 2005] for the maximization. It is widely known that a linear function as well as the combination of linear functions are aslo submodular [Fujishige, 2005]. [Nguyen et al., 2013] shows that 1-TPG can be reformulated as an integer linear program which aims to maximize a linear objective function f(P) under multiple knapsack constraints. Hence, the quality function f(P) is submodular due to the linearity property.
Lemma 1. Given a test paper P generated from a question set Q (P ⊆ Q), the quality evaluation function of discrimination degree f(P) : 2Q → R+ is submodular and monotone.
Hence, the total quality objective function is also submodular due to a linear combination of k submodular functions.
Corollary 1. The total quality objective function of k test papers ∑ki=1 f (Pi), Pi ⊆ Q is submodular and monotone.
To jointly optimize the biobjective functions, we take the advantage of submodularity to reformulate the total quality objective such that it also integrates the fairness objective.
Let fφ(P ) = min{f (P ), φ} be a truncated function, where φ is a non-negative constant. Note that fφ(P) is also submodular and monotone due to [Fujishige, 2005]. For any constant φ, we have the following important observation:
As k is a constant, this means that the fairness quality objective value of a paper is larger than or equal to φ if the total quality objective value is kφ and vice versa. Therefore, we have the following result in Theorem 1:
Theorem 1. Given the optimal fairness value φ∗ , i.e., maxP1,..,Pk minl f(Pl) = φ∗ , then it is sufficient to jointly optimize the two objective functions of the original k-TPG problem by solving the following equivalent problem: g-17pt
Proof Sketch: The original k-TPG problem is equivalent to the problem given in (6) since, by (5), there exists k test papers P1, .., Pk such that ∑kl=1 fφ∗(Pl) = kφ∗ . In addition, because of the property of the truncated function fφ∗(Pl), we have max ∑kl=1 fφ∗(Pl) ≤ kφ∗ . Thus, for any optimal generated papers P1, .., Pk of the problem in (6), it must satisfy that ∑kl=1 fφ∗ (Pl) = kφ∗ . Hence, we have minl f (P ∗ l ) = φ∗ due to (5).
4.2 Collective Biobjective Optimization
In this paper, we propose a novel Collective Biobjective Optimization (CBO) approach for k-TPG. We observe that the reformulated problem (6) can be solved effectively by an iterative multi-step framework. More importantly, we exploit the submodular optimization technique to design greedy-based approximation algorithm for enhancing the steps in the proposed approach. Figure 1 shows the 5 main steps of the CBO approach: Optimal Fairness Value Estimation, Infeasible Allocation Detection, Total Quality Maximization, Fairness Quality Balancing and Local Constraint Improvement.
In the first step, after each feedback loop, CBO either: (1) reduces half of the search space on φ if Infeasible Allocation Detection fails or (2) finds a better solution in terms of both of the objectives. In the remaining 4 steps, CBO will generate k test papers progressively by using the greedy-based algorithm for 1-TPG and adjusting the fairness value φ. Due to NPhardness of 1-TPG, when φ approaches its optimal value, we can only achieve a fraction β ≤ 1 of the optimal objective value of φ, where β is a constant that will be determined in Section 4.6. As such, our goal is to allocate questions into k test papers such that for all k papers, we have fφ(Pl) ≥ βφ, ∀l = 1..k.
4.3 Optimal Fairness Value Estimation
In each iteration, a new set of k papers will be generated according to a new fairness value φ. This step aims to find a new optimal value of φ to continue the co-optimization process. Generally we do not know the optimal value φ∗ . Therefore, we need to search for it using the binary search strategy, starting with the interval [φmin, φmax] = [0, N ×max q∈Q f(q)]. In each
step, we test the center φ = (φmin + φmax)/2 of the current interval [φmin, φmax] of possible fairness value.
4.4 Infeasible Allocation Detection
This step aims to detect whether it is possible to generate k test papers such that fφ(Pl) ≥ βφ, ∀l = 1..k. Specifically, it checks whether the estimated value of φ is appropriate or not. To overcome this, we propose a greedy-based approximation T�
3XEOLF 6WRUH
'HWHUPLQLQJ WKH
1XPEHU RI 4XHVWLRQV
,PSURYHPQHW Process:
,QLWLDO 3RSXODWLRQ
*HQHUDWLRQ

SURWRW\SH DSSUR[LPDWH
WHVW SDSHUV
�)DLUQHVV 4XDOLW\�
/RFDO 6HDUFK LQLWLDO WHVW SDSHUV 5DQNLQJ (YROXWLRQDU\ &RPSXWDWLRQ 1R /RFDO &RQVWUDLQW Algorithm 1: Infeasible Allocation Detection
'HWHUPLQDWLRQ �
LPSURYHG WHVW SDSHUV

$UFKLYH
8SGDWH
algorithm that generalizes the basic greedy-based approximation algorithm for submodular function. For the sake of simplicity, we consider only the topic and question type constraints. As such, the result obtained is the upper bound of the actual approximate solution. However, it is sufficient for the early infeasible allocation detection purpose.
The algorithm is outlined in Algorithm 1. In each iteration, we first check that whether the question q can be possibly allocated to a paper Pt. To verify whether q can be possibly allocated to Pt, we first check whether Pt is full, i.e., |Pt| = N. Then, we check whether allocating q to Pt will violate the two constraints. If yes, we then compute the marginal improvement value Ψt,q of allocating question q into Pt. Next, we greedily choose the best allocation of test paper and question (Pt∗ , q∗ ) with the maximum Ψt,q value.
We provide a theoretical result of this step. For general cases, i.e., k ≥ 2, we can prove that it achieves a weaker approximation ratio of 12 .
Theorem 2. Consider only the content constraints with k ≥ 2, Algorithm 1 can obtain a set of generated test papers P1, .., Pk with the total quality value such that:
4XHVWLRQ
where OPT refers to the optimal value.
Proof Sketch: Let H be the original problem of allocating k ∗ N out of n questions to k papers P1, .., Pk such that it maximizes the total quality objective ∑ki=1 fφ(Pi). Let H′ be the problem on the n - 1 remaining questions after the first question qt is selected for paper Pj. On the problemH′ , the quality evaluation function fj(Pj) = fφ(Pj) is replaced by f ′ j (Pj) = fj(Pj ∪ {qt}) - fj({qt}). All other quality evaluation function fi(Pi), i ̸= j, are unchanged.
Let VAL(H) be the value of the allocation produced by Algorithm 1 and OPT(H) be the value of the optimal allocation. Let p = fj({qt}). By definition of H′ , it is clear that V AL(H) = V AL(H′ ) + p. By submodularity, we can show that OPT(H) ≤ OPT(H′ ) + 2p. This proof is completed by induction on H′ since H′ is also a submodular function:
Theorem 2 means that Algorithm 1 can achieve 1/2approximation ratio for the total quality maximal objective based on a given fairness value φ. Based on this, we can decide whether it is feasible to allocate k papers corresponding to the current fairness φ.
4.5 Total QualityMaximization
It progressively solves k problem instances of 1-TPG to generate k papers P1, P2, .., Pk. Based on the submodular property of fφ(P), we greedily select questions that maximize the objective function while paying attention to satisfying the multiple knapsack constraints. This is motivated by an algorithm that maximizes a submodular function under a knapsack constraint: max
where c(x) ≥ 0 is a cost function and b ∈ R is a budget constraint. Sviridenko [Sviridenko, 2004] proposed the greedybased algorithm for solving this problem with an approximation ratio of 1 - 1e . It defines the marginal gain ∆f (x|S) c(x) when adding an item x into the current solution S as a ratio between the discrete derivative ∆f (x|S) and the cost c(x). This algorithm starts with S = ∅, and then iteratively adds the element x that maximizes the marginal gain ratio among all elements that satisfy the remaining budget constraint:
We extend the above algorithm of submodular function maximization under a knapsack constraint for solving the case of multiple knapsack constraints. Algorithm 2 gives the greedybased algorithm for this step. This algorithm maintains a set of weights that are incrementally adjusted in a multiplicative manner. These weights capture the possibility that each constraint is close to be violated when maximizing the objective function of generating a paper. The algorithm is based on a main loop in Line 4. In each iteration, the algorithm selects an available question that maximizes the sum of marginal gain ratio normalized by the weights as follows:
Algorithm 2: Total Quality Maximization
Process: 1 for l=1 to k do 2 Pl ← ∅ ; 3 for i=1 to m do hi = 1/bi ; 4 while ∑mi=1 bihi ≤ µ and |Pl| ≤ N do 5 qj ← arg max qj ∈Q ∑mi=1 ∆fφ (qj |Pl ) Aij hi ; 6 Pl ← Pl ∪ {qj}; 7 for i=1 to m do hi ← hiµ Aij bi ; 8 Q ← Q \ {qj } 9 return P1, P2, .., Pk
where A is a matrix and b is the vector of multiple knapsack constraints. Here, ∆fφ (qj|Pl) is the submodular incremental marginal value of question qj to the paper Pl.
The parameter µ in Algorithm 2 is important as it ensures that multiple knapsack constraints will not be violated while maximizing the submodular objective function. Let H = min{bi/Aij : Aij > 0} be the width of the knapsack constraints. By setting the parameter µ = eH m, Algorithm 2 can achieve near-optimal results. [Azar and Gamzu, 2012] has proved the following theoretical result:
Lemma 2. Algorithm 2 (Line 2-8) attains an approximation guarantee such that
where P ∗ i refers to the optimal solution of each main loop.
Corollary 2. The total quality objective function of k test papers P1, .., Pk attained by Algorithm 2 satisfies:
Proof Sketch: Let P ∗ i be the optimal solution corresponding to each main loop of Algorithm 2. By using Lemma 2, we can directly derive the result.
4.6 Fairness Quality Balancing
This step aims to employ a novel fairness balancing strategy to improve the fairness quality objective. Recall that our goal is to allocate questions into k test papers such that for all papers, we have fφ(Pl) ≥ βφ, ∀l = 1..k. However, this is not easy to achieve especially when φ approaches the optimal value. This is because in the small and less abundant pool of questions, Algorithm 2 greedily selects all questions with high value fφ(q) for some of the generated papers P1, P2, .., Ps to satisfy fφ(Pl) ≥ βφ, ∀l = 1..s. As a result, the subsequent papers Ps+1, .., Pk might not have enough good questions to satisfy this requirement. We need to swap some of the questions from the satisfied papers with questions from unsatisfied papers to achieve a fair allocation.
We will move questions from satisfied papers to unsatisfied papers and vice versa, until all papers satisfy the requirement fφ(Pl) ≥ βφ, ∀l = 1..k. Let's define the swapping operation
Algorithm 3: Fairness Quality Balancing
as follows. Select a satisfied paper Pi = {qi1 , qi2 , ...qiN } for which fφ(Pi) ≥ 3βφ. Such a paper is always ensured through appropriate choice of α and β as shown in Lemma 3. Then, we select an unsatisfied paper Pj, i.e., fφ(Pj) ≤ βφ. In the paper Pi, choose t < N such that fφ({qi1 , qi2 , ...qi t-1}) < βφ, fφ({qi1 , qi2 , ...qi t }) ≥ βφ, and fφ({qi t }) < βφ. Let Λi = {qi1 , qi2 , ...qi t }. As fφ(∅) = 0, the set Λi is not empty. In the reversed direction, let Λj = {qj1 , qj2 , ...qj t } be a set of questions in Pj such that each pair of questions qi l , l = 1..t, and qj l , l = 1..t, has the same topic and question type. We reallocate the questions of papers Pi and Pj by swapping questions of the two sets Λi and Λj . We note that the swapping operation does not violate the multiple knapsack constraints. More importantly, it improves the fairness among all papers. The swapping operation is given in Algorithm 3.
By some analysis, we can prove that swapping questions does not decrease the value of fφ(Pi) by more than 2βφ. Thus, Pi is still satisfied. Moreover, the previously unsatisfied test paper becomes satisfied by this operation. We can also make sure that we can always perform this operation until all test papers are satisfied by choosing β = α/3, where α = 1/2 is the approximation ratio of Algorithm 1.
Lemma 3. If we choose β = α/3 = 1/6, it is guaranteed that after at most t swapping operations, all test papers will be satisfied, i.e., fφ(Pl) ≥ βφ, ∀l = 1..k.
Lemma 3 ensures that there always exists a test paper such that fφ(Pl) ≥ 3βφ. It also ensures that all test papers will be satisfied after at most t swaps.
4.7 Local Constraint Improvement
So far, we have achieved a set of k test papers, having guarantee on the biobjective values and satisfying the multiple knapsack constraints. However, these test papers have not yet satisfied the total time and difficulty degree constraints.
Here, we propose an effective method for satisfying these constraints. Given a test paper P 0 = Pl = {q1, q2, .., qN}, l = 1..k, let q = {0, 1}n , |q| = N be the binary representation of the initial solution P. From the previous step, we have Aq0 ≤ b, which is the 0-1 ILP formulation of the corresponding 1-TPG problem. This step aims to turn the existing solution q0 to q1 such that Aq1 = b. This is the Subset Vector Sum problem, which is NP-hard. Here, we only need to optimize the total time and difficulty degree constraints. Let ∑nl=1 ailq ≤ bi be the total time constraint and ∑nl=1 ajlq ≤ bj be the difficulty degree constraint. To optimize constraint satisfaction while ensuring the objective value f(Pl) will not decrease, we reformulate the 1-TPG problem to unconstrained submodular optimization by introducing two weighting parameters λ1 and λ2:
| #Questions | #Topics | #Question Types | Distribution | |
|---|---|---|---|---|
| D1 | 20000 | 40 | 3 | uniform |
| D2 | 30000 | 50 | 3 | normal |
| D3 | 40000 | 55 | 3 | uniform |
| D4 | 50000 | 60 | 3 | normal |
It is not difficult to show that the problem maxfξ(Pl) is an unconstrained non-monotone submodular maximization, which can be solved by an effective deterministic approximation local search proposed by Feige et al. [Feige et al., 2007].
4.8 Termination
The process is repeated until the termination condition is reached: φmax -φmin ≤ δ, where δ is a predefined threshold. An optimal value of δ = 0.05 was found experimentally.
4.9 Theoretical Analysis
We summarize the approximation results of the proposed CBO approach for biobjective optimization of k-TPG.
Theorem 3. The proposed CBO approach has achieved the following theoretical biobjective approximation results of the total quality maximization and fairness quality maximization:
5 Performance Evaluation
The performance of CBO is compared with other techniques including the following 3 re-implemented algorithms for kTPG: k-TS [Hwang et al., 2008], k-PSO [Ho et al., 2008] and k-ACO [Hu et al., 2009] based on the published articles.
As there is no benchmark data available, we generated 4 large-sized synthetic datasets, namely D1, D2, D3 and D4, for performance evaluation. In datasets D1 and D3, the value of each attribute is generated according to a uniform distribution. On the other hand, in datasets D2 and D4, the value of each attribute is generated according to a normal distribution. Table 1 summarizes the 4 datasets.
We analyze the quality and runtime efficiency of the CBO approach for k-TPG based on the 4 large-scale datasets by using different specifications. Here, we have designed 12 test specifications in the experiments. We vary the parameters in order to have different test criteria in the test specifications. The number of topics is specified between 2 and 40. The total time is set between 20 and 240 minutes, and it is also set proportional to the number of selected topics for each specification. The average difficulty degree is specified randomly between 3 and 9. We have conducted the experiments according to 5 different values of k, i.e., k = 1, 5, 10, 15, 20.

To evaluate the quality for k-TPG, we use the common metrics including the Average Discrimination Degree and Average Constraint Violation for 1-TPG [Nguyen et al., 2013] based on the same user specification S. From the common metrics, for a given dataset D and k, we define the following metrics for k-TPG based on the average and deviation of the quality of generated test papers: the Average Discrimination Degree Mk,D d , the Deviate Discrimination Degree V k,D d , the Average Constraint Violation Mk,D c and the Deviate Constraint Violation V k,D c . Specifically, given a dataset D and for each k, we generate 12 test paper sets P1, P2, ..., Pk from the 12 specifications. For each of the 12 test paper sets, we measure the mean and deviation of quality of k test papers according to the discrimination degree and constraint violation. Finally, we obtain the performance results based on the 4 measures by averaging the means and deviations over the 12 test paper sets.
For high quality parallel test papers, the Average Discrimination Degree should be high and the Average Constraint Violation should be small. Similarly, the Deviate Discrimination Degree and the Deviate Constraint Violation should be small.
5.1 Performance Results based on Runtime
Figure 2 compares the runtime performance of the 4 techniques based on the 4 datasets. The results have clearly shown that the proposed CBO approach significantly outperforms the other heuristic techniques in runtime for the different datasets. CBO generally requires less than 6 minutes to complete the parallel paper generation process. Moreover, the proposed CBO approach is quite scalable in runtime on different dataset sizes and distributions. In contrast, the other techniques are not efficient to generate high quality parallel test papers. Particularly, the runtime performance of these techniques degrades quite badly as the dataset size or the number of generated parallel test papers gets larger, especially for imbalanced datasets D2 and D4.
5.2 Performance Results based on Quality
Figure 3 shows the quality performance results of the 4 techniques based on the Mean Discrimination Degree Mk,D d and Deviate Discrimination Degree V k,D d . As can be seen from Figure 3, CBO has consistently achieved higher Mean Discrimination Degree Mk,D d and lower Deviate Discrimination Degree V k,D d than the other heuristic k-TPG techniques for the generated parallel test papers. Particularly, CBO can generate high quality test papers with Mk,D d ≈ 7. Note that the lower Deviate Discrimination Degree V k,D d value indicates that the generated parallel test papers have similar quality in terms of discrimination degree. Generally, for a specific value of k, we observe that the quality of the generated parallel test papers of all 4 techniques based on the Mean Discrimination Degree Mk,D d and the Deviate Discrimination Degree V k,D d tend to be improved when the dataset size gets larger.
Figure 4 gives the quality performance results of the 4 techniques based on the Mean Constraint Violation MD,k c and Deviate Constraint Violation V D,k c . We also observe that CBO has consistently outperformed the other techniques on Mean Constraint ViolationMDc and Deviate Constraint Violation V D,k c based on the 4 datasets. The Mean Constraint Violation of CBO tends to decrease whereas the Mean Constraint Violations of the other 3 techniques increase quite fast when the dataset size or the number of specified constraints gets larger. In particular, CBO can generate high quality parallel test papers with MD,k c ≤ 10 for all datasets. Also, CBO is able to generate higher quality parallel test papers on larger datasets while the other techniques generally degrade on the quality of the generated test papers when the dataset size gets larger. In addition, we find that when k gets larger, the Mean Constraint Violation Mk,D c on a specific dataset D tends to decrease. Similarly, the Deviate Constraint Violation V k,D c quality tends to increase when k gets larger. These results have shown that the quality based on constraint violation on a specific dataset D tends to degrade when k gets larger.
The good performance of CBO is due to 2 main reasons. Firstly, as CBO is an approximation algorithm with constant performance guarantee, it can find the near-optimal solution for objective functions of k-TPG effectively and efficiently while satisfying the multiple constraints without using weighting parameters. As such, CBO can achieve better paper quality and runtime efficiency as compared with other heuristic-based k-TPG techniques. Secondly, CBO is a submodular greedybased algorithm, which is able to produce good solution in efficient polynomial runtime. Thus, CBO can also improve its computational efficiency on large-scale datasets as compared with the other k-TPG techniques.
6 Conclusion
In this paper, we have proposed an effective and efficient Collective Biobjective Optimization algorithm for solving k-TPG. The key success of CBO lies in the synergy of the effective problem reformulation with the exploitation of submodular property for collective biobjective optimization. CBO incorporates submodular optimization mechanism and submodular fairness balancing to jointly optimize the total quality maximization and the fairness quality maximization objectives. To the best of our knowledge, CBO is a pioneering greedybased approximation algorithm, which can achieve provably near-optimal solutions in polynomial runtime for k-TPG. The performance results on various datasets have shown that the CBO approach has achieved generated parallel test papers with not only high quality, but also runtime efficiency when compared with other k-TPG techniques.


@inproceedings{ijcai2015p65,
title = {Collective Biobjective Optimization Algorithm for Parallel Test Paper Generation},
author = {Nguyen, Minh Luan and Hui, Siu Cheung and Fong, Alvis Cheuk M.},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {418--423},
year = {2015},
month = {7},
note = {Main Track},
url = {https://ijcai.org/proceedings/2015/65},
}
TY - CPAPER TI - Collective Biobjective Optimization Algorithm for Parallel Test Paper Generation AU - Nguyen, Minh Luan AU - Hui, Siu Cheung AU - Fong, Alvis Cheuk M. T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 418 EP - 423 UR - https://ijcai.org/proceedings/2015/65 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: