基于二叉知識樹推理的可擴展智能排課系統(tǒng)

王運成，周春華，陳楚湘，吳善明，陳 冰

戰(zhàn)略支援部隊信息工程大學 信息作戰(zhàn)指揮系，鄭州450001

隨著我國高等教育的快速發(fā)展，高等院校規(guī)?？焖贁U大，教師、教室、課程數(shù)量和需求大量增多，課程排列組合方案也成幾何數(shù)級增加。以鄭州信息科技學院為例，假如每天上課時段dno∈{1,2,…,5}，每周上課天數(shù)d∈{1,2,…,5}，每學期上課周數(shù)w∈{1,2,…,20}，教室數(shù)量r∈{1,2,…,150}，總學時數(shù)為N=12 000，則排課的規(guī)模為：

對于如此規(guī)模的問題，使得大學排課變成一項具有現(xiàn)實需求的復雜的系統(tǒng)工程。早在1976年，Even等人已經(jīng)證明了此類問題本質(zhì)上就是一個NP完全問題[1]。

當前，研究排課問題的算法主要有模擬人工手動排課算法、貪心算法、遺傳算法、退火算法、回溯算法、蟻群算法和禁忌搜索求解排課算法等。其中，模擬人工手動排課算法更人性化，排課滿意度較高，適合小規(guī)模教學單位排課；柴婷婷等研究了貪心排課算法[2]，算法運行效率高、空間復雜度低，然而其求局部最優(yōu)解的前提是要找到正確的貪心思路和計算斷點，貪心思路難找且斷點選擇存在缺陷，這給貪心算法在排課問題的使用帶來了很大的困難；劉斌等提出了一種基于屬性重要性的貪心算法[3]，改進算法解決了在無法判斷斷點的情況下，如何有效地區(qū)分斷點，求得最小的斷點集，但算法的復雜度大大增加，因此，對問題的求解提出了更高的要求；徐錦國基于遺傳算法提出了排課算法[4]，它是一種全局優(yōu)化算法，可進行并行分布處理，具有較強的魯棒性和良好的穩(wěn)定性，然而排課問題涉及的要素多，對染色體的編碼以及選擇、交叉、變異等復雜操作使算法的計算量很大，算法的運行需要許多參數(shù)，如網(wǎng)絡拓撲結構、交叉率、變異率及權值和閾值的初始化等，這些參數(shù)的設置對經(jīng)驗提出了很高的要求；黃干平等研究了模擬退火算法解課表問題[5]，退火算法是一種新的隨機搜索方法，問題描述簡單、魯棒性強、運用廣泛、并行運行和受初始條件制約相對少，適合于解決大規(guī)模組合優(yōu)化問題，但模擬退火算法也有其自身的缺點，收斂速度慢、算法性能對初始參數(shù)敏感、難以避免搜索過程陷入局部極小值，且解空間的搜索能力和范圍難以達到理想解；倫冠民等提出了回溯算法在排課系統(tǒng)中的應用[6]，回溯算法是遞歸算法的一種特殊形式，將一個復雜問題分解為多個子問題，思路清晰，方法簡單，但面對大規(guī)模排課需求時，尤其是面對教務、教師眾多的排課需求，且這些需求隨時間變化而又動態(tài)地發(fā)生變化時，該算法不易實現(xiàn)，且靈活性、可擴展性差。

綜上所述，目前國內(nèi)外基于排課系統(tǒng)的研究都不能很好地適應這種復雜的、動態(tài)的、大規(guī)模的智能排課任務。針對大規(guī)模智能排課的現(xiàn)實需求，本文設計并實現(xiàn)了基于二叉知識樹推理的可擴展智能排課系統(tǒng)。原型系統(tǒng)能夠區(qū)分排課需求中硬約束需求和軟約束需求，并分別引入確定性推理和不確定性推理加以解決[7-8]，尤其是不確定推理的引入，較好地解決了排課軟約束造成的模糊性和不確定性問題；針對排課系統(tǒng)的靈活性和可擴展性問題，原型系統(tǒng)設計并實現(xiàn)了二叉知識樹推理結構和可擴展的規(guī)則庫存儲結構[9]。實踐證明了該智能排課系統(tǒng)的科學性、高效性、靈活性和可擴展性。

