基于遺傳算法完全學(xué)分制下排課系統(tǒng)模型的研究

侯若楠，范慶坤，張瀟元

隨著各大雙一流建設(shè)高校完全學(xué)分制改革的深入，以及師資力量的提升，未來各大雙一流建設(shè)高校能夠提供的課程種類、總數(shù)必將有所增長，學(xué)生跨專業(yè)選課的意愿也將有一定幅度的提高。因此如何在教學(xué)資源配置過程中進(jìn)一步突出學(xué)生的學(xué)業(yè)需求成為各個(gè)高校雙一流建設(shè)中遇到的難點(diǎn)問題。為了解決這一難點(diǎn)，優(yōu)化排課系統(tǒng)的算法必不可少。這是調(diào)度問題中關(guān)于排課問題的研究內(nèi)容。研究方法是把師資力量、課程數(shù)量等相關(guān)教學(xué)資源按照有關(guān)約束條件放置在特定的教室和時(shí)間里面，目標(biāo)是學(xué)生的選課組合數(shù)達(dá)到最大。因此本文通過對(duì)交叉和變異階段產(chǎn)生的個(gè)體采用蒙特卡洛概率接受的辦法，建立三維空間編碼的遺傳算法，即為構(gòu)建出的排課系統(tǒng)算法模型。

1 問題分析及模型假設(shè)

從已有的研究來看，利用遺傳算法]1[求解排課問題，約束條件主要為避免班級(jí)、教室、課程、教室等排課要素之間發(fā)生沖突，有效利用各種資源，使排出的課表更加人性化，學(xué)生和老師的滿意度最高。本文假設(shè)師資力量和教室數(shù)目可以滿足所有開課需要，即排課問題中面臨的硬約束條件減少；但由于同一時(shí)間可以安排多門課程供學(xué)生自行選擇和一門課程下屬有許多子類別的影響，因此我們需要增設(shè)部分軟約束條件對(duì)算法進(jìn)行優(yōu)化。

2 排課系統(tǒng)數(shù)學(xué)模型的建立

經(jīng)典遺傳算法具有早熟性，經(jīng)過一定的迭代之后，種群的多樣性有所降低，從而導(dǎo)致算法過早地收斂，很可能只會(huì)獲得局部最優(yōu)解。況且，在本文，已經(jīng)假設(shè)教室數(shù)目和師資力量足以滿足所有開課需要，使得排課問題的硬約束條件有所減少，種群的基因多樣性有所降低。故本模型在遺傳算法的基礎(chǔ)上，結(jié)合排課所面臨的實(shí)際問題，采用時(shí)間、課程、起止周三維空間編碼的形式，并且對(duì)交叉和變異階段產(chǎn)生的個(gè)體采用蒙特卡洛概率接受的辦法，提高種群質(zhì)量，避免求得局部最優(yōu)解。

2.1 三維空間編碼排課系統(tǒng)的數(shù)學(xué)模型

變量描述：

三維空間編碼排課問題的數(shù)學(xué)模型變量定義為：

硬約束條件：

軟約束條件：

上述軟約束條件是為了在選課組合數(shù)基本最多的基礎(chǔ)下，對(duì)得到的方案進(jìn)行進(jìn)一步優(yōu)化。

2.2 三維空間編碼排課基本流程

本模型中，排課是將課程按照一定約束條件安排在特定的時(shí)間中，得到選課組合數(shù)最多的方案。

排課的流程圖如圖1：

圖1 排課流程圖

2.3 具體編碼方案

在三維空間編碼排課問題的模型中，研究對(duì)象為不同類課程、不同子類課程、上課時(shí)間、課程起止周。課程子類所屬類別會(huì)隨課程子類確定。所以課程子類、上課時(shí)間、課程起止周可以作為三個(gè)不同的變量，分別對(duì)應(yīng)三維坐標(biāo)系中的X、Y、Z 軸。

圖2 三維空間染色體編碼方案[1]

從圖2 中可以看出，空間每個(gè)黑色小立方體表示一個(gè)個(gè)體基因，表示在第x1周第x2節(jié)可以選ci這門課這個(gè)事件。

具體編碼采用設(shè)計(jì)采用十進(jìn)制編碼形式。

1）時(shí)間編碼。在中午兩節(jié)不安排課程和沒有特殊的三節(jié)課的假設(shè)下，每天上課分為1—2、3—4、7—8、9—10、11—12 五個(gè)時(shí)間段，可分別編碼為01、02、03、04、05。同樣的道理，周一到周五可同時(shí)編碼為01 07。將日期的編碼與節(jié)次編碼相連接，這樣每周具體的上課時(shí)間就會(huì)與一個(gè)唯一的編碼一一相應(yīng)。例如0503 表示某課程在周五7～8節(jié)可選。

2）課程編碼。此課程集合C 中的i 值是所選課程的具體類別,為同一類課程不同子類別同樣分別編為相應(yīng)的j 值，然后順次連接得到ij 這個(gè)編碼。例如：0015007 這個(gè)編碼表示這門課在某時(shí)間某周次可選。

3)課程起止周編碼。課程起止周編碼按照起始周與結(jié)束周的周序號(hào)進(jìn)行連接即可。例如0108 表示該課程的起始周為第一周，在第八周結(jié)束。需說明的是，當(dāng)課程編碼確定的時(shí)候，課程起止周的編碼是唯一確定的，即變量課程起止周依賴于變量課程序號(hào)的變化而變化的。

2.4 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)是衡量一個(gè)個(gè)體好壞(一種課表好壞)程度的重要標(biāo)準(zhǔn)。本模型將重點(diǎn)從選課組合數(shù)最大對(duì)排課問題定義評(píng)價(jià)函數(shù)，同時(shí)加上其他一些必要的方面作為輔助評(píng)價(jià)。

1）選課組合數(shù)最大選課組合數(shù)的多少主要通過同一時(shí)間節(jié)次下，安排的同一類課程的不同子類數(shù)目；同一時(shí)間節(jié)次下，安排的不同類課程數(shù)目以及課表的空閑度來反映。即在課表的每一節(jié)次有適當(dāng)種選擇的情況下，排列越分散，課表的選課沖突矛盾越小，最后得到的選課組合數(shù)越多。

2）課程間隔：根據(jù)實(shí)際情況，兩節(jié)相同的課程連在一起上是不合理的，所以需要設(shè)置一定的參數(shù)來衡量時(shí)間間隔的大小以并賦予一定的權(quán)重，作為評(píng)價(jià)函數(shù)中的次要影響因素。因此可得如下算法公式：

綜上所述，本模型的適應(yīng)度評(píng)價(jià)函數(shù) F 定義如下：