李　陽(yáng),張　欣

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院,貴州 貴陽(yáng)　550025)

?

基于改進(jìn)遺傳算法的高校排課優(yōu)化問(wèn)題研究

李陽(yáng),張欣

(貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院,貴州 貴陽(yáng)550025)

摘要針對(duì)高校排課工作量大等問(wèn)題,提出了基于改進(jìn)遺傳算法的課表優(yōu)化方案。以教學(xué)任務(wù)為基因進(jìn)行編碼,總課表(行為時(shí)間段,列為班級(jí))為DNA隨機(jī)產(chǎn)生若干個(gè)滿足強(qiáng)制規(guī)則的初始種群,將遺傳算法中的隨機(jī)交叉改進(jìn)為局部列完整交叉算法,隨機(jī)變異改進(jìn)為列內(nèi)部隨機(jī)互換算法,并通過(guò)若干代的迭代優(yōu)化,促使最終生成一個(gè)科學(xué)合理的排課方案。實(shí)驗(yàn)仿真表明,課表適應(yīng)度由最初的76.0提升至123.0,優(yōu)化效果顯著。

關(guān)鍵詞排課;優(yōu)化;改進(jìn)遺傳算法

高校排課的實(shí)質(zhì)是教務(wù)系統(tǒng)根據(jù)每個(gè)學(xué)期各個(gè)學(xué)院的教學(xué)任務(wù),給每個(gè)班級(jí)合理安排課程,任課老師,上課地點(diǎn)等。排課問(wèn)題涉及因素眾多,各個(gè)因素之間互相影響,相互制約[1]。遺傳算法是通過(guò)模擬達(dá)爾文的生物進(jìn)化規(guī)律演變而來(lái),具有高度并行、自適應(yīng)的、隨機(jī)的、全局尋優(yōu)的搜索方法[2-3]。其通過(guò)對(duì)當(dāng)前群體施加一系列的遺傳操作,從而產(chǎn)生新一代群體,促使群體進(jìn)化到接近最優(yōu)解的狀態(tài),是一類具有較強(qiáng)魯棒性的優(yōu)化算法。簡(jiǎn)單的將遺傳算法應(yīng)用到排課優(yōu)化問(wèn)題中會(huì)出現(xiàn)收斂速度慢,易產(chǎn)生無(wú)用課表等問(wèn)題[4]。本文采用改進(jìn)遺傳算法對(duì)排課問(wèn)題進(jìn)行研究。運(yùn)算時(shí)間顯著減少。

1高校排課問(wèn)題限制因素

排課問(wèn)題中的規(guī)則可分為兩大類:強(qiáng)制規(guī)則和優(yōu)化規(guī)則。強(qiáng)制規(guī)則是不可違背的,否則該課表是不可行的。優(yōu)化規(guī)則應(yīng)當(dāng)盡量滿足,滿足的優(yōu)化規(guī)則越多說(shuō)明該課表越優(yōu)秀。

強(qiáng)制規(guī)則:(1)依據(jù)教學(xué)計(jì)劃,不得隨意更改課程;(2)一個(gè)班級(jí)不能在同一時(shí)間被安排不同課程;(3)一位老師不能在同一個(gè)時(shí)間上不同課程;(4)一間課室不能在同一個(gè)時(shí)間段為兩個(gè)班級(jí)所用,除非兩個(gè)班級(jí)課程相同;(5)課室的座位數(shù)略大于等于上課的學(xué)生人數(shù)。

優(yōu)化規(guī)則:(1)一個(gè)星期之內(nèi)應(yīng)間隔排列好各門(mén)課程;(2)課程應(yīng)安排在學(xué)習(xí)效率較低時(shí);(3)難度高的課程后應(yīng)搭配難度低的課程;(4)共同科目可考慮合班上課。

優(yōu)化規(guī)則還有諸多種,具體要根據(jù)實(shí)際情況而定。

2改進(jìn)遺傳算法解決排課優(yōu)化問(wèn)題

