高校多校區(qū)排課的遺傳算法的改進研究

楊秀玉 雷晶晶

摘 要：隨著計算機技術(shù)的不斷發(fā)展，教育現(xiàn)代化漸漸進入各大高校，計算機自動排課已經(jīng)取代了傳統(tǒng)的手工排課，但多校區(qū)辦學(xué)模式的興起，給排課帶來了新的挑戰(zhàn)。基于傳統(tǒng)的遺傳算法，結(jié)合部門的工作經(jīng)驗，充分考慮各方面的因素，對其進行改進，實現(xiàn)教務(wù)管理的科學(xué)化。

關(guān)鍵詞：多校區(qū);排課;遺傳算法

Abstract：With the development of computer technology，the modernization of education has gradually entered major universities.Computer automatic scheduling has replaced the traditional manual scheduling，but the rise of the multi-campus mode of schooling has brought new challenges to the scheduling.Based on the traditional genetic algorithm，fully considered various factors，and improved it，to realize the scientific management of educational administration.

Key words：multi-campus;course scheduling;genetic algorithm

隨著社會經(jīng)濟的不斷發(fā)展和高等教育大眾化進程的推進，高校招生規(guī)模不斷擴大，越來越多的學(xué)生參加高考進入大學(xué)接受高等教育。由于大部分高校建校早，配套設(shè)施已經(jīng)不能滿足不斷擴大的招生規(guī)模，形成了多校區(qū)辦學(xué)新格局。目前要保證多校區(qū)協(xié)同排課，實現(xiàn)資源共享，尋求多校區(qū)排課對資源利用的最優(yōu)化。

課表是各個學(xué)校組織與實施教學(xué)過程的主要依據(jù)，是學(xué)校教學(xué)工作有計劃、有秩序進行的重要保證。科學(xué)合理地編排、調(diào)度、執(zhí)行課表是順利實施人才培養(yǎng)方案，建立良好教學(xué)秩序的基礎(chǔ)。因此，排課是高校教務(wù)工作過程中必須面對的問題，科學(xué)、規(guī)范的排課是獲得高水平教學(xué)質(zhì)量的必要條件，也是教學(xué)管理中最為關(guān)鍵的一環(huán)。它涉及到的因素很多，是一個多約束、多目標的優(yōu)化問題，已經(jīng)被深入研究并被公認是NP完全問題。[1]目前，單校區(qū)的排課普遍采用傳統(tǒng)的遺傳算法，但多校區(qū)排課涉及老師在不同校區(qū)上課、教室分配等問題，復(fù)雜程度明顯提升，傳統(tǒng)的遺傳算法不能滿足需求。

一、排課問題的分析

隨著各大高校的擴招，學(xué)生數(shù)量不斷增長，教學(xué)資源也越發(fā)緊張，高校也紛紛擴建校區(qū)，使得多校區(qū)排課成為一項繁重而復(fù)雜的工作。多校區(qū)辦學(xué)，一學(xué)期幾百甚至上千門課程，課程的特殊性，老師的特殊要求，學(xué)校根據(jù)現(xiàn)狀的特別指示等因素都要考慮在內(nèi)，并合理地協(xié)調(diào)安排涉及的專業(yè)、老師、學(xué)生，同時要對幾百甚至上千門課程進行合理地組織安排。

