基于遺傳算法排課數(shù)學(xué)模型的研究

摘要：排課問(wèn)題作為一個(gè)NP完全問(wèn)題，它涉及多個(gè)約束條件、制約因素，且含有多個(gè)目標(biāo)函數(shù)。遺傳算法具有高效的并行性和智能性，所以使用遺傳算法研究排課問(wèn)題是個(gè)相對(duì)明智的選擇。排課前，我們先對(duì)排課的目標(biāo)和標(biāo)準(zhǔn)進(jìn)行研究、分析，然后用數(shù)學(xué)建模的思想建立模型，最終確定排課問(wèn)題的算法和整體方案。

關(guān)鍵詞：遺傳算法；數(shù)學(xué)模型；排課問(wèn)題

中圖分類號(hào)：G642.471 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-0079（2014）12-0031-02

隨著我國(guó)高校規(guī)模的逐漸擴(kuò)大，使得在校學(xué)生人數(shù)不斷增長(zhǎng)，導(dǎo)致高校教務(wù)部門的工作量急劇增大，而排課工作在高校的教務(wù)管理中起著突出重要的作用，因此研究如何合理、完善、快速的排課顯得十分緊迫且意義重大。排課問(wèn)題涉及多個(gè)約束條件、制約因素，且含有多個(gè)目標(biāo)函數(shù)，排課過(guò)程中不僅要保證學(xué)生、教師、教室、課時(shí)等不產(chǎn)生沖突，且要盡量合理、有效配備各方面資源。由于遺傳算法具有高效的并行性和智能性，使用遺傳算法研究排課問(wèn)題是個(gè)相對(duì)明智的選擇。

一、排課問(wèn)題

在排課前，首先建立相應(yīng)的數(shù)學(xué)模型，對(duì)排課問(wèn)題進(jìn)行研究、分析。

1.排課問(wèn)題關(guān)鍵要素

（1）時(shí)間要素：上課的時(shí)間一般按照周次來(lái)計(jì)算，每周一般為5天，每天分成上午、下午、晚上三個(gè)時(shí)段，一般上午4節(jié)課、下午4節(jié)課、晚上2節(jié)課。

（2）課程要素：每門課程都有自己唯一的課程編號(hào)、課程名稱、授課學(xué)時(shí)、授課的周數(shù)及每周課時(shí)的安排等。

（3）教室要素：包含獨(dú)立的編號(hào)、教室名稱，適合上課的類型和容量等。要求一間教室在一個(gè)時(shí)段只能安排一門課程，且上課人數(shù)小于或等于教室最大容量。

（4）班級(jí)要素：包含班級(jí)名稱、年級(jí)、隸屬的專業(yè)、院系等。要求一個(gè)班級(jí)在一個(gè)時(shí)段只能安排一門課程。

（5）教師要素：包含教師編號(hào)、姓名、職稱、隸屬院系等。要求一名教師在一個(gè)時(shí)段只能安排一門課程。

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

排課問(wèn)題中，涉及到五個(gè)主要的元素集合，分別是：課程、班級(jí)、教師、時(shí)間、教室。

（1）課程集合：，包含的屬性有：課程名稱、課程編號(hào)、課程性質(zhì)、所用教材、周學(xué)時(shí)、開(kāi)課院系等。

（2）班級(jí)集合：，包含的屬性有：班級(jí)名稱、專業(yè)名稱、年級(jí)等。

（3）教師集合：，包含的屬性有：教師姓名、教師編號(hào)等。

（4）時(shí)間集合：，包含的屬性有：時(shí)間段。例如周一1、2節(jié)。

（5）教室集合：：包含的屬性有：教室編號(hào)、教室容量等。

時(shí)間與教室的笛卡爾積記為：；G中的元素稱為時(shí)間教室對(duì)，我們稱G為時(shí)空資源集。

