高校排考系統(tǒng)資源沖突優(yōu)化算法的研究

岳沙沙

摘要：隨著高校學(xué)生人數(shù)的不斷增加，教學(xué)資源匱乏問(wèn)題日益明顯，使得考務(wù)安排工作變得繁重且繁瑣。為解決高校排考系統(tǒng)資源沖突優(yōu)化問(wèn)題，文章根據(jù)高校的考場(chǎng)安排問(wèn)題進(jìn)行了分析、抽象以及數(shù)學(xué)描述，通過(guò)構(gòu)建簡(jiǎn)單無(wú)向圖利用蟻群算法來(lái)解決排考時(shí)間安排的沖突問(wèn)題；利用循環(huán)隊(duì)列方法解決監(jiān)考教師安排的沖突問(wèn)題；提出了一種考場(chǎng)安排算法解決排考問(wèn)題中的考場(chǎng)安排問(wèn)題。文章針對(duì)各類排考資源（教室、監(jiān)考教師、考試時(shí)間等）在最優(yōu)考試時(shí)間段的選取組合優(yōu)化問(wèn)題，構(gòu)建了具體算法描述過(guò)程，解決了考試時(shí)間安排、考場(chǎng)安排及監(jiān)考教師安排三者的沖突問(wèn)題，應(yīng)用該方法使得排考系統(tǒng)資源沖突優(yōu)化問(wèn)題得以解決，自動(dòng)排考系統(tǒng)運(yùn)行效率得到了提高，各類排考資源之間的沖突現(xiàn)象明顯減少，進(jìn)而提高了高校教務(wù)管理人員的工作效率。

關(guān)鍵詞：高校排考系統(tǒng)；簡(jiǎn)單無(wú)向圖；循環(huán)隊(duì)列；考場(chǎng)安排；蟻群算法；組合優(yōu)化

考場(chǎng)安排是高校考務(wù)管理活動(dòng)的主要組成部分，由于排考沖突條件多，數(shù)據(jù)量大，人工排考無(wú)疑是一種繁復(fù)、瑣碎的工作。面對(duì)我國(guó)高校因擴(kuò)招而帶來(lái)的教育資源配置不足與培養(yǎng)方式多樣化之間以及教學(xué)資源短缺與考試方式多元化之間日益嚴(yán)重的矛盾，需要在各高校開(kāi)展教育國(guó)際化和協(xié)同創(chuàng)新體系，為適應(yīng)新時(shí)代的要求，實(shí)現(xiàn)學(xué)生考試管理方式的智能化就顯得十分必要。

1 排考問(wèn)題分析

排考問(wèn)題是要解決資源的有序組合，屬于時(shí)間表問(wèn)題。研究如何把高校的教師資源、教室資源、學(xué)生、班級(jí)、課程、考試時(shí)間資源等排考資源有機(jī)結(jié)合，從而使組合得到的資源是最優(yōu)的，也即場(chǎng)次盡量地少而安排合理的考試考場(chǎng)時(shí)間安排表。這些排考資源之間是相關(guān)的，在排考過(guò)程中可謂牽一發(fā)而動(dòng)全身，要實(shí)現(xiàn)排考過(guò)程的最優(yōu)化，則需要在多約束條件下，通過(guò)多種優(yōu)化規(guī)則，使現(xiàn)有的排考資源在編排過(guò)程中最大程度地達(dá)到最優(yōu)化。

總體來(lái)說(shuō)，排考主要解決的問(wèn)題是同一名考生不能在同一個(gè)時(shí)間段內(nèi)考多門(mén)課程（考試時(shí)間安排）；同一名教師不能在同一時(shí)間段內(nèi)監(jiān)考多門(mén)課程（監(jiān)考安排）；一個(gè)考場(chǎng)不能在同一時(shí)間段內(nèi)安排多門(mén)課程（考場(chǎng)安排）。也即解決考試時(shí)間安排、監(jiān)考安排、考場(chǎng)安排這三者之間的沖突問(wèn)題并且排考結(jié)果要求考生的各門(mén)考試課程之間要有一定的時(shí)間間隔以保證考生有足夠的調(diào)解時(shí)間。抽象的排考問(wèn)題已經(jīng)被證明是一種NP難問(wèn)題，至今沒(méi)有一種能適用于所有情況、結(jié)果普遍令人滿意的解。

