遺傳算法在自動排課中的應用研究

李英鶴

（沈陽理工大學信息科學與工程學院，遼寧 沈陽 110000）

排課問題在學校教學管理中十分重要，它是一個有約束的、多目標的組合優化問題，并且已經被證明為是一個NP完全問題。由于涉及信息較多且求解比較復雜資源的最優化配置不容易實現，因此使用計算機對排課信息進行管理，能夠極大地提高學校教務管理的效率，也是各種體制學校管理科學化、現代化的重要條件。現在大多數的排課系統是以編程語言為實現語言，采用各種算法為實現手段，比如遺傳算法、回溯算法、模擬退火算法等。作為對排課問題的探索，本文采用遺傳算法的思想，提出一個課表方案的隨機生成和優化算法，以期能夠較大程度地反映實際排課情況和盡量達到多個目標最優。

1 排課問題分析

1.1 排課問題的因素

從手工排課的過程看出，排課問題需要考慮的條件很多，如周課時設置、課程信息、班級信息、教師信息、教室信息等等。從排課過程可能引起潛在沖突的角度，可以將排課問題涉及的因素考慮如下：

時間：在排課問題中涉及關于時間的概念有學年、學期、周、天、節。

課程：每個課程都有自己的編號、名稱。每個課程都有指定的教師、教室等。某些課程由于上課班級較多難以協調或照顧教師要求等諸如此類原因，應該預先給定時間或教室。

教室：每個教室都有編號、門牌號和名稱。每個教室在同一時間內只能接納一門課程的授課，并且教室容量應該大于等于上課的人數。

班級：每個班級都有編號和名稱。每個班級同一時間只能上一門課程。

教師：每個教師都有編號和姓名。每個教師同一時間只能上一門課程。

1.2 排課過程的約束條件

排課是將教師與學生在時間和空間上根據不同的約束條件進行排列組合，以使教學正常進行。避免排課因素發生沖突是排課問題中要解決的核心問題。只有在滿足全部約束條件和避免沖突的基礎上，才能保證整個教學計劃合理正常進行。而對教師、教室、學生及時間等資源進行最優化組合配置，才能保證充分發揮各資源的優勢和提高教學質量。

?

排課過程中常見的約束條件如表1所示：

1.3 排課問題的目標實現

排課問題是一個多目標的組合規劃問題，要想制定出一個“合理、實用、有特色”的課表，必須保證所有的約束條件都不發生沖突。一套高質量的課表，在時間、教室資源、課程安排等很多方面都應該做到科學的安排，并且應該具有人性化的考慮。課表編排問題的難點在于：保證課表在時間及人員的分配上符合一切共性和個性要求，在此基礎上，所有的課程都能夠安排合適的時間和教室，使安排方案在各個目標上盡量達到全局最優。

遺傳算法是1975年美國MIChiga大學的John.H.Holland教授及其學生們根據生物進化的模型提出的一種優化算法。作為一種隨機的優化與搜索方法，遺傳算法有兩個主要特性：1智能性。即遺傳算法在確定了編碼方案、適應值函數及遺傳算子以后，算法將利用演化過程中獲得的信息自行組織搜索。適應值大的個體具有較高生存概率，它是具有“潛在學習能力”的自適應搜索技術。2并行性。由于遺傳算法采用種群的方式組織搜索，從而可以同時搜索解空間內的多個區域，并相互交流信息，這種搜索方式使得遺傳算法能以較少的計算獲得較大的收益。正是由于遺傳算法的這兩個特性，使得遺傳算法迅速被運用于求解組合優化的排課問題，且操作簡單，可以更少地依賴于實際問題的情況，實現課表的優化。

2 遺傳算法在課表編排中的應用

2.1 遺傳算法的基本原理

遺傳算法是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。一般的遺傳算法都包含三個基本操作：復制、交叉、變異。

2.1.1 復制，是從一個舊種群中選擇生命力強的個體字符串產生新種群的過程。復制操作過程中，目標函數是該字符串被復制或被淘汰的決定因素。遺傳算法的每一代都是從復制開始的。

2.1.2 交叉，在由等待配對的字符串構成的匹配池中，將新復制產生字符串個體隨機兩兩配對，然后隨機地選擇交叉點，對匹配的字符串進行交叉繁殖，產生一對新的字符串。

遺傳算法的有效性主要來自復制和交叉操作，尤其是交叉在遺傳算法中起著核心的作用。

2.1.3 變異，遺傳算法中，變異就是某個字符串某一位的值偶然的隨機的改變，即在某些特定位置上簡單地把1變成0，或反之。變異操作可以起到恢復字符串字符位多樣性的作用，并能適當地提高遺傳算法的搜索效率。

2.2 遺傳算法在課表編排中的設計

使用遺傳算法編排課表，我們把課程和老師當作同一變量考慮，這樣編排課表只需將教師編碼排入周課表，在以后打印課表時，將教師編碼改為課程名即可。于是我們設計以下步驟：對每一門任課教師進行編碼；使用二維數組來構成初始群體；沖突的檢驗和消除；定義課表的適應度函數(x)(x∈{1,2,…,N}),其中x表示個體在群體中的位置。當函數值為0時，即找到了本次優化過程的最優值；復制操作：按照適配值計算選擇率和期望的復制數；交叉操作：將種群中的個體配對產生的交叉點再分別交換；變異操作：將隨機產生的同列的兩個位置互換；再次進行沖突檢測和消除，直至無沖突存在。

2.3 算法的實現

遺傳算法結束后，可以得到綜合效率函數值最好的個體。根據這個結果，即可生成相應的課程表。系統的流程分為以下幾個主要的過程：（1）初始種群的產生：形成本學期教學信息二維表，對教師編碼；產生染色體。（2）對各類沖突進行檢測，如存在沖突則消除它。（3）計算適應度函數值、期望值及其復制數。（4）進行遺傳操作。（5）可行課程表的產生。

這樣，我們就有了一個課程表的數據庫表。因此，可以打印其中某一班級的課程表或全校的課程表了。

結論

本文采用遺傳算法來對課表編排問題進行求解，是求解這種難解的組合優化問題方法中較明智的選擇，目的是在遺傳算法基礎上提出一個課表方案的隨機生成和優化方案，能夠較大程度地實現課表編排和多個目標的最優化。本文算法對我們這類院系較多、教師工作量大、學科變化較大、不確定性較多的學校能有所借鑒。

[1]安勐.遺傳算法在排課問題求解中的應用[J].銅仁學院學報，2009，11（2）：135-139.

[2]陳春明.遺傳算法在自動排課系統中的應用研究 (碩士學位論文)[D].蘇州:蘇州大學,2009.

[3]徐艷斌.基于遺傳算法的高校排課系統設計與分析（碩士學位論文）[D].廣州：廣東工業大學，2007.