基于粒子群优化的考试时间安排问题的求解算法

Particle swarm optimization algorithm for solving examination timetabling problem

粒子群优化算法是近年来发展起来的一种元启发式的搜索算法,是目前解决组合优化问题的最有效的算法之一。针对考试时间表问题(ETP),通过基于时间序列的粒子编码方式和新的更新算子,建立ETP问题的粒子群求解模型,并结合简化邻域搜索算法给出了改进策略。仿真实验结果表明所提算法及策略的有效性。

Particle Swarm Optimization （PSO） is a new meta-heuristic search technology developed in recent years, and it is one of the most effective algorithms for combinatorial optimization problems at present. To solve the Examination Timetabling Problem （ETP）, this paper proposed a PSO algorithm, which adopted an encoding scheme based on time permutation and a new individual production operator, and employed a simple neighborhood search to improve searches. The experimental results show that the proposed algorithm and strategy are effective and efficient for different scale benchmarks of ETP.