利用改進遺傳算法破解排課難題

董玉鎖+賀波+尹迎+胡海琴+李鐵梅

摘 要 針對當前學校排課的實際問題，在傳統遺傳算法的基礎上做了一系列改進。設計專門的染色體結構，優化初始種群的生成過程，并在標準遺傳算法的基礎上對選擇算子、交叉算子和變異算子等多方面進行改進。目前，該算法已成功應用在東華博育云有限公司的排課產品中，實驗表明，改進后的算法能得到較滿意的課程安排方案，運行效率高，課表中出現資源沖突現象顯著減少，極大地縮短了學校教務管理人員排課工作消耗的時間。

關鍵詞 數學模型；遺傳算法；排課；教務管理；教學班

中圖分類號：G434 文獻標識碼：B

文章編號：1671-489X（2018）01-0016-04

1 引言

中小學校的教務管理部門在整個教學過程中起著組織、協調、管理及服務的作用，而排課又是教務工作中最基礎、最重要的組成部分，也是工作量最大、最煩瑣、難度最大的一項任務。排課工作的核心就是為學校所有的課程安排合適的教師、教學時間和地點，使學校的各項教育教學工作能夠穩步推進、相互銜接。排課問題是困擾各學校的主要難題之一。近年來，國家大力推行課程和教學改革，實施“分層走班”等試驗教學，這種走班模式下的排課難度更大。

所謂“走班制”，是指學校開設教學內容和程度要求不盡相同的各種層次班，教師、班級、學生并不固定，學生需要根據自己的能力和愛好選擇進入不同的層次班上課學習。這種模式下學生的學習課程和上課班級都不相同，打破了原來固有的行政班授課模式，更增大了學校排課工作的難度。

S.Even等人于20世紀70年代論證了排課問題為NP完全問題（Non-deterministic Polynomial complete Problem，

NP-C，即多項式復雜程度的非確定性問題，是世界七大數學難題之一），由此奠定了其理論深度和難度。由于NP完全問題的特殊性，到現在為止，業界對其還沒有通用的解決方案和算法。為了解決排課這類復雜的NP完全問題，本文立足實踐提出排課問題的數學模型，并專門對傳統遺傳算法操作進行一系列的改進來求解，依托模型和算法降低運算的復雜度，力爭使求解問題的時間大大減少。

排課問題描述 排課問題屬于復雜的動態組合規劃問題，由于限制因素較多且求解復雜性大，使求解計算所消耗時間成指數級增長。課表由教師、學生、課程、教室、上課班級和上課時間等元素構成，排課的過程是把這些課表元素進行排列組合規劃，保證教師、學生、班級、課程和教室等資源在課表中的任何上課時間里都不會發生沖突。為了使排出的課表更人性化、用戶滿意度高，同時要考慮另外一些因素，例如：每門課程的上課時間要分布均勻、間隔合理；根據不同課程的特點安排合適的上課時間，如語文、英語不適合在下午排課，足球課、游泳課不適合在上午第一節排課等。

在對排課模型進行分析之后，本文抽象出一個“教學班”的概念。所謂教學班，指的是在相同時間、相同地點（教室）學習，由相同教師講授同一門課程的一定數量的學生組成，便于教學和課堂活動的學生集體。在多個教師任同一門課程，或一門課程開設多個班級時，按課程和任課教師將學生分配到多個教學班（必修課可以在排課前確定教學學生分班情況，選修課教學班分班情況在選課完成后才能確定）。采用教學班的概念之后，無論傳統的行政班授課，還是走班制授課，都可以很好地轉換和對應起來，可以實現各種模式下的排課場景和需求。

排課的約束條件 排課不僅要考慮課表各元素在時間、空間上存在的合理性，同時要滿足學校自身的各種約束條件（如教師不排課時間、課程不排課時間、固定課安排和課程互斥等），從而保證學校教學工作正常進行。排課中設置約束條件是為了避免課表中出現沖突。為了保障學校教育教學工作順利進行，排出的課表必須不違反任何約束條件，也不允許出現任何課表元素沖突。同時，對課表各元素資源進行最優化組合配置，也有利于學校發揮資源優勢、提高教學質量。有鑒于此，本文定義了三種排課約束條件。

