基于遺傳-蟻群混合算法的排課系統①

孫 弋,胡粔琿

(西安科技大學 通信與信息工程學院,西安 710054)

引言

教務管理是教育活動的重要支撐,隨著高校教育改革的發展,高校人數的增加,但教學資源卻相對有限的情況下,排課工作的難度和復雜程度都有所提高.因此,如何設計一個能滿足多約束條件并且高效的排課系統成為了目前待解決的問題[1].

排課系統的核心是排課,排課算法一個NP完全問題,即算法的計算時間呈指數增長[2].常用的排課算法有: 蟻群算法、遺傳算法、貪心算法、圖論算法等.遺傳算法模擬生物進化過程,具有自適應全局尋優和智能搜索等優點,但是容易收斂得到局部近似最優解,進行大量的無用迭代,難以收斂于最優解[3,4].蟻群算法啟發于螞蟻尋找最優路徑的行為,具有較強的魯棒性,是一種正反饋算法.但當群體規模較大時,搜索初期信息素匱乏,容易產生停滯現象.單算法在解決問題時都會有局限性,花費的時間成本更多,求解的結果不理想[5,6].

為了提高排課的效率和成功率,本文提出一種將遺傳算法與蟻群算法結合使用的方法,首先使用遺傳算法對初始種群進行優化選擇,生成蟻群算法所需的信息素,再通過蟻群算法求得全局精確解.優劣互補,充分發揮兩者的優勢[7].

1 排課問題的分析

排課問題主要涉及教師、教室、課程、班級、上課時間等因素,排課的實質就是要求課程表在安排的時候不能在上述五個因素中發生沖突.可使用五個集合來表示這些因素.

班級集合:C={C1,C2,C3,···,Cn}

課程集合:S={S1,S2,S3,···,Sm}

教師集合:T={T1,T2,T3,···,Tx}

教室集合:R={R1,R2,R3,···,Rt},教室有多種類型,例如實驗室、多媒體教室、機房等,每個教室容納的人數也不相同.

時間段集合:P={P1,P2,P3,···,Pi},Pi表示時間段,例如P1為 周一的1-2節課,P2為3-4節課.時間和教室的笛卡兒積為:N=R*P={(r1,p1),(r2,p2),…,(rn,pn)},N中的元素是教室-時間對.排課問題由此轉化為一門課尋找一個合適的教室時間對.

1.1 硬約束條件

硬約束是在排課過程中必須要遵守的約束條件,如果排課過程中無法遵守硬約束條件,則會導致日常的教學計劃無法順利的進行.例如:

(1)同一個教師在同一時間段內只能夠上一門課,并且教室的性質要和課程要求相吻合;

(2)同一個班級在同一時間段內只能夠接受一門課;

(3)一門課程安排的教室座位數量要大于或等于本門課程上課的人數.

1.2 軟約束條件

軟約束條件需要將人體生物規律與排課進行結合.滿足軟約束條件越多,課表越能讓教師與學生滿意.例如:

(1)盡量將專業課或者難度較大的課程安排在學生思維活躍的時間段;

(2)體育課應安排在下午或者上午的第二大節,因為體育課后人體疲憊不適宜安排專業性過強的課程.

2 算法概述

2.1 遺傳算法

遺傳算法是通過模擬生物界遺傳選擇和自然淘汰的生物進化過程的計算模型,借鑒了生物界適者生存、優勝劣汰的進化規律,從而演化的隨機化搜索方法.遺傳算法從一個種群開始,在這個種群中可能存在問題的潛在解,每個種群是由經過編碼的N個個體組成,每個個體就是帶有一定特征的染色體實體.在每一代中,選擇適應度較大的個體進行培育,然后借助遺傳學中的遺傳算子進行多次組合交叉、變異等操作,產生出代表新的解集的種群.這樣經過了多次演化之后得到的種群就可以看作問題的近似最優解.

遺傳算法的流程如下:

(1)隨機產生一定數量的初始種群,數量由業務需求定義.

(2)對全部個體進行適應度的評估,如果某個個體的適應度已經滿足最優化的要求,則輸出此個體,并結束計算.否則轉向第(3)步.

(3)從所有個體中取出適應度較強的個體成為再生個體.

