基于改進(jìn)遺傳算法排課系統(tǒng)應(yīng)用研究

馬小姝 李芙蓉

摘要：針對(duì)復(fù)雜的排課問(wèn)題，結(jié)合高校實(shí)際排課需求，本文將排課問(wèn)題抽象成一個(gè)計(jì)算機(jī)可以求解的多約束多目標(biāo)組合優(yōu)化問(wèn)題。建立排課問(wèn)題數(shù)學(xué)模型，引入遺傳算法，提出一種改進(jìn)的算法方案來(lái)求解排課問(wèn)題。同時(shí)，設(shè)計(jì)了染色體編碼和適應(yīng)度函數(shù)，采用自適應(yīng)參數(shù)調(diào)整的交叉概率和變異概率，討論了遺傳算法在排課系統(tǒng)中的應(yīng)用，并采用Matlab工具進(jìn)行仿真實(shí)驗(yàn)。仿真結(jié)果表明，改進(jìn)遺傳算法平均適應(yīng)度值高于傳統(tǒng)遺傳算法平均適應(yīng)度值，收斂性好，提高了全局搜索能力，與傳統(tǒng)的遺傳算法相比，能更有效的解決高校排課問(wèn)題。該研究可以較好地解決排課問(wèn)題。

關(guān)鍵詞：遺傳算法; 排課問(wèn)題; 多目標(biāo)優(yōu)化; 數(shù)學(xué)模型; 適應(yīng)度函數(shù); 自適應(yīng)參數(shù)

中圖分類號(hào)： TP311.52; G642.0??文獻(xiàn)標(biāo)識(shí)碼： A

收稿日期： 20200114; 修回日期： 20200225

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61461046）;甘肅省教育廳創(chuàng)新能力提升項(xiàng)目（2019B129）;甘肅省天水師范學(xué)院中青年教師科研資助項(xiàng)目（YB201702）

作者簡(jiǎn)介：馬小姝（1979），女，甘肅天水人，碩士，講師，主要研究方向?yàn)橹悄苄畔⑻幚怼?Email： maxiaoshu2013@163.com

隨著信息技術(shù)的不斷發(fā)展和教育改革的不斷深入，利用信息技術(shù)實(shí)現(xiàn)智能化的教學(xué)管理在高校越來(lái)越有必要[1]。對(duì)于高校教學(xué)管理工作，合理的課程安排能充分體現(xiàn)一個(gè)學(xué)校的教學(xué)管理水平。近年來(lái)，由于國(guó)家大力投資教育事業(yè)，高等院校的招生規(guī)模不斷擴(kuò)大，學(xué)生數(shù)量不斷增加，因此如何高效利用有限的教學(xué)資源解決排課問(wèn)題，在教學(xué)管理工作中尤為重要。對(duì)于復(fù)雜的排課問(wèn)題，國(guó)內(nèi)外許多學(xué)者進(jìn)行了研究，S.Even等人[23]證明了排課問(wèn)題是一個(gè)多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題（nondeterministic polynomial complete，NP），是一個(gè)多約束多目標(biāo)的組合優(yōu)化問(wèn)題。對(duì)于算法的研究，早期提出了整數(shù)規(guī)劃算法[4]、圖論法[5]和啟發(fā)式算法[67]，但運(yùn)用比較多的是遺傳算法[810]、模擬退火算法[1112]和蟻群算法[1314]等方法。目前，遺傳算法因具有并行搜索能力，可以重點(diǎn)集中搜索性能高的部分，在解決排課問(wèn)題上得到了廣泛的應(yīng)用[1517]，雖然其效率較高[18]，但容易出現(xiàn)局部最優(yōu)解的早熟現(xiàn)象，具有較大的改進(jìn)空間。因此，本文在注重傳統(tǒng)遺傳算法的基礎(chǔ)上，提出了改進(jìn)的排課算法，建立了排課問(wèn)題數(shù)學(xué)模型，并進(jìn)行了仿真驗(yàn)證。與傳統(tǒng)的遺傳算法相比，本研究有效的解決了高校排課問(wèn)題，提高了高校的教學(xué)管理水平。

1?遺傳算法

