采用改進的混合遺傳算法求解高校排課問題

張赫男，張紹文

北京林業大學 經濟管理學院，北京 100083

1 引言

排課問題是一個在教育機構中廣泛存在的問題，能否有效地解決排課問題將直接關系到教學質量的好壞。近年來，隨著高校的擴招，學生的數量日益增多，并且隨著社會的發展，專業和課程的種類也都在與日俱增。在這樣的環境下，教師和教室等資源顯得愈發緊張。因此，一個有效的課程安排已經成為教師、學生以及學校管理人員的共同訴求。

排課問題是一種多約束和多目標的組合優化問題，它已被證明是一個NP難問題[1-2]。國內外的學者已經提出了一些解決排課問題的方法。早期的解決方法主要有直接啟發式方法[3]，圖著色法[4-5]，整數線性規劃法[6-8]，網絡流法[9-10]，這些方法能夠解決問題的規模都很有限。隨著計算機技術的發展，尤其是20世紀90年代以來，越來越多的智能算法被應用于解決排課問題，如遺傳算法[11-13]，模擬退火算法[14]，禁忌搜索算法[15]，以及多種智能算法相結合的混合算法[16-17]。這些算法都能在一定程度上解決排課問題，但也存在著一些不足：（1）考慮的約束條件不夠全面，如對合班的情況考慮比較少[18-19]；（2）目標函數僅僅取決于約束條件被違反的次數，并沒有考慮到不同課程的重要程度以及不同時間段具有不同的教學效果等[13，18]。本文針對這些不足之處提出了改進的方法。

遺傳算法具有自組織、自適應和自學習性，不需要其他的輔助知識，只需要影響搜索方向的目標函數和相適應的適應度函數[20]；遺傳算法進行的是全空間的并行搜索，并將搜索重點集中于性能高的部分，從而能夠提高效率，而且不容易陷入局部最優[21]。遺傳算法采用的是群體并行搜索，局部搜索能力較差；而模擬退火算法采用的是串行優化結構，全局搜索能力較弱。二者的結合能夠互相增強和補充進化的能力[21]。因此，本文將遺傳算法與模擬退火算法相結合，用以解決高校排課問題。

2 高校排課問題分析及數學建模

2.1 問題描述

排課問題是一種資源分配問題，是要將班級，課程，教師，時間和教室等要素進行合理的安排，在滿足各種約束條件的前提下，使目標函數盡量達到最優。不管是學生，教師，還是管理人員，都傾向于同一門課程在同一學期內固定在同一個教室，因此本文沒有考慮周次的概念，而是重點研究了課程安排最為密集的一周，若這周的課程可以得到合理的安排，則其他周次的課程安排只須在該周的基礎上做一定的刪減。

2.2 相關術語

小班：以專業名稱、年級和班級編號確定下來的班級，例如“會計10-1”表示會計專業10級1班。

班級：在同一時間同一地點學習同一科目的小班的集合，可以只由一個小班組成，也可以由多個小班組成。

科目：一名固定的教師和一個固定的班級所對應的課程。若存在不同的班級或不同的教師對應名稱相同的科目，則在原始數據預處理過程中通過修改科目名稱和賦予不同的編號作為區分。一個班級可以對應多門科目，但一門科目只能對應一個班級。

時間段：以每一節課時長45 min為例，在現實的教學中，一般都是2～4節課連在一起進行教學，如上午1～2節，上午1～4節，等等。根據這個特點，將每天的教學時間劃分為5個時間段，上午1～2節為第1個時間段，上午3～4節為第2個時間段，以此類推。若是3節課連在一起，如下午2～4節，則等同于下午要占用2個時間段，因為在這種情況下，下午的第1節已無法再安排其他課程。由于晚上一般最多只會安排一個科目，因此把晚上的教學時間記為每天的第5個時間段。

2.3 數據結構和變量

本文對變量的命名采用“屬性+類”的方式，變量名中排在后面的單詞首字母要大寫，以便于閱讀。若變量為一個元素，則首字母小寫；若變量為一個集合，則首字母大寫。如表示教師i的編號的變量命名為idTeacheri，表示班級j要學習課程的編號集合的變量命名為IdSubjectClassj。