(4)依據交叉概率,變異概率生成新的個體.

(5)由上述兩步交叉和變異產生新一代種群,然后返回第(2)步.

2.2 蟻群算法

蟻群算法是一個尋找最優路徑的方法.螞蟻在尋找食物的過程中,通過釋放信息素留下信息,后面的螞蟻就會根據路上的信息素來選擇路徑,信息素的濃度與行走的路程成反比,走的路途越長,信息素濃度越低,則越不容易找到,路途越短,信息素濃度含量越高.隨著時間的推移最優路上的信息素濃度越大,最終蟻群會找到一個最優路徑.

2.3 遺傳-蟻群混合算法

遺傳,蟻群算法是兩大仿生算法,都有各自的優勢和不足.遺傳算法的優勢在于在大范圍內具有快速全局搜索的能力,但在處理反饋信息時利用率過低,容易過早的收斂,或求解到一定范圍時會做大量的無用迭代,從而會降低求解過程中的效率.蟻群算法采用正反饋機制,具有較強的魯棒性,使搜索過程不斷收斂,有更好的全局優化能力.但是在搜索初期信息素分布較少時,求解速率較慢.

而排課問題的實質就是一個NP完全問題,影響排課因素的細微變動,尤其是信息量一點點的增加,都會給排課帶來“組合爆炸”災難,當排課規模較大時,單算法在排課問題中就表現出局限性,會出現排課時間較長、排出的課表無法令教師學生滿意等現象.因此,本文將兩算法結合應用于排課問題中,首先利用遺傳算法在大范圍內快速的生成信息素分布,再利用蟻群算法求出全局最優解,優勢互補,可以減少求解的時間,提高精確率.

3 遺傳-蟻群混合算法解決排課問題

3.1 遺傳算法在排課問題中的應用

3.1.1 構造基因編碼和染色體

實施遺傳算法的第一步就是對需要解決問題的參數進行基因編碼,從而進行相關的遺傳操作.本文采用二進制對編碼數據進行設計.如表1所示.

表1 編碼方式

3.1.2 適應度函數

在遺傳算法的進化過程中,其根據適應度函數來確定進化方向.適應度是對課表優劣的一種體現.適應度越大則證明課表的效果越優秀.因此適應度函數直接決定著排課方案的尋優速率和能否找到最優解.

所以這就需要制定一個合適的適應度函數(期望).在本文中,課表的期望值可以分為以下三種: 課程離散程度期望,節次優化度期望和特殊課程期望.

(1)課程離散程度期望

同一門課程安排的時間應該分布均勻,每周安排的時間不能分散也不能太集中.本文將每天的教學時間段分為4個,每周一共20個時間段.用編號相同課程的時差來表示離散程度的大小如表2所示.

表2 課程離散程度期望

每一個課程時差對應一個期望,期望函數公式為:

(2)節次優化度期望值

人體生物鐘規律應與教學內容相匹配,邏輯思維活躍的時間段一般在早晨,而下午更容易疲倦所以學習效率較低.根據人體生物鐘規律節次的不同的課程期望值也不同,如表3所示.

表3 節次優化度期望值

對于難度比較大的課程就可以安排在期望值高的節次上,對于節次期望值函數的公式為:

(3)特殊課程的期望值

特殊課程包含體育課與自習課,此類課程最好安排在下午的第二節.當體育課結束后,人體處于疲倦狀態,不適于將專業性過強的課程安排在體育課后.如表4對特殊課程給出了不同的期望.

表4 特殊課程的期望值

對體育課排課就依據上表的期望值為:

應將課表中沒有課程的時間段安排給自習課.則計算特殊課程期望值的公式為:

根據以上分析可得出適應度函數F,如下公式為:

式中,K1,K2,K3為調控期望值對總期望影響程度的參數.

3.1.3 種群操作

當形成初始種群,并設計好適應度函數后,下一步就是要進行遺傳操作.遺傳算法包括三個基本操作: 選擇、交叉和變異.

(1)選擇操作

選擇操作就是依照適應度的值保留優良的個體,適應度越高證明越近似于最優解.本文中保留優良個體的依據是期望值方法,選擇期望值高的個體進行交叉變異操作.

