排課系統(tǒng)的遺傳算法交叉算子實現(xiàn)畢業(yè)論文

1、<p>　　本科畢業(yè)論文（設(shè)計）</p><p>　　題目：排課系統(tǒng)的遺傳算法交叉算子實現(xiàn)</p><p>　　學 院：計算機與信息工程學院</p><p>　　學生姓名： *** </p><p>　　學 號： ******** </p><p&

2、gt;　　專 業(yè)： 計算機科學與技術(shù) </p><p>　　年 級： 2008級 </p><p>　　完成日期： 2012年4月 </p><p>　　指導教師： *** </p><p>　　排課系統(tǒng)的遺傳算法交叉算子實現(xiàn)</p>&l

3、t;p>　　摘要：近年來隨著各大高校的不斷擴招和合并，由于教室有限，排課逐漸成為一個日益復雜的問題，課程的編排以及教室的合理利用為教學管理的工作加大了難度。遺傳算法，是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。遺傳算法作為一種新的全局優(yōu)化搜索算法，以其簡單通用、魯棒性強、適于并行處理及應用范圍廣等顯著特點，奠定了它作為21世紀關(guān)鍵智能計算之一的地位。所以本文以遺傳算法為工具，對排課問題進行了深入的研究，設(shè)計了其中的交

4、叉算子，在實際應用中有一定的意義。</p><p>　　關(guān)鍵詞：遺傳算法；排課系統(tǒng)；交叉算子</p><p>　　Implementation of the Crossover of the Genetic Algorithm for Class Scheduling System </p><p>　　Abstract: In recent years, with

5、 continuous enrollment and consolidation of the major colleges and universities, and there are not enough classrooms, the course scheduling is becoming an increasingly complex problems. The genetic algorithm is the calcu

6、lation model of genetic selection imitating Darwin's natural selection of biological evolution process. Genetic algorithm as a new global optimization search algorithm, with its simple and universal, strong robustnes

7、s, suitable for parallel processi</p><p>　　Key words: Genetic Algorithms; Scheduling System; Crossover operator</p><p><b>　　目 錄</b></p><p><b>　　1 緒論（1）</b&g

8、t;</p><p>　　1.1 課題研究背景及意義（1）</p><p>　　1.2 課題主要研究內(nèi)容（1）</p><p>　　2 Microsoft visual C++ 6.0開發(fā)環(huán)境簡介（1）</p><p>　　3 排課系統(tǒng)的總體問題分析（2）</p><p>　　3.1 高校排課問題概述（2）&

9、lt;/p><p>　　3.2 排課問題的硬性約束（3）</p><p>　　3.2.1 課程問題分析（3）</p><p>　　3.2.2 班級問題分析（3）</p><p>　　3.2.3 教師問題分析（3）</p><p>　　3.2.4 教室問題分析（3）</p><p>　　3.

10、2.5 時間問題分析（3）</p><p>　　3.3 排課問題的軟性約束（3）</p><p>　　4 遺傳算法的設(shè)計（4）</p><p>　　4.1 遺傳算法概述（4）</p><p>　　4.2 遺傳算法分析（4）</p><p>　　4.2.1 遺傳算法的基本思想（4）</p>&l

11、t;p>　　4.2.2 遺傳算法基本算子（5）</p><p>　　4.2.3 交叉的數(shù)據(jù)結(jié)構(gòu)（8）</p><p>　　4.2.4 適應度量（8）</p><p>　　5 面向?qū)ο笤谂耪n系統(tǒng)中的應用（9）</p><p>　　5.1 定義班級類（9）</p><p>　　5.2 定義教室類（10）&

12、lt;/p><p>　　5.3 定義教師類（10）</p><p>　　5.4 定義課程類（11）</p><p>　　5.5 設(shè)定配置文件（11）</p><p>　　6 運行調(diào)試（15）</p><p><b>　　參考文獻（17）</b></p><p><

13、;b>　　致謝（18）</b></p><p><b>　　1 緒論</b></p><p>　　1.1 課題研究背景及意義</p><p>　　21世紀后，世界跨入了一個以高科技為產(chǎn)業(yè)支柱的知識經(jīng)濟時代。知識經(jīng)濟的出現(xiàn)，預示著人類社會正在進入一個以智力資源為主要依托的經(jīng)濟時代。高校作為高級人才培養(yǎng)的陣地，必將迎來新的挑戰(zhàn)。

