摘要：新形勢高校的發(fā)展，高校教務管理中的排課問題顯得更為復雜。排課問題是一個典型的組合優(yōu)化和不確定性調度問題，也是一個完全問題。該文根據(jù)高校實際情況，從遺傳算法的基本理論著手，研究如何利用遺傳算法解決高校排課中的資源沖突、課表優(yōu)化等問題，并引用了哈希表和時間粒度的概念，對傳統(tǒng)遺傳算法染色體的編碼模式進行了有益修正，增強了模式的靈活性。實驗證明，遺傳算法能夠簡化程序的復雜度和減少生成最佳課表的時間。達到了較高的師生滿意度。

關鍵詞：排課；遺傳算法；哈希圖；時間粒度；適應度函數(shù)

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)28-0175-03

The Making Class Schedule System of High School Based on Genetic Algorithms

XIA Xiao-yun1， GAO Wu-jun2

(1.Faculty of Information Engineering，Jiangxi University of Science and Technology， Ganzhou 341000， China;2.Faculty of Science， Jiangxi University of Science and Technology， Ganzhou 341000， China)

Abstract: As the ongoing development in the higher education institutions， the class arrangement model in the management system is also becoming more and more complicated. Course Scheduling is a typical portfolio optimization and uncertainty of scheduling problems， but also a complete problem. Based on the actual situation in high school. In addition， on the basis of GA basic theory， studies how to utilize GA to solve the conflict problem that aroused in schedule arranging system and improve schedule arrangement. We quoted a hash table and time granules， and amend the traditional genetic algorithm chromosome coding models， enhance the flexibility of the model. The practice has proved that GA can simplify the program complexity and shorten the time in generating new perfect schedule. And the curriculum schedule induced by the time code meet the satisfaction of students and teaching staff exactly.

Key words: making class schedule; genetic algorithms; hash map; time granules; fitness function

1 引言

隨著高校規(guī)模的擴大，學生人數(shù)也逐漸增加，高效教務部門排課問題也變得越來越復雜。高校排課問題是在給定教師資源、教室資源、學生人數(shù)和開課計劃的前提下，如何合理安排課表的問題。排課問題是一個NP難問題[1]。對于較為單一的排課問題來說，可以采取啟發(fā)式搜索算法找到最優(yōu)解，而對于復雜的排課問題，該算法很難找到合理和滿意的解。遺傳算法[2]作為一種有效的全局搜索方法，具有良好的并行性，通過對可行解進行選擇、交叉、變異等遺傳算子的作用使種群不斷進化，從而得到全局最優(yōu)解或近似最優(yōu)解?；谶z傳算法的魯棒性，適用范圍廣，有組織性、自適應和學習性、并行性等許多有點，其應用范圍也較為廣泛。本論文引入哈希表和時間粒度對編碼模式進行修正，并充分利用遺傳算法特點，給出了排課問題的有效求解方法，對高校教務管理排課研究具有重要的意義。

2 排課問題中的約束條件及優(yōu)化目標

在實際排課過程中，以某一等長的時間段為課表的時間安排單位，稱之為時間單元[3]。一個可行的課表安排應滿足以下約束條件：課表以一個星期為一周期，一個星期的課表就是一個學期的課表；課表應滿足班級、教師、教室上課不沖突；教室的座位應該滿足上課班級學生的需要；其他一些特殊要求。

高校排課問題實際上是時間表安排的問題[4]。在實際排課過程中，需要考慮到教師、學生、班級、教室、教室的大小、實驗設備等方面的問題。這些條件可以根據(jù)重要性將其分為硬件約束和軟件約束。為了更好的解決問題，我們假設硬件約束為：

某些課程需要安排在特定的教室。

同一時間，同一個教師，同一個學生，同一個教室不允許同時上一門以上課程。

教室必須有足夠的座位容納學生。

對于需要試驗設備的課程，教室需要有相應的配套設備。比如計算機課需要電腦。

硬件約束條件是在排課過程中必須滿足而無法變更的約束條件。

軟件約束為：

安排教師喜歡的特定時間上課。

安排教師喜歡的特定教室上課。

在相應的時間或教師給學生或老師安排特定的課程。

軟件約束條件是在排課過程中可以滿足但又可以不完全滿足的約束條件。

