基因遺傳算法在智能排課系統(tǒng)中的應(yīng)用研究

陳莉莉 胡寧

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

關(guān)鍵詞：遺傳算法；智能排課；教學(xué)管理；智慧校園

中圖分類號：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

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

1 高校智能排課系統(tǒng)發(fā)展現(xiàn)狀及存在問題

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

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

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

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

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

2 智能排課系統(tǒng)算法的問題描和述約束分析

2.1排課問題概述

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

2.2排課系統(tǒng)的約束條件

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

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

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

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

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

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

（6）教學(xué)計劃、教學(xué)課時、教學(xué)任務(wù)不能隨意變更。

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

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

（2）每位教師和學(xué)生每天的課程不能跨校區(qū)安排；

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

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

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

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

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

2.3排課系統(tǒng)算法的數(shù)學(xué)描述

高校排課系統(tǒng)想要找到最優(yōu)化的智能處理算法，達到較好的收斂效果，必須依靠智能化的軟件來實現(xiàn)，實現(xiàn)智能化的軟件就需要對現(xiàn)有的約束條件進行詳細的描述來，且將智能排課問題描述以數(shù)學(xué)建模的模型為基礎(chǔ)結(jié)構(gòu)，建立排課系統(tǒng)的數(shù)學(xué)描述和數(shù)學(xué)模型，更有利于實現(xiàn)智能化的自動排課功能。

3 基因遺傳算法在智能排課系統(tǒng)中的應(yīng)用

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

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

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

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

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

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

3.3基因遺傳算法在智能排課系統(tǒng)的需求和設(shè)計

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

4 總結(jié)

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

參考文獻：

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

[2] 李新良. 基于移動互聯(lián)網(wǎng)的智慧校園體系架構(gòu)研究[J]. 職教與經(jīng)濟研究， 2016（3）： 54-58.

[3] 吳松慧. 基于遺傳算法的智能排課系統(tǒng)設(shè)計與實現(xiàn)[D]. 蘇州大學(xué)， 2016.

[4] 吳衛(wèi)東. 高等院校智慧校園信息系統(tǒng)建設(shè)研究[J]. 數(shù)字技術(shù)與應(yīng)用， 2016（1）： 85-86.

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

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

【通聯(lián)編輯：王力】