唐 環(huán),高 健

(上海大學(xué) 機(jī)電工程與自動化學(xué)院,上海 200072)

在中學(xué)排課問題中實(shí)用的模擬退火算法應(yīng)用①

唐 環(huán),高 健

(上海大學(xué) 機(jī)電工程與自動化學(xué)院,上海 200072)

針對中學(xué)排課問題,提出了一種分階段的模擬退火算法解決方案.中學(xué)排課問題難點(diǎn)主要在于如何解決課表中存在的大量沖突以及如何優(yōu)化課表.初始化隨機(jī)生成一張帶有沖突的課表,經(jīng)過算法第一階段,人工干預(yù)異化解結(jié)構(gòu),使課表可行; 算法第二階段引導(dǎo)性的改變課表結(jié)構(gòu)使課表滿足通用的軟約束條件; 算法第三階段采用啟發(fā)式隨機(jī)鄰域異化操作,變異課表,產(chǎn)生更優(yōu)解.為了滿足實(shí)際生產(chǎn)環(huán)境中對課表多元化的需求,在UI界面中提供可以手動調(diào)節(jié)課表機(jī)制.經(jīng)過實(shí)驗發(fā)現(xiàn),改進(jìn)后的模擬退火算法在解決中學(xué)排課問題時收斂速度更快,運(yùn)行效率更高,并且在迭代次數(shù)較少的情況下,也能產(chǎn)生可行解.

模擬退火; 排課問題; 人工智能

學(xué)校的排課工作是教學(xué)管理任務(wù)的重要環(huán)節(jié)之一,同時也是耗時耗力較多的一項工作.傳統(tǒng)的排課工作大多由經(jīng)驗豐富的教務(wù)人員進(jìn)行手工編排,這種人工排課會導(dǎo)致排課效率低、效果差.為了優(yōu)化排課質(zhì)量、充分提高學(xué)生學(xué)習(xí)效率、推進(jìn)學(xué)校信息化辦公教育,利用計算機(jī)實(shí)現(xiàn)自動排課已經(jīng)成為必不可擋的趨勢.

排課問題早在20世紀(jì)50年代末,國外學(xué)者便對其展開研究.1976年,排課問題被證明是一個NP完全問題[1].這一論證奠定了求解排課問題的理論基礎(chǔ),學(xué)者們不再去刻意追求排課問題的最優(yōu)解,轉(zhuǎn)而采用相適應(yīng)的啟發(fā)式算法[2]求得排課問題的較優(yōu)解.

現(xiàn)階段,解決排課問題的方法主要有基于圖論算法[3]、遺傳算法[4,5]、模擬退火算法[6]、回溯法[7]、蟻群算法[8].然而這些研究主要針對大學(xué)課表,中學(xué)排課問題有其獨(dú)有的特點(diǎn)及難點(diǎn):

(1)為了保證中學(xué)學(xué)校的教學(xué)計劃,對于學(xué)生和教室而言,中學(xué)課表一般都處于飽和狀態(tài),容易引起沖突,而大學(xué)生課表則相對自由;

(2)中學(xué)課表問題中每個班級安排的年級課程固定,而在大學(xué)課堂上各個教室可以分配不完全相同的教學(xué)任務(wù),甚至可以混合多個年級的課程,因此中學(xué)教室的靈活性差;

(3)中學(xué)對課表質(zhì)量要求較高,根據(jù)課程性質(zhì)的不同安排不同的課時,且特殊課程安排在指定的時間較為妥當(dāng)(如體育課安排在下午最后的課時),從而保證學(xué)生在上其他課程時有良好的學(xué)習(xí)狀態(tài);

(4)中學(xué)會區(qū)分班主任老師,每個班級至少需要一名班主任老師任課,并且一名班主任老師同時只能在一個班級任職班主任.

1 排課問題的模型及模擬退火算法

1.1 排課問題的模型及模擬退火算法

根據(jù)學(xué)校教學(xué)計劃,將一個年級所有班級一周的時刻表在一個平面上展開,用 (ci,lj)表示平面上的單元格,即第i個班級第j節(jié)課時,用C表示所有班級的集合,L表示一周內(nèi)上課的課時集合,則設(shè)所有老師的集合為T,排課的實(shí)質(zhì)就是向所有的(ci,lj)單元格中填且僅填入一位老師并且保證課程表在完全滿足所有的硬約束的條件下,盡量滿足軟約束條件.其中硬約束和軟約束條件歸納如下[9].

硬約束:

