基于遺傳算法的智能排課問題的探究

李俊芳 張健立

摘要：目前，隨著高校在校生人數(shù)的不斷增長(zhǎng)，教學(xué)管理任務(wù)也開始變得越來越繁重，其中排課任務(wù)在教務(wù)管理中就是一項(xiàng)極其重要但又很繁雜的工作。所以，設(shè)計(jì)開發(fā)一個(gè)合理高效的智能排課系統(tǒng)從而全面提高排課管理人員的工作效率，對(duì)于各高校管理部門及其工作人員來說都是一件特別有意義的事情。

關(guān)鍵詞：智能排課遺傳算法排課變量

1.引言

近幾年，隨著高校教育走向大眾化，學(xué)生人數(shù)急速上升，這無疑加大了排課工作的難度，而課表安排又是教務(wù)管理工作中最基礎(chǔ)的部分。因此自動(dòng)排課系統(tǒng)是高校教務(wù)管理系統(tǒng)的一個(gè)重要組成部分，自動(dòng)排課系統(tǒng)的應(yīng)用，使得管理人員可以及時(shí)掌握學(xué)生的排課情況，進(jìn)一步優(yōu)化指導(dǎo)學(xué)校的教學(xué)資源，在一定程度上提高了高校教學(xué)管理人員的工作效率及教學(xué)質(zhì)量。

2.背景

隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展和教育信息化的不斷推進(jìn)，信息技術(shù)和計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)對(duì)教學(xué)和管理的各個(gè)方面都產(chǎn)生了很深的影響。教學(xué)計(jì)劃的實(shí)施是高校日常教學(xué)管理工作中最重要也是最基本的一個(gè)環(huán)節(jié)。而課程表的制定則是教學(xué)計(jì)劃實(shí)施的一個(gè)根本條件，是整個(gè)教學(xué)管理工作實(shí)施的基礎(chǔ)，對(duì)教學(xué)計(jì)劃的實(shí)施與教學(xué)培養(yǎng)計(jì)劃的落實(shí)起著至關(guān)重要的作用，在此基礎(chǔ)上對(duì)教育教學(xué)進(jìn)行科學(xué)統(tǒng)一的組織和管理，有助于充分整合及利用各種資源。一張好的課表不僅能給授課教師帶來工作上面的便利，而且也能為學(xué)生創(chuàng)造好的學(xué)習(xí)環(huán)境，提高學(xué)習(xí)效率。編制課表目的在于使整個(gè)教學(xué)過程能夠有計(jì)劃有秩序地進(jìn)行，這在高校的教務(wù)管理工作中是一項(xiàng)耗時(shí)巨大的工程。而這項(xiàng)排課工作的復(fù)雜程度與學(xué)校的規(guī)模有很大的關(guān)系，學(xué)校的規(guī)模越大，當(dāng)然排課工作的復(fù)雜程度就會(huì)越高。近幾年，隨著高校教育走向大眾化，學(xué)生人數(shù)急速上升，這無疑加大了排課工作的難度，而課表安排是又教務(wù)管理工作中最基礎(chǔ)的部分，因此如何設(shè)計(jì)一個(gè)好的排課系統(tǒng)，如何把教務(wù)管理人員從復(fù)雜的排課工作中抽離出來，是每一位教務(wù)工作人員和軟件開發(fā)者的希望，也是當(dāng)前迫切需要解決的一個(gè)問題。

因此，自動(dòng)化排課系統(tǒng)的廣泛應(yīng)用必然成為大勢(shì)所趨。排課系統(tǒng)是高校教務(wù)管理系統(tǒng)的一個(gè)重要組成部分，自動(dòng)排課系統(tǒng)的應(yīng)用，使得管理人員可以及其掌握學(xué)生的排課情況，進(jìn)一步優(yōu)化指導(dǎo)學(xué)校的教學(xué)，操作方便、靈活高效。自動(dòng)化排課系統(tǒng)實(shí)現(xiàn)了整個(gè)排課流程的自動(dòng)化，同時(shí)還解決了多種角色以及各個(gè)部門之間的協(xié)作關(guān)系。因此自動(dòng)化排課系統(tǒng)的應(yīng)用，在一定程度上提高了高校教學(xué)管理人員的工作效率及教學(xué)質(zhì)量。

3.遺傳算法

1.原理

遺傳算法（Genetic Algorithms，GA）通過模擬自然界的生物進(jìn)化過程來尋求問題的最優(yōu)解，它借鑒了生物界的自然選擇機(jī)制。遺傳算法被較多的用于解決排課問題，同時(shí)很多學(xué)者熱衷于對(duì)它的改進(jìn)與優(yōu)化，從而出現(xiàn)了諸多基于遺傳算法的排課算法。

2.遺傳算法流程如下：

1）進(jìn)行染色體編碼；

2）隨機(jī)產(chǎn)生初始種群，數(shù)量根據(jù)實(shí)際情況事先定義；

