吳　瓊

( 黎明職業(yè)大學 信息與電子工程學院， 福建 泉州 362000 )

?

智能排課優(yōu)化算法研究

吳瓊

( 黎明職業(yè)大學 信息與電子工程學院， 福建 泉州 362000 )

摘要：為解決高校排課優(yōu)化問題，建立了以教學效果好評度最大化為優(yōu)化目標的排課數(shù)學模型.針對傳統(tǒng)遺傳算法的不足，給出了一種混合遺傳算法，該算法不僅能夠?qū)鹘y(tǒng)遺傳算法的交叉率、變異率進行自適應改進，還能夠?qū)崿F(xiàn)沖突檢測與消除功能.測試結(jié)果表明，該算法比傳統(tǒng)的遺傳算法、貪婪算法和蟻群算法耗時短，而且教學效果好評度最高，這說明該算法能有效縮短排課時間，提高排課質(zhì)量和效率，實現(xiàn)高校排課智能化. 高校排課； 教學效果好評度； 自適應調(diào)整； 沖突檢測與消除； 混合遺傳算法 TP391.9

文獻標識碼：A

隨著高校規(guī)模的擴大，許多高校教學資源短缺的情況日益凸顯，使得排課問題成為教務管理中較為困難的一項工作.目前，國內(nèi)高校排課還主要依賴人工操作為主，為了避免排課沖突，工作人員需反復進行調(diào)整，缺乏智能性和科學性[1]，而且工作量巨大、效率低；因此，尋求一種科學排課的智能方法，對于提高排課效率和教學效果具有重要意義.

目前國內(nèi)許多高校針對排課系統(tǒng)進行了研發(fā)，如清華大學的TISER系統(tǒng)、西北工業(yè)大學的科教排課系統(tǒng)和南京工學院的UTSS系統(tǒng).這些系統(tǒng)在一定程度上提高了排課工作的效率，但這些系統(tǒng)畢竟都是依照自身院校實際情況研發(fā)的，并不具有普遍的通用性，其他高校引入后仍需大量的人工調(diào)整.針對這些情況，本文依據(jù)排課規(guī)則，以教學效果好評度為優(yōu)化目標，構(gòu)建了排課數(shù)學模型，實現(xiàn)了排課優(yōu)化設(shè)計和排課沖突檢測與消除功能，大大減少了后期人工調(diào)整的工作量.眾所周知，排課問題即教室、課程、教師、學生、時間等多因素的組合，是一個NP組合優(yōu)化問題，解決該類問題常用的方法有遺傳算法(GA)[2-3]、貪婪算法[4]、蟻群算法[5]等智能算法，其中貪婪算法由于度量標準難以把握往往會導致難以真正實現(xiàn)智能排課，蟻群算法由于搜索時間過長，容易因較優(yōu)解的信息強化而出現(xiàn)早熟、停滯現(xiàn)象.因此，本文設(shè)計了一種混合遺傳算法(HGA)進行排課，并將其結(jié)果與遺傳算法、貪婪算法和蟻群算法進行了比較，以此驗證了本文算法的有效性和優(yōu)越性.

1排課問題

1.1　排課問題數(shù)學描述

課程-時間-教室關(guān)系如下：

1.2　約束條件

合理排課就是令教師、教室、班級、課程和時間5個因素不發(fā)生沖突，以便教學活動能正常進行.因此本文將這5個因素作為約束條件，當滿足所有約束條件時，即實現(xiàn)排課無沖突.約束條件[6]描述如下：

(R1)同一時間，1位教師只能承擔1門課程；

(R2)同一時間，1個教室只能安排1門課程；

(R3)同一時間，1個班級只能安排1門課程；

(R4)同一時間，上課的課程數(shù)應少于或等于教室數(shù)；

(R5)上課班級的學生數(shù)應少于或等于教室容量；

(R6)將1天分為上午2個、下午和晚上各1個共4個教學時間段，1周5天為19個時間段(星期三下午空置)，1個時間段至少有1個班級有課；

(R7)同一班級所上同一門課程時間安排起碼應有1天的間隔；同一班級同一個半天教室安排應盡量接近；同一教師同一個半天教室安排應盡量接近；每一個班級周課時應盡量均衡等.