14、作為傳播科學知識的高等學校，只有了解和掌握了文化知識、的科學技術(shù)前沿，才能培養(yǎng)出合格的人才，也將在激烈的競爭洪流中立于不敗之地。高等院校培養(yǎng)學生的主要途徑就是教學。在教學活動中，有一系列的教學管理工作。其中，教學計劃的實施則是一個重要環(huán)節(jié)。課表是高校實施教學計劃的時間安排，它對維護教學秩序，保證教學質(zhì)量具有相當重要的作用。</p><p>　　隨著近幾年各個高校的合并與擴招，我國的綜合性大學和各個高校中在校的學生

15、數(shù)量的大大增加，對于高校教務(wù)部門來說，排課工作是非常令人頭痛的事，經(jīng)常會出現(xiàn)課程排列沖突，比如：一個教師在同一時間上兩門課，有兩個教師同時去了一個教室上不同的課程，有些教師在特定時間不可以上課。如果沒有很好地解決這些沖突，必然產(chǎn)生教學混亂等現(xiàn)象?？梢姡耪n算法的正確性、高效性是非常關(guān)鍵的。 </p><p>　　1.2 課題主要研究內(nèi)容</p><p>　　由于排課問題是一個有約束的、多目

16、標的、難解的組合優(yōu)化問題，單純采用數(shù)學算法或單一算法是很難解決排課的問題的。采用智能性和并行性的遺傳算法對排課問題來進行求解，是求解該問題所有的方法中比較明智的選擇。本文在相關(guān)的遺傳算法和多目標優(yōu)化理論的基礎(chǔ)上，提出一個課表的隨機生成和優(yōu)化的算法，該算法能夠較大程度地反映實際排課的情況并且盡量達到多個目標最優(yōu)的目的。本論文的研究內(nèi)容有：詳細的介紹遺傳算法的產(chǎn)生、發(fā)展及特點，遺傳算法的基本思想和基本操作，模式定理以及擴展的模式定理，應用遺

17、傳算法的關(guān)鍵等。說明排課問題中的幾大要素和常用約束條件，分析排課問題中求解的難點和目標，給出排課問題完整的數(shù)學描述，并且提出本文求解排課問題方案中的總體思路。對于一個實際問題的算例，利用上述隨機生成方案的算法和基于遺傳算法的排課優(yōu)化算法來進行求解，并對一些中間值進行跟蹤分析，從實驗的角度論述該算法的可行性。</p><p>　　2 Microsoft visual C++ 6.0開發(fā)環(huán)境簡介</p>

18、<p>　　Visual C++是一個功能強大的可視化軟件開發(fā)工具。自1993年微軟公司推出Visual C++1.0后，隨著其新版本不斷問世，Visual C++已經(jīng)成為專業(yè)程序員進行軟件開發(fā)首選的編譯工具。</p><p>　　雖然微軟公司推出了Visual C++7.0，但它的應用有很大的局限性，只適用于Windows 2000,Windows XP和Windows NT4.0。所以實際中，更多

19、的是以Visual C++6.0為平臺。</p><p>　　Visual C++6.0不僅是一個C++編譯器，而且是一個基于Windows系統(tǒng)的可視化集成開發(fā)環(huán)境。Visual C++6.0由許多的組件組成，包括編輯器、調(diào)試器及類向?qū)lass Wizard、程序向?qū)ppWizard等開發(fā)工具。 這些組件通過Developer Studio組件集成為和諧的開發(fā)環(huán)境。圖2.1為操作窗口。</p>

20、<p>　　圖2.1 VC操作窗口</p><p>　　3 排課系統(tǒng)的總體問題分析</p><p>　　3.1 高校排課問題概述</p><p>　　排課是高校教學管理當中十分重要卻又相當復雜的一種管理工作，其實質(zhì)就是給學校所設(shè)置的課程來安排時間和地點，使整個教學過程能有計劃有秩序的來進行。編排課表是一個能夠涉及到多種因素的組合規(guī)劃問題，其要保證在課程安排

