差分进化布谷鸟算法在实验室排课中的应用
2020-04-09彭勇陈俞强
彭勇 陈俞强



摘 要:随着高校实验课程比例越来越高,针对传统实验室排课手段效率低、出现冲突的可能性高等缺点,提出了一种基于改进布谷鸟算法的智能排课模型。首先,定义了课元表示教师在什么班级上什么课程,把排课问题转化为课元确定教室-时间对,提出了一个多目标、多约束的排课数学模型。其次将数学模型的求解转化为对二部图进行完美匹配操作获取初始解。然后,利用差分进化方法改进了布谷鸟算法,实现布谷鸟算法在实验室排课中的应用。最后,通過对仿真实验的结果分析来验证算法可行性与有效性。
关键词:实验室排课;布谷鸟算法;二部图;差分进化;课元;排课模型
中图分类号:TP319 文献标识码:A
Application of Improved Cuckoo Search Based on Differential Evolution
in Laboratory Course Arrangement
PENG Yong?覮,CHEN Yu-qiang
(Department of Computer,Dongguan Polytechnic College,Dongguan,Guangdong 523808,China)
Abstract:As proportion of experimental courses is increasing in colleges,aiming at the shortcomings of low efficiency and high possibility of conflict in traditional laboratory course arrangement methods,an intelligent course scheduling model based on improved cuckoo algorithm is proposed. Firstly,it defines the course elements to indicate what classes and courses teachers are taking,transforming the problem of course scheduling into course elements to determine classroom-time pairs,a mathematical model of multi-objective and multi-constraint is proposed. Secondly,the solution of mathematical model is transformed into perfect matching of bipartite graphs,then,the improved cuckoo search based on differential evolution is used to find the optimal schedule in the solution space,finally,the feasibility and validity of the algorithm are verified by analyzing the simulation results.
Key words:laboratory course arrangement;cuckoo search;bipartite graphs;differential evolution;course elements ;course scheduling model
在高校的实验室管理中,实验课程排课是一项非常复杂而繁琐的工作。近年来,高校招生规模日益扩大,各种新型专业课程层出不穷,大部分专业课程都要求在实验室进行理实一体化教学,尽管实验室建设进度也不断加快,但是实验实训资源仍然十分短缺,各高校对实验室的利用率提出较高的要求,尽量让课程能够共享实验室,这无形就增大了实训课程排课的复杂度和难度。目前高校排课很多还是利用Excel软件由教学秘书手工排课,远远不能满足新时代高校实验室排课的需求。早在70年代,高校排课问题就被证明是一个NP完全问题,即算法的计算时间是呈指数增长的,这一论断确立了排课问题的理论深度[1]。……
