一種改進蟻群算法在排課中的應用研究

何小虎

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

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

1 排課問題概述

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

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

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

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

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

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

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

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

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

2.1 排課問題的數學模型

Carter和Laporte提出：高校排課問題是一個多元分配問題，它研究的就是如何把學生和老師分配給課程，課程單元或者班級，如何把事件（上課事件）分配給教室和時間[2]。解決排課問題可以轉化為解決<課程、班級、教師>關系節點和<時間、教室>關系節點所構成的二分圖的最大匹配問題[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，表示教師、班級和課程三者有關聯的集合，R2=Classroom×Time。 則 R=R1×R2，這樣就形成了一個新圖 G（N，S），其中 N就 是 圖 G 中 的 所 有 節 點 ，N=R1∪R2，S 表 示 邊 ，S={（n1，n2）|n1∈R1，n2∈R2}，排課算法也就變成了二分圖匹配的問題了。排課算法就是在屬于R1中的節點中為屬于R2的某一個節點尋找一個合適的節點進行匹配。

2.2 蟻群算法基本原理

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

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

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

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

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

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

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

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

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

2.3.2 信息素的更新策略

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

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

2.3.3 狀態轉移規則

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

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

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

3 結 論

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

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

[2]李玉吉.蟻群遺傳算法在高校智能排課系統中的應用[J].現代電子技術，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，FU Ying-liang.Discusses how to use the ant colony algorithm class arrangement system[J].Science Information，2007（9）:26.

[4]王凌．智能優化算法及其應用[M]．北京：清華大學出版社，2001．

[5]徐寧，李春光，張健．幾種現代優化算法的比較研究[J]．系統工程與電子技術，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]張忠.基于蟻群算法的時間表問題的研究與實現[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.