IEEE Trans Cybern. 2017 Jun;47(6):1562-1575. doi: 10.1109/TCYB.2016.2552079. Epub 2016 Jun 23.
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 (MA), which exploits the submodular property of the collective objective functions to design greedy-based approximation algorithms for enhancing steps of the multiobjective MA. 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 MA 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.
并行试卷生成是一个双目标分布式资源优化问题，旨在根据多个用户指定的评估标准自动生成多个类似最优的试卷。由于集体目标函数的 NP 难性质，生成高质量的并行试卷具有挑战性。在本文中，我们提出了一种用于解决该问题的子模拟态进化算法。所提出的算法是一种自适应的拟态进化算法（MA），利用集体目标函数的子模性质，设计基于贪婪的近似算法，用于增强多目标 MA 的增强步骤。我们的算法将子模局部搜索机制的强化与基于种群的子模交叉算子的多样化相结合，可以共同优化总质量最大化目标和公平质量最大化目标。我们的 MA 可以在高效的多项式运行时间内，在大数据集的巨大搜索空间中实现可证明的近最优解。在各种数据集上的性能结果表明，我们的算法在试卷质量和运行效率方面明显优于现有技术。
