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

劉二鋼 黃榮芳 龍映宏

關(guān)鍵詞：排課；遺傳算法；智能排課；交叉；變異

0 引言

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

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

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

1 排課問題

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

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

硬約束主要包括：

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

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

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

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

軟約束主要包括：

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

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

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

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

2 排課過程當中的相關(guān)遺傳算法設(shè)計

2.1 編碼與染色體設(shè)計

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

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

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

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

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

2.2 適應(yīng)度評估

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

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

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

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

2） 課程時段優(yōu)度，用指標u2表示；

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

則整體的適應(yīng)度函數(shù)可以設(shè)計如下：

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

2.3 初始種群的生成改進

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

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

2.4 遺傳操作

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

1） 選擇操作的改進

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

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

2） 交叉操作的改進

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

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

3） 變異操作的改進

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

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

2.5 算法的終止條件

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

2.6 對于沖突檢測方法的優(yōu)化

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

2.7 排課改進算法流程

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

3 算法仿真實驗及結(jié)果分析

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

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

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

4 總結(jié)

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