遺傳算法（genetic algorithm，GA）是J.H.Holland于1975年提出[19]，受生物進(jìn)化論的啟發(fā)，是一種模擬生物進(jìn)化機(jī)制的隨機(jī)搜索自適應(yīng)算法。對(duì)所研究的問(wèn)題先進(jìn)行染色體編碼，形成初始種群。按照自然界進(jìn)化法則迭代進(jìn)化，產(chǎn)生最優(yōu)個(gè)體，得到問(wèn)題最優(yōu)解[20]。在迭代過(guò)程中，借助交叉算子和變異算子生成下一代種群個(gè)體，每次新生成的子代種群個(gè)體具有更高的適應(yīng)度值，經(jīng)過(guò)多次迭代進(jìn)化，最終解逐步接近最優(yōu)解，收斂到最適應(yīng)環(huán)境的個(gè)體，對(duì)最優(yōu)個(gè)體進(jìn)行編碼，即可認(rèn)為近似最優(yōu)解。

2?排課問(wèn)題

要實(shí)現(xiàn)課程的合理安排，生成合理的課程表，就要在合理分配教學(xué)資源的前提條件下，將班級(jí)、課程、教室、教師安排在一周內(nèi)的某一時(shí)間段內(nèi)而不發(fā)生任何沖突，還要考慮在排課過(guò)程中出現(xiàn)的各種影響排課的因素，包括課程因素、教室因素、班級(jí)因素、教師因素等，根據(jù)這些因素的重要性，可理解成排課過(guò)程中需要考慮的約束條件，分為硬約束和軟約束兩類。

2.1?硬約束條件

硬約束條件是指必須要滿足的條件，其受資源的限制，一般包括以下幾點(diǎn)：

1）?一個(gè)時(shí)間單元內(nèi)，一位教師只能講授一門(mén)課程。

2）?一個(gè)時(shí)間單元內(nèi)，一個(gè)教室只能安排一門(mén)課程。

3）?同一時(shí)間單元，一個(gè)班級(jí)只能安排一門(mén)課程。

4）?每個(gè)教室的座位數(shù)都應(yīng)滿足在此教室上課的班級(jí)人數(shù)。

5）?每門(mén)課程的課時(shí)總量應(yīng)嚴(yán)格按照教學(xué)計(jì)劃規(guī)定。

6）?對(duì)于特殊崗位的教師，某些時(shí)間段不能排課。

7）?需要特殊時(shí)間安排的課程，必須安排在預(yù)訂的時(shí)間段內(nèi)。

2.2?軟約束條件

軟約束條件是課表優(yōu)化的方向，滿足效果較佳，是不滿足也不會(huì)產(chǎn)生影響的條件，根據(jù)我校實(shí)際情況，一般包括以下幾點(diǎn)：

1）?一門(mén)課程在一周內(nèi)的安排時(shí)間盡量分散，不要連續(xù)。

2）?黃金時(shí)段盡量安排高難度的專業(yè)課程。

3）?盡量避免一個(gè)班級(jí)全天空課和滿課的情況。

4）?教學(xué)資源要盡可能的充分利用，對(duì)于采用專用教室的特殊課程，盡最大可能安排。

5）?盡量避免同一門(mén)課程在一天時(shí)間內(nèi)多次授課。

6）?考慮老師的特殊情況，安排是否需要連排課時(shí)。

由于每所學(xué)校都有各自的實(shí)際情況，軟硬約束條件不盡相同，其界定相對(duì)困難。因此，只要在定義約束范圍內(nèi)，給出一個(gè)新的遺傳算法，對(duì)此問(wèn)題進(jìn)行優(yōu)化處理。

3?建立排課問(wèn)題數(shù)學(xué)模型

3.1?數(shù)學(xué)模型描述

排課問(wèn)題中，會(huì)涉及課程、教師、教室、班級(jí)和時(shí)間5個(gè)因素，對(duì)5個(gè)因素分別進(jìn)行如下數(shù)學(xué)描述：

時(shí)間段集合為T(mén)={T1，T2，…，Tnt}。

課程集合為M={M1，M2，…，Mnm}，{z1，z2，…，znm}為每門(mén)課程開(kāi)課班級(jí)數(shù)。

式中，βi表示每位教師的滿意度權(quán)值;m為教師總數(shù)。

4）?教室利用率。由于教室的人數(shù)容量有限，首先要考慮教室容納的人數(shù)和上課學(xué)生的人數(shù)，如果學(xué)生人數(shù)與教室可容納人數(shù)之比越大，說(shuō)明此教室的利用率就越高，其值小于等于1。教室利用率為

f4=1r∑ri=1kcyr（4）

