基于遺傳算法的高校在線排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

樊偉宏 ，楊文婷 ，王 昊 ，劉 文

（1.新疆農(nóng)業(yè)大學(xué)科學(xué)技術(shù)學(xué)院，新疆烏魯木齊830052；2.新疆農(nóng)業(yè)大學(xué)思想理論教研部，新疆烏魯木齊830052）

基于遺傳算法的高校在線排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

樊偉宏1，楊文婷2，王 昊1，劉 文1

（1.新疆農(nóng)業(yè)大學(xué)科學(xué)技術(shù)學(xué)院，新疆烏魯木齊830052；2.新疆農(nóng)業(yè)大學(xué)思想理論教研部，新疆烏魯木齊830052）

高校排課工作作為教學(xué)管理中一個(gè)很重要的環(huán)節(jié)，影響因素較多，是一種典型的組合優(yōu)化問題。群體智能算法的研究發(fā)展，為自動(dòng)排課問題解決提供了可能。通過分析研究高校排課過程，選用遺傳算法設(shè)計(jì)在線排課系統(tǒng)，并基于PHP+MYSQL平臺(tái)，利用ThinkPHP框架實(shí)現(xiàn)高校在線排課系統(tǒng)。系統(tǒng)經(jīng)過測試，取得良好效果。有效解決了排課問題。減輕了教務(wù)管理人員工作壓力，提升了教學(xué)服務(wù)質(zhì)量。為相關(guān)研究提供一定的借鑒。

在線排課；組合優(yōu)化；遺傳算法；智能排課

隨著網(wǎng)絡(luò)技術(shù)和計(jì)算機(jī)技術(shù)的迅猛發(fā)展，在線排所需的外部條件以完全具備，很多學(xué)者也在智能排課領(lǐng)域進(jìn)行探索研究。有一定的理論和實(shí)踐基礎(chǔ)。高校排課工作要兼顧多個(gè)方面，且人工排課過程中出現(xiàn)的問題越來越多，人工排課耗時(shí)長，效率低。且隨著擴(kuò)招政策實(shí)施，學(xué)生人數(shù)，專業(yè)開設(shè)及開班數(shù)量不斷增加，排課過程越來越復(fù)雜。智能排課問題稱為一個(gè)研究課題。通過分析和查閱文獻(xiàn)，排課過程中的各種影響因素，組合起來其實(shí)是一種典型的組合優(yōu)化問題[1]。目前智能算法的研究為組合優(yōu)化問題的解決提供了有力的工具。有很多算法都可解決這樣的問題。本文通過研究遺傳算法[2]，和分析排課過程。提出利用遺傳算法設(shè)計(jì)高校在線排課系統(tǒng)的思路和具體的實(shí)現(xiàn)過程。

1 問題的描述

1.1 排課問題說明

排課過程有多約束、多目標(biāo)的組合優(yōu)化特點(diǎn)，為了找到問題解決最優(yōu)解，避免課程安排結(jié)果在時(shí)間、教室、教師、班級(jí)等方面的相互沖突，須有相應(yīng)的約束條件來實(shí)現(xiàn)。而在實(shí)際的排課過程中，時(shí)間均勻、老師滿意度、教室利用率、教室類型相符、教室座位數(shù)、班級(jí)上課沖突、老師上課沖突等方面，是衡量課程安排是否達(dá)到最佳效果的主要依據(jù)。

1.2 排課約束條件

排課過程中的約束條件有兩類:硬約束和軟約束[3-5]。硬性約束條件是一定要滿足的條件，直接影響著排課結(jié)果的正確性。因此硬性約束條件對(duì)于各個(gè)高校都是相近的，這些約束條件直接在系統(tǒng)設(shè)計(jì)時(shí)，直接在程序中進(jìn)行限制，是系統(tǒng)不可修改的部分。一張正確的排課結(jié)果應(yīng)至少滿足以下硬約束條件:

1）同一上課時(shí)間段內(nèi)的約束:教師和教授課程是1:1關(guān)系；班級(jí)和所學(xué)課程是1:1關(guān)系；教室必須容下上課的學(xué)生數(shù)，即Ks＜Xr（Ks:教室座位數(shù)，Xr:上課學(xué)生人數(shù)）；教師和使用的教室1:1關(guān)系；教室和所排課程1:1關(guān)系。

2）所安排的教室類型和課程中制定的類型一致。

……

