王軍，陳建云

（南京信息工程大學(xué)計(jì)算機(jī)軟件學(xué)院，江蘇南京210044）

隨著高校的發(fā)展，課程安排已成為教務(wù)部門(mén)頭痛的事情，經(jīng)常會(huì)出現(xiàn)課程排列沖突，比如：一個(gè)教師在同一時(shí)間上兩門(mén)課，有兩個(gè)教師同時(shí)去一個(gè)教室上不同的課程，有些教師在特定時(shí)間不可以上課但卻安排有課。如果沒(méi)有很好地解決這些沖突，必將產(chǎn)生教學(xué)混亂等現(xiàn)象?？梢?jiàn)，排課算法的正確性、高效性是非常關(guān)鍵的。

1 排課問(wèn)題的數(shù)學(xué)模型

學(xué)校排課問(wèn)題本質(zhì)上是時(shí)間表問(wèn)題的一類(lèi)典型應(yīng)用實(shí)例，是為了解決課程安排對(duì)時(shí)間和空間資源的有效利用并避免相互沖突。在排課過(guò)程中，需要考慮課程教學(xué)效果、滿足教師特殊要求等多項(xiàng)優(yōu)化指標(biāo)，將各門(mén)課程安排到相應(yīng)的時(shí)間和教室需要付出一定的成本。

1.1 符號(hào)與約束條件

設(shè)課程集合：P={p1，p2，...，pm，...，pM}；教師集合：M={m1，m2，...，mp，...，mP}；教室集合：S={s1，s2，...，sk，...，sK}；班級(jí)集合：C={c1，c2，...，cn，...，cN}；時(shí)間集合：T={t1，t2，...，td，...，tD}；時(shí)間與教室對(duì)的笛卡爾積為：G=T·S=（t1，s1），（t1，s2），...，（tD，sK）；G中的元素稱為時(shí)間教室對(duì)；課表問(wèn)題的求解過(guò)程就轉(zhuǎn)化成為每一門(mén)課程尋找一個(gè)合適的時(shí)間教室對(duì)。

排課過(guò)程中必須滿足各種約束條件，各種約束條件可以歸納成2類(lèi)，這樣能簡(jiǎn)化分析過(guò)程。

1.1.1 硬 約束條件

硬約束條件是在排課過(guò)程中由于各類(lèi)資源的有限，因此必須滿足而無(wú)法變更的約束條件，通常只要滿足下面3類(lèi)硬約束條件就能夠保證在排課的過(guò)程中不發(fā)生此類(lèi)沖突。

1）同一時(shí)間，一個(gè)教師只能上一門(mén)課程，記為X1，且X1≤1，其中：p=1，...，P；d=1，...，D。當(dāng)X1=1時(shí)，教師mp在時(shí)間td和教室sk上課pm；當(dāng)X1=0時(shí)，不成立。

2）同一時(shí)間，一個(gè)班級(jí)只能上一門(mén)課，記為X2，且X2≤1，其中：n=1，...，N；d=1，...，D。當(dāng)X2=1時(shí)，班級(jí)cn在時(shí)間td上教師mp的課程pm；當(dāng)X2=0時(shí)，不成立。

3）同一時(shí)間，一個(gè)教室只能上一門(mén)課，記為X3，且X3≤1，其中：k=1，...，K；d=1，...，D。當(dāng)X3=1時(shí)，教室sk在時(shí)間td由教師mp上課程pm；當(dāng)X3=0時(shí)，不成立。

1.1.2 軟 約束條件

軟約束條件是在排課過(guò)程中可以滿足又可以不完全滿足的約束條件，是排課過(guò)程中在滿足硬約束條件的基礎(chǔ)上能盡量要求滿足的約束條件。軟約束條件會(huì)因不同的教學(xué)情況而有所差異。通常也可以通過(guò)調(diào)節(jié)軟約束條件的滿足程度而改變排課的效果，可以將一定要滿足的軟約束條件轉(zhuǎn)換為“硬約束條件”。

以下是排課過(guò)程中常用的軟約束條件：

1）教師①老師一天之中連續(xù)上課節(jié)數(shù)；②老師課程大部分在上午或下午；③總學(xué)分為奇數(shù)的課程一次連上三小節(jié)；④早上8點(diǎn)（第一節(jié)）是否排課；⑤下午4點(diǎn)以后（最后一節(jié)）是否排課；⑥中午12點(diǎn)（第五節(jié)）是否排課；⑦一門(mén)課盡量分散在一個(gè)星期中。

2）學(xué)生①中午（12：00）盡量不要排課；②上完體育課盡量不要排課；③共同科目同班級(jí)一起上；④選修科目各班級(jí)分開(kāi)選課；⑤對(duì)于總學(xué)分為偶數(shù)的課程采取兩學(xué)分課連上；⑥對(duì)于總學(xué)分為奇數(shù)的課程采取三學(xué)分課連上；⑦學(xué)生課表中的上課時(shí)間不能過(guò)分集中，應(yīng)避免一天課程很滿而另一天卻一整天沒(méi)課的情況。