(1)全體老師必須完成教學(xué)計劃中的所有課時,即課程表不能有空缺單元格;

(2)同一位老師不能在相同的課時在不同的班級同時有教學(xué)任務(wù);

(3)一個班級不能安排不同的老師上同一門課程;

(4)一個單元格只能安排一位老師;

(5)班主任數(shù)目必須與班級數(shù)目相等,且各班至少分配一名不同的班主任老師任課.

軟約束:

(1)體育課盡量安排在下午的最后兩節(jié)課;

(2)盡量不安排課程連堂上;

(3)不同性質(zhì)的課程,應(yīng)該酌情分配在不同的時間.例如,主干課程盡量安排在上午1、2節(jié)學(xué)習(xí)效率較高的時段.

(4)其他差異性需求,例如:需要課程連堂,部分老師需要固定的時間段等.

1.2 模擬退火算法

模擬退火算法由Kirkpatrick于1983年提出[10],算法主要用于求解大規(guī)模組合優(yōu)化問題,特別是針對NP完全組合優(yōu)化問題的求解.本文基于模擬退火算法的框架,對于排課這種特殊問題,通過改進(jìn)其鄰域結(jié)構(gòu)的產(chǎn)生策略,從而生成一套高效的求解中學(xué)排課問題的方案.

模擬退火算法思路來源于物理學(xué)中的模擬退火冶金時采用的Metropolis準(zhǔn)則,簡而言之,算法的核心思想是隨著迭代次數(shù)的增加,產(chǎn)生較差的解被接受的概率也越來越小,而產(chǎn)生的較優(yōu)解一直被接受.

原始模擬退火算法在求解組合優(yōu)化問題時,采用的是一種高度隨機(jī)產(chǎn)生鄰域結(jié)構(gòu)的策略,算法的迭代次數(shù)較長,收斂較慢.

1.2 排課問題的模型及模擬退火算法

(1)基礎(chǔ)方案

將硬約束條件(2),同一位老師不能同時在不同的班級上課,看成軟約束條件,其他條件保持不變,由此可生成一張中學(xué)課表的解,且該解可能不可行.然后利用模擬退火算法,每次迭代時隨機(jī)選擇同一班級的兩門課時進(jìn)行交換,并按照退火算法中的Metropolis準(zhǔn)則決定是否保留變換之后的課表.

(2)改進(jìn)方案

模擬退火算法的缺點(diǎn)在于過多的迭代次數(shù),算法的效率較低.基礎(chǔ)方案中隨機(jī)挑選交換課時是導(dǎo)致迭代緩慢的根本原因.人工排課過程可描述為先編排出帶有沖突的課表,然后解決沖突,再調(diào)整連堂課時,最后全局調(diào)優(yōu)課表.本文基于人工排課的思想提出一種分階段的課表鄰域變化優(yōu)化策略,有針對性的、目的性的在退火過程中加入“人工干預(yù)”.

2 算法實(shí)現(xiàn)步驟

2.1 衡量排課質(zhì)量的優(yōu)劣

使設(shè)課表S對應(yīng)的代價值為f (S),有:

其中,T 為該年級老師總數(shù); ti表示第 i位老師; 將中學(xué)課程分成7種不同的性質(zhì):語、數(shù)、外、體、文、理、其他,根據(jù)軟約束條件的第(3)條定義二維數(shù)組dc[k][j]表示第k門性質(zhì)的課程被安排在第j課時產(chǎn)生的代價值;i表示該位老師任教的課程性質(zhì)索引號;設(shè)老師已安排的單元格屬性為 arrangeCells,則記老師連堂的單元格屬性則記老師沖突的單元屬性 conflictCells ,則Q1、Q2分別代表連堂和沖突的代價值常數(shù).

當(dāng)f(S)值越小時,則課表S越合理.

2.2 生成初始解并優(yōu)化解

2.2.1 劃分班級

為了滿足硬約束條件中的(3)和(5),可按如下步驟分配老師任課班級:

Step2.若老師 ti為班主任,則其中表示老師ti的任課班級集合.老師ti的任教課程為 COi,若則

Step3.若 ,則返回 Step2 繼續(xù)遍歷老師集合,否則轉(zhuǎn)入下一步;

Step5.對于第k門課程,統(tǒng)計任教該課程的所有老師索引號集合TIL;

Step6.遍歷TIL中老師的CLL集合,生成由Step2產(chǎn)生的對于第k門課程已分配的班級號集合CIL;