排課本身就是處理教學(xué)環(huán)節(jié)中的各種矛盾、解決教師與學(xué)生雙邊活動、推動教學(xué)工作向前發(fā)展的有效工作。排課的過程中出現(xiàn)的矛盾是班級、課程、教師、時間、教室、校區(qū)在排列組合中所發(fā)生的沖突和矛盾，它們也是排課過程中的約束。課表的編排必須準確無誤、科學(xué)化、合理化，以保證教學(xué)過程的正常運轉(zhuǎn)。排課涉及的因素很多，應(yīng)堅持以“綱”為本，以“人”為本，以“校”為本的三原則。以“綱”為本中的“綱”是指培養(yǎng)方案和教學(xué)任務(wù)，兩者都是排課工作的重要依據(jù)，是排課必須堅持的基本原則;以“人”為本是指考慮學(xué)生和老師在教學(xué)運行過程中的合理性，排課必須遵循教育教學(xué)規(guī)律，堅持“以人為本、以學(xué)為主”和“一切為了學(xué)生，為了學(xué)生一切”的教學(xué)理念，重視學(xué)生的身心健康，考慮學(xué)生的接受能力，保障課表編排的科學(xué)性、合理性;以“校”為本指考慮本校的校情，多校區(qū)排課需將不同的校區(qū)在系統(tǒng)中進行不同的設(shè)置，確保排課沒有人為造成的低級錯誤。[2]

二、遺傳算法的基本原理

遺傳算法是計算數(shù)學(xué)中用于解決最佳化的搜索算法，其特點是搜索群體和種群中個體之間的信息交換，可以用于對傳統(tǒng)方法非線性的、難以解決的、復(fù)雜問題的處理[3]。

遺傳算法的基本思想是從問題可能潛在解集的一個初始種群開始，再逐代演化產(chǎn)生出越來越好的近似解。在每一代根據(jù)問題域中個體的適應(yīng)度大小挑選，利用自然遺傳學(xué)的遺傳算子進行組合交叉和變異，產(chǎn)生出新的解集種群。這個過程將使得種群像自然進化一樣的后代，比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼，可以作為問題近似最優(yōu)解。

基本遺傳算法的構(gòu)成要素：

（1）染色體編碼。基本遺傳算法使用固定長度的二進制符號串來表示群體中的個體。初始群體中各個個體的基因值可用均勻分布的隨機數(shù)來生成。

（2）適應(yīng)度函數(shù)。基本遺傳算法按與個體適應(yīng)度成正比的概率來決定當(dāng)前群體中個體遺傳到下一代群體中的機會。遺傳算法是以適應(yīng)度函數(shù)為唯一反饋標準，也就是通過適應(yīng)度函數(shù)值的大小來判斷染色體的優(yōu)劣，決定染色體是否保留到下一代。[4]

（3）遺傳算子。基本遺傳算法使用選擇、交叉、變異三種遺傳算子。

三、排課遺傳算法的改進

（一）減小排課問題維度

多校區(qū)排課屬于涉及課程、班級、教師、教室、時間、校區(qū)的六元組合問題，多校區(qū)課表就是將這些六種因素進行合理整合，在滿足各種約束條件下，保證教學(xué)任務(wù)的順利完成。以{K、C、L、R、T、U}表示六元組合。

考慮到六維變量的復(fù)雜性，即使處理小規(guī)模的問題也很繁雜，因此本文將六維變量簡化為二維變量。任課老師教授哪些課程是由各二級學(xué)院相應(yīng)的教研室主任在前一學(xué)期期末就在教學(xué)計劃的落實里安排好了的，各個專業(yè)所對應(yīng)的班級在某學(xué)期需要開設(shè)的課程也是由培養(yǎng)方案確定好的，因此，班級C、課程K、教師L的組合基本已經(jīng)確定，由Q來表示，Q={C，K，L};教室R已經(jīng)包含了校區(qū)U的信息，用時間與教室的笛卡爾積用N表示，N=T*R;進行Q與N的組合，則六元組合的排課問題簡化為（Q，N）二元組問題。

（二）改進傳統(tǒng)的二進制染色體編碼方式

染色體的編碼方式極大地影響著交叉、變異等遺傳算子的運算方法和程序?qū)崿F(xiàn)的時間復(fù)雜度。遺傳算法的編碼方式很多，傳統(tǒng)的也是最常見的是二進制編碼，由于二進制編碼不太適用于多約束且復(fù)雜的高校課程編排，因此根據(jù)實際需求，改進遺傳算法采用二維資源片十進制編碼方式進行編碼。它便于計算適應(yīng)度函數(shù)，減小時間和程序復(fù)雜程度，方便生成初始種群，便于檢測交叉和變異中的沖突。

