高校智能排課系統(tǒng)問題研究及算法改進(jìn)策略

張蕓蕓

摘? ?要：排課是高校教學(xué)管理的重要工作，其本質(zhì)是在學(xué)?，F(xiàn)有的軟、硬件環(huán)境下，合理地安排教師、學(xué)生、課程、教室等，使教學(xué)規(guī)劃有計(jì)劃、有秩序地進(jìn)行。本文在對(duì)高校的學(xué)生、教師和教務(wù)管理員進(jìn)行認(rèn)真的調(diào)研、訪談的基礎(chǔ)上，通過匯總分析得出：為更好地提高教室利用效率、確保教學(xué)有序進(jìn)行，通過某種智能策略算法來建立智能排課系統(tǒng)尤為重要。

關(guān)鍵詞：遺傳算法? 智能排課系統(tǒng)? 群體策略

排課是高校教學(xué)管理的重要工作，其本質(zhì)是在學(xué)校現(xiàn)有的軟、硬件環(huán)境下，合理地安排教師、學(xué)生、課程、教室等，使學(xué)校的教學(xué)規(guī)劃有計(jì)劃、有秩序地進(jìn)行。隨著高校學(xué)生人數(shù)的增多，院系開設(shè)課程的規(guī)模大幅上升，排課已經(jīng)成為一項(xiàng)極其復(fù)雜的工作，現(xiàn)在使用人工排課已經(jīng)無法滿足學(xué)校教學(xué)管理的需求，因此利用計(jì)算機(jī)來實(shí)現(xiàn)自動(dòng)化排課，已經(jīng)成為計(jì)算機(jī)應(yīng)用學(xué)科的一項(xiàng)重要任務(wù)。

1? 高校排課工作現(xiàn)狀研究

排課任務(wù)實(shí)質(zhì)上是根據(jù)學(xué)校的教學(xué)環(huán)境，包括教師數(shù)量、教學(xué)地點(diǎn)、教室數(shù)量和教學(xué)時(shí)間的限制下，能夠促使整個(gè)學(xué)校的所有課程正常有序地開展教學(xué)工作。高校排課問題是一個(gè)非常復(fù)雜的組合規(guī)劃問題，需要滿足各種約束條件，以保證在上課過程中，教師、學(xué)生和教室不會(huì)產(chǎn)生任何的沖突，也即不同級(jí)兩個(gè)或者多個(gè)班級(jí)在同一時(shí)間被安排在同一個(gè)教室，或者是同一個(gè)教師在同一時(shí)間被安排上了多門課程，導(dǎo)致教學(xué)無法正常進(jìn)行。前期，國(guó)內(nèi)的部分院校在進(jìn)行排課時(shí)，使用人工排課的方法，人工排課工作的主要方法是實(shí)施擺牌，就是將印有課程名字的小紙牌在畫有空的課程表的版面上進(jìn)行初排、調(diào)整，一邊依據(jù)排課經(jīng)驗(yàn)進(jìn)行設(shè)置，一邊觀察每門課程所在的位置是否合理，以便能夠形成一個(gè)有效的正常課程表。由于人工排課沒有任何的理論指導(dǎo)，也沒有進(jìn)行數(shù)學(xué)建模，主要依靠排課者的經(jīng)驗(yàn)，具有很大的弊端，這種方法適合于規(guī)模較小、課程少的學(xué)校，但是隨著高等院校規(guī)模的擴(kuò)大，對(duì)上萬名學(xué)生需要在一年中完成上萬節(jié)課程的設(shè)置，如果僅僅依靠人工進(jìn)行排課，那么將會(huì)花費(fèi)大量的人力、物力和財(cái)力，工作量非常的大，并且無法排除易于調(diào)整的課程表。

2? 高校智能排課系統(tǒng)傳統(tǒng)算法的局限性

