高冬梅 陳利科

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

關(guān)鍵詞： 遺傳算法 適應(yīng)度函數(shù)設(shè)計 遺傳算子設(shè)計

引言

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

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

1.遺傳算法的設(shè)計

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

1.1遺傳算法步驟

1.1.1課表的染色體編碼：

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

1.1.2適應(yīng)度函數(shù)的設(shè)計：

遺傳算法通常基于適應(yīng)度值進行遺傳操作，合理的適應(yīng)度函數(shù)能夠?qū)⒏鱾€個體的優(yōu)劣程度充分、準確地體現(xiàn)出來，使得遺傳算法能夠在目標空間中盡快找到最優(yōu)解。一般而言，適應(yīng)度函數(shù)是由目標函數(shù)變換而成的，基本有以下3種：

（1）直接由待求解的目標函數(shù)轉(zhuǎn)化為適應(yīng)度函數(shù)。

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

（3）若目標函數(shù)為最小化問題或最大化問題，則適應(yīng)度函數(shù)分別為：

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

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

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

1.1.3遺傳算子的設(shè)計：

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

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

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

2.排課過程中出現(xiàn)的問題

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

硬約束條件：

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

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

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

軟約束條件：

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

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

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

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

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

3.排課系統(tǒng)的實現(xiàn)

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

排課的基本步驟：

（1）根據(jù)開課計劃對開課數(shù)據(jù)進行處理。為了實現(xiàn)排課，需要對原始的數(shù)據(jù)（開課計劃與課程設(shè)置）進行加工，單獨的數(shù)據(jù)產(chǎn)生關(guān)聯(lián)，生成一些有效的數(shù)據(jù)。

（2）對課程的資源結(jié)構(gòu)進行系統(tǒng)分析。對排課的主體對象及排課資源編成可適用的遺傳算法使用的編碼進行運算。通過算法，得出排課系統(tǒng)近似最優(yōu)解。

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

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

解決的問題：

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

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

（3）設(shè)計排課系統(tǒng)的數(shù)據(jù)資源模型。

（4）排課遺傳算法的設(shè)計求解及實現(xiàn)。

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

4.結(jié)語

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

參考文獻：

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

[2]陸峰，李新.自動排課系統(tǒng)算法的設(shè)計與實現(xiàn)[J].微機發(fā)展，2005，15（11）：2.

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

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

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