基于遺傳算法的高職學(xué)院排課系統(tǒng)設(shè)計(jì)研究

朱良學(xué)

(酒泉職業(yè)技術(shù)學(xué)院，甘肅 酒泉 735000)

一、高職排課問題描述

排課因素主要包括：(授課)時間、(授課)班級、(所授)課程、(授課)教師、(授課)地點(diǎn)。排課主要就是解決這幾個資源在排列組合中可能發(fā)生的矛盾和沖突，找到一組不發(fā)生沖突的較優(yōu)合理搭配。

二、排課問題數(shù)學(xué)描述[1，2]

將排課問題所涉及的資源做如下表示：

C表示課程(course)集合{c1,c2,,,cK}；

T表示教師(teacher)集合{ t1, t2,,, tA}；

R表示教室(room)集合{r1,r2,,,rC};

N表示時間集合{n1,n2,,,,nd};

S表示班級集合{s1,s2,,,sf}。

這樣排課問題就變成一個5元組CTRNS=(C，T，R，N，S)，排課的目標(biāo)就是找出滿足約束條件的(C，T，R，N，S)組合。排課要滿足的約束條件通常我們歸納為硬約束條件和軟約束條件兩大類:硬約束條件指排課過程中必須滿足的要求，軟約束條件通常包括排課過程中需考慮的經(jīng)驗(yàn)、常識、特殊情況等。

排課問題的硬約束條件至少有以下幾個方面的考慮：

第一， 除選修課外，一個班級在同一時間只能有一門課；

第二，一個教師在同一時間段只能有一門課；

第三，一個教室(實(shí)訓(xùn)室)在同一時間段只能有一門課；

第四，一個教師所上的多門課程必須排在不同時間段；

第五，同一時間段準(zhǔn)備的上課教室數(shù)應(yīng)大于上課班級數(shù)。

通常軟約束條件有以下考慮：

同一門課程的上課時間盡量間隔合理：也就是一周上多節(jié)的課程,各次課之間應(yīng)該有合理的時間間隔；學(xué)生上課時間要盡量選擇最適宜的上課時間片：也就是盡量將課程安排在最適合上該門課的時間段；適當(dāng)考慮某些教師的特殊情況；各班級課表要盡量避免某些天滿課,某些天少課或無課的情況發(fā)生。

三、以往手工排課過程[3]

按照J(rèn)職院的排課習(xí)慣，學(xué)期伊始，教學(xué)干事會根據(jù)某班級的教學(xué)任務(wù),先選取較難安排(或需優(yōu)先安排)的課程,根據(jù)課程的周課時安排該門課在每周上課的節(jié)次，在教師課表和教室課表中選取相應(yīng)的公共空閑時間。當(dāng)然這個過程需要不斷地回溯、反復(fù)調(diào)整，達(dá)到期望的排課效果。

當(dāng)排課量巨大時,便會出現(xiàn)沖突,反復(fù)回溯、調(diào)整,直到所有課程全部排完。所以，排課工作十分繁復(fù)，以J職院來說，近百個專業(yè)，一萬多名學(xué)生，六百多名教師，幾百門課程，教師、教室等資源日趨緊張，要實(shí)現(xiàn)合理、較優(yōu)排課，工作量、難度之大可想而知。

四、遺傳算法思想

綜上所述，由于排課問題的高度復(fù)雜性，特別是硬約束、軟約束條件下要達(dá)到較優(yōu)排課目標(biāo)時，傳統(tǒng)算法很難較好解決問題。大量研究人員對排課問題進(jìn)行了探索，常用的方法包括貪婪算法、回溯法、圖論法等等[4～6]。遺傳算法以其思想簡潔，解決問題思路清晰，搜索效率簡捷高效，成為解決排課問題的一種重要方法[7]。

遺傳算法(Genetic Algorithm, GA)在1975年被美國數(shù)學(xué)家JohnHolland率先提出，仿照生物界物種選擇和進(jìn)化原理，將問題轉(zhuǎn)化為遺傳編碼，將含問題解的種群作為解空間，設(shè)計(jì)適應(yīng)度函數(shù)對每個解進(jìn)行篩選；以概率論為基礎(chǔ)，在解空間進(jìn)行隨機(jī)搜索，最終一步步找到問題的最優(yōu)解；是一種具有高度并行性的隨機(jī)搜索算法。

