李印坤?任宣宇

摘要：排課是高職院校的日常工作，排課管理是否合理，直接影響了高職院校的辦學(xué)質(zhì)量?；诖耍瑢⑦z傳蟻群混合算法作為研究工具，針對(duì)高職院校排課管理系統(tǒng)進(jìn)行優(yōu)化研究。將混合遺傳螞蟻算法應(yīng)用于高職院校排課系統(tǒng)中，利用交叉函數(shù)設(shè)計(jì)和構(gòu)建了高校自動(dòng)排課系統(tǒng)。選擇某高職院校的課程調(diào)度系統(tǒng)進(jìn)行研究，利用遺傳螞蟻混合算法對(duì)原系統(tǒng)A進(jìn)行改進(jìn)，形成一個(gè)新的系統(tǒng)B，比較兩個(gè)系統(tǒng)的運(yùn)行時(shí)間和系統(tǒng)適應(yīng)性。實(shí)驗(yàn)結(jié)果表明，系統(tǒng)B的適應(yīng)度優(yōu)于系統(tǒng)A，遺傳蟻群混合算法可以提高課程的合理性。

關(guān)鍵詞：遺傳蟻群混合算法；排課系統(tǒng)；高職院校

一、前言

近年來(lái)，隨著我國(guó)高職院校規(guī)模迅速擴(kuò)大，許多高職院校都面臨著課堂資源和教師資源不足的問題，組織課程的方式越來(lái)越難以滿足不斷變化的需求。排課問題一直困擾著很多高職院校，特別是班級(jí)較多而教學(xué)資源緊張的學(xué)校，每次排課都是困難重重，在實(shí)際工作中，許多學(xué)校只能無(wú)奈地選擇手工排課。實(shí)現(xiàn)全自動(dòng)化的排課系統(tǒng)是眾多高職院校的共同期待。

排課問題是NP中的時(shí)間表問題，也就是在資源條件有限的情況下，將事件安排到適合的時(shí)間段。問題的核心在于為學(xué)院計(jì)劃制定合理的課程安排，包括分配教室、時(shí)間和教師資源，并確定適當(dāng)?shù)慕虒W(xué)時(shí)段和場(chǎng)地，以便有序地進(jìn)行教學(xué)工作，進(jìn)而設(shè)計(jì)一個(gè)滿足多約束條件且高效運(yùn)行的智能排課系統(tǒng)[1]。

國(guó)外學(xué)者解決排課問題大多采用智能算法，比如IA Ashari采用結(jié)合遺傳算法和蟻群算法，以優(yōu)化解決排課問題。經(jīng)過實(shí)驗(yàn)和大量測(cè)試，證明遺傳算法在此問題中表現(xiàn)良好[2]。G. Kendall及其團(tuán)隊(duì)將禁忌搜索算法與模擬退火算法相結(jié)合，提高可行解質(zhì)量，并成功求解排課問題[3]。Saptarini等學(xué)者應(yīng)用遺傳算法有效地避免了違反硬約束條件，在最大限度上滿足軟約束條件[4]。C.Akka等研究人員將遺傳算法和模擬退火算法相結(jié)合，適應(yīng)排課規(guī)模的變化，并應(yīng)用于排課系統(tǒng)中[5]。

但國(guó)外的排課系統(tǒng)普遍不適用于我國(guó)高校。袁俊毅設(shè)計(jì)了一種基于遺傳算法的排課系統(tǒng)，成功應(yīng)用于高職院校，顯著提升了排課效率[6]。羅義強(qiáng)等學(xué)者采用改進(jìn)的粒子群算法優(yōu)化高校排課問題，通過該算法得到潛在解并驗(yàn)證其有效性。馮月華則運(yùn)用動(dòng)態(tài)調(diào)整信息素策略改進(jìn)蟻群算法，并將其應(yīng)用于排課系統(tǒng)中，成功縮短了排課時(shí)間。

為了提高高職院校的排課效率，本文提出一種將遺傳算法與蟻群算法混合使用的方法，通過遺傳算法對(duì)初始種群進(jìn)行優(yōu)化選擇，進(jìn)而生成蟻群算法所需的信息素，再通過蟻群算法求得全局最優(yōu)解。本文選擇某高職院校的一個(gè)教務(wù)管理系統(tǒng)進(jìn)行實(shí)驗(yàn)研究，將原有的系統(tǒng)與運(yùn)用混合算法改進(jìn)后的系統(tǒng)進(jìn)行比較，通過比較遺傳蟻群混合算法的運(yùn)算時(shí)間和適用性，發(fā)現(xiàn)該算法可以更好地提高高職院校排課的合理性。