2 排課問(wèn)題的算法

2.1 算法流程

遺傳操作流程如圖1所示。

圖1 遺傳操作流程圖Fig.1 Flow chart of Genetic operation

2.2 染色體編碼

遺傳算法（GA）中首要考慮的是如何表現(xiàn)其問(wèn)題，即如何對(duì)染色體編碼，使之適用于GA操作。在經(jīng)典的遺傳算法中，常采用浮點(diǎn)數(shù)或二進(jìn)制的編碼方法，而研究中，每條染色體代表每位教師的課表，其結(jié)構(gòu)表示如圖2所示。

圖2 課表用染色體表示的結(jié)構(gòu)Fig.2 Structure of schedule of chromosomes

班級(jí)ID染色體在程序中可用十進(jìn)制數(shù)編碼，例如：某一個(gè)教師編號(hào)為1234，要教“計(jì)算機(jī)基礎(chǔ)”這門(mén)課，課程編號(hào)為5678，周學(xué)時(shí)為4，班級(jí)為JSJ08001、JSJ08002，隨機(jī)產(chǎn)生上課時(shí)間，隨機(jī)選擇大于兩班總?cè)藬?shù)的教室，則可生成染色體如：“JSJ08001 JSJ0800256781234024012241”其中02401，2241分別代表教室及上課時(shí)間星期二第二個(gè)教學(xué)單元（即上午3、4節(jié)）和星期四第一個(gè)教學(xué)單元（即上午1、2節(jié)）。

按如上編碼，兩條染色體對(duì)后9位作交叉操作，不會(huì)影響到每位教師所教授的課程，也不會(huì)造成教師課表內(nèi)含其他教師的教授課程或每代演化后染色體結(jié)構(gòu)不合理等問(wèn)題。

2.3 初始種群生成

一個(gè)染色體就是一個(gè)可能的排課結(jié)果，是一個(gè)m×26的數(shù)組，需處理的數(shù)據(jù)量較大，結(jié)構(gòu)相對(duì)比較復(fù)雜。如果初始種群中個(gè)體的分布不好，將很容易使整個(gè)排課結(jié)果陷入局部最優(yōu)而得不到好的排課結(jié)果，因此初始種群的生成對(duì)整個(gè)算法的影響較大。

2.4 選擇操作

在排課表問(wèn)題中，選擇操作方式采用輪盤(pán)賭方法，按照輪盤(pán)中的比例進(jìn)行區(qū)域的分配。適應(yīng)度較高的方案占據(jù)區(qū)域較大，選中的概率也較大，適應(yīng)度低的方案占據(jù)區(qū)域較小，選中的概率也較小。

2.5 交叉操作

編排課時(shí)，根據(jù)點(diǎn)交叉算子的思想，可在p個(gè)開(kāi)課時(shí)間和教師課表中隨機(jī)采樣兩個(gè)Li，對(duì)所有Pij和Tij的值進(jìn)行互換。將互換后的兩個(gè)個(gè)體作為兩個(gè)子代插入新種群。也可以選擇某個(gè)班級(jí)的課表TC和學(xué)生課表sij，對(duì)TC集合和S集合中的所有時(shí)間安排進(jìn)行互換。此時(shí)，交換的基因是若干個(gè)L時(shí)間安排組成的集合。

2.6 變異操作

變異雖然以很小的概率發(fā)生，但是它保證種群的多樣性，防止搜索得到的解陷入次優(yōu)解，有效抑制遺傳早熟現(xiàn)象的發(fā)生。隨機(jī)的方法可以保證個(gè)體的迥異，從而保證初始解在解空間的均勻性。在變異操作中隨機(jī)選擇一個(gè)個(gè)體的基因，這個(gè)基因可以是時(shí)間也可以是教室等，讓它隨機(jī)變換成另一個(gè)時(shí)間或者教室，使其在原始空間位置做輕微擾動(dòng)，有利于搜索空間逐漸向全局最優(yōu)空間靠攏。

2.7 適應(yīng)函數(shù)

編排課表主要將以下幾方面因素作為排課表所要達(dá)到的目標(biāo)：教師對(duì)時(shí)間的期望滿意度、教師課時(shí)分布密度、班級(jí)課時(shí)日分布均勻度、大多數(shù)學(xué)生愿意上此節(jié)課的程度。將以上4個(gè)目標(biāo)分別賦予不同的權(quán)值wi，運(yùn)用線性加權(quán)法，得適應(yīng)函數(shù)為中，α代表可行系數(shù)，當(dāng)進(jìn)行交叉形成不可行的課表（出現(xiàn)了教師、教室、時(shí)間等的沖突）時(shí)，則該方案的適應(yīng)度為0，在求解過(guò)程中直接被剔除。由于在交叉過(guò)程中會(huì)產(chǎn)生許多適應(yīng)度為0的方案，所以采用隨機(jī)生成初始種群的辦法不斷形成等量的可行解，以保持群體規(guī)模，避免算法的過(guò)早收斂。