在遺傳算法中，類比來說，染色體可以看作給定問題的解，染色體構(gòu)成的個體集合為初始種群；一個個體是問題的一個解，有多個個體組成的種群是問題的一組解。根據(jù)遺傳進(jìn)化原理，將當(dāng)前種群中個體適應(yīng)度較大的個體作為優(yōu)秀個體，設(shè)計(jì)選擇、變異、交叉等算子對個體進(jìn)行操作，不斷篩選掉適應(yīng)度小的個體，種群的適應(yīng)度不斷提高；這樣就使種群中的個體得到更新，整個種群不斷演化，持續(xù)衍生出新一代更為優(yōu)秀(即適應(yīng)度值更大)的種群；在演化過程中，由適應(yīng)度函數(shù)來評定個體的優(yōu)劣，當(dāng)最優(yōu)個體的適應(yīng)度達(dá)到給定的閾值，算法終止。如此，經(jīng)過若干代的演進(jìn)之后，最后得到的一個種群將是適應(yīng)度最優(yōu)之種群，也即最后一代種群就包含著問題的最優(yōu)解。

五、遺傳算法的高職排課系統(tǒng)設(shè)計(jì)

(一)排課問題向遺傳算法的轉(zhuǎn)化

要用遺傳算法思想解決排課問題，就必須將排課問題轉(zhuǎn)化為遺傳算法能處理的對應(yīng)問題。遺傳算法最基本的概念即是基因，進(jìn)化就是發(fā)生在基因?yàn)榛A(chǔ)的個體上的。所以如何將課表轉(zhuǎn)化為基因是實(shí)現(xiàn)利用遺傳算法解決排課問題的首要問題。這一過程通常稱之為編碼。編碼后，基因、個體、種群就構(gòu)成了遺傳算法解決排課問題的解空間。

排課問題向遺傳算法的對應(yīng)轉(zhuǎn)化如下:

1.基因

根據(jù)學(xué)院的實(shí)際排課情況，設(shè)定基因的組合形式如下 ：

教師工號課程代碼班級代碼教室編號課程周課時課程類型

基因編碼中包含了排課的主要因素：教師信息(誰上課)，課程信息(上什么課)，班級信息(在哪個班級上課)，教室信息(在哪兒上課)；教師上多少節(jié)次課程就產(chǎn)生多少條這樣的基因。再者，基因編碼中盡可能把課程表的各種沖突因素包含其中。課程周課時指該門課程每周占用幾個節(jié)次，教師每上一個節(jié)次就會對應(yīng)一個基因編碼。課程類型一般指該門課程的特別情況，如該門課有何特別要求等等。

2.染色體

染色體的構(gòu)成規(guī)則如下：基因+班級名稱+時間片?；蛉缟纤荆瑫r間片指學(xué)院課程時間安排的如下情形：學(xué)院正常上課5天，每天5個時間段:

第1時段:上午1、2節(jié), 8∶00-9∶40;

第2時段:上午3、4節(jié),10∶00-11∶40

第3時段:下午5、6節(jié), 15∶00-16∶40;

第4時段:下午7、8節(jié), 17∶00-18∶40;

第5時段:下午9、10節(jié), 19∶30-21∶10;

一般第5時段排課較少，主要排形勢政策課等等。這樣每天有5個時間段(T1-T5),每周5天共有25個時間段(T1-T25)。25個時間段構(gòu)成時間片。

這樣每一個“染色體”對應(yīng)的其實(shí)是班級的一個課表，即一個染色體就是一個班級課表。整個課表就是這一個個班級課表就構(gòu)成的。

3. “個體”

有多個染色體構(gòu)成個體；有多少個班級就有多少個染色體；所以一個個體對應(yīng)的其實(shí)就是一張完整課表，它包含了所有班級課表。

4. 種群

有多個個體構(gòu)成種群。所以種群包含了多種可能排課課表的情形。

5.初始種群產(chǎn)生

先產(chǎn)生染色體，這類同于排一個班級的初始課表，按照學(xué)院人工排課的習(xí)慣，為了減少沖突，應(yīng)先排固定時段的教師課程，因?yàn)樗麄冎挥羞@個時間段可以排課上課；然后再次第排其他教師的課程。相應(yīng)的做法就是：先在固定教學(xué)時段填入含對應(yīng)教師的基因編碼，再將含該班其他教師的基因編碼逐次填入隨機(jī)產(chǎn)生的相異時間段。如是直到所有含該班授課教師信息的基因編碼填寫完成。如此就生成了一個該班的初始課表。顯然，這樣的課表將來必然隱含大量的沖突。

