基于遺傳算法的排課系統(tǒng)

1、基于遺傳算法的排課系統(tǒng)    摘 要：隨著高校的發(fā)展，在教務(wù)管理系統(tǒng)中使用的排課模型也變得越來越復(fù)雜，亟需一種適用于開發(fā)、重用及設(shè)計(jì)的方法。針對(duì)這種情況，本文給出了排課問題的數(shù)學(xué)模型，提出基于遺傳算法解決方案。結(jié)果表明，該算法能比較有效的解決排課問題。該方法易于學(xué)習(xí)和應(yīng)用，且不必依賴特殊的實(shí)現(xiàn)模式。關(guān)鍵詞：排課 遺傳算法 優(yōu)化算法一、介紹隨著近幾年各個(gè)高校的合并與擴(kuò)招，我國(guó)的綜合性大學(xué)和各個(gè)高校中在校的學(xué)生數(shù)量的大大增加，對(duì)于高校教務(wù)部門來說，排課工作是非常令人頭痛的事，經(jīng)常會(huì)出現(xiàn)課程排列沖突，比如：一個(gè)教師在同一時(shí)間上兩門

2、課，有兩個(gè)教師同時(shí)去一個(gè)教室上不同的課程，有些教師在特定時(shí)間不可以上課。如果沒有很好地解決這些沖突，必將產(chǎn)生教學(xué)混亂等現(xiàn)象。可見，排課算法的正確性、高效性是非常關(guān)鍵的。120世紀(jì)70年代中期，就有人論證了課表問題是NP完全問題。當(dāng)課表所涉及的任何信息量稍有變化將會(huì)導(dǎo)致課表編排選擇方案的劇增。課表問題存在固定的數(shù)學(xué)模型，能找到相應(yīng)的解，且是一組解集。為此，現(xiàn)提出一些關(guān)于高校教學(xué)管理系統(tǒng)排課的算法。二、排課問題的數(shù)學(xué)模型學(xué)校排課問題本質(zhì)上是時(shí)間表問題的一類典型應(yīng)用實(shí)例，是為了解決課程安排對(duì)時(shí)間和空間資源的有效利用并避免相互沖突。在排課過程中，需要考慮課程教學(xué)效果、滿足教師特殊要求等多項(xiàng)優(yōu)化指標(biāo)，將

3、各門課程安排到相應(yīng)的時(shí)間和教室需要付出一定的“成本”(Cost)。2符號(hào)與約束條件設(shè)課程集合：L=l1，l2，.，lp，.，lP；班級(jí)集合：C = c1，c2，.，cm，.，cM ；教室集合：R = r1，r2，.，rn，.，rN ；教師集合：S=s1，s2，.，sk，.，sK ；時(shí)間集合：T=t1，t2，.，td，.，tD；時(shí)間與教室對(duì)的笛卡爾積為：G=T·R=(t1，r1)，(t1，r2)，.，(tD，rN)；G中的元素稱為時(shí)間教室對(duì)；課表問題的求解過程就轉(zhuǎn)化成為每一門課程尋找一個(gè)合適的時(shí)間教室對(duì)。排課過程中必

4、須滿足各種約束條件，可以將各種約束條件歸納成兩類以簡(jiǎn)化分析過程。（1）硬約束條件硬約束條件是在排課過程中由于各類資源的有限，因此必須滿足而無法變更的約束條件，通常只要滿足下面三類硬約束條件就能夠保證在排課的過程中不發(fā)生此類沖突。同一時(shí)間，一個(gè)教師不能同時(shí)有一門以上的課程，記為R1：R1 為： 1其中：k=1，.，K； d=1，.，D。=1 教師sk 在時(shí)間td 和教室rn 上課程lp；0 否則。同一時(shí)間，一個(gè)班級(jí)不能同時(shí)有一門以上的課程，記為R2：R2 為： 1其中：m=1，.，M； 

5、d=1，.，D。=1 班級(jí)cm 在時(shí)間td 上教師sk 的課程lp；0 否則。同一時(shí)間，一個(gè)教室不能同時(shí)有一門以上的課，記為R3 ：R3 為： 1其中： n = 1 ， .， N ； d = 1 ， .， D。=1教室rn在時(shí)間td由教師sk上課程lp；0否則。（2）軟約束條件軟約束條件是在排課過程中可以滿足但又可以不完全滿足的約束條件，是排課過程中在滿足硬約束條件的基礎(chǔ)上能盡量要求滿足

