一種改進(jìn)蟻群算法在排課中的應(yīng)用研究

何小虎

（渭南師范學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，陜西 渭南 714000）

隨著在校人數(shù)不斷增多，合理利用教學(xué)資源，提高教學(xué)質(zhì)量，是每個(gè)高校的首要任務(wù)。所以，有效組織各種軟硬件資源，安排合理的課表顯得尤為重要，因此，本文提出了利用改進(jìn)蟻群算法來實(shí)現(xiàn)高校課程的排課問題，設(shè)計(jì)出符合教學(xué)規(guī)律和教學(xué)要求的課表。

1 排課問題概述

20世紀(jì)50年代末，國外就有人開始研究課表編排問題。1962年，Gotlieb曾提出一個(gè)課表問題的數(shù)學(xué)模型[1]，1976年S．Even第一次證明了課表問題是NP完全問題，隨后，許多學(xué)者開始研究TTP問題。

高校的排課是一項(xiàng)十分繁重而復(fù)雜的工作。我們學(xué)院的課表安排涉及到49個(gè)專業(yè)、幾百名教師、16 000多名學(xué)生，同時(shí)要對幾百門課程進(jìn)行合理的組織安排，充分利用有限的教學(xué)資源，因此，合理安排一張高效的課表顯得越發(fā)重要。高校課表要實(shí)現(xiàn)滿意度高，沖突少，實(shí)現(xiàn)科學(xué)化，合理化，充分發(fā)揮空間、時(shí)間、人力的效益。就應(yīng)遵循一定的規(guī)則，以滿足各種約束條件，避免沖突的發(fā)生。

1）在同一時(shí)間，一個(gè)老師只能安排一門課。

2）在同一時(shí)間，一個(gè)班級只能安排一門課。

3）教師沖突問題，主要涉及到下面幾個(gè)問題，

①在同時(shí)間里，教室總數(shù)要大于安排的總課程數(shù)。②教室的座位數(shù)必須滿足上課學(xué)生人數(shù)。③相應(yīng)的課程必修安排在所需要類型的教室中。

以上幾點(diǎn)是最基本的硬性約束條件，但是還需要滿足一些其他的軟性要求：

①課程在一周有多次的，應(yīng)有一定的時(shí)間間隔。②根據(jù)課程的需要，盡量安排在合理的時(shí)間內(nèi)。③盡量滿足特殊教師的需要。

2 改進(jìn)蟻群算法解決排課問題

2.1 排課問題的數(shù)學(xué)模型

Carter和Laporte提出：高校排課問題是一個(gè)多元分配問題，它研究的就是如何把學(xué)生和老師分配給課程，課程單元或者班級，如何把事件（上課事件）分配給教室和時(shí)間[2]。解決排課問題可以轉(zhuǎn)化為解決<課程、班級、教師>關(guān)系節(jié)點(diǎn)和<時(shí)間、教室>關(guān)系節(jié)點(diǎn)所構(gòu)成的二分圖的最大匹配問題[3]。

