基于改進(jìn)遺傳算法的高中走班制排課算法

王衛(wèi)紅，李文瓊

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

?

基于改進(jìn)遺傳算法的高中走班制排課算法

王衛(wèi)紅，李文瓊

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

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

“走班制”教學(xué)；改進(jìn)遺傳算法；排課算法

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

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

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

1.1 排課問題描述

要解決的難點(diǎn)是在“走班制”的分層教學(xué)制度下，對于分層教學(xué)的課程，學(xué)生根據(jù)個(gè)人情況對不同層級(jí)的課程進(jìn)行選課.因此，基于“走班制”教學(xué)模式下的排課問題無法像傳統(tǒng)行政班級(jí)一樣依據(jù)固定的學(xué)生成員和教室.筆者提出的解決方案是將學(xué)生進(jìn)行分組，組內(nèi)的每門課程的學(xué)生按層級(jí)和相關(guān)參數(shù)劃分多個(gè)該課程教學(xué)班，在該分組的基礎(chǔ)上為每組制定不同的課表.因此，“走班制”教學(xué)模式下的排課問題，即如何對時(shí)間、教師、教室、課程以及組內(nèi)和組間的流動(dòng)教學(xué)班等5 個(gè)因素進(jìn)行最優(yōu)化組合規(guī)劃的問題，即保證課程安排中盡量少的沖突出現(xiàn)，并解決學(xué)校嚴(yán)重的資源沖突問題.

1.2 數(shù)學(xué)建模

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

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

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

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

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

1) 由于一個(gè)學(xué)生對于不同的課程可以選擇不同的層級(jí)，因此，設(shè)計(jì)同一個(gè)教學(xué)時(shí)間段，在同一組內(nèi)的學(xué)生不能上一門以上的課程.

2) 同一個(gè)時(shí)間段的各個(gè)課程組安排的課程不能相同.

3) 同一個(gè)教學(xué)時(shí)間段，一個(gè)教師不能上一門以上的課程.

4) 同一個(gè)教學(xué)時(shí)間段，一個(gè)學(xué)生不能上一門以上的課程.

5) 同一個(gè)教學(xué)時(shí)間段，一個(gè)學(xué)生不能分配在一個(gè)以上的組內(nèi).

6) 同一個(gè)教學(xué)時(shí)間段，一個(gè)教室不能上一門以上的課程.

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

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

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

2) 一個(gè)學(xué)生的所有課程分布不應(yīng)過度集中，避免某段時(shí)間過于空閑.

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

4) 同一個(gè)教師的相近時(shí)間段的教學(xué)盡量安排在相對固定的教室或相近教室.

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

6) 邏輯性強(qiáng)的課程盡量安排在教學(xué)效果好的上課節(jié)次.

7) 公共課及學(xué)時(shí)多的課應(yīng)優(yōu)先安排.

8) 每個(gè)教學(xué)班的人數(shù)不宜過少也不宜過多.

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

10) 對學(xué)生分組的組數(shù)要盡量小于需要進(jìn)行教學(xué)分層的課程數(shù)量.

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

2 算法設(shè)計(jì)

2.1 基因編碼

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

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

2.2 排課問題約束滿足模型

針對這些硬約束條件建立一些數(shù)學(xué)約束模型，從而保證進(jìn)行智能課表編排時(shí)教學(xué)資源、對象不產(chǎn)生沖突.

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

設(shè)pi∈P，pj∈P，rλ∈R，rγ∈R，vα∈V，vβ∈V

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

規(guī)定：當(dāng)pi≠pj，且rλ≠rγ時(shí)，必有vα≠vβ.

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

設(shè)gci∈GC，gcj∈GC，gx∈G，gy∈G，ttλ∈TT，ttγ∈TT

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

規(guī)定：當(dāng)gci≠gcj，且gx≠gy時(shí)，滿足ttλ≠ttγ.

3) 一個(gè)教學(xué)班在同一時(shí)間段不能分配在一個(gè)以上的教室，數(shù)學(xué)表示如下：

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

