基于改進(jìn)型遺傳算法求解高校排課問題

1、 基于改進(jìn)型遺傳算法求解高校排課問題 龔程陳高云劉胤田李代偉摘 要：隨著信息技術(shù)的不斷發(fā)展和教育改革的不斷深入，通過信息技術(shù)實現(xiàn)教學(xué)管理的智能化已經(jīng)成為可能。排課作為教學(xué)管理的核心內(nèi)容之一，它是衡量教學(xué)管理水平的重要指標(biāo)，它是教學(xué)管理智能化的重要體現(xiàn)。本文的研究是通過學(xué)校的教學(xué)計劃分析并建立排課的數(shù)學(xué)模型，對傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)，設(shè)計出一種改進(jìn)的自適應(yīng)的遺傳算法求解排課問題，改進(jìn)的自適應(yīng)遺傳算法相對于傳統(tǒng)的遺傳算法在排課效率上有很大提高。Key：排課模型；遺傳算法；節(jié)次；自適應(yīng)：TP311.5 ：AAbstract：With the continuous development of inf

2、ormation technology and the further deepening of education reform，intelligent teaching management by means of information technology has become possible.As one of the core contents of teaching management，course scheduling is an important index to measure teaching management as well as an important e

3、vidence of intelligent teaching management.This paper has analyzed and established the mathematics model of course scheduling through the teaching plan in colleges and universities，improved traditional genetic algorithm and designed an improved self-adaptive genetic algorithm to solve the scheduling

4、 problem.Compared with traditional genetic algorithm，the improved adaptive genetic algorithm has greatly increased the efficiency of course scheduling.Keywords：course scheduling model；genetic algorithm；section；self-adaptive1 引言（Introduction）隨著信息技術(shù)的不斷發(fā)展和教育改革的不斷深入，通過信息技術(shù)實現(xiàn)教學(xué)管理的智能化已經(jīng)成為可能1。排課作為教學(xué)管理的核心內(nèi)容

5、之一，它是衡量教學(xué)管理水平的重要指標(biāo)，它是教學(xué)管理智能化的重要體現(xiàn)。排課問題的目標(biāo)是在一定的約束條件下求解出較優(yōu)的排課方案，使得依據(jù)此方案執(zhí)行的教學(xué)計劃具有學(xué)生老師合理安排，教室資源利用率高，教學(xué)質(zhì)量高的特點2，3。2 常見的排課模型（Common course scheduling model）2.1 圖論算法圖論中的圖是由若干給定點及連接兩點的線所構(gòu)成的圖形，這種圖形通常用來描述事物之間的某種特定關(guān)系，用點代表事物，用連接兩點的線表示相應(yīng)兩個事物間具有這種關(guān)系圖論解決排課問題，將圖論的邊著色理論，對排課資源進(jìn)行建模，使得排課問題得以解決4。但圖論本身是NP完全問題，算法實現(xiàn)上比較繁瑣。2.

6、2 貪心算法貪心算法基本思路是從問題的某一個初始解出發(fā)一步一步地進(jìn)行，根據(jù)某個優(yōu)化測度，每一步都要確保能獲得局部最優(yōu)解。貪心算法的排課系統(tǒng)，以資源匹配為基礎(chǔ)，用內(nèi)存動態(tài)分區(qū)分配的最佳適應(yīng)法為依托解決排課問題5。與圖論算法比較，避免了算法實現(xiàn)上的困難，但貪心算法在斷點選擇中存在缺陷。2.3 人工智能算法人工智能是對人的意識、思維的信息過程模擬。人工智能解決學(xué)校的排課系統(tǒng)，以時間因素為核心進(jìn)行課程的安排符合學(xué)校教學(xué)實際情況，以影響學(xué)校課程安排中最為直接的三個因素教師。以學(xué)生和教室為核心來安排一門課程6。使用這種方法能夠使學(xué)校管理進(jìn)一步科學(xué)化，高效化。3 基于高校的排課模型（Course sched

