遺傳算法在排課問題中的改進研究

劉二鋼 黃榮芳 龍映宏

關鍵詞：排課；遺傳算法；智能排課；交叉；變異

0 引言

排課問題本質上是時空排列組合問題，即將教學中的班級、教師、課室等元素在時間上進行有序組合，從而使整個教學活動正常有序高效運行。近年來，由于高校辦學規模不斷擴大，課程安排規模逐年遞增，給課表的編排帶來一定困難。并且高校課表在編排過程中受到教室類型、專業要求等限制條件較多，結構更為復雜。因此編排出合理、科學的課表難度較大，需要花費大量的時間和精力，以往完全依靠人工的排課方式已不合時宜。

遺傳算法本身是一種仿生算法，算法是在達爾文的生物進化論和孟德爾的遺傳變異理論基礎上，通過模擬生物進化過程而構造的一種自適應啟發式全局優化搜索算法[1]。遺傳算法最早是由美國密歇根大學的約翰·霍蘭德（John H.Holland，1929-2015） 教授創建的，約翰教授也因此被稱為遺傳算法之父。遺傳算法除了結構簡單之外還具有全局搜索能力強、信息處理過程可以隱形魯棒性和并行性等特殊優勢，在數據挖掘、圖像處理、機器學習、自動控制、組合優化以及模式識別等領域有著非常廣泛的應用[2]。

近年來隨著信息技術及人工智能的不斷發展，計算機應用技術已經逐步深入人類社會的各個領域，起到極其重要的作用。通過計算機自動排課，本身具有手工排課無法比擬的諸多優點，例如：排課過程速度快、省時省力，排課結果查找方便、檢索迅速、可靠性較高。另外計算機存儲還可以保證保密性好、存儲量大，最終使得整個排課過程人工成本降低、使用壽命加長[3]。通過上述優點，不僅可以相應提高排課效率，還可以使管理人員更加有效地看到各種資源的使用情況，從而更好地分配和利用教學資源，也便于解決教室臨時借用、教師調停課等實時問題。因此計算機智能排課能夠推動教學活動良性循環，從而提高教學質量。

1 排課問題

實際過程中，排課規則需要受到各種條件約束，因此隨機產生的排課結果不可避免會產生大量沖突。一個好的課表必須做到統籌兼顧，既要滿足教學需要，又要為管理者提供決策依據，使排課結果滿足大多數師生的要求。

對上述問題進行歸納，主要解決兩類問題：一是解決教師、課室、班級等在時間上的沖突，此類問題必須解決，通常稱之為硬約束；二是解決教師個性需求、教學效果等特殊要求，使得課表編排能夠更加合理，此類問題應盡量滿足，通常稱之為軟約束。

硬約束主要包括：

1） 同一個時間一名教師只能在一個課室上課；

2） 同一個時間一個班級只能在一個課室上課；

3） 同一個時間，一間課室不能同時上一門以上的課程[4]；

4） 課室提供的座位數要大于或等于班級學生數。

軟約束主要包括：

1） 個別教師（如外聘教師）提出對于上課時間的特殊需要；

2） 同一個班級在一周內的同一門課程在時間安排上能夠有一定的間隔；

3） 同一個班級或同一名教師在一天內相鄰時間片所安排的課室能夠盡量相同或接近，以避免師生遠距離地更換課室；

4） 重要課程能夠盡量安排在較好的時間節次。

2 排課過程當中的相關遺傳算法設計

2.1 編碼與染色體設計

編碼與染色體是設計算法的兩個關鍵因素，染色體就是構造編碼之后生成的編碼串。染色體中的每一位稱之為基因，多個基因構造的有效信息段稱之為基因組。染色體不斷進化，最后需要的結果就是得出相對適宜的染色體。在算法實現過程中，通常以一周作為基本單位，整個學期可以看作是一周課程的多次重復。

根據上述的分析過程，首先將排課過程中的多個元素相互結合起來，根據辦學規模進行編碼，其中主要元素包括：

