凌敏

摘 要 本文分析了造成多校區(qū)高校排課困難的各種因素，研究了如何應(yīng)用遺傳算法來解決多校區(qū)高校排課困難的問題，并對該算法進(jìn)行詳細(xì)設(shè)計(jì)，給出了一個基于該算法的排課模型。

關(guān)鍵詞 遺傳算法 排課系統(tǒng) 教務(wù)管理

中圖分類號：G71 文獻(xiàn)標(biāo)識碼：A

排課問題是一個多約束、多目標(biāo)的優(yōu)化問題，是教務(wù)管理工作的一個重點(diǎn)和難點(diǎn)。尤其是多校區(qū)同時(shí)運(yùn)行的高校格局增加了更多的約束條件，問題的復(fù)雜度也增加了許多。多校區(qū)排課是一個典型的多因素的優(yōu)化決策問題，是組合規(guī)劃中的NP完全類問題，涉及信息較多且求解復(fù)雜性為課表規(guī)模的指數(shù)量級。遺傳算法被證明解決該類問題是最合適的。

1排課問題描述

課表要有利于教學(xué)設(shè)備的充分利用，要符合教學(xué)規(guī)律。將這個原則進(jìn)行細(xì)化、清晰化，一般可以歸納為以下具體要求。

（1）課表中沒有硬性沖突，在排課過程中必須遵守如下約束條件：

①每位教師在同一時(shí)間段內(nèi)只能安排一門課程；

②一個教室在某一時(shí)間只能安排一門課；

③教室的位置數(shù)量與每個自然班的人數(shù)應(yīng)盡量匹配；

④必須根據(jù)核定的教學(xué)計(jì)劃所規(guī)定的學(xué)時(shí)數(shù)排課，不得任意增減；

⑤一個教師兩節(jié)課間路程不超過10分鐘，半天的工作必須安排在同一個校區(qū)。

（2）課表要求有較高質(zhì)量，為了使排出的課表更優(yōu)化、合理、排課還應(yīng)考慮以下因素：

①一門課程在每個班的每兩天只能安排一次；

②專業(yè)必修課盡量安排在上午；

③同一門課的上課地點(diǎn)盡量安排在同一教室；

④體育課必須排在下午或者上午3-4節(jié)，體育課后避免安排講授課；

⑤實(shí)驗(yàn)、操作、訓(xùn)練、演示等課應(yīng)排在下午；

⑥滿足個別教師的特殊上課時(shí)間要求；

⑦編排課表時(shí)，先排公共課，后排專業(yè)課；先排合班課，后排單班課；

先排多頭課（一個教師有多門課），后排獨(dú)頭課；先排多時(shí)課，后排少時(shí)課。

2排課問題的遺傳算法設(shè)計(jì)

首先，人工安排或計(jì)算機(jī)根據(jù)條件自動生成，集中安排實(shí)驗(yàn)、實(shí)習(xí)、社會實(shí)踐等有固定時(shí)間和地點(diǎn)的課程。

其次，剩余課程按照院系為單位分為若干個子塊，用遺傳算法對每個子塊進(jìn)行排課操作。

2.1染色體編碼

遺傳算法中首要考慮的是如何表現(xiàn)問題，即如何對其進(jìn)行染色體編碼，使之適用于GA操作。一條染色體中應(yīng)包含課程、老師、教室、學(xué)生、時(shí)間和校區(qū)等相關(guān)信息。但由于某一門課程信息里面已經(jīng)包含了老師、學(xué)生和校區(qū)信息，故染色體中僅需要對課程、教室和節(jié)次采用可拼接的二進(jìn)制編碼。若某院系一學(xué)期有40門課程，可編為X1=（a1，a2，a3，a4，a5，a6），ai∈{0，1}。每個院系一般有20 個教室不等，可編為X2=（b1，b2，b3，b4，b5），bi∈{0，1}。每周上五天課，每天4次，共20次，可編為X3=（c1，c2，c3，c4，c5……，c19，c20），ci∈{0，1}。所有課程的DNA分子拼接形成一條染色體。

2.2初始化群體

