eHTA算法研究綜述

摘要:eHTA算法是對人工智能中的啟發(fā)式搜索理論加以分析和改進(jìn)，設(shè)計的一種適用于高校排課的算法，它包含了靠邊策略、擇劣策略、前景探測策略、學(xué)習(xí)策略等內(nèi)容。eHTA算法應(yīng)用在高校排課系統(tǒng)中，在減少人工干預(yù)排課次數(shù)、科學(xué)安排教師、均衡班級和教師的日負(fù)荷等方面起到了良好的效果，大大提高了排課效率。

關(guān)鍵詞:eHTA;啟發(fā)式算法;高校排課

中圖分類號:TP312文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2009)26-7475-03

eHTA Algorithms Reviewed

WANG Mei

(Jiangsu Maritime Institute， Nanjing 211170， China)

Abstract: eHTA algorithm of artificial intelligence is the heuristic search theory analysis and improvement， and design of a suitable timetabling algorithm， it contains a side strategy， choosing bad strategy， tactics， learning strategy prospects detection， etc. EHTA algorithm used in universities in system， reduce artificial intervention， reasonable arrangement of course， teachers and balanced class teacher of load on the good effect， can greatly improve the efficiency of course.

Key words: eHTA; heuristic algorithm; timetabling

高校排課是教學(xué)管理中最基本的、最重要的一項(xiàng)工作，其實(shí)質(zhì)就是為教學(xué)計劃中設(shè)置的課程安排合適的時間和地點(diǎn)，保證整個教學(xué)工作能夠順利地進(jìn)行。然而，排課問題被證明是一個NP問題，即沒有答案，只可能找更好的解決方案的問題。

本文介入這個課題，就目前高校始終以自動排課和手工排課交替作業(yè)的現(xiàn)狀，研究如何減少人工干預(yù)，實(shí)現(xiàn)基本自動化排課的最佳目標(biāo)。

1 啟發(fā)式排課算法(HTA算法)

人工智能中的啟發(fā)式搜索理論(Heuristic Search theory)是根據(jù)一定的規(guī)則，逐步求得中間解，并對中間解不斷進(jìn)行分析和優(yōu)化，最終搜索到目標(biāo)。啟發(fā)式搜索理論運(yùn)用在排課問題上，產(chǎn)生的算法要受到很多限制條件的影響，需要將這個理論和排課的基本原則結(jié)合起來，滿足高校對自動排課系統(tǒng)地要求，排課算法才能真正起到好的作用。

1.1 排課問題的分析

為了方便考慮和描述問題，將每次授課所包含的幾個要素組成的4元組(課程，班級列表，教師，周學(xué)時)稱作課元。將一周內(nèi)可供安排的每節(jié)上課時間稱作時間片，由時間片和課室構(gòu)成的序偶(時間片，教室)稱作時空片。將教室相同，時間在同一天的連續(xù)的若干個時空片的集合稱作時空片簇。因此排課的任務(wù)是為給定的每個課元合理地分配時空片簇。

我們對影響排課的約束條件進(jìn)行分類和量化，將約束條件分成三個層次:

1)硬約束條件

這個約束條件是保證排課系統(tǒng)能夠安排出一張基本的課表，主要包括:① 按課元及周學(xué)時分配時空，做到一天之內(nèi)安排兩次或兩次以上的課時;② 每個時空片最多只能分配給一個課元;③ 每個班級在同一個時間片內(nèi)最多只能有一門課程;④ 每個教師在同一個時空片內(nèi)最多只能有一門課;⑤ 其它必須滿足的條件。

2)優(yōu)化約束條件

旨在使課程的安排盡可能合理、科學(xué)，例如:① 為了利于學(xué)生的學(xué)習(xí)，同一班級的同一課程課元的時間間隔均勻且不在一天內(nèi)安排.而課室則盡可能相同。② 教學(xué)計劃中課程的性質(zhì)不一樣，盡可能給重點(diǎn)課程的課元分配好的時間片。③ 給相應(yīng)的課元安排合適的教室，比如多媒體教室和機(jī)房。

3)特殊約束條件

