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

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

1、從本學科出發(fā)，應著重選對國民經(jīng)濟具有一定實用價值和理論意義的課題。課題具有先進性，便于研究生提出新見解，特別是博士生必須有創(chuàng)新性的成果基于遺傳算法的高校排課系統(tǒng)研究GA中首要考慮的是如何表現(xiàn)其問題，即如何對染色體編碼，使之適用于GA操作。在經(jīng)典的遺傳算法中，常采用浮點數(shù)或二進制的編碼方法，而研究中，每條染色體代表每位教師的課表，其結(jié)構(gòu)表示如下：教師ID班級ID課程ID教室上課時間安排染色體在程序中可用十進制數(shù)編碼，例如：某一教師編號為1247，要教授“數(shù)據(jù)庫原理”這門課，“數(shù)據(jù)庫原理”課程編號為8017

2、，周學時為4，班級為01811、01812，隨機產(chǎn)生上課時間，隨機選擇大于兩班總?cè)藬?shù)的教室，則可生成染色體如：“12241”其中02401，2241分別代表教室及上課時間星期二第二個教學單元和星期四第一個教學單元。按如上編碼，兩條染色體對后9位作交叉操作，不會影響到每位教師所教授的課程，也不會造成教師課表內(nèi)含其他教師的教授課程或每代演化后染色體結(jié)構(gòu)不合理等問題。每一條染色體表示一種可能的排課結(jié)果，至于排課結(jié)果的優(yōu)劣，則由適應度函數(shù)評估染色體的適應值來決定。適應度函數(shù)遺傳算法在進化中是以每個個體的適應度值

3、為依據(jù)來選取下一代種群的。適應度函數(shù)設定的好壞直接影響到遺傳算法的收斂速度和能否找到最優(yōu)解。在本系統(tǒng)中，適應度函數(shù)的設計思想是對每條染色體中存在的沖突類型進行加權(quán)求和，其中權(quán)值Wi代表的是第i條規(guī)則的重要程度，若某條染色體違反了初始化[Initialize]課題份量和難易程度要恰當，博士生能在二年內(nèi)作出結(jié)果，碩士生能在一年內(nèi)作出結(jié)果，特別是對實驗條件等要有恰當?shù)墓烙?。從本學科出發(fā)，應著重選對國民經(jīng)濟具有一定實用價值和理論意義的課題。課題具有先進性，便于研究生提出新見解，特別是博士生必須有創(chuàng)新性的成果初始

4、化的目的在于為后面的遺傳操作提供初始種群。在我們的算法中，由于每次對一位教師進行遺傳操作，初始化時就需要考慮到教室及時間的設定，這其中包括教室可容人數(shù)的最優(yōu)逼近，以及上課時間安排的合理性，這在排課問題描述中已有解釋。選擇[Select]選擇運算用于模擬生物界去劣存優(yōu)的自然選擇現(xiàn)象。它從舊種群中選擇出適應度高的某種染色體，放入配對集合中，為染色體交叉和變異運算產(chǎn)生新種群做準備。適應度越高的染色體被選擇的可能性越大，選擇操作的方法有許多，如輪盤賭選擇法，局部選擇法，錦標賽選擇法等。研究中，我們選用了局部選擇

5、法中的一種：截斷選擇法。在截斷選擇法中，染色體按適應度函數(shù)值由高到低排序，只有最優(yōu)秀的個體才能被選作父個體。其中，用于決定染色體被選作父個體的百分比的參數(shù)稱為截斷閥值Trunc，其取值范圍為50%~10%。在該閥值之外的個體不能產(chǎn)生子個體。算法中選擇強度與截斷閥值的關系如表1所示。表1選擇強度與截斷閥值的關系[5]截斷閥值1%10%0%0%0%80%選擇強度其中選擇強度是將正規(guī)高斯分布應用于選擇方法，期望平均適應度。選擇強度表示為：SelIntTrunc(Trunc)=式中fc為下列高斯分布的積分下限：

6、Trunc=交叉[Crossover]課題份量和難易程度要恰當，博士生能在二年內(nèi)作出結(jié)果，碩士生能在一年內(nèi)作出結(jié)果，特別是對實驗條件等要有恰當?shù)墓烙嫛谋緦W科出發(fā)，應著重選對國民經(jīng)濟具有一定實用價值和理論意義的課題。課題具有先進性，便于研究生提出新見解，特別是博士生必須有創(chuàng)新性的成果交叉是根據(jù)選擇操作的結(jié)果，選取兩條染色體作為父個體，再取一隨機值與系統(tǒng)預設的交叉率值比較，若rm，在變異時先產(chǎn)生一個隨機數(shù)r，當rm時，執(zhí)行變異操作，否則不執(zhí)行。例如：有一染色體編碼為：“0872’01211’1005’04

7、201’122”，它表示星期二的第一、二教學單元節(jié)有編號為“1005”的課程，經(jīng)變異，該染色體變成：“0872’01211’1005’04201’152”，染色體的適應度大大提高。5沖突問題解決排課問題是一個NP-Complete問題，無論采用哪種方法都無法避免各種沖突問題的出現(xiàn)，同一位教師在同一時段內(nèi)排了兩門課是沖突問題中最明顯的一個。為了避免這種沖突產(chǎn)生，在本系統(tǒng)開發(fā)中引進了一個沖突檢測函數(shù)fConflict()，當排完一位教師的所有課程之后，系統(tǒng)就會用該函數(shù)對此教師課程安排的沖突情況進行檢測并作修

8、正。6結(jié)果評估本系統(tǒng)用VisualC++.0軟件實現(xiàn)上述遺傳排課算法，并對某高校的真實數(shù)據(jù)作了測試。該校XX—XX學年上學期共有686個排課單元，上課教師356名，共有160間教室，412個行政班。圖2顯示了一代染色體在演化過程中最高適應值和平均適應值的變化情況，其中染色體為30條，交叉率為，變異率為，演化的代數(shù)為1000代。圖2算例最高適應值-平均適應值曲線課題份量和難易程度要恰當，博士生能在二年內(nèi)作出結(jié)果，碩士生能在一年內(nèi)作出結(jié)果，特別