上述約束條件中，R1—R5為硬約束條件，R6為算法有解保證，R7為軟約束條件.

1.3　教學效果好評度分析

由于師生的個人喜好、學生對知識的接受能力和記憶強弱等原因，不同的授課時間會造成教學效果的差異，即教學效果好評度[7].通過對某校師生進行調(diào)查后，獲得了不同節(jié)次、不同周次對應的教學效果好評度表，如表1和表2所示.

表1　上課節(jié)次教學效果好評度表

表2　上課周次教學效果好評度表

注：表2中，周次(一、一)上課時間為周一搭配周一，以此類推.

1.4　排課問題數(shù)學模型的建立

綜上分析，將教學效果好評度作為排課問題的優(yōu)化目標，構(gòu)建排課問題優(yōu)化模型：

(1)

約束條件R1—R7.

式(1)中，目標函數(shù)中的Fmax為多種排課方案中教學效果好評度最大化對應的排課方案.

2混合遺傳算法

遺傳算法是一種搜索啟發(fā)式算法，它不受問題本身的限制，僅在目標函數(shù)的準則下進行全局自適應搜索，其強大的魯棒性非常適合求解如排課這種NP的數(shù)學問題最優(yōu)解，但傳統(tǒng)的遺傳算法在NP問題的求解過程中容易因早熟而導致局部收斂.為了解決這一問題，本文在傳統(tǒng)遺傳算法的基礎(chǔ)上對交叉率和變異率進行了改進和優(yōu)化[8]，使其具有自適應調(diào)整功能，從而獲得全局最優(yōu)解.

2.1　初始種群和編碼設(shè)置

傳統(tǒng)遺傳算法的初始種群通常是采用隨機方式產(chǎn)生，所生成的初始種群存在分布不均勻、優(yōu)化性能不好等問題；因此,本文采用歸一化方法對初始種群進行處理，保證其解盡可能均勻地分布于解空間，以避免早熟現(xiàn)象，從而能有效地獲得全局最優(yōu)解.選擇十進制編碼，生成一條共18位的染色體，如圖1所示.染色體5102-0018-3105-0400-52包含的信息為：工號為5102的教師給編號為0018的班級上代碼為3105的課程，上課地點為編號0400的教室，上課時間為周五的第2個時間段(即上午3、4節(jié)).

圖1　排課表染色體基因組成結(jié)構(gòu)圖

2.2　適值函數(shù)的確定

在遺傳算法的進化過程中，個體的適值大小將決定其是否會被淘汰，通過合理設(shè)置適值函數(shù)[9]可有效避免算法過早收斂，獲得全局最優(yōu).鑒于排課問題是一個多目標優(yōu)化數(shù)學問題，本文的適值函數(shù)的設(shè)計思路是將多目標優(yōu)化和適值函數(shù)相結(jié)合，構(gòu)建基于各目標值的貢獻大小分配對應權(quán)值的個體適值函數(shù)，則適值函數(shù)為：

(2)

式(2)中fi為各影響因素的教學效果好評度， ai為各影響因素對應加權(quán)值.適值F(x)越大，則說明課表編排越合理.

2.3　遺傳算子操作

1)選擇.基于適者生存的進化機制，在已生成的種群群體中，通過對個體的適值進行評價，將適值較高的個體選擇出來并將其優(yōu)秀的基因通過交叉變異操作遺傳至下一代.假設(shè)排課種群規(guī)模為N， 各個個體對應的適值為fi， 采用輪盤賭選法，則個體被選中的概率為：

(3)

由式(3)可看出，適值越高的染色個體被選中的機會越大.

2)帶自適應功能的交叉和變異.從種群中隨機抽取2個父代染色個體，對其一部分進行交叉組合操作，使其重組產(chǎn)生更為優(yōu)秀的2個子代染色個體插入新群體中.變異操作是在對種群中的個體基因進行變異以獲得更為優(yōu)秀的染色個體.由于交叉概率Pc和變異概率Pm決定后代個體的多樣性，為提高搜索能力，避免局部最優(yōu)解產(chǎn)生，本文對傳統(tǒng)交叉、變異操作進行了改進，設(shè)置了自適應調(diào)整的交叉率和變異率，以此提高算法的全局最優(yōu)性.具體設(shè)置為：

