基于改進(jìn)型遺傳算法求解高校排課問題

1、 基于改進(jìn)型遺傳算法求解高校排課問題 龔程陳高云劉胤田李代偉摘 要：隨著信息技術(shù)的不斷發(fā)展和教育改革的不斷深入，通過信息技術(shù)實(shí)現(xiàn)教學(xué)管理的智能化已經(jīng)成為可能。排課作為教學(xué)管理的核心內(nèi)容之一，它是衡量教學(xué)管理水平的重要指標(biāo)，它是教學(xué)管理智能化的重要體現(xiàn)。本文的研究是通過學(xué)校的教學(xué)計(jì)劃分析并建立排課的數(shù)學(xué)模型，對(duì)傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)，設(shè)計(jì)出一種改進(jìn)的自適應(yīng)的遺傳算法求解排課問題，改進(jìn)的自適應(yīng)遺傳算法相對(duì)于傳統(tǒng)的遺傳算法在排課效率上有很大提高。Key：排課模型；遺傳算法；節(jié)次；自適應(yīng)：TP311.5 ：AAbstract：With the continuous development of inf

2、ormation technology and the further deepening of education reform，intelligent teaching management by means of information technology has become possible.As one of the core contents of teaching management，course scheduling is an important index to measure teaching management as well as an important e

3、vidence of intelligent teaching management.This paper has analyzed and established the mathematics model of course scheduling through the teaching plan in colleges and universities，improved traditional genetic algorithm and designed an improved self-adaptive genetic algorithm to solve the scheduling

4、 problem.Compared with traditional genetic algorithm，the improved adaptive genetic algorithm has greatly increased the efficiency of course scheduling.Keywords：course scheduling model；genetic algorithm；section；self-adaptive1 引言（Introduction）隨著信息技術(shù)的不斷發(fā)展和教育改革的不斷深入，通過信息技術(shù)實(shí)現(xiàn)教學(xué)管理的智能化已經(jīng)成為可能1。排課作為教學(xué)管理的核心內(nèi)容

5、之一，它是衡量教學(xué)管理水平的重要指標(biāo)，它是教學(xué)管理智能化的重要體現(xiàn)。排課問題的目標(biāo)是在一定的約束條件下求解出較優(yōu)的排課方案，使得依據(jù)此方案執(zhí)行的教學(xué)計(jì)劃具有學(xué)生老師合理安排，教室資源利用率高，教學(xué)質(zhì)量高的特點(diǎn)2，3。2 常見的排課模型（Common course scheduling model）2.1 圖論算法圖論中的圖是由若干給定點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系圖論解決排課問題，將圖論的邊著色理論，對(duì)排課資源進(jìn)行建模，使得排課問題得以解決4。但圖論本身是NP完全問題，算法實(shí)現(xiàn)上比較繁瑣。2.

6、2 貪心算法貪心算法基本思路是從問題的某一個(gè)初始解出發(fā)一步一步地進(jìn)行，根據(jù)某個(gè)優(yōu)化測(cè)度，每一步都要確保能獲得局部最優(yōu)解。貪心算法的排課系統(tǒng)，以資源匹配為基礎(chǔ)，用內(nèi)存動(dòng)態(tài)分區(qū)分配的最佳適應(yīng)法為依托解決排課問題5。與圖論算法比較，避免了算法實(shí)現(xiàn)上的困難，但貪心算法在斷點(diǎn)選擇中存在缺陷。2.3 人工智能算法人工智能是對(duì)人的意識(shí)、思維的信息過程模擬。人工智能解決學(xué)校的排課系統(tǒng)，以時(shí)間因素為核心進(jìn)行課程的安排符合學(xué)校教學(xué)實(shí)際情況，以影響學(xué)校課程安排中最為直接的三個(gè)因素教師。以學(xué)生和教室為核心來安排一門課程6。使用這種方法能夠使學(xué)校管理進(jìn)一步科學(xué)化，高效化。3 基于高校的排課模型（Course sched

7、uling model in colleges and universities）3.1 相關(guān)術(shù)語(yǔ)教學(xué)班（Teaching Class）：一個(gè)教學(xué)班包含多個(gè)班級(jí)。例如：軟件工程2015級(jí)12班包含1班和2班兩個(gè)班，這樣定義不需要考慮合班情況，只需要在制定教學(xué)計(jì)劃時(shí)選擇出需要合班的班級(jí)即可，教學(xué)班集合定義為，每個(gè)教學(xué)班對(duì)應(yīng)的人數(shù)為。節(jié)次（Section）：一門課程上一節(jié)課45min所耗費(fèi)的時(shí)間為一個(gè)節(jié)次，一天共有10個(gè)節(jié)次，上午四個(gè)節(jié)次，下午四個(gè)節(jié)次和晚上兩個(gè)節(jié)次，節(jié)次集合定義為。課程（Course）：將課程分為公共基礎(chǔ)必修，公共基礎(chǔ)選修，學(xué)科基礎(chǔ)必修，學(xué)科基礎(chǔ)選修，專業(yè)課必修，專業(yè)課選修，實(shí)踐