1）排課硬約束條件。硬約束條件代表課表各元素在時間和空間概念上不能成立的情形，是排課過程中要遵守的最基本的約束條件。評價一張課表是否合理、可行，首先要看它是否滿足所有的硬約束條件：教師不能沖突，如一個教師既不能同時教授兩門或更多課程，也不能同時在多個教室上課；學生不能沖突，如一個學生既不能同時上兩門或更多課程，也不能同時在多個班上課；教室不能沖突，如一間教室內不能同時安排兩門及以上課程；班級不能沖突，如一個班級不能同時安排兩門及以上課程；每門課程安排的授課教室座位數不得少于該課程的上課人數。

2）用戶自定義約束條件：教師不排課時間要求；課程不排課時間要求；班級不排課時間要求；教室不排課時間要求；年級不排課時間要求；固定課要求；教師互斥要求；課程互斥要求。

3）排課軟約束條件。評價一張課表優秀質量高，不僅必須滿足上述硬約束條件和用戶自定義約束條件，還需要考慮一些額外的軟約束條件。軟約束條件不是排課中必須遵守的規則，雖然這些規則并不會影響排課的成功或失敗，但它們會對課表的合理性和用戶滿意度產生較大影響。硬約束條件和用戶自定義約束條件是評價一張課表是否合理有效的標準，而軟約束條件則是評價一張課表質量好壞的標準。軟約束條件在排課問題中要盡量遵守、滿足，一般的軟約束條件有：班級課程盡量均勻分布；教案對齊；教師連續長時間上課的情況要盡量避免；班級不同課程上課地點盡量靠近；同一門課程的不同上課時間間隔要合理；上課學生人數和教室容量盡量匹配，提高教室利用率。

排課的求解目標 排課問題是一個含多約束條件的多目標的組合規劃問題，按照多目標優化的方法與理論，在可行解域中找到的解將是一系列的解集合。如何從排課問題的眾多求解空間中找到一套完整的包含課表所有元素的信息組合，并且不違背任何硬性約束和用戶自定義約束的課表，是排課的最基本要求。在此基礎上，課表質量的高低還需要通過其他指標來評價。本文中確定了兩個排課目標：endprint

1）課表方案中不存在任何的硬性沖突，即課表必須滿足所有硬約束條件和用戶自定義約束，如同一個學生在同一時間不能上多門不同的課程，或者不能違背課程的不排課時間約束等，這是評價課表是否合理可行的基本條件；

2）課表質量高，即對課表各元素資源的分配合理、優化，盡可能多地滿足各種軟約束條件。

2 基于改進遺傳算法的排課問題求解

遺傳算法（Genetic Algorithm，GA）也叫基因進化算法，或進化算法，是由美國人J.Holland在20世紀60年代提出來的。遺傳算法屬于啟發式搜索算法，它模擬自然界生物的進化過程，試圖應用生命進化的規律找到一條有效解決實際問題中組合爆炸問題的途徑。遺傳算法提供了一種求解非線性、多模型、多目標等復雜系統優化問題的通用框架，它不依賴于問題具體的領域，已在很多領域得到廣泛應用[1-2]，用于求解各種組合優化問題，為求解排課問題提供了有效的手段。

染色體（Chromosome）結構 使用遺傳算法來求解排課問題的時候，首先必須把問題解的參數形式轉換成由基因編碼按一定結構組成的遺傳染色體或個體[3]。遺傳算法運算的起點和對象是種群（population），而種群是由大量經過基因編碼的離散個體（individual）所構成的。初始化種群以后，算法依據適者生存的生物進化理論迭代進行，進化過程中的每一代，算法通過交叉操作和變異操作，誕生出下一代種群，并根據適應度大小選擇優秀的后代個體，淘汰較差的個體，從而使整個種群保持穩定。經過多次迭代運算之后，遺傳算法將逐漸收斂于最好的個體[4]。

應用遺傳算法首先要對個體染色體進行基因編碼，將排課問題中的課表轉化為算法可操作的染色體編碼。染色體編碼方式設計至關重要，它不僅要能記錄表達種群個體的各種特征信息，而且決定了遺傳操作算子的設計和計算規模，直接影響了整個算法的收斂和搜索速度。

通過對常見遺傳算法編碼方案進行分析比較后，鑒于它們在實際求解排課問題時存在表示問題本身較為困難、排課效率較低、求解結果不理想的問題，本文針對排課問題專門設計一種優化改進的染色體編碼方案，使其更適合于表示和求解排課問題。排課一般按排課周期來進行，以中小學來說是按周排課，每周周一至周五共五天上課，每天上七節課（上午兩節課，下午三節課，晚上兩節課）。這樣，每周就會構成35個課節次，用T1，T2，T3，T4，T5，

