葉碧蝦

(漳州職業(yè)技術(shù)學(xué)院計算機工程系，福建 漳州 363000)

課程表針對高校教學(xué)計劃進(jìn)行了時間安排，是學(xué)校教學(xué)工作的指揮調(diào)度表，對學(xué)校其他工作的安排也有直接影響.對課表編排問題的數(shù)學(xué)模型、解的存在性以及計算機求解算法等問題國外研究人員是從20世紀(jì)50年代就開始進(jìn)行了研究，但由于實際教學(xué)活動中各種復(fù)雜的約束條件而使相關(guān)算法無能為力［1］.對排課問題的研究國內(nèi)始于上世紀(jì)90年代初期，當(dāng)時的系統(tǒng)都是模擬手工排課過程，以“班”為單位，采用啟發(fā)式函數(shù)來進(jìn)行編排的，但是這些課表編排系統(tǒng)比較依賴于各個學(xué)校的教學(xué)體制，不宜于廣泛推廣［2］.

目前，國內(nèi)解決排課問題的主要方案大體可分為:(1)基于傳統(tǒng)數(shù)學(xué)和運籌學(xué)方法，但隨著問題規(guī)模的擴大，這類方法就越難求解;(2)人—機交互方法，但這種半自動化的方式還是太過于耗時和耗工作量;(3)人工智能方法和基于啟發(fā)式算法的方法，人工智能在各領(lǐng)域的應(yīng)用已經(jīng)很廣泛，在解決排課問題中主要采用約束滿足和專家系統(tǒng)，而啟發(fā)式算法主要是采用模擬退火算法、遺傳算法、禁忌搜索算法.由于遺傳算法(Genetic Algorithm，簡稱GA)是一種適合求解帶有多變量、多參數(shù)、多目標(biāo)和多區(qū)域但連通性較差的智能優(yōu)化算法，因此本文考慮用遺傳算法來解決排課問題，但是遺傳算法具有早熟現(xiàn)象，并且很快收斂到局部最優(yōu)而非全局最優(yōu)解，所以結(jié)合了局部搜索方法之一的禁忌搜索算法(Tabu Search，簡稱TS)，即用遺傳算法結(jié)合禁忌搜索算法來解決大學(xué)排課問題.

1 排課問題的算法設(shè)計

1.1 排課問題的雙目標(biāo)分析

(1)班級課時日分布優(yōu)度的計算

這個指標(biāo)主要是均勻分布班級每日的課時，班級日分布優(yōu)度為:

式中td表示Bi班級在d個工作日所上的課的節(jié)次數(shù);n則表示一周內(nèi)的工作總天數(shù).全校課時分布均勻程度可以用全校所有班級的課時日分布優(yōu)度平均值來評價.

(2)班級日組合優(yōu)度的計算

該優(yōu)度重點用來表示班級課程組合的優(yōu)劣，可以用全校所有班級的所有非2學(xué)時的課程的日組合優(yōu)度的平均值來衡量.

式中，ki表示日組合優(yōu)度;非2學(xué)時課程總數(shù)用n表率;m則表示全校班級總數(shù).

1.2 排課問題的GATS算法設(shè)計

(1)GA編碼

本文采用混合式教師編碼，將它設(shè)定為遺傳算法的基因.基因由班級序號、教師號、課程號、課程特點組成.其中用六位表示教師號，用一位表示班級序號，指該教師教的第幾個班級.用一位表示課程序號，表示教師教的第幾門課程.用三位表示課程特點，用于表示課程的類型，通過這樣的編碼［4］，解決了特定時段教師課程安排和有效分配.系統(tǒng)如果想要得到完善的課程表，則只要按照算法對編碼進(jìn)行各類處理即可.染色體編碼就是把25個時間片(一般大學(xué)的課程工作日從周一到周五，一天最多有十節(jié)課:上午4節(jié)，下午4節(jié)，晚上2節(jié)，上課方式為一個課次兩個相鄰小節(jié)，所以設(shè)定一個課次為一個時間片，一天就可劃分為5個時間片.這樣總共一周可劃分為25個時間片)的基因串組成一個染色體.

我們可以構(gòu)造一個三維矩陣，其中時間片用橫坐標(biāo)表示，縱坐標(biāo)表示教師、課程和教室，而Z坐標(biāo)表示的是班級，如圖1所示.

圖1 染色體編碼

(2)產(chǎn)生初始群體及消除沖突

本文采用的是對隨機生成的初始群體進(jìn)行調(diào)整，使它產(chǎn)生一組沒有教室沖突的個體作為初始群體，同時，將教室利用率作為考查排課系統(tǒng)有效性的一個重要指標(biāo)，通過教室利用率P擴大10倍轉(zhuǎn)為適應(yīng)度值參與進(jìn)化計算.

