《高校自動(dòng)排課算法 算法設(shè)計(jì)》由會員分享，可在線閱讀，更多相關(guān)《高校自動(dòng)排課算法 算法設(shè)計(jì)（6頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、計(jì)算機(jī)算法分析與設(shè)計(jì) 算法分析與設(shè)計(jì)論文 高校自動(dòng)排課算法 姓 名：朱小波 班 級：09醫(yī)軟一班 學(xué) 號：09713054 高校自動(dòng)排課算法 朱小波，09713054 （安徽中醫(yī)學(xué)院 醫(yī)藥軟件開發(fā)專業(yè)，安徽 合肥 230031） 摘? 要：?? 提出并實(shí)現(xiàn)了一種高校自動(dòng)排課算法,利用遺傳算法建立數(shù)據(jù)模型,定義一個(gè)包含教師編號、班級編號、課程編號、教室編號、上課時(shí)間段的染色體編碼方案和適應(yīng)度函數(shù)，通過初始化種群、選擇、交叉、變異等過程不斷進(jìn)化，最后得到最優(yōu)解。利用該算法對某高校的真實(shí)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果顯示無一例教室、教

2、師、班級沖突，算法具有合理性和可行性。 關(guān)鍵詞? 遺傳算法； 排課問題； 適應(yīng)度函數(shù) ?University automatic arrangement algorithm ZHU Xiao-bo， 09713054 (anhui institute of traditional Chinese medicine and medical software development professional hefei, anhui 230031) Abstract:Put forward and realized a coll

3、ege automatic arrangement algorithm, setting up a data model by using the genetic algorithm, define a include teacher Numbers, class Numbers, course Numbers, classroom Numbers, the chromosomes of the class time coding scheme and fitness function, through the initial population, selection, crossover

4、and mutation process continuously evolved, finally get the optimal solution. By using the approach of a university in the real data of experiment, the results showed that no case was the classroom, teachers, and class conflicts, and the algorithm has rationality and feasibility. Key words :Genetic

5、 algorithm; Curriculum arrangement problems; Fitness function 作者簡介：朱小波，09713054, 09醫(yī)軟一班 0引言 1前言 ??? 每個(gè)學(xué)期對本校教學(xué)任務(wù)進(jìn)行合理安排是教務(wù)科的重要任務(wù)。其中排課是最為關(guān)鍵的環(huán)節(jié)。排課問題的本質(zhì)是將課程、教師和學(xué)生在合適的時(shí)間段內(nèi)分配到合適的教室中，涉及到的因素較多，是一個(gè)多目標(biāo)的調(diào)度問題，在運(yùn)籌學(xué)中被稱為時(shí)間表問題（Timetable Problem，簡稱TTP）。目前由于學(xué)校擴(kuò)招，學(xué)生和課程數(shù)量比以往大大增加，教室資源明顯不足，在這種情況下排課人員很難在同時(shí)兼顧多重

6、條件限制的情況下用人工方式排出令教師和學(xué)生都滿意的課表。 ??? 排課問題很早以前就成為眾多科研人員和軟件公司的研究課題，但是真正投入使用的排課軟件卻很少。原因是多方面的，其中算法的選擇是最關(guān)鍵的一個(gè)問題，S.Even等人在1975年的研究中證明了排課問題是一個(gè)NP-Complete問題，即若是用“窮舉法”之外的算法找出最佳解是不可能的。然而由于窮舉法成本太高，時(shí)間太長，根本無法在計(jì)算機(jī)上實(shí)現(xiàn)。因?yàn)榧僭O(shè)一個(gè)星期有n個(gè)時(shí)段可排課，有m位教師需要參與排課，平均每位教師一個(gè)星期上k節(jié)課，在不考慮其他限制的情況下，能夠推出的可能組合就有nm*k種，如此高的復(fù)雜度是目前計(jì)算機(jī)所無法承受的。因此眾多研究

7、者提出了多種其他排課算法，如模擬退火,列表尋優(yōu)搜索,約束滿意等[1]。其中，遺傳算法(Genetic Algorithm, 簡稱GA)是很有效的求解最優(yōu)解的算法。 ??? 遺傳算法是一種通過模擬自然界生物進(jìn)化過程求解極值的自適應(yīng)人工智能技術(shù)，是由美國芝加哥大學(xué)Holland教授于1962年首先提出的。遺傳算法借用了生物遺傳學(xué)的觀點(diǎn)，通過自然選擇、遺傳、變異等作用機(jī)制來提高各個(gè)個(gè)體的適應(yīng)性，體現(xiàn)了自然界中“物競天擇、適者生存”的進(jìn)化過程。遺傳算法也因此吸引了一大批的研究者，并廣泛應(yīng)用于函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)、圖像處理、模式識別等多個(gè)領(lǐng)域。 2? 排課問題描述 ???

