高校智能排課系統問題研究及算法改進策略

張蕓蕓

摘? ?要：排課是高校教學管理的重要工作，其本質是在學校現有的軟、硬件環境下，合理地安排教師、學生、課程、教室等，使教學規劃有計劃、有秩序地進行。本文在對高校的學生、教師和教務管理員進行認真的調研、訪談的基礎上，通過匯總分析得出：為更好地提高教室利用效率、確保教學有序進行，通過某種智能策略算法來建立智能排課系統尤為重要。

關鍵詞：遺傳算法? 智能排課系統? 群體策略

排課是高校教學管理的重要工作，其本質是在學校現有的軟、硬件環境下，合理地安排教師、學生、課程、教室等，使學校的教學規劃有計劃、有秩序地進行。隨著高校學生人數的增多，院系開設課程的規模大幅上升，排課已經成為一項極其復雜的工作，現在使用人工排課已經無法滿足學校教學管理的需求，因此利用計算機來實現自動化排課，已經成為計算機應用學科的一項重要任務。

1? 高校排課工作現狀研究

排課任務實質上是根據學校的教學環境，包括教師數量、教學地點、教室數量和教學時間的限制下，能夠促使整個學校的所有課程正常有序地開展教學工作。高校排課問題是一個非常復雜的組合規劃問題，需要滿足各種約束條件，以保證在上課過程中，教師、學生和教室不會產生任何的沖突，也即不同級兩個或者多個班級在同一時間被安排在同一個教室，或者是同一個教師在同一時間被安排上了多門課程，導致教學無法正常進行。前期，國內的部分院校在進行排課時，使用人工排課的方法，人工排課工作的主要方法是實施擺牌，就是將印有課程名字的小紙牌在畫有空的課程表的版面上進行初排、調整，一邊依據排課經驗進行設置，一邊觀察每門課程所在的位置是否合理，以便能夠形成一個有效的正常課程表。由于人工排課沒有任何的理論指導，也沒有進行數學建模，主要依靠排課者的經驗，具有很大的弊端，這種方法適合于規模較小、課程少的學校，但是隨著高等院校規模的擴大，對上萬名學生需要在一年中完成上萬節課程的設置，如果僅僅依靠人工進行排課，那么將會花費大量的人力、物力和財力，工作量非常的大，并且無法排除易于調整的課程表。

2? 高校智能排課系統傳統算法的局限性

隨著計算機技術的迅速發展，其擁有更強更快的數據處理能力，并且擁有高速運算的特點，通過對排課實施建模，能夠在滿足時間、教師、教室、課程、學生等約束條件的同時，通過排課算法進行求解，能夠有效的實現自動化排課，提高排課的正確性和排課效率，節省人力、物力和財力，使教務管理人員從繁瑣、復雜的排課任務中解脫出來，推動了排課工作的管理與發展，也間接地推動了教學管理的信息化，具有非常重要的意義。

在排課過程中，系統涉及的約束條件非常多，主要包括教師、課程、教室、班級等，排課表實施編排過程中，要對上述主要約束條件進行合理的規劃，不能夠產生任何的沖突，比如同一個教師在同一時間不能被安排多門課程，同一個班級在同一時間不能有兩個教師上課，并且滿足用戶需求資源，滿足教師的要求和限制。

目前，智能排課系統在進行課程表排設過程中，通常采用的算法有蟻群算法、模擬退火算法、回溯法、基于規則的推理算法、遺傳算法等，隨著試題的增多，試題難度等級的逐漸加大，使用現有的算法進行智能組卷，存在陷入局部最優、組卷成功幾率較低的問題。雖然許多專家和學者為了解決排課問題，已經提出了很多算法，比如分組優化、分支定界、專家系統等。但是，上述算法總是存在以下問題：

一是專家系統可以依據排課的經驗知識，組織排課的規則，但是排課過程約束條件較多，每個學校的實際情況各不相同，經驗知識較難獲取，排課結果也不好。

二是排課表的優劣判定標準較少，針對一個問題求解，無法從多個角度實施優化。

3? 傳統遺傳算法在進行智能排課時遇到的問題