排課問題[5-7]的關鍵就是為了解決課程安排對時間和空間資源的有效利用并避免相互沖突。排課的優(yōu)化目標就是使得各類沖突為零，并且盡可能滿足教師、學生的要求，達到較好的教學效果 。

3 用遺傳算法解決排課問題

3.1 排課問題中的對象描述

1）教師

■

2）學生組（大班）

■

3）教室

■

4）課程

■

5）教學班

■

3.2 染色體編碼及適應度函數(shù)

為了更靈活的進行染色體編碼，我們假定每周上課時間為周一至周五共五天，而每天從上午9點至晚上9點共十二個小時。規(guī)定一小時為一時間片段。我們可以定義一個大小為12*5*教室數(shù)量的向量，并使用哈希表存放上課的班級、時間及教室。

遺傳算法的進化過程是以每個個體的適應度值為依據(jù)來選取下一代種群的。適應度函數(shù)設定的好壞直接影響到遺傳算法的收斂速度和能否找到最優(yōu)解。本文中，我們僅考慮硬件約束方面的因素，在本研究中，適應度函數(shù)的設計思想是由于課表問題的優(yōu)化目標有多個，同時約束也有多個，因此采用多目標化和適應度函數(shù)相結合的個體適應度評價函數(shù)[8]。

每個教學班級有0——5的得分；

如果教學班級使用矛教室，就增加分值；

如果上課教室需要電腦并且安排上課的教室里有電腦，或者上課教室不需要電腦，就增加分值；

如果安排上課的教室沒有足夠的座位，就增加分值；

如果教師在上課時間沒有其它的課程，我們再一次增加分值；

如果學生在上課時間沒有其它的課程，我們就增加分值；

如果教學班級在任一時間間隔點破壞了上述規(guī)則，不再增加分值。

因此，我們可以定義適應度的計算公式如下：

■

其中， schedule_score代表所有教學班級總得分數(shù)， Maximum_score=教學班級數(shù)*5，適應度值為0~1之間的單精度浮點型值。

3.3 交叉和變異操作

交叉操作就是對選取的兩個父個體哈希表中數(shù)據(jù)進行組合，然后根據(jù)新的哈希表中的內容創(chuàng)建向量。交叉操作對隨機產生的部分父個體哈希圖進行分裂。分裂的部分由染色體特征中交叉點的數(shù)量決定。最終從父個體交替復制到新的染色體中，形成新的向量。

變異操作是很簡單的。它是隨機的選取課程然后隨機的放入所選擇的時間段。課程隨機移動的數(shù)量由變異的染色體特征決定。

4 結論

本文在對遺傳算法研究的基礎上設計實現(xiàn)了高校智能排課系統(tǒng)。并對傳統(tǒng)的編碼模式進行了有效的改進。從排課的結果分析得出所編排的課程表滿足排課原則，有效解決沖突問題，課時安排比較均勻。并且這種編碼模式具有較高的擴展性，算法的性能有待于進一步提高。

參考文獻：

[1] GAREY M R， JOHNSON D S， Compute and Intractability: A guide to the theory of NP completeness[M].San Francisco: W.H.Freeman Co Ltd，1979.

[2] 周明，孫樹棟.遺傳算法原理及應用[M].北京:國防工業(yè)出版社，1999.

[3] SAFAAI D，SIGERU O. Incorporating constrain propagation in genetic algorithm for university timetable planning[J].Engineering Application of Artificial Intelligence，1999，12(3):241-253.

[4] 滕姿，鄧輝文，楊久俊.基于遺傳算法的排課系統(tǒng)的設計與實現(xiàn)[J].計算機應用，2007，27(12):199-204.

[5] 蘇仰娜.基于遺傳算法的優(yōu)化排課系統(tǒng)[J].河南大學學報:自然科學版，2005，35(3):47-50.

[6] 楊宇.高校排課系統(tǒng)理論研究與開發(fā)遺傳算法在課表問題中的應用[M].北京:北京理工大學出版社，2003:35-67.

[7] 王健，董改芳，許道云.自動排課系統(tǒng)的模型與實現(xiàn)[J].貴州大學學報:自然科學版，2004，21(2):34-36.

[8] 胡義偉，謝勇，鄭金華.基于遺傳算法的綜合性大學排課系統(tǒng)研究[J].中國教育信息化，2007，(11):54-55.