基于蟻群算法的高校排課問題的應用研究

蔣正鋒，覃韓，呂佩佩，劉溯奇

（廣西民族師范學院數學與計算機科學學院，崇左532200）

0 引言

20 世紀50 年代，一些國外學者首次研究了自動排課系統，如Gotlieb 在1963 年提出了自動排課的數學模型，并對排課問題進行深入的研究，而我國對自動排課的研究始于80 年代初期，起步是比較晚，但取得了一定的成果[1-3]。

自2016 年秋季以來，廣西民族師范學院的課程安排任務從教務處下放到二級學院。一般是二級學院教學秘書手工安排課程，這將是非常耗時耗力，并且教學資源之間有可能存在沖突等情況，排課效果不盡人意。鑒于高等教育招生規模進一步擴大，入學大學生人數不斷增加，相對有限的教學資源提高了課程安排任務的難度和復雜性，如何設計一個多約束高效的自動排課系統替換二級學院手工排課已成為目前亟待解決的問題[4]?？紤]廣西民族師范學院的具體情況，根據各種自動排課算法[5]的特點，本文探討了使用蟻群算法來解決排課問題。

1 排課問題分析

1.1 排課問題五要素

如何合理配置有限的教學資源已成為每個高校避不開的問題，其中編排科學且合理的課表是這個問題的核心部分。排課問題需考慮課程、教師、班級、教室和時間五要素之間的相互制約的不確定因素，它是一多約束、多目標優化的時間表問題，使編排的課表盡可能滿足全校師生的要求。排課過程中涉及到課程、授課教師、上課班級、教室和時間五要素[10]，將其定義為如下的集合：

（1）課程集合：CO={ CO1,CO2,CO3,…,COL }，其中L 是開設課程的數量。

（2）授課教師集合：TE={TE1,TE2,TE3,…,TEK}，其中K 是全校授課教師的數量。

（3）班級集合：CL={CL1,CL2,CL3,…,CLN}，其中N是全校班級的個數。

（4）教室集合：CR={CR1,CR2,CR3,…,CRP}，其中P是不同類型教室的總數。

（5）時間集合：TI={TI1,TI2,TI3,…,TIQ}，其中Q 為25，表示時間片的個數。

1.2 排課問題的約束條件

課表的五要素之間是相互制約的，盡可能的去滿足約束條件，探索五要素之間最優的組合，排出比較合理的課表。排課過程中涉及到的分硬約束和軟約束兩類，其中硬約束是課表必須滿足的約束條件，軟約束是可選的約束條件，它起優化課表的作用。硬約束和軟約束[2,5,9]如下所示：

●硬約束

（1）上課教室在相同時間內，只能排一門課程。

（2）上課班級在相同時間內，只能排一門課程。

（3）授課教師在相同時間內，只能排一門課程。

（3）授課教師在相同時間內，只能給一個班級授課，合班除外。

（4）授課教室容量大小必須大于或等于上課班級的人數。

（5）學校上課教室的總數量必須大于或等于同一時間內上課的總課程數。

（6）上課教室類型要與課程對教室要求的類型匹配。

●軟約束

（1）同一班級的課程應均勻分散在一周內。

（2）同一教師同一門課程不同班級授課，同一天每個班級都安排授課內容，保證教學的連貫性。

（3）同一門班級同一門課間隔安排，至少間隔一天，但也不能超過兩天。

（4）體育課一般安排在下午，并且體育課后不再安排其他課程。

（5）連續上課或授課時，教室之間的距離不能太遠。

（6）數學類課程或專業課，安排在上午，選修課安裝在晚上或者周末。

（7）教師的授課任務間隔安排均勻分散在一周內。

2 蟻群算法概述

2.1 蟻群算法的基本思想

蟻群算法是一種從自然界觀察蟻群覓食行為中衍生出來的仿生優化算法，蟻群借助釋放一種稱為信息素（pheromone）的物質相互協作來發現巢穴與食物之間的最短路徑。蟻群算法最初是用于解決TSP（Traveling Salesman Problem）問題，TSP 問題具有廣泛的代表性，許多其他的問題都可抽象為類似TSP 問題來求解。

（1）蟻群算法的模型描述

一只螞蟻要去m 個城市覓食，它先隨機選擇其中一個城市作為起點，然后再逐個到達其他所有的城市，螞蟻在覓食過程中釋放隨時間推移而揮發的信息素，最后回到起點城市，要求螞蟻每個城市只能達到一次，那么螞蟻按什么順序訪問城市使得覓食的總行程是最短[6]？

