遺傳算法在自動(dòng)排課中的應(yīng)用研究

李英鶴

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

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

1 排課問題分析

1.1 排課問題的因素

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

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

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

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

班級(jí)：每個(gè)班級(jí)都有編號(hào)和名稱。每個(gè)班級(jí)同一時(shí)間只能上一門課程。

教師：每個(gè)教師都有編號(hào)和姓名。每個(gè)教師同一時(shí)間只能上一門課程。

1.2 排課過程的約束條件

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

?

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

1.3 排課問題的目標(biāo)實(shí)現(xiàn)

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

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

2 遺傳算法在課表編排中的應(yīng)用

2.1 遺傳算法的基本原理

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

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

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

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

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

2.2 遺傳算法在課表編排中的設(shè)計(jì)

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

2.3 算法的實(shí)現(xiàn)

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

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

結(jié)論

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

[1]安勐.遺傳算法在排課問題求解中的應(yīng)用[J].銅仁學(xué)院學(xué)報(bào)，2009，11（2）：135-139.

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

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