基于遺傳算法的排課編碼設(shè)計(jì)

李梅云

?

基于遺傳算法的排課編碼設(shè)計(jì)

李梅云

（漳州職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)工程系，福建 漳州 363000）

采用遺傳算法的基本理論，研究如何利用遺傳算法解決高校排課中的教室沖突、時(shí)間沖突、教師沖突和課表優(yōu)化等問題，根據(jù)人們的期望值設(shè)定遺傳算法染色體的優(yōu)先級。

教學(xué)管理；排課系統(tǒng)；遺傳算法；數(shù)據(jù)庫；時(shí)間片

隨著職業(yè)教育的發(fā)展，學(xué)院規(guī)模的擴(kuò)大，面對越來越多的學(xué)生和有限的教學(xué)資源，單純的以手工來完成學(xué)院的教學(xué)管理工作效率跟不上需要，須采用一種更快捷的處理方式。作為教學(xué)管理工作重要項(xiàng)目的排課，利用計(jì)算機(jī)進(jìn)行排課能夠快速地得到滿足約束條件的可行結(jié)果，具有時(shí)間短、人力省和質(zhì)量高的優(yōu)點(diǎn)。目前排課算法有“反復(fù)比較法、優(yōu)先級法、整體規(guī)劃法、蟻群法、遺傳算法等等。

1 排課約束條件分析

排課問題是一個(gè)NP完全類【1】，主要要考慮排課的硬性約束條件和軟性約束條件。協(xié)調(diào)好排課五種要素：班級、教室、教師、課程、時(shí)間。排出的課表盡可能實(shí)現(xiàn)三贏，即滿足學(xué)校、班級和教師三方的需求。

1.1 排課問題的要素

要排一張好的課表，首先就要對教學(xué)資源進(jìn)行調(diào)查和統(tǒng)計(jì)，清楚所有教學(xué)資源，這樣才能做出一張盡量不出現(xiàn)沖突，也能最大發(fā)揮教學(xué)資源利用率的完美課表，下面就排課所涉及到的因素進(jìn)行分析。

課程是排課因素里一個(gè)很重要的要素，每一門課程都有其課程的編號、名稱、是理論型課還是實(shí)訓(xùn)課、學(xué)時(shí)、學(xué)分、該課程的教師資源情況、授課對象情況、開設(shè)的院系、所需要的教學(xué)設(shè)備，每一門課程都有對應(yīng)的授課計(jì)劃，是否一個(gè)學(xué)期上完。每門課程既可以指定教師，又可以不指定教師。有些課程可以有多個(gè)班級合并上課，有時(shí)候是跨院系的。每門課程都有對教室類型的相關(guān)要求。如多媒體教室、一體化教室、語音室、實(shí)驗(yàn)室等等。某些課程由于上課班級較多難以協(xié)調(diào)或照顧教師要求等諸如此類原因，應(yīng)該預(yù)先給定時(shí)間或教室。

班級是教學(xué)的基本單位，應(yīng)有編號、專業(yè)名稱、學(xué)制、所在院系、輔導(dǎo)員等信息。在排課時(shí)要可慮到班級學(xué)生人數(shù)的多少、層次，便于在排課時(shí)發(fā)現(xiàn)班級人數(shù)少的班級在上公共課時(shí)可慮合班上課，節(jié)省教學(xué)資源。我們學(xué)校把全校的教室按系進(jìn)行分配如我們學(xué)校有成業(yè)樓、興業(yè)樓、敬業(yè)樓等教學(xué)樓，把這些教學(xué)樓分配給各系，讓各系自行支配所分得的教學(xué)樓。在此種情況下，在排課時(shí)會減低教室使用的沖突。

時(shí)間是排課中無形的但又左右排課的一個(gè)要素。學(xué)校時(shí)間一般為學(xué)年、學(xué)期、周、星期幾、時(shí)段、節(jié)。每天分三個(gè)時(shí)間段（上午、下午和晚上）。每個(gè)時(shí)間段又進(jìn)行分節(jié)，如上午為1、2、3、4，下午為5、6、7、8，晚上為9、10。一節(jié)就是一個(gè)課時(shí)，是上課的最小單元，一般一門課程的上課是按兩節(jié)課來進(jìn)行，所以可以把時(shí)間劃分為5個(gè)時(shí)間片，如表1所示用T1,T2,T3…T25表示。時(shí)間沖突決定了課表的實(shí)用性，因此要把時(shí)間進(jìn)行科學(xué)的合理的組織和分配。