21、中學生、教師、教室不能夠產(chǎn)生沖突 (所謂的沖突，就是將需要上不同課程的兩個或者多個班安排在同一時間段、同一教室，或者為同一個教師在同一時間安排多門課程等的情況)，并且還要滿足教師的要求與資源限制等的約束條件。目前，國內(nèi)大部分中學仍然采用手工排課的方法。手工排課的主要手段是“擺牌”，就是在一個空課表的版面上把有課名的牌擺在適當?shù)恼n表的位置上，整個過程邊擺邊觀察邊調(diào)整，憑借擺牌的經(jīng)驗將各門課程擺在合理的位置上，最后才形成一個有效且合理的

22、課程表。這種手工的辦法沒有一定的規(guī)律，也沒有理論指導，還沒有數(shù)據(jù)模型，所以具有很大的盲目性。因此，要為眾多的學生和眾位教師安排出合理的課程表，則往往需要花費管理人員大量的時間，不僅工作量大，而且排出的課程表不宜調(diào)整。近年來，隨著中國教育體制改革不斷的深入，學生人數(shù)不斷上升，課程設(shè)置不斷向著深度和廣度發(fā)展，手工進行排課的缺點愈加突出。由于計算機運算</p><p>　　3.2 排課問題的硬性約束</p&g

23、t;<p>　　3.2.1 課程問題分析</p><p>　　課程是由課程號來決定的，同一課程名稱不一定就是同一課程，因為它們在教材采用以及教學要求上可能會有所不同。每門課程對教學資源以及教師都有一定的要求，比如英語聽力課，可能就會要求教室安裝語音裝置。</p><p>　　3.2.2 班級問題分析</p><p>　　排課問題中將班級作為學習的一個排

24、課要素，同一個班級指的是按照同一個教學計劃進行學習的學生集合。</p><p>　　3.2.3 教師問題分析</p><p>　　一般情況下，同一個專業(yè)的某個課程會固定的由一個教師來進行授課，但是可能上某一門課程的班級較多，就可能由多名教師講授同一門課程了。</p><p>　　3.2.4 教室問題分析</p><p>　　教室在排課問題中作

25、為一個非常重要的教學資源來進行規(guī)劃和分配，排課過程中就是把教室當作一個有限的空間分配給進行排課的對象。3.2.5 時間問題分析</p><p>　　在學校的教學中，時間可以分為學年、學期、周、天。學校一般情況都會安排一個學期的課程表，而在課表上是以周來顯示。時間在課程安排中也是當作一個有限的資源來分配給排課對象的。</p><p>　　3.3 排課問題的軟性約束</p>&

26、lt;p>　　除了上述的硬性約束，還有一些約束比如：某個教師希望或者不希望在某個時間段上課；體育課和自習課最好不要排在每天的第一二節(jié)課；同一門課程在一周內(nèi)的分布盡可能的均勻等，這些要求稱為軟性約束，因為它們或者可以通過排課之外的方法，比如變更其他事務(wù)的日程安排來加以解決；或者只能盡可能的滿足，而不可能全部都滿足。</p><p><b>　　4 遺傳算法的設(shè)計</b></p>

27、;<p>　　4.1 遺傳算法概述</p><p>　　遺傳算法是由John.H.Holland根據(jù)生物進化的模型提出的一種優(yōu)化結(jié)果的算法，它是基于生物進化過程中的信息遺傳的機制和自然選擇中優(yōu)勝劣汰的原則和搜索算法。該算法從一個種群開始，利用選擇、交叉、變異等遺傳算子來對種群進行不斷的進化選擇和淘汰，最后得到全局最優(yōu)解或者近似最優(yōu)解。根據(jù)其算法的特點，遺傳算法非常適合于排課問題。</p>

28、<p>　　4.2 遺傳算法分析</p><p>　　4.2.1 遺傳算法的基本思想</p><p>　　遺傳算法是從要解決的問題可能存在解集的一個種群(population)開始的，這個種群則是由經(jīng)過基因(gene)和編碼(coding)的一定數(shù)目的個體(individual)組成的。每個個體實際上就是染色體(chromosome)帶有特征的實體。遺傳物質(zhì)的主要載體是染色體