二、高職院校的排課特點(diǎn)

根據(jù)教育分類的觀點(diǎn)，高職教育不屬于普通高等教育，而是技術(shù)與職業(yè)教育中的高等教育。2022年修訂的新《中華人民共和國(guó)職業(yè)教育法》第三條闡明“職業(yè)教育是與普通教育具有同等重要地位的教育類型”。特殊的教育類型決定高職院校的排課工作也具有挑戰(zhàn)性，既有普通高等學(xué)校排課的復(fù)雜性，又有自身的特殊性。

1.高職院校的特點(diǎn)之一是教學(xué)資源比較緊張，除了一般的教室、機(jī)房、實(shí)訓(xùn)室、體育場(chǎng)地，教師資源緊張也是高職院校在排課方面遇到困難的共同點(diǎn)，很多高職院校的教師周課時(shí)為18節(jié)至20節(jié)。

2.一般全院的課程表就是公共基礎(chǔ)課的安排，專業(yè)課程由各系安排。排課中最大的挑戰(zhàn)在于公共選修課。不同專業(yè)或班級(jí)的學(xué)生可能會(huì)選擇相同的課程，而各門選修課人數(shù)也參差不齊，因此安排教室變得十分困難。

3.受到教師資源限制，很多高職院校采用兩個(gè)及兩個(gè)以上的班級(jí)合堂上課，需要使用合堂教室或階梯教室，而合堂教室或階梯教室需求量較大又會(huì)帶來(lái)諸多相關(guān)的問題。

4.部分高職院校采取單雙周上課模式，或者分階段安排實(shí)訓(xùn)課，課程表的分階段變化在一定程度上增加了排課的復(fù)雜性。

三、高職院校排課問題分析

基于高職院校的排課特點(diǎn)，排課問題主要涉及課程、班級(jí)、教師、教室、上課時(shí)間等因素，排課的實(shí)質(zhì)是課程表中不能在上面5個(gè)因素之間發(fā)生沖突。為描述問題方面，下面使用5個(gè)集合表示這些因素。

（一）硬約束條件

在高職院校排課過程中，硬約束條件是必須遵守的限制條件。如果硬約束條件無(wú)法滿足，則無(wú)法得到最優(yōu)解，進(jìn)而導(dǎo)致教學(xué)計(jì)劃無(wú)法實(shí)施。根據(jù)高職院校的排課特點(diǎn)，具體硬約束條件有以下幾點(diǎn)：

（二）軟約束條件

軟約束條件是指那些是否滿足都不影響教學(xué)計(jì)劃實(shí)施，但影響師生體驗(yàn)的約束條件。為了提高師生對(duì)課表的滿意度，在排課的同時(shí)要充分考慮人體生物規(guī)律。在排課的過程中，滿足軟約束條件越多，教學(xué)計(jì)劃實(shí)施起來(lái)越順利，課表也越能讓師生滿意。

例如：①盡量將難度較大的課程或?qū)λ季S訓(xùn)練要求較高的課程安排在上午第1、2節(jié)課等節(jié)次，在這些時(shí)間段學(xué)生思維相對(duì)更活躍；②體育與健康課程盡量安排在上午的第3、4節(jié)和下午的第5、6節(jié)，充分考慮到體育鍛煉后因身體疲憊，不適宜立刻進(jìn)入專業(yè)性過強(qiáng)的課程。

四、遺傳蟻群混合算法

（一）遺傳蟻群混合算法的基本思想

通過對(duì)參考文獻(xiàn)的研究發(fā)現(xiàn)，在解決高校排課問題時(shí)，遺傳算法和蟻群算法各自具有一定的優(yōu)勢(shì)，但也存在相應(yīng)的缺陷。例如，在尋求最優(yōu)解的初始階段，遺傳算法的搜索效率較高，適用于大范圍的搜索。但在尋求最優(yōu)解的后半階段，遺傳算法沒有充分利用反饋信息，這一不足之處就會(huì)顯現(xiàn)出來(lái)，并消耗大量的時(shí)間在無(wú)效的迭代上。突出的并行計(jì)算能力和整體優(yōu)化能力是蟻群算法的最大優(yōu)勢(shì)，但不足之處是，在算法初期，信息素的匱乏會(huì)導(dǎo)致尋求最優(yōu)解的速度過慢，因而該算法的運(yùn)行時(shí)間比較長(zhǎng)。