其中教室占用數(shù)量用usingr(R)表示，上課學(xué)生總數(shù)用number(S)表示.

在GA運行中，沖突在交叉和變異都可能產(chǎn)生，通過引入負(fù)的適應(yīng)度值來降低沖突個體被選入的概率，還能將未消除的沖突記錄下來，并在下次迭代中進(jìn)行消除;對時間段沖突的兩個個體，也可以用一個個體的沖突時間段與其空時間段互換來消除沖突［5］.

(3)定義和計算適應(yīng)度函數(shù)

通過分析前面的雙目標(biāo)，采用如下的適應(yīng)度函數(shù)

e為組合可行度，它只取0、1.管理人員自行定義K1、K2，代表目標(biāo)的重要程度.當(dāng)然，如果需要的話還可以再加入其他的目標(biāo).如何加快算法收斂的速度?運行中每一代產(chǎn)生的沖突將進(jìn)行不完全消除，作為第三個條件，我們可以定義一個負(fù)的權(quán)值與其相對應(yīng).

(4)GA的運行

遺傳算法主要分為選擇、交叉、變異三個基本操作.

①選擇操作

本文采用輪盤賭選擇法種群下一代個體的選擇.傳統(tǒng)的遺傳算法存在初始種群分布不均勻的現(xiàn)象，所以本文先把解空間劃分n個區(qū)域，然后再分別對每個區(qū)域進(jìn)行遺傳的選擇操作，最后再合并這些區(qū)域，從而實現(xiàn)種群的均勻分布.同時采用上一代和新生代最優(yōu)個體類替換新生代的最差個體.這樣便可以保證從遺傳操作開始，新生代中都有目前為止最優(yōu)的個體.

圖2是輪盤賭選擇示意圖，其百分比表示的是被選中區(qū)域的概率.

圖2 輪盤賭選擇

②交叉操作

交叉操作使用部分匹配交叉法，為了確定一個匹配段，它要求隨機選擇兩個交叉點.即首先隨機在兩個父代個體中選擇一個交配區(qū)域，如:

P1=123|456|7890 P2=674|321|5980

對兩個父代交配區(qū)域進(jìn)行交換，將無交配區(qū)不重復(fù)的保留，重復(fù)的用X記，得:

P1=＊＊＊|321|7890 P2=*7*|456|*980

根據(jù)交換位的對應(yīng)關(guān)系用對應(yīng)的值代替子代X的值，從而得到:

P1=654|321|7890 P2=173|456|2980

這種方法最大好處是可以滿足染色體中沒有重復(fù)基因編碼的約束［6］.調(diào)整選課學(xué)生人數(shù)和教室座位人數(shù)間的沖突是交叉算子的首要作用.本文通過兩個個體中對應(yīng)班級的互換來完成交叉操作，首先按相同規(guī)則排序每個排課方案，接著對選擇操作形成配對庫，隨機兩兩配對新復(fù)制產(chǎn)生的個體，最后對個體隨機配對按預(yù)先設(shè)定的交叉概率來決定每對是否需要進(jìn)行交叉操作，若需要，就進(jìn)行交叉產(chǎn)生新位串.交叉算子操作如圖3所示.

圖3 交叉算子操作

③在變異階段用傳統(tǒng)GA進(jìn)行排課的不足

GA變異操作以一定的變異概率隨機找到某一行中的兩個排課單元，交換它們的位置，判斷它們是否滿足教室與課程的沖突，如沖突則重新選擇直到不沖突為止，這樣不會違反與教室相關(guān)的硬約束［7］.變異形式如下:

傳統(tǒng)的GA會造成算法“局部收斂”而非得到全局最優(yōu)解的原因是:GA具有“全局”搜索能力，如果進(jìn)化世代中有個體適應(yīng)度過高，使其被選擇復(fù)制的概率變大，從而使其后代過多以及近親繁殖.因此，對個體以變異概率進(jìn)行變異操作成為必須，這在變異率的選擇上就成了GA算法解決排課問題的關(guān)鍵.

④結(jié)合TS的變異操作

變異算子主要是使個體呈現(xiàn)多樣性，而對于二進(jìn)制編碼，往往采用一個小的變異概率，通過隨機翻轉(zhuǎn)某些位來實現(xiàn).由于TS算法有靈活的記憶功能和藐視準(zhǔn)則，可以得到更優(yōu)個體解，同時跳出局部最優(yōu)［8］，因此我們用TS來代替變異算子.而對于排課問題，因為約束條件相互制約，是無法實現(xiàn)隨機翻轉(zhuǎn)的，所以本文在變異階段用到禁忌搜索算法.

