遺傳算法在高職院校排課問題中的研究與應用

梁利亭

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

[關鍵詞]遺傳算法;高職院校;排課

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

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

前言

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

一、遺傳算法概述

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

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

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

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

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

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

4.遺傳算法具有自組織、自適應以及自學習性。通過遺傳算法對進化過程中獲得的信息進行自行組織搜索時，個體的適應度越大，其生存概率也就越高，并獲得更適應環境的基因結構。

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

6.遺傳算法本身采用了動態自適應技術，因此可以通過自動調整算法對進化過程中的參數以及編碼精度進行控制。

目前，遺傳算法廣泛應用許多學科，函數優化和組合優化是其應用的兩個主要領域。現如今，人們構造除了許多形式復雜的測試函數，這類函數具有非線性、多模型以及多目標的特征，在對其優化問題進行研究時需要應用遺傳算法。同時，隨著問題規模的增大，組合優化問題的搜索空間也隨之擴張，面對復雜問題的求解，遺傳算法也是最優化的工具。

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

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

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

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

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

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

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

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

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

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

遺傳算法是模仿達爾文的生物進化理論對復雜的優化問題進行求解。

（一）基因編碼

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

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

（二）種群初始化

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

（三）構建適應函數

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

綜上所述，可以構建以下適應度函數：

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

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

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

（四）遺傳算子的設計

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

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

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

（五）遺傳進化終止規則

隨著遺傳運算的不斷深入，各代種群的優良基因將不斷累積，在此過程中，種群平均適應度和個體適應度也將呈現出不斷上升的趨勢，同時，求解結果也逐漸向目標值靠近。當這一過程達到一定程度，必須通過一定的終止規則對其進行收斂。在高職院校排課過程中，可以適當地參考遺傳算法中常用的終止規則設計與之相適應的終止規則，具體內容如下：

首先，當種群中個體最大適應度超出預先設定值時，停止排課。其次，當種群的平均的適應度值超出預先設定值時，停止排課。最后，當遺傳世代數超過預先設定值時，停止排課。

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

（六）遺傳算法性能分析

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

通過對迭代次數的比較，當交叉概率為0.6時，變異概率為0.02條件下種群的個體適應度趨于穩定。同時，當交叉概率為0.5時，變異概率0.01條件下種群個體適應趨于穩定。通過數據比對發現，不同種群規模下，通過遺傳算法獲得的適應度迭代次數都低于普通算法，說明遺傳算法的搜索性能更加強大。

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

結語

綜上所述，隨著高職院校規模的不斷擴大以及專業課程的增加，其排課活動涉及的問題也逐漸增加。為了提升教學活動安排的合理性，本文充分考慮到了現階段高職院校教學活動特點、教學模式以及人才培養目標，基于遺傳算法構建了高職院校排課系統，有效提升了排課工作的效率和質量，促進了我國高職院校教學計劃合理性的提升。