原始數據包括以下4個表：

（1）配置表（CONFIG）：每天的時間段數nbPeriodDay=5，每周上課的天數nbDayWeek=5。可以計算出每周的總時間段數nbPeriodWeek=nbPeriodDay×nbDayWeek=25， 每周所有時間段的集合PeriodWeek={1，2，…，nbPeriodWeek}。

（2）教室表（ROOM）：共有nbRoom個教室，教室i對應的編號和容量分別為idRoomi和capacityRoomi。

（3）科目表（SUBJECT）：共有nbSubject門科目，科目i對應的編號、學分和每周的課次分別為idSubjecti，creditSubjecti和nbPeriodSubjecti。

（4）小班表（SMALLCLASS）：共有nbSmallclass個小班，小班i對應的編號和人數分別為idSmallclassi和sizeSmallclassi。

通過Access與Matlab混合編程，生成建模和求解所需要的其他數據，包括以下2個表：

（1）班級表（CLASS）：共有nbClass個班級，班級i對應的編號、包含的小班的編號集合、總人數、科目的編號集合、每周的課次分別為idClassi，IdSmallclassClassi，sizeClassi，IdSubjectClassi和nbPeriodClassi。

（2）教師表（TEACHER）：共有nbTeacher名教師，教師i對應的編號和科目的編號集合分別為idTeacheri和IdSubjectTeacheri。

2.4 硬約束條件

硬約束指的是必須被滿足的、符合客觀邏輯的約束[22]。本文考慮了4個硬約束條件：

（1）同一時間，同一班級最多只能有一門課程。

（2）同一時間，同一教師最多只能有一門課程。

（3）同一時間，同一教室最多只能有一門課程。

（4）教室的容量不小于在該教室上課的班級的總人數。

硬約束是否被滿足決定了排課方案是否可行。

2.5 軟約束條件

軟約束指的是在客觀上可以被違反，但會影響到教學質量的約束[22]。本文考慮了4個軟約束條件：

（1）重要的課程應盡量安排在教學效果更好的時間段。

（2）對于同一個班級的同一門課程，若每周的課次較多，則應盡量避免安排在同一天。

（3）對于每一個班級，要在考慮到課程重要程度的前提下盡量把課程均勻安排在每一天，避免出現某天重要性較高的課程過多或某天重要性較低的課程過少的情況。

（4）盡量實現班級人數與教室容量的匹配，以提高教室的利用率。

2.6 目標函數

目標函數的優劣由軟約束的滿足情況決定，軟約束被滿足的情況越好，目標函數越優。本文的目標函數是對各個軟約束條件被滿足情況的綜合評價。

（1）時間段安排效果

對于小班i，找出所有跟該小班有關的科目的學分以及時間段的安排，評價函數如下：

其中weightPeriodm表示第m個時間段的權重值。將每天的第1、3和5個時間段的權重值設置為1，每天的第2和4個時間段的權重值設置為0.5。課程的重要程度直接用學分的大小來衡量。

（2）同一課程應盡量避免安排在同一天

記小班i的課程安排總體效果為f2Smallclassi，初始值為0。對于小班i的科目j，計算該科目每周一共有多少課次。本文一共有3種情況。

①科目j每周只有1課次。則對該科目有f2Smallclassi=f2Smallclassi+2。

②科目j每周共有2課次。分別計算出2個課次對應的是一周的哪一天，并轉化為對應的數字，如周一為1，周二為2。用較大數減去較小數。評價方法如表1所示。

表1 每周共有2課次的科目的評價方法

③科目j每周共有3課次。分別計算出3個課次對應的是一周的哪一天，轉化為對應的數字并從小到大排列。對相鄰的兩個數，用較大數減去較小數，得到兩個差值。評價方法如表2所示。

表2 每周共有3課次的科目的評價方法

（3）同一小班的課程應盡量均勻安排在每一天

對于小班i，統計該班一周內每天的課次數，計算出標準差，標準差的值越小，安排的效果越好。評價函數如下：

若標準差為0，則將f3Smallclassi賦值為3。