2 排考問(wèn)題數(shù)學(xué)描述

在考試安排的過(guò)程中，主要涉及時(shí)間、考場(chǎng)、教師、學(xué)生、課程、班級(jí)這6個(gè)實(shí)體集合。以下是對(duì)這6個(gè)實(shí)體集合的定義：

（l）時(shí)間集合：

T={t₁，t₂…t_n}，共有n個(gè)考試時(shí)間段。

（2）考場(chǎng)集合：

R={r₁，r₂…r_m}，共m個(gè)考場(chǎng)用于考試安排。

（3）教師集合：

P={p₁，p₂…p_i}，共有i個(gè)教師參加監(jiān)考。

（4）學(xué)生集合：

S={s₁，s₂…s_j}，共有j個(gè)學(xué)生參加考試。

（5）課程集合：

C={c₁，c₂…c_k}，共有k個(gè)課程需要安排考試。

（6）班級(jí)集合：

Z={z₁，z₂…z_l}，共l個(gè)班級(jí)需要安排考試。

根據(jù)這6個(gè)實(shí)體集合構(gòu)造簡(jiǎn)單無(wú)向圖G=（V.E，c），其中V代表頂點(diǎn)集，每一門(mén)考試科目代表一個(gè)頂點(diǎn)，共有k門(mén)考試科目，則圖G中共有k個(gè)頂點(diǎn)。

V={v₁，v₂…v_k}。

E代表各項(xiàng)點(diǎn)相互連接所組成的邊集。如果有考生同時(shí)參加某2門(mén)考試科目的考試，則對(duì)應(yīng)的頂點(diǎn)之間有邊相連。

c為各邊權(quán)值的集合，定義為共同參加該邊連接的2個(gè)頂點(diǎn)對(duì)應(yīng)的考試科目考試的考生人數(shù)。如果有n個(gè)學(xué)生同時(shí)參加和這2門(mén)課程的考試，則v_i和v_j之間就有1條邊相連，即e_ij。邊的權(quán)值為n。

G的鄰接矩陣B=（b_ij）_kxk一個(gè)對(duì)稱陣，其維數(shù)為考試科目數(shù)，矩陣B中元素取值如下定義：

通過(guò)鄰接矩陣B的構(gòu)建，可見(jiàn)考試課程間的關(guān)系僅有2種表示方式，即相容（不存在1個(gè)學(xué)生同時(shí)選修2門(mén)課程的情況）；相斥（存在至少有1個(gè)學(xué)生同時(shí)選修2門(mén)課程的情況）。因此，用O表示相容，則2門(mén)課程同時(shí)安排在同一考場(chǎng)的條件完全滿足；而用1表示相斥，則2門(mén)課程同時(shí)安排在同一考場(chǎng)會(huì)引起課程沖突。 將上述鄰接矩陣B進(jìn)行簡(jiǎn)化，得到考試課程關(guān)系矩陣 矩陣M中元素取值如下：

依據(jù)課程關(guān)系矩陣M，可以得到如下2類數(shù)據(jù)：

（1）課程關(guān)聯(lián)系數(shù) ，其中k代表課程數(shù)。課程關(guān)聯(lián)系數(shù)的值越大，代表課程之間的相容性越差，即與其他課程組合能力越弱。

（2）與第i門(mén)課程相容的課程候選集，由滿足 條件的所有課程組成。

由關(guān)系矩陣M得出的2類數(shù)據(jù)可見(jiàn)，本文提出的排考算法為了使整個(gè)排考結(jié)果得以合理優(yōu)化，首先必須保證“考試課程之間在資源分配上無(wú)沖突”，滿足安排考試場(chǎng)次最少，盡可能使連考的學(xué)生數(shù)量少。

