Proceedings

Collective Biobjective Optimization Algorithm for Parallel Test Paper Generation

Download BibTeX Cite

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.

  1. [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.
  2. [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.
  3. [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.
  4. [Bertsimas et al., 2011] D. Bertsimas, V. F. Farias, and N. Trichakis. The price of fairness. Operations research, 59(1):17-31, 2011.
  5. [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.
  6. [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.
  7. [Fujishige, 2005] S. Fujishige. Submodular functions and opti- mization. Elsevier Science, 2005.
  8. [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.
  9. [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.
  10. [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.
  11. [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.
  12. [Lovasz, 1983] L. Lovasz. Submodular functions and convexity. Mathematical programming: the state of the art, pages 235-257, 1983.
  13. [Martin, 2012] F. G. Martin. Will massive open online courses change how we teach? Communication of the ACM, 55(8):26- 28, August 2012.
  14. [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.
  15. [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.
  16. [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.
  17. [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.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards