高校多校區排課的遺傳算法的改進研究

楊秀玉 雷晶晶

摘 要：隨著計算機技術的不斷發展，教育現代化漸漸進入各大高校，計算機自動排課已經取代了傳統的手工排課，但多校區辦學模式的興起，給排課帶來了新的挑戰。基于傳統的遺傳算法，結合部門的工作經驗，充分考慮各方面的因素，對其進行改進，實現教務管理的科學化。

關鍵詞：多校區;排課;遺傳算法

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

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

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

一、排課問題的分析

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

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

二、遺傳算法的基本原理

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

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

基本遺傳算法的構成要素：

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

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

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

三、排課遺傳算法的改進

（一）減小排課問題維度

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

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

（二）改進傳統的二進制染色體編碼方式

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

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

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

（三）遺傳算子的改進

1.選擇算子

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

2.交叉算子

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

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

3.變異算子

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

參考文獻：

[1]周芬.遺傳算法在多校區排課系統中的應用[J].科技信息，2010（06）：234.

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

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

[4]凌敏.基于遺傳算法的多校區排課系統的設計與實現[D].湖南大學，2015.

[5]李琳.多校區高校自動排課系統的研究與設計[D].電子科技大學，2013.

基金項目：2019年中央高校建設世界一流大學（學科）和特色發展引導專項資金支持（D201903）

作者簡介：楊秀玉（1993—），女，四川內江人，碩士，研究實習員，研究方向：教學管理。