陳娟 韓娜

1 山西大學商務學院 山西 030031

2 黑龍江科技學院 黑龍江 150027

0 引言

排課算法設計的優(yōu)劣是評價教務管理水平高低的一個重要標志之一。目前排課的算法有很多種，比較常用的有遺傳算法、貪心算法、回溯算法等。排課問題是一個有約束的、多目標的組合優(yōu)化問題。針對排課這個NP完全類問題進行深入的分析，研究科學排課需要遵循的原則以及所涉及的各種因素、問題，總結排課過程中所出現(xiàn)的各種時間、空間資源的沖突。本文根據(jù)課程表編排的特點，以實現(xiàn)時間和空間兩種資源的優(yōu)化為目標采用魯棒性較好的遺傳算法。針對遺傳算法的收斂性較低的問題，對遺傳算法進行了優(yōu)化，構造了混合式的教師基因編碼，該算法能夠有效降低排課沖突。

1 排課研究

在排課的過程中，最關鍵是要編排一張科學性和技術性強的周課程表。但在這一過程中有許多制約因素及沖突。

在課程表編排問題中涉及到教師、班級、時間、教師、課程這五個相互制約的因素。排課問題的求解過程是，對任何一門課來說，要有一個合適的教師和合理的時間、教室以及班級與之對應，并且兩兩之間不能發(fā)生沖突，同時盡量滿足實際需求。如：

（1）在同一時間給一個教師安排多個班級課程(合班除外)或同時講授多門課程。

（2）在同一時間給一個教室安排多個班級上課(合班除外)或多位教師授課。

（3）在同一時間給一個班級安排多門課程或在多個教室上課。

（4）安排教室時，教室容納人數(shù)小于實際上課人數(shù)。

這些沖突是排課過程中必須要解決的，所以要對沖突問題做透徹分析和適當處理是算法設計的基礎。

2 遺傳算法在課程表中的應用

遺傳算法(Genetic Algorithm)是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型。該算法按照“優(yōu)勝劣汰、適者生存”的原則，通過快速隨機搜索力求找到最優(yōu)解或次優(yōu)解。遺傳算法因在解決各類非線性問題時表現(xiàn)出的魯棒性、全局最優(yōu)性、可并行處理性及高效率而深受廣大軟件開發(fā)愛好者喜愛。

2.1 設計思想

把課程和教師當作同一變量考慮，這樣在編排課程表時只需將教師編碼排入周課表。要打印課程表時，將教師編碼改為課程名和教師姓名即可。設計步驟如下：

（1）教師編碼：對每一門課程的任課教師進行編碼。在教師編碼中，每一門課程和授課教師姓名共同組合，以便于解決：“多課頭”問題，“一師多班”沖突問題，“特別課”問題，“特定資源”沖突問題，“固定時段”問題。即：在教師編碼中盡可能的把課程表的各種類型沖突解決掉。

（2）產生初始種群：使用數(shù)據(jù)表文件存放一個個體，其中記錄行由班級名稱和15個時間片字段所組成。這15個時間片字段的值將填入教師的編碼，稱為“基因”；一條記錄行代表一個班級的課表，稱為“染色體”；N個染色體組成的二維表格，稱為“個體”；多個“個體”表組成“種群”(ZQ)。在個體表中，行表示每個班級的一周上課課程，用列表示該班的 T1-T15時間片。對每一班級的課表來說，首先把特定教學時間的教師編碼填入時間片字段中。然后使用隨機函數(shù)產生一個1-15的數(shù)，將該班的其它教師編碼填入。如產生的隨機函數(shù)對應的數(shù)組變量中已有數(shù)據(jù)，則重新分配，直到將所有教師編碼無重復地填入表中。這樣就有了一個初始的課程表。按種群的大小ZQS(班級數(shù))，產生一定數(shù)量的初始表，構成初始種群。

（3）沖突檢測和消除：對初始種群中的個體表進行沖突檢測，如存在各類沖突，“一師多班”沖突、“特定資源”沖突等，則確定沖突的行、列，然后在它的同一行找另一個隨機位置，將這兩個位置的數(shù)互換，直到沒有沖突存在。

（4）計算適應度值：按照適應度函數(shù)計算適應度值。

（5）選擇操作：按照適應度值計算選擇率和期望的選擇數(shù)，進行選擇產生下一代的種群。從選擇數(shù)的算式可知，具有較高的適應度值的父本更有可能在下一代中產生一個或多個子代。

（6）雜交操作：對已選擇好的個體兩兩配對，隨機產生一個雜交行。該行即為：某個染色體(一個班級課表)，然后將父本中的這兩行分別交換，產生二個新子代。

（7）變異操作：按概率決定變異的次數(shù)。對參與變異的個體隨機選一行(某班課表)，在該行隨機生成兩個變異的位置，然后將這兩個位置的教師編碼互換。注意：當這兩個編碼中至少有一個是固定教學時段碼時，則取消本次交換，重新執(zhí)行步驟7，直到交換完成。

（8）沖突檢測和消除：經過雜交和變異操作后，可能會產生沖突，因此要進行沖突檢測，并解決沖突。

這樣經過一次遺傳算法迭代步驟，新一代種群的適應度值可能有所提高，問題的解決朝著最優(yōu)解的方向前進了一步，只要將這個過程一直進行下去，最終將逼近全局最優(yōu)解，而每一步的操作卻是非常的簡單，而且對問題的依賴性小。

2.2 構造基因編碼和染色體

實施遺傳算法的第一步，就是把與求解目標相關的實際參數(shù)進行基因編碼，這是算法的關鍵與難點。

2.2.1 混合式教師編碼