結(jié)合實際分析，采用二維資源片十進制編碼代替?zhèn)鹘y(tǒng)的二進制編碼形式進行編碼。以某高校為例，由于該校兩小節(jié)課由同一位老師授課，且教室不會改變，班級不會改變，把兩小節(jié)課合并成一大節(jié)課，因此把兩小節(jié)課作為一個時間片，允許排課的時間為周一至周五，每天不超過四大節(jié)課，一周總共20個時間片，把{11，12，13，14，21，22，…，52，53，54}作為時間片集合，其中集合{11}表示星期一的第1節(jié)課，集合{21}表示星期二的第1大節(jié)課。把{R1，R2，R3，…，Rn}作為教室集合，教室和時間的笛卡爾積共有20*n個資源片空間{（R1，11），（R2，11），（R3，11），…，（Rn，54）}。

采取此種編碼方式進行排課可以確保一項信息只被分配到一個資源片，盡量避免了資源沖突，會更容易地產(chǎn)生初始種群，能縮短種群產(chǎn)生的時間，提升了實用性和排課效率。

（三）遺傳算子的改進

1.選擇算子

選擇的目的是尋找進化過程中最好的個體，確保目前保留下來的個體是最優(yōu)的。在此過程中若遇到更好的，就代替之前保留的，如果遇到?jīng)]當(dāng)前的個體好，就不選擇遇到的這個。選擇方法是計算染色體被選中的概率，保留概率大的。選中某一染色體的概率為：A/B。其中A代表該染色體的適應(yīng)度值，B代表所有染色體的適應(yīng)度值之和。

2.交叉算子

傳統(tǒng)的遺傳算法中有單點交叉和多點交叉兩種，由于要將遺傳算法應(yīng)用于多校區(qū)排課的實際問題中，兩種交叉都有增加沖突的可能，會降低進化效率，因此提出使用元素對交叉，找到染色體中的相同基因片，交叉其中的資源部分，以此得到更優(yōu)的個體，減少沖突的概率。[5]

元素對交叉，交叉前檢測有無沖突，若無沖突進行交叉，若有沖突再次選取交叉基因。隨機取出1對染色體，采用分步交叉方式，產(chǎn)生交叉位，交換該課程中兩個染色體基因中的資源，也就是改變上課的時間教室。該交叉方法，僅對部分交叉，避免了發(fā)生沖突。

3.變異算子

變異可以避免在選擇時漏掉最優(yōu)解，維護種群的多樣性。變異和交叉一樣，變異前檢測有無沖突，若無沖突進行變異，若有沖突重新選擇變異位。變異算子的采用與交叉算子相對應(yīng)，依據(jù)變異概率選出染色體，變換資源。

參考文獻：

[1]周芬.遺傳算法在多校區(qū)排課系統(tǒng)中的應(yīng)用[J].科技信息，2010（06）：234.

[2]李祥.多校區(qū)高校二級教學(xué)管理條件下的排課模式探討[J].科教文匯（中旬刊），2016（02）：132-133.

[3]梁宇滔.基于遺傳算法的多校區(qū)排課系統(tǒng)分析與設(shè)計[J].佛山科學(xué)技術(shù)學(xué)院學(xué)報（自然科學(xué)版），2011，29（06）：75-78.

[4]凌敏.基于遺傳算法的多校區(qū)排課系統(tǒng)的設(shè)計與實現(xiàn)[D].湖南大學(xué)，2015.

[5]李琳.多校區(qū)高校自動排課系統(tǒng)的研究與設(shè)計[D].電子科技大學(xué)，2013.

基金項目：2019年中央高校建設(shè)世界一流大學(xué)（學(xué)科）和特色發(fā)展引導(dǎo)專項資金支持（D201903）

作者簡介：楊秀玉（1993—），女，四川內(nèi)江人，碩士，研究實習(xí)員，研究方向：教學(xué)管理。