TS的領(lǐng)域定義為相鄰兩次課，我們把每個時間片的相鄰時間片設(shè)為四，把每天的頭尾兩次課定義為相鄰，把一周的頭尾也定義為相鄰.由此，從周一到周五進(jìn)行1到25編號后，領(lǐng)域集可定義如下:

很明顯每個班級課程數(shù)P的領(lǐng)域集為4P個，我們可以提取最佳的p個解做為候選解集.禁忌表長度設(shè)為6，算法結(jié)束條件為k次迭代.TS運行中也要一個概率.

⑤GA與TS相結(jié)合的流程

為了使群體中的個體分布在解空間的大部分區(qū)域，可先用GA進(jìn)行全局搜索，把可能的排課情況都搜索出來，再用TS算法從群體中每個個體課表進(jìn)行局部變異搜索，改善群體的質(zhì)量.下面給出整體結(jié)合的算法流程:

步驟1:給定群體規(guī)模、最大迭代次數(shù)、交換概率、最熟識別等初始參數(shù).

步驟2:確定編碼方式，將t，c，k初始化為0.(t為當(dāng)前迭代次數(shù)，c用來識別最熟現(xiàn)象，k為循環(huán)次數(shù)).

步驟3:隨機產(chǎn)生初始群體，生成N個個體，令XB=第一個個體.

步驟4:將群體中每個個體適應(yīng)值計算出來，設(shè)第一個個體為該代適應(yīng)值最大的個體.

步驟5:若XB=第一個個體，則設(shè)c=c+1;否則將第一個個體值賦給XB，并設(shè)c=0.

步驟6:若c＞最熟識別參數(shù)，將個體按適應(yīng)值從大到小排列，并按比例復(fù)制一部分個體到下一代，其余個體百分百變異，由此產(chǎn)生新一代個體，轉(zhuǎn)到步驟8;否則轉(zhuǎn)到步驟7.

步驟7:選擇操作.

步驟8:交換操作.

步驟9:傳統(tǒng)GA變異操作.

步驟10:若k=10，調(diào)用TS變異操作，改進(jìn)群體點質(zhì)量，并設(shè)k=0;否則轉(zhuǎn)到步驟11.

步驟11:如果t＜T||當(dāng)前時間未超時，設(shè)t=t+1，k=k+1，轉(zhuǎn)到步驟4;否則進(jìn)入步驟12.

步驟12:判斷終止準(zhǔn)則.

算法的終止準(zhǔn)則:

(1)能接受的優(yōu)秀個體被找到.

(2)達(dá)到了預(yù)定進(jìn)化代數(shù).

(3)在前后代數(shù)中適應(yīng)值最高的個體適應(yīng)度無改進(jìn).

(4)最適應(yīng)個體占群體比例達(dá)到預(yù)定的比例.

(5)當(dāng)運行時間達(dá)到我們指定的最大時間時［9］.

本文是采用終止優(yōu)先級原則，對(2)、(5)取短時優(yōu)先原則，即哪個快就哪個先停，然后再從中判斷是否有優(yōu)秀個體存在.

2 實例研究

作者以某高校信息技術(shù)與科學(xué)專業(yè)的排課系統(tǒng)建設(shè)為例，闡述了遺傳算法與禁忌搜索算法相結(jié)合在排課系統(tǒng)研究中的應(yīng)用.

2.1 排課問題的數(shù)學(xué)描述

課表編排將時間、教師、學(xué)生和教室四者進(jìn)行組合規(guī)劃.

在該專業(yè)的排課問題中，需要考慮到五個因素，分別為:

班級集合:C={C1，C2，C3，…，Cnc}

課程集合:L={L1，L2，L3，…，Lnl}

教師集合:T={T1，T2，T3，…，Tnt}

時間集合:P={P1，P2，P3，…，Pnp}

可排課的第i個時間段用Pi類表示，如P1表示周一1、2節(jié)、P10表示周三3、4節(jié).

教室集合:R={R1，R2，R3，…，Rnr}

排課問題的解空間由笛卡爾積L×C×T×P×R的五個元素構(gòu)成，排課問題也可以表示為映射:L→P×R，即為每門課找一個合適的時間和教室.

(1)排課中約束的描述

一個班級在同一時間只能安排一門課.

設(shè) CLi表示 Li這門課的班級主體，設(shè) f(Lm)=(Pxm，Rym)，f(Ln)=(Pxn，Ryn)且 m≠n，則當(dāng)

必有

一個老師在同一時間也只能安排一門課，當(dāng)然，一個教室在同一時間也是只能安排一門課程.表示方式均同上.

教室總數(shù)要求大于同一時間安排的課程總數(shù).

設(shè) f(Lm［i］)=(Pxm［i］，Rym［i］)，且 Pxm［1］=Pxm［1］=Pxm［n］，同時設(shè) count(R)表示全校教室可用數(shù)，則count(R)≥n.

