基于改進遺傳算法的高中走班制排課算法

王衛紅，李文瓊

(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

?

基于改進遺傳算法的高中走班制排課算法

王衛紅，李文瓊

(浙江工業大學 計算機科學與技術學院，浙江 杭州 310023)

隨著高考制度的深化改革，“走班制”教學模式逐漸替代傳統的高中教學方式.這種教學模式的啟用，導致影響排課效率的因素和約束條件增多，并且會出現教學資源匱乏的情況.傳統的人工編排課表的方式需要花費工作人員大量的時間，且排出的課表不宜調整，已經無法滿足“走班制”教學體制的排課需求.根據對現有排課算法存在的問題的分析，結合“走班制”高中教學的特殊性，建立了相應的數學模型、分析了“走班制”教學模式下排課算法需要設計的約束條件.基于“走班制”教學模式下學生分層選課的特性，通過將改進的遺傳算法分別運用在學生分組和排課兩個階段對此類排課問題進行求解.實驗結果證明：該改進算法可以有效的解決采用“走班制”教學模式的高中學校排課問題.

“走班制”教學；改進遺傳算法；排課算法

隨著高考制度的深化改革，“走班制”教學模式在各地區逐漸普及.浙江省的部分高中學校采用的“走班制”教學模式，主要指的是分層次教學，即“行政班”學生根據自己的特點和需求選擇不同層次的教學班進行學習的模式，在恰當的分層次教學策略和新型的課堂教學結構的雙重調控下，實現對教學目標及其過程的優化[1-3].“走班制”不再以行政班為單位，是一種不固定班級、不固定教室的流動性教學模式.在這種教學制度下，排課涉及的信息變得更加繁瑣、復雜，導致排課的解集不斷被誘發，手動排課需要花費工作人員大量的時間，排出的課表不宜調整，已經無法滿足教學要求.在這種新型教育模式下的高中學校迫切的需要一種智能、高效的自動排課方式來快速地得到滿足各種排課約束條件的最優可行解.近幾年，國內外學者將不同的算法應用在解決排課問題上，如模擬退火算法[4-5]，遺傳算法[6-10]，最佳個體置換策略[11-12]，整數規劃[13]等，但是這些方法一方面都存在一些缺點，例如：在排課問題的約束條件上考慮的不夠充分，并且，針對采用“走班制”教學模式的學校排課問題設計的約束條件還未被考慮；另一方面，這些算法的提出幾乎都是用來解決傳統教育模式的方案，即同一行政班的課程在該學期固定在同一教室內的非流動性教育模式.因此，傳統的排課問題沒有考慮流動性的班級的概念.

20世紀70年代，排課問題就一直被當做NP完全問題[14]來解決.NP問題是一個涉及多因素的優化組合問題，任意元素的改變都有可能引起“組合爆炸”，作為一種借鑒了自然選擇、變異機制的隨機搜索算法，遺傳算法利用群體搜索技術，可以高效的解決組合優化問題[15-17].鑒于目前的研究狀況及“走班制”教學的特殊性，筆者提出的算法基于對遺傳算法的改進，對以“走班制”教學模式為特點的排課算法進行了研究，設計了相應的數學模型，以及符合“走班制”特色要求的選擇算子、交叉算子、變異算子和適應度函數等.致力于解決“走班制”教育模式特色下的排課問題，使高校的排課體制趨于智能化，從而有效的提高學生學習效率，降低教務管理工作的復雜度，提高高校教育教學計劃完成力度.

1 “走班制”教學模式下的排課問題

1.1 排課問題描述

要解決的難點是在“走班制”的分層教學制度下，對于分層教學的課程，學生根據個人情況對不同層級的課程進行選課.因此，基于“走班制”教學模式下的排課問題無法像傳統行政班級一樣依據固定的學生成員和教室.筆者提出的解決方案是將學生進行分組，組內的每門課程的學生按層級和相關參數劃分多個該課程教學班，在該分組的基礎上為每組制定不同的課表.因此，“走班制”教學模式下的排課問題，即如何對時間、教師、教室、課程以及組內和組間的流動教學班等5 個因素進行最優化組合規劃的問題，即保證課程安排中盡量少的沖突出現，并解決學校嚴重的資源沖突問題.

1.2 數學建模

根據上述問題描述，排課問題中涉及到教學班、課程、教師、教室和時間等相互制約的因素，用到的集合：

學生集：S={s1,s2,s3,…，sm}，課程集：C={c1,c2,c3,…，cn}，任課教師集：T={t1,t2,t3,…，tp}，時間段集：P={p1,p2,p3,…，pq}，教室集：R={r1,r2,r3,…，rt}，時間段Pi={(px,py)}，一周可供排課天數daysPerWeek，一天可供排課課時數periodPerDay，x屬于daysPerWeek，y屬于periodPerDay，i=(x-1)periodPerDay+y.

“走班制”模式的排課過程沒有“行政班”的概念，基于學生選課情況對學生按選課情況進行分組形成不同的教學班，其中教學班、教師和課程作為一個授課安排，教室、時間段作為一個教室時間安排，因此排課問題可以演化成為任意授課安排尋找滿足約束條件的教室-時間對問題.

排課問題就是在保證合理的分配教學資源的情況下，將教師、學生和課程在不同的時間段下按照特定的約束規則進行優化組合.因此在解決排課問題時，需要為算法設計一些約束規則，確保課表達到有效性的同時具有實用性和合理性.

硬約束條件為在解決排課問題時必須遵守的原則，排課算法只有在符合硬約束條件的要求下得到的解集才能避免課表在時間、空間上發生的沖突.筆者設計的基于“走班制”條件下的排課規則需要考慮到分組和排課兩個階段.具體如下：

1) 由于一個學生對于不同的課程可以選擇不同的層級，因此，設計同一個教學時間段，在同一組內的學生不能上一門以上的課程.

