基于改進(jìn)型遺傳算法求解高校排課問題

龔程　陳高云　劉胤田　李代偉

摘 要：隨著信息技術(shù)的不斷發(fā)展和教育改革的不斷深入，通過信息技術(shù)實(shí)現(xiàn)教學(xué)管理的智能化已經(jīng)成為可能。排課作為教學(xué)管理的核心內(nèi)容之一，它是衡量教學(xué)管理水平的重要指標(biāo)，它是教學(xué)管理智能化的重要體現(xiàn)。本文的研究是通過學(xué)校的教學(xué)計(jì)劃分析并建立排課的數(shù)學(xué)模型，對傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)，設(shè)計(jì)出一種改進(jìn)的自適應(yīng)的遺傳算法求解排課問題，改進(jìn)的自適應(yīng)遺傳算法相對于傳統(tǒng)的遺傳算法在排課效率上有很大提高。

關(guān)鍵詞：排課模型；遺傳算法；節(jié)次；自適應(yīng)

中圖分類號：TP311.5 文獻(xiàn)標(biāo)識碼：A

Abstract：With the continuous development of information technology and the further deepening of education reform，intelligent teaching management by means of information technology has become possible.As one of the core contents of teaching management，course scheduling is an important index to measure teaching management as well as an important evidence of intelligent teaching management.This paper has analyzed and established the mathematics model of course scheduling through the teaching plan in colleges and universities，improved traditional genetic algorithm and designed an improved self-adaptive genetic algorithm to solve the scheduling problem.Compared with traditional genetic algorithm，the improved adaptive genetic algorithm has greatly increased the efficiency of course scheduling.

Keywords：course scheduling model；genetic algorithm；section；self-adaptive

1 引言（Introduction）

隨著信息技術(shù)的不斷發(fā)展和教育改革的不斷深入，通過信息技術(shù)實(shí)現(xiàn)教學(xué)管理的智能化已經(jīng)成為可能[1]。排課作為教學(xué)管理的核心內(nèi)容之一，它是衡量教學(xué)管理水平的重要指標(biāo)，它是教學(xué)管理智能化的重要體現(xiàn)。排課問題的目標(biāo)是在一定的約束條件下求解出較優(yōu)的排課方案，使得依據(jù)此方案執(zhí)行的教學(xué)計(jì)劃具有學(xué)生老師合理安排，教室資源利用率高，教學(xué)質(zhì)量高的特點(diǎn)[2，3]。

2 常見的排課模型（Common course scheduling model）

2.1 圖論算法

圖論中的圖是由若干給定點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系圖論解決排課問題，將圖論的邊著色理論，對排課資源進(jìn)行建模，使得排課問題得以解決[4]。但圖論本身是NP完全問題，算法實(shí)現(xiàn)上比較繁瑣。

2.2 貪心算法

貪心算法基本思路是從問題的某一個(gè)初始解出發(fā)一步一步地進(jìn)行，根據(jù)某個(gè)優(yōu)化測度，每一步都要確保能獲得局部最優(yōu)解。貪心算法的排課系統(tǒng)，以資源匹配為基礎(chǔ)，用內(nèi)存動態(tài)分區(qū)分配的最佳適應(yīng)法為依托解決排課問題[5]。與圖論算法比較，避免了算法實(shí)現(xiàn)上的困難，但貪心算法在斷點(diǎn)選擇中存在缺陷。

2.3 人工智能算法

人工智能是對人的意識、思維的信息過程模擬。人工智能解決學(xué)校的排課系統(tǒng)，以時(shí)間因素為核心進(jìn)行課程的安排符合學(xué)校教學(xué)實(shí)際情況，以影響學(xué)校課程安排中最為直接的三個(gè)因素教師。以學(xué)生和教室為核心來安排一門課程[6]。使用這種方法能夠使學(xué)校管理進(jìn)一步科學(xué)化，高效化。

3 基于高校的排課模型（Course scheduling model in colleges and universities）

3.1 相關(guān)術(shù)語

⑴教學(xué)班（Teaching Class）：一個(gè)教學(xué)班包含多個(gè)班級。例如：軟件工程2015級1—2班包含1班和2班兩個(gè)班，這樣定義不需要考慮合班情況，只需要在制定教學(xué)計(jì)劃時(shí)選擇出需要合班的班級即可，教學(xué)班集合定義為，每個(gè)教學(xué)班對應(yīng)的人數(shù)為。

⑵節(jié)次（Section）：一門課程上一節(jié)課45min所耗費(fèi)的時(shí)間為一個(gè)節(jié)次，一天共有10個(gè)節(jié)次，上午四個(gè)節(jié)次，下午四個(gè)節(jié)次和晚上兩個(gè)節(jié)次，節(jié)次集合定義為。

