基于遺傳算法的高校排課問題探討

劉 騰，吳仁協(xié)，李 毅

（廣東海洋大學(xué)1.教務(wù)處；2.水產(chǎn)學(xué)院，廣東 湛江524088）

排課是高校的重要教務(wù)管理工作，關(guān)系到高校教學(xué)秩序。從20世紀(jì)50年代末期開始，國外一些學(xué)者開始探討排課問題，1963年Gotlieb率先提出時(shí)間表問題的數(shù)學(xué)模型[1]，1999年Safaai和Sigeru采用遺傳算法解決在教室不足情況下如何合理分配教師和利用教室資源的排課問題[2]。從20世紀(jì)80年代初期開始，國內(nèi)開始研究運(yùn)用數(shù)學(xué)和運(yùn)籌學(xué)方法、人機(jī)交互方法、基于人工智能方法、基于啟發(fā)式算法等解決排課問題的方法[3]。高校經(jīng)歷了從模擬手工排課到運(yùn)用人工智能構(gòu)建專家系統(tǒng)或決策支持系統(tǒng)排課的過程，這些方法都是輔助排課工具，還不能完全替代人工排課。

近年來，隨著國內(nèi)高校規(guī)模越來越大、課程越來越多。雖然高校的教學(xué)條件得到了很大的改善，但是教學(xué)資源仍然有限，排課壓力很大。在排課過程中，不僅要有效地利用各種教學(xué)資源，而且還要避免班級(jí)、教師、課程、時(shí)間、教室等排課要素之間發(fā)生沖突。如何編排科學(xué)、合理的課表，是排課人員面臨的一項(xiàng)重大課題。隨著計(jì)算機(jī)技術(shù)和人工智能的迅速發(fā)展，遺傳算法廣泛用于求解排課問題。遺傳算法是美國Holland教授于1975年最先提出的一種模擬自然界生物進(jìn)化過程的全局優(yōu)化搜索算法[4]，能夠通過計(jì)算機(jī)科學(xué)技術(shù)使初始解逐漸逼近最優(yōu)解或準(zhǔn)最優(yōu)解。遺傳算法具有良好的并行性、通用性、穩(wěn)定性，是求解排課問題的一種有效方法。本文探索利用遺傳算法求解排課問題的策略，以優(yōu)化排課系統(tǒng)和提高排課效率。

1 排課問題分析

求解排課問題的實(shí)質(zhì)是消除在多約束條件下的資源沖突，優(yōu)化課程、班級(jí)、教師、教室和時(shí)間等要素之間的組合。

1.1 排課的約束條件

求解排課問題受到多種條件的約束，以避免約束條件之間發(fā)生沖突。約束條件包括硬約束和軟約束。硬約束是不可違反的約束條件，是排課過程中必須滿足的條件，它決定排課方案的可行性，決定班級(jí)、教師、教室等因素之間是否相容。軟約束條件影響排課的合理性和教師對(duì)排課的滿意度，既是為了優(yōu)化排課方案而設(shè)置的條件，也是衡量排課方案優(yōu)劣的標(biāo)準(zhǔn)。軟約束條件包括授課時(shí)間的合理性、教師和班級(jí)行課的均衡性等，同時(shí)也包括個(gè)別教師對(duì)排課提出的特殊要求。在排課過程中，先滿足硬約束條件，再滿足軟約束條件。

1.2 排課問題求解的數(shù)學(xué)模型

為了方便求解，將排課問題用數(shù)學(xué)模型進(jìn)行描述。設(shè)學(xué)校的課程為li，班級(jí)為ci，任課教師為pi，教室為ri，授課時(shí)間為 ti。則課程集合為：L={l1，l2，l3，…，li}；班級(jí)集合為：C={c1，c2，c3，…，ci}；教師集合為：P={p1，p2，p3，…，pi}；教室集合為：R={r1，r2，r3，…，ri}；時(shí)間集合為：T={t1，t2，t3，…，ti}。教室-時(shí)間對(duì)的笛卡爾積為：D=R×T={(r1,t1),(r2，t2)，(r3,t3)，…，(ri,ti)}。 設(shè)課程周學(xué)時(shí)為 wi，則課程 li的屬性集合為：li={wi，ci，pi，ri，ti}。課程、班級(jí)、任課教師在排課之前已經(jīng)安排好，為已知變量，則排課問題的求解過程轉(zhuǎn)換為確定每門課程的授課教室、授課時(shí)間的過程。

1.3 排課問題的組合爆炸效應(yīng)和不確定性