式中，kc表示班級(jí)對(duì)應(yīng)人數(shù);yr表示教室可容納的人數(shù)。

對(duì)求得的適應(yīng)度函數(shù)值進(jìn)行修正，即

f=f+f-favgfmax-fminf

式中，favg表示種群個(gè)體適應(yīng)度函數(shù)值的平均值;fmax表示最大適應(yīng)度函數(shù)值;fmin表示最小適應(yīng)度函數(shù)值。

4.3?初始種群

采用隨機(jī)生成方式產(chǎn)生初始種群，但種群中也會(huì)產(chǎn)生一些不滿足排課模型硬約束條件的個(gè)體。本文方法是對(duì)初始種群中的個(gè)體逐一進(jìn)行篩選，將不能滿足硬約束條件的個(gè)體丟棄，并重新生成新個(gè)體。反復(fù)操作，使其初始種群中的個(gè)體都盡可能的滿足硬約束條件。

4.4?選擇操作

選擇操作經(jīng)常使用的方法是輪盤(pán)賭選擇算法，從上一代種群中選出適應(yīng)度值較高的個(gè)體，并將其放到配對(duì)池中，剔除適應(yīng)度值較低的個(gè)體，保留適應(yīng)度值較高的個(gè)體，形成新的種群，從而進(jìn)行下一步交叉、變異操作。本文在采用輪盤(pán)賭選擇算法的基礎(chǔ)上進(jìn)行改進(jìn)，選擇個(gè)體進(jìn)入下一代種群的概率為

pi=fi/∑Mi=1fi

式中，fi為個(gè)體適應(yīng)度值;M為種群大小。

當(dāng)每次產(chǎn)生N個(gè)隨機(jī)數(shù)后，再?gòu)闹羞x擇一個(gè)個(gè)體，并不是產(chǎn)生一個(gè)隨機(jī)數(shù)就選中一個(gè)個(gè)體，這樣循環(huán)M次后會(huì)產(chǎn)生M個(gè)個(gè)體，可以保證每次都能選擇最高適應(yīng)度值的個(gè)體，提高下一代種群個(gè)體的更優(yōu)性。

4.5?交叉和變異操作

交叉操作是利用交叉算子得到新一代個(gè)體，將種群內(nèi)兩個(gè)個(gè)體根據(jù)交叉概率隨機(jī)交換其部分基因，產(chǎn)生新的基因組合，構(gòu)成新個(gè)體。通過(guò)交叉操作，可提高算法的搜索能力，是生成新個(gè)體的主要方法，通常有單點(diǎn)交叉、多點(diǎn)交叉等方法。變異操作可以使局部搜索范圍增加，提高算法局部搜索能力，依據(jù)變異概率，將個(gè)體中的某些基因組進(jìn)行替換，形成新個(gè)體，是產(chǎn)生新個(gè)體的輔助方法，保持了種群的多樣性。交叉概率pc的值決定了種群的空間搜索區(qū)域，但如果pc取值太大，會(huì)破壞個(gè)體的優(yōu)良特征;若取值太小，也會(huì)使最優(yōu)解出現(xiàn)過(guò)早的收斂。變異概率pm的取值保持了種群的多樣性，但是pm過(guò)大，會(huì)使算法變成隨機(jī)搜索算法，取值過(guò)小時(shí)也可避免某種單個(gè)基因的丟失。本文引入一種改進(jìn)的自適應(yīng)調(diào)節(jié)思想，使交叉概率和變異概率隨迭代情況和個(gè)體適應(yīng)度函數(shù)值進(jìn)行自我調(diào)整更新?；趐c的變化，當(dāng)pc增大時(shí)，pm減小;當(dāng)pc減小時(shí)，pm增大，這樣可以使交叉和變異操作共同保證了遺傳算法的全局搜索能力。

交叉概率為

pc=k1-（k1-k2）（f′-favg）fmax-favg， f′≥favgk1， f′

變異概率為

pm=k3-（k3-k4）（f-favg）fmax-favg， f≥favgk3， f

式中，fmax是種群最大個(gè)體適應(yīng)度值;favg為種群個(gè)體平均適應(yīng)度值;f′為要交叉的兩個(gè)個(gè)體中較大個(gè)體的適應(yīng)度值;f為變異個(gè)體的適應(yīng)度值;0