（4）教室的利用率

計算所有已有安排的教室的平均利用率。評價函數如下：

則總的評價函數為：

這種評價方式可以進一步擴大科目數量更多、科目重要程度更高、每周總課次更多的小班在目標函數中所占的比重，使這些小班在排課過程中具有更高的優先級。以該函數作為本文混合遺傳算法的適應度函數，函數值越大，解就越優。

3 高校排課問題的混合遺傳算法設計

3.1 編碼方法

排課問題是要把各個班級、科目和教師安排在合理的時間和地點，即時間段和教室。建立以每周總時間段數nbPeriodWeek為行數，以教室總數nbRoom為列數的二維矩陣，矩陣中的每一個非空位置的元素都包含了三個變量：班級編號，科目編號和教師編號。沒有元素的位置則表示該時間段的該教室沒有安排。采用這種編碼方式可以直接滿足第三個硬約束條件）。編碼方法如圖1所示。

3.2 初始種群的產生

每一個初始可行解即為初始種群中的一個個體。每一個可行解的產生過程如圖2所示。

圖1 編碼方法

圖2 可行解的產生過程

按照本文產生可行解的方法，若先安排每周課次較多的班級，由于解空間被過早壓縮，容易導致后面的班級無法被安排，即無法產生可行解。因此在進行排課之前，先把各個班級按照每周課次從小到大的順序進行排序，這樣就避免了解空間的過早壓縮，能夠很快地產生可行解。

如果在每次產生可行解的過程中班級的順序都固定不變，那么不同的可行解之間難免會具有一定的相似性，這樣就使得遺傳算法容易陷入局部最優解，不利于全局的搜索。因此，有必要進行一定的亂序處理，使不同的個體之間具有比較大的差異，這樣才能使遺傳算法能夠在范圍更大的解空間內進行搜索，以找到全局最優解。

本文采取的亂序處理有兩個步驟。首先，在各個班級按照每周課次從小到大的順序進行排序后，把每周課次相同的班級分為一組，在組內進行隨機的重新排序。如圖3和圖4所示。

圖3 亂序處理前的班級編號

圖4 亂序處理后的班級編號

然后，對于每個班級的所有科目，在排課過程中也進行隨機的重新排序，如圖5所示。

圖5 科目的亂序處理

3.3 選擇算子

本文的選擇算子引入了保留最優個體策略，即適應度最高的個體直接進入下一代，其余進入下一代的個體通過賭輪盤法選出。對種群中的每個個體進行評價，適應度越高的個體越有可能進入下一代種群。把個體i的適應度記為fi，則該個體進入下一代種群的概率為：

其中nbIndividual為一代種群中個體的數量。

3.4 交叉算子

每個可行解都是在滿足了許多約束條件的情況下產生的，若交叉操作的規模較大，則產生的子代很容易是一個非可行解，因此本文采用了兩點交叉操作。此外，為了保證交叉操作對解的改進作用，本文還引入了競爭機制。具體操作過程如下。

（1）對于兩個將要進行交叉操作的個體父代1（個體i）和父代2，找出它們對應的矩陣中都有安排、且坐標相同、且對應的科目編號不同的位置，把這些位置作為交叉操作的候選位置。

（2）從候選位置中隨機選出一個位置，記父代1和父代2在該位置對應的元素分別為元素1和元素2，交換該位置的元素1和元素2。則父代1中了多了一個元素2，少了一個元素1；父代2中多了一個元素1，少了一個元素2。從父代1中找出其他位置的元素2，放入集合1；從父代2中找出其他位置的元素1，放入集合2。從集合1中任選一個元素2，從集合2中任選一個元素1，將它們在兩個子代個體中的位置進行交換。交叉和修正的過程如圖6所示。

圖6 交叉操作過程

由于集合1和集合2的規模都很小，為了保證交叉操作的質量，這里采用局部遍歷的方式將集合1中的元素2和集合2中的元素1按照它們在各自集合中的次序逐個進行交換，直到某一次交叉操作產生的兩個子代個體都是可行解，則把它們與兩個父代個體都存放在集合GenerationTemp中，停止遍歷，交叉過程結束。