“適者生存,優(yōu)勝劣汰”。這是遺傳算法的主要思想。遺傳算法是一種隨機(jī)的全局搜索和優(yōu)化算法[5]。其從一個(gè)種群開(kāi)始,該群種可能是問(wèn)題的一個(gè)可能潛在解集。該種群在進(jìn)化過(guò)程中,遵守“優(yōu)勝劣汰”規(guī)則。在每一次進(jìn)化開(kāi)始之前,計(jì)算當(dāng)前種群中個(gè)體的適應(yīng)度(Fitness)。種群的適應(yīng)度越高,說(shuō)明其基因越好,應(yīng)遺傳到下一代。接下來(lái),借助代表自然遺傳學(xué)的遺傳算子(Genetic Operators),不斷進(jìn)行組合交叉(Crossover)和變異(Mutation)等操作,產(chǎn)生子代(代表新的解集的種群)[6]。周而復(fù)始,適應(yīng)度低的個(gè)體被淘汰。按照這樣的步驟操作下來(lái),新生成的種群總比前一代更加優(yōu)秀。因此,經(jīng)過(guò)若干代的進(jìn)化后,最后的一個(gè)種群將是最優(yōu)種群。

遺傳算法的一般步驟如下:首先初始化一個(gè)種群,然后利用適應(yīng)度計(jì)算函數(shù)計(jì)算該種群中每個(gè)個(gè)體的適應(yīng)度,然后根據(jù)指定規(guī)則計(jì)算個(gè)體是否滿足優(yōu)化準(zhǔn)則的判定標(biāo)準(zhǔn)[7],若滿足,則算法停止,當(dāng)前種群就是最優(yōu)的種群。若不滿足,就選取適應(yīng)度高的個(gè)體,對(duì)這個(gè)種群的個(gè)體進(jìn)行遺傳操作,經(jīng)過(guò)演化后的子代種群利用已有規(guī)則,重新判定優(yōu)化準(zhǔn)則的滿足程度,從而進(jìn)化成新的種群。

本文通過(guò)改進(jìn)遺傳算法中的基因編碼方法,交叉算法中的交叉方式,變異算法中的變異方式,解決了在交叉和變異過(guò)程中產(chǎn)生不滿足強(qiáng)制條件的課表問(wèn)題。

2.1排課優(yōu)化算法與遺傳算法相對(duì)應(yīng)

基因是組成染色體的基本單元,在排課問(wèn)題中,基因應(yīng)包括:課程-教師-教室-時(shí)間段-班級(jí)信息。通過(guò)計(jì)算機(jī)排課就必須考慮編碼的問(wèn)題。好的編碼方式能大幅提高算法的效率。針對(duì)此問(wèn)題,文中采用十進(jìn)制編碼,其可更好的提升計(jì)算機(jī)的運(yùn)算效率,更小的減少內(nèi)存占用。這里采用十進(jìn)制意味著我們要將每一門(mén)課程重新編碼,以貴州大學(xué)為例:公共課外語(yǔ)(英語(yǔ))的課程編號(hào)為:10657M101,而英語(yǔ)這門(mén)課又分為上下兩個(gè)學(xué)期,上學(xué)期課程編號(hào)為10657M101-1,共十一位,其中包含數(shù)字,英文字母,特殊符號(hào)。這在后續(xù)的計(jì)算機(jī)運(yùn)算當(dāng)中會(huì)增加大量的開(kāi)銷。所以將其直接編碼為4位十進(jìn)制碼0001;教師ID由于每個(gè)學(xué)校采用的方式不統(tǒng)一,因此重新編碼可增加該系統(tǒng)的擴(kuò)展性,這里也采用4位十進(jìn)制碼。教室的編碼方式與之前有所區(qū)別,在此將最高位1表示普通教室(無(wú)多媒體),2表示普通教室(多媒體),3表示階梯教室,4表示實(shí)驗(yàn)機(jī)房,針對(duì)具體情況還可細(xì)分。后3位表示教室編號(hào)。時(shí)間段代碼采用2位十進(jìn)制,這里假設(shè)每天劃為4個(gè)時(shí)間段上課,一周上5天。即將一周劃為20個(gè)時(shí)間段,用01～20表示。班級(jí)采用4位十進(jìn)制表示,如用0022表示通信2班。然后一個(gè)基因就編為18位十進(jìn)制碼,如000100252110050022表示英語(yǔ)課編號(hào)為0025的老師授課,地點(diǎn)在多媒體教室110,上課時(shí)間是周二上午前兩小節(jié),上課班級(jí)為通信2班。至此基因編碼結(jié)束。