排課問題的求解是一個(gè)典型的組合規(guī)劃問題。只要制約排課的因素發(fā)生變化，必然導(dǎo)致課程表的編排方案數(shù)急劇增加，形成排課組合爆炸效應(yīng)。具體來講，只要調(diào)整任何一門課程，必然導(dǎo)致其他課程表的數(shù)據(jù)發(fā)生變化，排課問題更加復(fù)雜，難以獲得排課問題的最優(yōu)解。因此，求解排課問題的關(guān)鍵是縮小搜索空間，并采取適當(dāng)?shù)拇胧?，以抑制“組合爆炸”效應(yīng)。同時(shí)，不追求排課問題的“單個(gè)絕對(duì)最優(yōu)”解，降低衡量課表滿意度的標(biāo)準(zhǔn)，只追求獲得一套完整的、無任何硬性約束條件沖突的課表，并符合人們主觀規(guī)定的軟約束條件。

1.4 排課問題的求解目標(biāo)

排課問題被認(rèn)為是一個(gè)多目標(biāo)的、帶有模糊約束條件的、資源有限的組合優(yōu)化問題[5]。多目標(biāo)是指在排課可行解域中的排課組合方案是一個(gè)集合，不容易達(dá)到“單個(gè)絕對(duì)最優(yōu)”方案。模糊約束條件是指各學(xué)校的排課軟約束條件不盡相同，很難滿足所有的約束條件，且軟約束條件難以用數(shù)學(xué)公式表示。資源有限是指教師、教室、時(shí)間等教學(xué)資源有限。因此，在排課組合規(guī)劃問題中，除了必須完全滿足硬約束條件外，應(yīng)以 “科學(xué)、合理、人性化”的要求作為優(yōu)化排課方案的目標(biāo)，不必追求“單個(gè)絕對(duì)最優(yōu)”方案。因此，排課問題求解應(yīng)達(dá)到兩個(gè)目標(biāo)，一是課表無硬性約束條件沖突，二是盡量滿足軟約束條件。

2 排課問題的遺傳算法設(shè)計(jì)

2.1 排課問題的基因編碼

遺傳算法是利用基因編碼技術(shù)和繁殖機(jī)制，從一個(gè)隨機(jī)產(chǎn)生的初始種群（初始解）開始，通過若干代的種群迭代實(shí)現(xiàn)對(duì)復(fù)雜問題的求解[6]。運(yùn)用遺傳算法求解排課問題的關(guān)鍵是對(duì)排課問題進(jìn)行編碼。編碼質(zhì)量關(guān)系到有效遺傳信息表達(dá)的完備性，并影響算法的計(jì)算效率。課表編排是對(duì)課程安排合適的授課時(shí)間和授課教室。課程是課程號(hào)、課程名稱、授課周學(xué)時(shí)數(shù)、授課教師、授課班級(jí)等構(gòu)成的信息集合，可用“課程—教師—班級(jí)”組合體表示待排課程信息。用一個(gè) “課程—教師—班級(jí)”和“時(shí)間”的二維矩陣進(jìn)行編碼，在排課中將“教室”安排到“課程—教師—班級(jí)”和“時(shí)間”的二維矩陣中。

2.2 初始種群和適應(yīng)度函數(shù)的設(shè)計(jì)

產(chǎn)生初始種群的具體步驟如下。第一，對(duì)于“課程—教師—班級(jí)”組合，隨機(jī)產(chǎn)生課程的授課時(shí)間；第二，將授課班級(jí)的學(xué)生人數(shù)由小到大排列；第三，按照教室容量從小到大編排教室編號(hào)；第四，根據(jù)教室編號(hào)搜索教室，系統(tǒng)選取當(dāng)前可用、教室容量足夠大且最接近授課班級(jí)人數(shù)的教室；第五，重復(fù)以上操作，直至所有課程排完為止。依據(jù)這種方式產(chǎn)生的初始種群，班級(jí)學(xué)生人數(shù)與教室容量之間盡可能接近，以盡量滿足軟約束條件。在課程編排過程中，還要對(duì)約束條件之間是否發(fā)生沖突進(jìn)行檢測(cè)，以獲得滿足全部硬約束條件的可行初始解。

適應(yīng)度函數(shù)是指度量個(gè)體優(yōu)劣程度的函數(shù)。適應(yīng)度函數(shù)設(shè)計(jì)質(zhì)量直接影響遺傳算法的迭代方向、收斂速度，甚至影響能否獲得滿足目標(biāo)的最優(yōu)解[7]。為了能夠獲得合理、可行、滿意的課程表，盡量利用相關(guān)經(jīng)驗(yàn)和常識(shí)進(jìn)行編排課表。而“相關(guān)經(jīng)驗(yàn)和常識(shí)”是模糊的，且具有不確定性。此外，涉及諸多要素和約束條件，很難判斷課程表編排的優(yōu)劣。為了更好地判斷一個(gè)課程表的優(yōu)劣程度，必須根據(jù)課程表的適應(yīng)度值進(jìn)行評(píng)價(jià)。適應(yīng)度函數(shù)為：