當(dāng)rλ≠rγ，gcК≠gcη，pi≠pj時(shí)，滿足ttο≠ttυ.

4) 層級(jí)課程的授課教師是固定的，組內(nèi)排課是同一時(shí)間只針對一門課安排教學(xué)單元，要保證一個(gè)授課教師在同一教學(xué)單元只對一個(gè)教學(xué)班進(jìn)行授課.數(shù)學(xué)表示如下：

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

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

當(dāng)gcК≠gcη，pi=pj，gx≠gy時(shí)，ttο≠ttυ.

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

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

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

2.3 設(shè)計(jì)適應(yīng)度函數(shù)

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

(1)

式中：crashg為該種群個(gè)體的沖突次數(shù)；rewardg為該種群個(gè)體的獎(jiǎng)勵(lì)指數(shù)；uλi為在第λ教學(xué)組中第i個(gè)課程的教學(xué)時(shí)間段分配均勻度；nteam為分組組數(shù)；ngcourseλ為第λ教學(xué)組內(nèi)分層后課程總數(shù).統(tǒng)計(jì)該課程在其組內(nèi)的教學(xué)時(shí)間段分配記錄tcourseλi={tcourse1, tcourse2, tcourse3,…, tcoursentime}，ntime表示該課程被分配的教學(xué)時(shí)間段總數(shù).課程在教學(xué)時(shí)間段分配的均勻度為

(2)

式中dαβ為課程的第α個(gè)教學(xué)時(shí)間段到第β個(gè)教學(xué)時(shí)間段的距離.具體如下：

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

(3)

2) 用wλ表示課程時(shí)間段安排優(yōu)度，不同課程之間或者不同層級(jí)的課程之間的邏輯強(qiáng)度、重要程度都不同，不同教學(xué)時(shí)間段的教學(xué)效果不同，課程節(jié)次的安排優(yōu)度為

(4)

式中：courseweightυω為第ν個(gè)課程在第ω個(gè)教學(xué)時(shí)間段的教學(xué)效果權(quán)重；ngcourse為該教學(xué)組課程總數(shù)；ppd為一天內(nèi)教學(xué)時(shí)間段個(gè)數(shù).

3) 用rλ表示教室資源利用率，在一次教學(xué)安排中，一間教室內(nèi)分配的教學(xué)班學(xué)生數(shù)過少會(huì)浪費(fèi)教室資源，與該教室容量過度相近則會(huì)影響教學(xué)質(zhì)量，將教學(xué)班學(xué)生個(gè)數(shù)與教室容量的比值作為資源利用率的衡量標(biāo)準(zhǔn)，并設(shè)置當(dāng)其值為0.8時(shí)，資源利用率為最佳[9].組內(nèi)資源利用率為

(5)

式中：nclass為該教學(xué)組內(nèi)教學(xué)班數(shù)量；nroom為該教學(xué)組內(nèi)教室數(shù)量；nstuclassi為第i個(gè)教學(xué)班學(xué)生個(gè)數(shù)；nsturoomj為第j個(gè)教室容量.

2.4 初始種群的產(chǎn)生

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

2.5 選擇算子

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

2.6 交叉算子

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

2.7 變異算子

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

3 實(shí)例驗(yàn)證

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

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

1) 種群規(guī)模，符號(hào)表示Population，種群規(guī)模對算法效率有著一定的影響，規(guī)模較小會(huì)導(dǎo)致算法求解目標(biāo)值波動(dòng)較大，無法反映出對各個(gè)目標(biāo)的優(yōu)化；規(guī)模過大不僅會(huì)延長目標(biāo)收斂時(shí)間而且導(dǎo)致內(nèi)存消耗過盛.設(shè)置種群規(guī)模為300.

2) 算法遺傳代數(shù)，n=3 000，N值影響算法求解目標(biāo)的收斂性和最優(yōu)解求解范圍，N值過大導(dǎo)致各目標(biāo)不收斂；較小時(shí)導(dǎo)致最優(yōu)解極大可能不是最優(yōu)解.