(4)

(5)

式(4)和式(5)中fmax為最大適值， favg為平均適值， f為父代染色個體中適值較大的個體.當父代適值高于平均適值時，應減小當前交叉率和變異率，以保證擁有優(yōu)秀基因的染色個體能夠順利進入子代；當父代適值低于平均適值時，保持當前交叉率和變異率.

2.4　沖突檢測與消除操作

當生成的種群解不滿足排課約束條件時，會導致課表安排不合理，即出現(xiàn)課表沖突現(xiàn)象，如同一時間同一班級上2門課程；因此，需對每代新生產(chǎn)的種群進行沖突檢測，并及時對存在的沖突進行處理.以同一時間一位教師教授2門(含2門)以上課程為例，其沖突檢測與消除實現(xiàn)步驟如下：

1)將19個時間段與n門課程信息編制為一個二維數(shù)組課表TC，行為時間，列為課程，形成19×n個單元格.

2)將在染色體信息中提取的對應時間-課程信息，在二維數(shù)組表中找到對應單元格后填入教師編號.

3) i=1， j=1.

4)判斷TC(i,j)與TC(i,j+1)的教師編號是否相同.若相同，令I(lǐng)′=(1~20的任一隨機整數(shù))，再將TC(i,j+1)和TC(I′,j+1)教師編號調(diào)換，跳轉(zhuǎn)4);若不相同， j=j+1， 跳轉(zhuǎn)5).

5)判斷j等于n否，若不相等，跳轉(zhuǎn)4)；若相等，令i=i+1， 跳轉(zhuǎn)6).

6)判斷i等于20否，若不相等，跳轉(zhuǎn)4)；若相等，完成沖突檢測與消除.

2.5　混合遺傳算法的實現(xiàn)步驟

混合遺傳算法的實現(xiàn)步驟為：

1)初始化參數(shù).將種群規(guī)模設(shè)置為100，設(shè)定變異概率Pm初值為0.07，交叉概率Pc初值為0.95；

2)十進制編碼，生成初始種群，做歸一化、沖突檢測和消除處理后，根據(jù)式(2)計算初始種群各個個體的適值作為個體評價依據(jù)；

3)遺傳操作.基于輪盤賭選法原理，根據(jù)式(3)計算選擇概率Pi并進行選擇操作；

4)對交叉概率Pc和變異概率Pm進行自適應調(diào)整.若當前子代個體適值大于平均適值，則根據(jù)式(4)和式(5)調(diào)整Pc和Pm，否則保持Pc和Pm不變；

5)以交叉概率Pc和變異概率Pm進行交叉變異操作生成子代種群，進行染色體沖突檢測和消除操作；

6)計算各個個體的適值，若子代個體適值大于父代個體適值，則采取替換操作，否則保持父代個體；

7)重復步驟3)—步驟6)，直至滿足算法終止條件；

8)輸出最優(yōu)解.

混合遺傳算法流程圖如圖2所示.

圖2　混合遺傳算法流程圖

3實驗數(shù)據(jù)測試及分析

以黎明職業(yè)大學排課為例，測試數(shù)據(jù)為：106名教師、4 400名學生、88個班級、129間教室和324門課程.算法最大進化代數(shù)設(shè)置為100~500，各自進行20次測試后取平均值，其結(jié)果如表3所示.

表3　進化代數(shù)測試對比表

由表3可看出:進化代數(shù)由300增加到500時，其最優(yōu)適值并無明顯改善,且當進化代數(shù)為300時，其計算耗時僅為400代所需耗時的68.3%， 500代的51.9%；其運行次數(shù)僅為400代運行次數(shù)的70.2%， 500代的53.6%.從運行耗時和次數(shù)的節(jié)約考慮，本文將進化代數(shù)設(shè)置為300.

由圖3可以看出，函數(shù)在前100代上升迅速，約在150代后趨于穩(wěn)定，并達到函數(shù)最佳適值，由此說明混合遺傳算法具有快速收斂性，其解收斂于全局最優(yōu)解.表4為混合遺傳算法(HGA)、傳統(tǒng)遺傳算法(GA)、貪婪算法和蟻群算法的優(yōu)化結(jié)果.

