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

黃嶺 秦春娣 陳偉

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

關(guān)鍵詞：排課;智能算法;分析對比

中圖分類號：TP312

文獻(xiàn)識別碼：

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

收稿日期：2019-12-05

基金項目：江蘇省大學(xué)生實踐創(chuàng)新訓(xùn)練計劃項目校級項目“機(jī)房排課系統(tǒng)的設(shè)計與實現(xiàn)"（項目編號：51800021644）

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

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

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

1 排課問題分析

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

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

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

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

2）硬約束：是指排課時需要遵循的教學(xué)計劃規(guī)定的一些硬性要求或?qū)嶋H教學(xué)場地的條件限制的原則。如“課程按照最小兩節(jié)或六節(jié)進(jìn)行”;“課程的總周數(shù)有要求”;“教學(xué)地點容納學(xué)生數(shù)限制”等。

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

2 幾種算法比較

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

2.1 回溯算法

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

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

其優(yōu)勢是整體結(jié)構(gòu)清晰，容易理解;空間占比較小;適合處理組合數(shù)較大且有限的問題。其不足體現(xiàn)在算法計算量較大，回溯層次多時過于耗時[1]。

2.2 遺傳算法

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

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