隨著計(jì)算機(jī)技術(shù)的迅速發(fā)展，其擁有更強(qiáng)更快的數(shù)據(jù)處理能力，并且擁有高速運(yùn)算的特點(diǎn)，通過對(duì)排課實(shí)施建模，能夠在滿足時(shí)間、教師、教室、課程、學(xué)生等約束條件的同時(shí)，通過排課算法進(jìn)行求解，能夠有效的實(shí)現(xiàn)自動(dòng)化排課，提高排課的正確性和排課效率，節(jié)省人力、物力和財(cái)力，使教務(wù)管理人員從繁瑣、復(fù)雜的排課任務(wù)中解脫出來，推動(dòng)了排課工作的管理與發(fā)展，也間接地推動(dòng)了教學(xué)管理的信息化，具有非常重要的意義。

在排課過程中，系統(tǒng)涉及的約束條件非常多，主要包括教師、課程、教室、班級(jí)等，排課表實(shí)施編排過程中，要對(duì)上述主要約束條件進(jìn)行合理的規(guī)劃，不能夠產(chǎn)生任何的沖突，比如同一個(gè)教師在同一時(shí)間不能被安排多門課程，同一個(gè)班級(jí)在同一時(shí)間不能有兩個(gè)教師上課，并且滿足用戶需求資源，滿足教師的要求和限制。

目前，智能排課系統(tǒng)在進(jìn)行課程表排設(shè)過程中，通常采用的算法有蟻群算法、模擬退火算法、回溯法、基于規(guī)則的推理算法、遺傳算法等，隨著試題的增多，試題難度等級(jí)的逐漸加大，使用現(xiàn)有的算法進(jìn)行智能組卷，存在陷入局部最優(yōu)、組卷成功幾率較低的問題。雖然許多專家和學(xué)者為了解決排課問題，已經(jīng)提出了很多算法，比如分組優(yōu)化、分支定界、專家系統(tǒng)等。但是，上述算法總是存在以下問題：

一是專家系統(tǒng)可以依據(jù)排課的經(jīng)驗(yàn)知識(shí)，組織排課的規(guī)則，但是排課過程約束條件較多，每個(gè)學(xué)校的實(shí)際情況各不相同，經(jīng)驗(yàn)知識(shí)較難獲取，排課結(jié)果也不好。

二是排課表的優(yōu)劣判定標(biāo)準(zhǔn)較少，針對(duì)一個(gè)問題求解，無法從多個(gè)角度實(shí)施優(yōu)化。

3? 傳統(tǒng)遺傳算法在進(jìn)行智能排課時(shí)遇到的問題

排課問題的約束條件分為軟約束、硬約束兩種類別，學(xué)生、教師、教室等硬件資源是硬約束，這些條件在排課過程中必須滿足，該約束度量一個(gè)排課算法的可行性;軟約束既可以滿足也可以不用滿足，其度量一個(gè)排課算法的優(yōu)劣。

遺傳算法能夠有效的模擬達(dá)爾文的自然淘汰和遺傳變異選擇的生物進(jìn)化過程，通過搜索最優(yōu)的模擬進(jìn)化算法。該算法可以針對(duì)一串描述字符的位串進(jìn)行操作，不同位串在實(shí)際的應(yīng)用環(huán)境中代表不同的問題。遺傳算法可以從若干個(gè)初始的種群開始搜索，根據(jù)當(dāng)前的種群成員，模仿生物的遺傳進(jìn)化過程，選擇基因優(yōu)良的下一代作為進(jìn)化的目標(biāo)。遺傳算法的主要目的是針對(duì)相關(guān)的問題進(jìn)行建模分析，尋求相關(guān)問題的最優(yōu)解。也就是根據(jù)問題的背景和性質(zhì)，構(gòu)建一個(gè)合適的適應(yīng)度函數(shù)，迭代執(zhí)行，然后在求解空間中選擇較優(yōu)的種群進(jìn)行評(píng)估、遺傳變換、變異和選擇等交叉選擇操作，將滿足目標(biāo)函數(shù)的個(gè)體選為最優(yōu)解。

目前，傳統(tǒng)的遺傳算法已經(jīng)在很多領(lǐng)域得到了廣泛的應(yīng)用，比如自動(dòng)組卷過程中、基因序列預(yù)測(cè)過程中、數(shù)據(jù)庫連接優(yōu)化過程中，均得到了良好的效果。但是傳統(tǒng)的遺傳算法在使用過程中，存在以下問題：