染色體則對(duì)應(yīng)問(wèn)題的一個(gè)可能解,是基因的綜合體。是遺傳算法操作的基本對(duì)象。在此對(duì)應(yīng)的就是一種排課方案。遺傳算法中要求隨機(jī)產(chǎn)生若干個(gè)染色體,即隨機(jī)產(chǎn)生若干個(gè)課表,但在實(shí)際中這些隨機(jī)產(chǎn)生的課表有較大一部分不滿足強(qiáng)制規(guī)則的無(wú)效課表。這些課表在后續(xù)的遺傳算法操作中已經(jīng)沒(méi)有必要。因此,這里要求進(jìn)入后續(xù)交叉變異等操作的課表都必須是有效的。之前的沖突檢測(cè)是在課表生成之后再開(kāi)始檢測(cè),若發(fā)現(xiàn)某張課表中出現(xiàn)沖突,則將該課表刪除,重新生成一張。因一張課表的強(qiáng)制條件較多,這種方法會(huì)帶來(lái)較大開(kāi)銷。本文采用的方法是在隨機(jī)產(chǎn)生的一張課表基因過(guò)程中就進(jìn)行沖突檢測(cè)將各個(gè)沖突排除。由此可為后續(xù)的計(jì)算減少大量開(kāi)銷。為了更好的消除沖突,在此采用一張二維表的方法,橫軸是班級(jí),縱軸是時(shí)間段。

表1　全校總課表

沖突消除方法如下:(1)同一個(gè)時(shí)間、班級(jí)上不同課的沖突。因這是張二維表,同一時(shí)間同一班級(jí)對(duì)應(yīng)的是表中的某行某列的一個(gè)元素,填表的時(shí)候不會(huì)產(chǎn)生沖突;(2)一個(gè)老師不能在同一個(gè)時(shí)間段上不同的課程。這只需要檢測(cè)同一行教師代碼,若教師代碼相同則要求課程代碼不允許相同,若課程代碼也相同則重新隨機(jī)產(chǎn)生一個(gè)教學(xué)任務(wù);(3)一間教室在同一個(gè)時(shí)間段不能為兩個(gè)班級(jí)所用。

檢測(cè)每一行。若課程編號(hào)相同,則兩個(gè)班級(jí)可合并上課,若課程編號(hào)不同則重新隨機(jī)生成一個(gè)新教室。

至此,排課表的主要沖突檢測(cè)和解決完畢。一張滿足強(qiáng)制規(guī)則的課表在后續(xù)優(yōu)化中才有意義,否則只能給計(jì)算機(jī)增加額外的無(wú)用開(kāi)銷。

適應(yīng)度評(píng)價(jià)函數(shù)使用計(jì)算染色體特征值的方式,其表示個(gè)體對(duì)應(yīng)解的優(yōu)劣[8]。在此考慮兩個(gè)因素,第一個(gè)是時(shí)間優(yōu)化度,即表示課程應(yīng)當(dāng)盡可能的安排在學(xué)生學(xué)習(xí)效率高的時(shí)間段;第二個(gè)是節(jié)次優(yōu)化度,即表示若一門(mén)課每周上兩次,其應(yīng)被間隔開(kāi)。若連續(xù)兩次相同的課,學(xué)生和教師均會(huì)感覺(jué)到力不從心。這里采用適應(yīng)度函數(shù)為e=w1a2+w2b2;a和b分別表示時(shí)間優(yōu)化度適應(yīng)度和節(jié)次優(yōu)化度適應(yīng)度。w1和w2代表對(duì)應(yīng)的權(quán)值。

初始群種隨機(jī)生成若干種排課方案的集合,表示基于遺傳算法的排課的搜索空間。

