基于改進(jìn)的蟻群算法的教室管理優(yōu)化問(wèn)題

懷麗波，崔榮一，趙亞慧

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

0 引言

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

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

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

1.1 教室管理問(wèn)題優(yōu)化要點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

2.2 針對(duì)教室管理問(wèn)題改進(jìn)的蟻群算法

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

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

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

(3)

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

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

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

τ∈[τmin,τmax],

(4)

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

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

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

step 2N∶=N+1；

step 3 當(dāng)N

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

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

step 6 計(jì)算螞蟻k的路徑長(zhǎng)度Lk，通過(guò)比較其大小求得最短長(zhǎng)度Lbest和最長(zhǎng)長(zhǎng)度Lworst；

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

圖2 改進(jìn)的蟻群算法的教室排課表(教室編號(hào)6和7)

(a)基本蟻群算法的班級(jí)編號(hào)為1和2的排課表 (b)改進(jìn)蟻群算法的班級(jí)編號(hào)為1和2的排課表

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

[8] 池元成，蔡國(guó)飆.基于蟻群算法的多目標(biāo)優(yōu)化[J].計(jì)算機(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].計(jì)算機(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] 吳小娟,呂強(qiáng).新蟻群算法模型在大學(xué)課程時(shí)間表問(wèn)題中的應(yīng)用[J].計(jì)算機(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．