康 彥

(安徽城市管理職業(yè)學院，安徽 合肥 230001)

遺傳算法在高職院校排課問題中的研究與應(yīng)用*

康 彥

(安徽城市管理職業(yè)學院，安徽 合肥 230001)

新形勢下的高職教育具有豐富多樣的教學形式，傳統(tǒng)的人工編排方式在應(yīng)對大量的教學活動編排工作時，效率較為低下，而一些市面上常見的教學管理系統(tǒng)中的排課模塊大多是按照本科的教學模式設(shè)計，無法適應(yīng)高職院校的教學活動編排問題的特殊性.該文研究和分析高職院校排課活動的特點，通過對普通遺傳算法的改進，提出一種解決高職院校排課問題求解算法，并對改進后的算法進行效率分析.

遺傳算法；排課問題；高職院校

我國高等教育事業(yè)的發(fā)展，從上個世紀的八十年代開始迎來了一個發(fā)展的高潮，特別是高等職業(yè)教育，也被納入到了高等教育序列中來，二十多年來，高等職業(yè)院校的數(shù)量和規(guī)模不斷擴大.截至到2012年，我國具有高考招生資格的高職類院校已有1288所，在校生人數(shù)超過1000萬人[1].伴隨著職業(yè)教育的快速發(fā)展，近年來，高職院校辦學特色不鮮明，定位不準確，教學質(zhì)量無法保證等問題慢慢凸顯出來.為了改變這一現(xiàn)狀，高職教育的課程改革也在不斷作出調(diào)整,通過實施“工學結(jié)合、校企合作”及項目化教學等手段，進一步開發(fā)實訓(xùn)模塊、提高學生職業(yè)能力，使高職學生真正成為企業(yè)需要的高級技能型人才.

這一變化使得原本套用本科教學安排模式的高職教學安排問題變得越來越復(fù)雜.除了正常的公共課程(“兩課”、體育、英語、高數(shù)和一些專業(yè)理論基礎(chǔ)課)以外，大多數(shù)實踐實訓(xùn)類課程教學為了達到良好的操作技能學習效果就需要在幾天甚至幾周時間內(nèi)連續(xù)進行授課,還有的課程需要去公司企業(yè)進行實際操作培訓(xùn).

1 遺傳算法

遺傳算法是借鑒了生物進化理論的一種全局搜索優(yōu)化的概率性算法.在生物進化理論中，種群(Population)是生物進化的基本單位[2].單個生物個體(Individual)無法進行遺傳進化.種群通常是一個有大量生物個體構(gòu)成的集合.種群中的個體都不重復(fù)，因為每個個體所表現(xiàn)出來的外部特征都是不同的，比如人類個體的膚色差異、性格差異、運動能力差異等等.之所以存在這些差異，是因為每個生物個體都具有獨一無二的染色體.染色體是遺傳因子(Genetic Factor)的載體.遺傳因子是由許許多多遺傳基因(Gene)按不同的排列組合而成的.生物進化過程中種群中的個體之間進行隨機的交配，產(chǎn)生下一代種群.通過基因交叉(Crossover)、突變(Mutation)和自然選擇等操作后，使得下一代種群更為適應(yīng)外部自然環(huán)境[3].遺傳算法正是模擬了生物進化的這一過程，通過遺傳迭代一定代數(shù)后，得出適應(yīng)度最高的種群.實現(xiàn)生物進化理論中的“優(yōu)勝劣汰，適者生存”[4].

2 高職院校教學活動的特點

(1)本科的學制一般是4年，而?？茷?年.由于受到高職學生需要進行近半年的頂崗實習的要求限制，實際上很多高職院校學生的在校學習時間僅有2.5年或者2.25年.在如此短的時間完成包括公開課、專業(yè)基礎(chǔ)課及專業(yè)實踐實訓(xùn)課在內(nèi)的所有課程難度較大.

(2)大部分高職院校由于建校時間短，規(guī)模發(fā)展快，普遍存在師資不足的情況.在加大本校專職教師的工作量的同時，還需聘請部分校內(nèi)和校外兼職教師.

(3)高職院校重視學生實際動手能力和實踐技能的培養(yǎng)，專業(yè)課程的實驗實訓(xùn)的比例一般不低于50%，這就導(dǎo)致很多教學活動不能安排在普通教室或是多媒體教室中進行，需要在專業(yè)的實驗實訓(xùn)室開展，甚至有的實訓(xùn)活動需要到校外的實訓(xùn)基地或者行業(yè)企業(yè)中進行.因此，高職的教學活動編排必須充分考慮實驗實訓(xùn)室的場地資源的合理調(diào)配和學生外出實踐的時間安排.

(4)在新的高職院校的教學模式中，有一些純實踐類的課程需要進行時間連續(xù)的教學安排.如某系的數(shù)字媒體技術(shù)專業(yè)的“影視后期制作”課程采取的上項目化教學方式，教學時間是安排某學期中連續(xù)的2周內(nèi)完成.這就要求在具體排課的時候，要減少同學期中其他課程的授課周數(shù)，增加周課時數(shù)來完成教學計劃.

綜上所述，這些特點都是高職院校在進行具體教學活動編排時遇到的一些共性的問題.正確地理解和分析它們，有助于我們在解決高職院校排課問題上提高，改進和創(chuàng)新.

