李梅云

?

基于遺傳算法的排課編碼設計

李梅云

（漳州職業(yè)技術學院 計算機工程系，福建 漳州 363000）

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

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

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

1 排課約束條件分析

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

1.1 排課問題的要素

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

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

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

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

表1 周時間片

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

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

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

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

1.2 排課問題的約束條件

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

1）硬性約束條件

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

2）軟性約束條件

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

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

表2 簡單課表

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

2 遺傳算法求解排課

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

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

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

表3 同一班級上課時間間隔的期望值

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

表5 不同課程上課時間的期望值

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

2.1 初始化

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

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

2.2 選擇算子

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

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

2.3 交叉算子

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

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

2.4 變異

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

3 結束語

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

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

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

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

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

[4] 王曉倩,陳定觀,林禮區(qū).高校實驗教學排課系統(tǒng)的設計與開發(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

（責任編輯：季平）