29、，即許多個基因的集合，其基因型就是某種基因的組合，它來決定個體的性狀和外部表現(xiàn)。所以，開始時需要實現(xiàn)從表現(xiàn)型到基因型的映射也就是進行編碼工作。第一代種群產(chǎn)生后，按照優(yōu)勝劣汰的原理，逐代(generation)演化產(chǎn)生出越來越好的近似解。在每一代，根據(jù)問題域中每個個體的適應度(fitness)大小來挑選(selection)個體，并借助自然遺傳學的遺傳算子(genetic operators)來進行組合交叉(crossover)和變異(m

30、utation)，產(chǎn)生出帶有新的解集的種群。此過程將導致種群自然進化出一樣的后代種群且比前代更加適應環(huán)境，末代種群的最優(yōu)個體經(jīng)過解碼(decoding )后，可以用來作為問題的近似最優(yōu)解。遺傳算法利用自然進化模型，如選擇、交叉、變異等。當計算開始，會隨機的初始化一定數(shù)目的個體(Paren</p><p>　　下面給出遺傳算法的具體步驟，流程圖參見圖4.1：</p><p>　　第一步：選擇

31、編碼的策略，把參數(shù)集合（可行解的集合）轉(zhuǎn)換染色體結(jié)構(gòu)空間；</p><p>　　第二步：定義適應度函數(shù)，便于計算適應值；</p><p>　　第三步：確定遺傳策略，包括選擇群體大小，選擇、交叉、變異的方法以及確定交叉的概率、變異的概率等遺傳參數(shù)；</p><p>　　第四步：隨機產(chǎn)生初始化的群體；</p><p>　　第五步：計算群體中的個體

32、或者染色體解碼后的適應值；</p><p>　　第六步：按照遺傳的策略，運用選擇、交叉和變異算子作用于群體，形成下一代的群體；</p><p>　　第七步：判斷群體性能是否能滿足某一指標、或者是否已完成預定的迭代次數(shù)，不滿足則返回第五步、或者修改遺傳策略后再返回第六步。</p><p>　　圖4.1 遺傳算的流程圖</p><p>　　4.2

33、.2 遺傳算法的基本算子</p><p>　　遺傳算法包括三個基本的核心遺傳算子：</p><p><b>　　選擇算子</b></p><p>　　選擇操作是從當前的種群中選擇出較好的染色體個體，并且為個體交叉和變異的運算產(chǎn)生新的個體做好準備。隨著候選的個體適應度的不斷提高，被選中的概率也就隨之變大，其后代在下一代中出現(xiàn)的數(shù)量也就相應增加，

34、染色體在下一代中群眾的分布也就隨之變廣。</p><p><b>　　交叉算子</b></p><p>　　交叉又稱為雜交或者交換。交叉操作利用部分匹配交叉法，要求選擇兩個隨機的交叉點，用來確定一個匹配的段，在根據(jù)兩個父個體中的兩交叉點間的中間段所給出的映射關(guān)系來生成兩個子代個體。這樣的話，因為每個個體都是一個矩陣，先隨機的選擇某行，在依次的比較兩個父個體在此行對應的

35、每個元素。若兩個父個體相對應的元素都有是0的情況，那么保持位置不變；若兩個股個體相對應的元素都不為0（都含有課程對象），則在交換各自父個體中對應課程對象的位置。</p><p>　　這種交換方式能夠避免班級和教師、教室之間的沖突，不會打亂班級元組的元素。</p><p>　　以下是交叉算子的程序段</p><p>　　// 利用染色體和指針返回給后代進行交叉操作&l

36、t;/p><p>　　Schedule* Schedule::Crossover(const Schedule& parent2) const</p><p><b>　　{</b></p><p>　　//檢查交叉操作的概率</p><p>　　if( rand() % 100 > _crossoverPro

37、bability )</p><p>　　//沒有交叉，只是復制第一代</p><p>　　return new Schedule( *this, false );</p><p>　　//新的染色體對象，復制染色體的設(shè)置</p><p>　　Schedule* n = new Schedule( *this, true );</p&g

38、t;<p><b>　　//班數(shù)</b></p><p>　　int size = (int)_classes.size();</p><p>　　vector<bool> cp( size );</p><p>　　//確定交叉點(隨機)</p><p>　　for( int i = _num

39、berOfCrossoverPoints; i > 0; i-- )</p><p><b>　　{</b></p><p>　　while( 1 )</p><p><b>　　{</b></p><p>　　int p = rand() % size;</p><p&g

40、t;　　if( !cp[ p ] )</p><p><b>　　{</b></p><p>　　cp[ p ] = true;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>

41、　　}</b></p><p><b>　　}</b></p><p>　　hash_map<CourseClass*, int>::const_iterator it1 = _classes.begin();</p><p>　　hash_map<CourseClass*, int>::const_iter

42、ator it2 = parent2._classes.begin();</p><p>　　//通過結(jié)合父母代碼的新代碼</p><p>　　bool first = rand() % 2 == 0;</p><p>　　for( int i = 0; i < size; i++ )</p><p><b>　　{</

43、b></p><p>　　if( first )</p><p><b>　　{</b></p><p>　　//從第一個父代的染色體的類表插入新的類</p><p>　　n->_classes.insert( pair<CourseClass*, int>( ( *it1 ).first, (

44、*it1 ).second ) );</p><p>　　//復制類的所有時間空間插槽</p><p>　　for( int i = ( *it1 ).first->GetDuration() - 1; i >= 0; i-- )</p><p>　　n->_slots[ ( *it1 ).second + i ].push_back( ( *it

