基于遺傳算法對高校多校區排課問題的研究目錄TOC\o"1-3"\h\u90671研究背景 摘要：隨著高等教育持續發展，如何實現教學資源的充分利用，實現準確、高效的排定課程，成為了高校教學管理效率提升的關鍵所在。本文基于遺傳算法在全局搜索方面的優勢，設計合理的的目標函數和約束條件，利用遺傳算法框架解決高校多校區的排課問題，并與貪心算法進行對比，力求實現在時間上和空間上做到科學化、人性化。關鍵詞：遺傳算法；NP問題；智能排課；多校區研究背景在高校的日常教學活動中，有計劃的安排每學期教師的授課任務是十分重要的。排課任務對于高校教務是一項重要且復雜的工作，傳統的排課方式往往依賴于人工操作，耗時長、效率低、并且不一定能保證課表不會出現任何錯誤和沖突。因此，智能算法在高校排課中的應用，帶來了多方面的深刻意義，不僅極大地提升了排課的效率和準確性，更在一定程度上優化了教育資源分配，充分考慮多方面約束條件，促進了教學管理的現代化和智能化。隨著技術水平的節節攀升和應用場景的不斷拓展，智能算法在高校排課領域的應用更加廣泛和深入了。排課問題是典型的NP問題，需要考慮多重限制因素，在實際的應用中，根據約束條件的必要性往往劃分為硬約束與軟約束[1]。多年來學者基于不同的應用場景，設計更具針對性的約束條件，并選擇智能算法進行研究。當下主流的智能算法主要包含遺傳算法、蟻群算法、模擬退火算法等，早在2014年張麗麗等人REF_Ref16986\r\h[2]，基于求解排課問題對比了上述三種常用算法的優劣，并闡明了其算法原理與特點。隨后，2020年黃嶺等人REF_Ref17032\r\h[3]又對回溯算法、貪心算法、粒子群優化算法、人工免疫算法、圖著色算法等八種算法做了介紹和分析，并提出了利用k-means算法改進初期選取簇中心點的想法，為今后的各種排課需求提供參考。基于上述研究，人們普遍認同遺傳算法具有優秀的全局搜索能力，初期求解排課問題收斂速度較快，但隨著迭代增加，計算量增大，耗時延長。當下，多數學者利用遺傳算法應用于實際的排課系統中，但為盡可能避免由遺傳算法導致的計算復雜等問題，學者們提出了新的思路，結合蟻群算法的特點，采取遺傳算法與蟻群算法的融合算法解決高校排課問題。先利用遺傳算法生成信息素分布，再利用蟻群算法適用于局部搜索最優解的特點，求出精確解，通過兩者的優勢互補，來獲得良好的優化性能和時間性能REF_Ref17113\r\h[4]。之后，李印坤等人REF_Ref17166\r\h[5]也采用了這種方法，先分析了高職院校的排課特點，考慮單雙周的排課問題，增加相應約束條件，求出最優解。除利用上述融合算法外，也有許多學者基于遺傳算法設計新的初始種群生成方案，改進適應度函數REF_Ref17198\r\h[6]，或改進選擇、變異、交叉過程等REF_Ref17241\r\h[7]，以進一步提升全局搜索能力，簡化計算量，加快收斂速度。同時，也有部分學者將局部搜索能力更強的蟻群算法或貪心算法，應用于排課系統中。韋芳萍REF_Ref17368\r\h[8]提出了基于蟻群算法的智能排課研究，利用二分圖模型實現教學資源的優化分配。貪心算法與蟻群算法雖然在局部搜索方面都有較強的優勢，但兩者有明顯的差異。貪心算法主要是對每一步尋找局部最優解，以此近似達到全局最優解，能夠省去在所有可能解中尋找最優解而必須耗費的大量時間[9]。因此，貪心算法得到的并不是問題的整體最優解，只是滿足貪心策略條件下的最優解。2020年劉丹REF_Ref17335\r\h[10]針對中小學的排課問題采用貪心算法，以設定的約束條件對課程和班級進行排序的順序為貪心策略，利用排序結果依次進行排課。蒙煥念等人[11]則使用優先級鏈表解決課表問題的貪心策略，定義了特有的數據優先級權重，并以權重為基礎生成排課數據的優先級鏈表，以優化設計編碼。當然，利用蟻群算法或貪心算法也不免會陷入局部最優解的問題。雷群泌等人REF_Ref17277\r\h[12]以課表的時間利用率最優為目標提出數學模型，設計一種改進的變異粒子群算法，通過變異增強了種群的自我進化能力和多樣性，避免了算法陷入局部收斂，提高了算法的全局尋優能力。林敏軍[13]還提出了提出了一種新的“靶向干擾制劑”注入方案，改善傳統免疫遺傳算法的局部最優困局，促使算法生成全局最優解。如今，利用智能算法解決排課問題已經成為一種主流研究，通過對上述研究現狀的調研分析，不論選擇何種智能算法，都存在一些不可避免的問題，所以研究者往往針對所選算法的缺陷進行改進。雖然針對排課問題的研究已經取得了很大的進展，并廣泛應用于實際的教學排課中，但仍然存在一些問題，例如：（1）現存的幾種主流智能算法雖有其相關優劣的分析調研，但針對同一應用場景，沒有具體的數據對比；（2）部分研究考慮的現實因素不夠全面，教育資源并沒有得到更加充分的利用；本文將利用遺傳算法，考慮兩校區的排課問題，增加約束條件，設計更加人性化，智能化的排課算法。并基于考慮兩校區的排課問題，對比遺傳算法與貪心算法的性能。遺傳算法算法原理遺傳算法(GeneticAlgorithms，簡稱GA)是一種模擬生物在自然環境中的遺傳和進化過程的自適應全局優化概率搜索算法。它的根本思想是從初始種群出發，借鑒“優勝劣汰、適者生存”的自然生存法則抉擇優質個體，并通過交叉、變異來產生新一代種群，如此逐代進化，直到得到最優解或近似最優解為止。遺傳算法主要包含選擇、交叉和變異三類基本操作。首先隨機生成初始種群，依據算法對象的特征定義基因，并通過編碼操作形成染色體，即種群中的單個元素個體，用于存儲該遺傳結構中的基本數據。其中每個個體都有可能是該問題的最優解，然后根據設定的目標函數，對種群中的每個個體進行適應度計算，模擬自然界中“優勝劣汰，適者生存”的原理，選出精英個體，再隨機配對進行交叉、變異操作，其中交叉是將染色體某些部分的等位基因相互交換，從而產生兩個新的個體。而變異操作則是以設定的變異概率，改變染色體某部分的基因值。因此交叉與變異被認為是遺傳算法中生成新種群的兩種方法。通過上述方法進行種群更新，迭代來逐步搜索最優解，直到找到沒有沖突的解或者達到最大迭代次數為止。算法設計遺傳算法的主要步驟可以歸結為，編碼，生成初始種群，計算適應度，選擇精英個體進行交叉、變異生成新的種群，然后再次計算適應度，迭代求解，直至求出最優解或達到設置的最大進化次數為止（如REF_Ref16343\h圖STYLEREF1\s2-1所示）。算法中的每一步都影響著整體的性能與求出的最優解，因此，每一步的設計都至關重要。圖STYLEREF1\s2-SEQ圖\*ARABIC\s11遺傳算法流程設計圖編碼遺傳算法以參數的編碼為運算對象，常見的編碼方式包含二進制編碼、實數編碼、符號編碼等，不同的編碼形式對于運算的性能也有所不同，在選擇編碼方式時，常常需要考慮對象的特性。排課問題是一個復雜的優化過程，需要涉及班級、教師、課程、教室等多個因素，選擇十進制的編碼方式可以更直觀的將各個要素數字化（如REF_Ref16343\h表STYLEREF1\s2-1所示）。表STYLEREF1\s2-SEQ圖\*ARABIC\s11結合排課因素的編碼形式課程ID班級ID教師ID教室周次節次校區以本文數據為例，記課程集合：（如式（1）所示）L=班級集合：（如式（2）所示）C=教師集合：（如式（3）所示）T=校區A內的教室集合：（如式（4）所示）R=校區B內的教室集合：（如式（5）所示）周次集合：（如式（6）所示）W=節次集合：（如式（7）所示）S=本文僅考慮兩校區的排課問題，校區集合：（如式（8）所示）X=通過這種編碼方式，可以形成一個形如Ll生成初始種群遺傳算法借鑒自然界種群的生存和繁衍規律，隨機生成初始種群，即為父代，每個初始解都是一種排課方案。檢驗沖突矛盾為得到合理優化的排課方案，就需要逐代尋找精英個體，然后再以這些精英個體作為父代，繁衍下一代，即計算適應度，選擇最優解。適應度函數即根據排課要求設計的目標函數。高校的排課問題，主要受課程、教師、教室和時間等因素影響。在實際的排課的過程中，主要解決的問題就是各因素組合后存在的沖突問題。通過認真分析與調研，充分考慮到高校排課中可能引起的各種矛盾，歸納出以下排課因素：時間因素：本文先考慮了一學期內的排課安排。在高校中，通常一學期包含19周，前17周為授課周，后2周為考試周，每周僅在周一至周五安排上課，每天的上課時間分為上午時段和下午時段，且均為4節課時（如REF_Ref16343\h表STYLEREF1\s2-2所示）。表STYLEREF1\s2-2周時間安排二維表星期一星期二星期三星期四星期五8：00-8：45WWWWW8：55-9：40WWWWW10：00-10：45WWWWW10：55-11：40WWWWW14：30-15：15WWWWW15：25-16：10WWWWW16：25-17：10WWWWW17：20-18：05WWWWW教室因素：高校的授課形式明顯有區別于中小學，主要采取走班制，即教室不固定，學生和教師均需要根據課表，在上課時間去到所安排的教室。因此根據教室的編號，容量，以及特定的性質等因素均需要考慮到。本文限制在同一時間內同一間教室只能安排學習一門課程。教師因素：在高校中，雖然每位學生都有具體的專業劃分，但基于培養高素質人才的要求，本專業學生不僅要學習專業課程，還需學習公共課程，和一些專業必備的基礎課程。所以在排課問題中，可能會存在教師對跨專業班級授課的問題。因此，排課前首先應將每個專業每學期的課程安排確定下來，然后根據課程安排，具體分配對應課程專業的教師。除此之外，還應保證在同一時間內，同一位教師只能教授一門課程。校區因素：在此前的排課研究中，許多研究均未考慮到多校區授課問題，但隨著時代的發展，國家對于高校建設的投入增加，許多高校會存在多個校區，并會按照專業將學生分配至不同的校區。針對這一多校區的問題，在排課中經常會考慮當教師安排到不同的校區授課時，兩節課之間的空余時間，是否能夠滿足校區之間的往返。而且如果兩校區之間的距離過遠，教師在一天之內往返于兩個校區授課，所花費的時間與路費過多，沒有體現出課程安排的人性化。本文僅考慮在同一市區內，兩個校區的排課問題。因此，將授課時間分為上午時段和下午時段，若教師在當天的某一時段有授課任務，則在該時段內，教師僅可在一個校區內授課。雖然排課問題牽涉的因素很多，但通過設計合理的判斷依據，仍可以遵循充分利用教育資源，符合教學規律的原則，并尋找出排課的最優解。為更加清晰的顯示出排課中存在的限制因素，現將上述約束條件歸納為以下5條：在同一時間每間教室只能安排一門課程；在同一時間每位教師只能教授一門課程；在同一時間每個班級只能學習一門課程；在同一天上午時段同一位教師的排課僅能分布在一個校區內；在同一天下午時段同一位教師的排課僅能分布在一個校區內以初始生成的種群為例，假設初始種群生成個體的參數設置為m，則在該種群中設計一個循環結構，遍歷種群中的每個個體，對于個體i，根據上述的約束條件逐條判斷，每檢查出一次矛盾，沖突數量加1（如式（9）所示）。之后，以沖突數量最小為目標函數，將該代種群的沖突數量從大到小排序，按照精英個體的參數設置，篩選出精英個體。交叉與變異通過計算適應度，上一代種群中適應度高的個體被保留到了下一代，但是上述步驟僅起到了篩選作用，并不能產生新個體。若要產生新的個體，就需要借助交叉與變異步驟。交叉算子交叉算子在遺傳算法中扮演著至關重要的角色。常見的交叉方法包含單點交叉、多點交叉、部分映射交叉等。不同的交叉方式具有不同的特性，單點交叉是指在父代個體中，在染色體上隨機選擇一個交叉點，然后將該交叉點后的全部基因進行互換，從而生成兩個新的子代個體。該交叉方法易于操作，且針對于染色體所含信息較少的情況下，采用單點交叉更能實現基因的有效交換。但也存在著一些問題，由于選擇一個交叉點，并對該點后面排列的基因均進行交換，可能會使部分優質基因被換掉。因此，考慮到排課問題所涉及到的影響因素，以及單點交叉的缺點，本文采用改進后的單點交叉方式。首先在上一代選出的精英個體中，隨機選擇一對染色體，確定個體中教室、周次以及節次這三個基因的起止位置，即確定構成每種屬性對應基因片段的交叉點。然后定義一個變量p，表示1-3的隨機數，分別對應于教室、周次、節次這三個屬性，根據生成的隨機數，確定交叉點，最后交換對應兩組基因片段的位置。與原有的單點交叉方式相比，改進后的交叉方式僅是交換交叉點處的基因，不僅保留了父代個體的有利特征，而且引入了新的變異，豐富了個體的多樣性，推動了種群進化的過程，這對于提升遺傳算法在搜索過程中的性能十分有效。針對本文的數據量而言，改進后的交叉方法對于簡化算法計算量也有重要意義。兩種方式的結果對比：（如REF_Ref16343\h表STYLEREF1\s2-3所示）表2-SEQ表\*ARABIC3改進前后單點交叉的結果對比單點交叉改進后的單點交叉父代染色體子代染色體父代染色體子代染色體154|3|8276154|3|1483154|3|8276154|5|8276762|5|1483762|5|8276762|5|1483762|3|1483變異算子遺傳算法中除了交叉可以用于生成新的個體，增加種群多樣性外，變異也是優化算法中的重要操作。其原理主要就是隨即改變個體染色體中的一個或多個基因，從而產生新的個體，避免過早收斂問題，進一步深化搜索空間，提高全局搜索能力。變異的操作方式存在多種形式，例如兩點變異、位變異、反轉變異、交換變異等。其中位變異是遺傳算法中最常見的一種操作，主要是隨機選擇染色體中的某個或多個基因位的基因值進行改變。兩點變異是一種特殊的變異操作方式，通常需要先隨機選擇染色體中的兩個點，然后交換這兩點之間的基因序列。反轉變異是將染色體中某個區間的基因順序進行反轉，交換變異則是隨機選擇兩個基因進行交換。本文采用的是位變異操作。位變異操作過程：（如REF_Ref16343\h表STYLEREF1\s2-4所示）表2-SEQ表\*ARABIC4位變異操作前后對比變異前父代染色體變異后子代染色體154|3|8|2|76154|1|8|5|76基于高校排課的應用場景，本文將針對教室、周次以及節次這三部分基因片段進行變異操作，由于本文還涉及了兩校區的排課問題，所以教室部分的基因變異應根據校區的不同，對應其相應的教室范圍生成不同的新基因值。設置控制參數遺傳算法的性能通常會多個方面的影響，例如編碼方式、適應度函數的設計、變異或交叉算子的選擇，以及控制參數的選取等。基于當下的研究，并結合本文的具體數據，對該算法的控制參數進行如下設置：種群規模種群規模的設置既不能太小，也不能太大。如果設置的太小，會限制種群的多樣性，容易陷入局部最優解。然而，種群規模太大會增大計算量，影響算法的效率，并且當種群個體較多時，只有少部分的精英個體會被選擇，進而影響個體的交叉與變異。按照研究者的經驗，種群的規模一般設置在幾十到幾百之間，按照本文數據量，設置種群規模為30。精英個體精英個體的數目即為在上一代種群中，按適應度值的大小選擇優良個體的數目。定義一個選擇概率為ep（如式（10）所示），即種群中所含精英個體的概率，elite表示精英個體，population表示種群規模。本文以選擇概率1/3為標準，設置精英個體為10。變異率在遺傳算法的迭代過程中，位變異按照一定的概率對染色體的基因值進行隨機的改變，以產生新的個體。變異率的選擇往往需要根據具體問題進行調整。變異率不宜太小或太大，太小時只能產生很少的新個體；太大時將導致遺傳算法成為隨機搜索。一般的最優變異率范圍位0.01-0.1[14][15][16][17]，本文中變異率取值為0.1。迭代次數迭代次數取決于問題的復雜性和所需的求解精度。該算法所輸入的數據量較小，在前期測試階段，一般在50輪內即可求出最優解，結合迭代輪數的建議范圍為100-500[14][15][16][17]，因此本文迭代次數設置為100。實驗數據與結果分析數據結構本文采用的數據量較少，共設置5個班級、21位教師、14門課程，2個校區，其中數學1班至數學3班在A校區，統計1班和大數據1班在B校區，每個校區均有5間教室可用于排課，A校區的教室編號為101-105，B校區的教室編號為111-115，且每周每個班均安排9節課時內容。實驗結果首先，利用遺傳算法根據上述目標函數、約束條件以及控制參數的設置，運行程序，得到5個班的課程表，以數學1班的課表為例，如REF_Ref18485\h圖STYLEREF1\s3-1所示。圖STYLEREF1\s3-SEQ圖\*ARABIC\s11基于遺傳算法的數學1班排課方案該算法運行19輪后即解出最優解，運行時間約為3.43s，且每輪計算出的沖突數量如REF_Ref18730\h圖STYLEREF1\s3-2所示。圖STYLEREF1\s3-SEQ圖\*ARABIC\s12遺傳算法每輪迭代沖突數量統計其次，采用貪心算法以數學1班、數學2班、數學3班、統計1班、大數據1班的排課優先順序為貪心策略設計算法。貪心算法的核心在于每一步都做出當前狀態下的最優選擇，以期望通過這些局部最優選擇達到全局最優。在滿足與遺傳算法相同的約束條件下，由貪心算法得到的排課結果如REF_Ref18962\h圖STYLEREF1\s3-3所示。圖STYLEREF1\s3-SEQ圖\*ARABIC\s13基于貪心算法增加約束條件前數學1班的排課方案顯而易見，該算法的排課效果很差，主要是由于該算法是從列表中依次選擇與前一步未產生矛盾的數據進行排課，在滿足數學1班的排課方案后，再迭代其他班級進行排課。因此，如果要排布出更加合理的課表，需額外增加約束條件，例如，每天的課時不超過3節，每天教師教授的課程不超過2節。在增加上述條件的基礎下，運行程序，得到新的排課安排，如REF_Ref19282\h圖STYLEREF1\s3-4所示。圖STYLEREF1\s3-SEQ圖\*ARABIC\s14基于貪心算法增加約束條件后數學1班的排課方案貪心算法中所謂的迭代與傳統的迭代算法不同，例如遺傳算法中，其迭代過程通常是通過反復更新解來逼近全局最優解，而貪心算法則是在每一步直接做出最優選擇，并不依賴于之前步驟的解。因此，在貪心算法中無法得出每輪迭代與沖突數量統計的二維圖像。從排課效果來看，相同的約束條件下，遺傳算法的效果更優。從算法運行時間來看，增加約束條件后的貪心算法，其運行時間約為0.28s，與未增加約束條件的遺傳算法相比，在時間性能上已體現出了顯著優勢。總結與展望排課問題是一項復雜的NP完全問題，需要考慮許多限制因素和約束條件，且對于智能算法的選擇與改進，學者們也提出了不同的看法，雖然現階段的排課算法在性能上有了很大的提升，但仍存在計算量大、耗時長、約束條件考慮不全面等問題。本文選擇了全局搜索能力更優的遺傳算法，對高校智能排課問題進行了研究，分析排課存在的約束條件，制定數學模型，并在此基礎之上，考慮了兩個校區之間的排課問題，使排課更加智能化、人性化。本算法彌補了高校排課問題中未考慮多校區排課的缺陷，在一定程度上緩解了教務工作人員的排課壓力，提升了高校教務系統的管理，使得教育資源得到充分利用。本文對高校排課系統的研究取得了一些初步成果，但并未對遺傳算法進行改進，并且測試數據規模較小，后期應該擴大數據規模，以便更好地驗證算法的性能。參考文獻蔣正鋒,呂佩佩,覃韓,龔瓊