邵婉婷

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

關(guān)鍵詞：實驗室管理;緊急搜索算法;實驗室預(yù)約

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2019）05-0139-02

1 實驗室管理中的問題

1.1 實驗室管理系統(tǒng)

實驗室管理系統(tǒng)是指為實驗室使用人員，如學(xué)生、教師、管理人員和學(xué)院領(lǐng)導(dǎo)提供的對實驗室活動如預(yù)約、實驗室教學(xué)、耗材設(shè)備管理、人員流動等，進(jìn)行系統(tǒng)化，流程化管理的網(wǎng)絡(luò)系統(tǒng)。實驗室管理系統(tǒng)以全面覆蓋的校園網(wǎng)為基礎(chǔ)既能實行對外全公開的管理，也能半公開即會員制管理，同時也能限制IP或者進(jìn)行局域網(wǎng)內(nèi)的管理。提高了對實驗室和實訓(xùn)基地的管理力度，大大的提高了工作效率。

1.2 實驗室課程安排問題

雖然各大高校已加大對實驗室設(shè)施的投入，但是設(shè)施的配備數(shù)量畢竟是有限的。隨著互聯(lián)網(wǎng)時代的發(fā)展和信息技術(shù)的普及，各大高校開始重視對學(xué)生信息素養(yǎng)的培養(yǎng)，對高校各個專業(yè)的每一名學(xué)生都進(jìn)行計算機方面的教學(xué)，而計算機方面教學(xué)的展開除了基本理論知識的教學(xué)，更離不開實際的動手上機操作。所以有限數(shù)量的實驗室設(shè)施又要滿足高校不同專業(yè)，不同學(xué)生的課程使用需求。

實驗室課程安排問題是高校實驗室管理中的難點問題，因為它的實現(xiàn)需要考慮多方面的因素：

（1）授課老師。高校對授課老師的辦公室位置安排不同，在為授課老師安排實驗室時應(yīng)考慮到距辦公室的距離問題，盡量為老師安排距離近的實驗室，以方便老師進(jìn)行授課。若授課老師同時對不同班級進(jìn)行同一課程的連續(xù)兩節(jié)課的教學(xué)時，應(yīng)保證實驗室位置的不變，以防授課老師來回奔波耽誤教學(xué)。

（2）學(xué)生專業(yè)。對于不同專業(yè)的學(xué)生應(yīng)安排標(biāo)準(zhǔn)不同的實驗室。對于非計算機專業(yè)的學(xué)生而言，實驗室教學(xué)的難度不大，對計算機器材及軟件配備、環(huán)境配置的要求不高，可以為之安排一般類型的實驗室以供使用。而對于計算機專業(yè)及計算機相關(guān)專業(yè)的學(xué)生而言，所學(xué)知識對計算機性能要求可能較高，則需為之安排較優(yōu)類型的實驗室供其使用。以便實現(xiàn)實驗室器材的最優(yōu)配置和不同專業(yè)的學(xué)生更有針對性的進(jìn)行教學(xué)。

（3）課程類型。運用到計算機的課程中，分為純計算機及計算機加板書綜合教學(xué)的兩種類型。對于只運用計算機的課程只需配備有計算機設(shè)施的實驗室即可。而對于計算機加板書綜合教學(xué)類型的則具有特殊性，需安排既有計算機又有黑板的實驗室，以便于授課老師更好的進(jìn)行課程教學(xué)，提高實驗室使用效率。

（4）上課時間。上課時間對于實驗室安排是最基礎(chǔ)也是最重要的。首要條件是按照教學(xué)計劃的課程時間安排，為不同類別不同時間段的課程進(jìn)行無時間沖突的安排。且對于某個時間段，只可安排授課老師一門課程，某個實驗室也只能安排一門課程，否則會出現(xiàn)對象沖突。時間需控制在實驗室管理人員上班期間，以便對實驗室的使用進(jìn)行監(jiān)管，及時排查實驗室設(shè)施故障情況。

（5）實驗室容量。實驗室的容量應(yīng)大于上課學(xué)生的人數(shù)，如果小于則會出現(xiàn)某些學(xué)生沒有座位、沒有計算機完成學(xué)習(xí)的情況;如果等于，則可能某臺或某幾臺計算機故障，耽誤學(xué)生課程學(xué)習(xí)。所以安排實驗室也要考慮實驗室的容量問題。

1.3 實驗室預(yù)約排課問題

預(yù)約排課即把某些已知的影響排課的因素條件進(jìn)行合理的安排，如：專業(yè)、班級、課程名稱、學(xué)生人數(shù)、授課老師、上課時間、上課地點。具體可表現(xiàn)為如圖1所示。

2 禁忌搜索算法

2.1 禁忌搜索的簡述

禁忌（Tabu Search）算法是一種亞啟發(fā)式（meta-heuristic）隨機搜索算法，它從一個初始可行解出發(fā)，選擇一系列的特定搜索方向（移動）作為試探，選擇實現(xiàn)讓特定的目標(biāo)函數(shù)值變化最多的移動。為了避免陷入局部最優(yōu)解，TS搜索中采用了一種靈活的“記憶”技術(shù)，對已經(jīng)進(jìn)行的優(yōu)化過程進(jìn)行記錄和選擇，指導(dǎo)下一步的搜索方向，這就是Tabu表的建立。

