基于遺傳-蟻群混合算法的排課系統(tǒng)①

孫 弋,胡粔琿

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

引言

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

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

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

1 排課問題的分析

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

班級(jí)集合:C={C1,C2,C3,···,Cn}

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

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

教室集合:R={R1,R2,R3,···,Rt},教室有多種類型,例如實(shí)驗(yàn)室、多媒體教室、機(jī)房等,每個(gè)教室容納的人數(shù)也不相同.

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

1.1 硬約束條件

硬約束是在排課過程中必須要遵守的約束條件,如果排課過程中無法遵守硬約束條件,則會(huì)導(dǎo)致日常的教學(xué)計(jì)劃無法順利的進(jìn)行.例如:

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

(2)同一個(gè)班級(jí)在同一時(shí)間段內(nèi)只能夠接受一門課;

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

1.2 軟約束條件

軟約束條件需要將人體生物規(guī)律與排課進(jìn)行結(jié)合.滿足軟約束條件越多,課表越能讓教師與學(xué)生滿意.例如:

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

(2)體育課應(yīng)安排在下午或者上午的第二大節(jié),因?yàn)轶w育課后人體疲憊不適宜安排專業(yè)性過強(qiáng)的課程.

2 算法概述

2.1 遺傳算法

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

遺傳算法的流程如下:

(1)隨機(jī)產(chǎn)生一定數(shù)量的初始種群,數(shù)量由業(yè)務(wù)需求定義.

(2)對(duì)全部個(gè)體進(jìn)行適應(yīng)度的評(píng)估,如果某個(gè)個(gè)體的適應(yīng)度已經(jīng)滿足最優(yōu)化的要求,則輸出此個(gè)體,并結(jié)束計(jì)算.否則轉(zhuǎn)向第(3)步.

(3)從所有個(gè)體中取出適應(yīng)度較強(qiáng)的個(gè)體成為再生個(gè)體.

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

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

2.2 蟻群算法

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

2.3 遺傳-蟻群混合算法

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

而排課問題的實(shí)質(zhì)就是一個(gè)NP完全問題,影響排課因素的細(xì)微變動(dòng),尤其是信息量一點(diǎn)點(diǎn)的增加,都會(huì)給排課帶來“組合爆炸”災(zāi)難,當(dāng)排課規(guī)模較大時(shí),單算法在排課問題中就表現(xiàn)出局限性,會(huì)出現(xiàn)排課時(shí)間較長、排出的課表無法令教師學(xué)生滿意等現(xiàn)象.因此,本文將兩算法結(jié)合應(yīng)用于排課問題中,首先利用遺傳算法在大范圍內(nèi)快速的生成信息素分布,再利用蟻群算法求出全局最優(yōu)解,優(yōu)勢互補(bǔ),可以減少求解的時(shí)間,提高精確率.

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

3.1 遺傳算法在排課問題中的應(yīng)用

3.1.1 構(gòu)造基因編碼和染色體

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

表1 編碼方式

3.1.2 適應(yīng)度函數(shù)

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

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

(1)課程離散程度期望

同一門課程安排的時(shí)間應(yīng)該分布均勻,每周安排的時(shí)間不能分散也不能太集中.本文將每天的教學(xué)時(shí)間段分為4個(gè),每周一共20個(gè)時(shí)間段.用編號(hào)相同課程的時(shí)差來表示離散程度的大小如表2所示.

表2 課程離散程度期望

每一個(gè)課程時(shí)差對(duì)應(yīng)一個(gè)期望,期望函數(shù)公式為:

(2)節(jié)次優(yōu)化度期望值

人體生物鐘規(guī)律應(yīng)與教學(xué)內(nèi)容相匹配,邏輯思維活躍的時(shí)間段一般在早晨,而下午更容易疲倦所以學(xué)習(xí)效率較低.根據(jù)人體生物鐘規(guī)律節(jié)次的不同的課程期望值也不同,如表3所示.

表3 節(jié)次優(yōu)化度期望值

對(duì)于難度比較大的課程就可以安排在期望值高的節(jié)次上,對(duì)于節(jié)次期望值函數(shù)的公式為:

(3)特殊課程的期望值

特殊課程包含體育課與自習(xí)課,此類課程最好安排在下午的第二節(jié).當(dāng)體育課結(jié)束后,人體處于疲倦狀態(tài),不適于將專業(yè)性過強(qiáng)的課程安排在體育課后.如表4對(duì)特殊課程給出了不同的期望.

表4 特殊課程的期望值

對(duì)體育課排課就依據(jù)上表的期望值為:

應(yīng)將課表中沒有課程的時(shí)間段安排給自習(xí)課.則計(jì)算特殊課程期望值的公式為:

根據(jù)以上分析可得出適應(yīng)度函數(shù)F,如下公式為:

式中,K1,K2,K3為調(diào)控期望值對(duì)總期望影響程度的參數(shù).

3.1.3 種群操作

當(dāng)形成初始種群,并設(shè)計(jì)好適應(yīng)度函數(shù)后,下一步就是要進(jìn)行遺傳操作.遺傳算法包括三個(gè)基本操作: 選擇、交叉和變異.

(1)選擇操作

選擇操作就是依照適應(yīng)度的值保留優(yōu)良的個(gè)體,適應(yīng)度越高證明越近似于最優(yōu)解.本文中保留優(yōu)良個(gè)體的依據(jù)是期望值方法,選擇期望值高的個(gè)體進(jìn)行交叉變異操作.

(2)交叉操作

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

(3)變異操作

變異操作能夠隨機(jī)的對(duì)個(gè)體的局部進(jìn)行搜索,提高種群的多樣化.本文中的變異操作

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

3.2 蟻群算法在排課問題中的應(yīng)用

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

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

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

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

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

在每只螞蟻訪問完所有的地區(qū)以后,每條路上的信息素濃度會(huì)發(fā)生變化,因此需要對(duì)信息素進(jìn)行更新.

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

3.2.1 蟻群算法的二分圖模型

當(dāng)遇到需要用圖結(jié)構(gòu)解決的問題時(shí)可以使用蟻群算法.在本文中,用蟻群算法解決排課問題,首先需將排課問題用圖結(jié)構(gòu)G來描述:

上式中,N是圖的頂點(diǎn);S是邊的集合;C是邊集有關(guān)的權(quán)值集合.

排課問題涉及五個(gè)要素,在蟻群算法中這五個(gè)要素的關(guān)系可轉(zhuǎn)化為“課程,教師,班級(jí)”關(guān)系與“時(shí)間,教師”關(guān)系,排課問題就是解決這兩個(gè)關(guān)系所構(gòu)成的二分圖的最大匹配問題.

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

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

(2)二分圖的邊集定義

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

(3)二分圖中邊的權(quán)值

每條邊上的權(quán)值根據(jù)具體課程時(shí)間的期望度來構(gòu)造.例如,較難的專業(yè)課嵌入式教師對(duì)課程的期望度是上午的第二節(jié)課,那么GLSC中所有嵌入式課程與GTR中時(shí)間段為滿足上午第二節(jié)的所有節(jié)點(diǎn)連接的邊權(quán)值要盡可能的小.通過設(shè)置權(quán)值,才能更加合理的排出質(zhì)量高的課表.

3.2.2 二分圖模型

根據(jù)上節(jié)構(gòu)造好的二分圖模型,螞蟻都是從左側(cè)GLSC的頂點(diǎn)集出發(fā),根據(jù)轉(zhuǎn)移概率的值和邊集在右側(cè)GTR尋找匹配的節(jié)點(diǎn).然后再返回至GLSC進(jìn)行下一次的搜索工作,如此反復(fù)直到螞蟻為GLSC的頂點(diǎn)集全部安排好上課地點(diǎn)和時(shí)間后,一次循環(huán)結(jié)束.

圖1 二分圖模型

圖1展示了螞蟻一次循環(huán)的過程,螞蟻從A1出發(fā),則螞蟻此次行走的路徑為:

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

3.3 遺傳-蟻群混合算法在排課問題中的應(yīng)用

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

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

為了驗(yàn)證遺傳-蟻群混合算法在排課系統(tǒng)中的應(yīng)用,選取一個(gè)學(xué)院對(duì)排課系統(tǒng)進(jìn)行測試,該學(xué)院的專業(yè)數(shù)量為6,班級(jí)數(shù)量為21,約有800名學(xué)生,55名教師,22間教室,其中有16名教師對(duì)排課有特殊要求,排課單元為202.

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

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

(1)實(shí)驗(yàn)參數(shù)設(shè)置

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

(2)排課效果的比較

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

表5 排課效果比較

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

(3)實(shí)驗(yàn)結(jié)果分析

三種算法的平均運(yùn)算時(shí)間如表5所示,平均適應(yīng)度結(jié)果如表6所示.

表6 運(yùn)算時(shí)間比較

表7 適應(yīng)度比較

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

由表7可得,三種算法的適應(yīng)度與排課的單元成正比.當(dāng)排課單元相同時(shí),遺傳-蟻群混合算法的適應(yīng)度最高.也就證明混合算法排出的課表最優(yōu).

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

在選擇最優(yōu)課表時(shí),可以將適應(yīng)度最大的三個(gè)課表取出,根據(jù)定義排課質(zhì)量的四個(gè)指標(biāo),滿足軟約束條件越多的課表則可作為最終使用的課表

4 結(jié)論

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