45、1 ).first );</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　//插入第二個父類到新的染色體的類表</p><p>　　n->_class

46、es.insert( pair<CourseClass*, int>( ( *it2 ).first,( *it2 ).second ) );</p><p>　　//復制類的所有時間空間插槽</p><p>　　for( int i = ( *it2 ).first->GetDuration() - 1; i >= 0; i-- )</p><

47、p>　　n->_slots[ ( *it2 ).second + i ].push_back( ( *it2 ).first );</p><p><b>　　}</b></p><p><b>　　//交叉點</b></p><p>　　if( cp[ i ] )</p><p>&l

48、t;b>　　//改變原染色體</b></p><p>　　first = !first;</p><p><b>　　it1++;</b></p><p><b>　　it2++;</b></p><p><b>　　}</b></p><

49、p>　　n->CalculateFitness();</p><p>　　//智能指針返回給后代</p><p><b>　　return n;</b></p><p><b>　　}</b></p><p><b>　　變異算子</b></p>&l

50、t;p>　　變異操作的主要作用是來調(diào)整教師和班級時間的沖突。利用變異操作的局部隨機搜索的能力，在運算結(jié)果接近最優(yōu)解的時候，可以快速的向最優(yōu)解收斂。雖然發(fā)生的概率比較小，但能夠防止搜索得到的解陷入次優(yōu)解中，能夠保證種群的多樣性。通過隨機的變異還能確保生成不同的個體，進而能夠使解在解空間中均勻的分布。</p><p>　　4.2.3 交叉的數(shù)據(jù)結(jié)構(gòu)</p><p>　　兩個class s

51、chedule雜交：將對應的兩個hash map分成幾部分(幾部分需要定義參數(shù))，交替合成一個新的hash map，然后得到一個新的vector list.</p><p>　　圖4.2交叉算子數(shù)據(jù)結(jié)構(gòu)</p><p>　　4.2.4 適應度量</p><p>　　對一個課程編排，該編排中的每個課程班按下面規(guī)則賦值算法中的適應度量(Fitness)（取值范圍0~7的

52、整數(shù)）：</p><p>　　如果一個class用了一個滿足class條件（起始到終止周內(nèi)，隔周還是全周，等條件）的空的room，則score (class):= score (class)+1;</p><p>　　如果一個class需要lab而安排的room是lab，或如果需要media而安排在有media的room，或class不需要lab和media，則score (class):

53、= score (class)+1;</p><p>　　如果一個class被安排在一個座位充裕的room，則score (class):= score (class)+1;</p><p>　　如果一個class的professor此時刻沒有別的class，則score (class):= score (class)+1;</p><p>　　如果一個class的