（2）構建蟻群算法的數學模型[10]

假設求解問題的規模即覓食城市數為m，蟻群中螞蟻的數量為n 只，則城市集合V={v1,v2,…,vm}，城市之間路徑的集合E={（r,s）|r,s∈V}。定義ci(t)(i=1,…,m)為t 時刻位于城市i 的螞蟻數量，故總的螞蟻數量n 的計算如公式（1）所示。

蟻群算法中出現了禁忌列表、信息素和能見度等概念。禁忌列表是記錄螞蟻經過的城市，為了避免螞蟻多次走進同一城市而設置的一種數據結構，Tubek為螞蟻k 的禁忌表，螞蟻k 經過城市i，則將城市i 添加到禁忌表Tubek，Tubek(q)是螞蟻k 的禁忌表中第q 個元素，表示螞蟻k 經過的第q 個城市。信息素是螞蟻釋放出來的一種物質，這種物質的濃度隨時間推移而揮發。能見度也稱為啟發信息，定義為兩城市間距離的倒數，如公式（2）所示。

σij( t )為城市i 與城市j 之間的啟發信息，dij是兩城市間的距離。城市間距離越近，啟發信息就越大，引導螞蟻搜索，路徑被選擇的概率就越大，這種啟發信息是固定不變的。

Pijk(t)表示t 時刻時，螞蟻k 從城市i 轉移到城市j的概率，Pijk(t)的定義如下公式（3）所示。

其中τij( t )為t 時刻兩個城市間路徑（i,j）上殘留的信息素，α 是信息啟發式因子，殘留信息的重要程度，β 是期望啟發式因子，是信息的相對重要程度。 Jk(i)表示螞蟻k 在城市i 時，下一步允許轉移到的城市集合，定義為如下公式（4）所示。

每只螞蟻覓食訪問完所有城市后，城市間路徑的信息素濃度會發生改變，所以需要對路徑上的信息素進行更新，信息素更新的計算如下公式（5）、（6）和（7）所示。

其中Δτij(t)為t 時刻路徑（i,j）上增加的信息素，是t 時刻螞蟻k 在路徑（i,j）上增加的信息素。ρ 是信息素蒸發系數，1-ρ 為信息素的持久性系數。螞蟻釋放的信息素量為Q，Lk是螞蟻k 是經過所有城市的總路徑長度。

2.2 蟻群算法的二分圖模型

二分圖模型[10]是由頂點、邊和權值三部分組成的無向圖G=（N,S,C），圖中所有頂點N 劃分為互補的兩個集合，不同集合頂點的連接構成了邊集合S，邊的權值集合C 是選擇下一個頂點的依據。二分圖模型如下圖1 所示。

圖1 二分圖模型

排課問題的五要素課程、教師、班級、教室和時間的笛卡爾積CO×TE×CL×CR×TI 就構成排課問題的解空間，排課問題就是在這個解空間上尋找滿足所有硬約束條件并且盡可能滿足軟約束條件的解。因為任課計劃表中教師給哪個班教授什么課程是確定的，所以課程、教師、班級的笛卡兒積CO×TE×CL 簡化為COTECL，教師和時間是滿射的關系，其笛卡兒積為CRTI=CR×TI。

（1）二分圖的頂點集合

開設哪些課程是根據培養方案先制定下學期合理的任課計劃表，任課計劃表中教師給哪個班教授什么課程是確定的，因此課程、教師和班級看成綁定在一起的組合，把排課問題中的課程、教師和班級組合組成的COTECL 集合作為二分圖左邊的頂點集。教室和時間動態組合組成的CRTI 集合作為二分圖右邊的頂點集。

（2）二分圖邊的集合

二分圖左邊COTECL 集合中的頂點與右邊CRTI集合中的頂點只要滿足對教室安排的兩個基本條件才能進行連接構成邊的集合。對教室安排要滿足的兩個基本條件：一是COTECL 集合頂點中班級的人數要少于CRTI 集合頂點中教室的容量，二是COTECL 集合頂點中課程對教室要求的類型與教室的類型是一致的。

（3）二分圖邊的權值

二分圖中邊的權值是根據具體課程時間的期望度來設置，排課過程中通過依據合理的權值才能排出高質量的課表。

3 基于蟻群算法的自動排課模型