8、教學(xué)環(huán)節(jié)必修，實(shí)踐教學(xué)環(huán)節(jié)選修，表示課程的重要程度，即權(quán)重。課程的權(quán)重為1，2，3，8。教室（Class Room）：集合定義為。教師（Teacher）：集合定義為。時(shí)間間隔（Time Interval）：對(duì)于一周多學(xué)時(shí)的課程需要有時(shí)間間隔，用，表示間隔的天數(shù)。3.2 約束條件3.2.1 硬約束條件3.2.2 軟約束條件課程約束：課程約束包含三個(gè)約束條件，分別是：重要的課程要安排在教學(xué)效果好的節(jié)次；同一門課程應(yīng)該安排在每周中同一個(gè)節(jié)次；同一門課程的教室應(yīng)該安排一致。對(duì)應(yīng)的數(shù)學(xué)表達(dá)式如下：教師約束：教室約束包含三個(gè)約束條件，分別是：同一個(gè)教師在一周上同一門課程是多節(jié)次，則課程的時(shí)間安排應(yīng)該有時(shí)間

9、間隔；同一個(gè)教師在一周上兩門課程，則課程的時(shí)間安排應(yīng)該連排；同一個(gè)教師在一周上兩門課程，則課程的教室安排應(yīng)該足夠的近。對(duì)應(yīng)的數(shù)學(xué)表達(dá)式如下：學(xué)生約束：學(xué)生約束包含三個(gè)約束條件，分別是：每個(gè)學(xué)生一個(gè)周節(jié)次排課分布均勻；每個(gè)學(xué)生一天不能排滿課；每個(gè)學(xué)生連續(xù)上兩門課程，則課程教室的安排應(yīng)該足夠的近。對(duì)應(yīng)的數(shù)學(xué)表達(dá)式如下：其中，表示一個(gè)教學(xué)班在一個(gè)工作日所上的課程數(shù)，表示一周上課天數(shù)，表示一個(gè)教學(xué)班一天平均要上的節(jié)次。教室約束：教室約束是教室的利用率應(yīng)該高。對(duì)應(yīng)的數(shù)學(xué)表達(dá)式如下：3.3 適應(yīng)度函數(shù)適應(yīng)度函數(shù)的好壞決定了遺傳算法的收斂性，若目標(biāo)函數(shù)設(shè)計(jì)不合理會(huì)造成程序執(zhí)行過早收斂，形成局部最優(yōu)解，合理的

10、目標(biāo)函數(shù)可以得到全局最優(yōu)解。本文所設(shè)計(jì)適應(yīng)度函數(shù)如式（6）所示，目標(biāo)函數(shù)適應(yīng)度的函數(shù)值的解越大所求出的解越優(yōu)。3.4 排課的流程排課是根據(jù)教務(wù)處指派的教學(xué)任務(wù)，合理的將教學(xué)任務(wù)分配教室和時(shí)間，排課流程如圖1所示。4.1 編碼設(shè)計(jì)編碼方式有浮點(diǎn)編碼、二進(jìn)制編碼、十進(jìn)制編碼等方式，本文采用十進(jìn)制編碼表示課表染色體的編碼，如下表2所示，能更好地表示排課問題的實(shí)際特點(diǎn)。每一種編碼對(duì)應(yīng)一條染色體，則每一條染色體表示的是一種排課可能。例如：軟件學(xué)院張三教授給2012級(jí)軟件工程1班上數(shù)據(jù)結(jié)構(gòu)課程，課程每周兩次，在2棟樓101多媒體教室進(jìn)行，時(shí)間是第四周周一下午五六節(jié)，則可此授課事件的染色體編碼為011001