遺傳算法能否順利實現(xiàn)的關鍵是構造合適的基因結構。設定混合式的教師編碼作為本系統(tǒng)遺傳算法的“基因”?；驑嫵梢?guī)則為：教師名㈩教學班序號㈩課程序號。課程特點，分別對應的位寬為：6+1+1+3共11位。

（1）教師姓名

由于教師在課表的構成元素中占據(jù)核心的地位，為使算法直觀與簡單化，故直接使用了教師的姓名在教師編碼中，如張三、李四等，教師名取6位，不足6位用空格補足，超過6位則截取前6位字符。同名的教師必須給予區(qū)分。

（2）教學班序

為了解決“一師多班”問題，在教師名后加上一位自然數(shù)表示該教師的教學班序號，如用1表示該教師所教學的第一個班級，用2表示該教師所教學的第二個班級，依次類推。

（3）課程序號

為了解決“多課頭”問題，在教師編碼中加上一位自然數(shù)表示該教師的課程序號，如用1表示該教師所教授的第一門課程，用2表示該教師所教授的第二門課程，依次類推。

（4）課程特點

為了解決“特定資源”沖突問題，可在教師編碼中加上三個字符表示該教師所教授的課程的特點。每一門課程都有其各自不同的特點，比如上機課需要在機房上課，英語口語需要在語音室上課。另外，有的教師可能因為某些原因需要特定的教學時段。因此，給每一門課程對應的教師編碼中補充了三位表示課程特點的代碼。

2.2.2 染色體的表示

對于每一門課程既可能只上一次(規(guī)定 2學時課占用一個時間片)，也可能上多次，如4學時、6學時等。上2學時課時，該教師編碼只能出現(xiàn)1次，上4學時課時該教師編碼出現(xiàn)2次，依次類推。

通過以上特點把班級與教室等同、課程與教師和功能室(機房、語音室等)等同的處理后，原課表的五要素(班級、教室、課程、時間、教師)轉化為三要素(班級、課程、時間)。

為了更好地闡述排課遺傳算法，定義排課遺傳算法名詞。

（1）“基因”：混合型的教師編碼，即T-T15時間片中的值。

（2）“染色體”：班級名稱與Tl-T15中的“基因”組成的串。

（3）“個體”：由BJS個染色體組合而成的二維數(shù)據(jù)表，即對應于一張課表。其中BJS為參與課表編排的班級總數(shù)。

（4）“種群”：由ZQS個個體構成。其中ZQS為種群大小。

2.3 產生初始種群

每一個“染色體”都是班級的一個課表，是數(shù)據(jù)庫KCB(課程表)表中的一條記錄行。首先把固定教學時間的教師編碼填入該行中，然后使用隨機函數(shù)產生一個 1～15的數(shù)，將該班的其它教師編碼填入其中。如產生的隨機數(shù)對應的時間片中己有數(shù)據(jù)，則重新產生，直到將所有教師編碼無重復地填入該行中。這樣就有了一條染色體。如此循環(huán)BJS次，產生了與班級數(shù)目對等的染色體數(shù)目。于是，一個初始個體便產生了。按種群規(guī)模的大小ZQS，產生一定數(shù)量的個體，每個個體都存放到一個序編號的表中，由這些個體組成初始種群。很明顯，由上述方式產生的個體通常含大量的沖突。

2.4 解決沖突問題

解決沖突問題是計算機自動排課的一個難點，在課程表的編排過程中必須完全避免如下沖突。

（1）對于同一時間，一個教師同時上一門以上課程的沖突，系統(tǒng)檢測在課程表的每一列(即同一時間片)是否有相同的教師名(教師編碼中的前6位字符)。如有，則消除沖突。

（2）對于同一時間，一個班級同時上一門以上課程的沖突，在編碼的過程中己經避免，不會發(fā)生。

（3）對于同一時間，一個教室同時上一門以上課程的沖突，在編碼的過程中己經避免，也不會發(fā)生。

圖1 課程表結構

（4）對于同一時間，一個實驗室(計算機房、語音室等)同時有一個以上的班級上課的沖突，系統(tǒng)比較同一時間片是否有多個上機或上語音課的班級，即檢測在課程表的每一列(即同一時間片)是否有相同的課程特點代碼，如有，則消除沖突。課程表編排后，如圖1。

3 小結

本文深入研究了科學編排課表所需要遵循的原則以及所涉及的各種因素與問題，給出了排課遺傳算法的基因、染色體、個體、種群的概念，其中詳細描述了“教師編碼”基因結構，進而完成算法實現(xiàn)的關鍵步驟。

[1]陳誼,楊怡等.基于優(yōu)先級自動排課算法 APSA的設計與實現(xiàn)[D].2008.

[2]竇煜明.教務管理信息系統(tǒng)的設計與實現(xiàn)[D].山東大學.2008.

[3]Peter Brucker.Scheduling Algorithm.Berlin etc:Springer.1998.

[4]J.H.Holland,Adaptation in natural and artificial systems[M].Ann arbor:University of Michigen press.1975.

[5]劉勇,康立山,陳毓屏.非數(shù)值并行算法-遺傳算法[M].科學出版社.1998.

[6]余建橋.預測模型獲取的遺傳算法研究[J].計算機科學.1998.

[7]王小平,曹立明.遺傳算法-理論、應用與軟件實現(xiàn)[M].西安交通大學出版社.2005.

[8]張宗華,張偉,趙霖.利用遺傳算法實現(xiàn)交通信號燈的控制[J].計算機科學.2002.

[9]田奕,劉濤,李國杰.求解可滿足性問題的一種高效遺傳算法[J].模式識別與人工智能.1996.