基于實(shí)驗(yàn)室預(yù)約機(jī)制算法的對(duì)比分析

董萃蓮，董海峰

（西安石油大學(xué)計(jì)算機(jī)學(xué)院，西安710065）

0 引 言

隨著高校信息化綜合體制的不斷改進(jìn)，對(duì)學(xué)生實(shí)踐能力的培養(yǎng)也已然成為一個(gè)長期追求目標(biāo)。與此相關(guān)的實(shí)驗(yàn)室預(yù)約排課問題［1］即已成為一個(gè)廣受關(guān)注的熱點(diǎn)探討內(nèi)容。但由于實(shí)驗(yàn)室預(yù)約排課研究是NP完全問題［2］，且容易受到多種因素的復(fù)雜影響［3］，因而就陸續(xù)涌現(xiàn)了不少基于實(shí)驗(yàn)室預(yù)約排課問題的算法，比如：遺傳算法［4］、蟻群算法［5］、課元算法［6］、圖論算法［7］、專家系統(tǒng)算法、模擬退火算法［8］、背包算法［9］等。

1 實(shí)驗(yàn)室預(yù)約問題

實(shí)驗(yàn)室預(yù)約主要是用于學(xué)生集中式預(yù)約和自主式預(yù)約，學(xué)生可以隨集體預(yù)約實(shí)驗(yàn)，也可自主預(yù)約實(shí)驗(yàn)。一般情況下，自主預(yù)約的實(shí)驗(yàn)不分配老師。對(duì)于集中式預(yù)約實(shí)驗(yàn)，不同專業(yè)、不同年級(jí)、不同班級(jí)的學(xué)生有可能選擇一個(gè)實(shí)驗(yàn)項(xiàng)目，在此種情況下根據(jù)課程情況指派相應(yīng)的實(shí)驗(yàn)室和輔導(dǎo)老師，為了使實(shí)驗(yàn)室器材資源可以物盡其用，能合理地安排老師指導(dǎo)學(xué)生實(shí)驗(yàn)，協(xié)調(diào)實(shí)驗(yàn)室、學(xué)生、老師三者之間的各種利益需求，使得學(xué)生可以受益最大化，實(shí)驗(yàn)室資源利用率最大化［10］；再者，對(duì)于自主式預(yù)約實(shí)驗(yàn)，為減少學(xué)生預(yù)定了實(shí)驗(yàn)后失約而造成實(shí)驗(yàn)室資源的閑置和浪費(fèi)，以及其它有此需要的學(xué)生還未能及時(shí)預(yù)約實(shí)驗(yàn)的現(xiàn)象［11］，這里擬將針對(duì)基于背包算法［12-13］和模擬退火算法在實(shí)驗(yàn)室預(yù)約機(jī)制的性能優(yōu)劣上做出分析對(duì)比，詳情展開如下。

2 算法分析

2.1 背包算法

背包算法［14-15］可以理解為給定一些物體，每個(gè)物體都有自己的重量和價(jià)值，在一定的總重量之內(nèi)，應(yīng)如何進(jìn)行擇取，能使得物品的總價(jià)值最大［16］。

假定實(shí)驗(yàn)室數(shù)為N，實(shí)驗(yàn)室的編號(hào)設(shè)為k（k小于等于N），每間實(shí)驗(yàn)室可容納人數(shù)在此設(shè)一固定值，一項(xiàng)實(shí)驗(yàn)進(jìn)行的人數(shù)分值為p［i］（i為項(xiàng)目數(shù)），人數(shù)分值等于人數(shù)值、即一人為一分，設(shè)定老師指導(dǎo)權(quán)重分值為 t［i］，因此有老師指導(dǎo)的情況設(shè)定 t［i］初值為2分，否則為1分，設(shè)一項(xiàng)目實(shí)驗(yàn)的實(shí)驗(yàn)學(xué)術(shù)評(píng)估分值為a［i］（即每個(gè)項(xiàng)目的學(xué)術(shù)評(píng)估分值），以此來區(qū)分每個(gè)實(shí)驗(yàn)項(xiàng)目的學(xué)術(shù)價(jià)值和重要性，該項(xiàng)基礎(chǔ)分值為1分，每隔0.5分作增減，設(shè)定實(shí)驗(yàn)的綜合需求分為z［i］，設(shè)定時(shí)間段的受益總分值為w（其初值設(shè)定為0）。在學(xué)生自主預(yù)約實(shí)驗(yàn)室時(shí)，基于集中式預(yù)約實(shí)驗(yàn)室增加一個(gè)信譽(yù)度的參數(shù)c［i］，每個(gè)學(xué)生的初始信譽(yù)度設(shè)置為10，每失約一次信譽(yù)度減1［17］。