排課問題的約束條件分為軟約束、硬約束兩種類別，學生、教師、教室等硬件資源是硬約束，這些條件在排課過程中必須滿足，該約束度量一個排課算法的可行性;軟約束既可以滿足也可以不用滿足，其度量一個排課算法的優劣。

遺傳算法能夠有效的模擬達爾文的自然淘汰和遺傳變異選擇的生物進化過程，通過搜索最優的模擬進化算法。該算法可以針對一串描述字符的位串進行操作，不同位串在實際的應用環境中代表不同的問題。遺傳算法可以從若干個初始的種群開始搜索，根據當前的種群成員，模仿生物的遺傳進化過程，選擇基因優良的下一代作為進化的目標。遺傳算法的主要目的是針對相關的問題進行建模分析，尋求相關問題的最優解。也就是根據問題的背景和性質，構建一個合適的適應度函數，迭代執行，然后在求解空間中選擇較優的種群進行評估、遺傳變換、變異和選擇等交叉選擇操作，將滿足目標函數的個體選為最優解。

目前，傳統的遺傳算法已經在很多領域得到了廣泛的應用，比如自動組卷過程中、基因序列預測過程中、數據庫連接優化過程中，均得到了良好的效果。但是傳統的遺傳算法在使用過程中，存在以下問題：

第一，傳統遺傳算法在排課應用過程中，由于排課軟硬約束條件較多，約束比較復雜，遺傳算法選擇優勢個體遺傳到下一代，遺傳算法在排課過程中，非常容易陷入到局部最優化，無法求得全局最優解。

第二，排課過程中，排課存在硬件約束（教師、教室）和軟件約束（時間），因此，如果同時考慮這兩種約束模式，遺傳算法則成為一個多約束和多目標的組合優化問題，無法求解。

4? 基于群體策略的遺傳算法在高校排課系統中的應用

遺傳算法通過應用和改進，已經出現了許多改進后的遺傳算法，比如并行遺傳算法、網格遺傳算法等。為了尋求一個排課問題的最優解，作者通過對相關的遺傳算法進行對比研究，將隨機數理論其引入到遺傳算法中，通過實施自然的選擇、變異等發生機制，提高每一個個體的適應度，充分體現物競天擇、適者生存的基本思想和原理，并且提出了一種改進的遺傳算法——基于群體策略的遺傳算法，該策略能夠促進每一代的平均適應度逐代提高，直到尋求到最優解，可以較好地解決傳統算法尋求最優解時容易產生的收斂速度慢、陷入局部最優等問題，盡可能地滿足“實用、合理、有特色”的需求，形成最優化的排課方案。

基于群體策略遺傳算法的基本操作流程包括以下6個步驟：

第一步：生成初始種群：隨機生成包含所有解空間的初始種群，種群中的每個解都使用一個個體表示;第二步：計算適應度函數：根據目標函數，計算種群中個體的適應度函數;第三步：執行選擇操作：根據適應度函數值和選擇操作方法，淘汰含有劣勢基因個體，選擇優勢個體，即逐步向最優解靠近;第四步：交叉操作：對種群中的個體實施交叉操作，產生新的個體;第五步：變異操作：對種群中的個體實施變異操作;第六步：判斷是否滿足終止條件或求得最優解。如果滿足終止條件或求得最優解，即可停止算法;否則，跳轉到第二步。

基于群體策略的遺傳算法使用概率策略設置選擇操作算子，促進適應度較高的個體遺傳到下一代，增加種群的平均適應度，該策略能夠逐代提高每一代的平均適應度，直到尋求到最優解，從而解決無法從多個約束條件實施優化的問題。實驗結果表明，基于群體策略的改進遺傳算法能夠有效地尋求滿足“實用、合理、有特色”的需求的排課方案，具有較好的效果。

參考文獻

[1] 郭彤.人工智能算法在排課系統中的研究與應用[J].天津職業院校聯合學報，2012，22（2）：14-18.

[2] 崇陽.遺傳算法在高職院校排課系統中的應用研究[J].電腦編程技巧與維護，2016（1）：23-24，30.

[3] 馬小姝，李海蕓.遺傳算法在高校排課系統中的應用研究[J].信息與電腦：理論版，2018（8）.