人工智能技術在課表生成中的應用

人工智能技術在課表生成中的應用

0湖南東南角的智能排課專家系統(tǒng)近年來，隨著相關技術的深入，人工智能技術的應用研究取得了很大進展。通用計算機不斷刷新的高速度和大容量為人工智能核心技術(如推理、回溯)提供了良好的應用基礎,許多基于人工智能基礎理論的應用算法取得了很好的效果。筆者參與設計的這個智能排課專家系統(tǒng),是針對現有排課軟件在約束條件增多,輸出課表量增大的情況下處理速度非常慢的現狀而開發(fā)的。通過測試幾個商品軟件,根據湖南文理學院現有的實際教學任務、教學資源的要求,其生成正式課表的時間多則30分鐘以上,少則10多分鐘。若增加特殊的限制條件,甚至沒有輸出結果。綜合應用了人工智能的相關理論和最新的處理技術,在快速、準確制定教學課表問題上,取得了預期的效果,本課題得到了湖南省教育廳高校教改項目經費的資助。1狀態(tài)空間搜索制約排課系統(tǒng)效率的瓶頸問題是發(fā)現排課沖突點,以及處理排課沖突。相對來說發(fā)現排課沖突點的問題其難度要低一些,而如何處理排課沖突是排課處理系統(tǒng)的核心。舉例說明:假定有100張待排課表,經初始化處理后生成的課表方案產生了20%的沖突,產生沖突的原因一般有以下幾種:⑴某教師在同一時間出現在兩個甚至幾個不同的授課點;⑵某教室(或實驗室)在同一時間安排了兩個(或幾個)不同的班級或不同的課程使用;⑶某一門課程在同一時間安排同一個教學班在不同地點上課;⑷某個教學班在同一時間被安排在不同的教學場所上不同的課程?？梢园颜n表系統(tǒng)看作是一個狀態(tài)空間,處理排課沖突的問題,就是要對給定狀態(tài)空間通過搜索算法給出一個解空間。而狀態(tài)空間搜索的關鍵是解決組合爆炸的問題。同理,處理排課沖突問題的難點,也是解決在處理沖突過程中的組合爆炸問題。對上例,在初始化處理時發(fā)現了20%的沖突,如果盲目地解決沖突,就會產生由更正一個沖突而引發(fā)25%、30%……或更多的新沖突出現,實可謂牽一發(fā)動全身。文中簡單介紹了所設計的這個智能排課專家系統(tǒng)的框架,以及處理沖突的A*算法。2課表vij傳統(tǒng)的排課方法是將每周教學時間離散成l5個教學單位點A1,A2,…,A15,然后將課程也對應地離散化,再憑經驗將離散的課程點放入到各個教學時間點上。一般按下列方式處理:取一課程→找一教學點放入→優(yōu)化、校驗→回寫取一課程→找一教學點放入→優(yōu)化、校驗→回寫上述處理模式僅適應于每班有固定教室、教師資源充足(假定每個教師周學時≤4學時)、不考慮教學資源共享以及有多種排課限制條件的情況。當前的現狀是:隨著高校新生的擴招力度加大,各高校都面臨著教學資源緊張的問題。每個班擁有一個固定教室的模式已不存在,甚至原來一個系專用的教學樓和實驗設備也要考慮參加全校的教學資源統(tǒng)一調配。同時還要考慮分、合班上課;教師特殊要求;特殊課程特殊處理等情況,比如非體育專業(yè)的學生一般不安排一、二節(jié)課進行體育訓練,以免大運動量影響三、四節(jié)課的學習精力。該智能排課系統(tǒng)由以下幾個基本模塊組成,依據排課過程實施的先后順序描述如下:⑴procedureTzpneoform1.firststep-initialize(sender:tobject)//系統(tǒng)數據初始化,形成本學期排課數據的屬性、條件及信息編碼等二維數據視圖(見圖1)。排課數據屬性是指說明該課程的總學時數、是否上大班課、是理論教學課還是實踐教學課。排課數據的條件是指該門課程有無時間安排的限制,如必須在第幾周結束,不能安排在某個時間段等。⑵procedureTzpneoform1.secondstep-orientation(sender:tobject)//課程定位、形成課程編號和基本的教學信息庫。這一部分的信息(見圖2)來自教學計劃,根據各年級、各專業(yè)、各門課程以及學生人數等信息擬定出最基本的課表資源。⑶procedureTzpneoform1.thirstep-predeject(sender:tobject)//依據產生式規(guī)則初步排出各教學班的課程表。這一階段的設計宗旨是粗線條、高速度。其主要工作是依據procedureTzpneoform1.firststep-initialize(sender:tobject)和procedureTzpneoform1.secondstep-orientation(sender:tobject)兩個信息源的數據,盡快地生成各個教學班的初始課表。在本階段不考慮各教學班的課表產生沖突的情況,僅考慮按照教學計劃的要求以及上課人數的約束,形成各教學班班級本期的課程、時間、教室、地點的初始化課表定位。各教學班初始化的課表生成由產生式規(guī)則算法實現,產生式規(guī)則算法包含以下幾個主要內容:R1定義一個二維表格A={D1,D2},D1,D2是兩個有界定義域,表示每周的教學天數和每天教學單位數,一般情況下5≥D1≥1,3≥D2≥1(或4≥D2≥1)。R2設V={v1,v2,…,vn},其中vi={vi1,vi2,…,vin},其中vij表示vi的第j個排課數據分量,vij具有兩個分量vij.weekday,vij.courepuantity,分別描述課程上課時間和課程課時量。R3從相關二維空間中取適當單元ui放入,每一班級單元可以描述為{u1,u2,…,un},其中ui對應vij,那么vij.Courepuantity=[lo,hi],lo表示課程的起始周次,hi表示課程的終止周次。R4將任意V={v1,v2,…,vn}落入一個單元u={u1,u2,…,un},如果對ui中元素滿足minnun<=maxnum,則一次放入成功,否則ξ-vi形成新的vi,再將vi選擇一空單元繼續(xù)放入。R5將每一ξi(1≤i≤k)從{u1,u2,…,un}中選一容量最大空單元一次性放入后{u1,u2,…,uj-ξi,…,un},經過多次這樣的處理,形成{Pt1,Pt2,…,Ptm},這樣反復處理保證每次課時數最大的課程總能放入到容納課時數最大的空單元Ptn中,這一步驟又由以下兩個操作實現:R5.1將單元集u={u1,u2,…,un}分解成{Qs1,Qs2,…,Qsn}和{Pt1,Pt2,…,Ptm},其中Qsi已排數據單元集合Pti空單元容量,且滿足Qsiu,Ptiu,Qsi∩Pti=ф,對任意取出參數ξi(i<k),利用Huffman規(guī)則,每次取出兩個最小的值進行結合,然后在對應空單元容量序列Ptj中找一個對應位置放下。R5.2若ξi(i<k)無論利用Huffman規(guī)則怎樣進行取值均無法放入,則報告錯誤,否則反復執(zhí)行R5.1,直到形成一合理序列為止。至此,形成了各教學班的初始化課表。⑷procedureTzpneoform1.forthstep-transion(sender:tobject)//應用關聯規(guī)則中FP-tree算法思想定位課表混排庫中出現的沖突。由于教學資源共享,一個教學班不能固定擁有一個教室;而有些熱門課程因教學任務大、教師人數少以及特殊課程對時間的特殊要求等原因,使得在不考慮約束條件前提下生成的初始課表存在各種沖突是必然的。采用了數據挖掘技術中發(fā)現頻繁項目集的FP-tree算法思想來發(fā)現課表混排庫中出現的沖突。FP-tree算法的初衷是生成發(fā)現關聯規(guī)則所需要的頻繁項目集,本系統(tǒng)中用FP-tree算法思想來定位混排數據庫中的沖突元素,算法運行結束將對沖突元素按其沖突計數值降序排列形成一棵樹結構,為隨后進行的沖突處理提供必要的信息。⑸procedureTzpneoform1.fifthstep-trans(sender:tobject)//應用啟發(fā)式搜索的A*算法處理沖突。處理沖突是本系統(tǒng)性能的重點設計任務,分析當前一些不能適應實際需求的排課軟件,其主要弊病是響應速度慢。筆者做過這樣的實驗,以簡單的回溯處理方法來處理50份課表所產生的沖突,再設計一個生成課表的臨時數據庫進行監(jiān)測,可以看到這樣一種現象:采用簡單的“沖突-回溯”處理方法,在斷斷續(xù)續(xù)給出第6份課表后,就長時間地運行在“發(fā)現沖突←→回溯處理”的周而復始循環(huán)過程。本系統(tǒng)中應用了人工智能技術中的啟發(fā)式搜索策略來處理沖突問題。在啟發(fā)式搜索策略中,主要參考了A*算法。為適應本系統(tǒng)的情況,所實施的A*算法在典型算法的基礎上作了必要的修改?！駥嵤〢*算法的可行性分析和效率分析A*算法應用在對狀態(tài)空間的搜索,實現由給定狀態(tài)到目標狀態(tài)的轉換。在實行轉換的過程中要滿足種種轉換的約束條件,還要在由狀態(tài)i進入到狀態(tài)i+1的轉換過程中排除若干可能出現的、但不是目標狀態(tài)必由路徑的干擾(即組合爆炸問題),而由算法引導找到一條最佳的狀態(tài)轉換路徑。將由過程procedureTzpneoform1.thirstep-predeject(sender:tobject)生成的初始化課表看成是一個給定的狀態(tài)空間,將符合教學任務要求、無沖突的各教學班級課表看作目標狀態(tài)。由于初始狀態(tài)到目標狀態(tài)有路徑存在,所以實施A*算法處理沖突是可行的。實施A*算法的效率分析參見圖3。●改進的A*算法定義1g(n)是狀態(tài)空間的轉換層次函數,g(n)是對g*(n)的估價值且g(n)>0;g(n)≥g*(n);h(n)是狀態(tài)空間轉換的啟發(fā)式函數。且h(n)是h*(n)的下界。定義2A*算法的估價函數f*(n)=g*(n)+h*(n)。算法5.1處理課表混排的沖突問題輸入:規(guī)模為N的初始課表數組L(1:N),FP-tree樹中沖突計數值最高的節(jié)點so。輸出:沒有沖突的N個班正式課表。改進的A*算法描述如下:ProcedureA*-search(s)①取FP-tree樹中沖突計數值最高的節(jié)點so放入open表中,計算f*(so)=g*(so)+h*(so),刪除FP-tree樹結構中的so節(jié)點;②如果open表為空,則問題無解,轉①取FP-tree的當前節(jié)點重新計算;③把open表的第一個節(jié)點取出來,放入close表,并記該節(jié)點為n;④考查由節(jié)點n引發(fā)的狀態(tài)轉換空間是否為目標狀態(tài),若是,找到解,成功退出;⑤若節(jié)點n不可擴展,則轉第②步;⑥擴展節(jié)點n,生成子節(jié)點ni(i=1,2,…),計算每一子節(jié)點的估價值f*(ni)(i=1,2,…);⑦封閉f*(ni)中所有>minf*(ni)的節(jié)點,將最優(yōu)的估價值minf*(ni)節(jié)點寫入open表中。⑧轉②。為找出系統(tǒng)的運行速度,我們還做了如下兩個處理:a.為減小f*(n)的計算工作量,沒有設置h(n)≤h*(n)的約束條件。b.系統(tǒng)提供的解狀態(tài)是以滿足約束條件的目標狀態(tài)為設計目標,并不對若干個可能的解狀態(tài)進行擇優(yōu)處理。⑹proc