相對(duì)硬性約束而言，軟約束條件不具備強(qiáng)制性。在實(shí)際教學(xué)當(dāng)中為了教學(xué)效果更好，在可能的情況下盡量滿足這些軟約束條件。因此軟約束條件對(duì)于各個(gè)高校可能是不相同的，這也是排課系統(tǒng)設(shè)計(jì)的難點(diǎn)，這些約束條件不能直接設(shè)計(jì)到系統(tǒng)中，需要根據(jù)不同高校的情況設(shè)計(jì)相應(yīng)的策略。軟約束條件策略設(shè)定應(yīng)考慮到以下方面:

1）老師的滿意度:盡量在重復(fù)利用資源和注意時(shí)間分布的情況下，滿足老師對(duì)排課的需求。

2）學(xué)生接受知識(shí)的規(guī)律:課程的學(xué)時(shí)安排盡量均勻，不能集中的安排同一課程。

3）生物規(guī)律:學(xué)生經(jīng)過一夜休息，上午注意了比較集中盡量安排理論課，下午盡量安排試驗(yàn)或?qū)嵺`性課程。

4）學(xué)生的滿意度:在重復(fù)利用資源和注意時(shí)間分布的情況下，晚上和周末盡量不安排課程。

2 遺傳算法在排課過程中的應(yīng)用

2.1 染色體編碼

利用遺傳算法實(shí)現(xiàn)自動(dòng)排課首要解決的問題是將基礎(chǔ)信息（教師，教室，課程，班級(jí)，時(shí)間）轉(zhuǎn)化成虛擬的編碼，也就是轉(zhuǎn)化成染色體，染色體目前設(shè)計(jì)方法有兩種二進(jìn)制和十進(jìn)制[6-9]，染色體設(shè)計(jì)成二進(jìn)制，雖然有利于雜交和變異，但使用的數(shù)據(jù)串較長，而且二進(jìn)制轉(zhuǎn)換較為復(fù)雜，本系統(tǒng)設(shè)計(jì)采用十進(jìn)制數(shù)進(jìn)行編碼形式，如圖1所示，例如:教師編碼為1002，所教授課程為“C語言程序設(shè)計(jì)”，課程的編號(hào)為1078，在編號(hào)為7224的教室上課，上課時(shí)間是隨機(jī)產(chǎn)生，每周上課時(shí)間段標(biāo)示方法設(shè)計(jì)為:每天分為5個(gè)時(shí)間段（含晚上的課，正常每天4個(gè)時(shí)間段），每周7天，每周共35個(gè)時(shí)間段，從周一第1節(jié)標(biāo)示為01，第5節(jié)課標(biāo)示為05，周二第1節(jié)就是06，直到星期日第5節(jié)標(biāo)示為35，共有01～35，35個(gè)時(shí)間段。假如隨機(jī)產(chǎn)生三個(gè)時(shí)間段“02”、“12”、“22”即代表的上課時(shí)間為周一第二節(jié)，周三第二節(jié)，周五第三節(jié)，則生成的染色體編碼為:“100210787224021222”，之后需要對(duì)后10位編碼“7224021222”即對(duì)教室和3個(gè)時(shí)間段進(jìn)行交叉，變異操作，而教師，課程，班級(jí)保持不變，從而演化出的染色體編碼更加合理。根據(jù)染色體編碼生成的課程表，進(jìn)而利用適應(yīng)度函數(shù)進(jìn)行判斷，適應(yīng)度滿足一定的取值范圍時(shí)，生成的課表才能達(dá)到最終要求，標(biāo)示獲得最優(yōu)解。

圖1 染色體編碼示意圖

2.2 適應(yīng)度函數(shù)概述

在排課系統(tǒng)中，為了滿足遺傳算法，而把約束條件轉(zhuǎn)化成數(shù)字，也就是適應(yīng)度，我們設(shè)置了適應(yīng)度函數(shù)來判斷該個(gè)體是否滿足最優(yōu)解，適應(yīng)度函數(shù)如下:

value=first_value+award_value-restrain_value

其中value表示為最終適應(yīng)度，first_value表示為初始化適應(yīng)度，初始值為100，restrain_value為硬約束條件，當(dāng)不滿足一個(gè)硬約束條件時(shí)restrain_value就會(huì)加10，award_value為軟約束條件，當(dāng)滿足一個(gè)軟約束條件時(shí)award_value就會(huì)加1，最終得到的value大于或等于100時(shí)表示得到一個(gè)解，而大于100的值越大表示離最優(yōu)解越近。

2.3 沖突檢測函數(shù)概述

在排課系統(tǒng)中，總有一些無法滿足條件的數(shù)據(jù)，因此在遺傳算法排課之后，使用沖突檢測函數(shù)，對(duì)那些無法滿足條件的數(shù)據(jù)進(jìn)行掃描查詢最優(yōu)解，使用改進(jìn)后的電梯調(diào)度算法進(jìn)行結(jié)果選優(yōu)[11-13]，排課的時(shí)間段有周六和周日，為了盡量避免周六和周日，掃描會(huì)先記錄當(dāng)前時(shí)間段后向周一的第一節(jié)進(jìn)行掃描，為了避免無解，掃描時(shí)加入晚上的時(shí)間段，如掃描到周一第一節(jié)課時(shí)還是無解后恢復(fù)原點(diǎn)向后掃描，這里加入周六和周日，避免完全無解。

2.4 遺傳算法的操作

2.4.1 初始化種群

選中需要排課的班級(jí)組成一個(gè)集合記做R（nn∈正整數(shù)），選中的班級(jí)已經(jīng)完成課程安排，且任課教師已進(jìn)行選課，課程所需的教室類型已確定，這里課程教室類型記做C，隨機(jī)生成幾個(gè)時(shí)間段記做為Tn（n∈正整數(shù)且n≤5），且任意的時(shí)間段Ti滿足Ti-5≥0。隨機(jī)產(chǎn)生的教室號(hào)記做cn滿足cn∈C，且學(xué)生人數(shù)≤教室座位數(shù)。在本階段不能滿足教師在同一時(shí)間內(nèi)只能教一門課程，這需要其他操作來解決。

2.4.2 選擇操作

在排課系統(tǒng)中，每個(gè)班級(jí)代表一個(gè)獨(dú)立的個(gè)體，遺傳算法的操作在每個(gè)個(gè)體內(nèi)進(jìn)行，選擇操作是每一代只有兩條染色體進(jìn)行操作，默認(rèn)進(jìn)行500代遺傳，每代按一定的概率出現(xiàn)兩條染色體。

2.4.3 遺傳操作

遺傳操作是將兩條染色體進(jìn)行交換，主要交換的是時(shí)間和教室產(chǎn)生新的染色體，將該染色體和父代染色體進(jìn)行適應(yīng)度對(duì)比，產(chǎn)生不同的適應(yīng)度。進(jìn)行適應(yīng)度選擇，適應(yīng)度較高者被選中，反之被放棄。

2.4.4 變異操作

在遺傳操作后新生的兩條染色體按一定的概率發(fā)生變異，變異主要是針對(duì)時(shí)間段染色體編碼，變異只在原點(diǎn)的上下4個(gè)時(shí)間段改變，存在排課時(shí)間段在晚上的可能性。通過變異操作可以得到更多的解。

2.4.5 自動(dòng)定位與消除沖突操作

通過自動(dòng)定位與消除沖突操作，對(duì)無法滿足條件的數(shù)據(jù)進(jìn)行掃描求解，可能求出的解不是想要的結(jié)果，但能排除條件苛刻的染色體[14]。

3 系統(tǒng)設(shè)計(jì)

3.1 系統(tǒng)的設(shè)計(jì)思路

系統(tǒng)的設(shè)計(jì)充分利用軟件工程的方法，經(jīng)可行性研究，需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)編碼測試，交付使用等步驟完成系統(tǒng)的設(shè)計(jì)和開發(fā)。系統(tǒng)總體工作流程如圖2所示。

圖2 系統(tǒng)的總體工作流程

教務(wù)管理人員錄入基礎(chǔ)信息。系統(tǒng)管理員設(shè)定遺傳算法排課參數(shù)（多次試驗(yàn)得出結(jié)論）教師選擇本學(xué)期所授課程，錄入上課條件。系統(tǒng)進(jìn)行自動(dòng)排課。排課過程中首先滿足硬約束策略。進(jìn)而滿足軟約束策略。排課結(jié)束生成課表。教務(wù)人員根據(jù)不同的條件查詢需要的課表。

3.2 系統(tǒng)的總體設(shè)計(jì)

系統(tǒng)的總體設(shè)計(jì)功能圖，如圖3所示。

圖3 系統(tǒng)總體功能模塊圖

3.3 系統(tǒng)自動(dòng)排課

自動(dòng)排課首先批量選擇要排課的班級(jí)，利用遺傳算法對(duì)選中班級(jí)進(jìn)行排課操作。結(jié)果產(chǎn)生的是最優(yōu)解。需將結(jié)果轉(zhuǎn)化為課表。方便進(jìn)行后期的查詢和其他操作。遺傳算法自動(dòng)排課流程如圖4所示，實(shí)現(xiàn)自動(dòng)排課過程代碼中類的調(diào)用關(guān)系如圖5所示。經(jīng)自動(dòng)排課操作，沒有獲得最優(yōu)解得班級(jí)信息，系統(tǒng)自動(dòng)導(dǎo)出數(shù)據(jù)，需手動(dòng)進(jìn)行簡單調(diào)整[16]。

圖4 遺傳算法自動(dòng)排課流程圖

圖5 自動(dòng)排課過程及其類的調(diào)用關(guān)系

3.4 人工排課

系統(tǒng)設(shè)計(jì)中考慮到個(gè)別特殊情況需要教務(wù)人員手動(dòng)排課。主要對(duì)個(gè)別班級(jí)排課，或?qū)ψ詣?dòng)排課結(jié)果進(jìn)行局部的修正。在人工排課過程中對(duì)于不滿足硬約束的情況系統(tǒng)會(huì)及時(shí)作出提示。

4 系統(tǒng)測試

系統(tǒng)在硬件環(huán)境為:內(nèi)存6G，i7CPU，操作系統(tǒng)為:window7 64位系統(tǒng)。使用有25個(gè)教室，20個(gè)班級(jí)，每個(gè)班級(jí)7門課，49門課程，20位教師為數(shù)據(jù)，并為個(gè)別教師設(shè)計(jì)特殊時(shí)間約束。并建立排課策略。在代失數(shù)、交叉率、變異率不同的情況下測試結(jié)果如表1所示。

7個(gè)測試都通過了，可以看出，代失數(shù)越少，運(yùn)行速度較快，在相同的環(huán)境和代失數(shù)下，交叉率和變異率越低，運(yùn)行速度較快，但得到解越少，通過上述測試發(fā)現(xiàn)代失數(shù)為50，交叉率為0.2，變異率為0.05時(shí)得到了最多解，取得較好效果。但也要根據(jù)實(shí)際的運(yùn)行環(huán)境，配置較高的計(jì)算機(jī)可以相對(duì)應(yīng)的增加代失數(shù)，同樣選擇要排課的班級(jí)數(shù)越多，所用時(shí)間越長，建議每次排課選擇一定數(shù)量的班級(jí)。通過5次排課的數(shù)據(jù)進(jìn)行分析，發(fā)現(xiàn)排出的課程表有一些細(xì)節(jié)問題，單雙周課程劃分不到位，針對(duì)需要特殊教室的課程排課不理想，排課時(shí)應(yīng)先排需要特殊教室的課程，而針對(duì)基礎(chǔ)信息的錄入較為麻煩，不能一次性導(dǎo)入。

表1 遺傳算法代失數(shù)、交叉率、變異率與排課效果、用時(shí)對(duì)照表

5 結(jié) 論

通過分析高校在線排課問題，該問題屬于典型的組合優(yōu)化問題。提出利用遺傳算法解決排課問題的思路。并采用軟件工程的思想通過需求分析、總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、系統(tǒng)編碼測試等環(huán)節(jié)，基于PHP+MYSQL平臺(tái)，利用ThinkPHP框架開發(fā)MVC模式的高校在線排課系統(tǒng)。系統(tǒng)實(shí)現(xiàn)了在線錄入課程計(jì)劃、老師選課、教室信息管理、自動(dòng)排課、手動(dòng)排課、系統(tǒng)管理，可設(shè)置查詢條件如:班級(jí)，教室、教師等進(jìn)行查詢并打印生成的課表等功能。系統(tǒng)中采用了RBAC權(quán)限控制，實(shí)現(xiàn)了不同角色操作人員登錄，所擁有不同的權(quán)限，提高系統(tǒng)的安全性。系統(tǒng)在PC機(jī)上經(jīng)過測試取得較好效果，取得一定的測試數(shù)據(jù)。系統(tǒng)的運(yùn)行緩解了教務(wù)管理人員的工作壓力，節(jié)省了一定的人力物力。但對(duì)計(jì)算機(jī)硬件資源消耗較大，在后期還需要在算法上進(jìn)行優(yōu)化，在系統(tǒng)設(shè)計(jì)方面進(jìn)行改進(jìn)。

[1]屈正庚.一種邏輯決策的排課算法[J].電子設(shè)計(jì)工程，2012（7）:13-15.

[2]葉碧蝦.遺傳算法在排課系統(tǒng)中的優(yōu)化研究[J].吉林師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2014（2）:134-139.

[3]王璐，楊亞偉.一種改進(jìn)的遺傳算法在年度排課問題中的應(yīng)用[J].計(jì)算機(jī)與數(shù)字工程，2016（8）:1619-1624.

[4]梁慧娜，周勁樺.基于遺傳算法的實(shí)訓(xùn)室多重優(yōu)先排課方法研究[J].微型機(jī)與應(yīng)用，2014（19）:91-93，101.

[5]錢海軍，郭澤睿.開放教育排課問題約束分析與數(shù)學(xué)建模[J].軟件工程，2016（9）:26-29.

[6]王瀚韜，李強(qiáng)，鄭永康.基于魚群算法的電梯群控調(diào)度算法[J].機(jī)電工程，2013（7）:888-892.

[7]嚴(yán)宏.教學(xué)資源配置優(yōu)化中遺傳算法的應(yīng)用與改進(jìn)[J].計(jì)算機(jī)技術(shù)與發(fā)展，2016（3）:130-134，139.

[8]靖靖，楊梅.基于滿意度的最優(yōu)排課方案[J].西南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2016（1）:185-188.

[9]楊彥明，岳翠翠，李其申.軍隊(duì)任職院校排課問題的數(shù)學(xué)建模[J].計(jì)算機(jī)與現(xiàn)代化，2012（11）:14-17.

[10]張赫男，張紹文.采用改進(jìn)的混合遺傳算法求解高校排課問題[J].計(jì)算機(jī)工程與應(yīng)用，2015（5）:240-246.

[11]余久久.基于探索性測試思想的可復(fù)用測試用例設(shè)計(jì)過程研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2015（9）:187.

[12]謝宗霖，劉亞君，霍偉敬，等.基于整數(shù)規(guī)劃的排課優(yōu)化問題[J].計(jì)算機(jī)與現(xiàn)代化，2015（7）:15-19.

[13]張艷紅，王玲玲，騰東興.基于空間模型和遺傳算法的高校排課系統(tǒng)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2015（9）:49-55.

[14]楊博凱，李曉瑜，黃一鳴，等.基于遺傳算法的高考志愿填報(bào)排序問題的研究[J].計(jì)算機(jī)科學(xué)，2016（S1）:390-394.

[15]樊偉宏，劉文，孫士鶴，等.基于B/S模式的高校試卷檔案管理系統(tǒng)設(shè)計(jì)[J].軟件導(dǎo)刊，2015（9）:134-136.

[16]楊彬彬.繼續(xù)教育學(xué)院綜合管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].成都：電子科技大學(xué)，2014.

Design and implementation of online course scheduling system based on genetic algorithm in colleges and universities

FAN Wei-hong1，YANG Wen-ting2，WANG Hao1，LIU Wen1
（1.Academy of Science and Technology of Xinjiang Agricultural University，Urumqi830052，China；2.Department of Ideological and Theoretical Teaching Research of Xinjiang Agricultural University，Urumqi830052，China）

As a very important part of the teaching management，the course arrangement of the university is a kind of typical combinatorial optimization problem，which has many affecting factors.The research and development of swarm intelligence algorithm provides the possibility to solve the problem of automatic course scheduling.Through the analysis of the course scheduling process，the genetic algorithm is used to design online course scheduling system，based on the PHP+MYSQL platform，use framework of ThinkPHP to achieve online course scheduling system.The system has been tested，and good results have been achieved.Effectively it solves the problem of course arrangement.The work pressure of the educational administration staff is reduced，and the teaching service quality is improved，which provides some reference for the related research.

online course arrangement；combination optimization；genetic algorithm；intelligentized course arrangement

TN302

A

1674-6236（2017）23-0019-05

2016-11-22稿件編號(hào)：201611178

新疆農(nóng)業(yè)大學(xué)科學(xué)技術(shù)學(xué)院青年科研啟動(dòng)基金項(xiàng)目（2016KJKY007）；新疆維吾爾自治區(qū)高?？蒲杏?jì)劃（XJEDU2016I049）

樊偉宏（1985—），男，陜西洛南人，助教。研究方向:計(jì)算機(jī)技術(shù)、數(shù)據(jù)分析。