基于遺傳算法的高校排課問(wèn)題優(yōu)化研究

中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2025）08-0165-05

Abstract：Aiming at the problemof course scheduling in collges and universities，this paper proposes a solution based on Genetic Algorithm.Course scheduling is akeytask ineducationmanagement.Itnotonlyaffects theeffciencyofresource utilizationinschols，utalsoisdrectlyrelatedtotheimprovementofeachingquality.Thetraditionalmanualcoursesheduling method is unable tofullconsider various complex constraints，resulting in wasteofresources andfrequent conflicts.Inrecent years，withtheadvancementofcomputing technology，GeneticAlgorithmhasshownsignificantadvantages insolving such problems due toitsstrong robustnessandparalelism.This paperachievesaneffcientandfexiblecourseschedulingbyrationally designingchromosomecoding，ftmess functionand geneticoperation.The experimentalresultsshow thatthe proposed algorithm can quickly converge to the high-quality solution， and has good robustness and flexibility.

Keywords： Genetic Algorithm;course scheduling incoleges anduniversities; multi-constraint optimization;automati course scheduling system

0 引言

排課問(wèn)題是教育管理中的關(guān)鍵任務(wù)，直接影響學(xué)校的資源利用效率和教學(xué)質(zhì)量。傳統(tǒng)的手工排課方式難以全面考慮復(fù)雜的約束條件，導(dǎo)致資源浪費(fèi)和沖突頻發(fā)。近年來(lái)，隨著計(jì)算技術(shù)的發(fā)展，遺傳算法因其強(qiáng)大的魯棒性和并行性，在解決此類(lèi)問(wèn)題上展現(xiàn)出了顯著的優(yōu)勢(shì)。通過(guò)編碼、選擇、交叉和變異等操作，遺傳算法能夠逐步優(yōu)化解空間，有效處理多約束優(yōu)化問(wèn)題。已有研究顯示，結(jié)合局部搜索、多目標(biāo)優(yōu)化及自適應(yīng)變異策略的改進(jìn)遺傳算法，能顯著提高排課系統(tǒng)的穩(wěn)定性和效率。例如，張永宏等針對(duì)中學(xué)走班制設(shè)計(jì)了一種優(yōu)化的遺傳算法，解決了復(fù)雜排課問(wèn)題[1；朱婷婷提出了一種結(jié)合多目標(biāo)優(yōu)化和自適應(yīng)變異策略的改進(jìn)遺傳算法，提高了職業(yè)院校自動(dòng)排課系統(tǒng)的性能[2；郭欣奇探討了遺傳算法參數(shù)優(yōu)化和交叉變異策略，為實(shí)際應(yīng)用提供了指導(dǎo)[3]。此外，徐海濤等探索了基于深度強(qiáng)化學(xué)習(xí)與遺傳算法相結(jié)合的方法，實(shí)現(xiàn)了排課系統(tǒng)的自學(xué)習(xí)能力[4。

除了遺傳算法，其他優(yōu)化算法也在排課問(wèn)題中得到了應(yīng)用。羅義強(qiáng)等提出了基于改進(jìn)粒子群算法的高校排課方案[5]，李陽(yáng)等研究了基于改進(jìn)遺傳算法的高校排課優(yōu)化問(wèn)題[。這些研究表明，不同算法在特定場(chǎng)景下具有獨(dú)特優(yōu)勢(shì)。例如，蔣正鋒等分別探討了基于蟻群算法[7和遺傳算法[的高校排課問(wèn)題，指出了各自的應(yīng)用特點(diǎn)。

從應(yīng)用場(chǎng)景來(lái)看，研究覆蓋了從中學(xué)到高等教育的不同層次，包括中學(xué)走班制、大學(xué)課程安排、職業(yè)院校排課等。胡秀華等介紹了基于移動(dòng)平臺(tái)的高校教務(wù)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[，強(qiáng)調(diào)了系統(tǒng)在實(shí)際應(yīng)用中的便利性。張宇瞳等專(zhuān)注于天課時(shí)分配下的多階段新高考走班制排課算法[1]，而陳璐等關(guān)注的是改進(jìn)遺傳算法求解走班制下的排課問(wèn)題[]。大多數(shù)研究采用了定量方法來(lái)驗(yàn)證算法的有效性。例如，張永宏等的研究顯示，其提出的算法在實(shí)驗(yàn)中成功減少了排課沖突，提高了教室利用率[1。朱婷婷的研究表明，通過(guò)引入多目標(biāo)優(yōu)化和自適應(yīng)變異策略，算法在保證課程分布均勻的同時(shí)，提升了教師滿(mǎn)意度[2。郭欣奇的研究則通過(guò)詳細(xì)的實(shí)驗(yàn)數(shù)據(jù)分析，展示了參數(shù)調(diào)優(yōu)對(duì)算法性能的影響[3]。這些研究不僅提供了理論上的支持，還通過(guò)實(shí)驗(yàn)結(jié)果證明了算法的實(shí)際應(yīng)用價(jià)值。

1排課問(wèn)題描述

1.1 問(wèn)題背景

高校排課問(wèn)題可以形式化為一個(gè)組合優(yōu)化問(wèn)題，其目標(biāo)是在滿(mǎn)足一系列約束條件下，為所有課程安排合適的教師、教室和時(shí)間。具體來(lái)說(shuō)，排課問(wèn)題可以描述如下：

1）課程信息。每門(mén)課程有固定的學(xué)時(shí)要求，需要分配到特定的時(shí)間段。2）教室資源。學(xué)校有多個(gè)教室，每個(gè)教室有一定的容量限制。3）教師資源。每位教師有固定的可用時(shí)間段，不能在同一時(shí)間教授多門(mén)課程。4）班級(jí)需求。每個(gè)班級(jí)有固定的課程表，不能在同一時(shí)間上多門(mén)課程。5）其他約束?？赡苓€包括教師和學(xué)生的偏好、課程的連貫性等。例如，教師可能希望某些課程在特定時(shí)間段進(jìn)行，學(xué)生可能希望避免連續(xù)的高強(qiáng)度課程，某些課程需要按順序安排以保證學(xué)習(xí)的連貫性。

排課目標(biāo)是確保沒(méi)有課程在相同的時(shí)間段安排在相同的教室、相同的班級(jí)或相同的教師，同時(shí)盡量考慮教師和學(xué)生的偏好，使課程安排更加人性化，提高教學(xué)質(zhì)量和學(xué)生的學(xué)習(xí)體驗(yàn)。

1.2數(shù)學(xué)模型

1.2.1 決策變量

假設(shè) 表示課程 i 是否在時(shí)間段 j 安排在教室 k 上課。其中 表示課程 i 在時(shí)間段 j 安排在教室k 上課。 表示課程 i 沒(méi)有在時(shí)間段 j 安排在教室k 上課。

1.2.2 參數(shù)設(shè)置

設(shè)課程集為 ，時(shí)間段集合為

，教室集合為 班級(jí)集合為 ，教師集合為 ， 為課程 i 所屬的班級(jí)， 為課程 i 所屬的教師。

1.2.3 約束條件

模型的約束條件設(shè)置如下：

1）每門(mén)課程必須安排在某個(gè)時(shí)間段和教室：

2）同一時(shí)間段同一教室只能安排一門(mén)課程：

3）同一時(shí)間段同一班級(jí)只能上一門(mén)課程：

4）同一時(shí)間段同一教師只能教授一門(mén)課程：

1.2.4 目標(biāo)函數(shù)

定義沖突函數(shù) f （ X ） ，表示所有沖突的數(shù)量。目標(biāo)是使 f （ X ） 盡可能小，理想情況下 f （ X ）=0 。

2 遺傳算法求解

2.1 染色體編碼設(shè)計(jì)

在遺傳算法中，個(gè)體的表示（即染色體編碼）是解決問(wèn)題的關(guān)鍵之一。對(duì)于高校排課問(wèn)題，一個(gè)合理的染色體編碼方案能夠有效地表達(dá)課程安排，并且易于實(shí)現(xiàn)遺傳操作。本文采用了一種基于時(shí)間槽的編碼方式。

時(shí)間槽定義：首先將一周的時(shí)間劃分為若干個(gè)連續(xù)的時(shí)間槽，每個(gè)時(shí)間槽代表一個(gè)可能的上課時(shí)間段。例如，可以將一天劃分為5個(gè)時(shí)間槽，那么一周就有25個(gè)時(shí)間槽。

染色體結(jié)構(gòu)：每個(gè)染色體代表一種完整的課程安排方案，由一系列基因組成。每個(gè)基因?qū)?yīng)一門(mén)具體的課程，其值為該課程被安排到的時(shí)間槽編號(hào)。此外，每門(mén)課程還需要額外的信息來(lái)指定教室和教師，這些信息可以作為基因的一部分，或者通過(guò)其他數(shù)據(jù)結(jié)構(gòu)關(guān)聯(lián)起來(lái)。

這種編碼方式的優(yōu)點(diǎn)在于它直觀地反映了課程安排的情況，同時(shí)便于進(jìn)行交叉和變異等遺傳操作。

2.2 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)用于評(píng)估每個(gè)排課方案的質(zhì)量，它是指導(dǎo)遺傳算法搜索過(guò)程的重要依據(jù)。本研究中的適應(yīng)度函數(shù)綜合考慮了硬約束和軟約束兩方面因素。

硬約束：確保沒(méi)有任何沖突發(fā)生，比如同一教師在同一時(shí)間教授多門(mén)課程、同一班級(jí)或同一教室在相同時(shí)間有多個(gè)活動(dòng)等。違反硬約束的解將被賦予極低的適應(yīng)度值。

軟約束：包括但不限于課程分布均勻性、教師偏好、學(xué)生滿(mǎn)意度等因素。這些軟約束雖然不是必須滿(mǎn)足的，但它們有助于提高整體方案的人性化水平。例如，如果某位教師希望自己的課程集中在上午，那么當(dāng)安排符合這一偏好時(shí)，可以適當(dāng)增加適應(yīng)度分值。

根據(jù)上述描述，適應(yīng)度函數(shù)可以表示為一個(gè)加權(quán)求和的形式，其中每一項(xiàng)代表不同的評(píng)價(jià)指標(biāo)。設(shè) F 為適應(yīng)度函數(shù)，適應(yīng)度函數(shù)形式為：

其中， 為第 i 個(gè)評(píng)價(jià)指標(biāo)（如沒(méi)有沖突、課程分布均勻性、教師偏好等），而 為與之對(duì)應(yīng)的權(quán)重。具體的 定義如下：

為無(wú)沖突情況下的獎(jiǎng)勵(lì)，若排課方案中不存在任何時(shí)間、教室或教師的沖突，則此值為正；否則為負(fù)或0。 為課程分布均勻性的評(píng)估，衡量課程在整個(gè)周內(nèi)是否均勻分布，分布越均勻則該值越高。 為教師偏好的滿(mǎn)足程度，依據(jù)教師對(duì)授課時(shí)間段的偏好進(jìn)行打分，偏好得到滿(mǎn)足越多則得分越高。 為學(xué)生學(xué)習(xí)體驗(yàn)的考量，如避免連續(xù)高強(qiáng)度課程，保持課程連貫性等，滿(mǎn)足條件則加分。

2.3 求解過(guò)程

求解過(guò)程如下：

1）初始化。隨機(jī)生成初始種群，每個(gè)個(gè)體是一個(gè)排課方案，表示為一個(gè)三維矩陣。

2）適應(yīng)度評(píng)估。計(jì)算每個(gè)個(gè)體的適應(yīng)度值，包括硬約束（無(wú)沖突）和軟約束（課程分布均勻性、教師偏好、學(xué)生學(xué)習(xí)體驗(yàn)等）。3）選擇。采用輪盤(pán)賭選擇或精英選擇策略挑選適應(yīng)度較高的個(gè)體進(jìn)入下一代。輪盤(pán)賭選擇依據(jù)適應(yīng)度比例；精英選擇直接保留適應(yīng)度最高的幾個(gè)個(gè)體。4）交叉。隨機(jī)選取兩個(gè)個(gè)體進(jìn)行交叉操作，通過(guò)交換部分基因（如時(shí)間段或教室安排）來(lái)生成新的個(gè)體。5）變異。對(duì)新生成的個(gè)體執(zhí)行變異操作，隨機(jī)改變某些基因以探索新的解空間。6）終止條件檢查。檢查是否達(dá)到最大迭代次數(shù)或已找到無(wú)沖突的排課方案。如果滿(mǎn)足任一條件，則轉(zhuǎn)到結(jié)果輸出階段；否則返回適應(yīng)度評(píng)估步驟繼續(xù)進(jìn)化。

7）結(jié)果輸出。將最優(yōu)排課方案輸出至Excel文件中，生成詳細(xì)的課程表，包含課程名稱(chēng)、上課地點(diǎn)、授課教師等信息。求解過(guò)程流程圖如圖1所示。

3實(shí)驗(yàn)設(shè)置與結(jié)果分析

3.1實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

本文使用Python實(shí)現(xiàn)了基于遺傳算法的排課系統(tǒng)，并對(duì)其性能進(jìn)行了測(cè)試。硬件配置為：IntelCorei7 CPU，16GBRAM；軟件環(huán)境為：Python3.9，NumPy，Pandas，Matplotlib。實(shí)驗(yàn)參數(shù)設(shè)置如下：種群規(guī)模為32，交叉率為0.7，變異率為0.1，最大進(jìn)化代數(shù)為500代。

3.2 實(shí)驗(yàn)數(shù)據(jù)

本次實(shí)驗(yàn)涉及13門(mén)課程（如軟件工程、數(shù)據(jù)庫(kù)原理與應(yīng)用等），23位教師（每位教師負(fù)責(zé)不同的課程組合），以及5個(gè)計(jì)算機(jī)班（計(jì)算機(jī)1班至計(jì)算機(jī)5班）對(duì)這些課程的需求情況。在教室資源方面，假設(shè)學(xué)校提供了一定數(shù)量的教室以滿(mǎn)足教學(xué)需求。在時(shí)間安排方面，每周的教學(xué)活動(dòng)分為5天（周一至周五），每天有5個(gè)時(shí)間段（第1-2節(jié)至第9-10節(jié)）。

課程信息表包含以下字段：CourseID（INT，主鍵）和CourseName（VARCHAR）。教師信息表包括以下字段：TeacherID（INT，主鍵）、Name（VARCHAR）、Gender（CHAR）、Title（VARCHAR）及一系列布爾字段，表示是否教授特定課程（如Coursel0112）。班級(jí)需求表由ClassID（INT，主鍵）及五個(gè)布爾字段組成，分別對(duì)應(yīng)五個(gè)計(jì)算機(jī)班是否需要該課程。課程安排表（Schedules）包括以下字段：ScheduleID（INT，主鍵）、Section（VARCHAR，節(jié)數(shù)）、StartTime（TIME）、EndTime（TIME）以及七個(gè)布爾字段，表示一周內(nèi)每天是否有課。

3.3 實(shí)驗(yàn)步驟

初始化階段，算法首先隨機(jī)生成32個(gè)初始排課方案，每個(gè)方案詳細(xì)包含了所有課程的安排信息，確保了種群的初始多樣性。隨后，進(jìn)入評(píng)估適應(yīng)度環(huán)節(jié)，算法會(huì)根據(jù)每個(gè)排課方案對(duì)硬約束和軟約束的滿(mǎn)足情況進(jìn)行綜合評(píng)價(jià)，計(jì)算出適應(yīng)度值。硬約束主要關(guān)注教師、教室、班級(jí)之間的時(shí)間沖突問(wèn)題，而軟約束則考慮課程分布的均勻性和教師的個(gè)人偏好等因素。接下來(lái)是選擇操作，依據(jù)計(jì)算出的適應(yīng)度值，算法會(huì)選擇保留那些適應(yīng)度較高的個(gè)體，以此來(lái)提高下一代種群的質(zhì)量。緊接著，對(duì)選出的高適應(yīng)度個(gè)體執(zhí)行交叉操作，通過(guò)交換部分課程安排信息，生成新的排課方案，這一步驟有助于探索更廣泛的解空間。為了進(jìn)一步增加種群的多樣性，防止過(guò)早收斂，算法還會(huì)對(duì)新生成的排課方案進(jìn)行隨機(jī)變異操作，即隨機(jī)調(diào)整某些課程的安排。最后，整個(gè)過(guò)程將循環(huán)往復(fù)，重復(fù)上述的選擇、交叉、變異步驟，直到達(dá)到預(yù)設(shè)的最大進(jìn)化代數(shù)（500代）或者滿(mǎn)足其他終止條件為止。通過(guò)這種不斷迭代優(yōu)化的過(guò)程，算法最終能夠生成既滿(mǎn)足所有硬約束又盡可能符合軟約束要求的高質(zhì)量課程表。

3.4 實(shí)驗(yàn)結(jié)果

通過(guò)實(shí)驗(yàn)輸出的排課安排表如圖2所示，算法收斂圖如圖3所示。實(shí)驗(yàn)結(jié)果表明，該算法能夠在有限的迭代次數(shù)內(nèi)找到滿(mǎn)足所有硬約束的排課方案，同時(shí)較好地兼顧了軟約束，提高了課程安排的人性化水平。

該算法在硬約束滿(mǎn)足方面表現(xiàn)出色，所有生成的課表均未出現(xiàn)任何教師、教室或班級(jí)的時(shí)間沖突，確保了課程安排的基本可行性。在軟約束滿(mǎn)足方面，課程的分布較為均勻，教師的個(gè)人偏好也得到了較好地滿(mǎn)足，這不僅提高了教師的工作滿(mǎn)意度，也有助于提升學(xué)生的學(xué)習(xí)體驗(yàn)。此外，算法的收斂速度非?？?，能夠在前200代內(nèi)迅速收斂到一個(gè)基本可行的解。之后，隨著進(jìn)化的繼續(xù)，算法逐漸優(yōu)化這一解，直至達(dá)到最終的優(yōu)質(zhì)解。這一特點(diǎn)使得該算法在實(shí)際應(yīng)用中能夠高效地生成滿(mǎn)意的課程表，為高校的排課工作提供了強(qiáng)有力的技術(shù)支持。

4結(jié)論

本文成功地將遺傳算法應(yīng)用于高校排課問(wèn)題，通過(guò)合理的設(shè)計(jì)和優(yōu)化，實(shí)現(xiàn)了高效、合理的課程安排。實(shí)驗(yàn)結(jié)果表明，該算法能夠快速收斂于優(yōu)質(zhì)解，并具備良好的魯棒性和靈活性。盡管如此，本文提出的基于遺傳算法的排課系統(tǒng)在實(shí)驗(yàn)中表現(xiàn)良好，但仍存在一些局限性和改進(jìn)空間：在算法參數(shù)調(diào)優(yōu)方面，不同場(chǎng)景下，遺傳算法的參數(shù)（如種群規(guī)模、交叉率、變異率等）可能需要進(jìn)一步調(diào)優(yōu)，以適應(yīng)不同的排課需求；在多目標(biāo)優(yōu)化方面，未來(lái)的改進(jìn)方向可以考慮引入多目標(biāo)優(yōu)化技術(shù)，同時(shí)優(yōu)化多個(gè)目標(biāo)（如課程分布均勻性、教師滿(mǎn)意度、學(xué)生滿(mǎn)意度等）；

在實(shí)時(shí)更新方面，在實(shí)際應(yīng)用中，排課系統(tǒng)需要支持實(shí)時(shí)更新功能，以應(yīng)對(duì)突發(fā)情況（如教師請(qǐng)假、教室維修等）。隨著人工智能技術(shù)的發(fā)展，基于遺傳算法的排課系統(tǒng)有望在更多的高校中得到應(yīng)用。未來(lái)的研究可以結(jié)合機(jī)器學(xué)習(xí)、深度學(xué)習(xí)等技術(shù)，進(jìn)一步提升排課系統(tǒng)的智能化水平，為高校管理提供更加高效、便捷的解決方案。

參考文獻(xiàn)：

[1]張永宏，王永吉，付立軍，等.面向中學(xué)走班制排課的優(yōu)化遺傳算法[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2020，29（12）：80-86.

[2]朱婷婷.基于改進(jìn)遺傳算法的職業(yè)院校自動(dòng)排課系統(tǒng)研究與實(shí)現(xiàn)[D].鎮(zhèn)江：江蘇大學(xué)，2022.

[3]郭欣奇.基于改進(jìn)遺傳算法的排課系統(tǒng)研究與設(shè)計(jì)[D].哈爾濱：哈爾濱師范大學(xué)，2023.

[4]徐海濤，程海燕，童名文.基于深度強(qiáng)化學(xué)習(xí)的自學(xué)習(xí)排課遺傳算法研究[J].計(jì)算機(jī)科學(xué)，2024，51（S1）：241-248.

[5]羅義強(qiáng)，陳智斌.基于改進(jìn)粒子群算法的高校排課問(wèn)題優(yōu)化[J].計(jì)算機(jī)應(yīng)用與軟件，2018，35（6）：241-247+303.

[6]李陽(yáng)，張欣.基于改進(jìn)遺傳算法的高校排課優(yōu)化問(wèn)題研究[J].電子科技，2016，29（5）：127-129+138.

[7]蔣正鋒，罩韓，呂佩佩，等.基于蟻群算法的高校排課問(wèn)題的應(yīng)用研究[J].現(xiàn)代計(jì)算機(jī)，2019（25）：22-27.

[8]蔣正鋒，呂佩佩，覃韓，等.基于遺傳算法的高校教務(wù)系統(tǒng)排課問(wèn)題的應(yīng)用研究[J].現(xiàn)代計(jì)算機(jī)，2019（21）：32-36.

[9]胡秀華，李承瑞，李桂萍，等.基于移動(dòng)平臺(tái)的高校教務(wù)管理系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].軟件導(dǎo)刊，2018，17（9）：125-128.

[10]張宇瞳，劉靜，郝星星.天課時(shí)分配下的多階段新高考走班制排課算法[J].計(jì)算機(jī)工程與應(yīng)用，2021，57（11）：266-278.

[11]陳璐，王秀.改進(jìn)遺傳算法求解走班制下的排課問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用，2019，55（6）：218-224.

作者簡(jiǎn)介：燕紫君（1993—），女，漢族，湖北仙桃人，講師，碩士，研究方向：數(shù)據(jù)分析、算法研究。