梁利亭

[摘要]隨著我國教育改革的不斷推進，高職教育的教學(xué)形式變得越來越豐富，在這樣的情況下，傳統(tǒng)的排課方式已經(jīng)無法適應(yīng)現(xiàn)階段規(guī)模不斷擴大的教學(xué)活動。為了適應(yīng)這種現(xiàn)狀，必須研究出一款符合高職院校教學(xué)活動要求的排課系統(tǒng)。本文將就基于遺傳算法的高職院校排課系統(tǒng)進行研究，用于解決現(xiàn)階段高職院校遇到的排課問題，為高職教育發(fā)展提供助力。

[關(guān)鍵詞]遺傳算法;高職院校;排課

[中圖分類號]G640 [文獻標(biāo)識碼]A [文章編號]1671-5918（2019）01-0076-03

doi：10.3969/j.issn.1671-5918.2019.01.034 [本刊網(wǎng)址]http：//www.hbxb.net

前言

隨著我國教育體制的不斷完善，我國高職教育獲得了迅猛的發(fā)展，為我國社會各行業(yè)輸出了許多技術(shù)型人才。隨著招生規(guī)模的持續(xù)擴大，廣大高職院校的專業(yè)體系也變得越來越豐富完善，這就為排課工作帶來了巨大的壓力。面對越來越復(fù)雜的排課問題，很多高職院校往往需要花費大量的時間。為了解決這一問題，必須采取先進技術(shù)措施予以解決。

一、遺傳算法概述

（一）遺傳算法的概念。遺傳算法是從生物進化理論中衍生出的一種全局搜索優(yōu)化的概率性算法。根據(jù)生物進化理論，在一個種群中，單個生物個體是無法實現(xiàn)遺傳進化的，因此種群中的個體所表現(xiàn)出的特征往往存在一定的差異性，這是因為每個生物都具有獨一無二的染色體，染色體中則包含了遺傳因子。不同個體之間隨機交配產(chǎn)生下一代種群，通過基因交叉、突變和自然選擇使種群更好地適應(yīng)外部自然環(huán)境。遺傳算法正是脫胎于上述過程，通過遺傳迭代一定代數(shù)后，獲得適應(yīng)度最高的種群，深刻體現(xiàn)了適者生存的自然規(guī)則。

遺傳算法的共同流程如下：首先，構(gòu)建一個候選解組集。其次，基于一定的適應(yīng)性條件對這些候選解的適應(yīng)度進行計算。在此，通過適應(yīng)度的對比分析淘汰一定的候選解。最后，對保留下來的候選解進行一定的操作，生成新的候選解。將上述內(nèi)容綜合起來，即可對遺傳算法進行定義：基于染色體群的并行搜索，帶有猜測性質(zhì)的選擇操作、交換操作和突變操作。

（二）遺傳算法的特點分析。目前，遺傳算法已經(jīng)成為解決搜索問題的一種通用算法，在各類通用問題中都能夠發(fā)揮著有效的作用。其特點主要包括以下幾個方面：

1.遺傳算法是從問題解的串集開始搜索，這是其于傳統(tǒng)優(yōu)化算法最大的區(qū)別。因此它避免了傳統(tǒng)算法從單個解人手可能誤入局部最優(yōu)解的問題，覆蓋范圍更加寬廣，實現(xiàn)了全局擇優(yōu)。

2.遺傳算法可以對群體中的多個個體進行同步處理，更加有利于實現(xiàn)并行化。

3.遺傳算法不需要使用到搜索空間的知識和其他輔助信息，而是利用適應(yīng)度函數(shù)值對個體進行評估，這時的遺傳算法的應(yīng)用范圍更加寬廣。

4.遺傳算法具有自組織、自適應(yīng)以及自學(xué)習(xí)性。通過遺傳算法對進化過程中獲得的信息進行自行組織搜索時，個體的適應(yīng)度越大，其生存概率也就越高，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。

5.遺傳算法采用的并不是不確定性規(guī)則，而是通過概率的變遷規(guī)則對搜索方向進行引導(dǎo)。

6.遺傳算法本身采用了動態(tài)自適應(yīng)技術(shù)，因此可以通過自動調(diào)整算法對進化過程中的參數(shù)以及編碼精度進行控制。

目前，遺傳算法廣泛應(yīng)用許多學(xué)科，函數(shù)優(yōu)化和組合優(yōu)化是其應(yīng)用的兩個主要領(lǐng)域?，F(xiàn)如今，人們構(gòu)造除了許多形式復(fù)雜的測試函數(shù)，這類函數(shù)具有非線性、多模型以及多目標(biāo)的特征，在對其優(yōu)化問題進行研究時需要應(yīng)用遺傳算法。同時，隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也隨之?dāng)U張，面對復(fù)雜問題的求解，遺傳算法也是最優(yōu)化的工具。

二、高職院校教學(xué)活動的特點以及排課的約束條件

（一）高職院校教學(xué)活動的特點分析