2) 同一個時間段的各個課程組安排的課程不能相同.

3) 同一個教學時間段，一個教師不能上一門以上的課程.

4) 同一個教學時間段，一個學生不能上一門以上的課程.

5) 同一個教學時間段，一個學生不能分配在一個以上的組內.

6) 同一個教學時間段，一個教室不能上一門以上的課程.

7) 教室的座位量不能少于被安排的教學班的人數.

軟約束條件為在實際的排課過程中，根據不同的排課對象的特殊性制定的優化條件，在解決排課問題時是否遵守了軟約束條件將會給排課結果帶來很大的影響，排課算法多大程度符合軟約束規則，便會得到相應程度優質的解.具體如下：

1) 一門課程的多次上課時間段的分配盡量均勻.

2) 一個學生的所有課程分布不應過度集中，避免某段時間過于空閑.

3) 上課教室的座位數和上課的教學班的人數相差適中，保證教室的利用率.

4) 同一個教師的相近時間段的教學盡量安排在相對固定的教室或相近教室.

5) 藝體課程應避免安排在早上和下午的一、二節次.

6) 邏輯性強的課程盡量安排在教學效果好的上課節次.

7) 公共課及學時多的課應優先安排.

8) 每個教學班的人數不宜過少也不宜過多.

9) 對于上課時間確定的教師，首先確保滿足其上課時間.

10) 對學生分組的組數要盡量小于需要進行教學分層的課程數量.

將軟、硬約束寫入課程的基因中，減少遺傳操作中無效課表產生的比例，提高有效課表的合理性.

2 算法設計

2.1 基因編碼

自然界里的物種遺傳由染色體決定，不同的染色體決定不同物種之間存在的差異，而每種物種特有的遺傳信息存放在染色體內，遺傳信息按一定的模式排列，即進行了遺傳編碼.以實施了“走班制”教學模式的某高中學校為例，設計了一組適合該校特定情況的基因編碼方式.排課得到的課表作為一條染色體，課表中的信息(排課記錄)作為染色體上不同的基因.以總教學時間段數為行數，以已經被分配教師和課程的教學班數(各組教學班總數)為列數，組成二維表，在表內非空單元放入教室編號.涉及的排課信息采用二進制編碼方式表示，染色體編碼方案如圖1所示.