T6，...，T35表示。其中，T1，T2，...，T7為周一的課節次，T8，T9，...，T14為周二的課節次，以此類推。如果全校有S個教學班，那么該學校課表可表示為以35個課節次為列、每個“教學班”為行組成的一個S*35二維矩陣。

基于這個設計，本文開創性地采用二維布爾矩陣（Boo-

lean Matrix）的方式來對課表染色體進行基因編碼。該矩陣的所有元素取值均為1或0，橫坐標為課節次，縱坐標為教學班。其中，值為0表示沒有安排課程，值為1表示已經安排了課程。任何一種排課方案都可以在設計的編碼空間中找到對應的解。

約束的處理 排課問題中的各類約束條件在設計的算法中都要得到對應和處理。本文采用懲罰函數法來處理約束。懲罰函數法是解非線性約束優化問題常用的一種方法[5-6]，

它根據約束的特點構造某種懲罰函數，并把它加到目標函數中去，使約束問題的求解轉化為一系列無約束問題的求解。對無約束問題求解過程中違反約束的迭代點給予很大的目標函數值，從而迫使這一系列無約束問題的極小點逐漸收斂于約束問題的極小點。本文具體做法：如果一個種群個體染色體對應的解違反了某個約束條件（包括硬性約束條件、用戶自定義約束條件），算法將根據其違反約束的程度給予一定的懲罰，使該個體具有較小的適應度值。這種處理方式可以保證在不損失種群數目的前提下，隨著種群的進化，使不可行解的數量在整個種群中所占的比例越來越小，而可行解的數量則越來越多，并逐步趨向于最優解。

初始種群生成 初始種群是遺傳算法迭代的起點，它選擇的好壞將直接影響算法的效率[7]。在遺傳算法中，要求初始種群內個體多樣化，以保證較高的進化效率[8-9]。根據前文介紹，每個個體的染色體是行為40個時間片（即一個教學班一周的課表），列為教學班組成的二維數組。對每一個教學班來說，根據課程的周任課數，隨機初始化到這一行中，用1表示，其他位數用0填充。所有的教學班均按此辦法操作，就可以形成一個個體。按照種群的大小，產生一定數量的個體構成初始種群。對于固定課和預排課，初始化的時候要特別注意。

適應度函數設計 在遺傳算法體系中，適應度是描述種群中個體優劣的主要指標，進化時根據個體適應度的大小優勝劣汰。參照以自然選擇學說為核心的現代生物進化理論，遺傳算法中的適應度對應著生物界中物競天擇、適者生存的物種生存能力，在算法執行過程中起到極其重要的作用。為了使用遺傳算法來表示和求解排課問題，需要將排課問題的目標函數與種群個體適應度建立一種映射關系，從而在群體進化過程中實現對排課問題目標函數的尋優。

前文提到排課問題中，對一種排課方案的好壞評價是很復雜的，包含各課表元素的規則和要求——硬約束條件、用戶自定義約束條件和軟約束條件。使用遺傳算法求解排課問題時，適應度函數的構造和設計尤為關鍵，是不可或缺的一步。綜合考慮三類約束條件，本文提出適應度函數由兩部分組成：不可違反代價f1（違反硬約束條件、用戶自定義約束條件產生的代價）和可違反代價f2（違反軟約束條件產生的代價）。本文設計的適應度函數的特點：當有違反硬性約束時（即使只違反了一個），那么個體的適應度將主要由f1決定；只有在沒有違反硬性約束的情況下，個體適應度主要由f2決定。適應度函數為：

其中：

ρ是一個0～1之間的小數，用于條件f1和f2間的權重比例；αi為第i個硬約束條件、用戶自定義約束條件的權重；βi為第i個軟約束條件的權重。endprint

遺傳算子設計 遺傳操作是遺傳算法的核心處理過程，是算法實現迭代尋優功能的最主要工具。在標準遺傳算法中，遺傳操作包括三種基本遺傳算子，即選擇算子、交叉算子、變異算子。

1）選擇算子（Selection）。生物界進化機制中的選擇操作能夠實現個體染色體的復制延續，使各種生物能夠保持各自性狀，從而保證物種種群穩定。遺傳算法也引入選擇操作方式，選擇的目的是優勝劣汰，它根據種群中個體適應度的大小，將適應度高的個體挑選出來，使其染色體有更高機率往下一代遺傳，而逐步將適應度低的個體淘汰。因此，選擇操作的實質是挑選，其作用是定向優化。在種群進化迭代的過程中，由于選擇算子的定向優化作用逐代疊加，使整個種群個體都朝著適應度高的方向進化，從而使種群的品質越來越高。選擇算子決定了種群中哪些個體染色體可以遺傳復制到下一代，直接影響到種群的多樣性。