選擇操作采用最經(jīng)典的輪盤(pán)賭算法,其思想是不同個(gè)體的適應(yīng)度在一個(gè)種群中所占比例的總和為 1,呈現(xiàn)在一個(gè)輪盤(pán)上,個(gè)體的適應(yīng)度越大,被選中的機(jī)會(huì)越高[9]。

交叉算子,父?jìng)€(gè)體按照一定的概率隨機(jī)交換基因形成新的個(gè)體,在本課題中采取局部列完整交叉操作。例如選中第1張課表的班級(jí)3和第5張課表的班級(jí)7,則將這兩張課表中的這兩列完全互換。采用此交叉方法的原因是:若完全隨機(jī)選擇若干個(gè)基因進(jìn)行交換,必然會(huì)帶來(lái)同一列中的課程沖突,而一旦產(chǎn)生沖突,此時(shí)只能刪除課表,將導(dǎo)致課表總量下降,不滿足遺傳算法思想。

變異操作,變異的目的:一是產(chǎn)生新的個(gè)體,使遺傳算法維持種群的多樣性;二是當(dāng)種群的所有個(gè)體差異已較小時(shí),交叉操作已沒(méi)有意義,只能靠變異來(lái)產(chǎn)生新的個(gè)體;第三個(gè)目的是變異算子既能加速向最優(yōu)解的方向收斂,又能有效抑制遺傳操作過(guò)早地結(jié)束收斂。但變異概率只能取較小值,否則可能破壞已確定的最優(yōu)解區(qū)域。這里采用改進(jìn)型的變異算法,以往的變異算法通常變異是完全隨機(jī)的,這樣有較大的概率會(huì)使生成的課表不滿足強(qiáng)制規(guī)則,成為無(wú)用解。而采用的變異算法是直接互換某一列中的若干位基因,這樣在同一列上不會(huì)產(chǎn)生沖突。可避免將一個(gè)有效解變異為無(wú)效解。

終止條件可分為兩種,第一種是達(dá)到了自定義的適應(yīng)度要求,通常人們均想以這種方式完成迭代獲得最優(yōu)解。但一般由于不了解適應(yīng)度值該如何設(shè)置,因此通常不適合;第二種是達(dá)到一定的迭代次數(shù),這個(gè)更易設(shè)置,算法上實(shí)現(xiàn)也較為簡(jiǎn)單。

2.2基于遺傳算法排課優(yōu)化流程描述

(1)對(duì)課程信息進(jìn)行編碼;(2)初始化遺傳算法種群;(3)計(jì)算種群適應(yīng)度,若滿足終止條件則跳轉(zhuǎn)至(7)。否則跳轉(zhuǎn)至(3);(4)計(jì)算個(gè)體適應(yīng)度,進(jìn)入輪盤(pán)賭選擇操作。被選中個(gè)體跳轉(zhuǎn)至(4)。未被選中個(gè)體直接進(jìn)入子代;(5)被選中個(gè)體進(jìn)行交叉、變異操作后進(jìn)入子代種群;(6)獲得子代種群后跳轉(zhuǎn)至(3);(7)譯碼輸出,算法結(jié)束。

2.3軟件運(yùn)行結(jié)果

本文算法的主要目的是提高課表適應(yīng)度,先將課程信息進(jìn)行編碼,0表示休息,1～8表示不同課程。生成的初始種群如圖1所示,最上方表示該DNA的適應(yīng)度。經(jīng)過(guò)若干代迭代后,適應(yīng)度由76提升至123,編碼后的課表如圖2所示。對(duì)該DNA進(jìn)行譯碼處理后,第一列表示第一和第二個(gè)班級(jí)課表如圖3所示。

圖1　初始種群中的一個(gè)DNA 適應(yīng)度為76.0

圖2　改進(jìn)遺傳算法優(yōu)化后DNA,適應(yīng)度到達(dá)123.0

圖3　第一個(gè)和第二個(gè)班級(jí)課表輸出結(jié)果

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