3）計(jì)算所有個(gè)體進(jìn)行適應(yīng)度函數(shù)值的計(jì)算，若某個(gè)個(gè)體適應(yīng)度值已滿足最優(yōu)化的要求，則輸出該個(gè)體及其優(yōu)化解，并結(jié)束當(dāng)前計(jì)算，否則轉(zhuǎn)到第4）步；

4）依據(jù)適應(yīng)度值的大小，從所有個(gè)體中選取出那些適應(yīng)能力較強(qiáng)的個(gè)體成為再生個(gè)體；

5）依據(jù)預(yù)先定義的交叉概率及方法產(chǎn)生出新的個(gè)體；

6）依據(jù)預(yù)先定義的變異概率及方法產(chǎn)生出新的個(gè)體；

7）由以上兩個(gè)步驟中的交叉、變異操作產(chǎn)生新一代種群，并返回到第3）步。

4.排課系統(tǒng)設(shè)計(jì)

4.1排課管理部分

包括智能排課和排課結(jié)果查詢兩個(gè)功能。確定專業(yè)和年級(jí)后，啟動(dòng)自動(dòng)排課功能，即可完成自動(dòng)排課功能。排課結(jié)果查詢即是對(duì)前面已排好的課表，在指定了專業(yè)和年級(jí)以后進(jìn)行查詢。

4.2數(shù)據(jù)庫設(shè)計(jì)

排課系統(tǒng)依賴的基本信息包括課程、教室、教師、班級(jí)等資源，求解目標(biāo)即滿足要求的課表安排。數(shù)據(jù)庫是上述信息的載體。利用關(guān)系型數(shù)據(jù)庫系統(tǒng)進(jìn)行系統(tǒng)的開發(fā)，需要首先完成概念結(jié)構(gòu)的設(shè)計(jì)。概念結(jié)構(gòu)反映了現(xiàn)實(shí)世界中實(shí)體之間的聯(lián)系。

4.3排課問題變量

1. 時(shí)間變量

排課時(shí)重點(diǎn)要注意的是時(shí)間段的劃分，一般高校安排周一至周五

為課程工作日， 一天可以安排8節(jié)課（上午4節(jié)， 下午4節(jié)），上課方式一般為兩節(jié)連上，一個(gè)課次為兩個(gè)相鄰的小節(jié)課。所以以一個(gè)課次為一個(gè)時(shí)間段，一天可以劃分為4個(gè)時(shí)間段。按一周五天計(jì)算，一周可以劃分為20個(gè)時(shí)間段。但是，并非20個(gè)時(shí)間段里面每一個(gè)時(shí)間段都適合排課，并且有的課程對(duì)時(shí)間可能還會(huì)有一定的要求，如：比較重要的課一般放在一二節(jié)；體育課盡量不要排在上午的時(shí)間；周五下午三四節(jié)一般不排課等等。

2. 教師變量

一個(gè)教師可能只帶一門課，也可能帶多門課，但是一個(gè)教師在某一個(gè)時(shí)間段，在某一個(gè)教學(xué)地點(diǎn)只能上一門課；另外，一個(gè)教師可能帶一個(gè)班級(jí)的課程也可能帶多個(gè)班級(jí)的課，如果一個(gè)教師在某一時(shí)間段內(nèi)被安排在多個(gè)班級(jí)上課，同樣會(huì)造成教學(xué)活動(dòng)的混亂。

3. 課程變量

一門課程可以由一位教師任教也可以由多位教師任教，而且每位教師可能對(duì)應(yīng)了個(gè)班級(jí)的學(xué)生。

4. 班級(jí)變量

同一時(shí)間段內(nèi)一個(gè)班級(jí)只能在一個(gè)教室里面上課，并且只能是一門課程。

5. 教室變量

學(xué)校里通常有多個(gè)教學(xué)樓，每個(gè)教學(xué)樓又會(huì)有若干個(gè)教室可供選擇，在某個(gè)時(shí)間段內(nèi)只能有一名教師在此教室授課，可以有多名學(xué)生，但是學(xué)生的課程必須相同，所選教師必須相同。

4.4排課問題約束

排課問題涉及到兩種約束，分別是基本約束和模糊約束。其中，基本約束又稱硬約束，是指在排課過程中必須要遵循的原則。而模糊約束又稱軟約束，是要盡量滿足的原則。

一個(gè)正確的課表要遵循的基本約束條件：

1. 同一時(shí)間段內(nèi)不能給一位教師安排兩門不同的課程上課；

2. 同一時(shí)間段內(nèi)一個(gè)班級(jí)只能安排一門課程；

3. 同一時(shí)間段內(nèi)一個(gè)教室只能安排一門課程；

4. 教室的最大容量應(yīng)不小于上課的學(xué)生人數(shù)；

除上述的基本約束外，還有一些模糊約束，這些模糊約束可以使課表更加合理、更加人性化。

模糊約束條件有：

1.根據(jù)課程類型以及學(xué)生接受程度，來為這類課程安排最合適的時(shí)間段；如：專業(yè)課、必修課一般安排在早上，而文體類的課程通常安排在下午；