8、 在排課問題中，我們的主要任務(wù)是將班級、教室、課程、教師安排在一周內(nèi)且不發(fā)生時(shí)間沖突[2]。據(jù)此，我們給出如下描述： ??? 學(xué)校有R間教室，C個(gè)班，S門課程，T位教師，P個(gè)時(shí)間段。 ??? ●教室集合R（R1,R2,…Rn），每間教室分別可容納（X1,X2…Xr）人； ??? ● 班級集合C（C1,C2,…Cn），每個(gè)班級分別有（K1,K2,…Kc）人，其中有x個(gè)班級上合班課； ??? ●課程集合S（S1,S2,…Sn），每門課對應(yīng)Ci個(gè)班，1位教師，（1≤ Ci

9、n

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

11、算法的解決方法，并對其進(jìn)行優(yōu)化操作。 3? ?遺傳算法 ???????? 遺傳算法采用類似基因演化的循環(huán)過程，其演算過程如下： ??? 1）隨機(jī)產(chǎn)生一定數(shù)目的初始種群 ??? 2）對個(gè)體適應(yīng)度進(jìn)行評估，如果個(gè)體的適應(yīng)度符合優(yōu)化準(zhǔn)則，則輸出最佳個(gè)體及其代表的最優(yōu)解，并結(jié)束計(jì)算，否則轉(zhuǎn)向第3步。 ??? 3）依據(jù)適應(yīng)度選擇再生個(gè)體 ??? 4）按照一定的交叉概率和交叉方法生成新的個(gè)體 ??? 5）按照一定的變異概率和變異方法生成新的個(gè)體 6）由交叉和變異產(chǎn)生新一代的種群，然后返回第2步。如圖1所示： 圖1 遺傳算法示意圖 ??? 以下是遺傳算法的偽代碼。

12、 ??? BEGIN: ??????? I = 0; ??????? Initialize P(I); ??????? Fitness P(I); ??????? While(not Terminate-Condition) ??????? { ??????????? I ++; ??????????? GA-Operation P(I); ??????????? Fitness P(I); ?????? } ????? END. 4? 設(shè)計(jì) 4.1? 染色體編碼 GA中首要考慮的是如何表現(xiàn)其問題，即如何對染色體編碼，使之適用于GA操作。在經(jīng)典的遺傳算法中，

13、常采用浮點(diǎn)數(shù)或二進(jìn)制的編碼方法，而研究中，每條染色體代表每位教師的課表，其結(jié)構(gòu)表示如下： 教師ID 班級ID 課程ID 教室 上課時(shí)間安排 ??? 染色體在程序中可用十進(jìn)制數(shù)編碼，例如：某一教師編號為1247，要教授“數(shù)據(jù)庫原理”這門課，“數(shù)據(jù)庫原理”課程編號為8017，周學(xué)時(shí)為4，班級為01811、01812，隨機(jī)產(chǎn)生上課時(shí)間，隨機(jī)選擇大于兩班總?cè)藬?shù)的教室，則可生成染色體如：“124701811018128017024012241”其中02401，2241分別代表教室及上課時(shí)間星期二第二個(gè)教學(xué)單元（即上午3、4節(jié)）和星期四第一個(gè)教學(xué)單元（即上午1、2節(jié)）。 ??? 按如

14、上編碼，兩條染色體對后9位作交叉操作，不會影響到每位教師所教授的課程，也不會造成教師課表內(nèi)含其他教師的教授課程或每代演化后染色體結(jié)構(gòu)不合理等問題。 每一條染色體表示一種可能的排課結(jié)果，至于排課結(jié)果的優(yōu)劣，則由適應(yīng)度函數(shù)評估染色體的適應(yīng)值來決定。 適應(yīng)度函數(shù)??? ??? 遺傳算法在進(jìn)化中是以每個(gè)個(gè)體的適應(yīng)度值為依據(jù)來選取下一代種群的。適應(yīng)度函數(shù)設(shè)定的好壞直接影響到遺傳算法的收斂速度和能否找到最優(yōu)解。在本系統(tǒng)中，適應(yīng)度函數(shù)的設(shè)計(jì)思想是對每條染色體中存在的沖突類型進(jìn)行加權(quán)求和，其中權(quán)值Wi代表的是第i條規(guī)則的重要程度，若某條染色體違反了 某條規(guī)則i，則將其值Pi置為1（若沒有違反規(guī)則i，則

15、Pi值為0），其受到的懲罰值為Wi*Pi，對染色體中存在的沖突進(jìn)行加權(quán)求和并加上1后，再求其倒數(shù)，如以下公式所示。染色體適應(yīng)度函數(shù)值越大，則表示其擁有較好的授課時(shí)段和教室，其在下一代的演化中的生存概率就較大。 4.2? 遺傳操作 ??? （1）初始化[Initialize] ??? 初始化的目的在于為后面的遺傳操作提供初始種群。 ??? 在我們的算法中，由于每次對一位教師進(jìn)行遺傳操作，初始化時(shí)就需要考慮到教室及時(shí)間的設(shè)定，這其中包括教室可容人數(shù)的最優(yōu)逼近（即避免一個(gè)30人的班級占用可容200人的教室這種情況），以及上課時(shí)間安排的合理性，這在排課問題描述中已有解釋。 ???