為了提高算法的全局搜索能力，改進選擇算子是最重要途徑之一。選擇算子有很多種處理方式，常見的方法有輪盤賭選擇法、隨機遍歷抽樣法、截斷選擇法和錦標賽選擇法等，這些方法都有各自的特點和適用范圍。本文在對常見的各種選擇算子進行分析研究后，決定采用輪盤賭選擇策略計算概率，并在此基礎上使用最優保存策略進行挑選，結合使用這兩種策略，保證種群最佳個體有更高概率向子代遺傳，避免其在迭代過程中損失，加快遺傳算法朝最優解收斂的速度。

2）交叉算子（Crossover）。為了模擬生物界物種繁衍的機制，遺傳算法引入交叉操作，從而達到基因重組的目的，使父代個體染色體中的基因片段定向遺傳到子代個體中去。交叉算子是通過交換兩個父代個體部分對應基因片段來進行操作的，其結果是產生兩個各自遺傳一部分父代染色體基因的子代個體。交叉算子在遺傳算法中起著最核心的作用[10]，經過交叉操作的處理，大大提升了遺傳算法的全局搜索能力。

種群初始化時，每個個體對應的布爾矩陣的每一行中數值為1的元素個數等于其對應教學班的周課時數。在遺傳算法執行過程中，不論是交叉操作還是后面將要介紹的變異操作，每一代每個種群個體都要遵循這個原則。單點交叉是傳統遺傳算法最常用的交叉操作方式，其做法是在個體染色體上任意選擇一個基因位置作為交叉點，互換待交叉的兩個父代個體在該交叉點右邊的染色體片段，但這種操作不能滿足周課時數規則，因此不能直接使用。考慮到課表問題的特殊性，本文采用矩陣染色體對應行之間分別進行局部交叉操作，具體操作時參照單點交叉的方式并對處理過程做了改良。為了保證交叉操作后的子代個體依然滿足周課時數規則，在設計交叉操作時對交叉點的選取做了限制：只有兩個父代染色體在交叉點前基因值為1的個數相同時，才允許交叉。交叉得到的兩個子代個體分別繼承了父代的部分基因。

3）變異算子（Mutation）。選擇算子和交叉算子的引入已經能夠保證遺傳算法逐代促進種群進化，但是并不能保證找到種群中沒有出現過的優秀個體。因此，單純通過選擇操作和交叉操作有可能只能得到局部最優解，而非全局最優解。遺傳算法為了解決這一問題，引入了變異算子。變異操作是根據變異率pm將個體染色體中的部分基因值換成其他基因值，其結果是產生一個全新的個體。變異操作是遺傳算法中生成新個體的另一種方式，它不僅增強了遺傳算法的全局搜索能力，而且能夠使種群具備多樣性。

變異是模擬物種繁衍過程中基因突變而引入的遺傳操作。在由初始種群中代表課表的大量隨機個體逐代進化為完全符合學校教學需要的有效課表的過程中，變異操作的作用也至關重要。本文中設計的變異操作過程是這樣設計的：進行變異操作前，在個體染色體上任意選取兩個變異點a，b，定義變異前的個體染色體為chromosome；為了保證變異產生的新個體依然滿足周課時數規則，在設計變異操作時對變異點的選取做了限制，只有當chromosome[a]+

chromosome[b]=1時才能進行變異操作；通過交換chromosome

[a]、chromosome[b]的數值，就產生了全新的個體。

算法控制參數和終止條件

1）控制參數。遺傳算法中控制參數（包括群體規模N、交叉率pc、變異率pm）的選取不同，對算法的性能和結果影響很大，要想得到遺傳算法的最優性能，必須確定最優參數的設置[11]。這里采用自適應策略調整交叉率pc和變異率pm，不僅提高了遺傳算法的搜索效率和速度，而且可以抑制未成熟過早收斂，還能防止優良個體染色體遭到破壞。為此，定義某代種群中最優個體的適應度為fmax，種群的平均適應度以表示，定義f′為k-交換變異個體的適應度，是兩個待交叉父代個體中適應度較大的一個，交叉率pc、變異率pm分別通過以下公式得到：

其中，k1、k2、k3、k4為小于等于1.0的常數。對于k2、

