懷麗波，崔榮一，趙亞慧

(延邊大學(xué)工學(xué)院 計算機科學(xué)與技術(shù)系，吉林 延吉 133002)

0 引言

近年來高校招生規(guī)模呈不斷擴大趨勢，使得許多高校都存在著學(xué)生數(shù)量多而相應(yīng)的教室資源有限的情況，因此教室的安排是否合理直接影響到學(xué)校教育資源的有效利用.教室管理問題作為排課問題的子問題，主要完成課程的教室分配任務(wù).排課問題作為一個多目標(biāo)、帶有模糊約束條件的組合優(yōu)化問題，1975年E.nen等證明了其屬于NP完全問題.目前，解決這個問題的方法有很多，主要有模擬退火算法、圖著色算法、遺傳算法、粒子群算法，以及幾種算法的混合方法等[1-4].針對教室管理問題的優(yōu)化，文獻[5]給出了從課程表到教室調(diào)度表的實現(xiàn)方法，文獻[6]針對減少教室流動性問題，提出固定一定教室比例的方法，但目前綜合考慮教室管理優(yōu)化問題的研究還很少.基于此，本文利用改進的蟻群算法對該問題進行研究.

1 教室管理問題的數(shù)學(xué)描述

教室管理問題主要涉及5個要素：時間、教師、教室、班級、課程.作為排課問題的一個子問題，教室管理優(yōu)化問題假設(shè)時間、教師要素已經(jīng)排好，故只涉及到3個硬性約束條件:①同一個教室在相同時間只能安排一門課；②每個教室的教室容量要大于上課班級的學(xué)生人數(shù)；③教室總數(shù)量在所有的時間里要滿足課程總門數(shù).

1.1 教室管理問題優(yōu)化要點

針對教室管理的優(yōu)化，本文研究主要集中在以下幾個軟約束條件：

1) 減少空閑座位，提高教室利用率；

2) 為提高學(xué)習(xí)效率，連續(xù)上課的同一班級盡量安排在同一教室，減少學(xué)生的課間流動性；

3) 選擇教室時，盡量使教室資源集中使用，多余教室可作為自習(xí)室或社團活動室靈活使用；

4) 為使教室最大化利用，單周和雙周同一時間上課的課元使用同一個教室.

1.2 教室管理優(yōu)化問題的二部圖模型

1.2.1構(gòu)造二部圖的節(jié)點

1) 課元結(jié)點GLCT由數(shù)組〈課程,班級,教師〉組成：課程集合包含課程代碼、課程名稱、上課時間、需要的教室類型等屬性；班級有班級編號、名稱、人數(shù)等屬性；教師包括教師編號、姓名、所在部門、職稱等屬性.課元是最小單位，每個課元有不同的編號，每周一次以上的課按不同的課元處理.

2) 目標(biāo)結(jié)點GPR由數(shù)組〈上課時間，教室〉組成：上課時間有〈單雙周,星期,節(jié)次〉 3個屬性；教室集合包含教室編號、名稱、容量、教室類型等屬性；同時需滿足|GLCT|?|GPR|.

1.2.2構(gòu)造二部圖的邊和權(quán)值 作為教室管理優(yōu)化問題，課元的上課時間已經(jīng)確定，所以每個課元結(jié)點不是和所有的目標(biāo)節(jié)點連邊，二部圖的邊需要滿足以下條件：①課元結(jié)點的上課時間和目標(biāo)結(jié)點的上課時間相同；②教室的容量大于上課學(xué)生人數(shù)；③教室類型要匹配.

邊的權(quán)值w(i,j)=教室容量-學(xué)生人數(shù).教室管理優(yōu)化問題轉(zhuǎn)化為為每個課元結(jié)點尋找一個對應(yīng)的目標(biāo)節(jié)點，即轉(zhuǎn)化為帶權(quán)二部圖的完備匹配問題.

2 改進的蟻群算法求解教室管理優(yōu)化問題

蟻群算法是對螞蟻群落食物采集過程的模擬，其主要特點是正反饋、分布式計算.蟻群算法先后被應(yīng)用至TSP問題、車間作業(yè)調(diào)度問題、車輛路徑問題等多個經(jīng)典組合優(yōu)化問題[7-8]；近年來，一些學(xué)者針對蟻群算法進行了改進，比如應(yīng)用比較廣泛的最大最小螞蟻系統(tǒng)[9]等.

2.1 基本蟻群算法的數(shù)學(xué)模型

(1)

其中:allowedk={0,1,2,…,n-1}-tabuk(k=1,2,3,…,m)表示螞蟻k下一個可以選擇的節(jié)點;ηi j代表啟發(fā)函數(shù)，一般取ηi j=1/di j，di j代表結(jié)點i,j之間的長度;α代表信息量殘留的重要程度;β代表啟發(fā)函數(shù)的重要程度.每條路徑的信息量要在每只螞蟻走完一步或完成遍歷后,根據(jù)公式(2)做出調(diào)整：

