基于遺傳算法的智能排課系統(tǒng)的設(shè)計和實現(xiàn)

1、最新【精品】范文 參考文獻(xiàn) 專業(yè)論文基于遺傳算法的智能排課系統(tǒng)的設(shè)計和實現(xiàn)基于遺傳算法的智能排課系統(tǒng)的設(shè)計和實現(xiàn)摘要：本文針對遺傳算法后期收斂速度慢，易陷入局部最優(yōu)的 困境，提出了改進(jìn)方案，有效解決了智能排課問題。關(guān)鍵詞：遺傳算法；排課問題；組合優(yōu)化中圖分類號：N945.23文獻(xiàn)標(biāo)識碼：A文章編號：排課是一個比較復(fù)雜的過程，對于特殊課程的排課采取的是手動 方式，而一般課程則采用自動方式。在自動排課前需要對一些參數(shù)進(jìn) 行初始化，課表生成后可以進(jìn)行人工調(diào)整。1排課的約束條件在排課的過程中，有些硬性約束條件必須遵循：如教師、教室、 課程、時間和地點均不可存在沖突；也有一些軟性約束因素值得考慮， 這樣

2、能使課表更加的合理和人性化，如專業(yè)課盡量安排在效率較高的 時間段；盡量滿足某些教師的特殊上課時間要求；同時排課也不能太零散，要盡量減少教師來校的次數(shù)；應(yīng)盡量避免學(xué)生一天課程很滿而 另一天卻整天沒課的情況，學(xué)生的上課時間不能安排得太過集中； 在 某個時間段不做任何教學(xué)任務(wù)的安排，以便教師和學(xué)生能利用這個時 間開展一些課余活動。2排課的遺傳算法設(shè)計2.1遺傳算法流程設(shè)計遺傳算法的核心內(nèi)容包括：參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度 函數(shù)的設(shè)計、遺傳操作設(shè)計及控制參數(shù)設(shè)定1。（1）基因編碼：對課程和授課教師進(jìn)行組合編碼，可以采用教 師編號（5位）+班級編號（5位）+教室編號（4位）+課程編號（6 位）+周

3、學(xué)時（2位）+特殊要求（6位）的編碼方式。（2）產(chǎn)生初始種群：首先把固定教學(xué)時間段的教師編碼填入對應(yīng)的時間段中，然后產(chǎn)生一個120的隨機數(shù)，根據(jù)產(chǎn)生的隨機數(shù)在 相應(yīng)的位置填入該班的其他教師編碼。若填入的位置已有數(shù)據(jù)，則重 新產(chǎn)生隨機數(shù)，直到所有的教師編碼無重復(fù)地填入數(shù)組。如此循環(huán)直 至產(chǎn)生滿足種群規(guī)模數(shù)量的個體，組成初始種群?？梢钥闯觯鲜龇?式產(chǎn)生的。(3) 沖突檢測：初始種群個體含有大量的沖突4，由于我們在 編碼已經(jīng)考慮到時間、班級、教室避免同時上一門以上課程的沖突， 因此，只需對同一時間，同一個教師同時上一門以上課程的沖突進(jìn)行 檢測和消除。(4) 沖突消除5:讀取第一個課程表二維數(shù)組 K

4、CB(BJS 20) 中第一個數(shù)據(jù)(教師編號)。將讀取的數(shù)據(jù)與KCB數(shù)組中該列下一行 的數(shù)據(jù)進(jìn)行比較，若一致，則選擇該行隨機列的數(shù)據(jù)，若可以調(diào)整， 則互換這兩個數(shù)據(jù)；若不可調(diào)整則再次對該行隨機列的數(shù)據(jù)進(jìn)行選取，直到數(shù)據(jù)互不相同。取該列第三行數(shù)據(jù)，重復(fù)操作至該列所有數(shù) 據(jù)互不相同為止。讀取 KCB( 1, 2)，重復(fù)以上過程，直至每列數(shù)據(jù) 互不相同，則沖突消除。該算法的對提高遺傳算法處理效率有明顯效 果。(5) 構(gòu)造適應(yīng)度函數(shù)：構(gòu)造函數(shù)f(1):考察多個教學(xué)時間段課 程盡量分散度；函數(shù)f(2):教師每天授課任務(wù)均衡度；函數(shù)f(3): 學(xué)生課時分布均衡度；函數(shù)f(4):課程安排時間適宜性。得到適應(yīng)

