何小虎

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

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

1 排課問題概述

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

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

1）在同一時間，一個老師只能安排一門課。

2）在同一時間，一個班級只能安排一門課。

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

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

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

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

2 改進蟻群算法解決排課問題

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

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

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

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

2.2 蟻群算法基本原理

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

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

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

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

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

2.3 運用蟻群算法的改進策略

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

2.3.1 構造人工螞蟻，使得螞蟻具有一定的特殊能力

1）螞蟻能夠記住在周游過程所達到過的結點。2）螞蟻具有路徑識別能力。

2.3.2 信息素的更新策略

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

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

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

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

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

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

3 結 論

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

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

[2]李玉吉.蟻群遺傳算法在高校智能排課系統(tǒng)中的應用[J].現(xiàn)代電子技術，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)化算法及其應用[M]．北京：清華大學出版社，2001．

[5]徐寧，李春光，張?。畮追N現(xiàn)代優(yōu)化算法的比較研究[J]．系統(tǒng)工程與電子技術，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]段海濱.蟻群算法原理及其應用[M].北京：科學技術出版社，2005.

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

[8]張獻.蟻群算法在排課問題中的應用研究[J].長春大學學報，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.