黃阿新

（漳州科技職業(yè)學院，福建 漳州 363202）

隨著高等教育的改革發(fā)展，高校專業(yè)建設加快、培養(yǎng)模式多元化、學生規(guī)模擴大。同時，課程也在拓寬，但是高校的教室、公共機房、專業(yè)實訓室等硬件條件卻無法滿足，從而產(chǎn)生了一個非常突出的問題。因此，將高校有限的資源進行合理的配置是當前迫切需要解決的難題。

高校日常教學工作的順利開展，取決于一份科學、合理、規(guī)范的課程表，它可以提高教學質量。傳統(tǒng)的排課模式無法滿足實際需求，因教室數(shù)量有限、師生配比不足導致每一位老師要承擔較多的教學任務，從而導致排課難度越來越大[1]。

一、排課問題

高校排課問題歸納起來就是對教師、班級、課程、教室、時間等資源的優(yōu)化配置，每學期的排課都是排課人員非常頭痛的事情，即使他們多么的努力，還是無法滿足所有人員的需求。

為了使資源的配置盡可能優(yōu)化，必須滿足以下兩個條件：

（一）硬性條件：

1.一個時間點，學生只能去上一門課，不可能同時上兩門課；

2.一個時間點，教師只能講一門課，不可能同時教多門課；

3.一個時間點，教室只能安排一門合適的課程；

4.給學生安排的教室，必須考慮每一個學生都有座位；

5.體育課之后學生體力透支，不再安排其他課程；

6.前兩節(jié)課與后兩節(jié)課不能安排學生在距離較遠的教室；

7.根據(jù)課程性質安排教室類型。

（二）軟性條件：

1.盡量滿足教師集中上課，但一天的課程最好不超過8節(jié)課；

2.學生的課程盡量安排在白天，并且課程要安排均勻；

3.教師和學生的兩次上課地點不宜太遠；

4.同一個班級相同課程的多次課要有時間間隔；

5.較為難理解的課程盡量安排在上午[2]。

二、蟻群算法

（一）蟻群算法描述

蟻群算法是機率型算法，旨在尋找優(yōu)化路徑。1992年，學者就提出一種模擬優(yōu)化算法，模擬蟻群尋找食物，求出從某一點開始，經(jīng)過若干個地址，最后返回出發(fā)點的最短路徑[3]。

早期的蟻群算法是解決TSP（旅行商問題），許多問題都可以像旅行商問題一樣求解，隨著研究的不斷深入，現(xiàn)在該算法已經(jīng)用于生活的方方面面[4]。

（二）基本原理

當螞蟻移動時，會釋放一種叫做信息素的物質，釋放的信息素會隨著它爬行距離越來越遠而減少。另外，信息素濃度是螞蟻選擇路徑的依據(jù)，而信息素本身就是易揮發(fā)的[5]。螞蟻的移動可以簡單歸納為：

1.當螞蟻沒有發(fā)現(xiàn)信息素時，它的移動是隨機的，而且具有創(chuàng)新性，當遇到障礙時馬上會選擇新的路徑移動；

2.當螞蟻發(fā)現(xiàn)信息素時，它的移動根據(jù)信息素濃度進行選擇，濃度越強越容易被選上；

3.螞蟻可以釋放兩種以上的信息素，“食物”信息素和“家”信息素，然而隨著爬行距離越來越遠，釋放的信息素會越來越少[6]；

4.信息素具有揮發(fā)性。

（三）建蟻群算法的數(shù)學模型

螞蟻a從城市i走到城市j的過程中都會釋放信息素，并且螞蟻選擇下一個城市的依據(jù)是一個概率公式，表示如下：

dij指的是兩個城市之間的距離；τij指的是城市i到城市j的路徑上的信息素的量；τij（t）指的是t時刻兩個城市間殘留的信息素，α和β是啟發(fā)式因子；ηij（t）指的是t時刻兩個城市間路徑（i，j）上的啟發(fā)信息素，ηij（t）=1/dij。