54、group此時刻沒有別的class，則score (class):= score (class)+1;</p><p>　　如果一個class在一個professor中意的section，則 score (class):= score (class)+1;</p><p>　　如果一個class在一個professor中意的學周，則 score (class):= score (class

55、)+1;</p><p>　　其他情形：score(class)不變.</p><p>　　求和所有class的score: schedule_score=sum of score of all class</p><p>　　Fitness=schedule_score/(#classes*7) (fitness介于0和1之間float型，當=1時就找到滿足所

56、有條件的schedule)</p><p>　　5 面向?qū)ο笤谂耪n系統(tǒng)中的應用</p><p><b>　　5.1 定義班級類</b></p><p>　　class CourseClass;</p><p>　　class StudentsGroup//存儲學生組的數(shù)據(jù)</p><

57、p><b>　　{</b></p><p><b>　　private:</b></p><p>　　int _id; //定義學生班ID</p><p>　　string _name; //定義學生班名稱</p><p>　　int _number

58、OfStudents; //定義學生數(shù)量</p><p>　　list<CourseClass*> _courseClasses; //類組出席列表</p><p><b>　　public:</b></p><p>　　StudentsGroup(int id, const string& nam

59、e, int numberOfStudents); </p><p>　　//初始化學生組數(shù)據(jù)</p><p>　　void AddClass(CourseClass* courseClass); //綁定到類組</p><p>　　inline int GetId() const { return _id; } //返回學生班ID</p

60、><p>　　inline const string& GetName() const { return _name; }//返回學生班名稱</p><p>　　inline int GetNumberOfStudents() const { return _numberOfStudents; }//返回學生班數(shù)量</p><p

61、>　　inline const list<CourseClass*>& GetCourseClasses() const { return _courseClasses; }// 返回類組出席列表參數(shù)</p><p>　　inline bool operator ==(const StudentsGroup& rhs) const { return _id =

62、= rhs._id; }</p><p>　　};// 比較代表學生團體的兩個對象的編號</p><p><b>　　5.2 定義教室類</b></p><p>　　class Room</p><p><b>　　{</b></p><p><b&

63、gt;　　private:</b></p><p>　　static int _nextRoomId; // ID計數(shù)器，用于自動分配的ID</p><p><b>　　private:</b></p><p>　　int _id; // 房間編號 - 自動分配</p><p>　

64、　string _name; // 教室名稱</p><p>　　bool _lab; // 表明房間有電腦</p><p>　　int _numberOfSeats; // 教室座位數(shù)目</p><p><b>　　public: </b></p><p>　　Room(cons

65、t string& name, bool lab, int numberOfSeats);</p><p>　　// 定義教室容量和教室ID</p><p>　　inline int GetId() const { return _id; } // 返回教室 ID</p><p>　　inline const string& GetName()

66、 const { return _name; }// 返回教室名稱</p><p>　　inline bool IsLab() const { return _lab; } // 若有實驗室返回TRUE，否則返回FALSE</p><p>　　inline int GetNumberOfSeats() const { return _numberOfSeats; }// 返回教室

67、的座位數(shù)</p><p>　　static inline void RestartIDs() { _nextRoomId = 0; }// 重置教室ID進行分配</p><p><b>　　};</b></p><p><b>　　5.3 定義教師類</b></p><p>　　class Pr

68、ofessor</p><p><b>　　{</b></p><p><b>　　private:</b></p><p>　　int _id; // 定義教授ID</p><p>　　string _name; // 名字</p><p>

69、;　　list<CourseClass*> _courseClasses; // 教授教的班列表</p><p><b>　　public:</b></p><p>　　Professor(int id, const string& name); // 初始化教授數(shù)據(jù)</p><p>　　void AddCourse

70、Class(CourseClass* courseClass); // 約束教授課程</p><p>　　inline int GetId() const { return _id; }// 返回教授的ID</p><p>　　inline const string& GetName() const { return _name; }// 返回教授名字</p>

71、;<p>　　inline const list<CourseClass*>& GetCourseClasses() const { return _courseClasses; }// 返回參考列出教授任教的班</p><p>　　inline bool operator ==(const Professor& rhs) const { return _

72、id == rhs._id; }// 比較兩個代表教授ID的對象</p><p><b>　　};</b></p><p><b>　　5.4 定義課程類</b></p><p>　　class Course</p><p><b>　　{</b>&