Fitness=(A×wl+(b×ql+c×q2)×w2)×d×e。

其中表示當(dāng)前組合方案的教師上課節(jié)次優(yōu)度的平均值A(chǔ)=(a1+a2+a3+…+an)/n，b為上課日組合優(yōu)度，c為上課節(jié)組合優(yōu)度，d為課表分布優(yōu)化度，e為組合可行度，q1和q2分別為上課日組合優(yōu)度和上課節(jié)組合優(yōu)度各占的權(quán)重，q1+q2=1；w1和w2為節(jié)次優(yōu)度和組合優(yōu)度各占的權(quán)重，w1+w2=1。

2.3 選擇操作、交叉操作和變異操作

選擇操作采用輪盤賭的方法。輪盤賭的選擇方法與博彩游戲的輪盤賭原理類似，整個(gè)輪盤被分為不同比例的扇形區(qū)域，分別對(duì)應(yīng)種群中各個(gè)個(gè)體。隨機(jī)轉(zhuǎn)動(dòng)輪盤，直到輪盤自然停下，指針?biāo)傅纳让娲淼膫€(gè)體則是選擇出來的個(gè)體。在輪盤賭過程中，“不同比例的扇形區(qū)域”中的“比例”是按照個(gè)體適應(yīng)度的大小來分配的，輪盤中面積越大的區(qū)域的個(gè)體適應(yīng)度越高，被遺傳到下一代的概率就越大。相反，輪盤中面積越小的區(qū)域的個(gè)體適應(yīng)度越低，被淘汰的概率越大。

交叉操作是遺傳算法中最重要的操作，在遺傳算法中起核心作用。借助交叉算子可以產(chǎn)生新的個(gè)體。本文采用單點(diǎn)交叉操作方法。第一步，將經(jīng)過選擇操作后產(chǎn)生的個(gè)體進(jìn)行隨機(jī)配對(duì)；第二步，隨機(jī)選定一個(gè)交叉點(diǎn)，該點(diǎn)將兩個(gè)父本個(gè)體的基因串分成前后兩部分，執(zhí)行交叉操作，該點(diǎn)前后兩個(gè)父本個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并產(chǎn)生兩個(gè)新的子代個(gè)體。

在遺傳算法中，變異改變種群個(gè)體模型值，維持種群的多樣性。繁重搜索陷入局部次優(yōu)解，有效抑制遺傳算法產(chǎn)生的不成熟收斂現(xiàn)象。本文采用逆轉(zhuǎn)變異方法，在父本個(gè)體基因串中隨機(jī)挑選兩個(gè)逆轉(zhuǎn)點(diǎn)，然后將這兩個(gè)逆轉(zhuǎn)點(diǎn)間的基因值以逆序排列。

3 排課結(jié)果分析

通過對(duì)某高校的排課數(shù)據(jù)進(jìn)行遺傳算法實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明所有課程均能根據(jù)教學(xué)任務(wù)要求安排在合適的上課時(shí)間和教室，沒有發(fā)生課表沖突現(xiàn)象，符合學(xué)生及教師的上課要求，排課結(jié)果滿足了所有硬約束條件和軟約束條件，排出的課表可行、合理、有效。因此，基于遺傳算法的排課問題求解可行，能夠得到令人滿意的課程表。

4 結(jié)語

本文針對(duì)排課問題進(jìn)行了詳細(xì)分析，并根據(jù)排課問題的特點(diǎn)建立數(shù)學(xué)模型，探討基于遺傳算法求解排課問題的應(yīng)用方法，并通過實(shí)驗(yàn)證明遺傳算法運(yùn)用于高校排課系統(tǒng)的可行性，且能最大程度地減少排課人員的工作量，有效地提高了工作效率和排課效果。排課問題是一個(gè)復(fù)雜的多目標(biāo)組合優(yōu)化問題，影響因素多、且數(shù)據(jù)量龐大。目前國內(nèi)高校普遍實(shí)行學(xué)分制改革，所開設(shè)課程數(shù)量大幅度增加，排課問題更加復(fù)雜。因此，今后有必要進(jìn)一步探索和改進(jìn)高校排課系統(tǒng)設(shè)計(jì)，以滿足在學(xué)分制條件下的排課需求。