第一，傳統(tǒng)遺傳算法在排課應(yīng)用過程中，由于排課軟硬約束條件較多，約束比較復(fù)雜，遺傳算法選擇優(yōu)勢(shì)個(gè)體遺傳到下一代，遺傳算法在排課過程中，非常容易陷入到局部最優(yōu)化，無法求得全局最優(yōu)解。

第二，排課過程中，排課存在硬件約束（教師、教室）和軟件約束（時(shí)間），因此，如果同時(shí)考慮這兩種約束模式，遺傳算法則成為一個(gè)多約束和多目標(biāo)的組合優(yōu)化問題，無法求解。

4? 基于群體策略的遺傳算法在高校排課系統(tǒng)中的應(yīng)用

遺傳算法通過應(yīng)用和改進(jìn)，已經(jīng)出現(xiàn)了許多改進(jìn)后的遺傳算法，比如并行遺傳算法、網(wǎng)格遺傳算法等。為了尋求一個(gè)排課問題的最優(yōu)解，作者通過對(duì)相關(guān)的遺傳算法進(jìn)行對(duì)比研究，將隨機(jī)數(shù)理論其引入到遺傳算法中，通過實(shí)施自然的選擇、變異等發(fā)生機(jī)制，提高每一個(gè)個(gè)體的適應(yīng)度，充分體現(xiàn)物競(jìng)天擇、適者生存的基本思想和原理，并且提出了一種改進(jìn)的遺傳算法——基于群體策略的遺傳算法，該策略能夠促進(jìn)每一代的平均適應(yīng)度逐代提高，直到尋求到最優(yōu)解，可以較好地解決傳統(tǒng)算法尋求最優(yōu)解時(shí)容易產(chǎn)生的收斂速度慢、陷入局部最優(yōu)等問題，盡可能地滿足“實(shí)用、合理、有特色”的需求，形成最優(yōu)化的排課方案。

基于群體策略遺傳算法的基本操作流程包括以下6個(gè)步驟：

第一步：生成初始種群：隨機(jī)生成包含所有解空間的初始種群，種群中的每個(gè)解都使用一個(gè)個(gè)體表示;第二步：計(jì)算適應(yīng)度函數(shù)：根據(jù)目標(biāo)函數(shù)，計(jì)算種群中個(gè)體的適應(yīng)度函數(shù);第三步：執(zhí)行選擇操作：根據(jù)適應(yīng)度函數(shù)值和選擇操作方法，淘汰含有劣勢(shì)基因個(gè)體，選擇優(yōu)勢(shì)個(gè)體，即逐步向最優(yōu)解靠近;第四步：交叉操作：對(duì)種群中的個(gè)體實(shí)施交叉操作，產(chǎn)生新的個(gè)體;第五步：變異操作：對(duì)種群中的個(gè)體實(shí)施變異操作;第六步：判斷是否滿足終止條件或求得最優(yōu)解。如果滿足終止條件或求得最優(yōu)解，即可停止算法;否則，跳轉(zhuǎn)到第二步。

基于群體策略的遺傳算法使用概率策略設(shè)置選擇操作算子，促進(jìn)適應(yīng)度較高的個(gè)體遺傳到下一代，增加種群的平均適應(yīng)度，該策略能夠逐代提高每一代的平均適應(yīng)度，直到尋求到最優(yōu)解，從而解決無法從多個(gè)約束條件實(shí)施優(yōu)化的問題。實(shí)驗(yàn)結(jié)果表明，基于群體策略的改進(jìn)遺傳算法能夠有效地尋求滿足“實(shí)用、合理、有特色”的需求的排課方案，具有較好的效果。

參考文獻(xiàn)

[1] 郭彤.人工智能算法在排課系統(tǒng)中的研究與應(yīng)用[J].天津職業(yè)院校聯(lián)合學(xué)報(bào)，2012，22（2）：14-18.

[2] 崇陽.遺傳算法在高職院校排課系統(tǒng)中的應(yīng)用研究[J].電腦編程技巧與維護(hù)，2016（1）：23-24，30.

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