李　陽,張　欣

(貴州大學 大數據與信息工程學院,貴州 貴陽　550025)

?

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

李陽,張欣

(貴州大學 大數據與信息工程學院,貴州 貴陽550025)

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

關鍵詞排課;優(yōu)化;改進遺傳算法

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

1高校排課問題限制因素

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

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

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

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

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

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

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

本文通過改進遺傳算法中的基因編碼方法,交叉算法中的交叉方式,變異算法中的變異方式,解決了在交叉和變異過程中產生不滿足強制條件的課表問題。

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

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

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

表1　全?？傉n表

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

檢測每一行。若課程編號相同,則兩個班級可合并上課,若課程編號不同則重新隨機生成一個新教室。

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

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

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

選擇操作采用最經典的輪盤賭算法,其思想是不同個體的適應度在一個種群中所占比例的總和為 1,呈現在一個輪盤上,個體的適應度越大,被選中的機會越高[9]。

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

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

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

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

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

2.3軟件運行結果

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

圖1　初始種群中的一個DNA 適應度為76.0

圖2　改進遺傳算法優(yōu)化后DNA,適應度到達123.0

圖3　第一個和第二個班級課表輸出結果

3結束語

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

參考文獻

[1]丁健.基于遺傳算法的排課系統(tǒng)的設計與實現[D].武漢:華中科技大學,2011.

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

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

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

[5]侯福均,吳祈宗.基于遺傳算法和模擬退火算法優(yōu)化神經網絡的鐵路營業(yè)里程預測[J].北京理工大學學報,2004,24(3):247-250.

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

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

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

[9]彭新竹.遺傳算法的改進策略及其應用[J].華東船舶工業(yè)學院學報:自然科學版,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

作者簡介:李陽(1989—),男,碩士研究生。研究方向:移動通信技術。張欣(1976—),男,博士,副教授,碩士生導師。研究方向:下一代無線通信及應用等。

中圖分類號TP391

文獻標識碼A

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