基于禁忌搜索算法的高校實驗室管理系統優化

邵婉婷

摘要：隨著信息技術的普及和互聯網時代的發展，越來越多的高校在學生的信息素養的培養和實驗室的建設上加以重視。而實驗室是教師展開教學和科研項目的重要場所，實驗室管理自然是重中之重。由于國家和校領導的大力支持，實驗室設施和實驗室管理人才稀缺的問題已經基本得到解決，而目前亟需解決的是實驗室使用安排的問題。禁忌搜索算法是一種亞啟發式隨機搜索算法，能很好的實現高校教學活動的需求和高校實驗室資源的最優配置。

關鍵詞：實驗室管理;緊急搜索算法;實驗室預約

中圖分類號：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.