1 問題定義及模型

1.1 問題定義

定義1課程情況

以course表示課程集合[10]，則有：

其中，code表示課程代號；characteristics∈{綜合素質(zhì)課、選修課、公共基礎必修課、專業(yè)必修課、專業(yè)選修課}；time表示課程學時數(shù)；weight表示課程權重，weight∈{0,1}；mark表示課程學分。

根據(jù)普通高校實際情況，將課程分為A、B、C三類。A類為綜合素質(zhì)課和選修課程，B類為公共基礎必修課程，C類為專業(yè)課程，課程分類情況如表1所示。

定義2時間情況

以TIME表示時間集合[10]，則有：

表1 課程情況表

其中，w表示學期周次；d表示周一至周五，d∈{1,5}；no表示每天安排5個時間段，no∈{1,5}；weight表示時間段的權重，weight∈{0,1}。排課時間表如表2所示。

表2 排課時間表

定義3專業(yè)情況

以SPECIALITY表示專業(yè)集合[11]，則有：

其中，scode表示專業(yè)代號，sname表示專業(yè)名稱，sgrade表示專業(yè)年級，snum表示專業(yè)人數(shù)。

定義4教室情況

以CLASSROOM表示教室集合[11]，則有：

其中，rcode表示教室編號；rcharacteristic表示教室性質(zhì)，rcharacteristic∈{語音室、多媒體教室、普通教室}；rposition表示教室位置；rcapacity表示教室容量。

定義5教師情況

以TEACHER表示教師集合，則有：

其中，tcode表示教師編號；course表示課程；time表示授課時間；content表示教師對排課的滿意度，content∈{0,1}。

定義6知識推理樹

產(chǎn)生式規(guī)則知識表示為：ifAthenB，即如果條件A成立則結論B成立。產(chǎn)生式規(guī)則知識特點：具有相同的條件可以得出不同的結論，相同的結論可以由不同的條件得到，一條規(guī)則的結論可以是另一條規(guī)則的條件，條件之間可以AND（與）和OR（或）連接。各規(guī)則的條件和結論可構成一棵以根節(jié)點為目標的知識推理樹[12]。

定義7可信度（Credible Factor）模型[13]

在推理的過程中由于知識的不確定性（包括條件的不確定性和規(guī)則的不確定性）引起結論不確定性的傳播，導致目標的不確定性。結論可信度的計算模型分為AND（與）和OR（或）兩種情況[13]。

（1）當進行AND（與）連接時，規(guī)則形式：

結論可信度的計算模型為：

（2）進行OR（或）連接時，規(guī)則形式：

轉化成等價的兩條規(guī)則，即：

兩條規(guī)則，則結論H的可信度CF(R)計算分別有：

合并為：

其中，CF(H)表示結論的可信度值，CF(R)表示推理的不確定性，CF(EN)表示事實的不確定性，可信度取值范圍：0≤CF≤1。

定義8硬約束[14]

在排課過程中必須遵循的原則，它規(guī)避了相關的各個要素在時間和空間上可能產(chǎn)生的沖突，是算法進行排課時必須滿足的約束條件。比如“同一教師在同一時間段只能安排一門課程”“同一專業(yè)班級在同一時間只能安排一門課程”“同一教室在同一時間只能安排一門課程”“教室容量應不小于合并專業(yè)班級人數(shù)，且教室類型符合所授課程要求”等。

定義9軟約束[14]

在排課過程中應盡量滿足的約束條件，它并不是排課結果可行與否的決定因素，而是作為權衡其優(yōu)劣的標準。比如教師要求“某課程盡量不要排在某個時間段或某個教室”“難度較大的兩門課程盡量不要連排”等。

1.2 模型構建

硬約束1同一教師在同一時間段只能安排一門課程；對于任意教師，?teacher∈TEACHER則滿足[15]：

