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

吳　瓊

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

?

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

吳瓊

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

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

文獻(xiàn)標(biāo)識(shí)碼：A

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

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

1排課問(wèn)題

1.1　排課問(wèn)題數(shù)學(xué)描述

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

1.2　約束條件

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

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

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

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

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

(R5)上課班級(jí)的學(xué)生數(shù)應(yīng)少于或等于教室容量；

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

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

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

1.3　教學(xué)效果好評(píng)度分析

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

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

表2　上課周次教學(xué)效果好評(píng)度表

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

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

綜上分析，將教學(xué)效果好評(píng)度作為排課問(wèn)題的優(yōu)化目標(biāo)，構(gòu)建排課問(wèn)題優(yōu)化模型：

(1)

約束條件R1—R7.

式(1)中，目標(biāo)函數(shù)中的Fmax為多種排課方案中教學(xué)效果好評(píng)度最大化對(duì)應(yīng)的排課方案.

2混合遺傳算法

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

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

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

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

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

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

(2)

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

2.3　遺傳算子操作

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

(3)

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

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

(4)

(5)

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

2.4　沖突檢測(cè)與消除操作

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

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

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

3) i=1， j=1.

4)判斷TC(i,j)與TC(i,j+1)的教師編號(hào)是否相同.若相同，令I(lǐng)′=(1~20的任一隨機(jī)整數(shù))，再將TC(i,j+1)和TC(I′,j+1)教師編號(hào)調(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)；若相等，完成沖突檢測(cè)與消除.

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

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

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

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

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

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

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

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

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

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

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

圖2　混合遺傳算法流程圖

3實(shí)驗(yàn)數(shù)據(jù)測(cè)試及分析

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

表3　進(jìn)化代數(shù)測(cè)試對(duì)比表

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

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

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

指標(biāo)HGA算法GA算法貪婪算法蟻群算法平均耗時(shí)/s164.868175.633179.845180.329平均教學(xué)效果好評(píng)度/%91848885

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

[9]劉秋紅,寒楓,張鈺，等.基于分層的自適應(yīng)遺傳算法在UTP中的應(yīng)用研究[J].貴州大學(xué)學(xué)報(bào)(自然科學(xué)版),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

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

作者簡(jiǎn)介：吳瓊(1979—)，男，講師，研究方向?yàn)榫W(wǎng)絡(luò)技術(shù)與智能優(yōu)化算法.

收稿日期：2015-07-25