基于遺傳算法的高校排課問題研究

摘要：排課問題一個(gè)是有約束的、多目標(biāo)的組合優(yōu)化問題，并且己經(jīng)被證明是一個(gè)NP完全問題。在高校，排課是高校教務(wù)管理的核心內(nèi)容，是教學(xué)工作正常運(yùn)轉(zhuǎn)的基本要素之一。本文通過對(duì)排課問題的闡述以及對(duì)遺傳算法操作的描述，結(jié)合自身實(shí)踐建立了一個(gè)基于遺傳算法的數(shù)學(xué)模型，可以合理地解決各種沖突，并在一定程度上實(shí)現(xiàn)智能排課。

關(guān)鍵詞：排課問題；遺傳算法；適應(yīng)度函數(shù)

一、前言

在高校，教學(xué)工作無(wú)疑是其運(yùn)作的基本要素，而排課問題更是教學(xué)工作的核心內(nèi)容之一。由于排課問題本身的性質(zhì)是屬于一個(gè)復(fù)雜的、難解的、有約束的、模糊多目標(biāo)化的組合數(shù)學(xué)問題，所以排課是每個(gè)學(xué)校在學(xué)期進(jìn)行中就要妥善解決的重要任務(wù)。排課問題的本質(zhì)是將教師、教室、課程以及班級(jí)在適當(dāng)?shù)臅r(shí)間段內(nèi)合理安排，由于其涉及范圍比較廣且相互約束，在運(yùn)籌學(xué)領(lǐng)域中也被稱為時(shí)間表問題（TimeTableProblem，簡(jiǎn)稱TTP）。

隨著我國(guó)高等院校招生比例的擴(kuò)大，學(xué)生、課程數(shù)目逐漸增多，同時(shí)教師、教室等固定資源的不足，出現(xiàn)一位老師多門課、教師課時(shí)繁重等情況，間接導(dǎo)致高校排課難度增加，排課人員在眾多約束條件的限制下很難人工排出十分完美的課表。利用計(jì)算機(jī)解決排課問題的方法有許多種，其中以遺傳算法最為突出。排課問題是組合優(yōu)化問題，而遺傳算法有兩大優(yōu)點(diǎn)，分別是智能性和并行性，利用遺傳算法的搜索全局最優(yōu)解的搜索能力能很好地解決該問題。

二、遺傳算法基本思想

遺傳算法是基于自然選擇、生物進(jìn)化理論和遺傳學(xué)的搜索算法，它將“優(yōu)勝劣汰，適者生存”的生物進(jìn)化原理引入待優(yōu)化參數(shù)形成的編碼串群體中，按照一定的適配值函數(shù)及一系列遺傳操作對(duì)各個(gè)體進(jìn)行篩選，從而使適配值高的個(gè)體被保留下來，組成新的群體，新群體包含上一代的大量信息，并且引入了新的優(yōu)于上一代的個(gè)體。這樣周而復(fù)始，群體中各個(gè)體適應(yīng)度不斷提高，直至滿足一定的極限條件[1]。此時(shí)，群體中適配值最高的個(gè)體即為待優(yōu)化參數(shù)的最優(yōu)解。遺傳算法有著不同于傳統(tǒng)優(yōu)化方法的特點(diǎn)，主要體現(xiàn)在以下幾個(gè)方面：（1）在應(yīng)用遺傳算法求解問題時(shí)，當(dāng)確定好編碼方案、適應(yīng)度函數(shù)以及遺傳算子后，算法將根據(jù)進(jìn)化過程獲得的信息自行搜素；（2）遺傳算法是按照并行方式進(jìn)行搜索種群數(shù)目的點(diǎn)，而不僅僅是單點(diǎn)搜素，可以防止過程收斂于局部最優(yōu)解而不是全局最優(yōu)解；（3）遺傳算法通過目標(biāo)函數(shù)來計(jì)算適值，不需要其他推導(dǎo)和附加信息，對(duì)問題的依賴性比較小。

下面是遺傳算法的一般算法過程：

1.隨機(jī)產(chǎn)生初始群體。通常，初始種群是隨機(jī)產(chǎn)生的，這個(gè)群體中的個(gè)體都是帶有特征的染色體（chromosome）或基因（gene）。