圖1 染色體編碼方案Fig.1 Chromosome coding scheme

2.2 排課問題約束滿足模型

針對這些硬約束條件建立一些數學約束模型，從而保證進行智能課表編排時教學資源、對象不產生沖突.

1) 在排課結果集中排課信息不能重復，由時間段和教室組成的教學單位組成的集合，如果時間和教室都不同，才保證由它們組成的教學單位不同，數學表示如下：

設pi∈P，pj∈P，rλ∈R，rγ∈R，vα∈V，vβ∈V

則vα=〈pi，rλ〉，vβ=〈pj，rγ〉

規定：當pi≠pj，且rλ≠rγ時，必有vα≠vβ.

2) “走班制”模式下教學班的課程和學生固定，因此將教學班gc和教師t的組合作為一個待排課任務集，所以由教學班和教師組成的排課對象列表TT中，排課任務集不能重復.筆者設計的解決方案中，組內各課程保證每個層級教學班有唯一與之對應的教師，因此，組內教學班和教師都不同，組成的排課任務集才不同，數學表示如下：

設gci∈GC，gcj∈GC，gx∈G，gy∈G，ttλ∈TT，ttγ∈TT

則ttλ=〈gci，gx〉，ttγ=〈gcj，gy〉

規定：當gci≠gcj，且gx≠gy時，滿足ttλ≠ttγ.

3) 一個教學班在同一時間段不能分配在一個以上的教室，數學表示如下：

設{ri，rj}∈R，{pλ，pβ}∈P且ttο=〈gcК，gx〉，ttυ=〈gcη，gy〉

當rλ≠rγ，gcК≠gcη，pi≠pj時，滿足ttο≠ttυ.

4) 層級課程的授課教師是固定的，組內排課是同一時間只針對一門課安排教學單元，要保證一個授課教師在同一教學單元只對一個教學班進行授課.數學表示如下：

設{gx，gy}∈G，{gcК，gcη}∈GC且vα=〈pi，rλ〉，vβ=〈pj，rγ〉，

ttο=〈gcК，gx〉，ttυ=〈gcη，gy〉

當gcК≠gcη，pi=pj，gx≠gy時，ttο≠ttυ.

5) 每門課程在某層級安排的教師是固定的人員，為了避免資源沖突，要求在同一時間段內，教學組間的課程類別各不相同.數學表示如下：

設{gtК，gtρ}∈GT，lυ=〈gtК，cλ，pi〉，lρ=〈gtη，cγ，pj〉

如果lυ=lρ，則要求gtК=gtη，cλ=cγ，pi=pj.

2.3 設計適應度函數

基于上述建立的數學模型，提出了將“走班制”下的排課問題拆分為分組、排課兩部分來解決排課問題的算法設計，該算法以基本遺傳算法為基礎，并將其應用在分組和排課兩個階段，重點描述排課階段的設計.該排課算法設計的適應度直接影響該算法是否能解決排課問題中的資源沖突和找到組合規劃最優解.排課問題作為多組合目標規劃問題，受到多個約束條件的影響，如：各個課程在教學時間段分配的均勻度、學生課程安排均勻度、教室資源利用率以及課程時間段安排優度等，將這些約束條件的綜合評價作為筆者算法的適應度函數，表示為

(1)

式中：crashg為該種群個體的沖突次數；rewardg為該種群個體的獎勵指數；uλi為在第λ教學組中第i個課程的教學時間段分配均勻度；nteam為分組組數；ngcourseλ為第λ教學組內分層后課程總數.統計該課程在其組內的教學時間段分配記錄tcourseλi={tcourse1, tcourse2, tcourse3,…, tcoursentime}，ntime表示該課程被分配的教學時間段總數.課程在教學時間段分配的均勻度為