高職院校屬于專科，其學(xué)制為3年，由于高職院校專業(yè)課程往往實踐性和理論性并重，因此在畢業(yè)之前，學(xué)生往往需要進行半年左右的頂崗實習(xí)，因此告知學(xué)生在學(xué)校的學(xué)習(xí)時間最多為兩年半。在這段時間內(nèi)，學(xué)生需要完成包括公開課、專業(yè)基礎(chǔ)課以及專業(yè)實踐實訓(xùn)課在內(nèi)的所有課程，時間十分緊張。與此同時，一些發(fā)展時間較短的高職院校各方面力量都存在一定的不足，教師的工作量相對較高，為了緩解壓力，高職院校通常會從校外聘請一部分兼職教師。

在課程安排上，高職院校的教育教學(xué)目標(biāo)是培養(yǎng)具有綜合職業(yè)能力的高素質(zhì)人才，因此除了理論教學(xué)外，同時也更加注重學(xué)生動手實踐能力的培養(yǎng)。因此在專業(yè)課程體系中，實驗實訓(xùn)課程所占的比例很高，基本上可以達到一半。在實驗實訓(xùn)課程開展時對教學(xué)條件的要求較高，需要高職院校建設(shè)專門的實驗實訓(xùn)場地。還有部分實驗實訓(xùn)活動需要深入到社會企業(yè)中開展，這就要求高職院校排課活動必須考慮到場地資源的調(diào)配以及學(xué)生外出的時間安排。

此外，高職院校專業(yè)課程中還包括了一些教學(xué)實踐項目，一般需要占用學(xué)生連續(xù)幾周的實踐，在這段時間內(nèi)，學(xué)生很難有多余的精力對完成其他課程，這一點在排課中也需要考慮到。

（二）高職院校排課的約束條件分析

高職院校排課活動實際上是一個帶有約束的多目標(biāo)組合優(yōu)化問題，在排課的過程中會受到一些約束條件的限制，同時排課方案并非是固定的。在具體工作中，不同約束條件之間會產(chǎn)生一定的沖突，排課活動的目標(biāo)就是消除這些沖突，如此才能保障教學(xué)計劃的順利實施。通常情況下，高職院校排課的約束條件主要包括以下幾個方面：

首先，兩門不同的課程無法在同一教室的同一時間開展。其次，一個教師無法同時在兩個教室開展教學(xué)活動。其三，一個學(xué)生不能同時上兩門不同的課程。其四，教師的座位數(shù)必須超過上課班級的總?cè)藬?shù)。其五，一個班級的同一門課程之間必須設(shè)置一定的間隔。其六，體育、實踐類課程最好安排在下午。其七，排課必須考慮到外聘教師的實際情況。其八，公共選修或是公共類課程最好優(yōu)先排課。其九，要對一些制定了教學(xué)區(qū)且周次不規(guī)則的特殊課程進行科學(xué)的安排。

在利用遺傳算法進行排課時，需要根據(jù)具體規(guī)則和約束條件設(shè)置適應(yīng)度函數(shù)，根據(jù)計算出的適應(yīng)度值判斷是否存在違反約束條件的情況，以此判斷排課方案的合理性。

三、基于遺傳算法的高職院校排課活動研究

遺傳算法是模仿達爾文的生物進化理論對復(fù)雜的優(yōu)化問題進行求解。

（一）基因編碼

在遺傳算法中，編碼即是指將一個問題的可行解從其求解空間轉(zhuǎn)換到能處理的搜索空間。編碼的方法決定了生物種群中個體的染色體排列形式，同時也體現(xiàn)了群體遺傳進化運算的方式。

在高職院校排課過程中，根據(jù)基因編碼方法，需要將班級、課程、教師、上課時間以及教室等元素進行科學(xué)的組合，在此基礎(chǔ)上形成課表。通常情況下，高職院校一周的上課時間的五天，每天課程為八節(jié)，采用兩節(jié)連排的方式。因此可以將兩節(jié)課視作一個時間段，基于此，每周的時間段的數(shù)量為20。在具體編碼的過程中，可以利用數(shù)字對上述五個元素進行編碼，即可獲得相應(yīng)的班級號、教師號、課程號、上課時間以及教室號。

（二）種群初始化

在完成基因編碼之后，就需要進行種群初始話，在此基礎(chǔ)上一代代進化下去，直到根據(jù)進化停止準(zhǔn)則終止進化。根據(jù)這一流程，高職院校排課過程中，需要利用計算機生成一定數(shù)量的排課方案，這樣一來，不同的班級就可以獲得多個隨機的班級一教師—課程一上課時間一教師編碼，之后篩選出其中不重復(fù)的個體填充到數(shù)組中，獲得不同班級的初始課程表。最后對所有班級的初始課程表進行綜合，形成初時種群。

（三）構(gòu)建適應(yīng)函數(shù)

在遺傳算法中，適應(yīng)度值決定了不同個體在種群中的好壞程度，適應(yīng)度值是下一代種群選取的重要依據(jù)。因此在高職院校排課過程中，為了保障適應(yīng)度值計算的合理性和可靠性，必須構(gòu)建科學(xué)的適應(yīng)度函數(shù)，這樣才有利于找到最優(yōu)解。在設(shè)置適應(yīng)函數(shù)的過程中，需要參考各項約束條件。對于一個排課方案而言，若是其中存在沖突，表明其不可行，則其適應(yīng)度為0，從而被淘汰。對于一個班級而言，同一課程的間隔越長，則適應(yīng)度值越高。同時，專業(yè)類課程設(shè)置在上午、實踐課程設(shè)置在下午的適應(yīng)度值相對更高。

