一種改進的遺傳算法在年度排課問題中的應用

王　璐　楊亞偉

(1.山東省質(zhì)量技術(shù)監(jiān)督教育培訓中心　濟南　250013)(2.山東電力工程咨詢院有限公司　濟南　250013)

?

一種改進的遺傳算法在年度排課問題中的應用

王璐1楊亞偉2

(1.山東省質(zhì)量技術(shù)監(jiān)督教育培訓中心濟南250013)(2.山東電力工程咨詢院有限公司濟南250013)

論文深入分析了年度排課問題的特點,提出了一種基于改進遺傳算法的求解方法。該方法通過分析適應度與編碼之間的內(nèi)在關(guān)系,對常規(guī)遺傳算法的雜交和變異操作進行了改進,提出了基于子適應度的縱向基因雜交法和自適應變異策略等方法。仿真結(jié)果表明該改進的遺傳算法相比于常規(guī)遺傳算法在求解年度排課問題時性能有了較大的提升。

遺傳算法; 年度計劃; 排課問題; 自適應變異策略

Class NumberTP391.1; G433

1　引言

隨著教育事業(yè)的發(fā)展和學校規(guī)模的增加,排課問題逐漸成為各類學校教學管理工作中的一個重點問題和難點問題[1]。排課問題是一個多約束、多目標的組合優(yōu)化問題,是一個NP完全問題[2],在排課的過程中,需要綜合考慮教師、教室、實驗室、時間分配以及各種約束條件等多方面的因素[3]。隨著計算機技術(shù)的發(fā)展,以遺傳算法為代表的各種智能算法被應用到這類排課問題當中,并取得了不錯的效果[4]。

目前對于排課問題的研究,絕大多數(shù)都集中在以高校排課為代表的周排課問題上,而對于年度排課問題的研究,則較為少見。

2　年度排課問題及其特點

年度排課問題是指以年為周期的排課問題,這類排課問題在各種培訓機構(gòu)中較為常見。以山東省質(zhì)量技術(shù)監(jiān)督教育培訓中心為例,該中心每年年初會制定并發(fā)布該年度的培訓計劃,以便學員根據(jù)需要來選擇培訓課程。該培訓計劃中通常包含了本年度所要開展的培訓課程及其時間、教室、實驗室、教師、班主任(主要負責該課程培訓期間的管理工作)等相關(guān)信息,是一個典型的以年為周期的排課問題。與普通高校的周排課問題相比,年度排課問題有如下特點:

1) 排課以一年為周期,以一天為最小時間片;

2) 每門課程的學員人數(shù)在排課時無法精確獲得,只能根據(jù)以往經(jīng)驗來估計;

3) 對于課表優(yōu)劣性的評判標準,與周排課問題有很多不同之處。

因此,在解決年度排課問題時,并不能完全照搬周排課問題的解決方案,而是需要針對年度排課問題的特點做一些改進和優(yōu)化。

3　年度排課問題的數(shù)學模型

3.1模型中的硬約束條件

年度排課問題的硬約束條件與周排課問題的硬約束條件[5]類似,即

1) 同一時間,一個教室不能同時有一門以上的課程;

2) 同一時間,一個實驗室不能同時有一門以上的課程;

3) 同一時間,一個教師不能同時有一門以上的課程;

4) 同一時間,一個班主任不能同時有一門以上的課程。

3.2模型中的軟約束條件

由于年度排課問題自身的特點,其軟約束條件與周排課問題相比有很多不同之處。下面是本文模型中的具體軟約束條件。

3.2.1均勻度

由于整個培訓中心一年的工作安排都與該年度的培訓計劃密切相關(guān),因此年度培訓計劃要求有良好的均勻度,以使全年的工作可以合理而均勻的分布,從而避免某些時段過于繁忙而某些時段過于清閑。

均勻度是表示點集在空間中分布均勻性的一個參數(shù)[6]。均勻度的表示方法有很多,但多數(shù)方法的本質(zhì)都是利用方差來計算均勻度[7]。對于課表的時間均勻度問題,可以看做是一個一維空間的點集均勻度問題,利用方差來表示其均勻度系數(shù)α的方法如下:

