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

唐 環(huán),高 健

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

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

唐 環(huán),高 健

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

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

模擬退火; 排課問(wèn)題; 人工智能

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

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

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

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

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

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

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

1 排課問(wèn)題的模型及模擬退火算法

1.1 排課問(wèn)題的模型及模擬退火算法

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

硬約束:

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

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

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

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

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

軟約束:

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

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

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

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

1.2 模擬退火算法

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

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

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

1.2 排課問(wèn)題的模型及模擬退火算法

(1)基礎(chǔ)方案

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

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

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

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

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

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

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

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

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

2.2.1 劃分班級(jí)

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

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

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

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

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

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

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

2.2.2 生成帶有沖突的課表

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

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

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

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

(1)退火第一階段

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

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

Step3.令 k=1;

Step4.令 i=1;

Step5.對(duì)于 lk和獲取滿足

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

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

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

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

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

(2)退火第二階段

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

(3)退火第三階段

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

Step1.隨機(jī)獲取一個(gè)班級(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í)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

4 排課系統(tǒng)

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

4.1 前端顯示模塊

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

圖2 前端顯示

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

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

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

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

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

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

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

4.3 后臺(tái)處理模塊

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

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

5 結(jié)束語(yǔ)

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

圖4 后臺(tái)處理結(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é)報(bào)(自然科學(xué)版),2005,22(1):35–38.

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

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

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

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

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

9姜謙.中小學(xué)排課系統(tǒng)的研究與設(shè)計(jì)[碩士學(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è)計(jì)與實(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é)排課問(wèn)題中實(shí)用的模擬退火算法應(yīng)用.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(10):225–230.http://www.c-s-a.org.cn/1003-3254/6059.html

2017-02-11; 采用時(shí)間:2017-03-22