在排課操作前，首先考慮學校的多種元素。設有R間教室，一周有T（每天上課節次×一周上課天數）個時間段上課時間，則一周的教學任務就可以安排于R×T個時空單元內。如果將所有時空單元按照一定序列排序，就可以構成一個有序的時空數組。然后考慮每門課程的課程ID，教師ID和班級ID。由于課程對于同一個教學班也會存在重復的現象，比如一個班級一周上課多次，因此必須考慮主鍵，否則會有重復記錄產生。將上述要素設定好后進行組合，構建的基因序列如圖1所示：

基因序列構建完成之后，通過算法的演化過程，適應度高的基因能夠留下，適應度差的基因相應去除，隨后進入下一輪演化過程。如此反復循環，直到遺傳算法整體終止或滿足所設定的結束條件，整個算法即表示完成。

多個基因組合之后構造成為染色體，染色體構造完成后生成一條排課記錄，將所有的排課記錄在數據庫二維表中，就構成了一種排課方案。有了排課方案，后續就可以根據適應度函數對排課方案進行評估。

2.2 適應度評估

適應度評估實際上是對排課結果的一種判斷，一般用函數值來評估排課結果的優劣。適應度函數（Fit?ness Function）的選取將會直接對遺傳算法的收斂速度及能否找到最優解產生影響[5]。由于遺傳算法在搜索進化中基本不利用外部信息，僅以適應度函數作為依據，利用種群個體的適應度來進行搜索[6]。并且遺傳算法需要得到非負的可比較結果，從而進行優劣比較，這也是遺傳算法能夠量化并廣泛應用的主要原因，因此適應度函數設計非常關鍵。

通常來講，適應度函數需要滿足下述條件：其本身是一個連續的實函數，其上每個點與之相匹配的適應度值和染色體好壞成反比。函數對可導并無要求，但設計應盡量簡單，參數盡可能少。

排課過程中，需要滿足硬約束和軟約束兩個指標。硬約束在上述方案中已經得到滿足，但課室的座位數并不一定能夠滿足學生的選課人數，因此在適應度函數計算時必須加以考慮，而軟約束主要考慮以下幾個指標：

1） 班級課程分散程度，用指標u1表示；

2） 課程時段優度，用指標u2表示；

3） 教師課時分散程度，用指標u3表示。

則整體的適應度函數可以設計如下：

其中，? 表示教室座位數滿足容納學生選課人數的平均值，α 是班級課程分散程度的全校平均值，β 表示課程時段優度平均值，γ 表示教師課程分散程度平均值。

2.3 初始種群的生成改進

初始種群創建之后，遺傳算法才能開始進行演化。通常初始種群的創建都是隨機生成，如果創建的初始種群搜索空間越大，在空間上分布得越均勻，就越有利于全局最優解的尋找[7]。

種群的生成改進則是在此基礎之上，根據每次隨機產生的新個體與已存在的個體進行比較，如果相關排列順序與已存在個體排列順序相同，則需要棄用此產生個體，重新生成新個體。這樣就能限制初始種群中相似個體總數。

2.4 遺傳操作

遺傳主要包含選擇、交叉和變異三種操作方式，對于各種方式都可進行改進。主要改進方法包括：

1） 選擇操作的改進

在排課過程中，衡量排課結果優劣的主要參數是適應度。在種群選擇中初期采用賭輪選擇法比較合適。該方法使得適應度高的個體更容易被選中，從而更容易產生優質的后代。賭輪選擇法每次從輪盤中的較大區域通過隨機選擇若干個遺傳樣本到下一代。在進化過程中，該算法能夠保證種群中最優個體被保留，最差個體被淘汰，從而使得種群整體被優化[8]。

考慮到初始種群適應度參差不齊，適應度低的個體也并非毫無價值，在算法演算的初始階段采用賭輪方式比較適宜，可以有效地保留各類個體。但在算法演化過程的后半階段，種群發展已經比較成熟，適應度高的個體普遍已經缺陷較少，質量較好，此時已經沒有必要保留所有個體，可以將適應度差的個體放心淘汰。此時應對算法改進，將賭輪算法修改為錦標賽選擇法，即將種群個體隨機分組，并按適應度大小排名，每個組排名靠前的個體將直接進入下一輪[9]。錦標賽選擇法更容易淘汰劣質個體，保留優質個體，使得算法演化速度更快。

2） 交叉操作的改進

