基于遗传-蚁群混合算法的排课系统
|
摘要
在高校的教务管理中,排课问题是复杂又关键的环节,科目数量众多,教学资源有限等等因素都制约着排课的复杂程度和结果.排课本质就是将课程、班级在合适的时间段安排到合适的教学位置,是一个NP问题的求解.随着规模的不断扩大,问题求解难度呈指数形式增加,当规模达到一定程度的时候就很难在短的时间内求出最优解.鉴于此,本文提出了遗传-蚁群混合算法,将两种算法混合使用,依靠遗传算法生成信息素分布,利用蚁群算法求最优解.实验结果表明,混合算法提高了排课的效率和课表的合理度.
In the administrative management of colleges and universities, the scheduling is a complex and critical task.The number of subjects and the limited teaching resources all restrict the complexity and results of class scheduling. The essence of class scheduling is to arrange the course and class to the appropriate teaching location at the appropriate time.It is a solution to the NP problem. As the scale continues expanding, the difficulty of solving problems increases exponentially. When the scale reaches a certain level, it is difficult to find the optimal solution in a short time. In view of this, this study proposes a genetic-ant colony hybrid algorithm, which uses a mixture of two algorithms, relies on genetic algorithm to generate pheromone distribution, and uses ant colony algorithm to find the optimal solution. The experimental results show that the hybrid algorithm improves the efficiency of class scheduling and the rationality of the class schedule.
In the administrative management of colleges and universities, the scheduling is a complex and critical task.The number of subjects and the limited teaching resources all restrict the complexity and results of class scheduling. The essence of class scheduling is to arrange the course and class to the appropriate teaching location at the appropriate time.It is a solution to the NP problem. As the scale continues expanding, the difficulty of solving problems increases exponentially. When the scale reaches a certain level, it is difficult to find the optimal solution in a short time. In view of this, this study proposes a genetic-ant colony hybrid algorithm, which uses a mixture of two algorithms, relies on genetic algorithm to generate pheromone distribution, and uses ant colony algorithm to find the optimal solution. The experimental results show that the hybrid algorithm improves the efficiency of class scheduling and the rationality of the class schedule.
引文
1薛冬梅.充分利用资源科学合理排课.中原工学院学报,2002,13(S1):97-98.
2杜立智,陈和平,符海东.NP完全问题研究及前景剖析.武汉工程大学学报,2015,37(10):73-78.
3朱剑冰,李战怀,赵娜.基于混合遗传算法的自动组卷问题的研究.计算机仿真,2009,26(5):328-331,352.[doi:10.3969/j.issn.1006-9348.2009.05.084]
4许秀林,胡克瑾.基于约束满足和遗传算法的排课算法.计算机工程,2010,36(14):281-284.[doi:10.3969/j.issn.1000-3428.2010.14.102]
5李俊,周虎,李波.基于虚拟蚂蚁的局部优化蚁群算法.控制与决策,1-10.[doi:10.13195/j.kzyjc.2018.0298]
6史文.基于遗传算法的自动排课系统设计与实现[硕士学位论文].成都:电子科技大学,2013.
7宗薇.高校智能排课系统算法的研究与实现.计算机仿真,2011,28(12):389-392.[doi:10.3969/j.issn.1006-9348.2011.12.095]
2杜立智,陈和平,符海东.NP完全问题研究及前景剖析.武汉工程大学学报,2015,37(10):73-78.
3朱剑冰,李战怀,赵娜.基于混合遗传算法的自动组卷问题的研究.计算机仿真,2009,26(5):328-331,352.[doi:10.3969/j.issn.1006-9348.2009.05.084]
4许秀林,胡克瑾.基于约束满足和遗传算法的排课算法.计算机工程,2010,36(14):281-284.[doi:10.3969/j.issn.1000-3428.2010.14.102]
5李俊,周虎,李波.基于虚拟蚂蚁的局部优化蚁群算法.控制与决策,1-10.[doi:10.13195/j.kzyjc.2018.0298]
6史文.基于遗传算法的自动排课系统设计与实现[硕士学位论文].成都:电子科技大学,2013.
7宗薇.高校智能排课系统算法的研究与实现.计算机仿真,2011,28(12):389-392.[doi:10.3969/j.issn.1006-9348.2011.12.095]