一般排課問題所涉及的元素主要有以下5種：班級集合：Class={C1，C2，…，Cn}；教師集合：Teacher={T1，T2，…，Tn}；教室集合：Classroom={CR1，CR2，…CRn）；課程集合：Lesson={L1，L2，…，Ln}；時(shí)間集合：Time={T1，T2，……，Tn}，

設(shè)一個(gè)三元組關(guān)系<教師，班級，課程>為R1和一個(gè)二元組關(guān)系為<教室，時(shí)間>為 R2。 其中 R1=Teacher×Class×Lesson，表示教師、班級和課程三者有關(guān)聯(lián)的集合，R2=Classroom×Time。 則 R=R1×R2，這樣就形成了一個(gè)新圖 G（N，S），其中 N就 是 圖 G 中 的 所 有 節(jié) 點(diǎn) ，N=R1∪R2，S 表 示 邊 ，S={（n1，n2）|n1∈R1，n2∈R2}，排課算法也就變成了二分圖匹配的問題了。排課算法就是在屬于R1中的節(jié)點(diǎn)中為屬于R2的某一個(gè)節(jié)點(diǎn)尋找一個(gè)合適的節(jié)點(diǎn)進(jìn)行匹配。

2.2 蟻群算法基本原理

蟻群算法是模擬真實(shí)蟻群覓食過程尋求最短路經(jīng)的原理，由意大利學(xué)者M(jìn) Dorigo等人首先提出的[4]。自然界中的螞蟻是以外激素（pheromone）為媒進(jìn)行信息傳遞的，從而螞蟻個(gè)體能相互協(xié)作，完復(fù)雜的任務(wù)。蟻群的行為表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上經(jīng)過的螞蟻越多，則后到者選擇該路徑的概率就越大[5]。

蟻群算法可以表述如下：初始時(shí)刻，各條路徑上的信息素量相等，設(shè) τij（0）=C（C 為常數(shù)），螞蟻 k（k=1，2，3，…，m）在運(yùn)動過程中根據(jù)各條路徑上的信息量決定轉(zhuǎn)移方向。螞蟻系統(tǒng)所使用的轉(zhuǎn)移規(guī)則被稱為隨機(jī)比例規(guī)則，在時(shí)刻t，螞蟻k從城市i選擇城市j的轉(zhuǎn)移概率（t）為：

其中，Jk（i）={1，2，……，n}-tabuk表示螞蟻 k 下一步允許選擇的城市。列表tabuk記錄了螞蟻k在本次迭代中已經(jīng)走過的城市，不允許該螞蟻在本次循環(huán)中再經(jīng)過這些城市。當(dāng)所有n座城市都加入到tabuk中時(shí)，螞蟻k便完成了一次周游，此時(shí)螞蟻 k所走過的路徑便是 TSP問題的一個(gè)可行解。（1）式中的ηij是一個(gè)啟發(fā)式因子，被稱為能見度因子。在AS算法中，ηij通常取城市 i與城市 j之間距離的倒數(shù)。α和β分別反映了在螞蟻的運(yùn)動過程中已積累的信息和啟發(fā)信息的相對重要程度。當(dāng)所有螞蟻完成一次周游后，各路徑上的信息素根據(jù)（2）式更新。

其中ρ（0<ρ<1）表示路徑上信息素的揮發(fā)系數(shù)，1-ρ表示信息素的持久系數(shù)；Δτij表示本次迭代邊（ij）上信息素的增量。表示第 k只螞蟻在本次迭代中留在邊（ij）上的信息素量。如果螞蟻 k 沒有經(jīng)過邊（ij），則的值為 0。表示為：

其中，Q為正常數(shù)，Lk表示第k只螞蟻在本次周游中所走過路徑的長度[6]。

2.3 運(yùn)用蟻群算法的改進(jìn)策略

針對蟻群算法容易出現(xiàn)停滯現(xiàn)象、陷入局部最優(yōu)，搜索時(shí)間過長等缺陷，要使算法保持高效的搜索能力同時(shí)又能夠避免停滯現(xiàn)象的關(guān)鍵是在“探索”和“利用”之間建立一個(gè)平衡點(diǎn)，也就是說既要使算法的搜索空間盡可能的大，以尋找那些可能存在最優(yōu)解的解空間；同時(shí)又要充分利用群體內(nèi)當(dāng)前的有效信息，使算法搜索的側(cè)重點(diǎn)放在那些具有較高適應(yīng)值的個(gè)體所在的空間內(nèi)，即縮小算法的探索空間，從而使算法在可以接受的時(shí)間內(nèi)收斂到全局最優(yōu)解[7]。

2.3.1 構(gòu)造人工螞蟻，使得螞蟻具有一定的特殊能力

1）螞蟻能夠記住在周游過程所達(dá)到過的結(jié)點(diǎn)。2）螞蟻具有路徑識別能力。

2.3.2 信息素的更新策略

信息素的更新策略是對優(yōu)質(zhì)解進(jìn)行更大限度的增強(qiáng)，而對劣質(zhì)解進(jìn)行削弱，使得屬于優(yōu)質(zhì)路徑的邊與屬于劣質(zhì)路徑的邊之間的信息素量差異進(jìn)一步增大，從而使螞蟻的搜索行為更集中于最優(yōu)解的附近。該改進(jìn)算法主要修改了蟻群系統(tǒng)中的全局更新公式。當(dāng)所有螞蟻完成一次循環(huán)后，增加對最差螞蟻所經(jīng)過的路徑信息素的更新，信息素量按下面公式進(jìn)行調(diào)整[8]。

其中，K為該算法引入的一個(gè)參數(shù)，Lworst表示當(dāng)前循環(huán)中最差螞蟻的路徑長度，Lbest表示當(dāng)前循環(huán)中最優(yōu)螞蟻的路徑長度，τij（r，s）表示兩個(gè)目標(biāo)之間的信息素軌跡量。

2.3.3 狀態(tài)轉(zhuǎn)移規(guī)則

狀態(tài)轉(zhuǎn)移規(guī)則[9]為更好更合理地探索新路徑和利用先驗(yàn)知識提供了方法。在基本蟻群算法中，螞蟻完全依賴概率進(jìn)行路徑選擇，使用的是隨機(jī)比例規(guī)則，蟻群系統(tǒng)使用了不同的決策規(guī)則，稱之為偽隨機(jī)比例規(guī)則。這個(gè)決策規(guī)則具有雙重功率。決策規(guī)則既可以利用關(guān)于問題的先驗(yàn)知識，也可以有傾向性的搜索。

其中J是根據(jù)（1）式計(jì)算出來的。參數(shù)q0的大小決定了利用先驗(yàn)知識和探索新路徑之間的相對重要性。每當(dāng)螞蟻要選擇下一個(gè)城市時(shí)，它就選取一個(gè)隨機(jī)數(shù)0≤q≤1，如果q≤q0，則根據(jù)先驗(yàn)知識公式來選擇最好的邊，否則就按照公式概率的選擇一條邊。

該優(yōu)化的蟻群算法在我們學(xué)院課表編排中得到實(shí)際應(yīng)用，通過在200個(gè)普通教室，105個(gè)多媒體教室，15個(gè)機(jī)房（15×50=750臺），各類實(shí)驗(yàn)室若干。在校學(xué)生16 000多個(gè)，任課教師689人應(yīng)用本算法編排結(jié)果來看，排課的效率和課表質(zhì)量一定提高，沖突現(xiàn)象也明顯減少。

3 結(jié) 論

狀態(tài)轉(zhuǎn)移和信息素在蟻群算法中起著關(guān)鍵性的作用，文中優(yōu)化的蟻群算法結(jié)合了蟻群系統(tǒng)中的狀態(tài)轉(zhuǎn)移規(guī)則和最優(yōu)最差螞蟻系統(tǒng)中的信息素更新策略，從而有效地引導(dǎo)螞蟻向更優(yōu)的路徑移動，有效地克服了基本蟻群算法存在的容易出現(xiàn)停滯現(xiàn)象、陷入局部最優(yōu)，搜索時(shí)間過長的缺點(diǎn)。

[1]張林.基于蟻群算法的排課系統(tǒng)研究與設(shè)計(jì)[D].安徽：安徽大學(xué)，2005.

[2]李玉吉.蟻群遺傳算法在高校智能排課系統(tǒng)中的應(yīng)用[J].現(xiàn)代電子技術(shù)，2010（14）:121-123.LI Yu-ji.Application of ant-colony genetic algorithm in smart course schedule systems of colleges [J].Modern Electronics Technique，2010（14）:121-123.

[3]趙惠怡，劉道源，傅英亮.探討如何利用蟻群算法解決排課問題[J].科技信息，2007（9）:26.ZHAO Hui-Yi，LI Dao-yuan，F(xiàn)U Ying-liang.Discusses how to use the ant colony algorithm class arrangement system[J].Science Information，2007（9）:26.

[4]王凌．智能優(yōu)化算法及其應(yīng)用[M]．北京：清華大學(xué)出版社，2001．

[5]徐寧，李春光，張?。畮追N現(xiàn)代優(yōu)化算法的比較研究[J]．系統(tǒng)工程與電子技術(shù)，2002（12）：100-103．XU Ning，LI Chun-guang，ZHANG Jian.Several modern comparative study of optimization algorithm [J].Systems Engineering and Electronics，2002（12）：100-103．

[6]段海濱.蟻群算法原理及其應(yīng)用[M].北京：科學(xué)技術(shù)出版社，2005.

[7]張忠.基于蟻群算法的時(shí)間表問題的研究與實(shí)現(xiàn)[D].蘇州：蘇州大學(xué)，2006.

[8]張獻(xiàn).蟻群算法在排課問題中的應(yīng)用研究[J].長春大學(xué)學(xué)報(bào)，2007，17（10）:80-82.ZHANG Xian.Ant colony algorithm based on the research of theproblem and realize the schedule [J].Journalof Changchun University，2007，17（10）:80-82.

[9]Dorigo.Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation，1997，1（1）:53-66.