馬小姝 李芙蓉

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

關鍵詞：遺傳算法; 排課問題; 多目標優(yōu)化; 數(shù)學模型; 適應度函數(shù); 自適應參數(shù)

中圖分類號： TP311.52; G642.0??文獻標識碼： A

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

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

作者簡介：馬小姝（1979），女，甘肅天水人，碩士，講師，主要研究方向為智能信息處理。 Email： maxiaoshu2013@163.com

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

1?遺傳算法

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

2?排課問題

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

2.1?硬約束條件

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

1）?一個時間單元內，一位教師只能講授一門課程。

2）?一個時間單元內，一個教室只能安排一門課程。

3）?同一時間單元，一個班級只能安排一門課程。

4）?每個教室的座位數(shù)都應滿足在此教室上課的班級人數(shù)。

5）?每門課程的課時總量應嚴格按照教學計劃規(guī)定。

6）?對于特殊崗位的教師，某些時間段不能排課。

7）?需要特殊時間安排的課程，必須安排在預訂的時間段內。

2.2?軟約束條件

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

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

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

3）?盡量避免一個班級全天空課和滿課的情況。

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

5）?盡量避免同一門課程在一天時間內多次授課。

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

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

3?建立排課問題數(shù)學模型

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

排課問題中，會涉及課程、教師、教室、班級和時間5個因素，對5個因素分別進行如下數(shù)學描述：

時間段集合為T={T1，T2，…，Tnt}。

課程集合為M={M1，M2，…，Mnm}，{z1，z2，…，znm}為每門課程開課班級數(shù)。

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

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

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

式中，kc表示班級對應人數(shù);yr表示教室可容納的人數(shù)。

對求得的適應度函數(shù)值進行修正，即

f=f+f-favgfmax-fminf

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

4.3?初始種群

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

4.4?選擇操作

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

pi=fi/∑Mi=1fi

式中，fi為個體適應度值;M為種群大小。

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

4.5?交叉和變異操作

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

交叉概率為

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

變異概率為

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

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

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

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]中的隨機數(shù)，反復操作，得到后代集合。交叉操作獲得的子代個體方法和傳統(tǒng)遺傳算法相比，在進化前期可以提高進化速度。變異操作，根據(jù)變異概率，隨機選取排課方案中的兩列，并將其交換，判斷是否滿足各約束條件，如發(fā)生沖突，則再次隨機選擇交換，直到不沖突為止，產(chǎn)生一個新個體。

4.6?算法描述

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

Step2?計算當前種群中個體適應度函數(shù)值，并加以修正。

Step3?根據(jù)個體適應度值及輪盤賭選擇算法進行選擇操作。

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

Step5?若t

5?仿真實驗

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

6?結束語

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

參考文獻：

[1]?潘以鋒. 高校智能排課系統(tǒng)的算法[J]. 上海師范大學學報： 自然科學版， 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]?王小平， 曹立明. 遺傳算法： 理論、應用與軟件實現(xiàn)[M]. 西安： 西安交通大學出版社， 2002.

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

[10]?楊從銳， 錢謙， 王鋒， 等. 改進的自適應遺傳算法在函數(shù)優(yōu)化中的應用[J]. 計算機應用研究， 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]. 計算機技術與發(fā)展， 2009， 19（6）： 3235.

[13]?孟曉琳. 蟻群算法的研究及其應用[D]. 成都： 西南交通大學， 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}背包問題的研究[J]. 計算機學報， 2016， 39（12）： 26142630.

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

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

[18]?馬玉芳， 張海娜， 邵杰. 遺傳算法在高校排課系統(tǒng)中研究與實現(xiàn)[J]. 計算機系統(tǒ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]. 南昌大學學報： 理科版， 2018（4）： 388392.

[21]?龔程， 陳高云， 劉胤田， 等. 基于改進型遺傳算法求解高校排課問題[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