(2)交叉操作

交叉操作就是把兩個個體的部分結構進行替換重組從而產生新的個體.根據選擇操作的結果,選擇兩條染色體作為父代,進行交叉操作.為了防止染色體的結構發生更改,本文的交叉操作只針對教室和上課時間,這樣教師和班級都沒有發生改變,維持了染色體原本的結構.同時設定交叉概率為PJ,若PJ大于隨機值r(0＜r＜1),就進行交叉操作.

(3)變異操作

變異操作能夠隨機的對個體的局部進行搜索,提高種群的多樣化.本文中的變異操作

就是對染色體編碼中教室和時間段的局部編碼進行修改,可以提高染色體的適應度.同時設定變異概率為PG,若PG大于隨機值r(0＜r＜1),就進行變異操作.

3.2 蟻群算法在排課問題中的應用

蟻群算法最初用于解決TSP(Traveling Salesman Problem),TSP具有廣泛的代表意義,許多問題都可類似的抽象為TSP問題的求解.

因此以TSP來描述蟻群算法的模型: 一只螞蟻要去n個有食物的地區,它先隨機選擇一個地方作為起點,然后在逐個到達所有地區,留下信息素,最后再返回起點,每個地區只能到達一次,螞蟻要怎么樣選擇順序才能使行程最短.下面建立蟻群算法的數學模型:

m為蟻群中的螞蟻數量;n為問題的規模大小(有食物地方的個數);bi(t)為t時刻位于i地區的螞蟻數量,故螞蟻數量為:

其中,τij(t)為t時刻路徑(i,j)上的信息素;μij(t)為螞蟻從i到j地區的期望程度;pkij(t)為t時刻螞蟻k從i轉移到j的概率.

螞蟻k是根據τij(t)的結果來決定該往哪個方向前進,一般會選擇τij(t)值高的路徑,則螞蟻k在t時刻由i地轉移到j的概率為:其中,α為信息啟發因子,表示在螞蟻選擇行走路徑時信息量的影響;μ為期望啟發式因子,表示啟發信息對螞蟻選擇路徑時產生的影響程度.

在每只螞蟻訪問完所有的地區以后,每條路上的信息素濃度會發生變化,因此需要對信息素進行更新.

其中,ρ是信息素揮發系數(0＜ρ＜1),1-ρ表示路徑殘留的信息素量;Δ τij(t)為從i到j地區路上增加的信息素量;Δ τkij(t)為螞蟻k在i到j地區路上留下的信息素量;Q為表示信息素濃度;Lk為螞蟻k需要行走的路徑長度.

3.2.1 蟻群算法的二分圖模型

當遇到需要用圖結構解決的問題時可以使用蟻群算法.在本文中,用蟻群算法解決排課問題,首先需將排課問題用圖結構G來描述:

上式中,N是圖的頂點;S是邊的集合;C是邊集有關的權值集合.

排課問題涉及五個要素,在蟻群算法中這五個要素的關系可轉化為“課程,教師,班級”關系與“時間,教師”關系,排課問題就是解決這兩個關系所構成的二分圖的最大匹配問題.

(1)二分圖的頂點集定義

在本文將“課程,教師,班級”的關系定義為RLSC,RLSC=L×S×C,RLSC的元素組成的集合為GLSC,稱其為二分圖左側的頂點集.“時間,教室”的的關系為RTR,RTR=T×R,RTR的 元素組成的集合為GTR,為二分圖右側的頂點集.

(2)二分圖的邊集定義

在排課中對教室的安排要滿足兩個要求: 一是安排人數不能大于教室座位數量,二是教室類型滿足課程要求.因此,GLSC與GTR之間只有滿足上述兩個基本要求的節點才能進行連接.二分圖的邊集就是GLSC中的節點與GTR中相匹配節點的連線.

(3)二分圖中邊的權值

每條邊上的權值根據具體課程時間的期望度來構造.例如,較難的專業課嵌入式教師對課程的期望度是上午的第二節課,那么GLSC中所有嵌入式課程與GTR中時間段為滿足上午第二節的所有節點連接的邊權值要盡可能的小.通過設置權值,才能更加合理的排出質量高的課表.