綜上所述，可以構(gòu)建以下適應(yīng)度函數(shù)：

Fn=Y*（x1*K+x2*S+x3*J）

在該適應(yīng)函數(shù)中，Y為沖突檢查結(jié)果，K為課表優(yōu)化中課程時間間隔、s為課程理想時段、J為教師上課要求，x1、x2、x3則分別代表著各期望值在總期望值中所占的比重。

以上述函數(shù)對不用排課方案的適應(yīng)度值進行計算，適應(yīng)度值越高，則表明該排課方案的合理性越高。

（四）遺傳算子的設(shè)計

首先，選擇。通過適應(yīng)函數(shù)計算獲得適應(yīng)度值，通過適應(yīng)度值的比對可以從中選擇出適應(yīng)度較高的個體。具體可以采用輪盤賭的方法，將適應(yīng)度值按照一定的比例轉(zhuǎn)化為概率，通過模擬輪盤賭的方式堆積獲得多個隨機數(shù)，將其與計算獲得的不同個體的概率進行對比，以此判斷該個體是被遺傳還是被淘汰。

其次，交叉。在進行交叉操作之前，需要將所有的排課方案按照一定的順利進行排列，根據(jù)選擇操作的結(jié)果選擇兩條染色體作為父個體，具體是通過將對應(yīng)班級的上課時間和上課教室進行交叉即可獲得新的染色體。

最后，變異。變異運算是使用其他等位基因?qū)€體染色體編碼串中的某些基因進行替換，獲得新的個體。延伸到排課過程中，是將種群中隨即選取個體的時間或是教室進行改變，之后檢查是否存在沖突，若是則繼續(xù)進行變異。

（五）遺傳進化終止規(guī)則

隨著遺傳運算的不斷深入，各代種群的優(yōu)良基因?qū)⒉粩嗬鄯e，在此過程中，種群平均適應(yīng)度和個體適應(yīng)度也將呈現(xiàn)出不斷上升的趨勢，同時，求解結(jié)果也逐漸向目標(biāo)值靠近。當(dāng)這一過程達到一定程度，必須通過一定的終止規(guī)則對其進行收斂。在高職院校排課過程中，可以適當(dāng)?shù)貐⒖歼z傳算法中常用的終止規(guī)則設(shè)計與之相適應(yīng)的終止規(guī)則，具體內(nèi)容如下：

首先，當(dāng)種群中個體最大適應(yīng)度超出預(yù)先設(shè)定值時，停止排課。其次，當(dāng)種群的平均的適應(yīng)度值超出預(yù)先設(shè)定值時，停止排課。最后，當(dāng)遺傳世代數(shù)超過預(yù)先設(shè)定值時，停止排課。

綜上所述，遺傳算法具有自適應(yīng)、隨機搜索、高度并行等特殊優(yōu)勢，能夠有效地適應(yīng)多約束條件的排課問題優(yōu)化。

（六）遺傳算法性能分析

為了驗證上述遺傳算法的應(yīng)用效果，將其應(yīng)用到了某高職院校信息工程系2016～2017學(xué)年第一學(xué)期的排課活動中。

通過對迭代次數(shù)的比較，當(dāng)交叉概率為0.6時，變異概率為0.02條件下種群的個體適應(yīng)度趨于穩(wěn)定。同時，當(dāng)交叉概率為0.5時，變異概率0.01條件下種群個體適應(yīng)趨于穩(wěn)定。通過數(shù)據(jù)比對發(fā)現(xiàn)，不同種群規(guī)模下，通過遺傳算法獲得的適應(yīng)度迭代次數(shù)都低于普通算法，說明遺傳算法的搜索性能更加強大。

從運算消耗的時間來看，遺傳算法在種群規(guī)模明確的情況下，迭代次數(shù)越多，所要消耗的時間也會隨之增長，與此同時產(chǎn)生的高適應(yīng)度個體數(shù)量也越來越多。在迭代次數(shù)相同的情況下，遺傳算法所消耗的時間更少，且產(chǎn)生的高適應(yīng)度個體數(shù)量則更多。此外，高適應(yīng)度個體的數(shù)量在迭代次數(shù)超過200之后開始趨于穩(wěn)定。

結(jié)語

綜上所述，隨著高職院校規(guī)模的不斷擴大以及專業(yè)課程的增加，其排課活動涉及的問題也逐漸增加。為了提升教學(xué)活動安排的合理性，本文充分考慮到了現(xiàn)階段高職院校教學(xué)活動特點、教學(xué)模式以及人才培養(yǎng)目標(biāo)，基于遺傳算法構(gòu)建了高職院校排課系統(tǒng)，有效提升了排課工作的效率和質(zhì)量，促進了我國高職院校教學(xué)計劃合理性的提升。