江蕭 弋改珍 袁嵐清

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）05-1032-04

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

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

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

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

1 遺傳算法

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

圖1 遺傳算法流程圖

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

2.1 總體設(shè)計(jì)

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

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

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

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

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

3）排課管理

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

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

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

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

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

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

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

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

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

2）初始種群

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

3） 約束條件

硬約束：

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

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

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

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

軟約束：

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

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

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

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

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

4） 評(píng)價(jià)函數(shù)

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

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

5）洗牌雜交

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

6）變異操作

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

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

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

3 實(shí)現(xiàn)與測(cè)試

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

圖5 自動(dòng)排課窗口

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

4 結(jié)論

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

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

參考文獻(xiàn)：

[1] 周建新. 課表編排專家系統(tǒng)[J].計(jì)算機(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].計(jì)算機(jī)工程與應(yīng)用，2002（4）：221-222.

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

[10] 余斌，謝昕.基于減小教師流動(dòng)性的排課算法研究[J].計(jì)算機(jī)時(shí)代，2004，10（2）：22-23.

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