從工作人性化的角度出發(fā)，主要是指教師個人提出的一些特殊的合理要求。特殊的約束條件一部分是靜態(tài)的，有些是動態(tài)的。靜態(tài)的約束條件是指在排課之前就有的約束，并且這些約束要貫穿整個課程實(shí)施的過程;而動態(tài)約束條件是指排課結(jié)束后產(chǎn)生的，比如調(diào)課后，原來的時間空間如何安排?

1.2 排課問題的數(shù)學(xué)描述

設(shè)C是所有課元的集合，TR是所有時空片的集合。將問題的解定義為給每個課元按照其周學(xué)時數(shù)分配互不相交的時空片的方案，滿足了全部硬約束條件的解就是一個基本解或稱可行解(即一張課表)。最優(yōu)解為最大程度滿足優(yōu)化約束條件和特殊約束條件的可行解(即一張最滿意的課表)。將所有的優(yōu)化約束條件和特殊約束條件依次編號為1，2，...，S，并對它們賦予相應(yīng)的權(quán)重wi≥0(1≤i≤s)，編號前的權(quán)重大，編號后的權(quán)重小。為了在數(shù)量上體現(xiàn)這些約束條件的滿足情況，我們引入兩個概念。

定義2-1 設(shè)t是可行解，i∈C是課元，定義函數(shù)

f(i，t)=W1X1+W2X2+ …+ WnXn (1)

并稱f(i，t)為課元i在可行解t中的不滿意度。其中.Xj∈{0，1}(1≤j≤s)表示在t中課元i的安排是否違反了第j個約束條件，若違反，Xj=1，否則Xj=0。對于權(quán)重Wi≥0(1≤i≤s)的確定，一般來說，硬約束條件和優(yōu)化約束條件的權(quán)重較大.而特殊約束條件的權(quán)重較小。

定義2-2 設(shè)t是可行解，定義評價函數(shù):

E(t)=∑i∈c f(i.t) (2)

并稱E(t)為可行解t的不滿意度。

將(2)作為我們的目標(biāo)函數(shù)，即搜索到盡可能使E(t)達(dá)到較小值的可行解t。

1.3 HTA算法分析

1.3.1 優(yōu)先權(quán)策略

課元所具有的屬性包括課程的類型、班級的數(shù)量、周學(xué)時，根據(jù)這些屬性可以給課元賦以優(yōu)先權(quán)。一般地，課元的優(yōu)先權(quán)值越大，課元的約束就越多，從而可供其選擇的滿意的時空片或時空片簇就少，所以應(yīng)該優(yōu)先安排。優(yōu)先權(quán)策略就是，按照課元的優(yōu)先權(quán)由大到小依次來給課元安排時空片簇。

1.3.2 最佳分配策略

所有可用教室和上課時間構(gòu)成一個完全時空片簇，將時空片簇上的排課情況視為格局TR，在任一時刻，由所有已被“合法”安排了時空片簇(即滿足硬約束條件)的課元子集Csub 在TR中形成的部分課表TR(Csub)為系統(tǒng)在此時刻的格局。所有課元均已被安排了時空片簇的格局稱為目標(biāo)格局(即可行解)。剩余課元中尚有課元可合法安排的非目標(biāo)格局為活格局。否則稱為死格局。

在某活格局TR(Csub )下，對于課元c∈C-Csub，稱TR(Csub)中每一個能合法安排下c的空閑時空片簇為課元c的可行時空片簇。

在某活格局TR(Csub)下，考慮課元c ∈C—Csub的安排。設(shè)FS≠Φ 是該格局下課元c的可行時空片簇集。對于任意的ts ∈FS，定義課元c對ts的不滿意度為:

g(c，ts，TR(Csub)) = W1X1+ W2 X2+…+Ws Xs

其中W j，(1≤j≤s)為評價函數(shù)E(t)中的權(quán)值，Xj ∈{0，1}表示在部分課表TR(Csub)中若將ts分配給c后c的安排是否滿足第j個約束條件，若不滿足，則Xj=1，否則Xj=0。

顯然，若從格局TR(Csub)最后能到達(dá)目標(biāo)格局TR(C)，則有g(shù)(c，ts，TR(Csub))≤f(c，TR(C))。

1.3.3 HTA 算法描述

根據(jù)上面的兩個策略，對啟發(fā)式排課算法(HTA)用下列流程圖1描述。