其中，tcode表示教師編號，coursecode表示編號為code的課程，N表示課程總數(shù)量，timew,d,no表示特定的時間段，且：

硬約束2同一專業(yè)班級在同一時間只能安排一門課程；對于任意班級，?specialityscode∈SPECIALITY則滿足[15]：

其中，specialityscode表示編號為scode的專業(yè)，coursecode表示編號為code的課程，timew,d,no表示特定的時間段，N表示課程總數(shù)量，且：

硬約束3同一教室在同一時間段只能安排一門課程；對于任意教室，?classroom∈CLASSROOM，則滿足[16-17]：

其中，classroomrcode表示編號為rcode的教室，coursecode表示編號為code的課程，timew,d,no表示特定的時間段，N表示課程總數(shù)量，且：

硬約束4教室容量應不小于合并專業(yè)班級人數(shù)，且教室類型符合所授課程要求；對于任意教室，?classroom∈CLASSROOM，則滿足：

其中，specialityscode,snum表示scode專業(yè)班的人數(shù)為snum，h=1,2,…,H，H表示專業(yè)班級數(shù)量。classroomrcode,rcapacity表示編號為rcode教室的容量。

排課軟約束：軟約束體現(xiàn)在教務管理者或教師對排課附加的一些主觀要求，雖然軟約束不滿足時仍可進行排課，但滿足排課軟約束的多少是衡量算法優(yōu)劣的標準[18]。

其中，softrequestcf表示某排課軟約束需求的可信度值，表示多排課軟約束經(jīng)可信度模型計算所得最終可信度值；w表示軟約束數(shù)量，θ表示閾值，θ∈{0,1}，且：

目標函數(shù)：根據(jù)上述條件分析，目標函數(shù)值由硬約束的目標值和軟約束的目標值構成，可建立目標函數(shù)的最大化：

2 系統(tǒng)模型設計

2.1 產(chǎn)生式規(guī)則及知識樹生成

根據(jù)以上分析，排課沖突可分為兩類：硬約束沖突和軟約束沖突。排課硬約束沖突要求教師、教室、專業(yè)班與課程之間的沖突必須解決，排課軟約束沖突對教務管理者、教師提出的主觀要求之間的沖突可以部分解決。系統(tǒng)設計基于產(chǎn)生式規(guī)則構建知識樹進行推理[19]。排課問題約束分析如表3所示。

表3 排課問題約束

軟約束具有可擴展性，教務管理者和教師可根據(jù)自身實際情況提出各自的排課要求，在求解的過程中也對應各自的知識樹進行推理，軟約束分析如表4所示。

表4 排課問題軟約束

將排課約束轉化為產(chǎn)生式規(guī)則，得如下規(guī)則：

規(guī)則1A∧B→G。

規(guī)則2C∧D→A。

規(guī)則3E∧F∧H→B。

規(guī)則4F1∧F2∧…∧Fi∧…∧Fn→F。

將總目標作為根節(jié)點，按照規(guī)則的前提和結論展開成一棵樹的形式，知識樹如圖1所示。

圖1 知識樹

判斷一門課程排課是否成功，可按照前序或后序遍歷知識樹，該過程實質(zhì)是進行確定性推理與不確定性推理相結合的混合推理過程，當G為true時表示排課成功，為false表示排課失敗。

2.2 改進生成二叉知識樹

基于知識樹設計推理機節(jié)點時結構固定，也就是說推理機前件的數(shù)量是受限的，而排課需求復雜多變，尤其是軟約束需求，不同學期教務管理者和教師主觀排課需求不定，它要求設計的推理機對前件的數(shù)量具有可擴展性。這造成了排課需求的靈活、多樣與推理機結構設計相對固定的矛盾。為克服推理機結構設計的缺點，本文將知識樹改進為二叉知識樹[19]，如圖2所示。

圖2 二叉知識樹

相較于原來的知識樹，這種結構的可擴展性更好，且易于計算機實現(xiàn)。該二叉知識樹的節(jié)點設計如下：

