基因遺傳算法在智能排課系統中的應用研究

陳莉莉 胡寧

摘要：本文主要針對當前智慧校園環境下高校在多種類型實驗室、多用途的智慧教室、多校區、多學科類型教師授課等復雜環境下，對教學管理過程排課的約束條件、流程處理進行研究，利用基因遺傳算法在處理排課系統中的優勢，以此來解決高校教務部門部分排課問題，生成最優化的教學課表。

關鍵詞：遺傳算法；智能排課；教學管理；智慧校園

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2019）06-0159-03

On Design of Intelligent Classroom Scheduling System Based on Genetic Algorithm

CHEN Li-li， HU Ning

（Jinling Institute of Technology， Nanjing 211169， China）

Abstract： The study explores the approaches to classroom scheduling in the multi-dimensional context of College Smart Campus concerning labs， classrooms， and teaching staff. It is concluded that genetic algorithms can be employed to achieve optimum course schedules because of their advantages in coping with multi-objective optimization and large-scale classroom scheduling under various mission constraints.

Key words： Genetic algorithm； Intelligent classroom scheduling； Teaching Management； Smart Campus

隨著智慧校園和一站式網上服務大廳在高校數字化校園中的廣泛應用，高校的教學和管理隨之發生了巨大的變革，微課、互動教學和翻轉課堂等新型的教學模式被不斷的應用到教學體系中，其課堂教學質量和效果也得到了很大的提高。近些年來，為了不斷滿足社會對高技術人才的需求，高校規模隨之不斷擴大，對高校教學管理提出了更高的要求，特別是在多種教學模式和環境的約束下，教師、課程、各類型實驗室、多用途的智慧教室、多校區等環境下的教學排課已經逐漸成為高校教學管理工作中一個難點，每學期如何設計出一套即符合師生上課的實際需求又能夠充分統籌利用好學校的各類資源的教學課表，以達到最優的教學目標，已經是各高校教學管理人員研究的重點課題。

1 高校智能排課系統發展現狀及存在問題

我國高校排課方面的工作研究始于 1980 年左右，初期主要研究的是各類型課程的規劃、班級與教師的匹配模型兩大類的問題。排課問題是一個多目標、多約束條件的組合優化問題，是一個NP完全問題[1]，在實際排課過程中需要綜合考慮教師、教室、校區、課程設置等多種約束條件，例如高校的體育、數學、英語等基礎課程基本采用的都是合班教學，學科專業課程都是小班教學，如數據結構、軟件工程等，而且還需要考慮各學科的不同教學計劃等諸多條件，因此，通過排課系統很難自動生成滿意的課表。

對于高校排課問題，很多學者對此進行了廣泛的研究，提出了很多不同的解決方法。有些是基于傳統和標準模式下的算法進行排課系統的設計，再根據教務管理部門和工作人員的經驗進行觀察調整課表，最終形成教學計劃和課表；也有基于改進的流程實現排課系統，主要采用不同的排課算法，如模擬退火算法、回溯算法、貪心算法等，在實現的過程中均需要大量的人工干預，且在實際使用過程中也存在較多問題，主要體現在以下幾個方面：

（1）基礎信息錄入不方便、不準確。目前，大多數高校智慧校園還處于建設階段，其教務排課系統相對獨立，與校內主數據平臺信息交互和共享接口均不完善，師生和教學場所等信息都需要教學管理人員不斷的更新，對教務排課系統的實時性和準確性無法保障。

（2）對于約束條件定義不完整。目前高?；径疾少徚瞬煌愋偷闹悄芘耪n系統，大多數為標準化的配置。實際上，高校排課中除了需要考慮基本的約束條件外，每所高校都有各自的個性化需求，其標準化的排課系統難以適應高校個性化的約束功能和條件，這些約束條件的缺失和不完整，對排課計劃和方案實施的可行性都會產生影響。

（3）難以實現智能化排課系統。教務排課系統在高校使用的過程中已經在不斷的優化流程和算法，實現了根據排課過程不同階段，不斷地對教學方案和計劃進行調整，從而達到自主收斂，生成適合高校師生和教學條件的排課方案。但是如何根據每所高校的不同情況制定個性化教學需求，找到最優化的智能處理算法，達到較好的收斂效果，更加適合師生教學的排課方案，是每個高校教學管理部門需要不斷處理的難點問題之一。

2 智能排課系統算法的問題描和述約束分析

2.1排課問題概述

在高校教學管理工作中，排課是學校各類教學管理工作的必須和前提保障。在每學期開學前，高校教務管理部門都會重新收集和統計下學期的額教學計劃、教師和學生基本信息、各校區的基本資源、各院部的特殊要求等，然后根據實際情況針對全校不同校區不同院系進行排課。排課工作會涉及到上課時間、上課地點、任課教師、教學計劃等眾多因素，任何因素的調整或變更都會影響到整個排課系統，而且在大多數情況下都會因為教師資源、教學場地和不同聽課人員等多種因素的影響，在編排課表的過程中出現各種矛盾和沖突。因此排課工作就是要綜合考慮學校各方面的因素，安排出能夠最大化提高教學資源和利用率，且盡可能符合師生意愿和最佳教學效果的全校課表。

2.2排課系統的約束條件

合理的教務排課課表必須遵循如下的基本約束條件：

（1）同一時間同一地點只能安排一門課程；

（2）同一時間同一教師只能安排一門課程；

（3）同一時間同一學生只能安排一門課程；

（4）同一專業不同課程不能安排在同一時間；