根據(jù)上述定義，將三元組t₁：<學(xué)生，課程，班級(jí)>看作事件，三元組t₂：<時(shí)間，考場(chǎng)，教師>看作資源，排考問(wèn)題就轉(zhuǎn)化為事件t₁分配合理的資源t₂，也就是解決時(shí)間、考場(chǎng)及教師之間的沖突問(wèn)題。

3 相關(guān)算法的構(gòu)建

3.1 考場(chǎng)時(shí)間安排算法

考場(chǎng)時(shí)間安排是排考過(guò)程一項(xiàng)重要的任務(wù)，科學(xué)、合理的考場(chǎng)安排方法不僅可以提高考試安排工作的效率，而且可以解決人工排考過(guò)程中出現(xiàn)的問(wèn)題。因此，在安排考場(chǎng)時(shí)，首先需解決的問(wèn)題是如何將選修同一門(mén)課程的學(xué)生安排在同一考場(chǎng)同一時(shí)段進(jìn)行考試且同一時(shí)間段內(nèi)1個(gè)學(xué)生只能參加1門(mén)課程考試。

時(shí)間安排從算法實(shí)現(xiàn)上來(lái)講可分為2個(gè)過(guò)程：從排考問(wèn)題中抽象出圖論的模型，將時(shí)間安排算法轉(zhuǎn)化為蟻群算法，得出多組可用解；再?gòu)目捎媒庵羞x取相對(duì)較好的解作為最終結(jié)果。

在使用蟻群算法求解考試時(shí)間安排優(yōu)化問(wèn)題時(shí)，螞蟻需要具備以下行為特征：

（l）螞蟻通過(guò)利用第2小節(jié)構(gòu)建的簡(jiǎn)單無(wú)向圖G={V，E，C}來(lái)尋找最優(yōu)解X^*。

（2）螞蟻具有記憶能力。與現(xiàn)實(shí)中的螞蟻不同，本文所采用的蟻群算法的人工螞蟻具有記憶能力，每個(gè)螞蟻對(duì)應(yīng)一個(gè)禁忌表M'，禁忌表M'中主要是用于：①幫助螞蟻記住該螞蟻在此次循環(huán)中，圖中哪些考試科目已經(jīng)分配過(guò)時(shí)間，哪些考試科目還沒(méi)有分配，從而避免再次選擇已經(jīng)選擇過(guò)的考試科目。②螞蟻從圖G的某一個(gè)頂點(diǎn)選取下一個(gè)頂點(diǎn)的概率是與該2點(diǎn)之間的權(quán)值有關(guān)的啟發(fā)信息η和邊上存有的信息素量的函數(shù)。這個(gè)概率直接反映的是考試科目之間的期望關(guān)聯(lián)程度。通過(guò)禁忌表螞蟻記住當(dāng)前選擇的頂點(diǎn)，幫助確定2點(diǎn)之間的權(quán)值，計(jì)算啟發(fā)信息η，從而決定螞蟻選擇下一個(gè)頂點(diǎn)的概率。這樣螞蟻們可以知道哪個(gè)考試科目安排在當(dāng)前的時(shí)間點(diǎn)相對(duì)較合適。③螞蟻完成一次循環(huán)以后，通過(guò)禁忌表構(gòu)建出一個(gè)可行解，計(jì)算出目標(biāo)函數(shù)值，并且可以同其他螞蟻循環(huán)后的目標(biāo)函數(shù)值進(jìn)行比較，找出最小目標(biāo)函數(shù)值所對(duì)應(yīng)的可行解。此后，禁忌表被清空，螞蟻可以進(jìn)行下一次的循環(huán)。