11、-1201011-1220001-22101-0413（其中011001表示教師編碼，01表示軟件學(xué)院，1表示教師的職稱，001表示教師的編號(hào)）。4.2 初始種群的產(chǎn)生初始種群的產(chǎn)生一般通過隨機(jī)搜索的方式產(chǎn)生，為后續(xù)各種操作提供初始可行解。由于初始種群中生成的個(gè)體適應(yīng)度值較低，本文首先按照課程權(quán)重對(duì)課程進(jìn)行排序，該操作可以避免解空間的過早壓縮，同時(shí)能夠盡早的產(chǎn)生可行解。4.3 選擇操作根據(jù)達(dá)爾文的進(jìn)化論提出的“適者生存”的原則，選擇是從種群中選擇出優(yōu)秀的個(gè)體作為父代，并為下一代個(gè)體繁殖作基礎(chǔ)。選擇操作通常也稱作再生操作。選擇操作從種群中選擇出適應(yīng)度高的個(gè)體遺傳到下代個(gè)體。種群中個(gè)體的適應(yīng)度的值

12、越大，被選擇的概率則越高。fi表示種群中個(gè)體的適應(yīng)度的值，n表示種群中個(gè)體的數(shù)量，則種群中個(gè)體的概率值：4.4 自適應(yīng)交叉和變異操作交叉操作是把種群中兩個(gè)個(gè)體進(jìn)行隨機(jī)的交叉重組，這種操作既保證的新產(chǎn)生的個(gè)體保留了父代個(gè)體的優(yōu)良基因，又是種群的個(gè)體具有多樣性。變異操作是種群中的個(gè)體根據(jù)一定的概率值做出基因位的變動(dòng)。傳統(tǒng)的遺傳算法中，采用固定的交叉概率和變異概率，容易產(chǎn)生局部最優(yōu)解，本文采用自適應(yīng)的交叉和變異操作進(jìn)行遺傳算法的計(jì)算，具體操作如下：其中，和分別表示交叉和變異概率，表示當(dāng)前種群最優(yōu)個(gè)體的適應(yīng)度值，表示當(dāng)前種群平均適應(yīng)度值，表示進(jìn)行交叉操作的個(gè)體中適應(yīng)度較大的值，表示變異個(gè)體適度值，和取

13、值均為0到1的隨機(jī)數(shù)。5 實(shí)驗(yàn)（Experiment）5.1 實(shí)驗(yàn)數(shù)據(jù)本文實(shí)驗(yàn)數(shù)據(jù)是來自軟件工程學(xué)院2017年秋季課表，如表3所示。實(shí)驗(yàn)參數(shù)如表4所示。實(shí)驗(yàn)平臺(tái)采用2.20GHz，Pentium i7處理器、8GB內(nèi)存、700GB硬盤，操作系統(tǒng)為win7。所有實(shí)驗(yàn)均采用C#語(yǔ)言，在Visual Studio 2010下實(shí)現(xiàn)。5.2 實(shí)驗(yàn)結(jié)果與分析對(duì)于同一初始種群下，將文獻(xiàn)7中（GA）方法與本文方法（MGA）進(jìn)行對(duì)比。圖2是10次實(shí)驗(yàn)兩種方法不同的種群平均適度的值，MGA的平均值高于GA的平均值，圖3是10次實(shí)驗(yàn)兩種方法不同的時(shí)間值，MGA的時(shí)間值低于GA的時(shí)間值。由圖2和圖3可以看出，本文方法

14、都優(yōu)于文獻(xiàn)7中的方法。根據(jù)表5的評(píng)價(jià)指標(biāo)分析，改進(jìn)后的遺傳算法MGA比傳統(tǒng)的遺傳算法GA在課程均勻度，學(xué)生課程分布，教室滿意度及教室利用率方面都有明顯的改善。6 結(jié)論（Conclusion）本文針對(duì)高校排課問題進(jìn)行分析，根據(jù)教學(xué)計(jì)劃對(duì)排課問題建模，通過改進(jìn)的遺傳算法對(duì)問題進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的遺傳算法比一般的遺傳算法具有更高的效率。如何合理的解決排課中漏排課問題是下一步研究的重點(diǎn)。Reference（References）1 Marc Goerigk，Christian Liebchen.An Improved Algorithm for the Periodic Timetabli

15、ng ProblemC.17th Workshop on Algorithmic Approaches for Transportation Modelling，Optimization，and Systems，2017（12）：1-14.2 H Babaei，J Karimpour，A Hadidi.A survey of approaches for university course timetabling problemJ.Computers & Industrial Engineering，2015，86（C）：43-59.3 G Woumans，L De Boeck，J Belin.A column generation approach for solving the examination-timetabling problemJ.European Journal of Operational Research，2016，253（1）：178-194.4 崔妍，王權(quán)，王康，等.排課問題的數(shù)學(xué)模型J.沈陽(yáng)工程學(xué)院學(xué)報(bào)（自然科學(xué)版），2016，12（3）：276-278.5