基于禁忌搜索算法的高校实验室管理系统优化

邵婉婷

摘要：随着信息技术的普及和互联网时代的发展，越来越多的高校在学生的信息素养的培养和实验室的建设上加以重视。而实验室是教师展开教学和科研项目的重要场所，实验室管理自然是重中之重。由于国家和校领导的大力支持，实验室设施和实验室管理人才稀缺的问题已经基本得到解决，而目前亟需解决的是实验室使用安排的问题。禁忌搜索算法是一种亚启发式随机搜索算法，能很好的实现高校教学活动的需求和高校实验室资源的最优配置。

关键词：实验室管理;紧急搜索算法;实验室预约

中图分类号：TP311 文献标识码：A 文章编号：1007-9416（2019）05-0139-02

1 实验室管理中的问题

1.1 实验室管理系统

实验室管理系统是指为实验室使用人员，如学生、教师、管理人员和学院领导提供的对实验室活动如预约、实验室教学、耗材设备管理、人员流动等，进行系统化，流程化管理的网络系统。实验室管理系统以全面覆盖的校园网为基础既能实行对外全公开的管理，也能半公开即会员制管理，同时也能限制IP或者进行局域网内的管理。提高了对实验室和实训基地的管理力度，大大的提高了工作效率。

1.2 实验室课程安排问题

虽然各大高校已加大对实验室设施的投入，但是设施的配备数量毕竟是有限的。随着互联网时代的发展和信息技术的普及，各大高校开始重视对学生信息素养的培养，对高校各个专业的每一名学生都进行计算机方面的教学，而计算机方面教学的展开除了基本理论知识的教学，更离不开实际的动手上机操作。所以有限数量的实验室设施又要满足高校不同专业，不同学生的课程使用需求。

实验室课程安排问题是高校实验室管理中的难点问题，因为它的实现需要考虑多方面的因素：

（1）授课老师。高校对授课老师的办公室位置安排不同，在为授课老师安排实验室时应考虑到距办公室的距离问题，尽量为老师安排距离近的实验室，以方便老师进行授课。若授课老师同时对不同班级进行同一课程的连续两节课的教学时，应保证实验室位置的不变，以防授课老师来回奔波耽误教学。

（2）学生专业。对于不同专业的学生应安排标准不同的实验室。对于非计算机专业的学生而言，实验室教学的难度不大，对计算机器材及软件配备、环境配置的要求不高，可以为之安排一般类型的实验室以供使用。而对于计算机专业及计算机相关专业的学生而言，所学知识对计算机性能要求可能较高，则需为之安排较优类型的实验室供其使用。以便实现实验室器材的最优配置和不同专业的学生更有针对性的进行教学。

（3）课程类型。运用到计算机的课程中，分为纯计算机及计算机加板书综合教学的两种类型。对于只运用计算机的课程只需配备有计算机设施的实验室即可。而对于计算机加板书综合教学类型的则具有特殊性，需安排既有计算机又有黑板的实验室，以便于授课老师更好的进行课程教学，提高实验室使用效率。

（4）上课时间。上课时间对于实验室安排是最基础也是最重要的。首要条件是按照教学计划的课程时间安排，为不同类别不同时间段的课程进行无时间冲突的安排。且对于某个时间段，只可安排授课老师一门课程，某个实验室也只能安排一门课程，否则会出现对象冲突。时间需控制在实验室管理人员上班期间，以便对实验室的使用进行监管，及时排查实验室设施故障情况。

（5）实验室容量。实验室的容量应大于上课学生的人数，如果小于则会出现某些学生没有座位、没有计算机完成学习的情况;如果等于，则可能某台或某几台计算机故障，耽误学生课程学习。所以安排实验室也要考虑实验室的容量问题。

1.3 实验室预约排课问题

预约排课即把某些已知的影响排课的因素条件进行合理的安排，如：专业、班级、课程名称、学生人数、授课老师、上课时间、上课地点。具体可表现为如图1所示。

2 禁忌搜索算法

2.1 禁忌搜索的简述

禁忌（Tabu Search）算法是一种亚启发式（meta-heuristic）随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。

为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。

2.2 禁忌搜索算法主要思路

（1）在搜索中，构造一个短期循环记忆表-禁忌表，禁忌表中存放刚刚进行过的|T|（T称为禁忌表）个邻居的移动，这种移动即解的简单变化。

（2）禁忌表中的移动称为禁忌移动。对于进入禁忌表中的移动，在以后的|T|次循环内是禁止的，以避免回到原來的解，从而避免陷入循环。|T|次循环后禁忌解除。

（3）禁忌表是一个循环表，在搜索过程中被循环的修改，使禁忌表始终保持|T|个移动。

（4）即使引入了禁忌表，禁忌搜索仍可能出现循环。因此，必须给定停止准则以避免出现循环。当迭代内所发现的最好解无法改进或无法离开它时，算法停止。

2.3 禁忌搜索算法中的影响因素

2.3.1 禁忌长度

在其他变量控制不变的情况下，从禁忌长度的因素来分析，禁忌长度越短，占用的机器内存空间越小，可搜索的范围区间相比之下会变大，这会导致实际能够所搜到的区间范围只占很小一部分，使得算法过早取得局部最优解。而禁忌长度过长则会导致执行过程中时间的增加。

2.3.2 特赦规则

对于在禁忌的对象中，如果出现以下三种情况，则将其禁忌长度设为0。

（1）当出现这样一种解，其目标值优于前面任意一个候选解;

（2）当所有的解都被划入禁忌表中，则选取评价函数值最小的那个解执行特赦;

（3）当某一对象的改变会引起目标函数值的明显变化时，则其可特赦。

2.3.3 候选集

候选集是通过其大小来影响禁忌搜索算法，候选集规模过大则会耗费过多的计算机内存同时增加算法的处理时间，候选集规模过小过早取得局部最优解。

2.4 禁忌搜索算法的过程

首先，输入给定的算法参数，随机产生初始解，这个初始解也就是满足基本条件的解，但不一定是最优解。由于禁忌搜索算法的特殊性和优越性体现在其具有算法收敛准则、特赦准则、“best so far”状态的判断三个方面，判断初始解是否具备以上三个特性，具体过程如图2所示。

3 禁忌搜索算法在实验室管理系统中的运用

基于以上的了解，禁忌搜索算法可对多目标、多约束的求优解问题进行非局部的整体最优求解。而实验室中的排课及学生预约实验室活动正是此类多目标的最优求解问题，因此将其算法运用入实验室管理系统的设计，可大大提高实验室的利用效率。

在实验室排课问题中，最基本的两大因素就是时间和地点，因此我们可根据这两大因素首先确定一个最初解，时间与实验室教师一一对应，即同一时间，一间教室只能用于一堂课的使用。其次再把如教师，距离问题等因素考虑进去，用禁忌搜索算法进行求解。

4 结语

一个好的实验室管理系统可大大减少实验室管理员工作的复杂度，提高实验室安排工作上的效率，从老师、学生、实验室器材等多方面进行考量，运用禁忌搜索算法对其进行优化，使得系统在求解过程中，在多因素、条件控制的情况下能够迅速有效的找到最优解，使得高校中实验室教学的环节能更好的开展，提高教学质量。

参考文献

[1] 陈冰剑.计算机系实验室管理系统的設计与实现[D].电子科技大学，2014.

[2] 刘艳.新形势下高校计算机实验室管理方法优化[J].计算机光盘软件与应用，2013，16（07）：198+200.

[3] 况爱农.高校实验室管理信息系统的研究与设计[D].电子科技大学，2007.