Step9.根據(jù)老師的教授班級數(shù)目屬性,對TIL中的老師按照順序分配每位老師的任課班級加入老師的CLL集合中;

Step10.k++,如果 k≤N,則返回 Step5,否則班級分配完成,退出循環(huán).

2.2.2 生成帶有沖突的課表

為了滿足軟約束的第(1)條,可將任教特殊性質(zhì)課程(如體育課)的老師放在老師集合的首位,其他老師按照一周內(nèi)總上課課時數(shù)目從多到少排序.

由上一節(jié)的劃分班級,可以得到每個班級具體由哪些老師授課.為了滿足硬約束條件(1),對于每一位老師,根據(jù)其在每個班級一周上課課時數(shù)目的屬性,分配對應(yīng)數(shù)量的該班級課時,并將所有分配的單元格記錄到對應(yīng)老師的arrangeCells屬性中; 為了滿足硬約束條件(4),設(shè)計一張班級禁忌表,用于判斷該班級的每個課時是否已被分配.對于每個可分配的課時,通過dc[k][j]獲取固定代價值,通過老師一周中已上課的課時weeky屬性決定是否額外添加連堂代價值或沖突代價值,若發(fā)生沖突,則將該老師的 conflictCells屬性不重復(fù)的添加發(fā)生沖突的兩個單元格.通過遍歷老師的arrangeCells屬性,填充二維數(shù)組 sheetInfo[ci][lj],其值表示在 ci班,li課時任課老師索引號.連堂屬性arrangeCells可以由sheetInfo遍歷來獲取.

2.2.3 解決沖突并優(yōu)化課表

模擬退火算法的關(guān)鍵步驟在于改變鄰域結(jié)構(gòu),產(chǎn)生新解,并以不同的概率接受新解.針對中學(xué)排課問題,本文將退火過程分為三個不同的階段,采用三種不同的鄰域異化操作.

(1)退火第一階段

這一階段僅作用于發(fā)生沖突的單元格,改變初始解結(jié)構(gòu),生成可行解.算法步驟如下:

Step2.遍歷教師t所有的單元格,獲取沖突所在的課時集合對應(yīng)沖突課時li所在的班級是所有發(fā)生沖突的班級的集合,與FLL一一對應(yīng);

Step3.令 k=1;

Step4.令 i=1;

Step5.對于 lk和獲取滿足

?lx∈ ALL,sheetInfo[ci][lx]≠ sheetInfo[??ci][lk]

&sheetInfo[??ci][lx]≠ sheetInfo[ci][lk],其中*表示所有班級表示除ci班以外的班級,ALL集合表示在ci班中能與lk交換且不使交換的兩處位置發(fā)生沖突的所有課時集合;

Step6.剔除ALL中包含與特殊性質(zhì)課程交換的課時,再依據(jù)交換后是否與周圍課時連堂而產(chǎn)生額外代價,采用輪盤賭的方式擇優(yōu)選擇一個交換課時,加入備選交換課時集合PY中;

Step8.隨機(jī)選擇PY中的優(yōu)選課時對各班進(jìn)行交換,選擇的個數(shù)為更新sheetInfo以及發(fā)生變化的位置處的老師各個屬性值;

退火第一階段解決了初始化課表中所有發(fā)生沖突的位置,課表的整體代價值必然是減少的,算法也一定會接受這些改變.

(2)退火第二階段

這一階段著力解決存在連堂的單元格,并且保證變化后的解仍為可行解.算法步驟類似于退火第一階段,區(qū)別在于觀察的是老師的屬性.當(dāng)分離了連堂的單元格,課表的整體代價值必然減少,算法也會接受該解; 當(dāng)程序無法分離連堂單元格時,自動轉(zhuǎn)入退火第三階段.

(3)退火第三階段

該階段處于退火的最后一個階段,采用全隨機(jī)方案優(yōu)化課表結(jié)構(gòu),產(chǎn)生代價值更小的解.算法步驟如下:

Step1.隨機(jī)獲取一個班級c,并置是否交換參數(shù)s為假;

Step2.初始化循環(huán)次數(shù)常量N;

Step5.若 s為假則轉(zhuǎn)入 Step6,否則轉(zhuǎn)入 Step7;

Step8.返回退火框架更新優(yōu)解結(jié)構(gòu)、溫度以及迭代次數(shù)信息,判斷是否退出該階段.

本文中模擬退火算法的內(nèi)外層循環(huán)的終止準(zhǔn)則均采用循環(huán)總數(shù)控制法,退火總框架偽代碼如下:

3 數(shù)據(jù)實(shí)驗結(jié)果

本文采用模擬院校數(shù)據(jù):12門課程; 50位老師;15 個班級; 每天上午有 4 節(jié)課,下午有 3 節(jié)課; 每周有六天上課時間,其中周六只安排上午課程,下午不安排課程; 一共需要安排 585 節(jié)課.為了對比的有效性,修改2.2.1節(jié)的Step7,生成列表后不亂序,即保證每次老師被分配到的班級一致,通過控制變量法來比較不同的排課方案在求解中學(xué)排課問題的效率.

實(shí)驗硬件環(huán)境為PC機(jī),配置為Inter(R)Core(TM)i3 CPU,4G RAM; 軟件平臺為 Eclipse Mars.1,數(shù)據(jù)存儲在Mysql數(shù)據(jù)庫中,基于Java語言編程.

表1通過保持其他參數(shù)不變,改變降溫次數(shù)T和迭代步長N,即控制算法的外層和內(nèi)層的循環(huán)次數(shù).經(jīng)過重復(fù)5次實(shí)驗取時間和最優(yōu)解的平均值得到兩種算法實(shí)驗結(jié)果對比表.

表1 兩種算法運(yùn)行效率對比表

由表1中的數(shù)據(jù)可以看出當(dāng)總循環(huán)次數(shù)在100左右時,基礎(chǔ)排課方案很難找到不發(fā)生沖突的課表,而改進(jìn)的分段模擬退火算法可以快速找到可行解; 改進(jìn)的方案較基礎(chǔ)方案在運(yùn)行時間上也有提高; 兩種算法在求得最優(yōu)解結(jié)果上基本保持一致.

取(T,N)=(250,50),橫坐標(biāo)為(T*N),縱坐標(biāo)為總代價值,為便于觀察前期兩種算法迭代結(jié)果的不同,可將橫坐標(biāo)取對數(shù),繪于圖1.

由圖1可以看出本例中基于改進(jìn)方案的模擬退火算法在解決中學(xué)排課問題中收斂速度比基于基礎(chǔ)方案退火算法快接近10倍; 兩種方案最后產(chǎn)生的最優(yōu)解值相近.

圖1 改進(jìn)前后方案尋優(yōu)半對數(shù)曲線圖

4 排課系統(tǒng)

在實(shí)際應(yīng)用中,中學(xué)排課問題的軟約束條件更加復(fù)雜.為了滿足軟約束(4),即多元化的排課需求,本系統(tǒng)基于 SSM(Spring,SpringMVC,Mybatis)框架提供可以和用戶交互的機(jī)制.

4.1 前端顯示模塊

前端利用JQuery編寫數(shù)據(jù)錄入邏輯以及校驗邏輯的代碼.如圖2所示.

圖2 前端顯示

合法性校驗主要包括:班主任數(shù)目=班級數(shù)目; 輸入不為空.

4.2 模擬數(shù)據(jù)模塊

數(shù)據(jù)庫連接池由Spring框架托管,并通過Mybatis框架從后臺服務(wù)器的數(shù)據(jù)庫中調(diào)用一組模擬數(shù)據(jù),自動填充圖2所示的所有表單字段,用于快速模擬排課流程.表單提交至deal.action后臺路徑,由后臺處理并返回至result.jsp頁面中.

4.3 前端調(diào)整模塊

如圖3所示在result.jsp頁面中,鼠標(biāo)懸停單元格以查看教師詳情.利用html5的拖拽特性,允許用戶手動調(diào)整課程單元格,單擊單元格變色固定再次提交后臺處理.

圖3 調(diào)整并固定單元格

圖3 顯示了得到一次后臺處理結(jié)果之后,人為調(diào)整,即將兩節(jié)“吳峰”的語文課程固定.前端記錄調(diào)整信息并提交至后臺change.action,后臺模擬用戶調(diào)整行為,并解決沖突、優(yōu)化課表,最后返回結(jié)果至result.jsp頁面中.重復(fù)以上動作,即可生成帶有人工干預(yù)的個性化課表.

4.3 后臺處理模塊

將前端輸入數(shù)據(jù)字段名稱規(guī)范化,基于SpringMVC框架即可自動將傳入的數(shù)據(jù)轉(zhuǎn)換成POJO,節(jié)省開發(fā)成本[11].