其中，type對應教師編號；Lchild存放左節(jié)點，若沒有則為空；Rchlid存放右節(jié)點，若沒有則為空；data存放該節(jié)點下子節(jié)點的與或屬性，若沒有則為空；value存放該節(jié)點的事實屬性值或可信度值，value∈{0,1}。

2.3 知識庫存儲結構設計

知識庫的存儲結構有多種，典型的有文件結構和數(shù)組結構。文件結構是將知識庫保存為若干文件的集合，每個文件中只有一種類型的記錄，不同文件保存不同的關系，這種方法最容易實現(xiàn)，目錄方式管理簡單明了，可以直接打開查看，缺點是管理難度大、搜索速度慢、靈活性和可擴展性差；數(shù)組結構是將前件存放在二維數(shù)組中，后件存放在一維數(shù)組中，這種方法直觀易理解，搜索速度快且靈活性好，缺點是排課的軟約束數(shù)量大于二維數(shù)組列數(shù)時無法處理，可擴展性差。這兩種方法都不適合用來存儲排課問題所需知識，與之相比，二維表結構存儲知識顯得更加合適。二維表結構存儲知識主要有以下優(yōu)點：可擴展性強，可以隨時添加規(guī)則知識而不必改變原有結構，例如教師的排課要求發(fā)生變化，可以直接在二維表中增加規(guī)則；易于存儲可信度值，便于進行不確定推理；簡單實用，易于計算機的搜索，便于維護[20]。知識庫存儲結構如圖3所示。

圖3 知識庫存儲結構

3 排課算法設計

3.1 算法設計思路

算法設計總體思路：對于綜合素質(zhì)課(Ab)、選修課(Ac)涉及不同專業(yè)、年級的學生，安排固定時間授課比較合理；公共基礎必修課(Ba)涉及面廣、學時多，涉及合并專業(yè)授課，這些課程所占用的資源相對也比較集中，應當適當?shù)赜枰詢?yōu)先處理；專業(yè)必修課(Ca)和專業(yè)選修課(Cb)由各專業(yè)教師講授，通常固定教室。通過分析，A類課程中Ab、Ac分別按照首字母排序為courseC1,courseC2,…,courseCi,…,courseCn，n為課程數(shù)量，所有教室按照其編號從小到大依次排序為classroom1,classroom2,…,classroomx，x為教室數(shù)量；B、C兩類課程的排課算法相同，但需要注意在排課時應首先排B類課程，待B類課程全部排完后再進行C類課程的編排，課程按照權重由大到小排序為courseC1,courseC2,…,courseCi,…,courseCn，n為課程數(shù)量，排課時間表中的時間段按權重由大到小排序為Um1,Um2,…,Umi,…,Umx，x為每周的時間數(shù)量。

3.2 排課算法步驟

步驟1初始化數(shù)據(jù)。

（1）初始化課程信息：包括課程名稱、課程代碼、課程學時、課程性質(zhì)、教師授課方式以及課程的權重；

（2）初始化教師信息：包括教師姓名、教師所教授課程名稱、教師對該課程所提出的需求；

（3）初始化時間信息：包括每門課程上課周數(shù)、每周上課天數(shù)、節(jié)數(shù)、節(jié)次及各時間段權重；

（4）初始化教室信息：包括教室編號、教室容量、教學樓擁有該容量教室的數(shù)量；

（5）初始化學生信息：包括學生專業(yè)名稱、專業(yè)代碼、該專業(yè)人數(shù)。

步驟2預處理。

（1）A類課程按優(yōu)先級高低排序；

（2）設置A類課程授課時間段；

（3）B、C類課程按優(yōu)先級由高到低排序；

（4）教室容量由小到大排序。

步驟3A類課程固定時間排課。

4 仿真實驗

4.1 仿真數(shù)據(jù)

仿真數(shù)據(jù)來自鄭州信息科技學院2014—2018學年的課程表，包括教師的實際排課需求，仿真數(shù)據(jù)如表5所示。

表5 排課資源表

