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

（廣西民族師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，崇左532200）

0 引言

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

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

1 排課問題分析

1.1 排課問題五要素

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

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

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

（3）班級(jí)集合：CL={CL1,CL2,CL3,…,CLN}，其中N是全校班級(jí)的個(gè)數(shù)。

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

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

1.2 排課問題的約束條件

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

●硬約束

（1）上課教室在相同時(shí)間內(nèi)，只能排一門課程。

（2）上課班級(jí)在相同時(shí)間內(nèi)，只能排一門課程。

（3）授課教師在相同時(shí)間內(nèi)，只能排一門課程。

（3）授課教師在相同時(shí)間內(nèi)，只能給一個(gè)班級(jí)授課，合班除外。

（4）授課教室容量大小必須大于或等于上課班級(jí)的人數(shù)。

（5）學(xué)校上課教室的總數(shù)量必須大于或等于同一時(shí)間內(nèi)上課的總課程數(shù)。

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

●軟約束

（1）同一班級(jí)的課程應(yīng)均勻分散在一周內(nèi)。

（2）同一教師同一門課程不同班級(jí)授課，同一天每個(gè)班級(jí)都安排授課內(nèi)容，保證教學(xué)的連貫性。

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

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

（5）連續(xù)上課或授課時(shí)，教室之間的距離不能太遠(yuǎn)。

（6）數(shù)學(xué)類課程或?qū)I(yè)課，安排在上午，選修課安裝在晚上或者周末。

（7）教師的授課任務(wù)間隔安排均勻分散在一周內(nèi)。

2 蟻群算法概述

2.1 蟻群算法的基本思想

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

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

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

（2）構(gòu)建蟻群算法的數(shù)學(xué)模型[10]

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

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

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

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

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

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

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

2.2 蟻群算法的二分圖模型

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

圖1 二分圖模型

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

（1）二分圖的頂點(diǎn)集合

開設(shè)哪些課程是根據(jù)培養(yǎng)方案先制定下學(xué)期合理的任課計(jì)劃表，任課計(jì)劃表中教師給哪個(gè)班教授什么課程是確定的，因此課程、教師和班級(jí)看成綁定在一起的組合，把排課問題中的課程、教師和班級(jí)組合組成的COTECL 集合作為二分圖左邊的頂點(diǎn)集。教室和時(shí)間動(dòng)態(tài)組合組成的CRTI 集合作為二分圖右邊的頂點(diǎn)集。

（2）二分圖邊的集合

二分圖左邊COTECL 集合中的頂點(diǎn)與右邊CRTI集合中的頂點(diǎn)只要滿足對(duì)教室安排的兩個(gè)基本條件才能進(jìn)行連接構(gòu)成邊的集合。對(duì)教室安排要滿足的兩個(gè)基本條件：一是COTECL 集合頂點(diǎn)中班級(jí)的人數(shù)要少于CRTI 集合頂點(diǎn)中教室的容量，二是COTECL 集合頂點(diǎn)中課程對(duì)教室要求的類型與教室的類型是一致的。

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

二分圖中邊的權(quán)值是根據(jù)具體課程時(shí)間的期望度來設(shè)置，排課過程中通過依據(jù)合理的權(quán)值才能排出高質(zhì)量的課表。

3 基于蟻群算法的自動(dòng)排課模型

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

構(gòu)造排課問題滿足硬約束條件的二分圖模型，可完成排課問題的基本需求，即任課計(jì)劃中應(yīng)開設(shè)的班級(jí)課程都在右邊頂點(diǎn)集中，教室要滿足安排所有課程的需求，以及教師、班級(jí)、課程時(shí)間不沖突，但是優(yōu)化課表，還需要使用蟻群算法進(jìn)一步的動(dòng)態(tài)調(diào)整[5]。

3.1 蟻群算法排課步驟

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

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

步驟3：初始化所有教師時(shí)間分配表、班級(jí)時(shí)間分配表和教室時(shí)間分配表，初始化每只螞蟻的臨時(shí)課表、個(gè)體權(quán)值、禁忌表、訪問過的頂點(diǎn)集和CRTI 中教室和時(shí)間的分配表。

步驟4：判斷迭代優(yōu)化是否結(jié)束，如果CNT＜=MAXITER 為假，則跳轉(zhuǎn)到步驟11。

步驟5：所有螞蟻分別隨機(jī)分配COTECL 集合中的一個(gè)頂點(diǎn)，初始化每只螞蟻的個(gè)體權(quán)值和課表。

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

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

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

步驟9：記錄選好的路徑，修改螞蟻個(gè)體課表、禁忌表、訪問過的頂點(diǎn)集和個(gè)體權(quán)值，跳轉(zhuǎn)到步驟6。

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

步驟11：輸出個(gè)體權(quán)值即代價(jià)最小的課程表。

3.2 蟻群算法自動(dòng)排課流程圖

圖2 蟻群算法自動(dòng)排課流程圖

4 基于蟻群算法智能排課系統(tǒng)

本排課系統(tǒng)采用B/S 結(jié)構(gòu)，前端使用HTML、CSS、JavaScript 和Bootstrap 等技術(shù)，后端采用SSM 框架技術(shù)，最后通過自動(dòng)化構(gòu)建工具M(jìn)aven 來管理整合整個(gè)項(xiàng)目。

排課系統(tǒng)面向的學(xué)校管理人員、教師和學(xué)生，所以根據(jù)使用系統(tǒng)用戶對(duì)象的不同，整個(gè)系統(tǒng)分管理員操作模塊、教師操作模塊和學(xué)生操作模塊，用戶登錄界面如圖3 所示。

圖3 基于蟻群算法智能排課系統(tǒng)的登錄界面

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

圖4 基于蟻群算法智能排課系統(tǒng)功能界面

其中自動(dòng)排課是經(jīng)過班級(jí)、課程、教師和教室等基本數(shù)據(jù)維護(hù)后進(jìn)行自動(dòng)排課，可對(duì)生成的課表進(jìn)行查看、修改、檢查和確認(rèn)操作。確認(rèn)自動(dòng)排課課表之前可進(jìn)行課表檢查及手動(dòng)修改，最終確認(rèn)后，將課表數(shù)據(jù)維護(hù)到系統(tǒng)數(shù)據(jù)庫中，系統(tǒng)自動(dòng)排課界面如圖5 所示。

自動(dòng)排課保存到數(shù)據(jù)庫中的課表是班級(jí)課表，課表分班級(jí)課表、教師課表和教室課表三種，但教師課表和教室課表可由班級(jí)課表變換得到。某教師登錄排課系統(tǒng)查看自己下學(xué)期授課任務(wù)的課表如圖6 所示。

圖5 基于蟻群算法智能排課系統(tǒng)自動(dòng)排課界面

圖6 教師查看自己的課表

5 結(jié)語

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