群體初始化的規(guī)模數(shù)n應(yīng)取適中。一般，n取值為染色體長度的兩倍左右。根據(jù)上述的染色體編碼，一個DNA分子長度為31，40門課程的一個染色體碼長為1240，故n可取2480。每條染色體中的DNA分子之間由于教室、時(shí)間、學(xué)生、老師、校區(qū)等因素會產(chǎn)生沖突，比如一個老師不能在同一時(shí)間安排兩門或兩門以上的課程。產(chǎn)生初始群體時(shí)，在不產(chǎn)生沖突的情況下（滿足上述5條硬約束條件），隨機(jī)為基因塊賦0或1，直到滿足群體規(guī)模。

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

遺傳算法根據(jù)適應(yīng)度群體中個體的優(yōu)良程度，適應(yīng)度較高的個體遺傳到下一代的概率較大。因此，遺傳算法是在適應(yīng)度函數(shù)的引導(dǎo)下運(yùn)行的，適應(yīng)度函數(shù)選擇的好壞直接影響算法的優(yōu)劣。在適應(yīng)度函數(shù)設(shè)計(jì)中，我們主要考慮以下沖突；

（1）教師沖突，教師安排是否沖突，同一時(shí)間段是否安排兩次課。

（2）教室沖突，同一教室同一時(shí)間段不能安排兩門課。

（3）班級沖突，同一班級同一時(shí)間的段不能安排兩門課。

（4）交通沖突：對于多校區(qū)或單校區(qū)教學(xué)樓分散情況，教師或?qū)W生相鄰時(shí)的教室間距不應(yīng)超過10分鐘；

（5）教室大小與學(xué)生人數(shù)的沖突。

以上約束條件Pi∈{0，1}，0表示有沖突，1表示沒有沖突首先對一條染色體中的每個DNA分子（一門課程）計(jì)算適應(yīng)度，然后計(jì)算一條染色體所有DNA分子適應(yīng)度之和，將該值作為個體適應(yīng)度，數(shù)學(xué)表達(dá)式如下：

fi=（P1譖2譖3譖4譖5？f譗1+j譗2+h譗3）

F=40i=1 %Lfi

f表示節(jié)次優(yōu)先度，j表示課程類別優(yōu)先度，h表示組合優(yōu)先度。Q1、Q2、Q3代表相應(yīng)權(quán)值，F(xiàn)為個體適應(yīng)度。

2.4選擇算子

采用截?cái)噙x擇法，染色體按適應(yīng)度函數(shù)值從高到低排序，只有最優(yōu)秀的個體才能被選作父個體。其中，用于決定染色體被選作父個體的百分比的參數(shù)稱為截?cái)嚅y值，范圍取90%～80%。在該閥值之外的個體不能產(chǎn)生子個體。

2.5交叉算子

交叉只對復(fù)制產(chǎn)生的85%的個體進(jìn)行，此時(shí)適當(dāng)?shù)倪x擇交換概率p，p過大或過小都不易收斂到最優(yōu)解，設(shè)p為0.95（保留的15%不參加交換）。采用一點(diǎn)交換方式，在排課問題中，每周某一課程上課節(jié)次是固定的，隨機(jī)選擇第n個DNA分子時(shí)間節(jié)次碼中第m個基因位為1的基因。

2.6變異算子

排課系統(tǒng)中由于課表合法性問題，如果采用簡單的隨機(jī)變異，會出現(xiàn)大量的沖突，導(dǎo)致需要消耗大量精力去糾錯。因此，我們在研究中采用有條件的基因變異。變異操作的作用是防止丟失有用的可能解，保證搜索到空間的重要點(diǎn)，使算法具有全局收斂性，變異的概率較小，在本文中取0.01。和交叉算子一樣僅是時(shí)間節(jié)次碼參與交換，教室和課程碼保持不變。選擇兩個點(diǎn)進(jìn)行變異，具體操作是：隨機(jī)選擇第n個DNA分子，再隨機(jī)選DNA分子中的時(shí)間碼第p、q個點(diǎn)進(jìn)行變異。

2.7終止條件

采用迭代次數(shù)來決定，取2500。

參考文獻(xiàn)

[1] 肖俊.遺傳算法的工程應(yīng)用[J].計(jì)算機(jī)科學(xué)，2005，11（32）：247-250