(1)

在利用式(1)計算年度課表的時間均勻度時,其時間段i可以選擇以天為單位,也可以選擇以周為單位。由于以天為時間段會大大增加程序的計算量,并且從實際角度來考慮也沒有明顯的優(yōu)勢,因此本文選擇以周為時間段來進行課表均勻度系數(shù)的計算。

一般認為,利用式(1)得到的均勻度系數(shù)越小,表示其均勻度越好。然而通過一些具體實例的研究發(fā)現(xiàn),在某些情況下,并不是得到的均勻度系數(shù)越小,其均勻度就越好。表1給出了兩個課表工作量分布的實例,利用式(1)計算得到兩個課表的均勻度系數(shù)都是5,然而通過觀察發(fā)現(xiàn),課表1的工作量時間分布要比課表2更為均勻,因此僅僅利用式(1)來衡量課表的均勻度并不完全合適。

表1　課表工作量實例

造成上述問題的原因在于,式(1)中計算的方差只能體現(xiàn)每個時間段工作量分布的離散程度,而不能體現(xiàn)整個時間周期內(nèi)工作量的分布趨勢。為了彌補這個缺陷,本文定義一個均勻分布系數(shù)β來表示工作量的整體分布趨勢:

(2)

(3)

利用式(2)得到的分布系數(shù)β值越小,表示其工作量的整體分布越均勻。利用式(2)來計算表1中兩個課表實例的均勻分布系數(shù)β,課表1的分布趨勢系數(shù)為3.54,課表2的分布趨勢系數(shù)為14.58,由此可以看出均勻分布系數(shù)β能夠很好地反應工作量的整體分布趨勢是否均勻。

均勻度系數(shù)α和均勻分布系數(shù)β分別從個體離散程度和總體分布趨勢兩個方面來體現(xiàn)了課表的均勻度,兩個參數(shù)可以起到很好的互補作用,因此關(guān)于年度課表的均勻度PA,本文用如下方式表示

PA=C1α+C2β

(4)

其中,C1和C2是常數(shù),用來設置均勻度系數(shù)α和均勻分布系數(shù)β在均勻度計算時的權(quán)重。

有了均勻度的表示方法,便可以對課表的均勻度進行計算。本模型中課表的均勻度計算由以下幾個部分組成:

1) 全部課程的總體均勻度。

2) 每種類型課程的均勻度。本模型中,按照課程類型,可以將全年所有培訓課程分為幾大類,對于每一類課程而言,應盡量均勻分布,以使本類課程的學員可以在全年的各個階段都能夠進行學習。

3) 每名教師的課程均勻度。對于每名教師而言,其教學任務也應該均勻地分布在全年各個時段,以避免某些時間過于繁忙。

4) 每名班主任的課程均勻度。對于每名班主任而言,其所負責的課程也應均勻的分布在全年各個時段,以避免某些時段過于繁忙。

3.2.2周末及節(jié)假日的占用情況

對于占用周末及節(jié)假日的問題,不同的模型可能有不同的要求,在本模型中,希望在滿足其他要求的情況下,周末及節(jié)假日占用率越低越好。周末及節(jié)假日占用率PH可利用下列公式計算

(5)

其中,W是課表所占用的周末總天數(shù),H是課表所占用的節(jié)假日總天數(shù),W0是該年度中周末的總天數(shù),H0是該年度中節(jié)假日的總天數(shù),C1和C2分別是周末及節(jié)假日的權(quán)重系數(shù),其值越高表示越不想被占用。

3.2.3備用教室

在本模型中,由于在制定計劃時并不能提前知道每門課程的精確學員人數(shù),因此只能根據(jù)預估的學員人數(shù)來選擇教室,這樣做必然存在實際學員人數(shù)超過教室容量的風險。為了降低這種風險,我們希望在滿足其他要求的情況下,能夠盡可能為每門課程留有一個容量更大的備用教室。備用教室的配備情況可以用備用教室配備率PC來表示:

(6)

3.2.4班主任及教師的工作量平均分配

在本模型中,每門課程一般都有多個班主任和教師可供選擇,因此我們希望每個班主任和教師的工作量可以盡量平均分布,避免某些班主任和教師的工作量過多,而某些班主任和教師的工作量過少。班主任和教師的工作量平均分配程度可以用平均分配系數(shù)PD來表示:

(7)

其中,n是班主任的總數(shù),Ei是第i名班主任的總工作量,S是所有課程的總工作量。

4　改進遺傳算法的設計方案

4.1編碼

本文采用排課問題中通常使用的十進制矩陣編碼方式來進行編碼,具體編碼方式如表2所示。其中,每門課程的開始日期用3位十進制數(shù)表示,其余4項均用2位10進制數(shù)表示,每個課程的編碼共計11位。例如編碼10003010401,代表該課程在該年度第100天開始培訓,培訓用教室ID為03,培訓用實驗室ID為01,課程班主任ID為04,授課教師ID為01。將所有課程的編碼依次羅列,便組成了整個課表的矩陣編碼。

表2　十進制矩陣編碼方式

4.2初始種群

初始種群一般采用隨機生成的方式產(chǎn)生,但是對于排課問題,利用隨機方式生成的初始種群中往往存在較多不滿足模型硬約束條件的個體,在這種情況下算法的性能會受到很大的影響。為了提高算法的搜索速度,本文在利用隨機方式生成初始種群后,會對初始種群中的個體進行硬約束條件檢測,當發(fā)現(xiàn)不滿足模型硬約束條件的個體時,會重新生成該個體直至所有個體均滿足模型的硬約束條件。

4.3適應度計算

個體的適應度主要從均勻度、周末及節(jié)假日占用情況、備用教室配備情況以及工作量平均分配情況等幾個方面來衡量。前文已經(jīng)給出了上述每種子適應度的具體模型和計算方法,在計算個體的總體適應度時,需要為每個子適應度設置一個權(quán)重值,以按照具體需求來調(diào)節(jié)每種子適應度的權(quán)重。本文中子適應度的權(quán)重值設置如表3所示。對于不滿足硬約束條件的個體,其適應度為0。

4.4復制

本文采用適應度比例選擇法來作為遺傳算法中的復制方法,該方法依據(jù)個體的適應度進行選擇,適應度越高的個體被復制的概率就越大。

表3　子適應度權(quán)重值

4.5基于子適應度的縱向基因雜交法

雜交是種群中不同個體之間通過交換對應的基因來實現(xiàn)的,是遺傳算法中產(chǎn)生新個體的主要手段[8]。對于排課問題而言,通常將每門課程的安排看做是一個基因,在進行雜交操作時,在隨機選擇雜交的個體之后,只需要將雜交雙方該范圍內(nèi)的課程安排互換即可。

然而,通過實際測試發(fā)現(xiàn),這種雜交方法在解決年度排課問題時效果并不理想。通過分析發(fā)現(xiàn),個體的適應度大小與本文所采用的十進制矩陣編碼之間存在一定的關(guān)聯(lián):

1) 課表均勻度、以及周末及節(jié)假日占用率,與整個課表的時間安排關(guān)系最為密切,即表2編碼中的第2列數(shù)據(jù);

2) 教師的課程均勻度及教師的工作量平均度,與教師的整體安排關(guān)系最為密切,即表2編碼中的第6列;

3) 班主任的課程均勻度及班主任的工作量平均度,與班主任的整體安排關(guān)系最為密切,即表2編碼中的第5列;

4) 備用教室配備情況,與教室的整體安排關(guān)系最為密切,即表2編碼中的第3列。

因此,在雜交操作時互換個體中對應的課程安排,即互換表2編碼中對應的某些行,很難有效的提高個體的適應度。為了解決這一問題,本文采用一種基于子適應度的縱向基因雜交法,該方法首先按照表3中的各項子適應度分別對種群中的個體進行排序,然后對于每項子適應度,選擇種群中該子適應度最低的個體,將其與該子適應度最為相關(guān)的縱向基因替換為種群中該子適應度最高的個體中的對應基因。基于子適應度的縱向基因雜交法的流程圖如圖1所示。