（3）螞蟻按照概率選擇策略進(jìn)行移動(dòng)。概率選擇策略增加了路徑隨機(jī)選擇的可能性，避免算法過(guò)早收斂于局部的解。概率選擇策略是一個(gè)關(guān)于局部可用的信息素和啟發(fā)信息（即螞蟻所在的圖G中當(dāng)前位置的鄰域上與頂點(diǎn)連接有關(guān)的信息素和啟發(fā)信息）的函數(shù)。

（4）一旦螞蟻建立了一個(gè)可行解，它可以按照原路返回并在返回的過(guò)程中對(duì)連接頂點(diǎn)的邊上的信息素進(jìn)行更新。

算法偽代碼如下：

procedure AS

for each edge

set initial pheromone value to

end of

while not stop

for each ant m

randomly choose an initial vertex

for i-l to k

choose next vertex with probability

end for

end for

compute the length Lk of the path constructed by the mth ant

for each edge

update the preromone value

end for

end while

print result

end procedure

蟻群算法對(duì)排考過(guò)程中的考試時(shí)間安排，提供了臺(tái)理的考試時(shí)間安排表，解決了時(shí)間和教室沖突問(wèn)題。

3.2 考場(chǎng)安排算法

學(xué)校的教室一般座位數(shù)固定不變，依據(jù)功能分為多媒體教室、普通教室、實(shí)驗(yàn)室等，根據(jù)各門(mén)課程考試要求，例如英語(yǔ)課程考試要求教室具有聽(tīng)力設(shè)備，安排相應(yīng)合理的教室進(jìn)行考試。同時(shí)，還要依據(jù)選修課程的學(xué)生數(shù)安排具有相近數(shù)量座位的教室進(jìn)行考試。

考場(chǎng)安排算法大致步驟如下：

（l）判斷課程有無(wú)特殊要求，為其安排合理的教室。

（2）依據(jù)選修課程的學(xué)生人數(shù)，教室的座位數(shù)量（教室的座位數(shù)量>選修課程學(xué)生人數(shù)）為其安排考場(chǎng)。

（3）若學(xué)生人數(shù)大于最大教室的座位數(shù)量，則應(yīng)該依據(jù)考生人數(shù)安排相應(yīng)數(shù)量的教室。

3.3 監(jiān)考教師安排算法

根據(jù)3.1考試時(shí)間安排算法以及3.2考場(chǎng)安排算法，在監(jiān)考教師安排算法的設(shè)計(jì)過(guò)程中構(gòu)造一個(gè)循環(huán)隊(duì)列R，存儲(chǔ)教師的信息，且用count存放隊(duì)列R中元素的個(gè)數(shù)。給已經(jīng)分配考試時(shí)間以及考試地點(diǎn)的考試任務(wù)分配監(jiān)考教師，判斷考場(chǎng)的考試人數(shù)，讀取預(yù)先設(shè)定參數(shù)t（多少學(xué)生分配一個(gè)監(jiān)考老師）分配監(jiān)考老師，本文設(shè)t=15。如果需要監(jiān)考老師n人，就從循環(huán)隊(duì)列中讀取n個(gè)教師分配給這個(gè)考試任務(wù)以盡量增大監(jiān)考的間隔。

按照監(jiān)考編排算法的描述過(guò)程，算法流程如圖l所示。

該算法完成對(duì)考試任務(wù)進(jìn)行監(jiān)考教師的安排。

4 結(jié)語(yǔ)

本文針對(duì)高校教務(wù)管理中的排考資源沖突問(wèn)題進(jìn)行優(yōu)化，采用蟻群算法對(duì)考試時(shí)間進(jìn)行安排；根據(jù)考試時(shí)間安排和考場(chǎng)安排算法得出已經(jīng)分配考試時(shí)間以及考試地點(diǎn)的考試任務(wù)，又利用監(jiān)考安排算法對(duì)考試任務(wù)進(jìn)行監(jiān)考教師的安排，從而完成排考過(guò)程。解決了排考在時(shí)間、監(jiān)考教師及考場(chǎng)資源之間的沖突問(wèn)題，為高校的教學(xué)工作得順利進(jìn)行提供了便捷。