2.計(jì)算適應(yīng)度。在根據(jù)種群的大小隨機(jī)產(chǎn)生初始種群后，按照“適者生存，優(yōu)勝劣汰”的原理，需要根據(jù)某個(gè)物種對(duì)環(huán)境的適應(yīng)程度來度量基因遺傳到后代的相對(duì)能力。遺傳算法在進(jìn)化搜索中基本不利用外部信息，僅以適應(yīng)度函數(shù)為依據(jù)，利用種群中每個(gè)個(gè)體的適應(yīng)度值來進(jìn)行搜索[2]。一般來說，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的。

3.遺傳操作。遺傳算法包括三個(gè)基本操作，分別為：選擇、交叉、變異。在每一代，根據(jù)適應(yīng)度大小挑選出的個(gè)體，通過選擇交叉等遺傳操作下產(chǎn)生新的種群。

4.下一代。通過以上操作，如果新的一代能夠產(chǎn)生出一個(gè)解是與期望的答案相符或者相接近，那么，整個(gè)過程就結(jié)束了。如果不是，那么子代的適應(yīng)度又將被重新計(jì)算，子代插入到父代形成新的父代，產(chǎn)生新的子代。這個(gè)過程將一直循環(huán)進(jìn)行，直到達(dá)到期望的解。以下是遺傳算法的偽代碼；

三、排課問題的描述

1.排課問題的描述。排課是指學(xué)校對(duì)學(xué)生上課過程中的課程安排，具體指在什么時(shí)間地點(diǎn)由哪位老師給哪個(gè)班級(jí)上什么課程。簡(jiǎn)單而言，課表問題中包含幾個(gè)相互制約的因素，分別為：上課時(shí)間、上課所用教室、老師所教授課程、授課人教師、對(duì)象學(xué)生。一份好的課表就是能夠?qū)r(shí)間和教室進(jìn)行合理分配。課程門類多、班級(jí)多、教師少、教室少是排課時(shí)發(fā)生沖突和矛盾的主要因素，而班級(jí)多、教室少則是矛盾的重要方面[3]。

判斷課表的好壞通常有兩大類，分別為：軟件約束條件和硬件約束條件。軟約束條件是指在情況允許的條件下可以滿足但也可以不完全滿足的約束條件。比如，難度較大的課程應(yīng)安排在學(xué)生及老師精力相對(duì)比較充沛的時(shí)間段；某些老師因?yàn)橐恍┰蚨a(chǎn)生的特殊要求等。硬約束條件是必須滿足的，是由客觀情況而出現(xiàn)的限制。比如，教室的座位數(shù)需大于學(xué)生人數(shù)，同位老師不能在同一時(shí)間內(nèi)出現(xiàn)在兩個(gè)不同的授課班級(jí)等。

2.排課問題的數(shù)學(xué)模型。排課問題中，最核心的問題是為了解決教師、教室、課程、班級(jí)在一周的時(shí)間內(nèi)不沖突[4]。假設(shè)：學(xué)校有t個(gè)時(shí)間段，r間教室，l門課程，p位教師，c個(gè)授課班級(jí)。那么可以表達(dá)為：時(shí)間集合：T={t1，t2，t3…，tn}，以韓山師范學(xué)院為例，一次課以一大節(jié)為準(zhǔn)，一大節(jié)為兩節(jié)課，每節(jié)課45分鐘，即每次課程的時(shí)間約為兩小時(shí)，每周上5天課，每天上課時(shí)間是7：50～21：15，所以將一天的時(shí)間按課節(jié)時(shí)間分為5個(gè)時(shí)間段，作為上課時(shí)間。這樣推算，一周上課時(shí)間為：5*5=25個(gè)時(shí)間段。如11代表周一第一個(gè)教學(xué)單元，即周一1、2節(jié)，12代表周一第二個(gè)教學(xué)單元，即周一3、4節(jié)，依次類推這些時(shí)間段構(gòu)成一個(gè)時(shí)間集合t（11，12，13，…，55）。

教室集合：R={r1，r2，r3…rm}，每間教室的容量為Xr；

時(shí)間與教室相對(duì)應(yīng)，時(shí)間與教室的笛卡兒積為：

N={（t1，r1），（t2，r2），（t3，r3）…（tn，rm）}。N中的元素稱為時(shí)間一教室對(duì)。

