Abstract
Online test paper generation (Online-TPG) generates a test paper automatically online according to user specification based on multiple assessment criteria, and the generated test paper can then be attempted online by user. Online-TPG is challenging as it is a multi-objective optimization problem that is NP-hard, and it is also required to satisfy the online generation requirement. In this paper, we propose an efficient multi-objective optimization approach based on the divide-and-conquer memetic algorithm (DAC-MA) for Online-TPG. Instead of solving the multi-objective constraints simultaneously, the set of constraints is divided into two subsets of relevant constraints, which can then be solved separately and effectively by evolutionary computation and local search of DAC-MA. The empirical performance results have shown that the proposed approach has outperformed other TPG techniques in terms of runtime efficiency and paper quality.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Back T, Fogel DB, Michalewicz Z (1999) Evolutionary computation 1: basic algorithms and operators. IOP Publishing Ltd., UK
Beckmann N, Kriegel HP, Schneider R, Seeger B (1990) The r*-tree: an efficient and robust access method for points and rectangles. ACM SIGMOD Record 19(2): 322–331
Bodin L, Golden B, Assad A, Ball M (1983) Routing and scheduling of vehicles and crews: the state of the art. Comput Oper Res 10(2): 63–211
Bosman PAN, de Jong ED (2006) Combining gradient techniques for numerical multi-objective evolutionary optimization. In: Proceedings of the 8th annual conference on genetic and evolutionary computation, ACM, pp 627–634
Caponio A, Neri F (2009) Integrating cross-dominance adaptation in multi-objective memetic algorithms. In: Goh CK, Ong YS, Tan KC (eds) Multi-objective memetic algorithms, vol 171. Springer, New York, pp 325–351
Chen XS, Ong YS, Lim MH, Tan KC (2011) A multi-facet survey on memetic computation. IEEE Trans Evol Comput 15(5):591–607
Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd Edn. McGraw-Hill Science, New York, pp 127–144
Das A, Kempe D (2011) Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: International conference on machine learning ICML
de Bruijn NG (1964) Polya’s theory of counting. In: Beckenbach EF, Polya G (eds) Applied combinatorial mathematics. Wiley, New York, pp 144–184
Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, New York
Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE Trans Evol Comput 6(2): 182–197
Goh CK, Ong YS, Tan KC (2009) Multi-objective memetic algorithms, vol 171. Springer, New York
Ho TF, Yin PY, Hwang GJ, Shyu SJ, Yean YN (2008) Multi-objective parallel test-sheet composition using enhanced particle swarm optimization. J ETS 12(4): 193–206
Hu XM, Zhang J, Chung HSH, Liu O, Xiao J (2009) An intelligent testing system embedded with an ant-colony-optimization-based test composition method. IEEE Trans Syst Man Cybern 39(6): 659–669
Hwang GJ (2003) A test-sheet-generating algorithm for multiple assessment requirements. IEEE Trans Educ 46(3): 329–337
Hwang GJ, Chu HC, Yin PY, Lin JY (2008) An innovative parallel test sheet composition approach to meet multiple assessment criteria for national tests. Comput Educ 51(3): 1058–1072
Hwang GJ, Lin B, Tseng HH, Lin TL (2005) On the development of a computer-assisted testing system with genetic test sheet-generating approach. IEEE Trans Syst Man Cybern 35(4): 590–594
Hwang GJ, Yin PY, Yeh SH (2006) A tabu search approach to generating test sheets for multiple assessment criteria. IEEE Trans Educ 49(1): 88–97
Ishibuchi H, Tsukamoto N, Nojima Y (2008) Evolutionary many-objective optimization: a short review. In: IEEE world congress on evolutionary computation, IEEE, pp 2419–2426
Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 7(2): 204–223
Knowles J, Corne D (2005) Memetic algorithms for multiobjective optimization: issues, methods and prospects. In: Recent advances in memetic algorithms. Springer, Berlin, pp 313–352
Knowles J, Corne D, Deb K (2008) Multiobjective problem solving from nature: from concepts to applications. Springer, Berlin
Kullback S (1997) Information theory and statistics. Dover Publisher, New York
Kung HT, Luccio F, Preparata FP (1975) On finding the maxima of a set of vectors. J ACM 22(4): 469–476
Lee CL, Huang CH, Li CJ (2007) Test-sheet composition using immune algorithm for e-learning application. New Trends Appl Artif Intell 4570: 823–833
Manolopoulos Y, Nanopoulos A, Theodoridis Y (2006) R-trees: theory and applications. Springer, Berlin
Mei Y, Tang K, Yao X (2011) Decomposition-based memetic algorithm for multiobjective capacitated arc routing problem. IEEE Trans Evol Comput 15(2): 151–165
Moscato P (1989) On evolution, search, optimization, genetic algorithms and martial arts: towards memetic algorithms. Caltech Concurrent Computation Program, C3P Report, 826
Nguyen ML, Hui SC, Fong ACM (2011) An efficient multi-objective optimization approach for online test paper generation. In: IEEE symposium on computational intelligence in multicriteria decision-making (MDCM), pp 182–189
Ong YS, Keane AJ (2004) Meta-lamarckian learning in memetic algorithms. IEEE Trans Evol Comput 8(2): 99–110
Ong YS, Lim M, Chen X (2010) Research frontier: memetic computation—past, present & future. IEEE Comput Intell Mag 5(2): 24–31
Orlin JB, Punnen AP, Schulz AS (2004) Approximate local search in combinatorial optimization. In: Proceedings of ACM-SIAM SODA, pp 587–596
Roussopoulos N, Kelley S, Vincent F (1995) Nearest neighbor queries. In: Proceedings of the ACM SIGMOD, pp 71–79
Rui WF, Hong WW, Ke PQ, Chao ZF, Liang JJ (2009) A novel online test-sheet composition approach for web-based testing. In: Symposium on IT in medicine & education, pp 700–705
Schaerf A (1999) A survey of automated timetabling. In: Artificial intelligence review, vol 13, issue 2. Springer, Berlin, pp 87–127
Schrijver A (1986) Theory of linear and integer programming. Wiley, New York
Schutze O, Lara A, Coello CAC (2011) On the influence of the number of objectives on the hardness of a multiobjective optimization problem. IEEE Trans Evol Comput 15(4): 444–455
Tsai KH, Wang TI, Hsieh TC, Chiu TK, Lee MC (2009) Dynamic computerized testlet-based test generation system by discrete pso with partial course ontology. Expert Syst Appl 37(1): 774–786
Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms—a comparative case study. In: International conference on parallel problem solving from nature. Springer, Berlin, pp 292–301
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Nguyen, M.L., Hui, S.C. & Fong, A.C.M. Divide-and-conquer memetic algorithm for online multi-objective test paper generation. Memetic Comp. 4, 33–47 (2012). https://doi.org/10.1007/s12293-012-0077-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12293-012-0077-z