（3）引入競爭機制，對集合GenerationTemp中的2個父代個體和2個子代個體逐一進行評價，從中挑選出表現最好的一個，作為本次交叉操作最終得到的最優個體，進入下一代種群。

此外，為了控制運算的時間，設置了進行交叉操作的嘗試次數限制。交叉操作的流程如圖7所示。

圖7 交叉操作流程圖

3.5 變異算子

對于要進行變異的父代個體，在其矩陣中隨機選出兩行，交換這兩行的元素，產生一個新的個體。由本文的編碼方式可知，經過這種變異操作所產生的子代也是可行解。變異的過程如圖8所示。

圖8 變異操作過程

圖9 模擬退火過程

3.6 種群的進化

種群進化的流程如圖10所示。

3.7 檢查機制

為了驗證算法的可行性，本文引入了4個檢查機制：

（1）每個時間段是否有同一個班級出現在不同的教室。

（2）每個時間段是否有同一名教師出現在不同的教室。

圖10 種群進化的流程圖

（3）每個教室的容量是否不小于在此上課的班級的總人數。

（4）一個解中所有元素的個數是否等于所有班級的總課次數。

檢查結果顯示，種群中的每一個個體都滿足了所有的硬約束條件，并且沒有任何班級、教師或科目存在安排遺漏的情況。

4 實驗例證

4.1 實例數據

本文的實驗數據來自于XX大學XX學院2013—2014學年秋季課程安排，共包括79個班級（其中包括93個不同的小班），145門科目，85名教師，18間教室。

4.2 參數設置

初始種群規模nbIndividual=100，迭代次數nbIteration=180，交叉概率pc和變異概率pm采用了自適應參數設置。

其中pc1=0.9，pc2=0.6，pm1=0.2，pm2=0.02，fi為要進行交叉或變異操作個體的評價值，favg為當前種群的平均評價值，fmax為當前種群的最大評價值。

由于標準模擬退火算法需要消耗很長的時間，而本文主要是借鑒模擬退火算法的思想，因此和模擬退火算法有關的參數設置較小。初始溫度t0=100，最低溫度tmin=0.1，退火系數a=0.9，溫度下降方式為t=t×a，每個溫度下對鄰域解的搜索次數為1。

4.3 實驗結果

對于同一初始種群，分別用4種方法對其進行優化：（1）文獻[23]的改進遺傳算法，記為GA1；（2）本文所設計的遺傳算法，記為GA2；（3）全局引入模擬退火算法的遺傳算法；（4）局部（前50次迭代）引入模擬退火算法的遺傳算法。進化情況如圖11所示。

圖11 同一初始種群在不同算法下的優化效果

從圖11中可以看出，本文所設計的遺傳算法有效地避免了種群的退化，并且跳出了局部最優解，在更大的解空間內搜索到了更好的解。在引入具有跳變能力的模擬退火算法之后，搜索的效率得到了進一步的提高。由于在算法的前期應當盡量擴大搜索范圍以提高找到更優解的概率，而在中后期則應集中對局部解空間的搜索，因此本文又嘗試僅在進化前期引入模擬退火算法以增大搜索范圍，而在中后期只使用遺傳算法以加強局部搜索，進一步提高了解的質量。分別把方法（1）和（4）得到的各項評價指標進行對比，如表3所示。

表3 評價指標比較

表3中各評價項目的計算方法如下。“教學時間段的安排效果（每天第1、3和5個教學時間段）”的計算方法是：對于一周內每天的第1、3和5個教學時間段，找出在這些時間段有教學安排的所有教室，用在該教學時間段和該教室上課的班級的小班數目乘以所學習科目的學分，作為相應的科目安排效果的評價值，最后將所有教學時間段的所有教室的科目安排效果評價值相加。“科目的安排效果”的計算方法是：分別計算出每個小班的科目的安排效果，然后再取平均值。“總課次的均勻程度”的計算方法是：分別計算出每個小班在一周內每天總課次的標準差，然后再取平均值。

