遺傳算法在高校排課調(diào)課中的應(yīng)用

葛曉春 彭俊文

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

關(guān)鍵詞：遺傳算法;三維編碼;沖突函數(shù);平面交叉;精英保留

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

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

1概述

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

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

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

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

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

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

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

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

2.1遺傳算法的基本思想

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

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

2.2.1編碼

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

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

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

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

2.2.2個體適應(yīng)度函數(shù)

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

其中，fllness為個體適應(yīng)度，clashes為個體存在的沖突數(shù)量。當(dāng)適應(yīng)度為1時，說明該個體所表示的課表合理。

2.2.3選擇

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

2.2.4交叉

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

1）隨機選擇編碼結(jié)構(gòu)中的某一個班級;

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

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

2.2.5變異

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

1）隨機選擇編碼結(jié)構(gòu)中的某一個班級;

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

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

2.2.6精英保留策略

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

2.2.7算法結(jié)束條件

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

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

3結(jié)束語

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