交叉操作，本文采用一種混合雜交算子的方法，利用交叉概率pc在種群中選取兩個(gè)父代個(gè)體x=（x1，x2，…，xm）∈[L，U]，y=（y1，y2，…，yn）∈[L，U]，兩個(gè)雜交點(diǎn)i1和i2進(jìn)行兩點(diǎn)凸雜交，得到兩個(gè)子代個(gè)體分別為

x′=（x1，…，xi1-1，x′i1，yi1+1，…，yi2-1，x′i2，xi2+1，…，xm）

y′=（y1，…，yi1-1，y′i1，xi1+1，…，xi2-1，y′i2，yi2+1，…，ym）

其中

x′i1=axi1+（1-a）yi1，x′i2=axi2+（1-b）yi2

y′i1=ayi1+（1-a）xi1，y′i2=ayi2+（1-b）xi2

式中，[L，U]={（x1，x2，…，xm）|li≤xi≤ui，i=1，2，…，m}表示可行解空間;a和b是[0，1]中的隨機(jī)數(shù)，反復(fù)操作，得到后代集合。交叉操作獲得的子代個(gè)體方法和傳統(tǒng)遺傳算法相比，在進(jìn)化前期可以提高進(jìn)化速度。變異操作，根據(jù)變異概率，隨機(jī)選取排課方案中的兩列，并將其交換，判斷是否滿足各約束條件，如發(fā)生沖突，則再次隨機(jī)選擇交換，直到不沖突為止，產(chǎn)生一個(gè)新個(gè)體。

4.6?算法描述

Step1?隨機(jī)生成初始種群p（t），令t=0。

Step2?計(jì)算當(dāng)前種群中個(gè)體適應(yīng)度函數(shù)值，并加以修正。

Step3?根據(jù)個(gè)體適應(yīng)度值及輪盤(pán)賭選擇算法進(jìn)行選擇操作。

Step4?進(jìn)行交叉、變異操作，產(chǎn)生新的種群p（t+1），并且t=t+1。

Step5?若t

5?仿真實(shí)驗(yàn)

采用Matlab工具進(jìn)行仿真實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)為15個(gè)班級(jí)，20間教室，26名教師，46門(mén)課程，每周上課的時(shí)間單元為25個(gè)，每個(gè)時(shí)間單元為2 h。設(shè)置初始種群個(gè)體數(shù)為40個(gè)，取參數(shù)k1=09，k2=06，k3=01，k4=001，進(jìn)化代數(shù)最大為1000。分別采用傳統(tǒng)遺傳算法和改進(jìn)遺傳算法迭代1000代，每進(jìn)化100代記錄一次種群最佳適應(yīng)度值，做15次實(shí)驗(yàn)，這樣每隔100代進(jìn)化會(huì)記錄到15個(gè)最佳適應(yīng)度值數(shù)據(jù)，取平均值作為實(shí)驗(yàn)結(jié)果，改進(jìn)遺傳算法與傳統(tǒng)遺傳算法對(duì)比如圖1所示，由圖1可以看出，改進(jìn)遺傳算法平均適應(yīng)度值高于傳統(tǒng)遺傳算法平均適應(yīng)度值，收斂性好，本文排課算法對(duì)解決排課問(wèn)題效果較好。

6?結(jié)束語(yǔ)

本文建立了排課問(wèn)題數(shù)學(xué)模型，引入改進(jìn)的遺傳算法求解排課問(wèn)題，設(shè)計(jì)了算法的改進(jìn)方案。仿真結(jié)果表明，該算法能夠在一定程度上解決排課問(wèn)題，提高了算法的收斂速度和尋找最優(yōu)解的能力，但排課沖突率還有待降低。下一步研究還需對(duì)各個(gè)約束條件進(jìn)行細(xì)化，根據(jù)學(xué)校特定的教學(xué)資源環(huán)境，完善算法自動(dòng)化，排出相對(duì)優(yōu)化的課表。

參考文獻(xiàn)：

[1]?潘以鋒. 高校智能排課系統(tǒng)的算法[J]. 上海師范大學(xué)學(xué)報(bào)： 自然科學(xué)版， 2006， 35（5）： 3137.

[2]?Even S， Itai A， Shamir A. On the complexity of timetable and multicommodity flow problems[J]. SIAM Journal of Computing， 1976， 5（4）： 691703.

[3]?Carter M W， Tovey C A. When is the classroom assignment problem hard？[J]. Operations Research， 1992， 40（S1）： 2839.