對(duì)于一個(gè)授課事件，我們用e來(lái)表示，它由以下三個(gè)元素構(gòu)成：課程、班級(jí)、教師，即，記：我們稱E為待調(diào)度的授課事件集。實(shí)際上排課結(jié)果就是由這5個(gè)元素構(gòu)成的集合。

二、約束條件

排課問(wèn)題中遇到的約束條件可分為兩個(gè)大類：必須嚴(yán)格遵守的硬約束條件和爭(zhēng)取盡量滿足的軟約束條件。硬約束條件是指在排課過(guò)程中必須要遵守的原則，大多數(shù)排課系統(tǒng)在排課時(shí)都會(huì)考慮這些；軟約束條件是指在排課過(guò)程中需要盡量滿足的條件，它影響著課表的質(zhì)量，在學(xué)生、老師的滿意度上會(huì)有影響。

1.硬約束條件

時(shí)空資源集中的

記，，當(dāng)或時(shí)，則

用語(yǔ)言描述為：時(shí)空資源集由時(shí)間和教室兩個(gè)元素構(gòu)成的集合，當(dāng)時(shí)間不相同或教室不相同時(shí)，構(gòu)成的時(shí)間教室對(duì)自然不同。

授課事件集，

記，，當(dāng)或或時(shí)，則

用語(yǔ)言描述為：授課事件集由課程、班級(jí)和教師三個(gè)元素構(gòu)成的集合，當(dāng)課程不同或班級(jí)不同或教師不同，構(gòu)成的授課事件自然不同。

排課問(wèn)題中需要嚴(yán)格遵守硬約束條件，也就是一個(gè)時(shí)空資源同時(shí)分配給多個(gè)（兩個(gè)或以上）的授課事件。可分別描述為：

2.軟約束條件

硬約束條件影響著課表的切實(shí)可行性，軟約束條件影響著排課的滿意度，是衡量排課優(yōu)劣的標(biāo)準(zhǔn)，所以也要盡可能滿足。包含以下多個(gè)因素：班級(jí)一周內(nèi)的課程盡可能平均分布；一門課程一周內(nèi)需要多次上課，盡量考慮課程的間隔；學(xué)生和老師相鄰兩次的上課地點(diǎn)盡可能接近；盡量滿足老師上課時(shí)間的期望；體育課、實(shí)踐課盡量不要安排在上午第一節(jié)課；根據(jù)學(xué)生人數(shù)分配教室；某些特定的課程需要特定的上課教室；同一門課程勁量安排在同一間教室等。

三、排課問(wèn)題數(shù)學(xué)模型求解

考慮研究的排課問(wèn)題有m個(gè)約束條件，n個(gè)決策變量，k個(gè)求解的目標(biāo)函數(shù)，它們之間互相滿足函數(shù)關(guān)系。則求解排課問(wèn)題的函數(shù)表達(dá)式可表示為：

上述表達(dá)式中，x中包含的元素主要由時(shí)空資源集中時(shí)間和教室兩個(gè)方面的因素組成。x是一個(gè)n維決策向量，X是決策空間。決策向量的維數(shù)不是一成不變的，隨著目標(biāo)向量y維數(shù)的變化，決策向量x的維數(shù)也在發(fā)生變化，一般說(shuō)來(lái)x的維數(shù)隨著y的增大而增大，隨著y的減小而減小。排課問(wèn)題中執(zhí)行的約束條件用來(lái)表示，用它來(lái)決定x中各元素的取值大小。

y表示需要優(yōu)化的目標(biāo)向量，Y表示目標(biāo)空間。y維數(shù)隨著學(xué)校實(shí)際排課狀況及老師、學(xué)生評(píng)判標(biāo)準(zhǔn)的改變而改變。

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

1.構(gòu)造編碼