2.8 停止規(guī)則

如果一輪適應(yīng)度計(jì)算比較以后，利用輪盤(pán)賭的方法按照一定的概率進(jìn)行選擇操作，將適應(yīng)度較高的個(gè)體選擇出來(lái)，以便于保留優(yōu)秀的個(gè)體為以后的操作，沒(méi)有達(dá)到理想的狀態(tài)，則按照一定的交叉概率進(jìn)行個(gè)體之間的交叉和遺傳變異操作，重組個(gè)體后再計(jì)算下一代的適應(yīng)度。直到有一代的適應(yīng)度達(dá)到預(yù)期要求。如果遺傳的代數(shù)達(dá)到了最大數(shù)，則將結(jié)果輸出，若滿足適應(yīng)度，且各個(gè)約束條件都已經(jīng)不存在沖突，則認(rèn)為排課結(jié)果比較合理，宣告遺傳算法正常結(jié)束。

3 系統(tǒng)結(jié)果展示

開(kāi)發(fā)排課系統(tǒng)，簡(jiǎn)要介紹C#運(yùn)用遺傳算法的實(shí)現(xiàn)過(guò)程。在VS2005運(yùn)行，生成主頁(yè)面排課系統(tǒng)，有排課向?qū)?，如圖3所示。然后輸入教師ID號(hào)、教師姓名、所教課程與優(yōu)先級(jí)排課，輸入完之后點(diǎn)擊下一步，到最后有開(kāi)始排課，就會(huì)給出排課的各種方案，如圖4所示。

圖3 排課系統(tǒng)主頁(yè)面Fig.3 Main page of timetabling system

圖4 排課后的方案Fig.4 Scheme after the timetabling

4 結(jié)論

該模型與求解方法已在實(shí)際中得到應(yīng)用，取得了較好的效果。在使用遺傳算法優(yōu)化后排課算法的實(shí)際效率有極大的提高。因此用遺傳算法實(shí)現(xiàn)類(lèi)似排課問(wèn)題的最優(yōu)解也是一種比較簡(jiǎn)單實(shí)用的方法，收斂速度很快，時(shí)間段分配均勻。但是在實(shí)際應(yīng)用中也可能沒(méi)有終止條件，目的是可以依次提供不同的可行解以供使用者選擇直到所有解給完或者使用者終止。如果只考慮最優(yōu)解的問(wèn)題，可以使用迭代的適應(yīng)度幾乎不變作為終止條件或者規(guī)定迭代次數(shù)。值得一提的是，有些實(shí)際問(wèn)題的可行解可能是唯一的，比如教學(xué)場(chǎng)地或教師資源緊缺的情況，更嚴(yán)重的是如果約束條件太苛刻，甚至可能沒(méi)有可行解，在此類(lèi)情況下人工干預(yù)還是有必要的。

[1]李敏強(qiáng).遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社.2002.

[2]韋玉，馮速.免疫遺傳算法在排課問(wèn)題中的應(yīng)用[J].北京師范大學(xué)學(xué)報(bào)，2008，44（2）：168-172.

WEI Yu，F(xiàn)ENG Su.The application of immune genetic algorithm int the proble of timetabling[J].Journal of Beijing Normal University，2008，44（2）：168-172.

[3]魏平熊，偉清.用遺傳算法解組卷問(wèn)題的設(shè)計(jì)與實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī)，2002，8（4）：44-50.

WEI Ping-xiong，WEI Qing.Test paper problem solving by generic algorithm[J].Microelectronics&Computer，2002，8（4）：44-50.

[4]Salem M，AlYakoob，Hanif D S.A mixed-integer programming approach to a class timetabling problem：a case study with gender policies and traffic considerations[J].European Journal of Operational Research，2007（180）：1028.

[5]膝姿，鄧輝文，楊久俊.基于遺傳算法的排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2007，27（12）：199-201.

QI Zi，DENG Hui-wen，YANG Jiu-jun.Timetabling system’s design and implementation based on the genetic algorithm[J].Journal of Computer Application，2007，27（12）：199-201.

[6]陳靜.自動(dòng)排課系統(tǒng)算法的分析與設(shè)計(jì)[J].科技情報(bào)開(kāi)發(fā)與經(jīng)濟(jì),2007，17（34）：217-219.

CHEN Jing.Analysis on and design of the algorithm of the auto-arranging curriculum system[J].Sci-tech in formation development&economy，2007，17（34）：217-219.

[7]唐慧豐.遺傳算法原理與應(yīng)用[EB/OL].（2006-05-20）

[2010-03-20].http：//wenku.baidu.com/view/0732d180d4d8d-15abe234e35.html.