為了找到“全局最優(yōu)解”，就不應(yīng)該執(zhí)著于某一個特定的區(qū)域。局部搜索的缺點就是太貪婪地對某一個局部區(qū)域以及其鄰域搜索，導(dǎo)致一葉障目，不見泰山。禁忌搜索就是對于找到的一部分局部最優(yōu)解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區(qū)間。

2.2 禁忌搜索算法主要思路

（1）在搜索中，構(gòu)造一個短期循環(huán)記憶表-禁忌表，禁忌表中存放剛剛進(jìn)行過的|T|（T稱為禁忌表）個鄰居的移動，這種移動即解的簡單變化。

（2）禁忌表中的移動稱為禁忌移動。對于進(jìn)入禁忌表中的移動，在以后的|T|次循環(huán)內(nèi)是禁止的，以避免回到原來的解，從而避免陷入循環(huán)。|T|次循環(huán)后禁忌解除。

（3）禁忌表是一個循環(huán)表，在搜索過程中被循環(huán)的修改，使禁忌表始終保持|T|個移動。

（4）即使引入了禁忌表，禁忌搜索仍可能出現(xiàn)循環(huán)。因此，必須給定停止準(zhǔn)則以避免出現(xiàn)循環(huán)。當(dāng)?shù)鷥?nèi)所發(fā)現(xiàn)的最好解無法改進(jìn)或無法離開它時，算法停止。

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

2.3.1 禁忌長度

在其他變量控制不變的情況下，從禁忌長度的因素來分析，禁忌長度越短，占用的機器內(nèi)存空間越小，可搜索的范圍區(qū)間相比之下會變大，這會導(dǎo)致實際能夠所搜到的區(qū)間范圍只占很小一部分，使得算法過早取得局部最優(yōu)解。而禁忌長度過長則會導(dǎo)致執(zhí)行過程中時間的增加。

2.3.2 特赦規(guī)則

對于在禁忌的對象中，如果出現(xiàn)以下三種情況，則將其禁忌長度設(shè)為0。

（1）當(dāng)出現(xiàn)這樣一種解，其目標(biāo)值優(yōu)于前面任意一個候選解;

（2）當(dāng)所有的解都被劃入禁忌表中，則選取評價函數(shù)值最小的那個解執(zhí)行特赦;

（3）當(dāng)某一對象的改變會引起目標(biāo)函數(shù)值的明顯變化時，則其可特赦。

2.3.3 候選集

候選集是通過其大小來影響禁忌搜索算法，候選集規(guī)模過大則會耗費過多的計算機內(nèi)存同時增加算法的處理時間，候選集規(guī)模過小過早取得局部最優(yōu)解。

2.4 禁忌搜索算法的過程

首先，輸入給定的算法參數(shù)，隨機產(chǎn)生初始解，這個初始解也就是滿足基本條件的解，但不一定是最優(yōu)解。由于禁忌搜索算法的特殊性和優(yōu)越性體現(xiàn)在其具有算法收斂準(zhǔn)則、特赦準(zhǔn)則、“best so far”狀態(tài)的判斷三個方面，判斷初始解是否具備以上三個特性，具體過程如圖2所示。

3 禁忌搜索算法在實驗室管理系統(tǒng)中的運用

基于以上的了解，禁忌搜索算法可對多目標(biāo)、多約束的求優(yōu)解問題進(jìn)行非局部的整體最優(yōu)求解。而實驗室中的排課及學(xué)生預(yù)約實驗室活動正是此類多目標(biāo)的最優(yōu)求解問題，因此將其算法運用入實驗室管理系統(tǒng)的設(shè)計，可大大提高實驗室的利用效率。

在實驗室排課問題中，最基本的兩大因素就是時間和地點，因此我們可根據(jù)這兩大因素首先確定一個最初解，時間與實驗室教師一一對應(yīng)，即同一時間，一間教室只能用于一堂課的使用。其次再把如教師，距離問題等因素考慮進(jìn)去，用禁忌搜索算法進(jìn)行求解。

4 結(jié)語

一個好的實驗室管理系統(tǒng)可大大減少實驗室管理員工作的復(fù)雜度，提高實驗室安排工作上的效率，從老師、學(xué)生、實驗室器材等多方面進(jìn)行考量，運用禁忌搜索算法對其進(jìn)行優(yōu)化，使得系統(tǒng)在求解過程中，在多因素、條件控制的情況下能夠迅速有效的找到最優(yōu)解，使得高校中實驗室教學(xué)的環(huán)節(jié)能更好的開展，提高教學(xué)質(zhì)量。

參考文獻(xiàn)

[1] 陳冰劍.計算機系實驗室管理系統(tǒng)的設(shè)計與實現(xiàn)[D].電子科技大學(xué)，2014.

[2] 劉艷.新形勢下高校計算機實驗室管理方法優(yōu)化[J].計算機光盤軟件與應(yīng)用，2013，16（07）：198+200.

[3] 況愛農(nóng).高校實驗室管理信息系統(tǒng)的研究與設(shè)計[D].電子科技大學(xué)，2007.