7、uling model in colleges and universities）3.1 相關(guān)術(shù)語教學(xué)班（Teaching Class）：一個教學(xué)班包含多個班級。例如：軟件工程2015級12班包含1班和2班兩個班，這樣定義不需要考慮合班情況，只需要在制定教學(xué)計劃時選擇出需要合班的班級即可，教學(xué)班集合定義為，每個教學(xué)班對應(yīng)的人數(shù)為。節(jié)次（Section）：一門課程上一節(jié)課45min所耗費的時間為一個節(jié)次，一天共有10個節(jié)次，上午四個節(jié)次，下午四個節(jié)次和晚上兩個節(jié)次，節(jié)次集合定義為。課程（Course）：將課程分為公共基礎(chǔ)必修，公共基礎(chǔ)選修，學(xué)科基礎(chǔ)必修，學(xué)科基礎(chǔ)選修，專業(yè)課必修，專業(yè)課選修，實踐

8、教學(xué)環(huán)節(jié)必修，實踐教學(xué)環(huán)節(jié)選修，表示課程的重要程度，即權(quán)重。課程的權(quán)重為1，2，3，8。教室（Class Room）：集合定義為。教師（Teacher）：集合定義為。時間間隔（Time Interval）：對于一周多學(xué)時的課程需要有時間間隔，用，表示間隔的天數(shù)。3.2 約束條件3.2.1 硬約束條件3.2.2 軟約束條件課程約束：課程約束包含三個約束條件，分別是：重要的課程要安排在教學(xué)效果好的節(jié)次；同一門課程應(yīng)該安排在每周中同一個節(jié)次；同一門課程的教室應(yīng)該安排一致。對應(yīng)的數(shù)學(xué)表達(dá)式如下：教師約束：教室約束包含三個約束條件，分別是：同一個教師在一周上同一門課程是多節(jié)次，則課程的時間安排應(yīng)該有時間

9、間隔；同一個教師在一周上兩門課程，則課程的時間安排應(yīng)該連排；同一個教師在一周上兩門課程，則課程的教室安排應(yīng)該足夠的近。對應(yīng)的數(shù)學(xué)表達(dá)式如下：學(xué)生約束：學(xué)生約束包含三個約束條件，分別是：每個學(xué)生一個周節(jié)次排課分布均勻；每個學(xué)生一天不能排滿課；每個學(xué)生連續(xù)上兩門課程，則課程教室的安排應(yīng)該足夠的近。對應(yīng)的數(shù)學(xué)表達(dá)式如下：其中，表示一個教學(xué)班在一個工作日所上的課程數(shù)，表示一周上課天數(shù)，表示一個教學(xué)班一天平均要上的節(jié)次。教室約束：教室約束是教室的利用率應(yīng)該高。對應(yīng)的數(shù)學(xué)表達(dá)式如下：3.3 適應(yīng)度函數(shù)適應(yīng)度函數(shù)的好壞決定了遺傳算法的收斂性，若目標(biāo)函數(shù)設(shè)計不合理會造成程序執(zhí)行過早收斂，形成局部最優(yōu)解，合理的

10、目標(biāo)函數(shù)可以得到全局最優(yōu)解。本文所設(shè)計適應(yīng)度函數(shù)如式（6）所示，目標(biāo)函數(shù)適應(yīng)度的函數(shù)值的解越大所求出的解越優(yōu)。3.4 排課的流程排課是根據(jù)教務(wù)處指派的教學(xué)任務(wù)，合理的將教學(xué)任務(wù)分配教室和時間，排課流程如圖1所示。4.1 編碼設(shè)計編碼方式有浮點編碼、二進(jìn)制編碼、十進(jìn)制編碼等方式，本文采用十進(jìn)制編碼表示課表染色體的編碼，如下表2所示，能更好地表示排課問題的實際特點。每一種編碼對應(yīng)一條染色體，則每一條染色體表示的是一種排課可能。例如：軟件學(xué)院張三教授給2012級軟件工程1班上數(shù)據(jù)結(jié)構(gòu)課程，課程每周兩次，在2棟樓101多媒體教室進(jìn)行，時間是第四周周一下午五六節(jié)，則可此授課事件的染色體編碼為011001