(2)

式中dαβ為課程的第α個教學時間段到第β個教學時間段的距離.具體如下：

1) 用vλj表示在第λ教學組中第j個學生的課程安排均勻度，ngstuλ表示第λ教學組內學生總數.“走班制”教學下采用的是流動式教學班，班級內的學生不固定，因此上課時間段均勻度細化到每個學生，統計學生一周內每天上課的次數，計算方差，其值越小，安排效果越好.學生上課時間段的分配均勻度為

(3)

2) 用wλ表示課程時間段安排優度，不同課程之間或者不同層級的課程之間的邏輯強度、重要程度都不同，不同教學時間段的教學效果不同，課程節次的安排優度為

(4)

式中：courseweightυω為第ν個課程在第ω個教學時間段的教學效果權重；ngcourse為該教學組課程總數；ppd為一天內教學時間段個數.

3) 用rλ表示教室資源利用率，在一次教學安排中，一間教室內分配的教學班學生數過少會浪費教室資源，與該教室容量過度相近則會影響教學質量，將教學班學生個數與教室容量的比值作為資源利用率的衡量標準，并設置當其值為0.8時，資源利用率為最佳[9].組內資源利用率為

(5)

式中：nclass為該教學組內教學班數量；nroom為該教學組內教室數量；nstuclassi為第i個教學班學生個數；nsturoomj為第j個教室容量.

2.4 初始種群的產生

以教學組為單位，首先同時為每個教學組內已分配課程和教師的教學班分配教學時間段，以教學時間段為行，以教學班為列生成一個二維表.采用隨機生成的方式，為每個教學班在各個時間段上分配教室，若教室、教師和時間資源不產生沖突，則將教室編號填入二維表非空單元，一個完整的二維表則表示一個排課方案，作為排課算法初始種群中的一條染色體.產生n條染色體則形成一個初始群.

2.5 選擇算子

排課算法中，選擇操作是基于適應度進行優勝略汰的過程.算法根據種群中每個個體的適應度大小，保留第g代中優越的候選解進入第g+1代，放棄其他一些非優的候選解.其中個體適應度越大，個體基因的優值越高，被遺傳到下一代種群的概率就越高.為了避免在此過程中出現的種群早熟早收斂現象，算法在選擇操作時引入了競爭機制的同時采用了是輪盤賭算法.具體操作：找到g代種群中最大獎勵值和最大適應度值，調用輪盤賭算法方法，首先以輪盤安置方式按種群適應度降序排列，設置隨機值r，采用二分查找的方式查找r在輪盤中對應位置設為id，該位置為要選擇的染色體位置.

2.6 交叉算子

在交叉操作過程中，通過將第g代種群中所有個體隨機的進行兩兩配對，產生更高效、合理的新個體解.為解決傳統遺傳算法在交叉操作時用來作為搜索解的空間相對較小的問題，采用計算編碼間的海明距離的方式，使得每兩對個體都有部分染色體相互交換，產生新個體，保持群體的多樣性，從而提高了種群變化的效率，避免早熟現象.具體操作：針對每個個體進行交叉操作預測，產生隨機值rd，根據選擇操作中計算的種群最大適應度、參數、該染色體的適應度計算交叉概率，若rd小于交叉概率則進行交叉操作，并通過輪盤賭法找到與當前染色體進行交叉操作的位置，實現交叉操作.需要說明的是，這里的交叉操作為兩個個體中同一個課程組的課表進行交叉操作，取當前個體課表優先安排，另一個課表先安排無沖突的課程，有沖突的課程隨機安排在無課的時間段.

2.7 變異算子

變異操作作為算法產生新個體的輔助方法，將個體染色體的部分基因編碼隨機交換，達到產生新個體的目的.為了擴大了遺傳算法中搜索區域的范圍，同時提高了種群變化的效率以及種群最優解搜索能力，變異概率的設置與交叉概率類似，采用自適應方式.種群中染色體的基因編碼(課程信息)以自適應的概率變異，若變異則隨機一個課程時間段安排與之交換.

