M. L. Nguyen, S. C. Hui and A. C. M. Fong, "Submodular Memetic Approximation for Multiobjective Parallel Test Paper Generation," in IEEE Transactions on Cybernetics, vol. 47, no. 6, pp. 1562-1575, June 2017. doi: 10.1109/TCYB.2016.2552079
Abstract:
Parallel Test Paper Generation is a biobjective distributed resource optimization problem, which aims to generate multiple similarly optimal test papers automatically according to multiple user-specified assessment criteria. Generating high-quality parallel test papers is challenging due to its NP-hardness in both of the collective objective functions. In this paper, we propose a Submodular Memetic Approximation algorithm for solving this problem. The proposed algorithm is an adaptive memetic algorithm, which exploits the submodular property of the collective objective functions to design greedy-based approximation algorithms for enhancing steps of the multiobjective memetic algorithm. Synergizing the intensification of submodular local search mechanism with the diversification of the population-based submodular crossover operator, our algorithm can jointly optimize the total quality maximization objective and the fairness quality maximization objective.
Our memetic algorithm can achieve provable near-optimal solutions in a huge search space of large datasets in efficient polynomial runtime. Performance results on various datasets have shown that our algorithm has drastically outperformed the current techniques in terms of paper quality and runtime efficiency.
License type:
PublisherCopyrights
Funding Info:
Description:
(c) 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.