高冬梅 陳利科

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

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

引言

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

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

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

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

1.1遺傳算法步驟

1.1.1課表的染色體編碼：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

硬約束條件：

（1）同一個(gè)老師在同一時(shí)間不能授課兩門課程。

（2）同一地點(diǎn)在同一時(shí)間不能安排兩門課程。

（3）同一班級(jí)在同一時(shí)間不能安排兩門課程。

軟約束條件：

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

（1）盡量滿足個(gè)別老師的特殊上課時(shí)間、地點(diǎn)。

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

（3）班級(jí)課程相鄰的地點(diǎn)盡量距離較近，以免學(xué)生課間不能按時(shí)到課。

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

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

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

排課的基本步驟：

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

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

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

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

解決的問題：

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

（2）說明排課問題中的制約因素和常用的約束條件，分析排課問題的求解難點(diǎn)和目標(biāo)。

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

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

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

4.結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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