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

李英鶴

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

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

1 排課問題分析

1.1 排課問題的因素

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

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

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

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

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

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

1.2 排課過程的約束條件

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

?

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

1.3 排課問題的目標實現(xiàn)

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

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

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

2.1 遺傳算法的基本原理

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

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

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

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

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

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

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

2.3 算法的實現(xiàn)

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

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

結(jié)論

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

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

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

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