基于遺傳算法高校排課系統(tǒng)研究

《基于遺傳算法高校排課系統(tǒng)研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、基于遺傳算法的高校排課系統(tǒng)研究沈麗容?陳明磊（南京林業(yè)大學(xué)信息學(xué)院計算機(jī)科學(xué)與工程系?南京210037）????摘?要??提出并實現(xiàn)了一種高校自動排課算法,利用遺傳算法建立數(shù)據(jù)模型,定義一個包含教師編號、班級編號、課程編號、教室編號、上課時間段的染色體編碼方案和適應(yīng)度函數(shù)，通過初始化種群、選擇、交叉、變異等過程不斷進(jìn)化，最后得到最優(yōu)解。利用該算法對某高校的真實數(shù)據(jù)進(jìn)行實驗，結(jié)果顯示無一例教室、教師、班級沖突，算法具有合理性和可行性。???關(guān)鍵詞?遺傳算法；排課問題；適應(yīng)度函數(shù)?1?前言???每個學(xué)期對本校教學(xué)任務(wù)進(jìn)行合理安排是教

2、務(wù)科的重要任務(wù)。其中排課是最為關(guān)鍵的環(huán)節(jié)。排課問題的本質(zhì)是將課程、教師和學(xué)生在合適的時間段內(nèi)分配到合適的教室中，涉及到的因素較多，是一個多目標(biāo)的調(diào)度問題，在運籌學(xué)中被稱為時間表問題（TimetableProblem，簡稱TTP）。目前由于學(xué)校擴(kuò)招，學(xué)生和課程數(shù)量比以往大大增加，教室資源明顯不足，在這種情況下排課人員很難在同時兼顧多重條件限制的情況下用人工方式排出令教師和學(xué)生都滿意的課表。???排課問題很早以前就成為眾多科研人員和軟件公司的研究課題，但是真正投入使用的排課軟件卻很少。原因是多方面的，其中算法的選擇是最關(guān)鍵的一個問題

3、，S.Even等人在1975年的研究中證明了排課問題是一個NP-Complete問題，即若是用“窮舉法”之外的算法找出最佳解是不可能的。然而由于窮舉法成本太高，時間太長，根本無法在計算機(jī)上實現(xiàn)。因為假設(shè)一個星期有n個時段可排課，有m位教師需要參與排課，平均每位教師一個星期上k節(jié)課，在不考慮其他限制的情況下，能夠推出的可能組合就有nm*k種，如此高的復(fù)雜度是目前計算機(jī)所無法承受的。因此眾多研究者提出了多種其他排課算法，如模擬退火,列表尋優(yōu)搜索,約束滿意等[1]。其中，遺傳算法(GeneticAlgorithm,簡稱GA)是很有效的

4、求解最優(yōu)解的算法。???遺傳算法是一種通過模擬自然界生物進(jìn)化過程求解極值的自適應(yīng)人工智能技術(shù)，是由美國芝加哥大學(xué)Holland教授于1962年首先提出的。遺傳算法借用了生物遺傳學(xué)的觀點，通過自然選擇、遺傳、變異等作用機(jī)制來提高各個個體的適應(yīng)性，體現(xiàn)了自然界中“物競天擇、適者生存”的進(jìn)化過程。遺傳算法也因此吸引了一大批的研究者，并廣泛應(yīng)用于函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)、圖像處理、模式識別等多個領(lǐng)域。2?排課問題描述???在排課問題中，我們的主要任務(wù)是將班級、教室、課程、教師安排在一周內(nèi)且不發(fā)生時間沖突[2]。據(jù)此，我們給

5、出如下描述：???學(xué)校有R間教室，C個班，S門課程，T位教師，P個時間段。???●教室集合R（R1,R2,…Rn），每間教室分別可容納（X1,X2…Xr）人；???●班級集合C（C1,C2,…Cn），每個班級分別有（K1,K2,…Kc）人，其中有x個班級上合班課；???●課程集合S（S1,S2,…Sn），每門課對應(yīng)Ci個班，1位教師，（1≤Ci

6、Pn)，假設(shè)一周上五天課，每天分為五個教學(xué)單元，每個單元為2個課時，即上午2個，下午2個,晚上1個，則時間集合包含25個時間段。如11代表周一第一個教學(xué)單元，即周一1、2節(jié)，12代表周一第二個教學(xué)單元，即周一3、4節(jié)，以此類推，這些時間段構(gòu)成一個時間集合P(11,12,13,….55)。???一張正確的課表應(yīng)至少滿足以下硬約束條件：[3]???⑴一個教師或者一個班級或者一個教室在同一時間段內(nèi)只能安排一門課程；???⑵分配的教室可容納人數(shù)應(yīng)該大于學(xué)生數(shù)。???除了上述的硬性約束，還有些軟約束，這些軟約束有助于使得課表更加合理，更加

7、人性化。這些軟約束條件可能是[4]：???⑴盡量在早上安排必修課，而下午安排選修課，晚上盡量不排課；???⑵盡可能滿足個別教師的特殊上課時間要求；???⑶一門課盡量分散在一個星期中，即某天上完某一門課后，要隔一天以上再上這門課，以使教師有充足的時間備課和批改作業(yè)，而學(xué)生也有足夠的時間復(fù)習(xí)消化；???(4)一個教師的課不能排滿一整天；???(5)學(xué)生課表中的上課時間不能過分集中，應(yīng)避免一天課程很滿而另一天卻一整天沒課的情況。這些軟約束條件各院校有所不同，在我們的研究中，旨在我們定義的約束范圍內(nèi)給出一個遺傳算法的解決方法，并對其進(jìn)行

8、優(yōu)化操作。3??遺傳算法????????遺傳算法采用類似基因演化的循環(huán)過程，其演算過程如下：???1）隨機(jī)產(chǎn)生一定數(shù)目的初始種群???2）對個體適應(yīng)度進(jìn)行評估，如果個體的適應(yīng)度符合優(yōu)化準(zhǔn)則，則輸出最佳個體及其代表的最優(yōu)解，并結(jié)束計算，否則轉(zhuǎn)向第3步。???3）依