基于遺傳算法的高校在線排課系統的設計與實現

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

（1.新疆農業大學科學技術學院，新疆烏魯木齊830052；2.新疆農業大學思想理論教研部，新疆烏魯木齊830052）

基于遺傳算法的高校在線排課系統的設計與實現

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

（1.新疆農業大學科學技術學院，新疆烏魯木齊830052；2.新疆農業大學思想理論教研部，新疆烏魯木齊830052）

高校排課工作作為教學管理中一個很重要的環節，影響因素較多，是一種典型的組合優化問題。群體智能算法的研究發展，為自動排課問題解決提供了可能。通過分析研究高校排課過程，選用遺傳算法設計在線排課系統，并基于PHP+MYSQL平臺，利用ThinkPHP框架實現高校在線排課系統。系統經過測試，取得良好效果。有效解決了排課問題。減輕了教務管理人員工作壓力，提升了教學服務質量。為相關研究提供一定的借鑒。

在線排課；組合優化；遺傳算法；智能排課

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

1 問題的描述

1.1 排課問題說明

排課過程有多約束、多目標的組合優化特點，為了找到問題解決最優解，避免課程安排結果在時間、教室、教師、班級等方面的相互沖突，須有相應的約束條件來實現。而在實際的排課過程中，時間均勻、老師滿意度、教室利用率、教室類型相符、教室座位數、班級上課沖突、老師上課沖突等方面，是衡量課程安排是否達到最佳效果的主要依據。

1.2 排課約束條件

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

1）同一上課時間段內的約束:教師和教授課程是1:1關系；班級和所學課程是1:1關系；教室必須容下上課的學生數，即Ks＜Xr（Ks:教室座位數，Xr:上課學生人數）；教師和使用的教室1:1關系；教室和所排課程1:1關系。

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

……

相對硬性約束而言，軟約束條件不具備強制性。在實際教學當中為了教學效果更好，在可能的情況下盡量滿足這些軟約束條件。因此軟約束條件對于各個高校可能是不相同的，這也是排課系統設計的難點，這些約束條件不能直接設計到系統中，需要根據不同高校的情況設計相應的策略。軟約束條件策略設定應考慮到以下方面:

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

2）學生接受知識的規律:課程的學時安排盡量均勻，不能集中的安排同一課程。

3）生物規律:學生經過一夜休息，上午注意了比較集中盡量安排理論課，下午盡量安排試驗或實踐性課程。

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

2 遺傳算法在排課過程中的應用

2.1 染色體編碼

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

圖1 染色體編碼示意圖

2.2 適應度函數概述

在排課系統中，為了滿足遺傳算法，而把約束條件轉化成數字，也就是適應度，我們設置了適應度函數來判斷該個體是否滿足最優解，適應度函數如下:

value=first_value+award_value-restrain_value

其中value表示為最終適應度，first_value表示為初始化適應度，初始值為100，restrain_value為硬約束條件，當不滿足一個硬約束條件時restrain_value就會加10，award_value為軟約束條件，當滿足一個軟約束條件時award_value就會加1，最終得到的value大于或等于100時表示得到一個解，而大于100的值越大表示離最優解越近。

2.3 沖突檢測函數概述

在排課系統中，總有一些無法滿足條件的數據，因此在遺傳算法排課之后，使用沖突檢測函數，對那些無法滿足條件的數據進行掃描查詢最優解，使用改進后的電梯調度算法進行結果選優[11-13]，排課的時間段有周六和周日，為了盡量避免周六和周日，掃描會先記錄當前時間段后向周一的第一節進行掃描，為了避免無解，掃描時加入晚上的時間段，如掃描到周一第一節課時還是無解后恢復原點向后掃描，這里加入周六和周日，避免完全無解。

2.4 遺傳算法的操作

2.4.1 初始化種群

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

2.4.2 選擇操作

在排課系統中，每個班級代表一個獨立的個體，遺傳算法的操作在每個個體內進行，選擇操作是每一代只有兩條染色體進行操作，默認進行500代遺傳，每代按一定的概率出現兩條染色體。

2.4.3 遺傳操作

遺傳操作是將兩條染色體進行交換，主要交換的是時間和教室產生新的染色體，將該染色體和父代染色體進行適應度對比，產生不同的適應度。進行適應度選擇，適應度較高者被選中，反之被放棄。

2.4.4 變異操作

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

2.4.5 自動定位與消除沖突操作

通過自動定位與消除沖突操作，對無法滿足條件的數據進行掃描求解，可能求出的解不是想要的結果，但能排除條件苛刻的染色體[14]。

3 系統設計

3.1 系統的設計思路

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

圖2 系統的總體工作流程

教務管理人員錄入基礎信息。系統管理員設定遺傳算法排課參數（多次試驗得出結論）教師選擇本學期所授課程，錄入上課條件。系統進行自動排課。排課過程中首先滿足硬約束策略。進而滿足軟約束策略。排課結束生成課表。教務人員根據不同的條件查詢需要的課表。

3.2 系統的總體設計

系統的總體設計功能圖，如圖3所示。

圖3 系統總體功能模塊圖

3.3 系統自動排課

自動排課首先批量選擇要排課的班級，利用遺傳算法對選中班級進行排課操作。結果產生的是最優解。需將結果轉化為課表。方便進行后期的查詢和其他操作。遺傳算法自動排課流程如圖4所示，實現自動排課過程代碼中類的調用關系如圖5所示。經自動排課操作，沒有獲得最優解得班級信息，系統自動導出數據，需手動進行簡單調整[16]。

圖4 遺傳算法自動排課流程圖

圖5 自動排課過程及其類的調用關系

3.4 人工排課

系統設計中考慮到個別特殊情況需要教務人員手動排課。主要對個別班級排課，或對自動排課結果進行局部的修正。在人工排課過程中對于不滿足硬約束的情況系統會及時作出提示。

4 系統測試

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

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

表1 遺傳算法代失數、交叉率、變異率與排課效果、用時對照表

5 結 論

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

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

[2]葉碧蝦.遺傳算法在排課系統中的優化研究[J].吉林師范大學學報：自然科學版，2014（2）:134-139.

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

[4]梁慧娜，周勁樺.基于遺傳算法的實訓室多重優先排課方法研究[J].微型機與應用，2014（19）:91-93，101.

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

[6]王瀚韜，李強，鄭永康.基于魚群算法的電梯群控調度算法[J].機電工程，2013（7）:888-892.

[7]嚴宏.教學資源配置優化中遺傳算法的應用與改進[J].計算機技術與發展，2016（3）:130-134，139.

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

[9]楊彥明，岳翠翠，李其申.軍隊任職院校排課問題的數學建模[J].計算機與現代化，2012（11）:14-17.

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

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

[12]謝宗霖，劉亞君，霍偉敬，等.基于整數規劃的排課優化問題[J].計算機與現代化，2015（7）:15-19.

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

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

[15]樊偉宏，劉文，孫士鶴，等.基于B/S模式的高校試卷檔案管理系統設計[J].軟件導刊，2015（9）:134-136.

[16]楊彬彬.繼續教育學院綜合管理系統的設計與實現[D].成都：電子科技大學，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稿件編號：201611178

新疆農業大學科學技術學院青年科研啟動基金項目（2016KJKY007）；新疆維吾爾自治區高校科研計劃（XJEDU2016I049）

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