遺傳算法在排課系統(tǒng)中的應(yīng)用與設(shè)計研究

江蕭 弋改珍 袁嵐清

摘要：為了方便教學(xué)管理方面的課程安排，在研究遺傳算法的基礎(chǔ)上，以軟件工程的思想研究了排課系統(tǒng)的設(shè)計過程，并使用Java語言實現(xiàn)了基于遺傳算法的排課系統(tǒng)。經(jīng)過測試，該系統(tǒng)能自動完成自動排課和手動調(diào)整功能。

關(guān)鍵詞：遺傳算法；排課系統(tǒng)；Java

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）05-1032-04

排課是教學(xué)管理中十分重要、又相當復(fù)雜的管理工作，課程表的編排是一個涉及多種因素的組合規(guī)劃問題，它要保證在課程安排中教師、學(xué)生、教室不能產(chǎn)生沖突并且要滿足教師的要求和資源限制等約束條件。

為了利用計算機來解決這個實際問題，減輕工作人員的負擔(dān)，自20世紀60年代起就有學(xué)者投入研究，研究者對于排課系統(tǒng)的解決方案大致分為以下幾種：第一種是基于簡單的經(jīng)驗法則解決教學(xué)規(guī)模不太大的問題[1]；第二類是建立排課模型，將排課問題歸結(jié)為圖的邊染色問題[2]；第三種方式是先將固定時段的課程優(yōu)先排入，然后依序填入其他課程[3，4]；第四種方法是采用模塊化方式[5]；圖形著色法[6]；搜索法[7]，總之這些方法適合處理小規(guī)模排課問題，當問題的約束條件增多時，問題變得相對復(fù)雜，求解過程會變得非常困難。

我國在排課方面的解決方案總結(jié)為兩種：一是圖著色模型[8]；而是數(shù)學(xué)模型[9，10]。

本文在討論遺傳算法的基礎(chǔ)上，研究了遺傳算法在排課系統(tǒng)中的應(yīng)用和設(shè)計。

1 遺傳算法

遺傳算法最早于1968年由Holland教授提出，并建立了遺傳算法原型，形成了遺傳算法的理論基礎(chǔ)。遺傳算法是從生物進化論觀點出發(fā)，用計算機模擬自然界演化的方式，對既定問題求最優(yōu)解的方法，是基于自然選擇和基因遺傳、進化機制基礎(chǔ)上的一種高度并行、自適應(yīng)的優(yōu)化算法[11]。遺傳算法的操作步驟如圖1所示。

圖1 遺傳算法流程圖

2 排課系統(tǒng)的設(shè)計

2.1 總體設(shè)計

在充分調(diào)研教學(xué)排課管理業(yè)務(wù)后，經(jīng)過分析，總結(jié)排課系統(tǒng)管理的信息和完成的功能有：

1） 基礎(chǔ)信息管理

排課系統(tǒng)中所需要管理的基本信息有：教室信息、教師信息、課程信息、和班級信息；對這些信息管理的主要操作有、搜索、查看、添加、修改和刪除。

2） 學(xué)期計劃管理

學(xué)期計劃管理模塊主要依據(jù)學(xué)生的培養(yǎng)方案設(shè)置課程所在的學(xué)期、對應(yīng)的專業(yè)（班級）、課程的名字以及課程所需的學(xué)時數(shù)；并為每一門課程指定相關(guān)的任何教師。

3）排課管理

排課管理有自動排課和手動課表調(diào)整兩個方面的功能。自動排課是根據(jù)遺傳算法的工作原理，對排課系統(tǒng)所管理的基本信息和學(xué)期計劃進行雜交、編譯操作后得到基本滿足硬約束、軟約束條件的課表；然后，在自動排課的基礎(chǔ)上，將不滿足條件的部分內(nèi)容進行調(diào)整，最后生成教師課表、班級課表。

系統(tǒng)的總體功能模塊圖如圖1所示。

圖2 系統(tǒng)功能模塊圖

2.2 數(shù)據(jù)庫設(shè)計

根據(jù)排課系統(tǒng)所涉及到的實體有：課程、教師、教室、班級、學(xué)期；這五個實體中教師和課程之間有授課關(guān)系；學(xué)期和課程之間有學(xué)期計劃關(guān)系；班級與課程之間有班級課程關(guān)系；教室和課程之間有哪些課程在哪個教室上課的關(guān)系。關(guān)系E-R圖如圖3所示。

圖3 排課系統(tǒng)中各實體及其關(guān)系E-R圖

2.3 排課系統(tǒng)詳細設(shè)計

1） 表示結(jié)構(gòu)

在遺傳算法排課系統(tǒng)中，一條染色體中應(yīng)包含所有排課DNA分子，每個排課DNA分子又包含班級課程信息、老師信息、教室信息和時間信息，以及院系和學(xué)期信息。由于院系和學(xué)期在處理中是提前設(shè)定好的，在每次處理時都是一個給定的值，所以在染色體中可以不考慮他們。

2）初始種群