⑶課程（Course）：將課程分為公共基礎(chǔ)必修，公共基礎(chǔ)選修，學(xué)科基礎(chǔ)必修，學(xué)科基礎(chǔ)選修，專業(yè)課必修，專業(yè)課選修，實(shí)踐教學(xué)環(huán)節(jié)必修，實(shí)踐教學(xué)環(huán)節(jié)選修，表示課程的重要程度，即權(quán)重。課程的權(quán)重為1，2，3，…，8。

⑷教室（Class Room）：集合定義為。

⑸教師（Teacher）：集合定義為。

⑹時(shí)間間隔（Time Interval）：對于一周多學(xué)時(shí)的課程需要有時(shí)間間隔，用，表示間隔的天數(shù)。

3.2 約束條件

3.2.1 硬約束條件

3.2.2 軟約束條件

⑴課程約束：課程約束包含三個(gè)約束條件，分別是：①重要的課程要安排在教學(xué)效果好的節(jié)次；②同一門課程應(yīng)該安排在每周中同一個(gè)節(jié)次；③同一門課程的教室應(yīng)該安排一致。對應(yīng)的數(shù)學(xué)表達(dá)式如下：

⑵教師約束：教室約束包含三個(gè)約束條件，分別是：①同一個(gè)教師在一周上同一門課程是多節(jié)次，則課程的時(shí)間安排應(yīng)該有時(shí)間間隔；②同一個(gè)教師在一周上兩門課程，則課程的時(shí)間安排應(yīng)該連排；③同一個(gè)教師在一周上兩門課程，則課程的教室安排應(yīng)該足夠的近。對應(yīng)的數(shù)學(xué)表達(dá)式如下：

⑶學(xué)生約束：學(xué)生約束包含三個(gè)約束條件，分別是：①每個(gè)學(xué)生一個(gè)周節(jié)次排課分布均勻；②每個(gè)學(xué)生一天不能排滿課；③每個(gè)學(xué)生連續(xù)上兩門課程，則課程教室的安排應(yīng)該足夠的近。對應(yīng)的數(shù)學(xué)表達(dá)式如下：

其中，表示一個(gè)教學(xué)班在一個(gè)工作日所上的課程數(shù)，表示一周上課天數(shù)，表示一個(gè)教學(xué)班一天平均要上的節(jié)次。

⑷教室約束：教室約束是教室的利用率應(yīng)該高。對應(yīng)的數(shù)學(xué)表達(dá)式如下：

3.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的好壞決定了遺傳算法的收斂性，若目標(biāo)函數(shù)設(shè)計(jì)不合理會造成程序執(zhí)行過早收斂，形成局部最優(yōu)解，合理的目標(biāo)函數(shù)可以得到全局最優(yōu)解。本文所設(shè)計(jì)適應(yīng)度函數(shù)如式（6）所示，目標(biāo)函數(shù)適應(yīng)度的函數(shù)值的解越大所求出的解越優(yōu)。

3.4 排課的流程

排課是根據(jù)教務(wù)處指派的教學(xué)任務(wù)，合理的將教學(xué)任務(wù)分配教室和時(shí)間，排課流程如圖1所示。

4.1 編碼設(shè)計(jì)

編碼方式有浮點(diǎn)編碼、二進(jìn)制編碼、十進(jìn)制編碼等方式，本文采用十進(jìn)制編碼表示課表染色體的編碼，如下表2所示，能更好地表示排課問題的實(shí)際特點(diǎn)。每一種編碼對應(yīng)一條染色體，則每一條染色體表示的是一種排課可能。

例如：軟件學(xué)院張三教授給2012級軟件工程1班上《數(shù)據(jù)結(jié)構(gòu)》課程，課程每周兩次，在2棟樓101多媒體教室進(jìn)行，時(shí)間是第四周周一下午五六節(jié)，則可此授課事件的染色體編碼為011001-1201011-1220001-22101-0413（其中011001表示教師編碼，01表示軟件學(xué)院，1表示教師的職稱，001表示教師的編號）。

4.2 初始種群的產(chǎn)生

初始種群的產(chǎn)生一般通過隨機(jī)搜索的方式產(chǎn)生，為后續(xù)各種操作提供初始可行解。由于初始種群中生成的個(gè)體適應(yīng)度值較低，本文首先按照課程權(quán)重對課程進(jìn)行排序，該操作可以避免解空間的過早壓縮，同時(shí)能夠盡早的產(chǎn)生可行解。

4.3 選擇操作

根據(jù)達(dá)爾文的進(jìn)化論提出的“適者生存”的原則，選擇是從種群中選擇出優(yōu)秀的個(gè)體作為父代，并為下一代個(gè)體繁殖作基礎(chǔ)。選擇操作通常也稱作再生操作。選擇操作從種群中選擇出適應(yīng)度高的個(gè)體遺傳到下代個(gè)體。種群中個(gè)體的適應(yīng)度的值越大，被選擇的概率則越高。fi表示種群中個(gè)體的適應(yīng)度的值，n表示種群中個(gè)體的數(shù)量，則種群中個(gè)體的概率值：