11、-1201011-1220001-22101-0413（其中011001表示教師編碼，01表示軟件學(xué)院，1表示教師的職稱，001表示教師的編號）。4.2 初始種群的產(chǎn)生初始種群的產(chǎn)生一般通過隨機搜索的方式產(chǎn)生，為后續(xù)各種操作提供初始可行解。由于初始種群中生成的個體適應(yīng)度值較低，本文首先按照課程權(quán)重對課程進(jìn)行排序，該操作可以避免解空間的過早壓縮，同時能夠盡早的產(chǎn)生可行解。4.3 選擇操作根據(jù)達(dá)爾文的進(jìn)化論提出的“適者生存”的原則，選擇是從種群中選擇出優(yōu)秀的個體作為父代，并為下一代個體繁殖作基礎(chǔ)。選擇操作通常也稱作再生操作。選擇操作從種群中選擇出適應(yīng)度高的個體遺傳到下代個體。種群中個體的適應(yīng)度的值

12、越大，被選擇的概率則越高。fi表示種群中個體的適應(yīng)度的值，n表示種群中個體的數(shù)量，則種群中個體的概率值：4.4 自適應(yīng)交叉和變異操作交叉操作是把種群中兩個個體進(jìn)行隨機的交叉重組，這種操作既保證的新產(chǎn)生的個體保留了父代個體的優(yōu)良基因，又是種群的個體具有多樣性。變異操作是種群中的個體根據(jù)一定的概率值做出基因位的變動。傳統(tǒng)的遺傳算法中，采用固定的交叉概率和變異概率，容易產(chǎn)生局部最優(yōu)解，本文采用自適應(yīng)的交叉和變異操作進(jìn)行遺傳算法的計算，具體操作如下：其中，和分別表示交叉和變異概率，表示當(dāng)前種群最優(yōu)個體的適應(yīng)度值，表示當(dāng)前種群平均適應(yīng)度值，表示進(jìn)行交叉操作的個體中適應(yīng)度較大的值，表示變異個體適度值，和取

13、值均為0到1的隨機數(shù)。5 實驗（Experiment）5.1 實驗數(shù)據(jù)本文實驗數(shù)據(jù)是來自軟件工程學(xué)院2017年秋季課表，如表3所示。實驗參數(shù)如表4所示。實驗平臺采用2.20GHz，Pentium i7處理器、8GB內(nèi)存、700GB硬盤，操作系統(tǒng)為win7。所有實驗均采用C#語言，在Visual Studio 2010下實現(xiàn)。5.2 實驗結(jié)果與分析對于同一初始種群下，將文獻(xiàn)7中（GA）方法與本文方法（MGA）進(jìn)行對比。圖2是10次實驗兩種方法不同的種群平均適度的值，MGA的平均值高于GA的平均值，圖3是10次實驗兩種方法不同的時間值，MGA的時間值低于GA的時間值。由圖2和圖3可以看出，本文方法

14、都優(yōu)于文獻(xiàn)7中的方法。根據(jù)表5的評價指標(biāo)分析，改進(jìn)后的遺傳算法MGA比傳統(tǒng)的遺傳算法GA在課程均勻度，學(xué)生課程分布，教室滿意度及教室利用率方面都有明顯的改善。6 結(jié)論（Conclusion）本文針對高校排課問題進(jìn)行分析，根據(jù)教學(xué)計劃對排課問題建模，通過改進(jìn)的遺傳算法對問題進(jìn)行求解。實驗結(jié)果表明，改進(jìn)后的遺傳算法比一般的遺傳算法具有更高的效率。如何合理的解決排課中漏排課問題是下一步研究的重點。Reference（References）1 Marc Goerigk，Christian Liebchen.An Improved Algorithm for the Periodic Timetabli

15、ng ProblemC.17th Workshop on Algorithmic Approaches for Transportation Modelling，Optimization，and Systems，2017（12）：1-14.2 H Babaei，J Karimpour，A Hadidi.A survey of approaches for university course timetabling problemJ.Computers & Industrial Engineering，2015，86（C）：43-59.3 G Woumans，L De Boeck，J Belin.A column generation approach for solving the examination-timetabling problemJ.European Journal of Operational Research，2016，253（1）：178-194.4 崔妍，王權(quán)，王康，等.排課問題的數(shù)學(xué)模型J.沈陽工程學(xué)院學(xué)報（自然科學(xué)版），2016，12（3）：276-278.5