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

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

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

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

1 排課問題分析

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

1.1 排課的約束條件

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

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

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

1.3 排課問題的組合爆炸效應和不確定性

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

1.4 排課問題的求解目標

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

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

2.1 排課問題的基因編碼

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

2.2 初始種群和適應度函數(shù)的設(shè)計

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

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

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

其中表示當前組合方案的教師上課節(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 選擇操作、交叉操作和變異操作

選擇操作采用輪盤賭的方法。輪盤賭的選擇方法與博彩游戲的輪盤賭原理類似，整個輪盤被分為不同比例的扇形區(qū)域，分別對應種群中各個個體。隨機轉(zhuǎn)動輪盤，直到輪盤自然停下，指針所指的扇面代表的個體則是選擇出來的個體。在輪盤賭過程中，“不同比例的扇形區(qū)域”中的“比例”是按照個體適應度的大小來分配的，輪盤中面積越大的區(qū)域的個體適應度越高，被遺傳到下一代的概率就越大。相反，輪盤中面積越小的區(qū)域的個體適應度越低，被淘汰的概率越大。

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

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

3 排課結(jié)果分析

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

4 結(jié)語

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