從表3中可以看出，每天教學效果最好的時間段，即第1，3和5個教學時間段，得到的評價值要明顯高于第2和4個教學時間段，達到了重要程度更高的科目被安排在教學效果更好的教學時間段的目的。科目的安排效果和教室利用率都得到了改進，課次的分布也更為均勻。這里的教室利用率是一個接近50%的數值，說明學生在上課時能夠基本以間隔一個位置的方式就坐，這樣學生上課的舒適度會更高。

5 結束語

對于高校排課問題，合班教學是一個廣泛存在的現象，本文針對這個特點對問題進行了數學建模，并設計了引入模擬退火算法的混合遺傳算法進行求解，使兩種算法能夠互相彌補。實驗結果表明，與一般的遺傳算法相比，本文提出的混合遺傳算法具有更高的搜索效率。

遺傳算子的方法設計并不只有一種，遺傳算法與其他智能算法的結合也有多種選擇，如何設計出合適的算子以及與更多智能算法相結合，是下一步將要研究的重點。

[1]Even S，Itai A，Shamir A.On the complexity of time table and multi-commodity flow problems[J].SIAM Journal of Computation，1976，5（4）：691-703.

[2]Carter W M，Tovey C.When is the classroom assignment problem hard?[J].Operations Research，1989，40（S1）：28-39.

[3]Junginger W.Timetabling in Germany-asurvey[J].Interface，1986，16（4）：66-74.

[4]Neufeld G A，Tartar J.Graph coloring conditions for the existence of solutions to the timetable problem[J].Communications of the ACM，1974，17（8）：450-453.

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

[6]Shih W，Sullivan J A.Dynamic course scheduling for college faculty via zero-one programming[J].Decision Sciences，1977，8（4）：711-721.

[7]McClure R H，Wells C E.A mathematical programming model for faculty course assignments[J].Decision Sciences，1984，15（3）：409-420.

[8]Tripathy A.School timetabling-a case in large binary integer linear programming[J].Management Science，1984，30（12）：1473-1489.

[9]Ostermann R，de Werra D.Some experiments with a timetabling system[J].OR Spectrum，1982，3（4）：199-204.

[10]Mulvey J M.A classroom/time assignment model[J].European Journal of Operational Research，1982，9（1）：64-70.

[11]Yu E，Sung K S.A genetic algorithm for a university weekly courses timetabling problem[J].International Transactions in Operational Research，2002，9（6）：703-717.

[12]Ueda H，Ouchi D，Takahashi K，et al.Comparisons of genetic algorithms for timetabling problems[J].Systems and Computers in Japan，2004，35（7）：1-12.

[13]Kohshori M S，Liri M S.Multi population hybrid genetic algorithms for university course timetabling[J].International Journal for Advances in Computer Science，2012，3（1）：12-22.

[14]Liu Y，Zhang D，Leung S C H.A simulated annealing algorithm with a new neighborhood structure for the timetabling problem[C]//Proceedings of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation，2009.

[15]Minh K N T T，Thanh N D T，Trang K T，et al.Using tabu search for solving a high school timetabling problem[M]//Studiesin computationalintelligence，2010：305-313.

[16]Jat S N，Yang S.A hybrid genetic algorithm and tabu search approach for post enrolment course timetabling[J].Journal of Scheduling，2011，14（6）：617-637.

[17]Chiarandini M，Birattari M，Socha K，et al.An effective hybrid algorithm foruniversity course timetabling[J].Journal of Scheduling，2006，9（5）：403-432.

[18]汪曉飛，李曉寧.GA編碼方案在高校排課系統中的應用[J].計算機工程與設計，2008，29（17）：4565-4567.

[19]李紅蟬，朱顥東.采用十進制免疫遺傳算法求解高校排課問題[J].系統工程理論與實踐，2012，32（9）：2031-2036.

[20]王小平，曹立明.遺傳算法——理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.

[21]王凌.智能優化算法及其應用[M].北京：清華大學出版社，2004.

[22]LewisR.A survey ofmetaheuristic-based techniques foruniversity timetabling problems[J].OR Spectrum，2008，30（1）：167-190.

[23]李紅蟬，朱顥東.基于最佳個體置換策略的高校排課問題求解[J].計算機工程，2011，37（19）：186-188.