**Journal of Software Engineering and Applications** Vol.5 No.8(2012), Article ID:21962,5 pages DOI:10.4236/jsea.2012.58073

The Research of Examination Paper Generation Based on Index System Metrics and Multi-Objective Strategy

^{ }^{ }^{ }^{}

^{1}Engineering Research Center of Mechanical Testing Technology and Equipment, Chongqing University of Technology, Chongqing, China; ^{2}Information & Education Technology Center, Chongqing University of Technology, Chongqing, China.

Email: ly@cqut.edu.cn

Received April 10^{th}, 2012; revised May 8^{th}, 2012; accepted May 17^{th}, 2012

**Keywords:** Generating Examination Paper with Computer; Multi-Objective Strategy; Genetic Algorithm

ABSTRACT

Since the examination paper generated with computer by the algorithms of random and backtracking takes on inferior quality and inefficient, and the question of generating examination paper with computer has the character of multi-objective because of the index system metrics, the genetic algorithm with multi-objective strategy optimization is proposed to solve this problem. Mapping the index system to multi-objective functions and optimizing the computing with multi-objective strategy are employed in the algorithm. The genetic algorithm experiment based on the multi-objective strategy optimization shows that the result has the advantages getting tradeoff between performance and quality, and having the ability to tune the performance and quality to meet the user’s requirements.

1. Introduction

The technology of generating examination paper with computer is an import part for modern education. This technology is the infrastructure of others application such as intelligent tutoring systems [1], distance learning systems [2], computerized adaptive testing systems [3], e-learning systems [4], etc. In recent years, this technology is focused by many researchers on the algorithm how to search and compose a paper [5-9].

Generating examination paper with computer is defined as searching items from item bank and composing it following the paper index system. The process of generating examination paper with computer has the character of huge searching space, complex computing, and multi-objective [5]. Many algorithms are proposed to solve this problem, such as random algorithm, backtracking algorithm, and intelligent algorithm [6,7].

The random algorithm is searching the item bank and composing a paper with the random searching process. This is an efficient way to get a paper with computer, but this algorithm can’t guarantee the quality. The backtracking algorithm is searching all possible combination of items in item bank and composing a paper with the best result. This algorithm can get the optimization result, but can’t get a result when the item bank holding numbers of items. Intelligent algorithm employs the process of biological evolution to compose a paper. The representative algorithms of intelligent algorithm are genetic algorithm, artificial fish swarm algorithm, etc.

In this thesis, the genetic algorithm with multi-objective optimization is proposed to solve this problem. Firstly, the index system is mapped to multi-objective functions. Secondly, multi-objective strategy is used to optimize the computing process. By experiment, the proposed algorithm can control the scale of computing and get tradeoff result between performance and quality.

2. Examination Paper Model

Examination paper is regarded as a collection of items, so paper P and item bank B denotes as matrixes of m × n and s × n:

The parameter m of matrix P denotes the items’ number of paper P, and the parameter s of matrix B denotes the items’ number of item bank B. The parameter n of matrix P and matrix B denotes n objects of index system, and each column of matrixes denotes one object of index system. To generate the optimization result matrix P (i.e. paper P), the condition m ≤ s must be satisfied.

To generate paper P, a temporary paper S must be created from the item bank B. The paper S has the same structure as the paper P which includes m rows and n columns. The item bank B can generate numbers of S from the huge solution space.

3. Index System Metrics and Multi-Objective Optimization

The index system outlines the objects (i.e. the constraints) of generating examination paper with computer. Generally, the index system includes several objects, such as examination paper rubric number object, examination paper rubric type object, examination paper knowledge object, examination paper difficulty distribution object, examination paper rubric reference times object, etc. All of these objects can be regarded as multi-objective, and each object can reason an object function to measure the degree of approximation from S to P.

From above, the concrete paper matrix P, S and item bank B can be defined as:

The matrix P and matrix S contains both the same rows and columns, and the parameter m denotes m items. Matrix B contains s rows and 4 columns. All the matrixes include 4 columns, the first column denotes the rubric type index, the second column denotes the rubric knowledge index, the third column denotes difficulty index, and the forth column denotes reference times. These indexes, such as rubric type index, rubric knowledge index, etc, are integers the corresponding item’s attribute identity.

To characterize the rubric type of paper P, S and item bank B, vector T_{p}, T_{s} and T_{b} are defined as:

The index of vector T_{p}, T_{s} and T_{b} denotes the identity of rubric type, for example, t_{1} denotes rubric type number 1. The elements of vector T_{p}, T_{s} and T_{b} are statistics from the first column of matrix P, S and B.

To measure the rubric type approximation degree of paper P and S, the vector distance F_{t} between matrix P and S is defined as:

(1)

F_{t} is a vector distance between vector T_{s} and vector T_{p}, , and is the i’th element of vector T_{s}, T_{p} and T_{b} respectively.

F_{t} can measure the rubric type approximation degree between paper P and paper S, because the vector distance between vector T_{p} and vector T_{s} varies smaller when rubric type between paper P and paper S becomes more similar. In particular, the value of F_{t} is 0 when rubric type of paper P and paper S is the same.

To characterize the knowledge distribution of paper P and S, collection K_{p} and K_{s} is defined as:

The collection K_{p} contains p elements coming from the statistics of, correspondently, the collection K_{s} contains s elements coming from the statistics of.

To measure the knowledge distribution approximation degree of paper P and S, the collection operation is defined as:

(2)

It should be noted that the operator “” means getting the count of elements in collection x, so F_{t} is the sum of different elements between matrix P and S. The smaller F_{t} is, more similar the knowledge distribution between paper P and S will be, and the best F_{t} is 0.

To characterize the rubric difficulty distribution of paper P and S, vector D_{p} and D_{s} is defined as:

The vector D_{p} and D_{s} has the same semantic as the vector T_{p}, T_{s} and T_{b}, the index of vector D_{p} and D_{s} denotes the identity of rubric difficulty. The elements of vector D_{p} and D_{s} is the statistics of the third column of matrix P, matrix S respectively.

To measure the rubric difficulty distribution approximation degree between paper P and S, the vector distance F_{d} is defined as:

(3)

F_{d} is the vector distance between vector D_{s} and D_{p}, and is the i’th element of vector D_{s}, vector D_{p} respectively.

F_{d} can also measure the rubric difficulty approximation degree between paper P and S, F_{d} will vary smaller when the rubric difficulty distribution of paper S becomes more similar as paper P’s, F_{d} is 0 when the rubric difficulty distribution of paper S is the same as paper P’s.

To characterize the rubric reference times between paper P and S, R_{p} the sum of vector is defined, and R_{s} the sum of vector is defined too.

To measure the reference approximation degree between paper P and S, the distance F_{r} is defined as:

(4)

Generally, R_{p} is very small, such as 0.

Formulae (1)-(4) define the object functions according to the index system metrics, and the following conclusion can be draw from these formulae:

The range of F_{t}, F_{k}, F_{d} and F_{r} is [0, +∞)

The weightiness of F_{t}, F_{k}, F_{d} and F_{r} decreases orderly The optimum solution is

According to above conclusion, this problem is a multi-objective optimization problem. It can be solved by the multi-objective optimization method. To solve this problem, function vector F and weight vector W are defined as:

The vector F is a function vector composed of F_{t}, F_{k}, F_{d} and F_{r}, and the weight vector W is the corresponding weight of vector F’s elements. In practice, the value of w_{t}, w_{k}, w_{d} and w_{r} decreases orderly with the weightiness of F_{t}, F_{k}, F_{d} and F_{r} decreasing orderly.

To optimize the multi-objective problem, the multiobjective function F_{0} is defined as:

(5)

(and)

The approximation degree between paper P and paper S can be estimated by the value of F_{0}, because the value of F_{0} is smaller as paper P and paper S is more alike. From formula (5), the best value of F_{0} is 0.

4. Genetic Algorithm for Multi-Objective Optimization

To optimize this multi-objective problem with genetic algorithm [5,9], the coding scheme, selection operation, crossover operation and mutation operation should be established firstly. In our experiment, binary coding scheme is used, the binary vector X_{s} is defined as:

X_{s} is a vector whose elements denote the corresponding item whether or not contained in paper S, and the parameter m is the items’ count of paper S.

To establish the selection operation, the multi-objecttive function F_{0} is employed as the fitness function and the proportion is adopted to form the individual selection probability. The selection probability P_{is} is defined as:

is the total fitness in the population of one generation, and is the fitness of the ith individual in the population of one generation.

The crossover operation is defined as half of the gene of individual participates in crossover, and the remainder keeps the same. This rule is employed to generate two children from two parents. The mutation operator changes the gene’s value of all individuals according to the defined mutation probability P_{m}.