在其它條件完全相同的情況下,基于子適應度的縱向基因雜交法與常規(guī)雜交法的實際運行結(jié)果如圖2所示。通過圖2可以看出,基于子適應度的縱向基因雜交法能夠大大改善算法的性能。

圖1　基于子適應度的縱向基因雜交法流程圖

圖2　基于子適應度的縱向基因雜交法與常規(guī)雜交法對比

4.6自適應變異策略

種群中進行變異的基因數(shù)量B由變異概率變Pm來決定,即

(8)

其中,M為種群中個體的數(shù)量,L為個體中攜帶的基因數(shù)量。

變異概率是一個敏感參數(shù),其值對算法的運行結(jié)果有較大的影響。增大變異概率,能夠增強物種的多樣性,但變異概率過大,會降低算法的收斂速度;減小變異概率,則會影響算法的搜索范圍,不利于得到全局最優(yōu)解[9]。本文模型中變異概率取值對結(jié)果的影響如圖3所示。

通過圖3可以看出,變異概率不能設得過大或者過小,而是應當在一個適當?shù)姆秶鷥?nèi)取值。

常規(guī)遺傳算法中將變異概率設置為一個常數(shù),因而無法根據(jù)每個個體的特點來執(zhí)行不同的變異策略。本文采用一種自適應變異策略[10],其在執(zhí)行變異操作時,會根據(jù)不同個體的各項子適應度的大小來決定變異概率的取值,具體方法為:

圖3　變異概率對結(jié)果的影響

1) 在對課程的日期安排進行變異操作時,變異概率根據(jù)課程均勻度以及周末及節(jié)假日占用率兩項子適應度的值確定;

2) 在對課程的教室安排進行變異操作時,變異概率根據(jù)備用教室配備情況的子適應度值確定;

3) 在對課程的班主任安排進行變異操作時,變異概率根據(jù)班主任的課程均勻度以及班主任工作量平均度兩項子適應度的值確定;

4) 在對課程的教師安排進行變異操作時,變異概率根據(jù)教師的課程均勻度以及教師工作量平均度兩項子適應度的值確定。

群體中第i個個體的自適應變異概率Pmi的取值與相關(guān)子適應度的關(guān)系如下:

(9)

通過設置變異概率取值上限Pmax、取值下限Pmin以及基準概率Pm,可以讓不同個體根據(jù)其相關(guān)子適應度的大小來改變其變異概率,當相關(guān)子適應度較大時,變異概率取值介于Pmin和Pm之間,當相關(guān)子適應度較小時,變異概率取值介于Pm和Pmax之間。

為了驗證自適應變異策略的性能,本文分別對普通變異策略和自適應變異策略進行了仿真測試,結(jié)果如圖4所示。通過圖4可以看出,相比于普通變異策略,自適應變異策略性能更優(yōu)。

4.7中止條件

遺傳算法是一個反復迭代的過程,每次迭代期間,都要執(zhí)行適應度計算、復制、雜交、變異等操作,直至滿足終止條件。遺傳算法常用的終止方法有三種,即最大迭代次數(shù)設定法、最小方差設定法以及適應度變化趨勢觀察法。本文中選擇最大迭代次數(shù)法,迭代次數(shù)設置為1000。

圖4　普通變異策略與自適應變異策略對比

5　仿真結(jié)果

本文選擇山東省質(zhì)量技術(shù)監(jiān)督教育培訓中心某年的年度培訓計劃為仿真測試數(shù)據(jù),該仿真測試數(shù)據(jù)的相關(guān)要素如表4所示。

表4　測試數(shù)據(jù)相關(guān)要素

仿真測試時遺傳算法的相關(guān)參數(shù)設置如表5所示。

表5　遺傳算法參數(shù)設置

圖5　仿真結(jié)果