根據(jù)不同的action使用不同階段的模擬退火算法.對于deal.action,應(yīng)用第一階段模擬退火算法生成可行解,應(yīng)用第二階段模擬退火算法指向性優(yōu)化解,應(yīng)用第三階段模擬退火算法隨機(jī)優(yōu)化解; 對于change.action,只使用前兩個階段的模擬退火算法生成并優(yōu)化解,因為第三階段的退火過程會隨機(jī)全局打亂課表,導(dǎo)致調(diào)整后課表其他單元格可能會發(fā)生較大的差異,即用戶為了滿足特殊需求調(diào)整的課表方案無需經(jīng)過退火第三階段處理.如圖4是對圖3調(diào)整后的處理結(jié)果.

5 結(jié)束語

分階段的模擬退火算法在解決中學(xué)排課問題中,根據(jù)當(dāng)前的課表狀態(tài),采用不同的鄰域異化操作,可以快速生成可行課表,全局搜索優(yōu)化課表并達(dá)到收斂.為了滿足對于課表的更多復(fù)雜需求,基于本文中提出的改進(jìn)后的模擬退火算法,設(shè)計了一套完整的可以與用戶交互的系統(tǒng),并投放于生產(chǎn)環(huán)境中.

圖4 后臺處理結(jié)果

1Even S,Itai A,Shamir A.On the complexity of timetable and multicommodity flow problems.SIAM Journal on Computing,1976,5(4):691–703.[doi:10.1137/0205048]

2趙玉新,Yang XS,劉利強(qiáng).新興元啟發(fā)式優(yōu)化方法.北京:科學(xué)出版社,2013.

3張健.基于圖論的高校排課系統(tǒng)實(shí)現(xiàn).重慶師范大學(xué)學(xué)報(自然科學(xué)版),2005,22(1):35–38.

4許琦.基于遺傳算法的高校排課問題的研究[碩士學(xué)位論文].廣州:華南理工大學(xué),2012.

5祝勇仁,曹煥亞.應(yīng)用遺傳算法求解排課問題.計算機(jī)應(yīng)用與軟件,2007,24(12):130–132,141.[doi:10.3969/j.issn.1000-386X.2007.12.051]

6李增智,王云嵐,陳靖.課程表問題的一種混合型模擬退火算法.西安交通大學(xué)學(xué)報,2003,37(4):343–345,350.

7陳本慶,馬永強(qiáng),何虎.改進(jìn)型回溯法在高校排課中的應(yīng)用.成都信息工程學(xué)院學(xué)報,2003,18(2):150–154.

8趙惠怡.基于蟻群算法的排課問題的研究[碩士學(xué)位論文].遼寧:大連海事大學(xué),2007.

9姜謙.中小學(xué)排課系統(tǒng)的研究與設(shè)計[碩士學(xué)位論文].廣州:華南理工大學(xué),2010.

10Kirpatrick S,Gelatt CD,Vecchi MP.Optimization by simulated annealing.Science,1983,220(4598):671–680.[doi:10.1126/science.220.4598.671]

11吳婉楠.基于SpringMVC和MyBatis框架的炒股比賽系統(tǒng)的設(shè)計與實(shí)現(xiàn)[碩士學(xué)位論文].南京:南京大學(xué),2016.

Application of Simulated Anneal Algorithm for Curriculum Schedule Problem in Senior High Schools

TANG Huan,GAO Jian

(School of Mechatronic Engineering and Automation,Shanghai University,Shanghai 200072,China)

A solution of staged simulated annealing is proposed to settle the schedule problem of senior high schools.The difficulty of the problem mainly lies in how to solve lots of conflicts existing in the schedule and how to optimize it.We initialize a schedule with conflicts randomly,and dissimilate the structure of the solution with artificial intervention to make the schedule feasible in the first stage.In the second stage,we try to make the schedule meet general constraints by instructively changing the structure of the schedule.In the third stage,we generate optimized solution through varying the schedule with heuristic dissimilate random field employed.In order to meet the demand for diversified schedule,the actual production environment in the user interface provides the manual adjustment to the schedule.It is found that the improved simulated annealing algorithm has a faster convergence speed,and higher operation efficiency in solving curriculum schedule problem of senior high schools and in the case of less number of iterations,it can also generate a feasible solution.

simulated annealing; curriculum schedule problem; artificial intelligent

唐環(huán),高健.在中學(xué)排課問題中實(shí)用的模擬退火算法應(yīng)用.計算機(jī)系統(tǒng)應(yīng)用,2017,26(10):225–230.http://www.c-s-a.org.cn/1003-3254/6059.html

2017-02-11; 采用時間:2017-03-22