遺傳算法在排課系統(tǒng)中的優(yōu)化研究

葉碧蝦

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

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

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

1 排課問(wèn)題的算法設(shè)計(jì)

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

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

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

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

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

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

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

1.2 排課問(wèn)題的GATS算法設(shè)計(jì)

(1)GA編碼

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

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

圖1 染色體編碼

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

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

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

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

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

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

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

(4)GA的運(yùn)行

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

①選擇操作

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

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

圖2 輪盤賭選擇

②交叉操作

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

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

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

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

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

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

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

圖3 交叉算子操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟7:選擇操作.

步驟8:交換操作.

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

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

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

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

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

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

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

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

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

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

本文是采用終止優(yōu)先級(jí)原則，對(duì)(2)、(5)取短時(shí)優(yōu)先原則，即哪個(gè)快就哪個(gè)先停，然后再?gòu)闹信袛嗍欠裼袃?yōu)秀個(gè)體存在.

2 實(shí)例研究

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

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

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

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

班級(jí)集合:C={C1，C2，C3，…，Cnc}

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

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

時(shí)間集合:P={P1，P2，P3，…，Pnp}

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

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

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

(1)排課中約束的描述

一個(gè)班級(jí)在同一時(shí)間只能安排一門課.

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

必有

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

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

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

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

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

在排課問(wèn)題中，我們假設(shè)有n個(gè)決策變量參數(shù)、m個(gè)目標(biāo)函數(shù)和p個(gè)約束條件，目標(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)決定了決策向量的取值范圍，反映了排課問(wèn)題中的編排規(guī)則.

2.2 總體目標(biāo)

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

圖4 生成課表

3 結(jié)束語(yǔ)

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

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

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

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

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

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

［5］Alan Dix，蔡利棟，方思行譯＞人機(jī)交互［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é)計(jì)算機(jī)與信息管理中心.清華大學(xué)綜合教務(wù)系統(tǒng)簡(jiǎn)介［R］.2005:96～98.

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