有多少個班級就這樣生成多少個班級初始課表；所有班級初始課表就組成了完整排課課表，也即生成了一個遺傳個體。

設(shè)定一個種群數(shù)，按這個數(shù)生成一定數(shù)量的遺傳個體，就形成初始種群；它包含了所有可能的排課情形。

(二)基于遺傳算法的排課系統(tǒng)算法設(shè)計(jì)

1. 檢測和消除沖突

由于在做編碼設(shè)計(jì)時已經(jīng)考慮到硬約束條件的因素，由此可能導(dǎo)致的沖突將不會發(fā)生；我們只需對每個教師在同一時間段上一門以上課程的沖突進(jìn)行檢測和消除就可以了。

2.適應(yīng)度函數(shù)設(shè)計(jì)

根據(jù)J職院教學(xué)實(shí)際情況，考慮了以下3個因素：課程安排是否太集中或分散；課程安排的上課時間段是否合理或高效；上課地點(diǎn)或設(shè)備對學(xué)生上課的影響。

第一，課程安排是否太集中或分散。同一門課上課時間太集中或分散，都不利于學(xué)生學(xué)習(xí)。每周時間片共有25個時間段，兩個時間段的差值就反映了課程安排的均衡情況。每個差值賦予一個期望值，這個期望值就表示了這種均衡。

課程的均衡用

Fjh=∑Fjh(i)

(5-1)

函數(shù)表示。

第二，課程安排的上課時間段是否合理或高效。每周時間片共有25個時間段，這25個時間段中有些時間段上課效率較高，這些時間段就賦予較高的期望值。用函數(shù)

Fgx=∑Fgx(i)

(5-2)

表示課程上課時間段是否合理或高效。

第三，上課地點(diǎn)設(shè)備對學(xué)生上課的影響。J職院由于上課地點(diǎn)、設(shè)備的差異，影響了學(xué)生上課的積極性。這種差異也賦予一個期望值，用函數(shù)

Fds=∑Fds(i)

(5-3)

表示。

這樣課表適應(yīng)度函數(shù)就可以表示為：

Fit= (k1×Fjh+k2×Fgx+k3×Fds)3

(5-4)

K1,K2,K3為加權(quán)因子。

根據(jù)學(xué)校的實(shí)際情況，合理設(shè)置k1,k2,k3的值，對每一個期望值及其所占比例也要合理配置，以便使所設(shè)計(jì)的排課系統(tǒng)更加符合實(shí)際、方便高效。

3.遺傳算子設(shè)計(jì)

生成的初始種群，從生物角度來說，其個體的適應(yīng)性還處于較差的程度，表現(xiàn)在個體的適應(yīng)度函數(shù)上，其值還較小。根據(jù)生物逐代進(jìn)化的原理，下一代比上一代更適應(yīng)環(huán)境，也就是下一代比上一代有更高的適應(yīng)度函數(shù)值。遺傳算法就是依據(jù)這個原理，以適應(yīng)度函數(shù)值作為評價個體優(yōu)劣的標(biāo)準(zhǔn)，逐代優(yōu)化，一步步搜索到最優(yōu)解。

下面是遺傳算法所涉及的幾個典型算子:

(1)選擇算子(Reproduction )

根據(jù)生物界適者生存、擇優(yōu)棄劣的自然選擇法則，從種群中選擇出適應(yīng)性較好的個體，作為產(chǎn)生下一代的基礎(chǔ)。遺傳算法模仿這個原理，從種群中選擇出適應(yīng)度值較高的個體，作為染色體進(jìn)行后續(xù)運(yùn)算之基礎(chǔ)。

現(xiàn)在選擇算法比較常見的是輪盤賭方法。選擇概率計(jì)算方法為:

P1=f1/∑f

(5-5)

各個個體的選擇概率和其適應(yīng)度值成比例。選擇算子從父代個體中選出適應(yīng)度函數(shù)值最高的替代當(dāng)前子代個體適應(yīng)度函數(shù)值最低的，這樣，就從上一代種群中保留了適應(yīng)度函數(shù)值高的染色體，作為后續(xù)進(jìn)化迭代之基礎(chǔ)。

(2)交叉算子(Crossover )