在算法演算過程中，將隨機產生的交叉點已經產生的染色體分成兩個基因片段，形成左右兩個子染色體，然后將左右兩個子染色體進行對調，形成了新染色體，這就是交叉算法的本質。鑒于此過程會產生重復課程，因而交叉算法不能隨意對調，必須進行改進。如果在交叉過程中采用多個交叉點，就構成了多點交叉。

目前遺傳算法在排課問題中對于交叉操作都是基于單點交叉或多點交叉的一種交叉方式，這兩種方式各有特點。單點交叉容易破壞優秀基因，而多點交叉又不利于優秀基因的擴散。因此，本文采取將兩種理論進行結合，即前期使用多點交叉，便于優秀基因擴散；后期采用單點交叉，此時的迭代過程已經使得優秀基因比較穩定，單點交叉已不易破壞其完整性。

3） 變異操作的改進

交叉和變異是影響算法搜索最優解質量的關鍵要素，尤其是在算法的收斂性方面。算法的變異因子在演化過程中可以有效防止過早收斂而無法得到全局最優解的局面，可以據此對算法進行變異改進。

首先需要對種群中的大多數基因進行變量優化。由于此類基因本身適應度小，通過優化后再進行迭代，就會使得最終結果發生改變，從而趨向于最優解。但是由于早熟發生，需要進行變異操作，才能產生比剩余基因更好的基因，這樣算法的搜索空間變得更小，尋優速度更快，進而解決原來遺傳算法的早熟問題和易陷入局部最優解的問題。通過變異操作還可以相應減少遺傳算法的進化迭代次數，并更早得到最優解[11]。

2.5 算法的終止條件

遺傳算法由于客觀條件限制，可能會產生無限循環的情況，因此一般需要設定算法終止條件。一般來講，算法迭代次數設置為300～500次。如果在迭代次數到達之前，已經出現了滿足條件，則算法可以提前結束，此時得到的就是最優解；如果達到了設定的循環條件仍沒有滿足約定結果，則將此時的最優解作為問題最終解。

2.6 對于沖突檢測方法的優化

由于排課問題本身屬于NP（Nondeterministic Poly?nomially，非確定性多項式）問題，因此排課沖突無法避免，例如一個班級可能在相同時間段內被安排了多門課程，又或者是一間教室被安排了多個班級同時上課[12]。解決的方法是引入沖突檢測函數，通過沖突檢測函數防止沖突發生。所有排課過程結束之后，利用沖突檢測函數判斷排課結果是否有沖突，并對結果進行相應調整。

2.7 排課改進算法流程

通過上述討論，排課問題改進算法流程如圖2所示。

3 算法仿真實驗及結果分析

為檢測改進算法的性能，以某高校機電工程學院2021—2022 年第1 學期的排課過程為例進行分析。實驗過程對使用遺傳算法和改進的遺傳算法進行編程測試，在內存8.0 G和CPU3.8 GHz的計算機運行結果。實驗中將種群設置為120，實驗主要考察算法出現較優解的次數和平均運行時間兩個指標。

實驗結果中采用兩種方式后，采用同樣的算法及同樣的適應度函數。假設迭代次數分別為50、100、150、200、250、300、350，即每次運行50次迭代步數，分別記錄算法的平均運行時間和最優解運行次數兩個運算指標，實驗結果如圖3、圖4所示。

從實驗結果可以看出，本文提出的辦法在一定程度上解決了傳統遺傳算法所帶來的隨機早熟收斂問題，并在此基礎上提升了算法的尋優能力和收斂速度，使得遺傳操作更具有規律，整個運行過程也更平穩，并且適應度方面及操作收斂效果上略有提高，后續可以在此基礎上進一步完善。

4 總結

本文在介紹遺傳算法的基礎上，對初始種群的生成方法以及選擇、交叉、變異等操作進行解析，通過結合多種方法的優缺點后，對相應的步驟提出改進方法，最后將結論應用到實際問題中。實驗證明上述方案使得算法的收斂性和尋優能力在一定程度上都有了相應提升，運算過程也更加平穩，提升了運算精度。結論證明本文算法具有更好的可行性和實用性，可以加以推廣和使用。