3 實例驗證

實驗數據來自浙江省寧波市鄞州中學實行了“走班制”教學模式的高中學校2015—2016(2)學期高二年級的實際教學活動數據.實驗數據包括教師、教室、學生、分層課程、一周時間段(該校每周上課5 天，一天9 節課，即一天9 個時間段，一周為45 個時間段)、班級最大人數、最少人數以及軟硬約束條件等信息，其中每組最少100 人，最多120 人，教學班最少20 人，最多40 人.實驗環境：Visual Studio 2015，C++，SQLServer.

根據筆者對改進遺傳算法設計的描述，排課過程中控制參數的設計切實影響算法的效率.排課算法的控制參數描述如下：

1) 種群規模，符號表示Population，種群規模對算法效率有著一定的影響，規模較小會導致算法求解目標值波動較大，無法反映出對各個目標的優化；規模過大不僅會延長目標收斂時間而且導致內存消耗過盛.設置種群規模為300.

2) 算法遺傳代數，n=3 000，N值影響算法求解目標的收斂性和最優解求解范圍，N值過大導致各目標不收斂；較小時導致最優解極大可能不是最優解.

3) 選擇率，設計個體的選擇率是由該個體在當代種群中的適應度值與所有個體適應度總和的比例值，公式為

(6)

式中：fitg[i]為個體i在第g代種群中的適應度大小；fit.back()為存放種群個體的適應度總和.

4) 交叉概率，交叉概率的大小直接影響算法最優解的收斂程度，概率設置過大導致算法求解過程中解的波動范圍過大，設置的太小導致算法收斂緩慢，交叉概率pc初始值設置為0.02，執行交叉操作時自適應交叉概率為

(7)

式中：fitmax為最大適應度值；fitg[i]為個體當代種群中的適應度大小.

5) 變異概率，變異概率設置太大導致解的范圍波動過大，設置過小引發全局最優解收斂過緩慢，一般其值取0.001～0.2之間，變異概率設置初始值pm為0.01.

實驗的分組結果：由于科目繁多，僅以語文、物理、化學、地理和歷史等5 門課程作為代表，展示這5門課程的分組結果，如表1所示.

表1 分組結果

Table 1 Grouping result

組號教學班語文物理化學地理歷史0語文1物理A1物理A2化學A1化學A2地理A1地理A2歷史A1歷史A2語文2物理B1化學B1化學B2地理B1歷史B1語文3物理C1化學C1地理C1歷史C11語文1物理A1物理A2化學A1地理A1地理A2歷史A1語文2物理B1化學B1化學B2地理B1歷史B1歷史B2語文32語文1物理A1化學A1地理A1地理A2歷史A1歷史A2語文2物理B1物理B2化學B1化學B2地理B1歷史B1語文3

向讀者展示第一組、第二組的排課結果，分別如表2，3所示.

表2 第一組排課結果

Table 2 The timetable of the first group