分別對本文所給的改進遺傳算法和普通遺傳算法進行100次仿真測試,然后將所得結(jié)果取平均值,最終結(jié)果如圖5所示。通過圖5可以看出,在解決年度排課問題時,本文所給的改進遺傳算法與普通遺傳算法相比在性能上有了較大的提升。

[1] 張赫男,張紹文.采用改進的混合遺傳算法求解高校排課問題[J].計算機工程與應用,2015,51(5):240-246.

ZHANG Henan, ZHANG Shaowen. Improved hybrid genetic algorithm for university timetabling problem[J]. Computer Engineering and Applications,2015,51(5):240-246.

[2] 江齊,蘭競.遺傳算法在排課問題中的運用[J].重慶大學學報:自然科學版,2005,28(11):58-61.

JIANG QI, LAN Jing. Application of the Genetic Algorithm in Timetable Problem[J]. Journal of ChongQing University(Natural Science Edition),2005,28(11):58-61.

[3] 李紅蟬,朱顥東.采用十進制免疫遺傳算法求解高校排課問題[J].系統(tǒng)工程理論與實踐,2012,32(9):2031-2036.

LI Hongchan, ZHU Haodong. Decimal immunization GA used to solve UTP[J]. Systems Engineering — Theory & Practice,2012,32(9):2031-2036.

[4] Edmund K B, Sanja p. Recent research directions in automated timetabling[J]. European Journal of Operational Research,2002,7:18-27.

[5] 滕姿,鄧輝文,楊久俊.基于遺傳算法的排課系統(tǒng)的設計與實現(xiàn)[J].計算機應用,2007(12):199-204.

TENG Zi, DENG Huiwen, YANG Jiujun. Courses arrangement system base on genetic algorithms[J]. Journal of Computer Applications,2007(12):199-204.

[6] 羅傳文.點空間分析——分維與均勻度[J].科技導報,2004,196(10):51-54.

LUO Chuanwen. Point spatial analyses-fractal dimension and uniform index[J]. Science & Technology Review,2004,196(10):51-54.

[7] 聶峻.均勻度理論及其應用研究[D].成都:成都理工大學碩士學位論文,2011:1-2.

NIE Jun. Research on Uniformity Theory and Applications[D]. Chengdu: Chengdu University of Technology,2011:1-2.

[8] 王小平,曹立明.遺傳算法——理論、應用與軟件實現(xiàn)[M].西安:西安交通大學出版社,2002:34-37.

WANG Xiaoping, CAO Liming. Genetic algorithms: theory, application and software implementation[M]. Xi’an: Xi’an Jiaotong University Press,2002:34-37.

[9] 云慶夏.進化算法[M].北京:冶金工業(yè)出版社,2000:70-72.

YUN Qingxia. Evolutionary algorithms[M]. Beijing: Metallurgical Industry Press,2000:70-72.

[10] 朱燦,梁昔明.一種多精英保存策略的遺傳算法[J].計算機應用,2008,28(4):939-941.

ZHU Can, LIANG Ximing. Novel genetic algorithm with multi-elitist preservation method[J]. Journal of Computer Applications,2008,28(4):939-941.

Application of an Improved Genetic Algorithm in Annual Timetable Problem
WANG Lu1YANG Yawei2
(1. Shandong Education Training Center of Quality and Technical Supervision, Jinan250013)

(2. Shandong Electric Power Engineering Consulting Institute Co ltd, Jinan250013)

Annual timetabling problem was analyzed detailedly, and an improved genetic algorithm was proposed to solve this problem. Longitudinal gene crossover method based on sub-fitness and adaptive aberrance strategy was proposed by analyzing the intrinsic relation between fitness and code. Simulation results indicated that this improved genetic algorithm can solve annual timetable problem more effective than common genetic algorithm.

genetic algorithm, annual plan, timetable problem, adaptive aberrance strategy

2016年2月10日,

2016年3月24日

王璐,女,碩士,工程師,研究方向:特種設備培訓。楊亞偉,男,碩士,工程師,研究方向:電廠儀控系統(tǒng)的設計與工程管理

TP391.1; G433

10.3969/j.issn.1672-9722.2016.08.047