結合學校教務、教師、學生和教學效果反饋，時間段權重的實驗數(shù)據(jù)如表6。

表6 排課時間權重表

根據(jù)課程對資源的占有情況，確定不同性質(zhì)課程的權重如表7所示。

表7 課程權重表

4.2 實驗分析

（1）最優(yōu)化參數(shù)

由式（13）可知，在排課資源、排課時間權重和課程權重確定的情況下，排課系統(tǒng)的最優(yōu)解與閾值θ和軟約束權重α有著密切關系。其中，θ值的大小與軟約束的松緊有關，θ值越小，教師的排課要求越容易得到滿足，但排課沖突的概率增大，在整個排課過程中硬約束必須滿足，同時兼顧軟約束。

通過Matlab仿真，最優(yōu)參數(shù)進化如圖4所示，當θ=0.5，α=0.24時，排課算法獲得最優(yōu)解。

圖4 不同參數(shù)值最優(yōu)化分析

（2）靈敏度分析

調(diào)整不同類型課程的權重，通過Matlab仿真，分析θ、α的收斂性及最優(yōu)性如表8所示。

表8 課程權重對收斂性和最優(yōu)性影響

Ca類課程相對數(shù)量少，又固定教室排課，權重提高對整體排課影響小，θ、α仍趨于收斂，只是因占用了比它更優(yōu)的時段排課，已非最優(yōu)解。其他類課程權重的調(diào)整導致θ、α不收斂，排課失敗。

（3）可擴展性分析

回溯算法與本文算法本質(zhì)上也是基于樹的推理，從知識庫存儲結構、推理機節(jié)點結構和軟約束可擴展比較兩種算法的優(yōu)缺點如表9所示。

表9 算法可擴展性比較

（4）其他性能分析

通過與貪心算法、遺傳算法、退火算法和本文算法進行對比實驗仿真，得出各算法在沖突率、成功率、運行時間和可擴展軟約束等方面的指標性能差異。本文算法在課程權重一定的情況下進行20次仿真實驗，平均性能值如表10所示。

表10 幾種算法的指標性能比較

由表10中的數(shù)據(jù)可知，基于二叉知識樹推理的可擴展智能排課算法排課的成功率和運行時間明顯優(yōu)于傳統(tǒng)的貪心算法、遺傳算法和退火算法，該算法通過設計可擴展軟約束較好地解決了常規(guī)排課系統(tǒng)在面對需求復雜多變時所表現(xiàn)出的軟約束擴展性不足和結構不夠靈活的問題。

5 結語

本文分析了目前常規(guī)排課算法存在的問題，利用不確定性推理技術解決排課中的軟約束問題，通過閾值和軟約束可信度的設定平衡管理者和教師之間的排課要求，設計并實現(xiàn)了一種適用于大規(guī)模排課需求的可擴展智能排課系統(tǒng)原型，創(chuàng)造性地利用二叉知識樹的生成解決了系統(tǒng)的可擴展性問題，但可能會增加樹的深度，而影響二叉知識樹深度變化的主要因素是軟約束的數(shù)目，在推理的過程中，本文假定每名教師的主觀需求有限，則其對應的二叉知識推理樹深度增加有限，幾乎不影響系統(tǒng)的求解速度。原型系統(tǒng)算法設計的前提是固定時間排A類課程，固定教室排B、C類課程，從而使算法的復雜度降低，這必然影響算法的通用性。如何平衡算法的通用性與復雜性是當前排課算法亟待解決的一個問題，研究和探索各大學的排課需求，構建各類特定條件下的分類器模型，使用戶可根據(jù)不同需求選取相應的分類器模型，以滿足既可保證算法的通用性，又能降低算法的復雜度是下一步的研究方向。目前，該智能排課原型系統(tǒng)已經(jīng)應用于鄭州信息科技學院的現(xiàn)實教學課程編排。實踐證明，該排課系統(tǒng)很好地解決了動態(tài)的大規(guī)模排課需求問題，對于高校提高排課質(zhì)量和排課效率有較好的實用價值。