采用系統(tǒng)的隨機數(shù)，生成初始種群。將排課任務(wù)表示為CyKwTx，在進行排課時，初始化種群中的個體就是用隨機函數(shù)生成染色體中的RzMN的組合。

3） 約束條件

硬約束：

l每個指定時間段一個班級、一個教師、一個教室分別只能對應(yīng)一門課程；

l要求教室的個數(shù)大于或等于指定時間段將要安排的課程數(shù)；

l安排教室時，要求教室容量必須大于或等于班級人數(shù)；

l教室類型與課程要求一致。

軟約束：

l優(yōu)先安排全校公共基礎(chǔ)課；

l一周內(nèi)課次多于2次以上的多課時課程，在時間安排上要求盡量隔天安排；

l較難課程應(yīng)安排在上午第一節(jié)或下午第一節(jié)；

l體育課后盡量避免直接排課；

l同一門課程盡量安排在固定的教室。

4） 評價函數(shù)

評價函數(shù)是對種群中的每個染色體設(shè)定一個概率，使得高概率地選擇某染色體，適應(yīng)性值高的染色體被選擇產(chǎn)生后代的機會更大。

評價函數(shù)的定義因各種問題而異，參數(shù)的個數(shù)也不一致。一般情況下，都是根據(jù)某種性的函數(shù)將各基因所獲得的適應(yīng)值進行統(tǒng)計，以求得整條染色體的適應(yīng)值。

5）洗牌雜交

遺傳算法中的雜交算法主要有：多點雜交、均勻雜交和洗牌雜交。本系統(tǒng)設(shè)計中使用的是洗牌雜交，即從每個父本中取它們一般的基因重組成新的個體。

6）變異操作

變異是隨機改變一個染色體中某一基因的值，使得染色體出現(xiàn)新的基因特性，有時候?qū)⑶蠼膺^程中趨于局限制時出現(xiàn)新的解決方法。變異的染色體個數(shù)根據(jù)變異率而定，如果變異率過高，將近似于隨機數(shù)，難以達到最優(yōu)解，如果變異率過小，將無法達到變異的效果。

基于遺傳算法的排課流程圖，如圖4所示。

圖4 基于遺傳算法的排課流程圖

3 實現(xiàn)與測試

自動排課系統(tǒng)按照學(xué)期進行，首先在學(xué)期課程計劃中對教室、教室、課程、班級進行設(shè)置，在自動排課管理中選擇“自動排課”，自動排課窗口如圖5所示。

圖5 自動排課窗口

自動排課功能并不一定能得到恰當?shù)恼n表，這時可以手動對自動生成的課表進行調(diào)整。手工排課及課表調(diào)整窗口如圖6所示。

4 結(jié)論

排課系統(tǒng)的求解的方法在實際中有許多解決方案?；谶z傳算法的排課系統(tǒng)在實際效率上有很大的提高，這也是遺傳算法在解決實際問題的一個簡單應(yīng)用。該文使用Java語言設(shè)計實現(xiàn)了基于遺傳算法的排課系統(tǒng)，該系統(tǒng)實現(xiàn)了排課的自動化、智能化，使教務(wù)人員從繁雜的排課任務(wù)中解脫出來，而且對于推動教學(xué)的發(fā)展也起到非常重要的作用。

但是在非常復(fù)雜的應(yīng)用中，使用遺傳算法不一定能夠得到最優(yōu)解，即通過若干次迭代，算法不一定能收斂于某個最優(yōu)解。這是可以提供不同的可行解供使用者進行選擇，直到使用者得到一個解決方案為止。

參考文獻：

[1] 周建新. 課表編排專家系統(tǒng)[J].計算機應(yīng)用，2000，20（5）：76-78.

[2] Bondly J. A Graph Theory with Application[J].The Macnulan Press Ltd，1976：10-23.

[3] Selim S M. An Algorithms for Constructing a University Faculty Timetable[J].Compute Edue，1982（1）：323-332.

[4] Selim S M. An Algorithm for Producing Course and Lecture Timetable[J].Compute Edue，1983（2）：323-332.

[5] Dowsland W B，Lim S.Computer Aided School Timetable – part2：the Micro-computer for School Timetabling[J].Compute Education，1982（1）：2-4.

[6] Dde Werra. Restricted Coloring Models for Timetabling[J]. Discrete Mathematics，1997（1）： 161-179.

[7] Hertz A.Finding a Feasible Course Schedule Using Tabu Search[J].Discrete Applied Mathematics，1992（3）：255-270.

[8] 胡順仁，鄧毅，王錚.基于高校排課系統(tǒng)中圖論問題研究[J].計算機工程與應(yīng)用，2002（4）：221-222.

[9] 孫建平，梅曉勇.關(guān)聯(lián)規(guī)則在高校智能排課系統(tǒng)中的應(yīng)用[J].計算機應(yīng)用，2002，22（5）：37-38.

[10] 余斌，謝昕.基于減小教師流動性的排課算法研究[J].計算機時代，2004，10（2）：22-23.

[11] 周水庚.基于遺傳算法的排課系統(tǒng)設(shè)計與實現(xiàn)[D].上海：復(fù)旦大學(xué)，2006.