5. Experiments and Evaluation

To evaluation the performance of the proposed algorithm, two experiments have been conducted to compare performance and quality between random algorithm and genetic algorithm based on the multi-objective strategy optimization. The first experiment is to use random algorithm to generate several papers and the second one is to use the genetic algorithm to generate numbers of paper. Both of them can be evaluated by the Formula (5).

To perform the experiment, an item bank is set up by create 10,000 items randomly. The item bank can be used by the first and the second experiment. The random algorithm’s parameters are listed in Table 1, the multi-objective’s parameters are listed in Table 2, and the genetic algorithm’s parameters are listed in Table 3.

Figure 1 shows the generated papers by random algorithm, and Figure 2 shows the generated papers by genetic algorithm. From the two figures, it can be seen that the random algorithm can generate a paper quickly but the fitness hardly to approximate to 0. By contrary, the genetic algorithm with the multi-objective optimization can get the best fitness 0 in generations.

From Figure 2, it can be seen that the dot curve of best fitness shows a downward trend from generation 0 to 43 and the best fitness 0 in generation 43. The user can

Table 1. Random algorithm’s parameters.

Table 2. Multi-objective optimization’s parameters.

Table 3. Genetic algorithm’s parameters.

Figure 1. Random algorithm’s result.

Figure 2. Genetic algorithm’s result.

choose the generated paper from generation 15 to 43, and get tradeoff between performance and quality.

6. Conclusion and Future Work

In this paper, multi-objective strategy with genetic algorithm is proposed to solve the problem generating examination paper with computer. The object functions are defined according to the index system metrics, and the multi-objective function is defined from the object functions. To generate a paper meeting the index system metrics with genetic algorithm, the multi-objective function is set to be the fitness function. From the experiments, the multi-objective strategy with genetic algorithm to generate examination paper has the advantage getting tradeoff result between performance and quality and having the ability to tune the performance and quality. For further work, it should pay more attention to the constringency grads of the multi-objective function.

REFERENCES

- B. P. Butz, M. Duarte and S. M. Miller, “An Intelligent Tutoring System for Circuit Analysis,” IEEE Transactions on Education, Vol. 49, No. 2, 2006, pp. 216-223. doi:10.1109/TE.2006.872407
- O. G. Bellmunt, D. M. Miracle, S. G. Arellano, A. Sumper and A. S. Andreu, “A Distance PLC Programming Course Employing a Remote Laboratory Based on a Flexible Manufacturing Cell,” IEEE Transactions on Education, Vol. 49, No. 2, 2006, pp. 278-284. doi:10.1109/TE.2006.873982
- G. J. Hwang, B. M. T. Lin, H. H. Tseng and T. L. Lin, “On the Development of a Computer-Assisted Testing System with Genetic Test Sheet-Generating Approach,” IEEE Transactions on Systems, Man, and CyberneticsPart C, Vol. 35, No. 4, 2005, pp. 590-594. doi:10.1109/TSMCC.2004.843184
- S. C. Wang and Y. H. Liu, “Software-Reconfigurable e-Learning Platform for Power Electronics Courses,” IEEE Transactions on Industrial Electronics, Vol. 55, No. 6, 2008, pp. 2416-2424. doi:10.1109/TIE.2008.922592
- H. M. Gao and Y. J. Li, “An Autogenerating Test Paper Method Based on Latent Semantic Analysis and Genetic Algorithm,” International Workshop on Intelligent Systems and Applications, Wuhan, 23-24 May 2009, pp. 1-4. doi:10.1109/IWISA.2009.5072709
- P. Guo, L.-L. Liu and Q. Yao, “An Intelligent Test Sheet Composition System,” International Workshop on IT in Medicine and Education, Xiamen, 12-14 December 2008.
- X.-M. Hu and J. Zhang, “An Intelligent Testing System Embedded with an Ant Colony Optimization Based Test Composition Method,” IEEE Congress on Evolutionary Computation, Trondheim, 18-21 May 2009, pp. 1414- 1421.
- O.-Y. Yong and H.-F. Luo, “Computer-Based Language Testing Perspectives of the Past and the Future,” Computer Science & Education, 25-28 July 2009, pp. 1764- 1768.
- W. Huang and Z.-H. Wang, “Design of Examination Paper Generating System from Item Bank by Using Genetic Algorithm,” Computer Science and Software Engineering, Vol. 5, 2008, pp. 1323-1325.