教室容量必須滿足上課學(xué)生人數(shù).用Ri－capacity表示Ri教室所能容納的學(xué)生數(shù).CLi－number表示Li這門課對應(yīng)班級學(xué)生人數(shù).如果 f(Lm)=(Pxm，Rym)，則 CLm－count≤Rym－capacity.

(2)排課中的優(yōu)化解模型

在排課問題中，我們假設(shè)有n個決策變量參數(shù)、m個目標(biāo)函數(shù)和p個約束條件，目標(biāo)函數(shù)約束條件和決策變量間是函數(shù)關(guān)系，則排課最優(yōu)化目標(biāo)如下:

其中 x=(x1，x2，…，xn)∈X，y=(y1，y2，…，yn)∈Y

決策向量用x表示，優(yōu)化目標(biāo)向量用y表示，X，Y分別表示各自的目標(biāo)空間，c(x)決定了決策向量的取值范圍，反映了排課問題中的編排規(guī)則.

2.2 總體目標(biāo)

本文通過對排課的目標(biāo)要求和數(shù)學(xué)模型進(jìn)行分析，認(rèn)為應(yīng)該分為兩部分來求解.(1)我們把排課前已經(jīng)定好把教師、班級、課程這三個因素綁定為一個整體，作為一個元組，并對這個元組隨機分配時間和教室，生成可行課表;(2)運用遺傳算法對排課問題進(jìn)行編碼，用基因和染色體方式表示排課中的各個變量，通過復(fù)制、交叉、變異的優(yōu)化設(shè)計，計算出適應(yīng)度函數(shù).而TS主要用來代替遺傳算法中的變異因子，從而得到比單純用遺傳算法更優(yōu)的個體解，同時跑出局部最優(yōu)，產(chǎn)生新的具有更優(yōu)結(jié)構(gòu)的個體，最終生成有效的課表.結(jié)果如圖4所示:

圖4 生成課表

3 結(jié)束語

本文對遺傳的染色體采用了一種較新的編碼方式，針對排課問題的復(fù)雜性，本文提出了一種雙目標(biāo)的適應(yīng)值計算方式，并有效地在初始種群的產(chǎn)生上進(jìn)行了均勻化設(shè)計.由于遺傳算法本身存在的一些不足:過早的局部收斂，因此采用禁忌搜索算法來代替遺傳算法中的變異因子，設(shè)計了遺傳禁忌搜索算法來解決排課問題.通過測驗和使用，證實了在系統(tǒng)的操作性和搜索速率上，運用本算法有了明顯的提高;數(shù)據(jù)分析也顯示該算法能很好地完成預(yù)期要求，且結(jié)果令人滿意.

由于課表問題具有規(guī)模大、約束條件復(fù)雜、需求不斷變化等特征，本文在排課算法的完善方面還有很多需要努力的地方，如不規(guī)則周次課程的處理、異常狀況突發(fā)的處理、排課結(jié)果的輸出方式以及對算法復(fù)雜度的進(jìn)一步縮小等.今后，在解決排課問題中，本人將更多地考慮研究多算法的融合，并將其定為一個主要的研究方向，繼續(xù)努力.

［1］趙 輝，秦維佳.基于資源匹配的一種大學(xué)排課方法［J］.沈陽工業(yè)大學(xué)學(xué)報，2001，(4):342～344.

［2］李志強，趙衛(wèi)東.排課問題的實現(xiàn)策略與模型［J］.泰山學(xué)院學(xué)報，2004，(6):61～64.

［3］王 璐，邱玉輝.基于協(xié)商的智能排課系統(tǒng)的研究［J］.計算機科學(xué)，2006，33(6):214～217.

［4］王 力.高校通用排課管理信息系統(tǒng)設(shè)計與實現(xiàn)［J］.貴州工業(yè)大學(xué)學(xué)報，1999，28(1):87～90.

［5］Alan Dix，蔡利棟，方思行譯＞人機交互［M］.北京:電子工業(yè)出版社，2006.

［6］S.Daskalaki，T.Birbas.Efficient solutions for a university timetabling problem through integer programming［J］.European Journal of Operational Research，2005，160(1):106 ～120.

［7］D.Abramson.Constructing School Timetable using Simulated Annealing［J］.Sequence and Parallel Algorithm.Management Science.1991，37(1):98～113.

［8］清華大學(xué)計算機與信息管理中心.清華大學(xué)綜合教務(wù)系統(tǒng)簡介［R］.2005:96～98.

［9］王書振.改進(jìn)遺傳算法在調(diào)度領(lǐng)域中的應(yīng)用［D］.西安:西安電子科技大學(xué)，2003.