幾種智能排課算法的對比探討

黃嶺 秦春娣 陳偉

摘要：該文給出了排課系統避免沖突所需要遵循的條件和因素，對可實現于排課的幾種智能算法做了介紹和分析，并對智能算法以后的發展進行了探究，為今后的各種排課需求提供參考。

關鍵詞：排課;智能算法;分析對比

中圖分類號：TP312

文獻識別碼：

文章編號：1009-3044（2020）04-0159-02

收稿日期：2019-12-05

基金項目：江蘇省大學生實踐創新訓練計劃項目校級項目“機房排課系統的設計與實現"（項目編號：51800021644）

作者簡介：黃嶺（1979—），男，江蘇常州人，講師，碩士，研究方向為電子及計算機應用;秦春娣，女，工程師，本科;陳偉，男，?？粕?。

Comparison of several intelligent Course Scheduling Algorithms

HUANG Ling，QIN Chun-di，CHEN Wei

（Changzhou Vocational Institute of Textile and Garment，Changzhou 213164，China）

Abstract：This paper gives the conditions and factors that need to be followed to avoid conflict in course scheduling system，analyzes and compares several intelligent algorithms that can be used to solve course scheduling problems，and forecasts the development pros-pect of intelligent algorithm，so as to provide reference for future various courses scheduling needs.

Key words：course scheduling;intelligent algorithm;analysis and comparison

人類每一次的思考創新都離不開技術革新帶來的取代傳統手工操作，轉向高效人工智能處理的進步。一直困擾著學校教務的排課問題也隨著專業、班級、課程等必要條件的不斷擴展而顯得愈演愈烈。排課問題作為資源分配調度的一種典型問題，已經被證明是非確定性多項式（NP）完全問題。完成排課課程表這個過程的課程調度算法也是NP問題中較難的一類。近些年，許多研究人員將人工智能、神經網絡、模糊算法、進化算法等方面的研究成果不斷在控制盒優化、復雜線性系統模型.創建方面進行探索，并產生了一系列的智能排課算法，本文就常用的幾種算法做一個比較分析。

1 排課問題分析

排課問題需要解決的是根據具體教學需要滿足諸如節次、班級、教學地點、教師這一系列因素的組合，并且能夠很好地處理特殊需求，協調各因素之間的矛盾沖突，換言之就是要借助計算機技術權衡各種制約條件，最終達到課程安排合理化的結果[1]。

排課系統中的涉及的約束條件歸納起來主要有三種：基礎硬約束、硬約束和軟約束。

1）基礎硬約束：是指教師、班級和教學地點在節次上不可發生的沖突，包括“同一節次同一班級不能上兩門不同的課程”;“同一節次同一教師不能上兩門不同課程”，這類約束條件是所有排課模型都會涉及的，最基礎的要求，這個約束若無法

滿足，排課也就沒有意義了。

2）硬約束：是指排課時需要遵循的教學計劃規定的一些硬性要求或實際教學場地的條件限制的原則。如“課程按照最小兩節或六節進行”;“課程的總周數有要求”;“教學地點容納學生數限制”等。

3）軟約束：是指在若能夠完成基礎硬約束和硬約束排課的前提下，可適當考慮教學規律或個性化排課需求。如“每個班級的課程周分布均勻”;“教師特定時間段上課”等。

2 幾種算法比較

當前常用的排課算法，主要包括回溯算法、人工免疫算法、遺傳算法、粒子群優化算法、圖著色算法、貪婪算法、模擬退火算法、蟻群算法等，下面對這幾種常用算法的特點加以描述。

2.1 回溯算法

回溯算法也稱為試探法，它是一種類似枚舉 的系統搜索問題解的方法，原理是在搜索探試過程中尋找問題的解，當發現不滿足求解條件時，就“回溯"返回，嘗試別的路徑。

回溯算法基本步驟：面向設定問題，定義問題的解空間，它至少包含問題的一個解;設計易于搜索的解空間結構模型，使其能用回溯法搜索整個解空間;以深度優先的方法搜索解空間，并且在搜索過程中用剪枝函數來避免無效的搜索。

其優勢是整體結構清晰，容易理解;空間占比較小;適合處理組合數較大且有限的問題。其不足體現在算法計算量較大，回溯層次多時過于耗時[1]。

2.2 遺傳算法

遺傳算法是在20世紀六七十年代由美國密歇根大學的Holland教授創立的。Holland在設計人工自適應系統時建議參考遺傳學基本原理來模擬生物自然進化的方法。遺傳算法是一種基于進化論的自然選擇、遺傳進化并行，且隨機自適應的搜索算法[2]，將問題解通過復制、交叉、變異來編碼，生成的“染色體”群通過一代代的不斷進化、收斂，最終成為最適應的群體。

遺傳算法的基本步驟：預估期望進化代數，計數器初始設置，隨機生成多個初始群體;評估群體中各體適應度;在評估基礎上將優化的個體直接或者配對交叉產生新個體遺傳到下一代;將交叉算子（在此算法中起核心作用）作用于群體;群體通過選擇、交叉、變異運算這一系列手段修改來自個體串的某些基因座上的基因值從而得到下一代群體;若計數達到期望進化代數，則可得到最大適應度個體，即最優解[2]。