組號周一周二周三周四周五1歷史A1(教學樓201)歷史A2(教學樓210)歷史B1(教學樓203)歷史C1(教學樓106)數學1(教學樓301)數學2(教學樓302)數學3(教學樓203)數學1(教學樓201)數學2(教學樓301)數學3(教學樓306)信息1(科藝樓203)信息2(科藝樓205)信息3(科藝樓211)化學A1(教學樓403)化學A2(教學樓401)化學B1(教學樓402)化學B2(教學樓405)化學C1(教學樓410)2語文1(教學樓101)語文2(教學樓112)語文3(教學樓201)通技1(科藝樓301)通技2(科藝樓303)通技3(科藝樓306)藝術1(科藝樓401)藝術2(科藝樓410)藝術3(科藝樓403)英語1(教學樓101)英語2(教學樓102)英語3(教學樓110)物理A1(教學樓304)物理A2(教學樓410)物理B1(教學樓405)物理C1(教學樓302)3英語1(教學樓102)英語2(教學樓108)英語3(教學樓203)政治A1(教學樓102)政治A2(教學樓104)政治B1(教學樓305)政治C1(教學樓311)英語1(教學樓103)英語2(教學樓101)英語3(教學樓104)物理A1(實驗樓201)物理A2(實驗樓203)物理B1(實驗樓210)物理C1(實驗樓207)生物A1(教學樓307)生物A2(教學樓206)生物B1(教學樓209)4通技1(科藝樓303)通技2(科藝樓307)通技3(科藝樓305)體育1(體育小管)體育2(體操管)體育3(足球場)政治A1(教學樓201)政治A2(教學樓310)政治B1(教學樓207)政治C1(教學樓203)化學A1(教學樓403)化學A2(教學樓401)化學B1(實驗樓102)化學B2(實驗樓105)化學C1(實驗樓110)政治A1(教學樓101)政治A2(教學樓110)政治B1(教學樓301)政治C1(教學樓303)5體育1(體育小館)體育2(體操管)體育3(足球場)歷史A1(教學樓210)歷史A2(教學樓201)歷史B1(教學樓104)歷史C1(教學樓106)地理A1(教學樓106)地理A2(教學樓204)地理B1(教學樓202)地理C1(教學樓311)語文1(教學樓101)語文2(教學樓110)語文3(教學樓103)6生物A1(實驗樓301)生物A2(實驗樓310)生物B1(實驗樓309)語文1(教學樓101)語文2(教學樓110)語文3(教學樓203)化學A1(教學樓402)化學A2(教學樓405)化學B1(教學樓403)化學B2(教學樓401)化學C1(教學樓410)數學1(教學樓201)數學2(教學樓302)數學3(教學樓306)7數學1(教學樓201)數學2(教學樓302)數學3(教學樓203)信息1(科藝樓203)信息2(科藝樓205)信息3(科藝樓210)歷史A1(教室樓201)歷史A2(教學樓205)歷史B1(教學樓105)歷史C1(教學樓107)政治A1(教學樓103)政治A2(教學樓111)政治B1(教學樓301)政治C1(教學樓310)數學1(教學樓302)數學2(教學樓310)數學3(教學樓203)8物理A1(教學樓304)物理A2(教學樓410)物理B1(教學樓405)物理C1(教學樓302)地理A1(教學樓303)地理A2(教學樓106)地理B1(教學樓311)地理C1(教學樓202)語文1(教學樓201)語文2(教學樓210)語文3(教學樓303)藝術1(科藝樓401)藝術2(科藝樓405)藝術3(科藝樓410)地理A1(教學樓211)地理A2(教學樓304)地理B1(教學樓308)地理C1(教學樓209)9地理A1(教學樓202)地理A2(教學樓303)地理B1(教學樓106)地理C1(教學樓108)化學A1(實驗樓111)化學A2(實驗樓102)化學B1(教學樓401)化學B2(教學樓403)化學C1(教學樓407)物理A1(教學樓303)物理A2(教學樓304)物理B1(實驗樓203)物理C1(實驗樓207)生物A1(教學樓301)生物A2(教學樓310)生物B1(教學樓209)英語1(教學樓102)英語2(教學樓107)英語3(教學樓210)

表3 第二組排課結果

Table 3 The timetable of the second group

