基于遺傳算法的課程表中教師編碼的優(yōu)化

陳娟 韓娜

1 山西大學(xué)商務(wù)學(xué)院 山西 030031

2 黑龍江科技學(xué)院 黑龍江 150027

0 引言

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

1 排課研究

在排課的過程中，最關(guān)鍵是要編排一張科學(xué)性和技術(shù)性強(qiáng)的周課程表。但在這一過程中有許多制約因素及沖突。

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

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

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

（3）在同一時(shí)間給一個(gè)班級(jí)安排多門課程或在多個(gè)教室上課。

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

這些沖突是排課過程中必須要解決的，所以要對(duì)沖突問題做透徹分析和適當(dāng)處理是算法設(shè)計(jì)的基礎(chǔ)。

2 遺傳算法在課程表中的應(yīng)用

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

2.1 設(shè)計(jì)思想

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

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

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

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

（4）計(jì)算適應(yīng)度值：按照適應(yīng)度函數(shù)計(jì)算適應(yīng)度值。

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

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

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

（8）沖突檢測和消除：經(jīng)過雜交和變異操作后，可能會(huì)產(chǎn)生沖突，因此要進(jìn)行沖突檢測，并解決沖突。

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

2.2 構(gòu)造基因編碼和染色體

實(shí)施遺傳算法的第一步，就是把與求解目標(biāo)相關(guān)的實(shí)際參數(shù)進(jìn)行基因編碼，這是算法的關(guān)鍵與難點(diǎn)。

2.2.1 混合式教師編碼

遺傳算法能否順利實(shí)現(xiàn)的關(guān)鍵是構(gòu)造合適的基因結(jié)構(gòu)。設(shè)定混合式的教師編碼作為本系統(tǒng)遺傳算法的“基因”?；驑?gòu)成規(guī)則為：教師名㈩教學(xué)班序號(hào)㈩課程序號(hào)。課程特點(diǎn)，分別對(duì)應(yīng)的位寬為：6+1+1+3共11位。

（1）教師姓名

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

（2）教學(xué)班序

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

（3）課程序號(hào)

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

（4）課程特點(diǎn)

為了解決“特定資源”沖突問題，可在教師編碼中加上三個(gè)字符表示該教師所教授的課程的特點(diǎn)。每一門課程都有其各自不同的特點(diǎn)，比如上機(jī)課需要在機(jī)房上課，英語口語需要在語音室上課。另外，有的教師可能因?yàn)槟承┰蛐枰囟ǖ慕虒W(xué)時(shí)段。因此，給每一門課程對(duì)應(yīng)的教師編碼中補(bǔ)充了三位表示課程特點(diǎn)的代碼。

2.2.2 染色體的表示

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

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

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

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

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

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

（4）“種群”：由ZQS個(gè)個(gè)體構(gòu)成。其中ZQS為種群大小。

2.3 產(chǎn)生初始種群

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

2.4 解決沖突問題

解決沖突問題是計(jì)算機(jī)自動(dòng)排課的一個(gè)難點(diǎn)，在課程表的編排過程中必須完全避免如下沖突。

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

（2）對(duì)于同一時(shí)間，一個(gè)班級(jí)同時(shí)上一門以上課程的沖突，在編碼的過程中己經(jīng)避免，不會(huì)發(fā)生。

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

圖1 課程表結(jié)構(gòu)

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

3 小結(jié)

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

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

[2]竇煜明.教務(wù)管理信息系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].山東大學(xué).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].科學(xué)出版社.1998.

[6]余建橋.預(yù)測模型獲取的遺傳算法研究[J].計(jì)算機(jī)科學(xué).1998.

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

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

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