k4，因為或者，個體適應度低于種群平均適應度，于是給予較大的pc、pm，加大適應度差個體染色體被破壞的概率；而k1、k3可根據需要動態調節。pc一般在

0.75～0.95之間，pm 一般為0.005～0.01。

2）終止條件。遺傳算法本質是模擬生物的進化與遺傳，依據“生存競爭”和“優勝劣汰”的原則，借助選擇、交叉和變異等操作，使所要解決的問題經過多次迭代計算，從初始解一步步逼近最優解[12]。這些操作使得遺傳算法具備很強的全局搜索能力，同時造成其結果受到隨機性的干擾。為避免算法缺乏有效的迭代停止條件，本文設計幾種終止條件：如果種群進化至1000代，則終止算法；如果某代種群中個體的平均適應度與當代最優個體適應度的比值大于0.9時，則終止算法；如果最優個體持續保持10代，則終止算法。

以上設計的三種終止條件，遺傳算法執行過程中如果符合其中任意一個條件，即認為算法達到收斂，可終止算法并返回排課結果。

3 結語

本文結合新形勢下排課的實際問題，立足工作實踐經驗，總結抽象構建出排課問題的數學模型，并在傳統遺傳算法的基礎上做了一系列改進來求解排課問題。本文針對排課數學模型設計了專門的染色體結構，優化了初始種群的生成過程，并在標準遺傳算法的基礎上對選擇算子、交叉算子和變異算子等多方面進行改進，采用自適應策略調整交叉率pc和變異率pm，并借鑒模擬退火算法的思想調整個體適應度，根據適應度，按輪盤賭法和最佳個體保存選擇策略復制子代染色體。目前，該算法已成功應用在東華博育云有限公司的排課產品中，實驗表明能得到較滿意的課程安排方案，運行效率高，課表中出現資源沖突現象顯著減少，極大地縮短了學校教務管理人員排課工作消耗的時間。endprint

博育云是上市公司東華軟件股份公司旗下的智慧教育服務平臺，由東華博育云有限公司負責研發和運營，致力于為全國教育行業用戶提供優質的信息化產品。博育云教育產品以國家政策為依據，以“博創治教、智慧育人”為核心理念，應用系統貫穿教育活動中教、學、研、評、考、管等多個環節，并基于大數據、云計算、虛擬化、移動互聯等技術，為用戶提供區域智慧教育綜合解決方案、數字化校園解決方案，打造云時代以新高考解決方案為核心的教育服務商。

參考文獻

[1]Saleh H A， Chelouah R. The design of the global navigation satellite system surveying networks using genetic algorithms[J].Engineering Applications of Artificial Intelligence，2004，17（1）：111-122.

[2]Tao Q， Liu X， Xue M. A Dynamic genetic algorithm based on continuous neural networks for a kind of nonconvex optimization problems[J].Applied Mathematics and Computation，2004，150（3）：811-820.

[3]賀波.基于帶時間窗集送貨雙需求巡回車輛路徑優化問題研究[D].北京：北京科技大學，2011：27-28.

[4]陳冬亮.排課的數學模型和算法在教務管理系統中的應用研究[J].電腦知識與技術：學術交流，2006（6）：12.

[5]席少霖.非線性最優化方法[M].北京：高等教育出版社，1992.

[6]Coello C A C. Theoretical and numerical constrainthandling techniques used with evolutionary algorithms： a survey of the state of the art[J].Computer Methods in Applied Mechanics & ngineering，2002，191（11）：1245-1287.

[7]郭建蓬，王可人，海磊.MANET中基于遺傳算法的帶寬計算[J].計算機工程與應用，2005，41（26）：154-157.

[8]Nandakumar P， Rummel J L， Hartvigsen D， etc. A Subpath Ejection Method for the Vehicle Routing Problem[J].Management Science，1998，44（10）：1447-1459.

[9]Angel E， Bampis E， Pascual F. An exponential （matching based） neighborhood for the vehicle routing problem[J].Journal of Combinatorial Optimization，2008，15（2）：179-190.

[10]潘正君，康立山，陳毓屏.演化計算[M].北京：清華大學出版社，1998.

[11]吳少巖，許卓群.遺傳算法中遺傳算子的啟發式構造策略[J].計算機學報，1998（11）：1003-1008.

[12]云慶夏，黃光球，王戰權.遺傳算法和遺傳規劃：一種搜索尋優技術[M].北京：冶金工業出版社，1997.endprint