基于禁忌搜索算法的高校實(shí)驗(yàn)室管理系統(tǒng)優(yōu)化

邵婉婷

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

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

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

1 實(shí)驗(yàn)室管理中的問(wèn)題

1.1 實(shí)驗(yàn)室管理系統(tǒng)

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

1.2 實(shí)驗(yàn)室課程安排問(wèn)題

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

實(shí)驗(yàn)室課程安排問(wèn)題是高校實(shí)驗(yàn)室管理中的難點(diǎn)問(wèn)題，因?yàn)樗膶?shí)現(xiàn)需要考慮多方面的因素：

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

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

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

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

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

1.3 實(shí)驗(yàn)室預(yù)約排課問(wèn)題

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

2 禁忌搜索算法

2.1 禁忌搜索的簡(jiǎn)述

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

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

2.2 禁忌搜索算法主要思路

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

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

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

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

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

2.3.1 禁忌長(zhǎng)度

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

2.3.2 特赦規(guī)則

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

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

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

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

2.3.3 候選集

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

2.4 禁忌搜索算法的過(guò)程

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

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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