遺傳算法在高校排課調課中的應用

葛曉春 彭俊文

摘要：高校排課中待解決的主要問題就是合理的安排教師、教室、時間、班級等教學資源。大多數遺傳算法對排課的應用考慮的是節次優先等問題，而對排課中的教學資源沖突采用消除的辦法解決。針對排課中的沖突，該文以班級、時間、教室為三維坐標空間，以排課中存在的沖突數為適應度函數，采用平面交叉的方式，通過精英保留策略構造遺傳種群進行選擇進化。

關鍵詞：遺傳算法;三維編碼;沖突函數;平面交叉;精英保留

中圖分類號：TP301.6 文獻標識碼：A

文章編號：1009-3044（2019）32-0080-02

1概述

隨著高校的不斷擴招，對高校教學資源的合理分配顯得越來越重要，其直接影響到高校的正常教學工作的開展。尤其是新學期開學時對高校內的課程安排問題最為突出。排課問題中，涉及了任課教師、教室、教學班、任課時間等多種因素，而我們首要解決的便是在存在大量教師、教室、教學班、認可時間等情況下找到一種合理的排課方案，例如：同一時間同一老師不能出任兩門課程等。

排課問題是一個復雜的、多約束的組合問題。國外從20世紀50年代末開始對排課問題進行研究，并在S.Even和Cooper的論文中被證明這是一個NP完全問題。在意識到無法求出排課問題的精確解的情況下，科學家們致力于研究新的排課算法并應用于實際當中，例如Ferland等提出的將整數規劃用于排課算法，然而由于該算法計算量大，只能運用于小型課表的編排。

2基于遺傳算法的排課理論

遺傳算法（Genetic Algorithm，簡稱GA）是一種模擬生物自然進化過程的優化算法，它由美國Michigan大學的Holland教授于1975年首先提出，并吸引了大批學者進行研究與推廣。

高校排課的實質就是利用本校有限的資源，合理的安排教師和學生的授課任務。通常，在高校中都是以班為單位參與到教學計劃的制定當中，因此排課當中涉及的因素有教室、教師、班級、時間、課程等因素。其次，在實際當中，教師與課程是對應的，即對一門固定的課程，其任課老師會提前確定下來。再有，對每一個班級，其所上課程是確定的。而不同班級之間又相互關聯，即可能存在同一教師擔任不同班級的某一門課程的授課任務或者不同班級可能存在占用同一間教室的情況。排課所對應的任務便是為不同班級合理的安排授課時間以及地點，以使其不產生沖突。一個合理的排課方案必須滿足以下要求：

同一時間同一教師不能出任一門以上的課程;

同一時間同一教室不能安排一門以上的課程;

同一時間同一班級不能安排一門以上的課程。

2.1遺傳算法的基本思想

遺傳算法是從代表問題的可能潛在的解集的一個種群開始的，而一個種群是由經過基因編碼的一定數目的個體組成。初始種群產生后，根據適者生存和優勝劣汰的原則，逐代演化產生越來越好的個體。而逐代演化的過程則是根據當代種群中個體適應度的優良挑選出父代，并根據遺傳學中的遺傳算子進行交叉與變異等產生子代，子代又組成新的種群。如此，使得每一代的個體越來越優秀，即所求問題的解越趨近真實解。

2.2排課問題的遺傳算法模型

2.2.1編碼

使用遺傳算法首要考慮的便是如何編碼，即怎樣將問題與遺傳算法對應起來。例如，求一個一元函數的極大值問題，可將自變量用二進制的方式編碼，這樣既利于計算機的計算又方便執行遺傳算法中的交叉、變異等操作。排課問題中，課程與教師的關系為多對一、班級與課程的關系為一對多，而教室與班級、課程并無實際聯系。由此，可采用三維網格的形式將一張課表完整的表示。

建立三維坐標系，以x軸表示班級，y軸表示時間段，z軸表示教室，如圖1所示。

此時，若通過x軸上某一點，得到平行于yoz平面的切面，該平面上又有許多網格節點，如圖2。

