搜索区域自动变更的智能水滴算法实训课排课优化

排课问题是NP完全问题,高校实训室排课需考虑实训设备配置及教学改革"走班制"专业选修课所增加的排课复杂度.将高校实训室排课问题建模为硬约束目标及软约束优化满足问题,提出了经过改进的智能水滴算法,改进算法在路径寻优过程中根据待排课程的属性与当前排课状态,结合优化目标,自动进行跳转或围绕核心点变更搜索区域,有效解决了标准智能水滴算法搜索范围固定不利于算法搜索效率提升的问题.提出了预排序策略,减轻算法后期运行的阻力,在排课资源紧张的情况下,更好地实现收敛.通过改进智能水滴算法、标准智能水滴算法、遗传算法进行排课实验对比,验证了改进智能水滴算法在排课系统中的优化效果和高效性。

Research on the College Training Course Scheduling Problem with Intelligent Water Drop Algorithm Based on Self-Adaptive Search Space

The college course scheduling problem belongs to Non-deterministic Polynomial complete problem.College training course scheduling should take into account the training equipment configuration and the increasing complexity of the arranging process due to the teaching reform of the Class-Selection System.Modeling the college course scheduling problem as a constrained optimization problem with some hard and soft constraint objectives,a modified intelligent water drops algorithm is proposed.The modified algorithm can skip automatically and alter search area around core points during the process of searching the best route,according to the attributes of the courses needed to be scheduled,the current coursescheduling status,and the optimization objective.The modified algorithm effectively solves the problem of not conducive to improving the efficiency of search for the standard intelligent drop algorithm due to its fixed search scope.The pre order courses strategy is also proposed to reduce the resistance in the later stage and achieve better convergence under the condition of tight schedule resources.Comparing to the standard intelligent water drops algorithm and the genetic algorithms in the scheduling experiments,the optimization and high-efficiency of the modified intelligent water drops algorithm in the course-scheduling system is proved.