τi j(t+n)=(1-ρ)τi j(t)+△τi j,

(2)

2.2 針對教室管理問題改進的蟻群算法

教室管理優(yōu)化問題是為帶權(quán)二部圖尋找最小的完備匹配，即尋找一個單射f∶GLCTGPR，在盡量滿足軟約束條件下，總權(quán)值最小.

2.2.1數(shù)據(jù)準(zhǔn)備 1) 排序.為提高蟻群算法的局部搜索能力，將課元按照班級學(xué)生人數(shù)降序排列(人數(shù)多的優(yōu)先級高)，同一個班級按照上課時間的先后排序；目標(biāo)集按照教室容量升序排列,教室容量相同的按照上課時間先后排序；并將同一個班級單雙周的課程合并成一個課元.2)分組.為縮小螞蟻的搜索空間，將兩個節(jié)點集按匹配的教室類型進行分組，將二部圖劃分為幾個二部子圖.

2.2.2算法的主要內(nèi)容 1) 轉(zhuǎn)移概率.使用蟻群系統(tǒng)的偽隨機比例規(guī)則：

(3)

其中：ηi j=1/wi j；q0(0≤q0≤1)是初始設(shè)定的參數(shù)；q是一個隨機數(shù)，q∈[0，1]；參數(shù)q0的大小決定了利用先驗知識和探索新路徑之間的相對重要性.每當(dāng)螞蟻要選擇下一個目標(biāo)時，它就選取一個隨機數(shù)0≤q≤1，如果q≤q0，則根據(jù)先驗知識公式來選擇最好的邊，否則J按照公式概率(1)選擇.該轉(zhuǎn)移策略將確定性選擇和隨機選擇相結(jié)合，既保證搜索收斂性好,又避免過早陷于搜索停滯.

2) 信息素更新策略.更新策略使用基于超立方框架的最大最小蟻群算法[13],通過設(shè)置信息素的上下限，將各路徑初始化信息素濃度設(shè)為τmax，這樣可解決應(yīng)用過程中出現(xiàn)的停滯和擴散問題，避免信息素的無限制累加和可能出現(xiàn)的信息素為零的現(xiàn)象，提高算法的魯棒性.

同時為進一步增大最優(yōu)路徑邊與劣質(zhì)路徑邊之間的信息素量差異，引入負反饋機制，使螞蟻的搜索行為更集中于最優(yōu)解的附近.每條路徑的信息量在迭代后根據(jù)公式(4)做出調(diào)整：

τ∈[τmin,τmax],

(4)

其中K為引入的一個參數(shù)，Lworst表示當(dāng)前循環(huán)中最差螞蟻的路徑長度，Lbest表示當(dāng)前最好的路徑長度，τmin和τmax表示信息素的上下限.

2.2.3算法的主要步驟 本文提出的教室管理優(yōu)化問題的蟻群算法的實現(xiàn)步驟為：

step 1 參數(shù)初始化：設(shè)置螞蟻個數(shù)m，迭代次數(shù)N=0；最大迭代循環(huán)次數(shù)Nmax，初始化新信息素τi j(0)=τmax, 將m只螞蟻隨機分布在GLCT中的起點上;

step 2N∶=N+1；

step 3 當(dāng)N

step 4 選擇具有最大狀態(tài)轉(zhuǎn)移概率的元素j，修改螞蟻k的禁忌表，將j加入禁忌表中；

step 5 若沒有遍歷完GLCT中的所有點，跳轉(zhuǎn)到第3步，否則轉(zhuǎn)到第6步;

step 6 計算螞蟻k的路徑長度Lk，通過比較其大小求得最短長度Lbest和最長長度Lworst；

step 7 按照(4)式進行信息素更新;

step 8 如果滿足結(jié)束條件，即N=Nmax，迭代結(jié)束，輸出結(jié)果；否則，清空禁忌表，跳轉(zhuǎn)到第2步.

3 實驗結(jié)果與分析

為驗證算法的有效性，以延邊大學(xué)工學(xué)院69門課程、6個班級、16個教室為數(shù)據(jù)進行仿真實驗，實驗參數(shù)設(shè)置參照文獻[14].對基本蟻群算法和改進蟻群算法進行對比試驗，對每次試驗記錄下最優(yōu)解Length_best，以實現(xiàn)算法性能的比較.

圖1和圖2分別給出了基本蟻群算法和改進蟻群算法得出的類型相同、容量相同的教室排課表：教室編號6和7的教室容量和類型相同，矩陣表示的是周一到周五每天5個時間片安排的課程.比較圖1和圖2可以看出：在沒有沖突的情況下，基本蟻群算法在課程分布上比較均勻；而改進的蟻群算法盡量把課程集中在一個教室，這樣可以空出其他教室作為自習(xí)室或社團活動室，滿足教室資源的合理利用.