由于HTA算法的結(jié)果對于課元優(yōu)先次序很敏感，即排課結(jié)果往往會因課元的優(yōu)先次序不同而差別較大，而在這里又常常需要人工的干預(yù)。為了在較大程度上消除這種敏感性，對HTA算法進(jìn)行改進(jìn)，采用靠邊策略、擇劣策略、前景策略、學(xué)習(xí)策略等，提高HTA算法的效率，改進(jìn)的HTA算法稱為eHTA算法。

2 優(yōu)化的啟發(fā)式排課算法(eHTA)

2.1 靠邊策略和擇劣策略應(yīng)用

在某活格局TR(Csub)下，考慮課元c ∈C-Csub的安排，其周學(xué)時為P，每次課時p=2，那么在部分課表TR(Csub )中任意大小為p(2)的空閑時空片簇都有可能是其可行時空片簇。例如，某個最大空閑時空片簇如圖2所示。

圖2 最大空閑時空片簇

其大小為8。P=4，p=2，對于課元而言，實(shí)際上它對應(yīng)7個大小為2的空閑時空片簇:1-2，2-3，3-4、4-5，5-6，6-7，7-8。我們首先考慮靠邊的兩個時空片7-8和1-2。采用靠邊策略一方面可以縮小搜索范圍，另一方面可以使得時空片的剩余空間更好利用，為后面課元的安排留下更多的機(jī)會。其次，在優(yōu)化排課后，從可行的時空片簇中選擇最劣的時空片簇，目的也是為了后面的排課在時空片簇上有更多的選擇。

2.2 前景探測策略應(yīng)用

在某活格局α = TR(Csub)下，考慮課元c ∈C-Csub的安排。設(shè)FS≠Φ 是該格局下課元c的可行時空片簇集。對于任意的ts∈FS，新格局TR(Csub ) ∪{c←ts)(在TR(Csub)中將課元c安排在ts處后所得的新課表)均可能是格局α的后繼格局。用h(c，ts，α)來度量每個新格局的前景:從新格局TR(Csub )∪{c←ts}出發(fā)，使用最佳分配策略依次對C-(Csub∪{c})中課元進(jìn)行排課。若最后能達(dá)到目標(biāo)格局(可行解)，該可行解的不滿意度即為h(c，ts，α);若最終到達(dá)的是一死格局，則h(c，ts，α)=W0 × FailSet，其中FailSet是該死格局中未能安排的課元集。W0是比任何可行解的不滿意度都大的一個數(shù)。其搜索過程如圖3所示。

2.3 學(xué)習(xí)策略應(yīng)用

根據(jù)前景探測策略，若得到一個可行解TR(C)，則可以計算每個課元在這張課表中的不滿意度f(c，TR(C))，然后挑選出最不滿意的課元;若不能得到一個可行解，而是到達(dá)一個死格局，則認(rèn)為其中未能安排的課元是最不滿意的課元.對最不滿意的課元增加其優(yōu)先權(quán)值，然后再應(yīng)用前景探測策略進(jìn)行下一輪排課。

2.4 eHTA算法描述

根據(jù)上述兩個策略，用流程圖4描述eHTA算法。

3 總結(jié)

本文以人工智能學(xué)中的啟發(fā)式搜索理論為基礎(chǔ)，設(shè)計出能夠應(yīng)用在實(shí)際排課系統(tǒng)中的eHTA算法。該算法運(yùn)用分層規(guī)劃思想，提出靠邊策略、前景策略和學(xué)習(xí)策略。實(shí)驗(yàn)證明，排課中應(yīng)用eHTA算法大大減少了人工干預(yù)的次數(shù)，提高了排課效率。

參考文獻(xiàn):

[1] 胡小兵，魯宏偉.基于模糊專家系統(tǒng)的排課系統(tǒng)關(guān)鍵技術(shù)研究[J].電力學(xué)院學(xué)報:自然科學(xué)版，2006，16(4).

[2] 吳金榮.求解排課問題的分支定界算法[D].中國科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院，2002.

[3] 董艷云，錢曉群，張宇舒.基于課元組相關(guān)運(yùn)算的高校排課算法[J].西南交通大學(xué)學(xué)報，1998，33(6).