6、的約束條件，軟約束條件會(huì)因不同的教學(xué)情況而有所差異。通常也可以通過調(diào)節(jié)軟約束條件的滿足程度而改變排課的效果，可以將一定要滿足的軟約束條件轉(zhuǎn)換為“硬約束條件”。以下是排課過程中常用的軟約束條件，也是本文中所考慮的軟約束條件。(1) 課程盡量安排在教學(xué)效果較好的節(jié)次。課程上課的效果與上課的節(jié)次有密切的關(guān)系，在排課的過程中我們應(yīng)該盡量將課程安排在教學(xué)效果較好的節(jié)次中，用ph表示第h節(jié)次的教學(xué)效果系數(shù)：(2) 多學(xué)時(shí)課程的周次安排要錯(cuò)開。在實(shí)際的排課過程中，一般對(duì)于每周多學(xué)時(shí)( 4) 的課程，應(yīng)該能夠盡量將其隔天安排，才能保證有較好的教學(xué)效果，用qt(t=1，2

7、，3，4，5)表示一門課程安排隔天天數(shù)t的教學(xué)效果系數(shù)：(3) 滿足教師所提出的上課時(shí)間和地點(diǎn)的要求。課程的主講教師和課程有著對(duì)應(yīng)的關(guān)系，我們將教師提出的上課要求固化在其對(duì)應(yīng)的課程上，用hj表示滿足課程上課要求的系數(shù)：(4) 當(dāng)一個(gè)班的周總課時(shí)數(shù)需在某個(gè)數(shù)值范圍內(nèi)的要求。三、排課問題的算法1.算法分析排課的沖突異常復(fù)雜，對(duì)于這些沖突的復(fù)雜度我們進(jìn)行分析。以下給出分析的過程。過程1：將模型中的五個(gè)集合降維為一個(gè)給定四維空間V(S，T，R，C)，稱之為：課表。四維分別代表了：S（教師）：全校所有課程的任課教師；T（時(shí)間）：上課的時(shí)間段，每天分為1-2、3-4、5-6、7-8、9

8、-10，總共五個(gè)時(shí)間段，每學(xué)期20周，每周五天，合計(jì)每學(xué)期有500個(gè)上課時(shí)間段；R（教室）：全校所有的可用教室，包括不同的教室屬性，如：教室大小、是否為多媒體或語(yǔ)音教室等等；C（班級(jí)）Class：當(dāng)前學(xué)期的所有教學(xué)班級(jí)，包括班級(jí)屬性，如：班級(jí)人數(shù)、是否合班。過程2 ：在課表V中求解存在著子空間L，且L 過程3 ：在課表V中求解存在著四維向量l (Sr，Tm，R，C)，且lL，那么稱l為：課。過程4 ：在課表編排過程中，對(duì)于P( liVljL，i，jN)，li (Tr，Tm，R，C)與lj (Tr，Tm，R，C)，沒

9、有沖突，認(rèn)為V是：有效課表。3 4通過對(duì)四維向量li ( Sr，Tm，R，C)與lj (Sr，Tm，R，C)的簡(jiǎn)化。在排課過程中的所有關(guān)系情況TmR + Tm RC。那么：由過程1、過程2 可以推導(dǎo)出，在課表空間中，恒有f (Tr，Tm，R，C)，那么V就是有效的課表。最后為了簡(jiǎn)化，再給出過程5：過程5 ：在課表V中，對(duì)于li ( Sr，Tm，R，C)與lj (Sr，Tm，R，C)，i、jN，沒有沖突，記為：lilj ；對(duì)于Li、Lj沒有沖突，記為：LiL

10、j。這樣有對(duì)于P( liVljL)，li (Sr，Tm，R，C)與lj (Sr，Tm，R，C)，i、jN，沒有沖突，就可以得到VL。四、結(jié)束語(yǔ)該模型與求解方法已在實(shí)際中得到應(yīng)用，取得了較好的效果。在使用遺傳算法優(yōu)化后排課算法的實(shí)際效率有極大的提高。因此用遺傳算法實(shí)現(xiàn)類似排課問題的最優(yōu)解也是一種比較簡(jiǎn)單實(shí)用的方法，收斂速度很快，時(shí)間段分配均勻。5但是在實(shí)際應(yīng)用中也可能沒有終止條件，目的是可以依次提供不同的可行解以供使用者選擇直到所有解給完或者使用者終止。如果只考慮最優(yōu)解的問題，可以使用迭代的適應(yīng)度幾乎不變作為終止條件或者規(guī)定迭代次數(shù)。值得一提的是，有些實(shí)際問題的可行解可能是唯一的，比如教學(xué)場(chǎng)地或教師資源緊缺的情況，更嚴(yán)重的是如果約束條件太苛刻，甚至可能沒有可行解，在此類情況下人工干預(yù)還是有必要的。參考文獻(xiàn)1 陶滔，李赫男，熊正為*沖突在排課算法中的應(yīng)用J華東地質(zhì)學(xué)院學(xué)報(bào)2001，(4):2562592 吳志斌，陳淑珍，孫曉安回溯算法與計(jì)算機(jī)智能排課J計(jì)算機(jī)工程1999,(3):7928