73、lt;/p><p><b>　　private:</b></p><p>　　int _id; // 課程ID</p><p>　　string _name; //課程名</p><p><b>　　public:</b></p><p>　　Co

74、urse(int id, const string& name); //初始化過程</p><p>　　inline int GetId() const { return _id; }// 返回課程ID</p><p>　　inline const string& GetName() const { return _name; }// 返回課程名</p&g

75、t;<p><b>　　};</b></p><p>　　5.5 設(shè)定配置文件</p><p><b>　　對象：</b></p><p>　　教師 (#prof tag) - 描述一位教授</p><p>　　課程 (#course tag) - 介紹課程</p>&l

76、t;p>　　教室 (#room tag) - 描述一間教室</p><p>　　學生班 (#group tag) - 描述一個班的全體學生</p><p>　　課程班 (#class tag) - 描述一個課程班，約束它的授課教師，課程和學生班</p><p>　　對于每個對象，其開始以其自己的標簽，結(jié)束以#end標記結(jié)束，每一個標簽必須是在單獨一行。在一個對

77、象內(nèi)，每一行只包含一個鍵和值對（屬性）被一個“=”字符分隔開。每個屬性應該指定一個時間，除了在#組對象中的組屬性可以有多個。標簽和鍵名能夠識別大小寫，這里是一個對象的屬性列表：</p><p><b>　　#prof</b></p><p>　　id (number, required) - 教授的ID</p><p>　　.name (str

78、ing, required) -教授名字</p><p><b>　　#course</b></p><p>　　id (number, required) - 課程ID</p><p>　　name (string, required) - 課程名</p><p><b>　　#room</b>&

79、lt;/p><p>　　name (string, required) -教室名稱</p><p>　　size (number, required) - 教室容納人數(shù)</p><p>　　lab (布爾變量, optional) - 表示，如果房間是一個實驗室（有電腦），如果沒有指定，默認值是false。</p><p><b>　　

80、#group</b></p><p>　　id (number, required) - 學生班ID</p><p>　　name (string, required) - 學生班名稱</p><p>　　size (number, required) - 學生班人數(shù)</p><p><b>　　#class</b

81、></p><p>　　professor (number, required) - 教授ID；為一個班限定一個教授</p><p>　　course (number, required) - 課程ID; 為一個班限定一個課程</p><p>　　group (number, required) - 學生班ID;約束學生班到一個課程班，每個課程班可以綁定多個學

82、生班</p><p>　　duration (number, optional) - 上課時間（小時），如果沒有指定，默認值是1。</p><p>　　lab (boolean, optional) - 是否這個課程班需要電腦;如果沒有指定，默認值是false。</p><p>　　下面給出各對象的變量列表</p><p>　　表5.1對象的

83、變量列表</p><p>　　要注意，教授，學生組，課程對象必須定義之前，它們屬于課程類對象。</p><p><b>　　配置文件舉例：</b></p><p><b>　　#prof</b></p><p><b>　　id = 1</b></p><p

84、>　　name = 張少強</p><p><b>　　#end</b></p><p><b>　　#prof</b></p><p><b>　　id = 2</b></p><p>　　name = 孫德兵</p><p><b>

85、　　#end</b></p><p><b>　　#course</b></p><p><b>　　id = 1</b></p><p>　　name = 高等數(shù)學</p><p><b>　　#end</b></p><p><b&

86、gt;　　#course</b></p><p><b>　　id = 2</b></p><p>　　name = 大學英語</p><p><b>　　#end</b></p><p><b>　　#course</b></p><p>

87、<b>　　id = 3</b></p><p>　　name = 信息導論</p><p><b>　　#end</b></p><p><b>　　#room</b></p><p>　　name = 勸學A303</p><p>　　lab = t

88、rue</p><p><b>　　size = 50</b></p><p><b>　　#end</b></p><p><b>　　#room</b></p><p>　　name = 勸學A213</p><p>　　lab = false<

89、;/p><p><b>　　size = 60</b></p><p><b>　　#end</b></p><p><b>　　#group</b></p><p><b>　　id = 1</b></p><p>　　name =

90、計算機10-1</p><p><b>　　size = 19</b></p><p><b>　　#end</b></p><p><b>　　#group</b></p><p><b>　　id = 2</b></p><p>

91、;　　name = 計算機10-2</p><p><b>　　size = 19</b></p><p><b>　　#end</b></p><p><b>　　#group</b></p><p><b>　　id = 3</b></p>

92、<p>　　name = 計算機10-3</p><p><b>　　size = 19</b></p><p><b>　　#end</b></p><p><b>　　#group</b></p><p><b>　　id = 4</b>

93、</p><p>　　name = 計算機10-4</p><p><b>　　size = 19</b></p><p><b>　　#end</b></p><p><b>　　#class</b></p><p>　　professor = 1&l

94、t;/p><p>　　course = 1</p><p>　　duration = 2</p><p><b>　　group = 1</b></p><p><b>　　group = 2</b></p><p><b>　　#end</b></p

95、><p><b>　　#class</b></p><p>　　professor = 1</p><p>　　course = 1</p><p>　　duration = 2</p><p><b>　　group = 3</b></p><p>&l

96、t;b>　　group = 4</b></p><p><b>　　#end</b></p><p><b>　　#class</b></p><p>　　professor = 9</p><p>　　course = 1</p><p>　　durati

97、on = 3</p><p><b>　　group = 1</b></p><p>　　lab = true</p><p><b>　　#end</b></p><p><b>　　#class</b></p><p>　　professor = 9

98、</p><p>　　course = 1</p><p>　　duration = 3</p><p><b>　　group = 2</b></p><p>　　lab = true</p><p><b>　　#end</b></p><p>&

99、lt;b>　　6 運行調(diào)試</b></p><p>　　如圖6.1所示，是輸入為17位教師，15門課程，六個班級，四間教室且容量分別為50，60各兩間，通過遺傳算法進行排課得出的最優(yōu)結(jié)果的課程表。通過遺傳算法進行優(yōu)勝劣汰的選擇到第2583代才得到最優(yōu)解。</p><p><b>　　圖6.1 運行結(jié)果</b></p><p>

100、<b>　　參考文獻：</b></p><p>　　[1]黃海．基于遺傳算法排課系統(tǒng)的設(shè)計與實現(xiàn)[J]．大眾科技，2005，09：17-20．</p><p>　　[2]徐克圣，張素芳．一種基于遺傳算法的自動排課系統(tǒng)設(shè)計[J]．計算機安全，2007，10：135-140．</p><p>　　[3]胡獻華．基于遺傳算法的自動排課問題的研究[D]

101、．杭州：浙江工業(yè)大學，2004．</p><p>　　[4]江齊，蘭競．遺傳算法在排課問題中的應用[J]．重慶大學學報（自然科學版），2005，11：79-85．</p><p>　　[5]陳本慶．遺傳算法研究及其在排課問題中的應用[D]．成都：西南交通大學，2003． </p><p>　　[6]梁飛鴻．基于遺傳算法的排課系統(tǒng)研究[J]．電腦與電信，2005，08

102、：104-110．</p><p>　　[7] 唐勇，唐雪飛，王玲．基于遺傳算法的排課系統(tǒng)[J]．計算機應用，2002，10：342-350．</p><p>　　[8]陸鋒，李新．自動排課系統(tǒng)算法的設(shè)計與實現(xiàn)[J]．微機發(fā)展，2005，11：127-134．</p><p>　　[9]范玉玲．遺傳算法在高校排課系統(tǒng)中應用的研究[D]．濟南：山東師范大學，2004．

103、</p><p>　　[10]趙光哲．基于遺傳算法的大學排課問題的研究[D]．吉林：延邊大學，2006．</p><p><b>　　致謝：</b></p><p>　　本人的學位論文是在我的指導教師xx老師的親切關(guān)懷和悉心指導下完成的。他嚴肅的科學態(tài)度，精益求精的工作作風，嚴謹?shù)闹螌W精神，深深地感染和激勵著我。從課題的選擇到設(shè)計和論文的最終完