3.2.2 二分圖模型

根據上節構造好的二分圖模型,螞蟻都是從左側GLSC的頂點集出發,根據轉移概率的值和邊集在右側GTR尋找匹配的節點.然后再返回至GLSC進行下一次的搜索工作,如此反復直到螞蟻為GLSC的頂點集全部安排好上課地點和時間后,一次循環結束.

圖1 二分圖模型

圖1展示了螞蟻一次循環的過程,螞蟻從A1出發,則螞蟻此次行走的路徑為:

其中,B1是第一次匹配的終點,A2是第二次匹配的起點,B1和A2可以看成是一個邏輯節點.同理,B4和A3在此次周游中也可以看成是相同的邏輯節點.

3.3 遺傳-蟻群混合算法在排課問題中的應用

本文將遺傳與蟻群算法進行混合,首先利用遺傳算法生成信息素分布,在利用蟻群算法求出問題的精確解.在遺傳算法生成信息素時,為了防止其在收斂后進行無用的迭代,要設置相應的終止條件.在運算工程中,當連續兩次運算結果出現的差值小于0.01,或迭代100次,滿足其中一個條件時可停止運算并將取得的最優解作為蟻群算法的初始解.蟻群算法在進行100次迭代之后,選擇路徑最短的解即可作為最優解.遺傳-蟻群混合算法對排課問題解決步驟如圖2所示.

3.4 實驗結果及分析

為了驗證遺傳-蟻群混合算法在排課系統中的應用,選取一個學院對排課系統進行測試,該學院的專業數量為6,班級數量為21,約有800名學生,55名教師,22間教室,其中有16名教師對排課有特殊要求,排課單元為202.

圖2 遺傳-蟻群混合算法流程圖

為了驗證遺傳-排課算法在排課系如中的實際使用效果,在排課單元為100,400,800的情況下,對遺傳-蟻群混合算法、遺傳算法、蟻群算法三種算法的排課效果、運算時間及適應度進行了比較.三種算法各測試10組數據后取得平均值.

(1)實驗參數設置

遺傳算法的參數設置如下: M=40,PJ=0.4,PG=0.02;蟻群算法設置的參數如下:m=6,α =1,β =4,ρ=0.25 ,Q=8 ,τmax=800 ,τmin=0.01 ,μij=1/cij,gen=100.

(2)排課效果的比較

通過以下四個指標來衡量排課課表的質量,如表5所示.1為違反硬約束的次數;2為一周有兩次課程且間隔少于一天的次數;3為難度較大的課程安排在時間段 不好的次數;4為教師的特殊要求未滿足的次數.

表5 排課效果比較

如表5可以看出,遺傳算法在軟約束的沖突方面表現的最不理想,基于遺傳-蟻群混合算法排出的課程表,在軟約束方面的沖突次數最令人滿意,課程表的可行性及質量都要優于單算法排出的課程表.

(3)實驗結果分析

三種算法的平均運算時間如表5所示,平均適應度結果如表6所示.

表6 運算時間比較

表7 適應度比較

由表6可得,每種算法隨著排課單元的增加,所需要的排課時間隨之增加.在排課單元相同的情況下,遺傳算法需要的時間最短,而蟻群算法需要的時間最長.

由表7可得,三種算法的適應度與排課的單元成正比.當排課單元相同時,遺傳-蟻群混合算法的適應度最高.也就證明混合算法排出的課表最優.

由此可見,在相同的條件下,遺傳-蟻群混合算法排課消耗的時間比遺傳算法高一些,但適應度卻遠遠高于另外兩個算法.說明混合算法解決排課問題具有良好的時間性能和優化性能.

在選擇最優課表時,可以將適應度最大的三個課表取出,根據定義排課質量的四個指標,滿足軟約束條件越多的課表則可作為最終使用的課表

4 結論

目前解決排課問題可使用的單算法很多,但混合算法卻相對較少.本文提出了一種遺傳-蟻群混合的排課算法,將兩種算法的優勢進行了結合.在經過測試后混合算法在運算時間上介于遺傳與蟻群算法中間,但適應度高于單算法.混合算法不僅解決了單算法的局限性問題,還在排課效率上有所提高.