3 基于遺傳算法的高職院校排課算法

求解排課問題的遺傳算法首先需要解決的就是如何對排課記錄進行合理的編碼，實質(zhì)上就是為排課記錄設(shè)定教學場地時間對[5-6].將基因按一定的順序組合到一起，就是一條染色體.在排課問題中，基因是排課記錄，染色體就是一張完整的課表.通過對課表染色體的選擇、交叉和變異等一系列遺傳操作后得出適應(yīng)度較高的個體作為最后的解.排課算法的整體流程如圖1.

圖1 排課算法流程

本文在研究分析傳統(tǒng)的遺傳算法的特點之后，對其進行了改進，設(shè)計出一套符合高職院校特點的排課算法，主要改進如下：

(1)為每個排課記錄設(shè)置優(yōu)先級，設(shè)計出基于優(yōu)先級的課表染色體，提高了生成有效課表的效率.

(2)改進優(yōu)化目標，將硬約束寫入課程基因中，減少了遺傳操作中無效課表的出現(xiàn)比例.

(3)引入課表個體自動修復(fù)，將沖突較少的無效課表個體在有限的時間代價內(nèi)修復(fù)為有效個體.減少課表生成次數(shù).

4 算法性能分析

實驗的數(shù)據(jù)來自于某高職學院信息工程系2012～2013學年第一學期的實際教學活動數(shù)據(jù).

(1)迭代次數(shù)比較.表1是交叉概率為0.6，變異概率為0.02條件下種群個體適應(yīng)度趨于穩(wěn)定的代數(shù).

表1 迭代次數(shù)對比-1

表2是交叉概率為0.5，變異概率為0.01條件下種群個體適應(yīng)度趨于穩(wěn)定的代數(shù).

表2 迭代次數(shù)對比-2

通過上述數(shù)據(jù)的對比，可以看出在不同的種群規(guī)模下，改進后的遺傳算法得到穩(wěn)定的適應(yīng)度的迭代次數(shù)均小于普通遺傳算法.證明其搜索性能優(yōu)于普通遺傳算法.

(2)算法時間消耗分析.通過對上述實際排課數(shù)據(jù)進行模擬不同的迭代次數(shù)來比較改進后的遺傳算法和普通遺傳算法之間的時間消耗.假設(shè)初始的種群規(guī)模為50.迭代次數(shù)分別為100次、150次、200次和300次.具體結(jié)果見表3、表4.

表3 迭代次數(shù)100次

表4 迭代次數(shù)200次

通過對上述對比數(shù)據(jù)的分析，我們得出以下結(jié)論：

① 不管是普通遺傳算法還是改進后的遺傳算法，在種群規(guī)模確定的情況下，迭代次數(shù)越高，時間消耗越大.產(chǎn)生適應(yīng)度較高個體的數(shù)量也隨著迭代次數(shù)的增加而增加.

② 在相同迭代次數(shù)中，改進后的遺傳算法的時間效率和產(chǎn)生較高適應(yīng)度的個體數(shù)明顯優(yōu)于普通遺傳算法.

③ 出現(xiàn)適應(yīng)度較高個體數(shù)在迭代次數(shù)超過200次以后，基本趨于穩(wěn)定.

5 總結(jié)

高職院校的教學活動安排問題是一個涉及諸多學科的現(xiàn)實問題.本文以某高職學院為例分析和總結(jié)了高職院校教學活動安排問題的特點.當今的高職院校教學模式多為“工學結(jié)合、校企合作”模式[7]，注重提高學生的實踐操作能力的培養(yǎng).實驗實訓(xùn)課程的比例相對較高.從而加大了教學活動編排的復(fù)雜度.本文在研究分析了傳統(tǒng)的遺傳算法的特點之后，對其進行了改進，設(shè)計出一套符合高職院校特點的排課算法.

[1]邊昊.我國高職院校教學改革的現(xiàn)狀與趨勢分析[J].遼寧科技學院學報，2014(03).

[2]A.Colorni,Dorigomarco,V.Maniezzo. Metaheuristics for high school timetabling[J].Computer Optimization and Application,1998,9(7):275-298.

[3]Pillay N，Banzhaf W.An informed genetic algorithm for the examination timetabling problem[J].Applied Soft Computing，2010，10(2)：457-467.

[4]任克強,趙光甫,張國萍. 高校排課問題的模型與算法[J]. 計算機與現(xiàn)代化,2007(10)：80-82.

[5]張獻.蟻群算法在排課問題中的應(yīng)用研究[J]. 長春大學學報,2007(10)：80-82.

[6]祝勇仁,鄧勁蓮,胡獻華,張煒.排課問題的一種遺傳算法適應(yīng)度求解方法[J].四川大學學報(工程科學版),2007(S1):277-282.

[7]韋玉,馮速. 免疫遺傳算法在排課問題中的應(yīng)用[J]. 北京師范大學學報(自然科學版),2008(02):168-173.

(責任編輯:王前)

10.13877/j.cnki.cn22-1284.2015.04.013

2015-02-10

2014 年省級教學質(zhì)量與教學改革工程項目“高職院校軟件設(shè)計類課程自主學習平臺的研究與應(yīng)用”( 2014jyxm603)

康彥，男，安徽合肥人，講師.

TP31

A

1008-7974(2015)02-0034-03