針對(duì)高職院校的排課特點(diǎn)，本文在前人研究的基礎(chǔ)上進(jìn)一步將遺傳算法和蟻群算法結(jié)合起來(lái)使用，可以更好地發(fā)揮它們各自的優(yōu)勢(shì)。具體而言，在算法運(yùn)行過程中，可以先充分利用遺傳算法的優(yōu)點(diǎn)，以期達(dá)到更高的搜索效率。即在初始階段具有高效搜索的特點(diǎn)，進(jìn)而能夠生成必要的信息素，以供接下來(lái)蟻群算法的使用，然后利用蟻群算法求得全局最優(yōu)解，充分利用了蟻群算法的整體優(yōu)化能力和突出的并行計(jì)算的能力。

（二）遺傳蟻群混合算法的執(zhí)行步驟

遺傳蟻群混合算法的執(zhí)行步驟如下：

Step 1 初始化遺傳算法的參數(shù)，生成初始種群，并將初始迭代次數(shù)設(shè)為0；

Step 2 計(jì)算所有個(gè)體的適應(yīng)度函數(shù)；

Step 3 對(duì)個(gè)體進(jìn)行基本遺傳操作，迭代次數(shù)加1；

Step 4判斷是否滿足終止條件，如果滿足，繼續(xù)執(zhí)行，否則跳至Step 2；

Step 5 利用遺傳算法尋求近似最優(yōu)解，并將其轉(zhuǎn)化為初始信息素，以供蟻群算法使用，然后構(gòu)建排課問題的二分圖模型；

Step 6 在蟻群算法運(yùn)行前，初始化相關(guān)參數(shù)，并將迭代次數(shù)設(shè)置為gen=0；

Step 7 將m只螞蟻放GLSC（在二分圖左側(cè)的頂點(diǎn)集）中，為每只螞蟻建立禁忌表tabuk和允許RTR選擇的表allowdk；

Step 8 螞蟻k根據(jù)排課約束條件和轉(zhuǎn)移概率選取轉(zhuǎn)移路徑；

Step 9 對(duì)m條路徑進(jìn)行記錄，并完成迭代；

Step 10 計(jì)算m條路徑的長(zhǎng)度，并對(duì)當(dāng)前最優(yōu)路徑值進(jìn)行記錄；

Step 11 對(duì)最優(yōu)路徑上邊的信息素量進(jìn)行更新，揮發(fā)其余邊的信息素；

Step 12 判斷是否符合終止約束條件，若符合，則終止運(yùn)算，求出當(dāng)前最優(yōu)路徑的數(shù)值，否則gen=gen+1，并返回Step 7繼續(xù)新的迭代。

遺傳蟻群混合算法求解排課問題的流程圖如圖1所示。

五、實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證混合遺傳螞蟻算法在編程系統(tǒng)中的應(yīng)用，選擇某高職院校作為調(diào)度系統(tǒng)的測(cè)試對(duì)象。該學(xué)院有15個(gè)專業(yè)、39個(gè)班級(jí)、70名教師、57間教室，其中有30名教師對(duì)課程的安排設(shè)置了特殊的需求。本實(shí)驗(yàn)調(diào)度系統(tǒng)采用較為常用的蟻群算法，在本文研究的基礎(chǔ)上，刪除原算法，代之以遺傳螞蟻混合算法。利用上述實(shí)驗(yàn)數(shù)據(jù)，我們分別在蟻群算法和遺傳蟻群混合算法中進(jìn)行多次實(shí)驗(yàn)。我們將原有的蟻群算法系統(tǒng)簡(jiǎn)稱為A系統(tǒng)，對(duì)于遺傳蟻群混合算法則稱之為B系統(tǒng)，并對(duì)兩種算法解決排課問題的合理性、效率等方面進(jìn)行驗(yàn)證。

（一）算法運(yùn)算時(shí)間比較

當(dāng)排課單元為100、400、800時(shí)，對(duì)A系統(tǒng)和B系統(tǒng)的運(yùn)行時(shí)間以及適應(yīng)度進(jìn)行比較，并進(jìn)行詳細(xì)分析。算法運(yùn)算時(shí)間比較如表1所示。

表1中的數(shù)據(jù)顯示系統(tǒng)A比系統(tǒng)B所花費(fèi)的操作時(shí)間更少。當(dāng)調(diào)度單元為100時(shí)，系統(tǒng)A為56，系統(tǒng)B為36；當(dāng)調(diào)度單元為400時(shí)，系統(tǒng)A為192，系統(tǒng)B為174；當(dāng)調(diào)度單元為800時(shí)，系統(tǒng)A為578，系統(tǒng)B為541。