3) 選擇率，設(shè)計(jì)個(gè)體的選擇率是由該個(gè)體在當(dāng)代種群中的適應(yīng)度值與所有個(gè)體適應(yīng)度總和的比例值，公式為

(6)

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

4) 交叉概率，交叉概率的大小直接影響算法最優(yōu)解的收斂程度，概率設(shè)置過大導(dǎo)致算法求解過程中解的波動(dòng)范圍過大，設(shè)置的太小導(dǎo)致算法收斂緩慢，交叉概率pc初始值設(shè)置為0.02，執(zhí)行交叉操作時(shí)自適應(yīng)交叉概率為

(7)

式中：fitmax為最大適應(yīng)度值；fitg[i]為個(gè)體當(dāng)代種群中的適應(yīng)度大小.

5) 變異概率，變異概率設(shè)置太大導(dǎo)致解的范圍波動(dòng)過大，設(shè)置過小引發(fā)全局最優(yōu)解收斂過緩慢，一般其值取0.001～0.2之間，變異概率設(shè)置初始值pm為0.01.

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

表1 分組結(jié)果

Table 1 Grouping result

組號(hào)教學(xué)班語文物理化學(xué)地理歷史0語文1物理A1物理A2化學(xué)A1化學(xué)A2地理A1地理A2歷史A1歷史A2語文2物理B1化學(xué)B1化學(xué)B2地理B1歷史B1語文3物理C1化學(xué)C1地理C1歷史C11語文1物理A1物理A2化學(xué)A1地理A1地理A2歷史A1語文2物理B1化學(xué)B1化學(xué)B2地理B1歷史B1歷史B2語文32語文1物理A1化學(xué)A1地理A1地理A2歷史A1歷史A2語文2物理B1物理B2化學(xué)B1化學(xué)B2地理B1歷史B1語文3

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

表2 第一組排課結(jié)果

Table 2 The timetable of the first group

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

表3 第二組排課結(jié)果

Table 3 The timetable of the second group

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

實(shí)驗(yàn)結(jié)果證明：通過筆者設(shè)計(jì)的排課算法，可以為實(shí)行“走班制”教學(xué)模式下的高中學(xué)校制定合理、高效的課表.

4 結(jié) 論

目前國內(nèi)外學(xué)者對傳統(tǒng)排課設(shè)計(jì)了很多算法，而針對“走班制”教學(xué)模式設(shè)計(jì)的排課算法卻沒有，筆者對傳統(tǒng)遺傳算法進(jìn)行研究后，采取了一定的改進(jìn)措施，研究、設(shè)計(jì)適應(yīng)以“走班制”教學(xué)為特色的排

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

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

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

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

[4] 吳紅艷.淺談遺傳退火算法在高校排課問題中的應(yīng)用[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].計(jì)算機(jī)仿真,2012,29(2):386-391.

[8] 馬玉芳,張海娜,邵杰.遺傳算法在高校排課系統(tǒng)中研究與實(shí)現(xiàn)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,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ìn)制最佳個(gè)體置換遺傳算法求解高校排課問題[J].計(jì)算機(jī)工程與科學(xué),2013,3(6):186-190.

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

[13] 謝宗霖,劉亞軍,霍偉敬,等.基于整數(shù)規(guī)劃的排課優(yōu)化問題[J].計(jì)算機(jī)與現(xiàn)代化,2015(7):15-19.

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

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

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

[17] 陳勇,胡婷婷,魯建夏.基于遺傳算法改進(jìn)的動(dòng)態(tài)車間調(diào)度[J].浙江工業(yè)大學(xué)學(xué)報(bào),2012,40(5):537-543.

(責(zé)任編輯：陳石平)

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

國家自然科學(xué)專項(xiàng)基金資助項(xiàng)目(61340058)；浙江省自然科學(xué)基金重點(diǎn)資助項(xiàng)目(LZ14F020001)

王衛(wèi)紅(1969—)，男，浙江臨海人，教授，研究方向?yàn)閳D像圖形處理、遙感與地理信息系統(tǒng)以及信息安全等方面，E-mail：wwh@zjut.edu.cn.

TP311

A

1006-4303(2016)06-0601-07