16、 （2）選擇[Select] ??? 選擇運(yùn)算用于模擬生物界去劣存優(yōu)的自然選擇現(xiàn)象。它從舊種群中選擇出適應(yīng)度高的某種染色體，放入配對集合中，為染色體交叉和變異運(yùn)算產(chǎn)生新種群做準(zhǔn)備。適應(yīng)度越高的染色體被選擇的可能性越大， ??? 選擇操作的方法有許多，如輪盤賭選擇法（roulette wheel selection），局部選擇法（local selection），錦標(biāo)賽選擇法（tournament selection）等。 研究中，我們選用了局部選擇法中的一種：截?cái)噙x擇法（truncation selection）。 在截?cái)噙x擇法中，染色體按適應(yīng)度函數(shù)值由高到低排序，只有最優(yōu)秀的個(gè)體才能

17、被選作父個(gè)體。其中，用于決定染色體被選作父個(gè)體的百分比的參數(shù)稱為截?cái)嚅y值Trunc，其取值范圍為50%~10%。在該閥值之外的個(gè)體不能產(chǎn)生子個(gè)體。算法中選擇強(qiáng)度與截?cái)嚅y值的關(guān)系如表1所示。 表1 選擇強(qiáng)度與截?cái)嚅y值的關(guān)系[5] 截?cái)嚅y值 1%? 10% 20% 40% 50% 80% 選擇強(qiáng)度 2.66 1.76 1.2? 0.97? 0.8 0.34 其中選擇強(qiáng)度是將正規(guī)高斯分布應(yīng)用于選擇方法，期望平均適應(yīng)度。 選擇強(qiáng)度表示為： 式中fc為下列高斯分布的積分下限： ??? （3）交叉[Crossover] ??? 交叉是根據(jù)選擇操作的結(jié)

18、果，選取兩條染色體作為父個(gè)體，再取一隨機(jī)值（設(shè)為r）與系統(tǒng)預(yù)設(shè)的交叉率值（設(shè)為t）比較，若r

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

20、 結(jié)果評估 本系統(tǒng)用Visual C++ 6.0軟件實(shí)現(xiàn)上述遺傳排課算法，并對某高校的真實(shí)數(shù)據(jù)作了測試。該校2002—2003學(xué)年上學(xué)期共有686個(gè)排課單元，上課教師356名，共有160間教室，412個(gè)行政班。圖2顯示了一代染色體在演化過程中最高適應(yīng)值和平均適應(yīng)值的變化情況，其中染色體為30條，交叉率為0.8，變異率為0.02，演化的代數(shù)為1000代。該算法具有較好的收斂性，也說明了本文中提到的染色體編碼方案和適應(yīng)度函數(shù)能夠較好地反映排課要求，染色體經(jīng)過世代進(jìn)化后可以得到令人滿意的最優(yōu)解。圖3是利用遺傳算法排出的01811,01812兩個(gè)班級某個(gè)學(xué)期的課表，從課表中可以看出該課表不存在教

21、師、教室、班級沖突，同一門課程兩次上課時(shí)間間隔都達(dá)到一天以上，并且沒有課程被安排在晚上，因此不管是硬約束條件還是軟約束條件都得到較好的滿足。 7? 結(jié)論 ??? 本文論述了利用遺傳算法求解高校課表的安排問題，實(shí)驗(yàn)證明文中提出的染色體編碼方案和適應(yīng)度函數(shù)是可行的，適應(yīng)度函數(shù)值能夠隨著進(jìn)化代數(shù)的增加而呈不斷上升趨勢，實(shí)驗(yàn)結(jié)果令人滿意。在染色體編碼方案方面，今后還準(zhǔn)備考慮更復(fù)雜的課程安排要求。 圖3? 基于遺傳算法的排課結(jié)果示例 參考文獻(xiàn) [1]業(yè)寧,梁作鵬,董逸生. 一種基于遺傳算法的ＴＴＰ問題求解算法. 東南大學(xué)學(xué)報(bào)(自然科學(xué)版)

22、.2003(1):41-44 [2]唐　勇,唐雪飛,王　玲.基于遺傳算法的排課系統(tǒng). 計(jì)算機(jī)應(yīng)用.2002(1):93-94,97 [3]H.L.Fang,”Genetic Algorithms in Timetabling and Scheduling”,Ph.D. Thesis,Department of Artificial Intelligence, University of Edinburgh, UK,1994. [4] E.K. Burke, D.G. Elliman, R.F. Weare, "A Genetic Algorithm Based University Timetabling System", East-West Conference on Computer Technologies in Education, Crimea, Ukraine, 1994, pp. 35-40. [5] 王小平,曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn).西安：西安交通大學(xué)出版社，2002:31-33