表1 周時(shí)間片

教師是教學(xué)活動(dòng)的一個(gè)主體，能否合理、有效、充分利用教師資源，決定學(xué)校的辦學(xué)質(zhì)量和水平。學(xué)校教師可分為教學(xué)型、研究型和教學(xué)研究型三種。在錄入教師基本情況時(shí)，都要對他們進(jìn)行詳細(xì)的登記如姓名、編號、學(xué)歷、職稱、研究方向、所能勝任的課程等。

作為基本教學(xué)管理的院系單位，在排課時(shí)應(yīng)該充分考慮各院系的不同，盡量協(xié)調(diào)，達(dá)到和諧，比如不要出現(xiàn)院系辦公室沒人的情況。包括院系名稱、編號、所在校區(qū)、辦公室人員。

班級做為教學(xué)活動(dòng)的另外一個(gè)主體，應(yīng)考慮學(xué)生上課的最佳時(shí)段，盡量把課程安排在該時(shí)段上課。提高學(xué)生的學(xué)習(xí)興趣，從而提高教學(xué)水平。每個(gè)班級都要設(shè)置專業(yè)、班號、年紀(jì)等。

教室是實(shí)施教學(xué)活動(dòng)的場所，每一間教室都有其特有信息，比如該教室處于哪個(gè)校區(qū)，歸哪個(gè)系所有，這間教室可以容納的學(xué)生數(shù)，是什么類型的教室等等。

1.2 排課問題的約束條件

眾所周知，排課是一種多組合問題【2】。它不僅要考慮很多的資源如教師、教室、時(shí)間、班級等，還要考慮排課問題自身的約束條件。根據(jù)現(xiàn)有的文獻(xiàn)，可以看到，一般把約束條件分成兩種，一種是硬性約束條件，另外一種是軟性約束條件。所謂的硬性約束條件就是在排課過程中一定要滿足的條件，而軟性約束條件就是盡量滿足的條件，如果滿足了，可以使排課的效果更佳，但如果沒有滿足，也沒關(guān)系，不會影響排課。排出來的課表在實(shí)際情況中是否可行就得由硬性約束條件來衡量，而課表是否優(yōu)秀就要采用軟性約束條件來評判。下面列出一些硬性約束條件和軟性約束條件。

1）硬性約束條件

（1）一個(gè)班級不能同時(shí)段在兩個(gè)或兩個(gè)以上教室上課；（2）一位老師不能同時(shí)段在兩個(gè)或兩個(gè)以上教室上課；（3）一間教室不能同時(shí)段有兩門或兩門以上的課程同時(shí)占用；（4）教室的座位數(shù)必須大于等于上課的學(xué)生人數(shù)。

2）軟性約束條件

（1）理論上說上午的時(shí)間上課效果優(yōu)于其它時(shí)間，其次是下午、晚上；（2）要盡量為專業(yè)課程安排上課效果好的時(shí)間段；（3）是連堂類課還是分散類課；（4）中午、周末盡量不要排課；（5）盡量不要在體育課完后排課；（6）一個(gè)班級應(yīng)盡量避免安排在連續(xù)的時(shí)間段上相同的課程；（7）盡量安排教師在比較集中地時(shí)間上同一門課；（8）先排專業(yè)課，再排基礎(chǔ)課、公共課。

在對教學(xué)資源和約束條件都比較清楚情況下，就可以在有限的教學(xué)資源下，充分運(yùn)用約束條件來解決排課問題。先來看一個(gè)例子，假設(shè)就一個(gè)班級，那么學(xué)校的所有資源就只有這個(gè)班級使用。這種情況下就不用考慮會發(fā)生沖突，就表2這樣的一個(gè)簡單的二維表就可解決。但實(shí)際情況是學(xué)校不可能只有一個(gè)班級，隨著班級數(shù)的增多，沖突也就跟著增多，約束條件也會越來越多。而排課問題又是一個(gè)多組合和不確定性的組合規(guī)劃問題的求解，約束條件越多，求解越困難。

表2 簡單課表