tabua指的是螞蟻a的禁忌列表，為了避免螞蟻a多次進入同一個城市，當螞蟻a進入城市j之后，j就被列入禁忌列表里；Paij（t）指的是螞蟻a從城市i走到城市j的概率。

當所有的螞蟻完成一次路徑循環(huán)后，才更新信息素。因此，路徑上的信息素分為兩部分：未揮發(fā)所殘留的信息素和經(jīng)過當前循環(huán)所有螞蟻在經(jīng)過該路徑后所留下的信息素。用公式表述如下：

ρ指的是信息素揮發(fā)因子，ρ∈[0,1)；△τij(t)指的是t時刻路徑（i,j）上增加的信息素；△ταij(t)指的是t時刻螞蟻a在路徑（i,j）上增加的信息素；Q指的是螞蟻釋放的信息素量；Lα指的是螞蟻a經(jīng)過所有城市的總路徑長度。

三、蟻群算法在排課系統(tǒng)中的應用ρ

將排課問題空間通過另外一種方式進行描述，采用圖形結構，就能使得排課系統(tǒng)模型嵌入蟻群算法，這種圖結構即二分圖[7]，如圖1所示。一般情況，<教師,課程,班級>和<教室,時間>的笛卡爾積即為排課問題解空間，其中，C表示課程、教師和班級所構成的排課結點，T表示可用的時間、教室的結點集合[8]。

圖1 二分圖

蟻群算法在排課系統(tǒng)的應用流程圖，如圖2所示。

圖2 蟻群算法流程圖

蟻群算法在排課問題的解決當中，優(yōu)點很突出，具有正反饋性、通用性、啟發(fā)性、并行性等特點。剛開始蟻群算法信息素生成較慢，影響到搜索能力，然而隨著信息素的增加，搜索能力越強，能很快搜索到最優(yōu)解。很多的研究都發(fā)現(xiàn)，蟻群算法很容易發(fā)現(xiàn)最優(yōu)解，它是一種特殊的強化算法。

四、排課管理系統(tǒng)的設計

（一）需求分析

高校排課系統(tǒng)四大功能，分別為：

1.系統(tǒng)管理：按照同一類型的用戶進行權限組管理，權限管理關系到整個系統(tǒng)的安全。

2.教學資源：設置班級、教師、教室、課程、時間片段等基本信息，從而進行系統(tǒng)排課，管理員對設置的基本信息進行維護。

3.教學計劃：根據(jù)各專業(yè)人才培養(yǎng)方案，設置所開設的課程；

4.課表編排：該功能是使各因素獲得最優(yōu)的組合，實現(xiàn)自動排課。

（二）系統(tǒng)功能模塊設計

該排課系統(tǒng)共開發(fā)四個模塊，其排課系統(tǒng)功能結構圖如圖3所示。

圖3 排課系統(tǒng)功能結構圖

（三）數(shù)據(jù)庫設計

1.教師表，主要是對教師信息的增、查、刪、改。如表1所示。

表1 教師表

2.班級表，主要是對班級信息的增、查、刪、改。如表2所示。

表2 班級表

3.課程表，主要是對課程信息的增、查、刪、改。如表3所示。

表3 課程表

4.教室表，主要是對教師信息的增、查、刪、改。如表4所示。

表4 教室表

5.排課表，系統(tǒng)根據(jù)排課要求排出新學期課程表，也可以作手動輔助修改。如表5所示。

表5 排課表

五、結語

排課問題實質上是一個組合優(yōu)化問題，其復雜度較高。本排課系統(tǒng)采用B/S結構，前端使用Client/Server、SOA等技術，后端使用SSH框架技術?；谟嬎銠C網(wǎng)絡，實現(xiàn)了高校教務管理和排課管理的功能需求分析。運用蟻群算法設計的排課系統(tǒng)，能夠滿足各方面因素，找出最優(yōu)解，大大提高了排課效率，使高校教學資源得到合理的配置。