通過選擇算子從上一代種群的父代個體中繼承了適應(yīng)度函數(shù)值高的染色體，但并沒有生成新的染色體。要生成新的優(yōu)秀個體，就必須增加新的操作，通常簡單有效做法是交叉操作：在配對父本中的對應(yīng)染色體之間進(jìn)行交叉。本文采用配偶對的交叉方式，只進(jìn)行單點(diǎn)交叉。

(3)變異算子(Mutation )

生物由于自然環(huán)境的變化，基因發(fā)生突變，生物學(xué)稱之為遺傳變異。遺傳算法依照這個原理，設(shè)計(jì)了變異算子。變異算子有反轉(zhuǎn)變異、插入變異、移位變異等。通過變異算子，人為改變了群體中個體的某些值，為新個體的產(chǎn)生提供機(jī)會，在隨機(jī)搜索時避免了過早收斂，也使算法增強(qiáng)了隨機(jī)搜索能力。

(4)設(shè)置控制參數(shù)

控制參數(shù)的選取對遺傳算法性能有極大影響，在后面的實(shí)驗(yàn)中可清晰看到。遺傳算法需要設(shè)置的控制參數(shù)通常有：

1)編碼長度

由于盡可能要把排課過程中包含的各種沖突因素考慮其中，編碼長度一般由問題求解結(jié)果的精確性決定。

2)種群規(guī)模

根據(jù)實(shí)際的排課要求和實(shí)驗(yàn)條件，確定種群規(guī)模的大小。但一般的情況是：種群規(guī)模太小，搜索找到最優(yōu)解的可能性就??；種群規(guī)模過大，搜索找到最優(yōu)解所花費(fèi)的時間就多，致使收斂時間增長，算法求解效率低。一般種群數(shù)目取20-160之間。

3)選擇率

根據(jù)遺傳原理，只有適應(yīng)度高的優(yōu)秀個體被延續(xù)至下一代，它的優(yōu)越性才可能保持。因此可設(shè)計(jì)下面的選擇率及選擇數(shù)計(jì)算公式:

期望的選擇率：

Px=Fit(i)/Fit

(5-6)

其中Fit(i)為其中某個個體適應(yīng)度值，F(xiàn)it為種群的適應(yīng)度值總和，i=1, 2, 3,種群數(shù)；得到的個體期望的選擇數(shù)如下:

XZ(S)=INT(Px×種群數(shù))

(5-7)

個體的適應(yīng)度值占整個種群適應(yīng)度值的比值決定了選擇數(shù)的大小。

4)交叉率

交叉操作是種群生成新個體的主要操作，交叉概率又決定了交叉操作發(fā)生的頻率；因此，交叉概率通常應(yīng)取一個合理的較大值。但若過大，會使高適應(yīng)度值的優(yōu)良結(jié)構(gòu)很快被破壞掉，太小又會使搜索停滯不前。故通常pc取0.5-1.0之間，本系統(tǒng)pc取0.8 。

5)變異率

變異概率Pm是增大種群多樣性的又一個因素，變異概率太小，不會生成新個體;變異概率太大，又會使遺傳算法變成隨機(jī)搜索。通常Pm取0.001-0.1之間。本系統(tǒng)取0.02。

6)進(jìn)化代數(shù)

當(dāng)編碼長度較長時，進(jìn)化代數(shù)要取小一些，否則會影響算法執(zhí)行效率。但取值太小，各目標(biāo)不收斂。取值較小，雖收斂但不是全局最優(yōu)。因而要取較大值。進(jìn)化代數(shù)的選取還可采用某種判定準(zhǔn)則，準(zhǔn)則成立時，即停止。

六、J職院排課實(shí)驗(yàn)結(jié)果及分析

選擇MATLAB_R2008a及其漢化包；由于實(shí)驗(yàn)條件所限，縮小排課規(guī)模至二級學(xué)院，按照J(rèn)職業(yè)技術(shù)學(xué)院機(jī)電工程學(xué)院2019一2020學(xué)年第二學(xué)期的教學(xué)計(jì)劃安排為例,進(jìn)行了模擬排課實(shí)驗(yàn)，設(shè)置的數(shù)據(jù)如下:

時段:每周上課5天,每天排5次課,總時段數(shù)為25,各時段期望值根據(jù)學(xué)院實(shí)際情況確定(這里不必列出，實(shí)驗(yàn)設(shè)置是直接填入);

教室:36個(含所有可排課的教室及計(jì)算機(jī)室);

實(shí)訓(xùn)室:12個;

教師(含外聘教師)90人;

課程:224(所有專業(yè)，所有課程);

班級:42個(每班人數(shù)最大值為50);