但隨著班級的增加，開課計(jì)劃數(shù)的增加，其組合方案為（其中n為所有班級要排課的計(jì)劃數(shù)，m為需要排課的班數(shù)）將會迅速增加【3,4】。在一個(gè)大學(xué)里班級數(shù)多，且排課的計(jì)劃數(shù)組合方案會隨著n和m的增加，呈線性增長。如何控制這種增長，是我們排課的關(guān)鍵。對于排課這種沒有確定解的組合問題，在排課時(shí)，不可能只有一個(gè)解，它可能有多個(gè)解，在選擇解時(shí)，就要選擇那種不發(fā)生硬性約束條件沖突的，包含所有年級、課程、班級的，可以滿足較為多種的軟性約束條件的解。盡管一次好的排課，在人們理解是也只是使用如優(yōu)秀、合理、完美等這些文字來形容，沒有一個(gè)數(shù)量上的概念；但在實(shí)施具體排課時(shí)，就要把人們的這種模糊的、不確定的因素量化。

2 遺傳算法求解排課

用遺傳算法求解排課這樣一個(gè)實(shí)際問題時(shí)，首要要做的是如何把這個(gè)排課問題表示成染色體，使之便于實(shí)施遺傳算法。在本文中每一條染色體代表著一個(gè)班級的課表，可采用十進(jìn)制進(jìn)行編碼，染色體的結(jié)構(gòu)可用下面的結(jié)構(gòu)表示出來：

染色體以十進(jìn)制數(shù)編碼為例，例如09嵌入式2的班級編號是21100902，有一門課為計(jì)算機(jī)導(dǎo)論，該課程的課程編號是0103010，上這門課的教師編號為33，學(xué)時(shí)為4，隨機(jī)選擇大于班級總?cè)藬?shù)的教室，則可生成染色體如：“21100902010301033B5020211”，其中B502代表教室，02、11分別代表上課時(shí)間是星期一上午的3、4節(jié)和星期三上午的1、2節(jié)。每一條染色體表示一種可能的排課結(jié)果。這樣就可排出所有班級所有課程，但在實(shí)際的排課中還涉及到資源沖突問題。如所排的課表是否有時(shí)間、教室、教師等方面沖突，所以還需要適應(yīng)度函數(shù)來評判排課結(jié)果的優(yōu)劣。

由于適應(yīng)值是遺傳算法中個(gè)體生存機(jī)會選擇的唯一確定標(biāo)準(zhǔn)指標(biāo)，所以適應(yīng)值函數(shù)的形式直接決定著群體的進(jìn)化行為。在本文中，適應(yīng)度函數(shù)的設(shè)計(jì)是先設(shè)定各種硬性和軟性約束條件的期望值，再對每條染色體中存在的硬性和軟性約束條件的期望值進(jìn)行求和。表3、4、5、6列出一些排課相關(guān)因素的期望值。則適應(yīng)值就可設(shè)置為f=∑si（i =1…k）。其中si表示某條約束條件的期望值染色體適應(yīng)度函數(shù)值越大，則表示適應(yīng)性越好，其在下一代的演化中的生存概率就較大。

表3 同一班級上課時(shí)間間隔的期望值

表4 同一教師上不同班級的同一門課時(shí)間間隔的期望值

表5 不同課程上課時(shí)間的期望值

表6 同一教師上不同課時(shí)間間隔的期望值

2.1 初始化

初始化的作用主要為后面的遺傳操作提供初始種群。而在不具有問題解空間先驗(yàn)知識的情況下，很難判定最優(yōu)解的數(shù)量和其在可行解空間中的分布情況。因此初始群體的個(gè)體一般多是隨機(jī)產(chǎn)生的。在算法中，是以班級作為染色體的，所以在初始化時(shí)就需要考慮跟班級相關(guān)的因素。對于一個(gè)班級來說班級上課不外乎涉及到上課的教室，上課時(shí)間，上課科目，上課教師這幾個(gè)因素。

在此算法中采用先對教室的容量與該班級的人數(shù)做比較，把大于班級人數(shù)而且教室多出的座位不超過10各座位的教室設(shè)置為一個(gè)教室空閑集room(),再對每一個(gè)班保留一個(gè)空閑時(shí)間集hour(c)。先把教師和課程安排進(jìn)去再搜索時(shí)間空閑集hour(c)，把時(shí)間分配給該課程；搜索教室空閑集room()，把教室分配給該課程。重復(fù)上述過程，直到生成初始的一個(gè)班級的課表。以此得到個(gè)個(gè)班級的初始課表。

2.2 選擇算子