圖3　適值與進化代數(shù)關(guān)系曲線圖

指標HGA算法GA算法貪婪算法蟻群算法平均耗時/s164.868175.633179.845180.329平均教學效果好評度/%91848885

由表4優(yōu)化結(jié)果可知：采用混合遺傳算法進行排課，其計算時間比傳統(tǒng)遺傳算法節(jié)省了6.53%，比貪婪算法節(jié)省了9.08%，比蟻群算法節(jié)省了9.38%;優(yōu)化后的教學效果好評度比傳統(tǒng)遺傳算法高7.7%，比貪婪算法高3.3%，比蟻群算法高6.6%.這說明了本文提出的混合算法的合理性和優(yōu)越性.此外，在排課中，當涉及的班級、教師和課程等數(shù)量越多時，其優(yōu)化效果會更加明顯.

4結(jié)束語

本文以教學效果好評度最大化為優(yōu)化目標，構(gòu)建了高校排課優(yōu)化設(shè)計數(shù)學模型，并提供了一種將自適應調(diào)整功能融入交叉變異操作的混合遺傳算法.該算法既提高了算法搜索能力和全局最優(yōu)性，還實現(xiàn)了課表沖突檢測與消除功能.測試結(jié)果表明，該混合算法可獲得較高的教學效果好評度，節(jié)省排課耗時時間，很好地提高排課的效率及質(zhì)量，具有較好的實際應用意義.本文獲得的測試結(jié)果并未涵蓋本校所有的排課資源，下一步的研究內(nèi)容應全面覆蓋所有排課數(shù)據(jù)以及嘗試與其他智能算法進行結(jié)合以進一步改進和完善本文算法.

參考文獻：

[1]孫丹瑩.高校排課問題與算法分析[J].信息與電腦,2012,10:210-211.

[2]鐘耀廣,劉群鋒.基于遺傳算法的高校排課數(shù)學模型[J].東莞理工學院學報,2012,10(19):4-8.

[3]陳行平,陳江,陳啟華.基于遺傳算法的高校排課系統(tǒng)設(shè)計[J].紹興文理學院學報,2004,34(20):25-28.

[4]趙耀鋒.基于貪婪算法的多媒體教室排課算法設(shè)計[J].信息技術(shù),2013,13:80-82.

[5]何小虎.一種改進蟻群算法在排課中的應用研究[J].電子設(shè)計工程,2012,8(20):28-29.

[6]宗薇.高校智能排課系統(tǒng)算法的研究與實現(xiàn)[J].計算機仿真,2011,28(12):389-392.

[7]范文廣.基于遺傳算法的排課設(shè)計[J].齊齊哈爾大學學報,2011,27(5):27-29.

[8]劉化龍,胡釙,青志明.基于混合遺傳算法的變壓器局部放電超聲定位法[J].蘭州理工大學學報,2014,12(40):105-109.

[9]劉秋紅,寒楓,張鈺，等.基于分層的自適應遺傳算法在UTP中的應用研究[J].貴州大學學報(自然科學版),2007,24(2):184-187.

Research of optimization algorithm for course timetabling problem

WU Qiong

(CollegeofInformationandElectronicsEngineering,LimingUniversity,Quanzhou362000,China)

Abstract：In order to solve the problem of university course timetabling, a mathematic model was established based on the objective function of maximum teaching effect praise degree. Aiming at the shortcoming of traditional genetic algorithm, a hybrid genetic algorithm which combined with self-adaptive crossover and mutation were put forward. The conflict detection and elimination function were realized. The test result show that hybrid algorithm was faster than traditional genetic algorithm, greedy algorithm and ant colony algorithm but the highest teaching effect praise degree. It proved that the algorithm shorten the time consuming, improve the quality and implementation the intelligence of course timetabling effectively.

Keywords：university course timetabling; teaching effect praise degree; self-adaptive adjustment; hybrid genetic algorithm; hybrid genetic algorithm

文章編號：1004-4353(2015)04-0331-06

作者簡介：吳瓊(1979—)，男，講師，研究方向為網(wǎng)絡技術(shù)與智能優(yōu)化算法.

收稿日期：2015-07-25