學(xué)生:1620人;

根據(jù)遺傳算法搜索最優(yōu)解的原理，實(shí)驗(yàn)考慮了如下幾個因素：

第一，種群規(guī)模對排課的影響：主要是參考找到最優(yōu)解所需的時間；多大的種群規(guī)模比較適中，這樣對于排課性價比比較高。因此，要找到一個適中的種群規(guī)模。

第二，交叉概率對排課的影響：交叉概率的大小影響到搜索最優(yōu)解的收斂性，值越大收斂越快，但太大會過早收斂,不能較好的進(jìn)行全局搜索。因此，要找到一個適中的交叉概率值。

第三，變異概率對排課的影響：變異概率太大,會引起遺傳算法不穩(wěn)定；變異概率太小,又會使全局搜索難于進(jìn)行。因此，要找到一個適中的變異概率值。

第四，收斂時的遺傳進(jìn)化代數(shù)。

表1 種群規(guī)模對排課的影響 時間:秒

按照習(xí)慣性的做法，種群規(guī)模暫定為50、100、150，三組進(jìn)行測試，每組實(shí)驗(yàn)記錄了6次結(jié)果；顯然，與我們對此問題的常識與預(yù)測一致，種群規(guī)模越小,找到一個合理解的時間越短。但種群規(guī)模太小在有限的遺傳代數(shù)內(nèi)無法找到最優(yōu)解。從實(shí)驗(yàn)可看出種群規(guī)模100是一個較適中的結(jié)果。

表2 交叉概率對排課的影響 時間:秒

本文對交叉概率為0.7,0.8,0.9進(jìn)行了實(shí)驗(yàn)。

從以上實(shí)驗(yàn)數(shù)據(jù)可以看出，交叉概率越大,找到一個合理解花費(fèi)的時間越少，這其實(shí)是搜索過程收斂越快。但太大會過早收斂,不能較好的進(jìn)行全局搜索。故本系統(tǒng)交叉概率pc取值0.8是一個較適中的結(jié)果。

表3 變異概率對排課的影響

變異概率太大,會引起算法不穩(wěn)定。按照遺傳常識，太大量的變異不僅不能進(jìn)化出好的個體,反而會使得每條染色體極不穩(wěn)定, 大量產(chǎn)生沖突的結(jié)果。變異概率太小,產(chǎn)生新的個體太少，全局搜索難于進(jìn)行。本文對變異概率為0.01,0.02,0.04進(jìn)行了實(shí)驗(yàn)。從實(shí)驗(yàn)結(jié)果可以看出不同的變異概率之間實(shí)驗(yàn)結(jié)果的差異。本系統(tǒng)變異概率Pm為0.02是一個較適中的結(jié)果。

表4 遺傳迭代與收斂情況

續(xù)表4

表1-4中可以看出，初始種群規(guī)模越大，得到的最優(yōu)個體的特征值也越大， 得到最優(yōu)搜索解所耗費(fèi)的時間也越多。初始種群為50時，遺傳算法的收斂在遺傳代數(shù)為320左右就基本穩(wěn)定，但特征值卻是420左右，這是由于初始種群的數(shù)量不夠充足而停止了進(jìn)化；初始種群為100 時，隨著遺傳代數(shù)的增加，染色體的特征值也逐步升高，在迭代360次左右時基本找到了最優(yōu)解442 ，而以后的32次迭代幾乎是在最優(yōu)解附近浮動；初始種群150時，在表4中可以清晰地看到當(dāng)遺傳代數(shù)到達(dá)390次時，已經(jīng)搜索到最優(yōu)解451，而其后的60次迭代基本就無必要 。通過上表數(shù)據(jù)可以看出，初始種群選擇100，遺傳代數(shù)360次，可以搜索找到最優(yōu)解 。

結(jié)論

本文較實(shí)際全面地討論了高職院校排課問題中的主要影響因素，約束條件，求解目標(biāo)；將遺傳算法與排課問題相結(jié)合，解決了排課的編碼問題，設(shè)計(jì)了簡潔有效的適應(yīng)度函數(shù)，通過排課模擬實(shí)驗(yàn)得到了種群規(guī)模、交叉概率、變異概率等因素對排課的影響；最后實(shí)驗(yàn)得到了尋求一個最優(yōu)解時收斂和迭代的情況。由此，提出了用遺傳算法求解排課問題的總體框架和思路，使高職院校排課問題得到了一種有效解決方案。