论文摘要
排课问题是一个有约束的、多目标的组合优化问题,被证明是NP完全类问题。如何利用现有的各种技术实现课表编排的自动化、科学化和合理化,提高资源利用率以及教师和学生对课表的满意度是目前高校教学管理工作亟待解决的问题之一。粒子群算法(Particle Swarm Optimization,PSO)是一种基于群智能方法的演化计算技术,最早由心理学研究者Kennedy博士和从事计算智能研究的Eberhart博士受到人工生命和演化计算的研究结果启发于1995年提出的优化算法。PSO算法既简单、易于实现同时又有深刻的智能背景,既适合科学研究,又特别适合工程应用。因此,PSO算法一提出,短期内迅速得到了国际演化计算研究领域的认可,并受到广泛关注,在短短的十几年时间里涌现出大量的研究成果,成为计算智能领域当前的一个研究热点。本文首先对排课问题进行了比较深入的探讨,详细分析了排课问题的国内外研究现状,并对排课问题涉及的教师、教室、课程、班级、时间等要素及各种约束条件进行详细描述,给出了排课问题的数学模型。然后文章介绍了粒子群算法的理论和算法流程,重点对离散粒子群近几年研究现状进行了总结,并给出几种典型离散粒子群算法,在此基础上分析了离散粒子群算法在排课系统中的应用,给出了一个基于离散粒子群思想的排课算法。最后针对具体需求,对排课系统进行了详细设计,利用C#语言在Microsoft Visual Studio 2005平台上实现了基于离散粒子群算法的排课系统,并以三个学院一个学期的课程表为依据对系统进行了评估,测试粒子群数量对算法性能的影响、不同排课数据对系统性能的影响、系统排出的课表与人工排出的课表在给定指标下的性能优劣,测试结果验证了粒子群算法在排课系统中不仅解决了高校复杂的排课难题而且实现了智能化、人性化的排课过程,同时也验证了本系统的可用性。