本文以所在學(xué)校為背景,首先分析了排課問(wèn)題的復(fù)雜性,接著簡(jiǎn)要分析了遺傳算法思想及解決排課優(yōu)化問(wèn)題的可行性。給出一般遺傳算法的計(jì)算步驟、排課問(wèn)題的強(qiáng)制條件和優(yōu)化條件,然后分析了使用遺傳算法解決排課優(yōu)化問(wèn)題的方法即詳細(xì)步驟。在根據(jù)學(xué)校的情況驗(yàn)證了整個(gè)排課過(guò)程,印證了此排課優(yōu)化算法的科學(xué)性和合理性。通過(guò)該方法能夠顯著減輕教務(wù)員工的工作量,提升工作效率。此智能排課算法雖可實(shí)現(xiàn)智能排課優(yōu)化,但使用范圍有限,只能針對(duì)公共課的排課問(wèn)題,目前諸多高校已開(kāi)設(shè)不同的選修課,班級(jí)不再固定,對(duì)智能排課系統(tǒng)提出了更高的要求,這也是本課題后續(xù)研究的方向。

參考文獻(xiàn)

[1]丁健.基于遺傳算法的排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].武漢:華中科技大學(xué),2011.

[2]周德全.免疫遺傳算法及認(rèn)知無(wú)線電參數(shù)優(yōu)化決策[J].通信技術(shù),2012,45(2):53-55.

[3]夏磊,俞能海.基于遺傳算法的小衛(wèi)星任務(wù)調(diào)度[J].通信技術(shù),2013,46(11):64-68.

[4]王彥,王超,劉宏立.模擬退火遺傳算法在多用戶檢測(cè)技術(shù)中的應(yīng)用[J].電子技術(shù)應(yīng)用,2011,37(4):102-105.

[5]侯福均,吳祈宗.基于遺傳算法和模擬退火算法優(yōu)化神經(jīng)網(wǎng)絡(luò)的鐵路營(yíng)業(yè)里程預(yù)測(cè)[J].北京理工大學(xué)學(xué)報(bào),2004,24(3):247-250.

[6]Holland J.Adaptation in natural and artificial systems[M].England:A Bradford Book,1975.

[7]林茂,李孝全,蘇楊.基于改進(jìn)免疫遺傳算法的電網(wǎng)故障診斷研究[J].電子技術(shù)應(yīng)用,2012,38(8):66-68.

[8]馮阿芳.基于遺傳算法的自動(dòng)組卷策略[J].哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào),2008,24(4):27-28.

[9]彭新竹.遺傳算法的改進(jìn)策略及其應(yīng)用[J].華東船舶工業(yè)學(xué)院學(xué)報(bào):自然科學(xué)版,2002,16(3):53-58.

Arrangement and Optimization of College Curriculum Schedule by Improved Genetic Algorithm

LI Yang,ZHANG Xin

(Big Data and Information Engineering College,Guizhou University,Guiyang 550025,China)

AbstractIn order to solve the problem of the large amount of work multi condition and high complexity in the course of the college arrangement,we propose a schedule optimization scheme based on the improved genetic algorithm with the teaching mission and total schedule as the gene and DNA,respectively and the initial population randomly generated to meet the mandatory rules for the DNA.Some improvements of the genetic algorithm are discussed,including changing random cross column to be a local full cross algorithm,and random mutation to be random swap algorithm for the inside of column.The final form of a scientific and rational arrangement plan is obtained through several generations of iterative optimization.Experiment results show that the fitness schedule increases from 76 to 123,indicating a good optimization effect.

Keywordscourse scheduling;optimization;improved genetic algorithm

doi:10.16180/j.cnki.issn1007-7820.2016.05.034

收稿日期:2015-10-14

作者簡(jiǎn)介:李陽(yáng)(1989—),男,碩士研究生。研究方向:移動(dòng)通信技術(shù)。張欣(1976—),男,博士,副教授,碩士生導(dǎo)師。研究方向:下一代無(wú)線通信及應(yīng)用等。

中圖分類號(hào)TP391

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

文章編號(hào)1007-7820(2016)05-127-04