蟻群算法解決排課問題[7,9]，需建立特殊的圖形結構，由排課問題分析可知，排課過程中的課程、教師、班級、教室和時間五要素之間的關系轉成COTECL“課程、教師、班級”和CRTI“教室、時間”之間的關系，則使用二分圖模型可解決兩個互不相交COTECL 集合和CRTI 集合的最大匹配問題。

構造排課問題滿足硬約束條件的二分圖模型，可完成排課問題的基本需求，即任課計劃中應開設的班級課程都在右邊頂點集中，教室要滿足安排所有課程的需求，以及教師、班級、課程時間不沖突，但是優化課表，還需要使用蟻群算法進一步的動態調整[5]。

3.1 蟻群算法排課步驟

步驟1：參考任課計劃表，把排課問題的五要素分成兩個頂點集合COTECL 和CRTI，然后連接滿足條件的COTECL 和CRTI 集合中的頂點，構建邊集合及邊兩邊頂點公用權值信息表，建立二分圖模型。

步驟2：初始化蟻群算法中信息啟發因子、期望啟發因子、信息素蒸發系數、循環迭代次數、信息素濃度記錄表等參數。

步驟3：初始化所有教師時間分配表、班級時間分配表和教室時間分配表，初始化每只螞蟻的臨時課表、個體權值、禁忌表、訪問過的頂點集和CRTI 中教室和時間的分配表。

步驟4：判斷迭代優化是否結束，如果CNT＜=MAXITER 為假，則跳轉到步驟11。

步驟5：所有螞蟻分別隨機分配COTECL 集合中的一個頂點，初始化每只螞蟻的個體權值和課表。

步驟6：判斷每只螞蟻是否訪問過所有COTECL集合中的頂點，如果訪問了所有的頂點，則跳轉到步驟10，否則隨機選擇一個沒有訪問過的頂點。

步驟7：計算每只螞蟻的轉移概率Pij( t )，然后使用輪盤賭算法去選擇路徑。

步驟8：判斷是否滿足硬約束，如存在沖突，則跳轉到步驟7 重新選擇路徑。

步驟9：記錄選好的路徑，修改螞蟻個體課表、禁忌表、訪問過的頂點集和個體權值，跳轉到步驟6。

步驟10：更新二分圖模型的信息素濃度值，跳轉到步驟3。

步驟11：輸出個體權值即代價最小的課程表。

3.2 蟻群算法自動排課流程圖

圖2 蟻群算法自動排課流程圖

4 基于蟻群算法智能排課系統

本排課系統采用B/S 結構，前端使用HTML、CSS、JavaScript 和Bootstrap 等技術，后端采用SSM 框架技術，最后通過自動化構建工具Maven 來管理整合整個項目。

排課系統面向的學校管理人員、教師和學生，所以根據使用系統用戶對象的不同，整個系統分管理員操作模塊、教師操作模塊和學生操作模塊，用戶登錄界面如圖3 所示。

圖3 基于蟻群算法智能排課系統的登錄界面

自動排課是屬于管理員操作模塊，也是本系統最為核心的部分。管理員成功登錄后，進入管理員操作界面，主要有班級管理、課程管理、教師管理、教室管理和自動排課等功能模塊，系統功能界面如圖4 所示。

圖4 基于蟻群算法智能排課系統功能界面

其中自動排課是經過班級、課程、教師和教室等基本數據維護后進行自動排課，可對生成的課表進行查看、修改、檢查和確認操作。確認自動排課課表之前可進行課表檢查及手動修改，最終確認后，將課表數據維護到系統數據庫中，系統自動排課界面如圖5 所示。

自動排課保存到數據庫中的課表是班級課表，課表分班級課表、教師課表和教室課表三種，但教師課表和教室課表可由班級課表變換得到。某教師登錄排課系統查看自己下學期授課任務的課表如圖6 所示。

圖5 基于蟻群算法智能排課系統自動排課界面

圖6 教師查看自己的課表

5 結語

如何合理配置有限的教學資源已成為每個高校避不開的問題，其中編排全校科學與合理的課程表是這個問題的核心部分。本文簡單介紹了蟻群算法及二分圖的基本原理，并對排課問題的硬約束和軟約束條件進行了分析，考慮廣西民族師范學院的具體情況，對蟻群算法以及二分圖匹配策略進行分析，設計了一個基于蟻群算法的自動優化課表的排課模型，排課結果表明該智能排課模型先生成一個滿足硬約束的基本課表，然后自動優化成較科學與合理的課表，省時又省力。隨著學校的快速發展及招生規模的進一步擴大，以及學校教務管理工作的變化，因此排課問題有待于進一步研究。