構(gòu)造合適的編碼是遺傳算法順利實(shí)現(xiàn)的關(guān)鍵，我們將課程集合L、班級(jí)集合C、教師集合P構(gòu)成授課事件集合，這三個(gè)元素結(jié)合為一個(gè)班級(jí)元組；將時(shí)間集合T、教室集合R構(gòu)成時(shí)空資源集。時(shí)間、教室再加上班級(jí)元組便得到了某個(gè)班級(jí)一門課程的排課狀況，用相同的方法便可得到某個(gè)班級(jí)所有課程的排課狀況。按班級(jí)數(shù)的多少，便得到了一定規(guī)模的初始表，構(gòu)成最初的種群。

2.適應(yīng)度函數(shù)

一個(gè)排課方案的確定是非常困難和復(fù)雜的，需要考慮多方面的因素。最常見(jiàn)的是前面提到的硬約束條件和軟約束條件。適應(yīng)度函數(shù)的構(gòu)造和設(shè)計(jì)是遺傳算法的重要一環(huán)。所以設(shè)計(jì)一個(gè)自適應(yīng)能力強(qiáng)的適應(yīng)度函數(shù)對(duì)于排課問(wèn)題非常關(guān)鍵。我們從以下幾個(gè)方面加以考慮：

（1）節(jié)次優(yōu)先度。節(jié)次優(yōu)先度是指教師、學(xué)生對(duì)每周每小節(jié)時(shí)間的偏好程度，它是課表好壞的一個(gè)度量?？紤]實(shí)際的上課情況，每天分為5個(gè)時(shí)段，上午2個(gè)，下午2個(gè)，晚上1個(gè)，每個(gè)時(shí)間根據(jù)自己的滿意度給定一個(gè)分值（取值在0和1之間）。用全校的平均節(jié)次優(yōu)先度來(lái)衡量排課方案關(guān)于節(jié)次安排的好壞。，其中ai是節(jié)次優(yōu)先度，n為總的開(kāi)課數(shù)，顯然越大，排課方案越令人滿意，效果越好。

（2）日均勻度。日均勻度是度量班級(jí)每日的課程過(guò)于集中或松散的一個(gè)量，排課時(shí)應(yīng)盡量使得每周的課程在每天分布均勻，班級(jí)課時(shí)的日均勻度可示為：，其中，hd表示某班級(jí)i在第d日一共上課的節(jié)次數(shù)，表示某班級(jí)i在一周內(nèi)平均上課的節(jié)次數(shù)。分別計(jì)算出全校所有的日均勻度，用他們的平均值來(lái)衡量全校課時(shí)的日均勻度，，其中m表示全校的總班級(jí)數(shù)，越大，說(shuō)明班級(jí)的日課時(shí)分布越不均勻，班級(jí)授課過(guò)于集中或分散，學(xué)校的教學(xué)資源不能得到充分的利用。

（3）日組合優(yōu)先度。日組合優(yōu)先度是某班級(jí)課程組合的好壞的一個(gè)度量標(biāo)志，它能有效避免某課程一周內(nèi)多次上課出現(xiàn)連續(xù)上課的情況。一門課程一周內(nèi)多次開(kāi)課（一般不超過(guò)3次），對(duì)隔天上課的組合賦予一個(gè)較大的值，對(duì)連續(xù)上課的組合賦予一個(gè)較小的值（在0到1之間），計(jì)算一個(gè)班級(jí)課程的平均日組合優(yōu)度，以此類推計(jì)算出全校所有班級(jí)的日組合優(yōu)度，平均值越大，表明全校班級(jí)的課程組合越好。

（4）組合可行度。組合可行度是檢測(cè)當(dāng)前課表安排是否發(fā)生沖突的一個(gè)量。如教師在同一時(shí)間為一個(gè)班級(jí)上不同的課程，教室在一個(gè)時(shí)段安排了兩門不同的課程等，它的取值只能是0或者1。

除了以上考慮的幾個(gè)方面以外，還需要考慮分布優(yōu)化度、資源優(yōu)化度等多方面的因素?；谝陨系难芯浚傻贸鰡伍T課程遺傳算法適應(yīng)度函數(shù)的公式如下：