課程集合：L={l1，l2，l3…lt}，

教師集合：P={p1，p2，p3…ps}。

一般來說，大學(xué)教師，都是多門課程由一名教師來教，因此，固定的多門課程與一名教師相對(duì)應(yīng)。教師與固定的課程相對(duì)應(yīng)，教師與課程的笛卡兒積為：

K={（l1，p1），（l2，p2），（l3，p3）…，（lt，ps）}。K中的元素稱為教師一課程對(duì)。

班級(jí)集合：C={c1，c2，c3…cu}，

根據(jù)以上約定，我們可以把一次授課表示為：（kicj）RaPb，

把課表表示為：CL={（kicj）RaPb；其中：i=（1，…，C），j=（1，…，s），a∈（1，r），b∈（1，p）}

3.排課問題中的適應(yīng)度函數(shù)。適應(yīng)度函數(shù)（FitnessFunction）的選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解[5]，遺傳算法在優(yōu)化搜索中基本不用外部信息，僅用適應(yīng)度函數(shù)為尋優(yōu)依據(jù)。由于遺傳算法中，適應(yīng)度函數(shù)要比較排序并在此基礎(chǔ)上計(jì)算選擇概率，所以適應(yīng)度函數(shù)的值要取正值。遺傳算法的復(fù)雜度最大的誘因來自適應(yīng)度函數(shù)的復(fù)雜度，所以只有越簡(jiǎn)單的適應(yīng)度函數(shù)，計(jì)算的時(shí)間復(fù)雜度才會(huì)越小。

四、實(shí)驗(yàn)與分析

1.實(shí)驗(yàn)測(cè)試的環(huán)境和工具：（1）硬件環(huán)境：IntelCoreZT7200+2GRAM；（2）操作系統(tǒng)：MicrosoftWindowsXPProfessional；（3）編譯環(huán)境：VisualStudio2008，MicrosoftSQLServer2000；（4）實(shí)驗(yàn)數(shù)據(jù)：本文以韓山師范學(xué)院政法系課程計(jì)劃作為源數(shù)據(jù)，分別對(duì)兩個(gè)學(xué)期數(shù)據(jù)進(jìn)行測(cè)試和分析。為方便表示，選擇其中一學(xué)期課程計(jì)劃作為性能對(duì)比分析的源數(shù)據(jù)。

2.結(jié)果分析。通過軟件設(shè)計(jì)，經(jīng)過不斷優(yōu)化，把最終得到的可以接受的排課結(jié)果錄入到數(shù)據(jù)庫(kù)中的課程表，為了使得學(xué)生及老師更加滿意課表的安排，接著對(duì)上面排好的課表進(jìn)一步人工優(yōu)化。總之，遺傳算法對(duì)系統(tǒng)適應(yīng)度的提升是比較明顯的，這正是遺傳算法的特點(diǎn)[6]。

五、結(jié)束語(yǔ)

本文通過對(duì)排課問題的闡述，建立了排課問題相對(duì)應(yīng)的數(shù)學(xué)模型，將遺傳算法融入至排課系統(tǒng)的研究中并進(jìn)行了實(shí)現(xiàn)。排課問題是一個(gè)復(fù)雜的多學(xué)科交叉的難解問題，至今未有最完美的解決方案，在本文的研究基礎(chǔ)上今后可以在如何設(shè)定算法中各個(gè)控制參數(shù)上進(jìn)行進(jìn)一步探索。

參考文獻(xiàn)：

[1]陳江.基于遺傳算法的自動(dòng)排課問題的研究[D].杭州：浙江大學(xué)，2001.

[2]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：交通大學(xué)出版社，2002.

[3]梁飛鴻.基于遺傳算法的排課系統(tǒng)研究[J].電腦與電信，2010，（08）：51-53.

[4]郭蕓俊.遺傳算法在排課系統(tǒng)中的應(yīng)用[J].電腦開發(fā)與應(yīng)用，2009，163（22）：75-77.

[5]樊星，利用遺傳算法求解大學(xué)課表問題[D].科學(xué)與技術(shù)工程，2007：1990-1991.

[6]趙光哲.基于遺傳算法的大學(xué)排課問題的研究[D].延邊大學(xué)，2006.