基于改進型遺傳算法求解高校排課問題

龔程　陳高云　劉胤田　李代偉

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

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

中圖分類號：TP311.5 文獻標識碼：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ù)實現(xiàn)教學管理的智能化已經(jīng)成為可能[1]。排課作為教學管理的核心內(nèi)容之一，它是衡量教學管理水平的重要指標，它是教學管理智能化的重要體現(xiàn)。排課問題的目標是在一定的約束條件下求解出較優(yōu)的排課方案，使得依據(jù)此方案執(zhí)行的教學計劃具有學生老師合理安排，教室資源利用率高，教學質(zhì)量高的特點[2，3]。

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

2.1 圖論算法

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

2.2 貪心算法

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

2.3 人工智能算法

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

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

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

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

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

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

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

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

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

3.2 約束條件

3.2.1 硬約束條件

3.2.2 軟約束條件

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

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

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

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

⑷教室約束：教室約束是教室的利用率應該高。對應的數(shù)學表達式如下：

3.3 適應度函數(shù)

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

3.4 排課的流程

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

4.1 編碼設計

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

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

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

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

4.3 選擇操作

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

4.4 自適應交叉和變異操作

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

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

5 實驗（Experiment）

5.1 實驗數(shù)據(jù)

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

5.2 實驗結(jié)果與分析

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

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

6 結(jié)論（Conclusion）

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

參考文獻（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ù)學模型[J].沈陽工程學院學報（自然科學版），2016，12（3）：276-278.

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

[6] 楊斌.人工智能算法在學校排課系統(tǒng)中的應用[J].數(shù)字技術(shù)與應用，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)域：智能信息處理，知識工程.