2.1.1 預(yù)約實(shí)驗(yàn)室的算法研究

（1）集中式預(yù)約實(shí)驗(yàn)室的設(shè)計(jì)分析

①情況一：如果該項(xiàng)目人數(shù)大于實(shí)驗(yàn)室可容納人數(shù)，則：

②情況二：該項(xiàng)目人數(shù)小于實(shí)驗(yàn)室可容納人數(shù)，則：

（2）自主式預(yù)約實(shí)驗(yàn)室的設(shè)計(jì)分析

①如果該項(xiàng)目人數(shù)大于實(shí)驗(yàn)室可容納人數(shù)，則：

②該項(xiàng)目人數(shù)小于實(shí)驗(yàn)室可容納人數(shù)，則：

2.1.2 基于實(shí)驗(yàn)室預(yù)約的背包算法［18-19］

Step 1計(jì)算出一個(gè)時(shí)間段中每個(gè)實(shí)驗(yàn)項(xiàng)目的實(shí)驗(yàn)綜合需求分。

Step 2找出實(shí)驗(yàn)綜合需求分中最大的實(shí)驗(yàn)項(xiàng)目。

Step 3對(duì)實(shí)驗(yàn)綜合需求分最大的實(shí)驗(yàn)項(xiàng)目分配實(shí)驗(yàn)室，如果預(yù)約該實(shí)驗(yàn)項(xiàng)目的學(xué)生人數(shù)大于一個(gè)實(shí)驗(yàn)室的容納人數(shù)，則按公式（1）更新該項(xiàng)目的實(shí)驗(yàn)綜合需求分，按公式（2）更新受益總分，更新該項(xiàng)目的總?cè)藬?shù)，否則將該項(xiàng)目的實(shí)驗(yàn)綜合需求分置為0，按公式（5）更新該項(xiàng)目的受益總分，更新該實(shí)驗(yàn)項(xiàng)目的總?cè)藬?shù)為0。

Step 4用更新后的值代替原來的，重復(fù)Step 2～Step 3。

Step 5當(dāng)已有實(shí)驗(yàn)室已經(jīng)安排滿或者實(shí)驗(yàn)綜合需求分最大為0，則終止循環(huán)。

至此，研究可得到背包算法的設(shè)計(jì)流程如圖1所示。在實(shí)驗(yàn)室沒有排至滿額的情況下，空閑的實(shí)驗(yàn)室可以作為學(xué)生自主學(xué)習(xí)的實(shí)驗(yàn)室用，但不對(duì)其分配老師進(jìn)行輔導(dǎo)、也不設(shè)定限制，學(xué)生可依據(jù)自己的時(shí)間安排在工作日內(nèi)隨時(shí)去進(jìn)行實(shí)驗(yàn)。預(yù)約情況將進(jìn)行統(tǒng)一集中公布，沒有預(yù)約成功的學(xué)生可以轉(zhuǎn)入下一輪的預(yù)約，但卻需要提前數(shù)周來申請(qǐng)預(yù)約。在某些時(shí)間段若發(fā)現(xiàn)預(yù)約實(shí)驗(yàn)室的人數(shù)很少，此時(shí)會(huì)有很多閑置的實(shí)驗(yàn)室，為此即可將下一時(shí)間段或者預(yù)約人數(shù)較多的時(shí)間段的實(shí)驗(yàn)項(xiàng)目調(diào)配轉(zhuǎn)換至此空閑時(shí)間段內(nèi)，只是在該種情況下還需要對(duì)程序做出一定的修改［20］。

綜上分析［21］只是對(duì)集中式預(yù)約實(shí)驗(yàn)提供了算法描述，自主式預(yù)約實(shí)驗(yàn)室的算法在計(jì)算實(shí)驗(yàn)項(xiàng)目需求分和受益分時(shí)需要引入信譽(yù)度分進(jìn)行相應(yīng)的換算，在此不作贅述。

圖1 背包算法流程圖Fig.1 Knapsack algorithm flow chart

2.2 模擬退火算法

模擬退火算法［22］是以某一比較高的初溫為出發(fā)點(diǎn)，伴隨著溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解。模擬退火算法［23］包括3個(gè)函數(shù)、2個(gè)準(zhǔn)則，分別是：狀態(tài)產(chǎn)生函數(shù)、狀態(tài)接受函數(shù)、退溫函數(shù)、以及抽樣穩(wěn)定準(zhǔn)則和退火結(jié)束準(zhǔn)則。

