遺傳算法在高校教務排課系統中的應用研究

高冬梅 陳利科

摘 要： 遺傳算法是一種借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。針對高職院校課表的特點，本文詳細分析遺傳算法在排課系統中的基本思想及遺傳算法的設計步驟，主要論述了利用遺傳算法求解高職院校課表的編排問題，提出了應用遺傳算法解決排課問題的有效方法。

關鍵詞： 遺傳算法 適應度函數設計 遺傳算子設計

引言

隨著我國職業教育事業的迅速發展，高職院校辦校規模的不斷擴大，教學資源越來越緊張，高校教學單位和課程眾多，教師和教室短缺，使得教務管理系統中的排課模型的難度增加。雖然每個學校都不盡相同，但在教學排課中出現的實質問題仍需要綜合考慮。即課程、教師、多媒體教室、機房實訓室、課程和時間等變量中諸多資源的合理利用、優化配置、以教學計劃和各種特殊要求為制約條件的組合規劃問題。傳統的手工排課易于出錯且非常麻煩，針對這一復雜問題，許多學校都提出如模擬退火、列表尋優搜索、遺傳算法等方法。

遺傳算法是一種借鑒生物界自然遺傳機制和自然選擇的隨機化搜索算法。它的主要特點是直接對結構對象進行操作，不存在函數連續性和求導的限定；采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，適當地調整搜索方向，不需要確定的規則，具有內在的并行性和更好的全局尋優能力。針對高職院校課表的特點，本文提出了應用遺傳算法解決排課問題的方法，即利用遺傳算法解決排課問題。只要給出目標函數的計算規則，更少地依賴于實際問題的情況，就能實現課表的優化。實驗表明，遺傳算法結構清晰，思路簡潔，效率較高，作為一種有效的求解最優算法，其可以有效地解決排課問題。

1.遺傳算法的設計

遺傳算法的基本原理是，采用某種編碼方式將解空間映射到編碼空間，每個編碼對應問題的一個解，一般通過隨機方法確定一個初始種群，在種群中根據適應度值或某種機制選擇個體，用各種遺傳操作算子產生下一代，反復計算，直到滿足期望的終止條件，產生最優解。

1.1遺傳算法步驟

1.1.1課表的染色體編碼：

由于遺傳算法通常不直接作用于問題的解空間，而利用解的某種編碼表示進行進化，將實際問題中的課表轉化為計算機可以識別的變量。同時考慮到高職院校課表的時間制度每周5天，每天最多8節課，程序中采用長度為20的二進制編碼表示課表基因。1表示1次課（2節），0表示沒有課。其記錄了不同時間段每個老師要上課的次數，就樣就建立了老師與班級、課程之間的聯系。

1.1.2適應度函數的設計：

遺傳算法通常基于適應度值進行遺傳操作，合理的適應度函數能夠將各個個體的優劣程度充分、準確地體現出來，使得遺傳算法能夠在目標空間中盡快找到最優解。一般而言，適應度函數是由目標函數變換而成的，基本有以下3種：

（1）直接由待求解的目標函數轉化為適應度函數。

（2）若目標函數為最小化問題，則：

（3）若目標函數為最小化問題或最大化問題，則適應度函數分別為：

Fit（f（x））=1/（1+c+f（x））

Fit（f（x））=1/（1+c-f（x））

其中，c為函數界限的保守估計值。

1.1.3遺傳算子的設計：

（2）交叉算子：所謂交叉運算，是指對兩個相互配對的染色體依據交叉概率Pc，按某種方式相互交換其部分基因，從而形成兩個新的個體。

由于存在一個老師講授多個班級的課或合班上課的情況，為避免沖突的產生，在交叉算子執行后，必須對新產生的染色體進行沖突檢驗。如：在N1個老師中隨機選取一個老師，對他的時間安排進行單點交叉操作，或者在N2個授課班級中隨機選取一個班級，對授課班級的時間安排進行單點交叉操作。

（3）變異算子：變異操作發生在同一個染色體中的兩個基因位之間，即在所選的變異個體中隨機產生一個行，在該行中任選兩個基因編碼進行互換。產生新的個體的輔助方法，保證種群的多樣性，能有效地抑制遺傳算法早熟現象的發生。在交叉運算和變異運算的相互配合中，共同完成對搜索空間的全局搜索和局部搜索。本文采用的是：首先隨機生成1-5中的兩個數，（對應星期一到星期五），表示為要交換的時間段，若生成的兩個數不同則交換這兩個時間段所有授課班級的課程，交換后進行檢測和處理。

2.排課過程中出現的問題

在排課中要對班級、教師、教室、課程和時間五個相制約的因素進行安排。就要滿足“多頭課、一師多班、多學時”等條件，要想處理好這些排課中出現的問題，我們就要把這些需要滿足的條件歸納為硬約束條件和軟約束條件。

硬約束條件：

（1）同一個老師在同一時間不能授課兩門課程。

（2）同一地點在同一時間不能安排兩門課程。

（3）同一班級在同一時間不能安排兩門課程。

軟約束條件：

目前大多數高職院校校區不集中，分散班分教學，課程安排較集中，實訓課與理論課分開行課。

（1）盡量滿足個別老師的特殊上課時間、地點。

（2）班級課表在一周的上課時間分布均勻，避免有一天沒有課的情況，每天的第一節課不能為自習課。

（3）班級課程相鄰的地點盡量距離較近，以免學生課間不能按時到課。

（4）每一門課程在一周內的上課時間分布合理，讓學生在學與練之間能夠有充足的時間。

3.排課系統的實現

高職院校教學管理系統中的排課系統功能的主要功能包括：開課計劃、課程設置、手動排課、自動排課、課表查詢、課表打印、系統維護等，為了使整個排課系統的功能更合理、更優化，要完成以下操作。

排課的基本步驟：

（1）根據開課計劃對開課數據進行處理。為了實現排課，需要對原始的數據（開課計劃與課程設置）進行加工，單獨的數據產生關聯，生成一些有效的數據。

（2）對課程的資源結構進行系統分析。對排課的主體對象及排課資源編成可適用的遺傳算法使用的編碼進行運算。通過算法，得出排課系統近似最優解。

（3）運用遺傳算法對排課進行求解。排課問題進行編碼后，為求得出最優化結果，要經過選擇、交叉、變異等操作。

（4）用算法解碼處理。對得出的最優化結果的編碼進行“翻譯”，得出排課的結果，形成課表。

解決的問題：

（1）詳細分析遺傳算法的設計步驟及基本思想。

（2）說明排課問題中的制約因素和常用的約束條件，分析排課問題的求解難點和目標。

（3）設計排課系統的數據資源模型。

（4）排課遺傳算法的設計求解及實現。

（5）用ASP.NET實現交互界面，以C#為腳本，采用SQL Server2005為后臺數據庫，對主要的算法進行實現。

4.結語

本文主要論述了利用遺傳算法求解高職院校課表的編排問題，詳細分析了遺傳算法和排課問題。以遺傳算法理論研究為擇指導，結合高校排課的具體要求，針對大部分高校的教學管理模式和教學資源的配置情況進行了具體分析，數據采用的染色體編碼和適應度值是合理的，不存在課表沖突問題，在對待特殊的課程安排上，完全達到排課人員的期望。遺傳算法對系統中排課的方法給予了具體的實現，使高校教務管理工作趨于網絡化、智能化的管理。

參考文獻：

[1]傅學芳.現代優化計算方法——遺傳算法簡介[J].昌灘師專學報，2001，20（2）：42-46.

[2]陸峰，李新.自動排課系統算法的設計與實現[J].微機發展，2005，15（11）：2.

[3]陳國良.遺傳算法及其應用[M].北京：人民郵電出版社，2004：35-48.

[4]王小平，曹立明.遺傳算法[M].西安：西安交通大學出版社，2004：30-87.

基金項目：河北省廊坊市科技局2013年立項課題（201301025）