[4]?McClure R H， Wells C E. A mathematical programming model for faculty course assignment[J]. Decision Sciences， 2007， 15（3）： 409420.

[5]?de Werra D. An introduction to timetabling[J]. European Journal of Operational， 1985， 19（2）： 151162.

[6]?Junginger W. Timetabling in germanya survey[J]. Interfaces， 1986， 16（4）： 6674.

[7]?Lee Y， Chen ChuenYih. A heuristic for the train pathing and timetabling problem[J]. Transportation Research Part B： Methodological， 2009， 43（8/9）： 837851.

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

[9]?任子武， 傘冶. 自適應(yīng)遺傳算法的改進(jìn)及在系統(tǒng)辨識(shí)中應(yīng)用研究[J]. 系統(tǒng)仿真學(xué)報(bào)， 2006， 18（1）： 4143， 66.

[10]?楊從銳， 錢(qián)謙， 王鋒， 等. 改進(jìn)的自適應(yīng)遺傳算法在函數(shù)優(yōu)化中的應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用研究， 2018（4）： 10421045.

[11]?Liu Y K， Zhang D F， Leung S C H. A simulated annealing algorithm with a new neighborhood structure for the timetabling problem[C]∥Genetic and Evolutionary Computation Conterence， GEC Summit 2009， Shanghai， China： GEC， 2009.

[12]?朱顥東， 鐘勇. 一種改進(jìn)的模擬退火算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展， 2009， 19（6）： 3235.

[13]?孟曉琳. 蟻群算法的研究及其應(yīng)用[D]. 成都： 西南交通大學(xué)， 2015.

[14]?Lee hsinyun. A decision support system for exposition timetabling using ant colony optimization[J]. Intenational Journal of Information Technology & Decision Making， 2012， 11（3）： 609626.

[15]?賀毅朝， 王熙照， 李文斌， 等. 基于遺傳算法求解折扣{01}背包問(wèn)題的研究[J]. 計(jì)算機(jī)學(xué)報(bào)， 2016， 39（12）： 26142630.

[16]?李紅嬋， 朱顥東. 基于小生境遺傳算法的排課問(wèn)題研究[J]. 計(jì)算機(jī)工程， 2011， 37（16）： 194196.

[17]?張赫男， 張紹文. 采用改進(jìn)的混合遺傳算法求解高校排課問(wèn)題[J]. 計(jì)算機(jī)工程與應(yīng)用， 2015， 51（5）： 240246.

[18]?馬玉芳， 張海娜， 邵杰. 遺傳算法在高校排課系統(tǒng)中研究與實(shí)現(xiàn)[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2014， 23（5）： 112115.

[19]?Holland J H. Adapatation in natural and artificial systems[J]. The University of Michigan Press， Ann Arbor， 1975（1）： 2124.

[20]?姜婧， 白似雪. 遺傳算法的改進(jìn)及其在排課問(wèn)題中的應(yīng)用[J]. 南昌大學(xué)學(xué)報(bào)： 理科版， 2018（4）： 388392.

[21]?龔程， 陳高云， 劉胤田， 等. 基于改進(jìn)型遺傳算法求解高校排課問(wèn)題[J]. 軟件工程， 2018， 21（3）： 14.

Design of Course Scheduling System Based on Improved Genetic Algorithm

MA Xiaoshu， LI Furong

（School of Electronic Information and Electrical Engineering， Tianshui Normal University， Tianshui 741000， China）

Abstract： ?Aiming at the complicated problem of course arrangement， combining with the actual demand of course arrangement in colleges and universities， this paper abstracts the problem of course arrangement into a multiobjective combination optimization problem which can be solved by computer. The mathematical model of scheduling problem is established， and genetic algorithm is introduced to solve the scheduling problem. At the same time， the chromosome coding and fitness function are designed， and the crossover probability and mutation probability are adjusted by adaptive parameters. The application of genetic algorithm in the course arrangement system is discussed， and the simulation experiment is carried out with Matlab. The simulation results show that the average fitness value of the improved genetic algorithm is higher than the average fitness value of the traditional genetic algorithm， which has good convergence and improves the global search ability. Compared with the traditional genetic algorithm， it can solve the problem of university course arrangement more effectively. This research can solve the problem of course arrangement.

Key words： genetic algorithm; timetabling problem; multiobjective optimization; mathematical model; fitness function; adaptive parameter