其中a標(biāo)示節(jié)次優(yōu)先度，r標(biāo)示日組合優(yōu)先度，w1、w2標(biāo)示權(quán)重，且有，com為組合（combination）可行度，res為資源（resource）優(yōu)化度，dis為分布（distribution）優(yōu)化度。

3.遺傳算子設(shè)計(jì)

得到初始種群后，個(gè)體所處的水平還較低，各自對(duì)應(yīng)的適應(yīng)度函數(shù)值參差不齊。遺傳算法以課表個(gè)體對(duì)應(yīng)的適應(yīng)度函數(shù)值的大小作為標(biāo)準(zhǔn)，個(gè)體適應(yīng)度函數(shù)值大的較大幾率保留，函數(shù)值小的較大幾率淘汰，進(jìn)行逐步迭代、進(jìn)化，求解最優(yōu)。影響排課遺傳算法關(guān)鍵的幾個(gè)算子如下：

（1）選擇算子。選擇操作借用“適者生存”的生物進(jìn)化理論，若個(gè)體的適應(yīng)度高，表明優(yōu)秀，被選擇作為父代的幾率就大。從當(dāng)前的種群中挑出優(yōu)良的個(gè)體，使它們有較大幾率成為父代，進(jìn)而繁衍產(chǎn)生下一代種群。

（2）交叉算子。在選擇操作結(jié)束后，我們對(duì)種群進(jìn)行交叉操作。由于按照相同規(guī)則對(duì)每個(gè)排課方案進(jìn)行編碼，這就保證了染色體中基因在各位置上的相互對(duì)應(yīng)。在進(jìn)行交叉操作時(shí)，將兩個(gè)染色體對(duì)應(yīng)位置的基因進(jìn)行互換，這樣的交叉方式?jīng)]有打亂染色體中對(duì)應(yīng)位置的基因結(jié)構(gòu)，從而避免了沖突的產(chǎn)生。

（3）變異算子。變異操作在遺傳算法中是輔助性的，發(fā)生的概率一般較小，但它能有效防止最終解陷入局部的最優(yōu)，對(duì)早熟現(xiàn)象也有較好的抑制效果。

五、總結(jié)

排課問(wèn)題作為一個(gè)NP完全問(wèn)題，涉及多個(gè)約束條件、制約因素，且含有多個(gè)目標(biāo)函數(shù)。由于遺傳算法天生具有高效的并行性和智能性，使用遺傳算法研究排課問(wèn)題是個(gè)相對(duì)明智的選擇。本文通過(guò)對(duì)排課的目標(biāo)和標(biāo)準(zhǔn)進(jìn)行研究、分析，然后用數(shù)學(xué)建模的思想建立模型，從遺傳算法的基本理論入手，最終提出課表的隨機(jī)生成、遺傳迭代及優(yōu)化算法，使課程安排科學(xué)、合理，對(duì)高校的教學(xué)工作起到積極的作用。

參考文獻(xiàn)：

[1]S.Even，A.Itai，A.Shamir.n The Complexity of Timetable and Multi Commodity Flow Problems[J].SIAM Journal on Computing，1976：691-703.

[2]柳衛(wèi)東，裘泳銘.遺傳算法尋優(yōu)能力研究[J].武漢交通科技大學(xué)學(xué)報(bào)，1998，22（5）：486-501.

[3]牟紹波.高校教學(xué)管理系統(tǒng)排課算法的研究[J].四川工業(yè)學(xué)院學(xué)報(bào)，2000，10（5）：51-53.

[4]任克強(qiáng)，趙光甫.基于約束滿足的高校排課問(wèn)題研究[J].江西理工大學(xué)學(xué)報(bào)，2006，26（6）：70-72.

[5]李銳.高校排課系統(tǒng)算法的研究與實(shí)現(xiàn)[D].長(zhǎng)春：吉林大學(xué)，2010：10-12.

（責(zé)任編輯：劉輝）