選擇運(yùn)算又稱復(fù)制操作，它是模擬自然界適者生存、優(yōu)勝劣汰的自然選擇現(xiàn)象。它以一定的概率從種群里選擇若干對個(gè)體的操作，放入下一代種群中，接下來的交叉操作和變異操作都是以此為依據(jù)的。

在系統(tǒng)設(shè)計(jì)時(shí)采用了輪盤賭選擇法。某染色體被選中的概率可表示為pi=fi/∑fi，式中fi為種群中第i個(gè)染色體對應(yīng)的適應(yīng)值，∑fi是種群中所有染色體的適應(yīng)度值之和。

2.3 交叉算子

選擇操作可以使種群里比較好的染色體，遺傳到下一代；但選擇操作只是做選擇，不能創(chuàng)造出新的染色體，因此，還需要交換操作，交叉也稱雜交、交換。

在排課系統(tǒng)中，因?yàn)榫幋a是以數(shù)據(jù)庫記錄字段為單位進(jìn)行的，而且影響排課問題的元素本身相互之間有關(guān)聯(lián)，所以不能利用簡單的單點(diǎn)交叉和雙點(diǎn)交叉。本文的交叉算子選擇多點(diǎn)交叉的方式進(jìn)行，在編碼時(shí)，編碼的順序是班級、課程、教師、教室和時(shí)間。將這些編碼分成三個(gè)段：班級、課程與教師一組、教室一組和時(shí)間一組，在交叉時(shí)隨機(jī)選擇兩條染色體，然后再隨機(jī)的在對應(yīng)的某兩段之間進(jìn)行交換。

2.4 變異

變異運(yùn)算用來模擬自然界中生物的基因突變，讓遺傳因子以一定的概率變化，這種變化的概率通常都比較小。在系統(tǒng)中，利用變異算子的局部的隨機(jī)搜索可以加速向最優(yōu)解逼近的能力，當(dāng)運(yùn)算接近最優(yōu)解區(qū)域時(shí)，先設(shè)定變異算子為教室中的任意時(shí)間片。

3 結(jié)束語

根據(jù)漳州職業(yè)技術(shù)學(xué)院實(shí)際情況，本文通過對人們的期望值設(shè)定遺傳算法染色體的優(yōu)先級，并設(shè)定時(shí)間空閑集和教室空閑集。基本解決了高校排課中的教室沖突、時(shí)間沖突、教師沖突和課表優(yōu)化等問題。

高校排課系統(tǒng)一直是教務(wù)管理中重要、復(fù)雜的問題,除了對系統(tǒng)進(jìn)行精心設(shè)計(jì)外還要在排課過程中,還要充分發(fā)揮個(gè)人主觀能動(dòng)性,把學(xué)生的利益放在第一位,同時(shí)兼顧教師和校方的利益。另外，排課人員需要掌握各種現(xiàn)代化管理技術(shù),不斷改進(jìn)排課的方法,促進(jìn)教育信息化建設(shè),這也是高等教育改革向縱深發(fā)展的必然要求。

[1] 蔡振鋒.遺傳算法在高校排課中的應(yīng)用[J].湖北工業(yè)大學(xué)學(xué)報(bào),2006(1):35-38.

[2] 霍然.自然與人工系統(tǒng)的適應(yīng)性[M].北京:高等教育出版社,2008.

[3] 陳喬禮,吳懷宇.一種新的求解旅行商問題的混合遺傳算法[J].武漢科技大學(xué)學(xué)報(bào)：自然科學(xué)版,2007(1):19-22.

[4] 王曉倩,陳定觀,林禮區(qū).高校實(shí)驗(yàn)教學(xué)排課系統(tǒng)的設(shè)計(jì)與開發(fā)[J].科技資訊,2009(2):27-31.

The Course code design Based on Genetic Algorithms

LI Mei-yun

(Department of Computer Engineering,Zhangzhou Institute of Technology,Zhangzhou 363000,China)

The author uses the basic theory of the genetic algorithm to study how to solve the problems of resource conflict and curriculum optimization by way of genetic algorithm. The system allows people to set the priority of chromosome genetic algorithm according to people's expectations.

Teaching management；curriculum-arrangement；system；genetic algorithms；time slice

2011－06－25

李梅云（1981－），女，福建莆田人，助教，碩士。

TP311.52

A

1673-1417（2011）03-0022-06

（責(zé)任編輯：季平）