算法運(yùn)算理想的時(shí)間長(zhǎng)度是衡量算法質(zhì)量的一個(gè)重要關(guān)鍵績(jī)效指標(biāo)。運(yùn)算時(shí)間越短，可能的損失就越小，帶來(lái)的機(jī)會(huì)就越多。通過表1可以發(fā)現(xiàn)，隨著排課單元數(shù)量的增加，兩種算法的運(yùn)行時(shí)間也會(huì)隨之增加。在排課單元數(shù)量相同的情況下，蟻群算法所需時(shí)間較長(zhǎng)，而遺傳蟻群混合算法則需要較短的時(shí)間。

（二）算法適應(yīng)度比較

在遺傳算法中，適應(yīng)度是描述遺傳算法個(gè)體性能和驅(qū)動(dòng)力的主要指標(biāo)。從生物學(xué)的角度來(lái)看，正常的條件相當(dāng)于“適者生存”的生物可持續(xù)性競(jìng)爭(zhēng)，這在遺傳過程中很重要。建立優(yōu)化問題的目標(biāo)操作與個(gè)體適應(yīng)性之間的映射關(guān)系，有助于實(shí)現(xiàn)優(yōu)化問題在群體發(fā)展中的客觀作用。因此，我們比較兩個(gè)系統(tǒng)的適應(yīng)性，結(jié)果如表2所示。

從表2的數(shù)據(jù)可以看出，系統(tǒng)B的適應(yīng)性優(yōu)于系統(tǒng)A。當(dāng)調(diào)度單元為100時(shí)，系統(tǒng)A為191，系統(tǒng)B為213。當(dāng)調(diào)度單元為400時(shí)，系統(tǒng)B比系統(tǒng)A高31。當(dāng)調(diào)度單元為800時(shí)，系統(tǒng)B比系統(tǒng)A高69?？梢钥闯?，隨著排課單元的增加，兩種算法的適應(yīng)度值也在增加。隨著排課單元數(shù)量的增加，兩種算法的適應(yīng)度值都會(huì)趨于穩(wěn)定。因此可以得出結(jié)論：在相同數(shù)量的排課單元下，遺傳蟻群混合算法的適應(yīng)度要優(yōu)于單一的蟻群算法。

六、結(jié)語(yǔ)

綜上所述，遺傳蟻群混合算法的排課時(shí)間比蟻群算法短，而且其適應(yīng)度值遠(yuǎn)大于蟻群算法，因此，運(yùn)用遺傳蟻群混合算法解決排課問題的可行性已經(jīng)得到驗(yàn)證。將蟻群算法與遺傳算法相結(jié)合，首先采用蟻群算法隨機(jī)搜索，具有良好的全局收斂性，然后充分利用并行性，對(duì)前向反應(yīng)機(jī)制和有效性進(jìn)行了高層次的分析，建立了一種高層次分析的有效遺傳算法。采用遺傳蟻群混合算法可以有效提高算法的收斂速度，縮小搜索范圍。實(shí)驗(yàn)結(jié)果表明，遺傳蟻群混合算法顯著提高了高職院校課程設(shè)計(jì)系統(tǒng)的效率和合理性。該算法生成的課程規(guī)劃方案在每門課程中均勻分布，基本滿足高職院校的要求。

參考文獻(xiàn)

[1]孫弋，胡粔琿.基于遺傳——蟻群混合算法的排課系統(tǒng)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2019，28（2）：81-86.

[2]Ashari IA，Muslim MA，Alamsyah A.Comparison Performance of Genetic Algorithm and Ant Colony Optimization in Course Scheduling Optimizing[J].Scientific Journal of Informatics，2016，3（2）：51-60.

[3]Goh SL，Kendall G，Sabar NR.Improved local search approaches to solve the post Enrolment course timetabling problem[J].European Journal of Operational Research，2017，261（1）：17-29.

[4]Saptarini NGAPH，Suasnawa IW，Ciptayani PI.Senior high school course scheduling using genetic algorithm[C].2018.

[5]Akkan C，Gulcu A.A bi-criteria hybrid Genetic Algorithm with robustness objective for the course timetabling problem[J].Computers & Operations Research，2018，90：22-32.

[6]袁俊毅.基于遺傳算法的高校教務(wù)排課系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].長(zhǎng)沙：湖南大學(xué)，2017.

作者單位：煙臺(tái)文化旅游職業(yè)學(xué)院