圖3是以班級為單位生成的課表，矩陣表示的是周一到周五5個時間片所使用的教室情況.從圖3可以看出：基本蟻群算法中，班級1在相鄰時間片占用15231、15221兩個多媒體教室和兩個機房15252和23062；改進的蟻群算法中，班級1在相鄰的時間片占用一個多媒體教室15221和一個32062機房；班級2情況類似.由以上知改進的蟻群算法減少了學(xué)生的課間流動性，有利于改善教學(xué)秩序.

圖1 ACS算法的教室排課表(教室編號6和7)

圖2 改進的蟻群算法的教室排課表(教室編號6和7)

(a)基本蟻群算法的班級編號為1和2的排課表 (b)改進蟻群算法的班級編號為1和2的排課表

圖4為兩種算法隨迭代次數(shù)的增加而生成的最優(yōu)解的變化曲線圖.由圖4也可以看出，隨著迭代次數(shù)的增加，兩種算法都收斂，其中改進的蟻群算法在迭代次數(shù)30～40之間的效果最好，這與所選數(shù)據(jù)的規(guī)模有關(guān).

表1給出了兩種算法最優(yōu)值的對比數(shù)據(jù)(單位：座位數(shù)).從圖4可以看出，迭代次數(shù)在35左右時的效果最好，所以對比數(shù)據(jù)的迭代次數(shù)選為35次.結(jié)果表明，改進的蟻群算法權(quán)值更低，得到了更優(yōu)解.

圖4 兩種算法的迭代次數(shù)和最短距離的對比曲線

表1 兩種算法的最優(yōu)值的對比

4 結(jié)論

本文實驗結(jié)果表明,改進的蟻群算法能夠滿足硬性約束，未出現(xiàn)教室沖突或教室類型不匹配現(xiàn)象，達到了優(yōu)化的目的.通過在邊的權(quán)值優(yōu)化方面加以改進，可保證學(xué)生人數(shù)少的課程盡量占用容量小的教室，也可解決大部分連續(xù)兩節(jié)課之間的教室距離問題、單雙周課程安排問題；本文的研究對教室資源有限的高校教室管理有一定的應(yīng)用價值.本文的算法只針對教室管理進行了優(yōu)化，課元的上課時間預(yù)先給定，沒有考慮時間沖突，下一步的工作將主要解決排課問題的時間沖突，對蟻群算法信息素做進一步改進，以提高算法效率.

參考文獻：

[1] 侯文靜，馬永杰,張燕，等.求解TSP的改進蟻群算法[J].計算機應(yīng)用研究,2010,27(6):2087-2089.

[2] 崔旭,崔榮一,金小峰，等.基于時間資源的大學(xué)排課問題研究[J].延邊大學(xué)學(xué)報：自然科學(xué)版,2006,32(4):256-258.

[3] 詹亞坤.基于模擬退火算法的高校排課系統(tǒng)研究[D].東北師范大學(xué),2012.

[4] 王鳳，林杰.高校排課問題的圖論模型及算法[J].計算機工程與應(yīng)用,2009,45(27):240-242.

[5] 景雪琴,朱玉芳,杜棟，等.從排課表到教室調(diào)度表的設(shè)計與實現(xiàn)[J].計算機應(yīng)用與軟件,2004,21(2):123-125.

[6] 余斌,謝昕.基于減小教室流動性的排課算法研究[J].計算機時代,2004(2):22-24.

[7] 倪慶劍,邢漢承,張志政.蟻群算法及其應(yīng)用研究進展[J].計算機應(yīng)用與軟件,2008,25(8):12-15.

[8] 池元成，蔡國飆.基于蟻群算法的多目標(biāo)優(yōu)化[J].計算機工程,2009,35(15):168-169.

[9] Thomas Stützle, Holger H Hoos. MAX-MIN ant system[J]. Future Generation Computer Systems, 2000,16(8):889-914.

[10] 何小虎.優(yōu)化蟻群算法在排課中的應(yīng)用策略[J].計算機與數(shù)字工程,2012,40(7):33-35.

[11] Broderick Crawford, Ricardo Soto. A Max-Min ant system algorithm to solve the software project scheduling problem[J]. Expert Systems with Applications, 2014(41):6634-6645.

[12] 吳小娟,呂強.新蟻群算法模型在大學(xué)課程時間表問題中的應(yīng)用[J].計算機應(yīng)用與軟件,2009,26(6):80-83.

[13] Christian Blum. The Hyper-Cube framework for ant colony optimization[J]. IEEE Transactions on Systems Man, and Cybernetics Cybernetics-part B:Cybernetics, 2004,34(2):1161-1171.

[14] Li Zhiyong, Wang Yong, Dai Yun, et al. The cloud-based framework for ant colony optimization[C]//Proceedings of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Computation. Shanghai, 2009:279-286．