（5）班級上課人數不能超過上課教室實際可容納人數；

（6）教學計劃、教學課時、教學任務不能隨意變更。

除上述的基本約束條件之外，還有存在一些非必要約束條件，主要體現在如何提高實際課表編排的真實性和合理性，使得教學管理服務工作更加智能和人性化。結合筆者本校的實際情況，主要存在如下非必要約束條件：

（1）所有課程盡可能合理均勻分布，課程不能連天安排；

（2）每位教師和學生每天的課程不能跨校區安排；

（3）學生同一天連續節次的兩門課程安排地點時考慮就近原則；

（4）理論性較強課程盡量每天間隔時間段內合理分布，將理論學習、實踐教學、體育課程等相繼排課；

（5）專業核心課程盡量安排在上午1至2節、選修課程盡量安排在下午或晚間教學；

（6）對特殊學院特殊要求的課程先行排課，盡量滿足。

另外，根據每所高校的不同情況，對實際存在的師生情況、教學場所情況等具體問題具體分析。

2.3排課系統算法的數學描述

高校排課系統想要找到最優化的智能處理算法，達到較好的收斂效果，必須依靠智能化的軟件來實現，實現智能化的軟件就需要對現有的約束條件進行詳細的描述來，且將智能排課問題描述以數學建模的模型為基礎結構，建立排課系統的數學描述和數學模型，更有利于實現智能化的自動排課功能。

3 基因遺傳算法在智能排課系統中的應用

基于排課系統復雜性，近幾年來，隨著高校智慧校園的不斷發展，以基因遺傳算法為代表的各類智能算法被廣泛的應用到智能排課系統中，在很大程度上適應了各高校的個性化需求，取得了良好的效果。

3.1基因遺傳算法的基本原理

基因遺傳算法是一種高度模仿生物進化的理論模型，遵循自然界中優勝劣汰、適者生存的規則，模擬生物進化進程的啟發式智能算法。借鑒這種基本原理，可以引入到計算數學中來處理各類型應用程序，從而得到最優化搜索問題的有效方法。為了更好的理解其流程算法，必須先了解其最基本的一些概念和術語。比如個體指染色體上的基因表現特征的實體，在一般問題中用于代表染色體；種群指在某一時間段內占據一定空間的同一物種的所有個體；適應度指用來衡量種群中某個體針對個性化環境的適應程度，適應度是描述個體性能的主要指標，將直接影響到遺傳算法的收斂速度和排課系統能否最終找到最優解。

3.2基因遺傳算法迭代的基本步驟和流程設計

基因遺傳算法的整個過程就是不斷尋找問題最優解的過程，在每次迭代過程中都會給出新解，每個解都會利用適應度函數進行評價，保留適應度高的染色體再進行迭代，其算法的主要流程描述如下。

首先利用人工對基因進行編碼，給定起始種群規模，其中每一個染色體由多個基因組成，多個染色體組成一個種群；其次構建適應度函數，對種群中的每一個染色體計算其針對問題的適應度，然后利用算法進行交叉操作和變異操作，根據“優勝劣汰、適者生存”的原則來判斷是否有滿足最優性能的染色體；最后，對遺傳算法的進化結束條件進行判斷，主要包含兩種狀態，即達到了迭代過程的最大值或達到了最優化的要求。否則繼續進行迭代處理。筆者為了能夠清晰的表示遺傳算法的主要步驟和流程，結合基因遺傳算法給出的流程圖如圖1所示。

3.3基因遺傳算法在智能排課系統的需求和設計

利用基因遺傳算法對排課系統進行設計時，需要針對不同高校的排課業務流程、學校資源和個性化需求統籌分析，制定出符合高校排課規則的智能排課系統，由此來自動生成滿足教學管理需求的排課方案，以達到高校對智能排課系統的性能需求，其性能需求主要指標主要有算法在執行效率，系統的穩定性、可擴展性和可維護性等。其需求目標是能夠構建一套充分利用現有資源、有較高智能化自動處理能力，用戶使用時具有較強的靈活性、擴展性和多角色應用的高效智能排課系統，最終能夠最優化的滿足高校教學管理部門和師生的需求。筆者結合基因遺傳算法和實際工作給出的高校智能排課系統功能架構設計圖如圖2所示。

4 總結

本文對基因遺傳算法在高校智能排課系統中的設計和應用進行了研究，并針對當前高校建設規模和排課約束條件不斷增加的情況下，如何提高排課的效率和效果進行了分析。從目前實施的效果來看，遺傳算法作為一種尋求最優解的算法，利用其作為排課處理的核心算法，研究各類約束條件，優化問題求解模式，構建適應度函數，實現智能領域的排課方案，解決了高校教務部門部分排課問題，但是，如何能夠更好的提高多約束條件下的排課效率，獲得全局最優解，還需要進一步研究和探討。

參考文獻：

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

[2] 李新良. 基于移動互聯網的智慧校園體系架構研究[J]. 職教與經濟研究， 2016（3）： 54-58.

[3] 吳松慧. 基于遺傳算法的智能排課系統設計與實現[D]. 蘇州大學， 2016.

[4] 吳衛東. 高等院校智慧校園信息系統建設研究[J]. 數字技術與應用， 2016（1）： 85-86.

[5] 張越然. 改進型遺傳算法在高校排課系統中的應用[J]. 中國新通信， 2017（19）：100-104.

[6] 馬小姝，李海蕓. 遺傳算法在高校排課系統中的應用研究[J].信息與電腦， 2018（8）：76-80.

【通聯編輯：王力】