組號周一周二周三周四周五1物理A1(教學樓204)物理A2(教學樓202)物理B1(教學樓105)物理A1(教學樓201)物理A2(教學樓210)物理B1(教學樓101)歷史A1(教學樓201)歷史B1(教學樓203)歷史C1(教學樓106)地理A1(教學樓307)地理A2(教學樓301)地理B1(教學樓303)2數學1(教學樓201)數學2(教學樓302)數學3(教學樓306)語文1(教學樓101)語文2(教學樓112)語文3(教學樓201)數學1(教學樓306)數學2(教學樓302)數學3(教學樓210)地理A1(教學樓206)地理A2(教學樓210)地理B1(教學樓302)歷史A1(教學樓210)歷史B1(教學樓203)歷史C1(教學樓106)3生物A1(教學樓205)生物A2(教學樓303)生物B1(教學樓308)體育1(體育小館)體育2(體操管)體育3(足球場)物理A1(教學樓304)物理A2(教學樓410)物理B1(教學樓303)信息1(科藝樓203)信息2(科藝樓207)信息3(科藝樓211)數學1(教學樓201)數學2(教學樓301)數學3(教學樓306)4地理A1(教學樓202)地理A2(教學樓310)地理B1(教學樓304)政治A1(教學樓101)政治B1(教學樓305)政治B2(教學樓303)化學A1(教學樓403)化學B1(教學樓402)化學B2(教學樓405)政治A1(教學樓103)政治B1(教學樓301)政治B2(教學樓310)體育1(體育小館)體育2(體操管)體育3(足球場)5語文1(教學樓110)語文2(教學樓208)語文3(教學樓106)化學A1(實驗樓110)化學B1(實驗樓102)化學B2(實驗樓105)英語1(教學樓102)英語2(教學樓110)英語3(教學樓205)藝術1(科藝樓401)藝術2(科藝樓405)藝術3(科藝樓403)6藝術1(科藝樓405)藝術2(科藝樓403)藝術3(科藝樓410)英語1(教學樓102)英語2(教學樓107)英語3(教學樓203)語文1(教學樓106)語文2(教學樓110)語文3(教學樓103)英語1(教學樓203)英語2(教學樓102)英語3(教學樓110)政治A1(教學樓106)政治B1(教學樓311)政治B2(教學樓303)7化學A1(教學樓402)化學B1(實驗樓102)化學B2(實驗樓110)歷史A1(教學樓101)歷史B1(教學樓106)歷史C1(教學樓207)地理A1(教學樓206)地理A2(教學樓108)地理B1(教學樓202)化學A1(教學樓410)化學B1(教學樓401)化學B2(教學樓402)生物A1(實驗樓301)生物A2(實驗樓302)生物B1(實驗樓310)8英語1(教學樓203)英語2(教學樓110)英語3(教學樓104)通技1(科藝樓301)通技2(科藝樓310)通技3(科藝樓304)通技1(科藝樓305)通技2(科藝樓307)通技3(科藝樓306)數學1(教學樓211)數學2(教學樓310)數學3(教學樓203)物理A1(實驗樓201)物理A2(實驗樓203)物理B1(實驗樓210)9政治A1(教學樓103)政治B1(教學樓301)政治B2(教學樓310)數學1(教學樓301)數學2(教學樓304)數學3(教學樓206)生物A1(教學樓301)生物A2(教學樓310)生物B1(教學樓209)語文1(教學樓201)語文2(教學樓210)語文3(教學樓103)信息1(科藝樓201)信息2(科藝樓207)信息3(科藝樓211)

實驗結果證明：通過筆者設計的排課算法，可以為實行“走班制”教學模式下的高中學校制定合理、高效的課表.

4 結 論

目前國內外學者對傳統排課設計了很多算法，而針對“走班制”教學模式設計的排課算法卻沒有，筆者對傳統遺傳算法進行研究后，采取了一定的改進措施，研究、設計適應以“走班制”教學為特色的排

課算法.雖然筆者設計的算法可以使教學管理者從繁瑣、復雜的教務勞動中脫離出來，能夠盡可能的提高教學效率，并且將學校教學資源盡可能的不被浪費，但是算法依然存在不足之處，希望在以后的研究中有所改進.

[1] 黃文濤.高中選課走班制教學的實踐與思考[J].教育科學論壇,2014(4):22-23.

[2] 王開香.探析分層走班制的應用態、實然態和必然態[J].教育探索,2012(1):72-74.