假設(shè)實(shí)驗(yàn)室的預(yù)約排課的周期為一周，本次研究則致力于將一個(gè)實(shí)驗(yàn)項(xiàng)目集安排到一組時(shí)間和一組實(shí)驗(yàn)室中。設(shè)實(shí)驗(yàn)項(xiàng)目集Xi為第i項(xiàng)實(shí)驗(yàn)，Pi表示指導(dǎo)教師，Si表示實(shí)驗(yàn)項(xiàng)目的學(xué)生數(shù)量，時(shí)間段Tm表示一周中的實(shí)驗(yàn)時(shí)間劃分，Rk表示實(shí)驗(yàn)室編號(hào)（且設(shè)實(shí)驗(yàn)室可容納學(xué)生數(shù)為固定值），Lin表示某項(xiàng)實(shí)驗(yàn)Xi安排的實(shí)驗(yàn)時(shí)間段組，G（S）表示目標(biāo)函數(shù)，故而，此問題的最佳解決方案可表示為：S（Lin，Tm，Rk）。

由此，可推得基于實(shí)驗(yàn)室預(yù)約的模擬退火算法的設(shè)計(jì)流程如圖2所示，對(duì)其流程步驟可闡釋解析如下。

Step 1設(shè)置初溫T0，初始解S，預(yù)設(shè)迭代次數(shù)為L，計(jì)算目標(biāo)函數(shù)G（S）。

Step 2擾動(dòng)生成新解S?，計(jì)算目標(biāo)函數(shù)G（S?）。

Step 3計(jì)算目標(biāo)函數(shù)的增量ΔG＝G（S?）-G（S）。

Step 4當(dāng)目標(biāo)函數(shù)的增量大于0時(shí)，按照Metropolis準(zhǔn)則［24］選擇新的解，否則以當(dāng)前解S?為當(dāng)前新解。

Step 5當(dāng)未達(dá)到預(yù)設(shè)迭代次數(shù)時(shí)，返回Step 2，否則進(jìn)入 Step 6。

Step 6判斷是否滿足停止條件，若未滿足，則降低溫度返回Step 2，否則，迭代結(jié)束，返回最優(yōu)解S?。

圖2 模擬退火算法流程圖Fig.2 Flow chart of simulated annealing algorithm

3 算法的對(duì)比分析

考慮到前文2種算法對(duì)于實(shí)驗(yàn)室預(yù)約排課時(shí)的著重點(diǎn)各有不同，即使用于同一約束條件下的實(shí)驗(yàn)室項(xiàng)目預(yù)約，得到的結(jié)果也未必一致。因此，需要根據(jù)實(shí)際情況加以選擇性使用，對(duì)比分析［25］這2種算法的優(yōu)缺點(diǎn)后，對(duì)此內(nèi)容可分述如下。

（1）算法機(jī)理對(duì)比。背包算法分2種情況考慮，在學(xué)生自主預(yù)約實(shí)驗(yàn)室時(shí)，加入了信譽(yù)度參數(shù)，從而約束學(xué)生使得實(shí)驗(yàn)室資源盡可能地不被浪費(fèi)，而模擬退火算法中是對(duì)大集體的實(shí)驗(yàn)室預(yù)約的排列求解，并未充分考慮到學(xué)生的自主性。

（2）算法復(fù)雜度對(duì)比。背包算法［26-27］的算法復(fù)雜度為2，模擬退火算法的復(fù)雜度為5，相比而言模擬退火算法的實(shí)現(xiàn)難度較背包算法大。

（3）算法應(yīng)用范圍對(duì)比。此處的背包算法比較適合于解決小型的實(shí)驗(yàn)室預(yù)約安排，范圍相對(duì)較小，而此處的模擬退火算法比較適合相對(duì)大型的實(shí)驗(yàn)室預(yù)約安排。

（4）涉及因素對(duì)比。2種算法的考慮因素都是多重的，對(duì)于參數(shù)的選擇有所不同。

（5）算法的適用性分析。2種算法常常是圍繞某一場(chǎng)景問題來進(jìn)行相應(yīng)設(shè)計(jì)，通用性較差。

4 結(jié)束語

本文中，對(duì)于以上2種算法的學(xué)習(xí)分析主要是基于實(shí)驗(yàn)室預(yù)約機(jī)制的環(huán)境模擬［28］，缺乏相對(duì)深入的數(shù)學(xué)推理分析論證。但對(duì)于解決同一類型問題的各種算法［29-30］，這些算法往往各具特色，不能一概而論，需根據(jù)具體情況給出具體分析。有時(shí)，可用一種算法解決某類問題，而在其它時(shí)候則可用多種算法結(jié)合的方法來解決另一類問題，以求得到最佳設(shè)計(jì)方案。