將x軸上對應班級下的課程按照一個網格節點至多填充一門課程一教師對的原則全部填人上述平面的網格節點中，即該班級的課程安排完成。對于剩下的班級以此類推，由此一個課表的編碼完成。

2.2.2個體適應度函數

自然選擇過程中，適者生存、優勝劣汰的法則普遍存在。而評判個體是否較其他個體優秀則是根據其對環境的適應來確定。在排課問題中，個體代表一張課表，其適應度越高則表示越趨近合理。因此，排課問題的適應度可由課表中存在的沖突數來反映，沖突越多則表明是適應度越低。故本問題的適應度函數可由如下公式計算：

其中，fllness為個體適應度，clashes為個體存在的沖突數量。當適應度為1時，說明該個體所表示的課表合理。

2.2.3選擇

生物的進化時通過自然選擇來完成的，在遺傳算法理論中，搜索解通過選擇操作來達成。常見的選擇操作有賭輪盤選擇以及錦標賽選擇，而錦標賽選擇更具通用性，且性能更優。錦標賽選擇策略每次從種群中隨機取出一定數量的個體（放回抽樣），然后選擇其中最好的一個個體進入子代種群。通常采用二元錦標賽選擇，即每次隨機取出2個個體。

2.2.4交叉

交叉操作在遺傳算法起到核心作用，通過交叉使得遺傳算法的搜索能力大大增加，同時使子代更容易出現優良的基因模式。排課問題中，不能在不同班級之間進行交叉操作，否則會破壞課表結構。遺傳算法中，常見的交叉方式主要有單點交叉、兩點交叉以及多點交叉等。其中，兩點交叉的原理為隨機選擇染色體上的2個位置，將兩者中間的基因片段互換。本文根據編碼結構，結合兩點交叉原理，設計了排課問題的面交叉方式。操作如下：

1）隨機選擇編碼結構中的某一個班級;

2）將父代中該班級對應的平行于教室一時間平面的切面相互交換;

3）檢測交換后生成的子代適應度;若適應度更低則返回1），否則交叉結束。

2.2.5變異

遺傳算法中，變異操作保持了種群的多樣性，同時防止遺傳算法的過早收斂。在基于二進制編碼的遺傳算法中，變異操作一般是對0-1二進制串中的某一位進行求反操作。例如，將0變為1或將1變為0。在排課問題中，一個班級下的課程不能改變的原則不變，因此變異操作可用如下方法進行：

1）隨機選擇編碼結構中的某一個班級;

2）隨機選擇該班級下某兩個時間段;

3）交換步驟2）中選擇的兩個時間段中的教師一課程對，變異結束。

2.2.6精英保留策略

對遺傳算法來講，能否收斂到全局最優解是其首要解決的問題，而Rudoph已經采用有限馬爾可夫鏈理論證明了僅采用交叉、變異和選擇（比例選擇法）三個標準遺傳算子的遺傳算法不能收斂到全局最優解。“精英保留”策略是De Jong針對遺傳算法提出的，該策略保證了遺傳算法的全局收斂性。在排課問題中，采用群體“精英保留”策略，即：將父代種群和子代種群合并后，選擇其中最優的N個（種群大小）個體構成下一代種群。

2.2.7算法結束條件

算法本身不能無限制的執行下去，因此必須設置排課算法的結束條件。對于排課問題，算法結束標志著找到一個最優解或者沒有找到，因此根據適應度值為1可判斷算法結束，此時找到最優解;其次，設置算法的最大迭代次數，若算法執行完了最大迭代次數還沒有找到最優解則強制結束。

在算法結束后，輸出的原始結果為一條經過編碼的染色體，即課表。通過解碼的方式可找到任意班級、教室、教師的課表。

3結束語

本文通過分析高校排課問題中存在的主要問題，結合遺傳算法理論，構造三維編碼模式，極大地降低了排課問題中的沖突量。同時，在編碼方案的基礎上通過平面交叉的方式，結合“群體精英保留”策略實現排課算法理論。考慮的遺傳算法的并行性，該算法在計算機上能快速穩定的進行排課求解。