[3] 鄒冬梅,高軒.基于培智學校學生特點的“走班制”教學路徑[J].現代特殊教育,2013(11):42-44.

[4] 吳紅艷.淺談遺傳退火算法在高校排課問題中的應用[J].科技展望,2015(2):256-258.

[5] LIU Yongkai，ZHANG Defu，LEUNG S C H. A simulated annealing algorithm with a new neighborhood structure for the timetabling problem[C]//Proceedings of the 1st ACM/SIGEVO Summit on Genetic and Evolutionary Compu-tation. London: William Langdon,2009:381-386.

[6] KOHSHORI M S，LIRI M S. Multi population hybrid genetic algorithms for university course timetabling[J]. Interna-tional journal for advances in computer science，2012，3(1)：12-22.

[7] 孫彤,郭倩倩.基于新型免疫遺傳算法的高校排課仿真研究[J].計算機仿真,2012,29(2):386-391.

[8] 馬玉芳,張海娜,邵杰.遺傳算法在高校排課系統中研究與實現[J].計算機系統應用,2014(5):112-115.

[9] 張燕,唐啟濤,王聰,等.基于遺傳算法的高校排課算法研究[J].科技展望,2015(19):272-273.

[10] PILLAY N, BANZHAF W. An informed genetic algorithm for the examination timetabling problem[J]. Applied soft com-putting,2010,10(2):457-467.

[11] 朱顥東,李紅嬋.采用十進制最佳個體置換遺傳算法求解高校排課問題[J].計算機工程與科學,2013,3(6):186-190.

[12] 李紅嬋,朱顥東.基于最佳置換策略的高校排課問題求解[J].計算機工程,2011,37(19):186-189.

[13] 謝宗霖,劉亞軍,霍偉敬,等.基于整數規劃的排課優化問題[J].計算機與現代化,2015(7):15-19.

[14] 杜立智,陳和平,符海東.NP完全問題研究及前景剖析[J].武漢工程大學學報,2015,37(10):73-77.

[15] 胡恒,魯建夏,李英德.基于多群體并行遺傳算法的混流混合車間模糊調度研究[J].浙江工業大學學報,2012,40(5):554-558.

[16] 蘭月政,魯建夏,孔令革.基于遺傳算法的混流生產線產品分組指派問題研究[J].浙江工業大學學報,2011,39(3):312-316.

[17] 陳勇,胡婷婷,魯建夏.基于遺傳算法改進的動態車間調度[J].浙江工業大學學報,2012,40(5):537-543.

(責任編輯：陳石平)

Timetabling algorithm of high school optional class system based on improved genetic algorithm

WANG Weihong, LI Wengqiong

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

With the deepening reform of the college entrance examination system, the "course selection system" education mode gradually replaces the traditional teaching pattern in high schools. This teaching pattern leads to the increased factors and constraints that influence the effectiveness of curriculum arrangement, as well as the shortage of teaching resources. Traditional manual scheduling curriculum will take a lot of staff time and the schedule is hard to be adjusted. It can not meet the demand of the current teaching pattern. According to the analysis about the weakness of existing timetabling problem(TP), combining with the specificity of class-selection-system teaching pattern, we establish the corresponding mathematical model and analyze the constraint condition needed to be designed for TP. Based on the characteristics of course selected hierarchically by students, we solve this type of TP through applying improved genetic algorithm on students grouping and courses arranging. The experiment results show that the improved algorithm can effectively solve the TP of class-selection-system.

class-selection-system; improve genetic algorithm; curriculum arrangement algorithm

2016-02-28

國家自然科學專項基金資助項目(61340058)；浙江省自然科學基金重點資助項目(LZ14F020001)

王衛紅(1969—)，男，浙江臨海人，教授，研究方向為圖像圖形處理、遙感與地理信息系統以及信息安全等方面，E-mail：wwh@zjut.edu.cn.

TP311

A

1006-4303(2016)06-0601-07