4.4 自適應(yīng)交叉和變異操作

交叉操作是把種群中兩個(gè)個(gè)體進(jìn)行隨機(jī)的交叉重組，這種操作既保證的新產(chǎn)生的個(gè)體保留了父代個(gè)體的優(yōu)良基因，又是種群的個(gè)體具有多樣性。變異操作是種群中的個(gè)體根據(jù)一定的概率值做出基因位的變動。傳統(tǒng)的遺傳算法中，采用固定的交叉概率和變異概率，容易產(chǎn)生局部最優(yōu)解，本文采用自適應(yīng)的交叉和變異操作進(jìn)行遺傳算法的計(jì)算，具體操作如下：

其中，和分別表示交叉和變異概率，表示當(dāng)前種群最優(yōu)個(gè)體的適應(yīng)度值，表示當(dāng)前種群平均適應(yīng)度值，表示進(jìn)行交叉操作的個(gè)體中適應(yīng)度較大的值，表示變異個(gè)體適度值，和取值均為0到1的隨機(jī)數(shù)。

5 實(shí)驗(yàn)（Experiment）

5.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)數(shù)據(jù)是來自軟件工程學(xué)院2017年秋季課表，如表3所示。實(shí)驗(yàn)參數(shù)如表4所示。實(shí)驗(yàn)平臺采用2.20GHz，Pentium i7處理器、8GB內(nèi)存、700GB硬盤，操作系統(tǒng)為win7。所有實(shí)驗(yàn)均采用C#語言，在Visual Studio 2010下實(shí)現(xiàn)。

5.2 實(shí)驗(yàn)結(jié)果與分析

對于同一初始種群下，將文獻(xiàn)[7]中（GA）方法與本文方法（MGA）進(jìn)行對比。圖2是10次實(shí)驗(yàn)兩種方法不同的種群平均適度的值，MGA的平均值高于GA的平均值，圖3是10次實(shí)驗(yàn)兩種方法不同的時(shí)間值，MGA的時(shí)間值低于GA的時(shí)間值。由圖2和圖3可以看出，本文方法都優(yōu)于文獻(xiàn)[7]中的方法。

根據(jù)表5的評價(jià)指標(biāo)分析，改進(jìn)后的遺傳算法MGA比傳統(tǒng)的遺傳算法GA在課程均勻度，學(xué)生課程分布，教室滿意度及教室利用率方面都有明顯的改善。

6 結(jié)論（Conclusion）

本文針對高校排課問題進(jìn)行分析，根據(jù)教學(xué)計(jì)劃對排課問題建模，通過改進(jìn)的遺傳算法對問題進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的遺傳算法比一般的遺傳算法具有更高的效率。如何合理的解決排課中漏排課問題是下一步研究的重點(diǎn)。

參考文獻(xiàn)（References）

[1] Marc Goerigk，Christian Liebchen.An Improved Algorithm for the Periodic Timetabling Problem[C].17th Workshop on Algorithmic Approaches for Transportation Modelling，Optimization，and Systems，2017（12）：1-14.

[2] H Babaei，J Karimpour，A Hadidi.A survey of approaches for university course timetabling problem[J].Computers & Industrial Engineering，2015，86（C）：43-59.

[3] G Woumans，L De Boeck，J Belin.A column generation approach for solving the examination-timetabling problem[J].European Journal of Operational Research，2016，253（1）：178-194.

[4] 崔妍，王權(quán)，王康，等.排課問題的數(shù)學(xué)模型[J].沈陽工程學(xué)院學(xué)報(bào)（自然科學(xué)版），2016，12（3）：276-278.

[5] 聶小東，李振坤，陳平華.基于貪婪算法的排課系統(tǒng)的探討與實(shí)現(xiàn)[J].現(xiàn)代計(jì)算機(jī)：專業(yè)版，2007（11）：109-112.

[6] 楊斌.人工智能算法在學(xué)校排課系統(tǒng)中的應(yīng)用[J].數(shù)字技術(shù)與應(yīng)用，2015（10）：144-145.

[7] NPillay，W Banzhaf.An informed genetic algorithm for the examination timetabling problem[J].Applied Soft Computing，2010，10（2）：457-467.

作者簡介：

龔 程（1990-），男，碩士生.研究領(lǐng)域：數(shù)據(jù)挖掘.

陳高云（1963-），女，碩士，教授.研究領(lǐng)域：數(shù)據(jù)挖掘，數(shù)據(jù)集成與可視化.

劉胤田（1972-），男，博士，教授.研究領(lǐng)域：智能信息處理，數(shù)據(jù)集成與可視化.

李代偉（1976-），男，碩士，副教授.研究領(lǐng)域：智能信息處理，知識工程.