2.理論性課程盡量分散安排，即一門課盡量分散在一周的某幾天，并且中間盡量隔開，以便教師能夠有充足的時(shí)間備課，而學(xué)生也有足夠的時(shí)間消化已學(xué)到的知識(shí)；理論與實(shí)踐并重的課程最好將理論與實(shí)踐課穿插安排，可以在學(xué)生學(xué)習(xí)完理論課程后及時(shí)通過動(dòng)手操作加以鞏固，有利于學(xué)生對(duì)知識(shí)的理解、掌握；

3.學(xué)生的上課時(shí)間不能過分集中，應(yīng)盡量避免某一天課程安排的很滿而另一天卻沒課的情況；

4.排課時(shí)，應(yīng)盡量把知識(shí)性強(qiáng)的和趣味性強(qiáng)的、理論性的和理解性的課程交叉安排；

5.考慮教師的工作負(fù)荷，一天內(nèi)上課一般不超過四節(jié)；

6. 同一教師，同一門課程可以盡量安排在相對(duì)固定的教學(xué)場(chǎng)所，不但方便記憶， 還有利于教師和學(xué)生的適應(yīng)；

7.教師或?qū)W生接連兩門課程地點(diǎn)盡量比較接近；

8.對(duì)于教師、學(xué)生可能提出的一些特殊要求，根據(jù)情況安排，如若合理，盡量滿足。

另外，對(duì)于其它特殊情況，如分單、雙周上的課程，不確定周次的課程等，也需要綜合考慮，合理安排。此外對(duì)于計(jì)算機(jī)預(yù)排的結(jié)果，還可以根據(jù)實(shí)際情況，通過人工交互的方式進(jìn)行修改。

4.5基于遺傳算法的智能排課算法

1.連接數(shù)據(jù)庫獲得課程信息，班級(jí)信息，教室信息，公共課程信息，系別信息；

2.根據(jù)多媒體教室資源數(shù)據(jù)生成空白時(shí)間安排表；

3.按照群體中個(gè)體數(shù)量，隨機(jī)地將課程序號(hào)數(shù)據(jù)裝入到時(shí)間安排表中；

4.計(jì)算每個(gè)個(gè)體的適應(yīng)度向量，即個(gè)體染色體適應(yīng)度函數(shù)值；

5.若適應(yīng)度達(dá)到事先設(shè)定的進(jìn)化結(jié)束要求（無繼續(xù)收斂），或進(jìn)化代數(shù)達(dá)到最大代數(shù)，則跳轉(zhuǎn)到9；

6.根據(jù)4所得適應(yīng)度值，計(jì)算交叉、變異和選擇概率，根據(jù)概率選擇優(yōu)秀的時(shí)間安排方案，并淘汰掉適應(yīng)度值低的方案；

7.應(yīng)用交叉、變異算子與染色體；

8.繼續(xù)循環(huán)，跳到5；

9.從較優(yōu)群體中選擇一個(gè)最優(yōu)方案，生成最優(yōu)時(shí)間安排表。

5.結(jié)束語

本文中的自動(dòng)排課算法實(shí)現(xiàn)了教師、教室、課程、時(shí)間等資源在教學(xué)活動(dòng)中的合理配置與安排，把教學(xué)工作者從繁雜的手工排課工作中解脫出來。同時(shí)，也減少了排課過程中可能出現(xiàn)的沖突錯(cuò)誤，保證了教學(xué)秩序的正常運(yùn)行，大幅度的提高了教務(wù)教學(xué)管理水平以及教務(wù)人員的工作效率。雖然實(shí)現(xiàn)了自動(dòng)排課功能，而在實(shí)際應(yīng)用中，還應(yīng)該考慮到因?yàn)橐恍┨厥庠驅(qū)е碌男枰止ふ{(diào)節(jié)課表安排的情況，所以在今后還需要改善這方面的功能。

參考文獻(xiàn)：

[1]修磊， 楊社堂. 高校排課管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].太原理工大學(xué)學(xué)報(bào)，2006， 37（5）：75-77.

[2]張海濤， 劉萬軍. 高校計(jì)算機(jī)排調(diào)課算法研究[J].遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2005，24（1）： 110-111.

[3]袁宏武， 薛模根， 姚翎. 基于規(guī)則的個(gè)性化課表生成算法[J].計(jì)算機(jī)工程，2006，32（4）， 194-224.

[4]蘇仰娜. 基于遺傳算法的優(yōu)化排課系統(tǒng)[J].河南大學(xué)學(xué)報(bào)（自然科學(xué)版），2005， 35（1）， 75-78.

[5]魏敏.基于遺傳算法電大排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].復(fù)旦大學(xué)，2011.

課題信息：課題名稱：遺傳算法在高等學(xué)校智能排課問題方面的研究，課題類別： 內(nèi)蒙古自治區(qū)高等教育科學(xué)“十二五”規(guī)劃課題課題，批準(zhǔn)號(hào)：NGJGH2014083。