5、 度函數(shù)為：其中，k(i)為權(quán)值。(6) 遺傳算子選擇算子：模擬生物界中的優(yōu)勝劣汰的自然選擇過程， 采用賭盤 法(如圖2所示)，將適應(yīng)度高的個體放在輪盤較大區(qū)域，適應(yīng)度低 的放在輪盤的較小區(qū)域，則選擇適應(yīng)度高個體的幾率會明顯增大，從而篩選出適應(yīng)度較高的個體6。圖1賭盤選擇法交叉算子：選擇父本個體后隨機選出兩個個體， 隨機確定一個數(shù) 作為交叉位置進(jìn)行互換操作，如兩父本個體 F1、F2,位置為左起第6 億則：父本：F1 = 12345 6 789 F2=98765 4 321產(chǎn)生子代：P仁 12345 4 789 P2=98765 6 321變異算子：在染色體上隨機選擇兩點，將對應(yīng)數(shù)據(jù)進(jìn)行反轉(zhuǎn)，女

6、口：325 321 257 變異為 325 123 257(7) 參數(shù)設(shè)置種群規(guī)模，不宜過大也不宜過小。過小減弱群體多樣性，可能不 存在最優(yōu)解；過大則會增加計算量，降低算法的運算速度。交叉率， 交叉概率取值過大時，會近親繁殖，失去活力；過小對系統(tǒng)不利。一 般認(rèn)為取值在0.60.9之間，本系統(tǒng)取0.7。變異率，變異概率較 大時，會使遺傳算法變成隨機搜索；當(dāng)變異概率較小時，新個體的產(chǎn) 生會少。進(jìn)化迭代數(shù)，為了使最終結(jié)果既收斂又能達(dá)到最優(yōu)，那么遺 傳代數(shù)的取值應(yīng)該足夠大，本文遺傳代數(shù)取值為1000。3實例測試及分析本系統(tǒng)利用Matlab 7.6進(jìn)行了模擬測試，用到的數(shù)據(jù)如表 1所 示：表1實驗數(shù)據(jù)(

7、1 )種群規(guī)模選取三個對照組進(jìn)行實驗：表2種群規(guī)模對排課效率的影響(單位：秒)由表2可以看出，種群的規(guī)模越小，時間越短，效率也就越高(2) 交叉概率表3交叉概率對排課效率的影響(單位：秒)從表3中觀察到，交叉概率的取值較大時，它對系統(tǒng)效率的影響 則較小。經(jīng)過反復(fù)分析，本系統(tǒng) Pc取值為0.7。(3) 變異概率表4變異概率對排課效率的影響從表4看出，過大會使算法的穩(wěn)定性低，過小又會使得全局搜索 難以進(jìn)行，并且很難有較好的模式產(chǎn)生?；谝陨蠑?shù)據(jù)，可將排課求解過程中所需要的參數(shù)值設(shè)置如表5所示：表5參數(shù)設(shè)置實際求解效果如圖3所示：圖3遺傳進(jìn)化過程適應(yīng)度值變化曲線4結(jié)論實驗證明，應(yīng)用遺傳算法解決排課問題時收斂效果是比較好的。 參考文獻(xiàn)：1 張春梅,行飛.用自適應(yīng)的遺傳算法求解大學(xué)課表安排問題J.內(nèi)蒙古大學(xué)學(xué)報：自然科學(xué)版，2002,33(4):4594642 徐艷斌.基于遺傳算法的高校排課系統(tǒng)設(shè)計與分析.廣東工業(yè) 大學(xué)工學(xué)碩士學(xué)位論文D,2007,35473 胡小兵,魯宏偉,基丁 模糊專家系統(tǒng)的排課系統(tǒng)關(guān)鍵技術(shù)研 究.電力學(xué)院學(xué)報(自然科學(xué)版),2001:16(4)4 朱冠宇,王乘,席大春.利用遺傳算法求解中學(xué)課表安排問題.計算機工程與應(yīng)用，2004(27):