基于量子粒子群优化算法的排课系统的设计与实现

• 作 者: 郭丽敏
• 出 处: 南京理工大学
• 发表日期: 2011年期
• 关键词: 排课问题 量子粒子群优化算法 组合优化 粒子群优化

高校排课管理工作是高等教育中的一个极为重要的环节,本文首先分析了课表问题中的各种因素以及人工排课的模拟过程,确定了课表问题是一个具有不确定性、NP完全的组合优化问题。为了能够有效地解决课表问题,我们进行了深入地研究了量子粒子群优化算法,最后在此基础上进行改进,把改进出来的新算法应用到高校排课系统优化中,量子粒子群优化算法是一种新兴的群体智能优化工具,能够大大减轻复杂的大规模多目标优化问题的计算负担,便于实际应用,可以得到许多比较好的Pareto最优解,并能够很方便地处理大型多目标优化设计问题。针对高校课表安排问题,首先建立了它的数学模型,并根据实际情况对量子粒子群优化算法做了多个方面的改进和优化。例如,量子粒子算法的改进、排课难度量化的计算、上课时间安排冲突判断方法、适应函数的选择等等,这些改进能很好提高量子粒子群优化算法中的收敛速度,避免算法出现未成熟收敛等一系列问题。本文在排课系统设计与实现中的关键技术主要体现在以下几个方面：一、增加了对排课难度的量化计算,对较难安排的课程给于一定的优先度进行安排,从而提高高校排课的效率和减少了工作量。二、针对量子粒子群优化算法在求解多目标优化问题时易出现早熟收敛现象,本文提出改进的量子粒子群优化算法,并通过测试函数验证了改进的有效性。三、通过考虑排课中实际存在的方方面面的因素,并第一次尝试把改进的量子粒子群优化算法应用到高校自动排课系统中,实验表明,该算法切实可行,它能够较好地优化高校排课这个复杂优化的问题。作为一种全局搜索优化算法,它能够有效地避免局部最优,但是却增加了搜索时间,本文就是为了更好更快地找到问题的最优解,在其过程中加入了局部搜索算法,即避开了局部最优,又加快了算法全局搜索速度。