邵婉婷
摘要:隨著信息技術(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.