1、<p>　　普通本科畢業(yè)論文(設(shè)計(jì))</p><p>　　題 目: 學(xué)分制模式下基于遺傳算法</p><p><b>　　的排課系統(tǒng)的設(shè)計(jì)</b></p><p><b>　　摘 要</b></p><p>　　排課問(wèn)題是一個(gè)多約束、多目標(biāo)的優(yōu)化問(wèn)題，其實(shí)質(zhì)是時(shí)間表問(wèn)題，已經(jīng)被

2、確認(rèn)為NP完全問(wèn)題。遺傳算法作為一種隨機(jī)搜索算法，利用群體搜索技術(shù)，對(duì)解決NP問(wèn)題非常有效。</p><p>　　本文將遺傳算法應(yīng)用于學(xué)分制模式下的排課系統(tǒng)中，通過(guò)對(duì)排課因素和約束條件的深入分析，制定了排課問(wèn)題的優(yōu)化目標(biāo)，設(shè)計(jì)出了適合于遺傳操作的編碼模型，給出了合理的適應(yīng)度值的計(jì)算方法。通過(guò)對(duì)初始種群進(jìn)行選擇、交叉、變異等過(guò)程不斷進(jìn)化，取得了優(yōu)化的課表。</p><p>　　在排課系統(tǒng)設(shè)計(jì)

3、中，本文采用了面向?qū)ο蟮姆椒?，設(shè)計(jì)了課表安排中的教室調(diào)度算法、基因填充算法、沖突檢測(cè)算法，使得排課得以實(shí)現(xiàn)。利用真實(shí)的數(shù)據(jù)進(jìn)行系統(tǒng)測(cè)試，并分析了各參數(shù)對(duì)遺傳操作及結(jié)果的影響。</p><p>　　【關(guān)鍵詞】學(xué)分制模式；排課系統(tǒng)；遺傳算法；多目標(biāo)優(yōu)化</p><p>　　Design of the Course Arrangement System Based on Genetic Algo

4、rithms in Credit Mode</p><p><b>　　Abstract：</b></p><p>　　The problem of course arrangement is an optimization problem with multi-constraints and multi-objective, which is actually a

5、timetable problem and has been proved to be a NP-completed problem. As a ramdom searching algorithm, the genetic algorithm(GA) using colony searching technology is very suitable for NP-completed problem.</p><p

6、>　　This thesis uses GA for the course arrangement system with credit mode. Therough analyzing deeply the factors and constraints of course arrangement, the optimization objectives of course arrangement are determined

7、first. Then the coding mode for genetic operations is designed and the computation method for reasonable fitness is given. An optimized course table is gotten through the operations of selection, recombination and mutati

8、on on the initial colony.</p><p>　　Based on the object-oriented method, this design makes use of classroom schedule algorithm, genetic fill algorithm and conflict detecting algorithm to arrange course. The e

9、xperiments are carried out using real data to analyse the influence of all parameters on the genetic operations and results.</p><p><b>　　Keywords：</b></p><p>　　Credit Mode; Course Ar

10、rangement System; Genetic Alogrithm; Multi-objective Optimization</p><p><b>　　目 錄</b></p><p><b>　　1 引言1</b></p><p><b>　　2 遺傳算法2</b></p&

11、gt;<p>　　2.1 遺傳算法研究的內(nèi)容3</p><p>　　2.2 遺傳算法的基本術(shù)語(yǔ)4</p><p>　　2.3 遺傳算法的基本思想5</p><p>　　2.4 遺傳算法的基本操作6</p><p>　　3 排課系統(tǒng)的需求分析8</p><p>　　3.1 排課系統(tǒng)的業(yè)

12、務(wù)流程分析8</p><p>　　3.2 排課因素分析10</p><p>　　3.3 排課的約束條件11</p><p>　　4 基于遺傳算法的排課算法的描述12</p><p>　　4.1 排課問(wèn)題的目標(biāo)分析12</p><p>　　4.2 排課系統(tǒng)中的基本算法15</p>&l

13、t;p>　　4.2.1 排課算法的面向?qū)ο蟮膽?yīng)用15</p><p>　　4.2.2 教室調(diào)度算法17</p><p>　　4.2.3 基因初始化算法18</p><p>　　4.2.4 沖突檢測(cè)算法19</p><p>　　4.3 排課問(wèn)題中遺傳算法的設(shè)計(jì)19</p><p>　　4.3.1

14、 遺傳算法的編碼19</p><p>　　4.3.2 初始種群的產(chǎn)生20</p><p>　　4.3.3 遺傳操作的設(shè)計(jì)20</p><p>　　4.3.4 適應(yīng)度函數(shù)的設(shè)計(jì)22</p><p>　　5 實(shí)驗(yàn)及結(jié)果分析22</p><p>　　5.1 排課系統(tǒng)開(kāi)發(fā)環(huán)境22</p>

15、<p>　　5.2 參數(shù)設(shè)置對(duì)排課效率的影響23</p><p>　　5.3 結(jié)果分析26</p><p>　　6 總結(jié)與展望27</p><p><b>　　參考文獻(xiàn)29</b></p><p><b>　　1 引言</b></p><p>　　排

16、課問(wèn)題是高校日常教學(xué)工作和其他各項(xiàng)活動(dòng)的基礎(chǔ)。課程表不僅是老師和學(xué)生上課的依據(jù)，也對(duì)學(xué)校的其他工作的安排有一定影響。利用計(jì)算機(jī)輔助排課，是教學(xué)管理實(shí)現(xiàn)科學(xué)化，現(xiàn)代化的重要課題之一。</p><p>　　目前高校招生逐年擴(kuò)張，學(xué)生人數(shù)不斷增加，再加上大多數(shù)高校實(shí)行學(xué)分制，課程開(kāi)設(shè)逐漸向著廣度和深度擴(kuò)展，但學(xué)校的教學(xué)資源及設(shè)備卻得不到及時(shí)補(bǔ)充，這些都給教務(wù)處排課人員造成很大的壓力。單純采用勞動(dòng)強(qiáng)度大、效率低的手工排課

17、，已成為提高教學(xué)管理質(zhì)量的瓶頸。隨著計(jì)算機(jī)在教學(xué)工作中的普及應(yīng)用，利用計(jì)算機(jī)進(jìn)行自動(dòng)排課已經(jīng)成為一個(gè)重要的研究課題。</p><p>　　排課問(wèn)題不僅是教學(xué)管理工作中必需面對(duì)的問(wèn)題，而且也是運(yùn)籌學(xué)中研究的一個(gè)問(wèn)題——時(shí)間表問(wèn)題 (TimeTable Problems，簡(jiǎn)記TTPS)。排課問(wèn)題的研究始于20世紀(jì)50年代末，但直到1963年，Gotlieb在他的文章中對(duì)排課問(wèn)題進(jìn)行了形式化描述并提出了排課問(wèn)題的數(shù)學(xué)模

18、型[1]，才標(biāo)志著排課問(wèn)題的研究進(jìn)入科學(xué)的殿堂。但由于在實(shí)踐中遇到的困難，人們對(duì)排課問(wèn)題的解是否存在產(chǎn)生了疑問(wèn)。1976年，S Even和Cooper等人證明了排課問(wèn)題是NP完全問(wèn)題[2,3]，這雖然回答了在排課實(shí)踐中遇到困難的原因，但同時(shí)宣布計(jì)算機(jī)解決排課問(wèn)題無(wú)法實(shí)現(xiàn)，因?yàn)橛?jì)算機(jī)難解性理論指出，現(xiàn)代計(jì)算機(jī)尚未找到解決NP完全問(wèn)題的多項(xiàng)式算法。</p><p>　　我國(guó)對(duì)排課問(wèn)題的研究始于20世紀(jì)80年代初期，所

19、用方法從模擬手工排課到運(yùn)用人工智能構(gòu)建專(zhuān)家系統(tǒng)或決策支持系統(tǒng)。吳金榮把排課問(wèn)題化成整數(shù)規(guī)劃來(lái)解決[4]，但計(jì)算量很大，而且僅僅適用于規(guī)模很小的排課問(wèn)題。何永太、胡順仁等人試圖用圖論中的染色問(wèn)題來(lái)求解排課問(wèn)題[5,6]，但染色問(wèn)題本身也是排課問(wèn)題?；趯?zhuān)家系統(tǒng)的求解算法將專(zhuān)家系統(tǒng)知識(shí)引入排課問(wèn)題的求解[7]，能有效組織排課過(guò)程中的知識(shí)。但由于實(shí)際排課問(wèn)題存在各種各樣的限制條件與特殊要求，至今沒(méi)有一個(gè)有效地普遍適用的排課算法。</p&

20、gt;<p>　　隨著現(xiàn)代智能優(yōu)化技術(shù)的出現(xiàn)和發(fā)展，模擬退火算法、禁忌搜索算法、蟻群算法、遺傳算法等被應(yīng)用到排課問(wèn)題中。模擬退火算法(Simulated Annealing)是Kirkpatrick等人于1983年首先提出的，它是人們從自然界固體退火過(guò)程中得到啟發(fā)并從中抽象出來(lái)的一種隨機(jī)優(yōu)化算法。模擬退火法用于求解優(yōu)化問(wèn)題的出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般優(yōu)化問(wèn)題間的相似性。在對(duì)固體物質(zhì)進(jìn)行退火處理時(shí)，常先將它加

21、溫使其粒子可自由運(yùn)動(dòng)，以后隨著溫度的逐漸下降，粒子逐漸形成低能態(tài)晶格。若在凝結(jié)點(diǎn)附近的溫度下降速率足夠慢，則固體物質(zhì)一定會(huì)形成最低能量的基態(tài)。優(yōu)化問(wèn)題也存在類(lèi)似過(guò)程。模擬退火法被用來(lái)解決許多實(shí)際應(yīng)用中的優(yōu)化問(wèn)題，取得了不錯(cuò)的效果，用其解決排課問(wèn)題[8]，現(xiàn)在還處在模型實(shí)驗(yàn)階段，還有許多問(wèn)題要解決。禁忌搜索的思想最早由Glover于1986年提出，它是對(duì)局部領(lǐng)域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，是對(duì)人類(lèi)智力過(guò)程的一種模擬。禁忌搜索算

22、法通過(guò)引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來(lái)避免迂回搜索，并通過(guò)藐視準(zhǔn)則來(lái)赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索以最終實(shí)現(xiàn)全局優(yōu)化。文獻(xiàn)[</p><p>　　上述算法都是一定程度上的啟發(fā)搜索算法，但是搜索過(guò)程的啟發(fā)信息依賴(lài)于實(shí)際情況，排課問(wèn)題求解只能針對(duì)個(gè)別的實(shí)際問(wèn)題，且沒(méi)有引入目標(biāo)優(yōu)化技術(shù)，更不用說(shuō)人性化方面的考慮。正是因?yàn)槿绱?，具有智能性、并行性和高魯棒性的遺傳算法迅速應(yīng)用于排課問(wèn)題，并得到了

23、很快的發(fā)展。</p><p>　　本文正是在上述背景下展開(kāi)的，在分析和實(shí)踐的過(guò)程中，針對(duì)江西財(cái)經(jīng)大學(xué)排課問(wèn)題的具體情況，結(jié)合排課問(wèn)題中常見(jiàn)的約束及優(yōu)化目標(biāo)，采用了一種適應(yīng)于排課問(wèn)題的編碼方法，并將遺傳算法應(yīng)用到課表的優(yōu)化，以此獲得最終的排課方案。</p><p><b>　　2 遺傳算法</b></p><p>　　遺傳算法(Genetic

24、Algorithm, GA)是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它出現(xiàn)在20世紀(jì)60年代，最早是由美國(guó)密執(zhí)安大學(xué)的John Holland教授與其同事、學(xué)生研究形成的一個(gè)比較完整的理論和方法，在一系列研究工作的基礎(chǔ)上，80年代由Goldberge進(jìn)行歸納總結(jié)，形成了遺傳算法的基本框架。經(jīng)過(guò)20余年的發(fā)展，計(jì)算機(jī)智能已經(jīng)成為人工智能研究的一個(gè)重要方向，以及后來(lái)人工生命研究的興起，使遺傳算法受到廣泛

25、關(guān)注。從1985年在美國(guó)卡內(nèi)基梅隆大學(xué)召開(kāi)的第一屆國(guó)際遺傳會(huì)議(International Conference on Genetic Algorithms：ICGAs，85)，到1997年5月，IEEE的Transaction on Evolutionaly Computation創(chuàng)刊，遺傳算法作為系統(tǒng)優(yōu)化、自適應(yīng)和學(xué)習(xí)的高性能計(jì)算和建模方法的研究日趨成熟[3]。</p><p>　　遺傳算法是一種借鑒生物界自

26、然選擇和進(jìn)化機(jī)制發(fā)展起來(lái)的高度并行、隨機(jī)、自適應(yīng)的搜索算法。其主要特點(diǎn)是群體搜索策略和種群中個(gè)體之間的信息交換。由于其具有健壯性，特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜的和非線性問(wèn)題。簡(jiǎn)單的講，它使用了群體搜索技術(shù)，從而產(chǎn)生新一代的種群，并逐步使種群進(jìn)化到近似最優(yōu)解的狀態(tài)。遺傳算法是多學(xué)科結(jié)合與滲透的產(chǎn)物，從產(chǎn)生至今已廣泛地運(yùn)用于包括工程設(shè)計(jì)、制造業(yè)、人工智能、計(jì)算機(jī)科學(xué)、生物工程、石油勘探、自動(dòng)控制、社會(huì)科學(xué)、商業(yè)和金融等各個(gè)領(lǐng)域。

27、</p><p>　　2.1 遺傳算法研究的內(nèi)容</p><p>　　遺傳算法的研究主要集中在編碼方法、適應(yīng)函數(shù)、遺傳算子、遺傳算法參數(shù)選擇、全局收斂性和搜索效率的數(shù)學(xué)基礎(chǔ)、欺騙問(wèn)題、收斂性分析、局部收斂及混合遺傳算法等[8]。本文在將遺傳算法應(yīng)用到排課問(wèn)題中時(shí)，對(duì)遺傳算法的編碼、適應(yīng)函數(shù)的設(shè)計(jì)、遺傳算子、遺傳算法參數(shù)的選擇等進(jìn)行了分析[11]。</p><p>

28、<b>　　(1) 編碼方法</b></p><p>　　遺傳算法的編碼在許多問(wèn)題的求解中，對(duì)算法的性能有很重要的影響。簡(jiǎn)單二進(jìn)制編碼的采用得到了Holland早期理論結(jié)果（Schema定理、最小字母表原理）的支持，但仍有很多不足之處?；疑幋a可用于克服二進(jìn)制編碼映射的不連續(xù)問(wèn)題。動(dòng)態(tài)參數(shù)編碼的提出是為了克服搜索效率與表示精度間的矛盾，同時(shí)對(duì)克服過(guò)早收斂現(xiàn)象也有所幫助。此外，多值編碼、實(shí)值編

29、碼、區(qū)間值編碼、Delta編碼、對(duì)稱(chēng)編碼以及將以往的合成編碼分解成多個(gè)相對(duì)獨(dú)立編碼的獨(dú)立編碼策略等多種編碼方法也都被證明各有優(yōu)缺點(diǎn)。這些編碼方法的提出是啟發(fā)式的，缺乏一個(gè)理論基礎(chǔ)來(lái)判斷各種編碼方法的好壞并指導(dǎo)它們的設(shè)計(jì)。為解決二進(jìn)制編碼帶來(lái)的“組合爆炸” 和遺傳算法的早熟收斂問(wèn)題，提出了十進(jìn)制編碼。根據(jù)Holland教授提出的編碼應(yīng)該有利于交叉變異操作的編碼原則[4]，本文設(shè)計(jì)了適用于排課問(wèn)題的編碼模型。</p><

30、p>　　(2) 適應(yīng)函數(shù)的設(shè)計(jì)</p><p>　　在遺傳算法中，適應(yīng)度值是用來(lái)區(qū)分群體中個(gè)體好壞的標(biāo)志。遺傳算法正是根據(jù)適應(yīng)值對(duì)個(gè)體進(jìn)行選擇的。在實(shí)際操作中，適應(yīng)函數(shù)的設(shè)計(jì)對(duì)算法的收斂性及收斂速度的影響較大。本文根據(jù)排課問(wèn)題的求解目標(biāo)，并考慮系統(tǒng)與排課者的交互，設(shè)計(jì)了合理的適應(yīng)度函數(shù)。</p><p><b>　　(3) 遺傳算子</b></p>

31、<p>　　遺傳算法的三個(gè)算子分別是選擇、交叉和變異。選擇體現(xiàn)“適者生存”的原理，通過(guò)適應(yīng)值選擇優(yōu)質(zhì)個(gè)體而拋棄劣質(zhì)個(gè)體。雜交能使個(gè)體之間的遺傳物質(zhì)進(jìn)行交換從而產(chǎn)生更好的個(gè)體。變異能恢復(fù)個(gè)體失去的或未開(kāi)發(fā)的遺傳物質(zhì)，以防止個(gè)體在形成最優(yōu)解過(guò)程中過(guò)早收斂。</p><p>　　① 選擇策略是遺傳算法中的很重要的一個(gè)環(huán)節(jié)。由于其對(duì)遺傳搜索過(guò)程具有較大的影響，很多人早就意識(shí)到它在遺傳算法中的重要性。所以近年來(lái)

32、，不同的遺傳策略相繼被提出。Potts等人概括了23種選擇策略。Goldberg首先引入了選擇算子的收斂模型，隨后，他和Deb又作了擴(kuò)展，并提出取代時(shí)間概念，可以對(duì)各種選擇策略之間選擇壓力進(jìn)行定量分析。Muhlenbein和Schlierkamp-Vossen討論了選擇強(qiáng)度在收斂分析中的應(yīng)用。Back對(duì)選擇壓力進(jìn)行推廣。后來(lái)為解決模式里有太大的變動(dòng)或遺傳算法欺騙問(wèn)題，有人提出了具有破壞性選擇的遺傳算法。</p><p

33、>　　② 交叉操作使不同個(gè)體間的基因相互交換。Potts概括了17種交叉方法。吳少巖等研究了交叉算子與其探索子空間之間的關(guān)系，并提出了設(shè)計(jì)良好算子的指導(dǎo)性原則，并構(gòu)造出一種啟發(fā)式交配算子。</p><p>　?、?變異是一種防止早熟的操作。Potts總結(jié)的變異技術(shù)有管理變異，變化的變異概率和單值運(yùn)算。</p><p>　　本文根據(jù)這些相關(guān)算子設(shè)計(jì)原則，設(shè)計(jì)了有利于排課操作的遺傳算子。

34、</p><p><b>　　(4) 參數(shù)的選擇</b></p><p>　　遺傳算法的群體規(guī)模、收斂判據(jù)、交叉概率和變異概率都對(duì)排課算法的效率有很大影響，但這些參數(shù)的設(shè)置還缺少相應(yīng)的理論指導(dǎo)。由于參數(shù)選擇關(guān)系到算法的精度、可靠性和計(jì)算時(shí)間等諸因素，并影響到結(jié)果的質(zhì)量和系統(tǒng)性能，因此參數(shù)選擇的研究受到重視。本文各參數(shù)的設(shè)置主要是建立在實(shí)驗(yàn)的基礎(chǔ)上。</p>

35、<p>　　2.2 遺傳算法的基本術(shù)語(yǔ)</p><p>　　既然遺傳算法效法于自然選擇的生物進(jìn)化，是一種模仿生物進(jìn)化過(guò)程的隨機(jī)算法，那么我們先分析幾個(gè)生物學(xué)的基本概念與術(shù)語(yǔ)，這對(duì)理解和運(yùn)用遺傳算法是非常重要的[13]。</p><p>　　(1) 染色體(chromosome)</p><p>　　生物細(xì)胞中含有的一種微小的絲狀化合物。它是遺傳物質(zhì)的

36、主要載體，由多個(gè)遺傳因子——基因組成。遺傳因子(Gene) DNA或RNA長(zhǎng)鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位，也稱(chēng)為基因。生物的基因數(shù)量根據(jù)物種的不同多少不一，小的病毒只含有幾個(gè)基因，而高等動(dòng)植物的基因卻數(shù)以萬(wàn)計(jì)。</p><p>　　(2) 個(gè)體(individual)</p><p>　　指染色體帶有特征的實(shí)體，在問(wèn)題簡(jiǎn)化的情況下可用染色體代替。</p><p&g

37、t;　　(3) 種群(population)</p><p>　　染色體帶有特征的個(gè)體的集合稱(chēng)為種群。該集合內(nèi)個(gè)體數(shù)稱(chēng)為群體的大小或種群的規(guī)模。有時(shí)個(gè)體的集合也稱(chēng)為個(gè)體群。</p><p>　　(4) 進(jìn)化(evolution)</p><p>　　生物在其延續(xù)生存的過(guò)程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱(chēng)為進(jìn)化。生物的進(jìn)化是以種群的形式進(jìn)

38、行的。</p><p>　　(5) 適應(yīng)度(fitness)</p><p>　　在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時(shí)，生物學(xué)家使用適應(yīng)度這個(gè)術(shù)語(yǔ)來(lái)度量某個(gè)物種對(duì)于生存環(huán)境的適應(yīng)程度。對(duì)生存環(huán)境適應(yīng)度高的物種將獲得更多的繁殖機(jī)會(huì)，而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖的機(jī)會(huì)就會(huì)相對(duì)較少，甚至逐漸滅絕。</p><p>　　(6) 選擇(selection)</

39、p><p>　　指決定以一定的概率從種群中選擇若干個(gè)體的操作。一般而言，選擇的過(guò)程是一種基于適應(yīng)度的優(yōu)勝劣汰的過(guò)程。正如達(dá)爾文描述的，適者生存。</p><p>　　(7) 復(fù)制(reproduction)</p><p>　　細(xì)胞在分裂時(shí)，遺傳物質(zhì)DNA通過(guò)復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新的細(xì)胞就繼承了舊細(xì)胞的基因。</p><p>　　(8)

40、交叉(crossover)</p><p>　　有性生殖生物在繁殖下一代時(shí)兩個(gè)同源染色體之間通過(guò)交叉而重組，即在兩個(gè)染色體的某一相同位置處被切斷，其前后兩串分別交叉組合形成兩個(gè)新的染色體。這個(gè)過(guò)程又稱(chēng)為基因重組(recombination)，俗稱(chēng)“雜交”。</p><p>　　(9) 變異(mutation)</p><p>　　在細(xì)胞進(jìn)行復(fù)制時(shí)可能以很小的概率產(chǎn)生

41、某些復(fù)制差錯(cuò)，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀。</p><p>　　(10) 編碼(coding)</p><p>　　DNA中遺傳信息在一個(gè)長(zhǎng)鏈上按一定的模式排列，即進(jìn)行了遺傳編碼。遺傳編碼可以看作從表現(xiàn)型到遺傳子型的映射。</p><p>　　(11) 解碼(decodi ng)</p><p>

42、　　編碼的逆過(guò)程，即從遺傳子型到表現(xiàn)型的映射。</p><p>　　2.3 遺傳算法的基本思想</p><p>　　通過(guò)以上分析，我們可以更好的描述遺傳算法。遺傳算法是從代表問(wèn)題可能潛在解集的一個(gè)種群(population)開(kāi)始的，而一個(gè)種群則由經(jīng)過(guò)基因(Gene)編碼(coding)的一定數(shù)目的個(gè)體(individual)（或染色體）組成。每個(gè)個(gè)體實(shí)際上是染色體(chromosome)

43、帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（基因型）是某種基因組合決定的。初始種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代(generation)演化產(chǎn)生出越來(lái)越好的近似解。在每一代中，根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度(fitness)大小挑選(selection)個(gè)體，并借助于自然遺傳學(xué)的遺傳算子(geneticoperators)進(jìn)行組合交叉(crossover)和變異(mutation)，產(chǎn)生出代表新的

44、解集的種群。這個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣，后代種群比前代更加適應(yīng)環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼(decoding)可以作為問(wèn)題近似最優(yōu)解。遺傳算法采納了自然進(jìn)化模型，如選擇、交叉、變異、遷移、局域與臨域等。計(jì)算開(kāi)始時(shí)，隨機(jī)地初始化一定數(shù)目的個(gè)體(父?jìng)€(gè)體1、父?jìng)€(gè)體2、父?jìng)€(gè)體3、父</p><p>　　2.4 遺傳算法的基本操作</p><p>　　遺傳算法包括三個(gè)基本操作：選擇、交

45、叉和變異。這些基本操作又有許多不同的方法。</p><p>　　(1) 選擇(selection)</p><p>　　遺傳算法中的選擇操作就是用來(lái)確定如何從父代群體中按某種方法選取哪些個(gè)體遺傳到下一代群體中的一種遺傳運(yùn)算[3]。</p><p>　?、?選擇是用來(lái)確定重組或交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少子代個(gè)體。首先計(jì)算個(gè)體適應(yīng)度，具體有以下算法：</p&

46、gt;<p>　　(a) 按比例的適應(yīng)度計(jì)算(proportional fitness assignment)</p><p>　　(b) 基于排序的適應(yīng)度計(jì)算(rank-based fitness assignment)</p><p>　?、?適應(yīng)度計(jì)算之后是實(shí)際的選擇，按照適應(yīng)度進(jìn)行父代個(gè)體的選擇。選擇算法有：</p><p>　　(a) 輪盤(pán)賭

47、選擇(roulette wheel selection) </p><p>　　(b) 隨機(jī)遍歷抽樣(stochastic universal sampling) </p><p>　　(c) 局部選擇(local selection)</p><p>　　(d) 截?cái)噙x擇(truncation selection)</p><p>　　(e

48、) 錦標(biāo)賽選擇(tournament selection)</p><p>　　(2) 交叉或重組基因(crossover/recombination)</p><p>　　遺傳算法中的所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起著關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法[3]。<

49、/p><p>　　基因重組是結(jié)合來(lái)自父代交配種群中的信息產(chǎn)生新的個(gè)體。依據(jù)個(gè)體編碼表示方法的不同，可以有以下的算法：</p><p>　　① 實(shí)值重組(real valued recombination)</p><p>　　(a) 離散重組(discrete recombination)</p><p>　　(b) 中間重組(intermedi

50、ate recombination)</p><p>　?、?二進(jìn)制交叉(binary valued crossover)</p><p>　　(a) 單點(diǎn)交叉(single-point crossover)</p><p>　　(b) 多點(diǎn)交叉(multiple-point crossover)</p><p>　　(c) 均勻交叉(uni

51、form crossover)</p><p>　　(d) 洗牌交叉(shuffle crossover)</p><p>　　(e) 縮小代理交叉(crossover with reduced surrogate)</p><p>　　(3) 變異(mutation)</p><p>　　遺傳算法中的所謂變異運(yùn)算，是指將個(gè)體染色體編碼串中的

52、某些基因座上的基因值用該基因座的其他等位基因來(lái)替換，從而形成一個(gè)新的個(gè)體[3]。</p><p>　　交叉之后子代經(jīng)歷的變異，實(shí)際上是子代基因按小概率擾動(dòng)產(chǎn)生的變化。依據(jù)個(gè)體編碼表示方法的不同，可以有以下的算法：</p><p><b>　　① 實(shí)值變異</b></p><p><b>　?、?二進(jìn)制變異</b></

53、p><p>　　3 排課系統(tǒng)的需求分析</p><p>　　排課系統(tǒng)的設(shè)計(jì)必需建立在對(duì)排課流程的詳細(xì)分析的基礎(chǔ)之上。由于各學(xué)校自身情況、采用的教學(xué)模式(學(xué)分制或?qū)W年制)的不同，導(dǎo)致各學(xué)校排課流程存在差異，本文以江西財(cái)經(jīng)大學(xué)為分析對(duì)象，設(shè)計(jì)出適合學(xué)分制模式下的高校排課算法[14,15]。</p><p>　　3.1 排課系統(tǒng)的業(yè)務(wù)流程分析</p><

54、;p><b>　　(1) 主要流程</b></p><p>　　江西財(cái)經(jīng)大學(xué)排課工作的基本流程如圖3-1所示：</p><p>　　(2) 教務(wù)處工作流程</p><p>　　教務(wù)處根據(jù)各年級(jí)、各專(zhuān)業(yè)的培養(yǎng)方案，學(xué)生人數(shù)結(jié)合考慮課程性質(zhì)向各個(gè)學(xué)院下達(dá)教學(xué)任務(wù)書(shū)，明確這學(xué)期的教學(xué)要求。教學(xué)任務(wù)書(shū)中要明確所要開(kāi)設(shè)的課程、應(yīng)開(kāi)設(shè)班級(jí)數(shù)目(班別)

55、、課程開(kāi)設(shè)的校區(qū)等信息。其中，某課程應(yīng)開(kāi)設(shè)的班級(jí)數(shù)，是由要選修該課程的學(xué)生總數(shù)及該課程的參考容量決定的，各學(xué)院可以根據(jù)自身情況對(duì)其進(jìn)行調(diào)整。教務(wù)處工作流程如圖3-2 所示。</p><p>　　(3) 學(xué)院工作流程</p><p>　　教學(xué)任務(wù)書(shū)下達(dá)到各學(xué)院后，各學(xué)院根據(jù)自身教師情況，可以適當(dāng)調(diào)整教學(xué)任務(wù)書(shū)中某課程的開(kāi)課班級(jí)數(shù)及班級(jí)容量。然后，在教學(xué)任務(wù)書(shū)中為每門(mén)課程的每個(gè)班添加老師，以及

56、該課程對(duì)教室的要求，這樣形成的信息稱(chēng)之為課元信息。同時(shí)學(xué)院的老師可以向教務(wù)處提交特殊時(shí)間要求，如星期三下午，信息學(xué)院領(lǐng)導(dǎo)因工作會(huì)議，不能安排上課。學(xué)院工作流程如圖3-3 所示。</p><p><b>　　(4) 排課流程</b></p><p>　　各學(xué)院把課元信息提交給教務(wù)處，教務(wù)處根據(jù)全校教師情況，教室資源情況，老師的特殊要求利用排課系統(tǒng)排出預(yù)排課表，學(xué)生根據(jù)預(yù)

57、排課表選課，教務(wù)處在學(xué)生選課后，根據(jù)各個(gè)選課班的人數(shù)，撤銷(xiāo)人數(shù)小于15人（特殊課程除外）的選課班。課程表包括全?？傉n程表、學(xué)生課程表、教師課程表和教室課程表。課程表由教務(wù)處編制，不得隨意變動(dòng)。如因特殊情況調(diào)整，須按學(xué)校有關(guān)規(guī)定辦理手續(xù)，并由教務(wù)處下達(dá)調(diào)課通知。執(zhí)行流程如圖3-4所示。</p><p>　　(5) 江西財(cái)經(jīng)大學(xué)排課總流程</p><p>　　江西財(cái)經(jīng)大學(xué)每屆新生入學(xué)前，各學(xué)院

58、各專(zhuān)業(yè)已經(jīng)為新生制定了在校四年的培養(yǎng)方案，作為在校期間學(xué)生選課的依據(jù)。其中不僅列出了學(xué)生完成學(xué)業(yè)所必需選修的公共基礎(chǔ)課、專(zhuān)業(yè)課，還列出了有利于學(xué)習(xí)專(zhuān)業(yè)知識(shí)、擴(kuò)大知識(shí)面的推薦選修課，以及這些課程在哪個(gè)學(xué)期開(kāi)設(shè)。并注明了所列出的每門(mén)課程的學(xué)分，及每個(gè)學(xué)生畢業(yè)時(shí)所要修完的總學(xué)分。排課工作開(kāi)始后，教務(wù)處根據(jù)各年級(jí)各專(zhuān)業(yè)培養(yǎng)方案、各年級(jí)各專(zhuān)業(yè)學(xué)生人數(shù)、課程性質(zhì)，生成教學(xué)任務(wù)書(shū)，其包括要開(kāi)設(shè)的課程名稱(chēng)、該課程要開(kāi)設(shè)的班級(jí)數(shù)(班別)、校區(qū)等信息。教學(xué)

59、任務(wù)書(shū)下達(dá)到各學(xué)院后，學(xué)院根據(jù)自身教師情況，修改某些課程的班級(jí)數(shù)目及相應(yīng)的班級(jí)容量，之后為教學(xué)任務(wù)書(shū)添加老師，并提出課程對(duì)教室的要求，及學(xué)院老師對(duì)上課時(shí)間的要求(如某個(gè)時(shí)間段不能安排課程)，這樣就形成了課元信息。學(xué)院再將課元信息提交教務(wù)處，教務(wù)處根據(jù)教師情況，教室資源情況，老師的特殊要求利用排課系統(tǒng)排出預(yù)排課表，學(xué)生根據(jù)預(yù)排課表選課，教務(wù)處在學(xué)生選課后，根據(jù)各個(gè)選課班的人數(shù)，撤銷(xiāo)人數(shù)小于15的選課班。教務(wù)處可以根據(jù)具體情況調(diào)整課程表，并

60、下達(dá)調(diào)課通知。執(zhí)行流程如圖3-5所示。</p><p>　　3.2 排課因素分析</p><p>　　排課工作是教學(xué)工作順利進(jìn)行的基礎(chǔ)工作，排課問(wèn)題涉及到的因素也幾乎是全校性的。從排課可能引起的沖突的角度來(lái)考慮，排課涉及到的因素如下： </p><p><b>　　(1) 時(shí)間因素</b></p><p>　　在排課問(wèn)

61、題中涉及到的時(shí)間因素主要有學(xué)年、學(xué)期、周、天、時(shí)段、節(jié)次等。一般我們按照周課表來(lái)上課，從開(kāi)學(xué)第一周到第N周，江西財(cái)經(jīng)大學(xué)每上學(xué)上課16周。一周上課天數(shù)M≤7，一般學(xué)校一周上課5天(二專(zhuān)周六、日上課，本文不作考慮)。每天上午分兩個(gè)時(shí)間段(片)，每個(gè)時(shí)間段兩節(jié)課，下午和晚上各一個(gè)時(shí)間段，每個(gè)時(shí)間段三節(jié)課。這樣一周有20個(gè)時(shí)間段。</p><p><b>　　(2) 課程因素</b></p&

62、gt;<p>　　課程有課程編號(hào)、課程名稱(chēng)、課程的周學(xué)時(shí)、課程學(xué)分、課程對(duì)教室類(lèi)型的要求、所屬學(xué)院等。每門(mén)課程可以有指定的老師授課，也可以沒(méi)有。課程因素還包括開(kāi)設(shè)的班級(jí)數(shù)及課程開(kāi)設(shè)的校區(qū)等。</p><p><b>　　(3) 教室因素</b></p><p>　　每個(gè)教室都有教室編號(hào)，教室代號(hào)及所屬的教學(xué)區(qū)域。每個(gè)教室都有教室類(lèi)型，教室類(lèi)型包括普通教室

63、、多媒體教室、語(yǔ)音教室、實(shí)驗(yàn)室、機(jī)房、體育館等。每個(gè)教室都有一定的容量，教室的容量必須不小于上課的人數(shù)。</p><p><b>　　(4) 教師因素</b></p><p>　　每個(gè)教師都有自己的編號(hào)及姓名，每個(gè)教師都隸屬于一個(gè)學(xué)院，教師可以對(duì)上課時(shí)間提出自己的特殊要求。同一時(shí)間老師只能上一個(gè)教學(xué)班的課。</p><p><b>　

64、　(5) 班級(jí)因素</b></p><p>　　本文所涉及的班級(jí)均指的是教學(xué)班（選課班或行政班）。如前面的分析，教務(wù)處下達(dá)的教學(xué)任務(wù)書(shū)里規(guī)定了開(kāi)設(shè)的課程名稱(chēng)、班別、開(kāi)設(shè)的校區(qū)等。其中課程名稱(chēng)，班別，校區(qū)編號(hào)唯一決定一個(gè)選課班。每個(gè)選課班都有一個(gè)的最大選課人數(shù)的限制。</p><p><b>　　(6) 校區(qū)因素</b></p><p&g

65、t;　　每個(gè)校區(qū)都有編號(hào)和名稱(chēng)。其中蛟橋園編號(hào)為“A”，麥廬園為“B”，楓林園為“C”。當(dāng)老師、學(xué)生在不同校區(qū)上課時(shí)，應(yīng)該留有一定的時(shí)間用于趕赴。根據(jù)江西財(cái)經(jīng)大學(xué)課間時(shí)間的安排，上午兩個(gè)時(shí)間段之間留有40分鐘的時(shí)間，上午跟下午，下午跟晚上的上課時(shí)間間隔在90-120分鐘之間，所以趕赴的時(shí)間本文不予考慮。</p><p>　　3.3 排課的約束條件</p><p>　　排課問(wèn)題中，主要任務(wù)

66、是將班級(jí)、教師、課程安排在一周內(nèi)某一不發(fā)生沖突的時(shí)間和教室，保證課表在時(shí)間的分配上符合一切共性(時(shí)間上不存在沖突)和個(gè)性(不與老師的特殊時(shí)間要求沖突)的要求，在此基礎(chǔ)上，使其安排在各個(gè)目標(biāo)上盡量達(dá)到最優(yōu)。</p><p>　　一張可行的課表首先要滿足排課因素的約束。這里的約束條件主要是避免沖突。只有在滿足全部約束條件和避免所有沖突的基礎(chǔ)上，才能保證整個(gè)教學(xué)計(jì)劃合理正常進(jìn)行。對(duì)教師、班級(jí)、課程、時(shí)間、教室等幾部分資

67、源進(jìn)行最優(yōu)化配置，才能保證排課的順利完成以及充分發(fā)揮各個(gè)資源的優(yōu)勢(shì)以達(dá)到提高管理水平和教學(xué)質(zhì)量的目的。</p><p>　　根據(jù)是否必須滿足，我們可以將約束條件分為硬約束和軟約束。硬約束是指教師、班級(jí)、教室、校區(qū)在時(shí)空概念上發(fā)生了不可能發(fā)生的事情，也就是發(fā)生了沖突。它是在排課過(guò)程中需要滿足的最基本的約束條件，是排課時(shí)必須遵循的原則，否則將會(huì)導(dǎo)致排課結(jié)果無(wú)意義。軟約束則是指排課過(guò)程中若滿足則更佳，不能滿足也不影響教

68、學(xué)的開(kāi)展的約束條件。它能夠使課表更加合理，更加具有人性化[16]，它影響排課結(jié)果的好壞。</p><p>　　通常，排課方案的標(biāo)準(zhǔn)有多個(gè)，以下是按照江西財(cái)經(jīng)大學(xué)的校情制定的約束條件。</p><p>　　(1) 硬性約束條件</p><p>　?、?同一時(shí)間同一班級(jí)只能上一門(mén)課；</p><p>　?、?同一時(shí)間同一教室只能上一門(mén)課；<

69、/p><p>　　③ 同一時(shí)間同一教師只能上一門(mén)課；</p><p>　?、?教室的容量必須不小于或等于實(shí)際上課的人數(shù)；</p><p>　?、?所分配的教室類(lèi)型必須與課程所要求的教室類(lèi)型一致；</p><p>　?、?課程必須安排在教學(xué)任務(wù)書(shū)所規(guī)定的校區(qū)。</p><p>　　(2) 軟性約束條件</p>

70、<p>　?、?每個(gè)時(shí)間段安排的課程數(shù)盡量均勻；</p><p>　?、?一周的課表中每個(gè)上課時(shí)間都有一定的優(yōu)度，盡量將課程安排在優(yōu)度高的時(shí)間段；</p><p>　?、?一門(mén)課程的多次上課的時(shí)間盡量間隔并分布均勻；</p><p>　?、?教室容量適中，以充分利用教室；</p><p>　?、?兩個(gè)課時(shí)的課程盡量不要安排在下午或晚

71、上，以免造成一個(gè)課時(shí)的浪費(fèi)。</p><p>　　4 基于遺傳算法的排課算法的描述</p><p>　　本文前面已經(jīng)對(duì)遺傳算法、排課流程、排課因素及排課的約束條件進(jìn)行了分析，下面結(jié)合上述分析將遺傳算法具體應(yīng)用到排課算法的設(shè)計(jì)過(guò)程中。</p><p>　　4.1 排課問(wèn)題的目標(biāo)分析</p><p>　　根據(jù)江西財(cái)經(jīng)大學(xué)的校情，本文確定了五個(gè)

72、目標(biāo)，分別為：教室利用度、節(jié)次優(yōu)度、課程日組合優(yōu)度、時(shí)間片利用度、課程的時(shí)段分布均勻度。下面分別介紹這五個(gè)目標(biāo)[17]。</p><p><b>　　(1) 教室利用度</b></p><p>　　教室利用度，是衡量所開(kāi)設(shè)的課次的教室利用程度的好壞標(biāo)志。其計(jì)算方法如下：</p><p><b>　　(4.1)</b><

73、;/p><p>　　式中 ——所有課次的教室利用率的平均值</p><p>　　——第i個(gè)課次的教室利用率</p><p><b>　　——課次總數(shù)</b></p><p>　　值越大，我們認(rèn)為排課方案的教室利用率越高。</p><p><b>　　(2) 節(jié)次優(yōu)度</b>&l

74、t;/p><p>　　節(jié)次優(yōu)度是對(duì)某一時(shí)間片上課效果好壞的量化。我們?yōu)槊恳粋€(gè)時(shí)間片賦予不同的優(yōu)度值以表示對(duì)這個(gè)時(shí)間片的偏好程度。節(jié)次優(yōu)度含有一定的主觀因素，每個(gè)人對(duì)同一時(shí)間片的偏好不同，不同的季節(jié)同一個(gè)時(shí)間片的上課效果也會(huì)有差別。我們可以讓排課人員來(lái)設(shè)置每個(gè)時(shí)間片的節(jié)次優(yōu)度，以體現(xiàn)不同人，不同學(xué)期的要求。如學(xué)年的第一個(gè)學(xué)期進(jìn)入到冬季時(shí)，上午1、2節(jié)比3、4節(jié)的節(jié)次優(yōu)度可能低些，因?yàn)樘炖洳糠滞瑢W(xué)不愿早起上課。第二學(xué)期進(jìn)

75、入到夏季時(shí)，下午的時(shí)間片的節(jié)次優(yōu)度要低些，因?yàn)榇藭r(shí)上課，效果會(huì)差些。本系統(tǒng)采用的節(jié)次優(yōu)度值如表3-1所示。</p><p>　　表4-1 節(jié)次優(yōu)度表</p><p>　　我們用全校課程的節(jié)次優(yōu)度的平均值來(lái)衡量排課方案中節(jié)次安排的好壞，即對(duì)開(kāi)課方案中每個(gè)課次的節(jié)次優(yōu)度進(jìn)行累加，再除以總的課次數(shù)。</p><p><b>　　(4-2)</b>&l

76、t;/p><p>　　式中 ——全校課程的節(jié)次優(yōu)度的平均值</p><p>　　——第i個(gè)課程的第j個(gè)時(shí)間段的節(jié)次優(yōu)度</p><p>　　——第i個(gè)課程的時(shí)間段的個(gè)數(shù)</p><p>　　——所開(kāi)設(shè)的課程的總數(shù)</p><p>　　的值越大，我們認(rèn)為排課方案的節(jié)次優(yōu)度越好。</p><p>　　

77、(3) 課程日組合優(yōu)度</p><p>　　課程的日組合優(yōu)度，是衡量每周上課次數(shù)大于1的課程的多次上課的日組合優(yōu)度好壞的標(biāo)志。我們對(duì)所有的課程的日組合優(yōu)度進(jìn)行優(yōu)度判定。例如：一個(gè)周學(xué)時(shí)為6的課程，每周上課3次，每次兩個(gè)課時(shí)，如果這三個(gè)時(shí)間片分別為周一的1、2節(jié)、周三的3、4節(jié)、周五的1、2節(jié)或者周一的3、4節(jié)、周三的1、2節(jié)、周五的3、4節(jié)，則我們認(rèn)為該課程的日組合優(yōu)度為1。如果一門(mén)周學(xué)時(shí)為4的課程，分別安排在周

78、二的3、4節(jié)、周三的1、2節(jié)，則我們認(rèn)為該課程的日組合優(yōu)度為0.2。當(dāng)然，有些課程屬于例外，例如兩節(jié)理論假兩節(jié)實(shí)驗(yàn)則可以間隔較短的時(shí)間；有些課程設(shè)計(jì)則需要連續(xù)進(jìn)行。</p><p>　　我們可以利用全校的所有周上課次數(shù)大于1的課程的日組合優(yōu)度的平均值來(lái)衡量課程表中日組合優(yōu)度的優(yōu)劣。</p><p><b>　　(4.3)</b></p><p>

79、;　　式中 ——全校所有周上課次數(shù)大于1的課程的日組合優(yōu)度的平均值</p><p>　　——課程i的日組合優(yōu)度</p><p>　　——周上課次數(shù)大于1的課程總數(shù)</p><p>　　值越大，說(shuō)明課表中非2課時(shí)的課程日組合優(yōu)度越大。</p><p>　　(4) 課程時(shí)間片利用度</p><p>　　課程的時(shí)間片利用度

80、，是衡量該課程的每次上課對(duì)所分配的時(shí)間片的利用情況的標(biāo)志。例如：一個(gè)周學(xué)時(shí)為2的課程，如果為其分配的時(shí)間片是在上午(1、2節(jié)或3、4節(jié))，則其時(shí)間片利用度為1，如果在下午或晚上，則會(huì)造成一節(jié)課時(shí)間的浪費(fèi)，其時(shí)間片利用度就為0.3。</p><p><b>　　(4.4)</b></p><p>　　式中 ——所有課程的時(shí)間片利用度的平均值</p>&l

81、t;p>　　——課程i的第j個(gè)時(shí)間片的利用度</p><p>　　——課程i的所分配的時(shí)間片的個(gè)數(shù)</p><p>　　——所開(kāi)設(shè)的課程的總數(shù)</p><p>　　的值越大，說(shuō)明課表的所有課程的時(shí)間片利用度越高。</p><p>　　(5) 課程時(shí)間段分布均勻度</p><p>　　課程的時(shí)間段分布均勻度的作用是

82、使每個(gè)時(shí)間段所安排的課程的數(shù)目相對(duì)均勻，避免出現(xiàn)某個(gè)時(shí)間段的課程過(guò)于集中，某個(gè)時(shí)間段沒(méi)有課的現(xiàn)象。如果安排在每個(gè)時(shí)間段的課程的數(shù)目越均勻，同樣數(shù)目的課程對(duì)資源的需求就越少。課程的時(shí)間段分布均勻度為：</p><p>　　其中 (4.5)</p><p>　　式中 ——課程的時(shí)間段分布均勻度</p><p>　　——每個(gè)時(shí)間段開(kāi)設(shè)的課程的平均

83、值</p><p>　　——第d個(gè)時(shí)間段開(kāi)設(shè)的課程總數(shù)</p><p>　　我們用全校課程的時(shí)間段分布均勻程度的平均值來(lái)評(píng)價(jià)開(kāi)設(shè)的課程的日分布均勻程度。的值越大，我們認(rèn)為課程表中每個(gè)時(shí)間段安排的課程的數(shù)目越均勻。</p><p>　　4.2 排課系統(tǒng)中的基本算法</p><p>　　4.2.1 排課算法的面向?qū)ο蟮膽?yīng)用</p>

84、<p>　　排課系統(tǒng)的實(shí)現(xiàn)采用C#語(yǔ)言，利用面向?qū)ο蟮姆椒╗18-24]。在實(shí)現(xiàn)時(shí)，考慮到排課因素，約束條件的表現(xiàn)，定義如下的類(lèi)(只給出各個(gè)類(lèi)的字段的定義)：</p><p><b>　　(1) 課元信息類(lèi)</b></p><p>　　為了記錄課程、教師、班級(jí)、開(kāi)課校區(qū)、教室類(lèi)型的要求、班級(jí)人數(shù)、周學(xué)時(shí)等信息，我們建立了相應(yīng)的課元信息類(lèi)，用來(lái)保存從數(shù)據(jù)庫(kù)

85、讀取得每個(gè)教學(xué)任務(wù)中的上述信息，一個(gè)課元就相當(dāng)于一個(gè)教學(xué)任務(wù)。在排課時(shí)，所有課元作為靜態(tài)數(shù)據(jù)，為排課算法提供相應(yīng)的信息。</p><p>　　public class CourseUnite</p><p><b>　　{</b></p><p>　　internal int CourseUniteNo; //課元編號(hào)，主鍵</p>

86、;<p>　　internal string CourseNo; //課程編號(hào)</p><p>　　internal string TeacherNo; //教師編號(hào)</p><p>　　internal string ClassNo; //班級(jí)編號(hào)</p><p>　　internal char CampusNo; //開(kāi)課校

87、區(qū)編號(hào)，A：蛟橋園</p><p>　　//B：麥廬園 C：楓林園</p><p>　　internal sbyte RoomType; //教室類(lèi)型編號(hào)：多媒體1：機(jī)房</p><p>　　//2：實(shí)驗(yàn)室 3：語(yǔ)音室4：普通教室 </p><p>　　internal int ClassCapacity ; //班級(jí)人數(shù)編號(hào)</

88、p><p>　　internal sbyte WeekTime; //課程周學(xué)時(shí)</p><p><b>　　}</b></p><p>　　(2) 基因基本信息類(lèi)</p><p>　　排課的任務(wù)就是為每個(gè)教學(xué)任務(wù) (課元)安排一個(gè)合適時(shí)間和教室。基因用來(lái)記錄每個(gè)課元的具體安排的信息。本文在給課元安排教室時(shí)，只考慮

89、了同一課元被安排在一個(gè)教室的情況。</p><p>　　public class Genetic </p><p><b>　　{</b></p><p>　　internal int courseuniteno; //課元編號(hào)</p><p>　　internal int roomno;

90、 //教室編號(hào)</p><p>　　internal sbyte[] timeno=new sbyte[3]; //時(shí)間片數(shù)組</p><p><b>　　}</b></p><p>　　(3) 教師特殊時(shí)間要求類(lèi)</p><p>　　老師可能由于工作方面的原因，在一周內(nèi)的某個(gè)時(shí)間段

91、不能安排課程?？紤]到這種情況，我們創(chuàng)建了教師特殊時(shí)間要求類(lèi)，記錄老師不能上課的時(shí)間段。同時(shí)，為方便檢測(cè)同一老師同一時(shí)間只能上一個(gè)班課的約束，創(chuàng)建了一個(gè)記錄教師上課時(shí)間安排的數(shù)組。</p><p>　　public class TeacherTime //創(chuàng)建教師特殊時(shí)間類(lèi)</p><p><b>　　{</b></p><p>　　inter

92、nal int TeacherNo; //教師編號(hào)</p><p>　　internal string canottime; //教師不能上課的時(shí)間對(duì)應(yīng)的字符串</p><p>　　//創(chuàng)建老師上課時(shí)間安排數(shù)組，取值為1表示該時(shí)間段已經(jīng)安排</p><p>　　//課，否則為0；若1-12節(jié)安排課，則arrangetime[0]=1;</p&

93、gt;<p>　　internal sbyte[] arrangetime=new sbyte[20];</p><p><b>　　}</b></p><p>　　假如，信息管理學(xué)院周四下午所有老師要開(kāi)會(huì)，不能上課，其他時(shí)間都可以上課，則信息學(xué)院所有老師的canottime值為“O”。如果一名住在南昌市區(qū)的老教師，由于身體及上下班回家距離的限制，不能再

94、晚上安排課，則將該老師的canottime字段設(shè)置為“DHLPT”。時(shí)間片對(duì)照表如表4-2所示。</p><p>　　在排課系統(tǒng)初始化數(shù)據(jù)時(shí)，我們視老師不能上課的時(shí)間段為在該時(shí)間段老師已經(jīng)安排了課程，這樣該時(shí)間段就不能再安排課程了。即首先根據(jù)某老師的canottime，設(shè)置arrangetime數(shù)組的值。如老教師的arrangetime數(shù)組的第3、7、11、15、19個(gè)(編號(hào)從0開(kāi)始)字段的值為1。</p&

95、gt;<p>　　表4-2 時(shí)間片對(duì)照表</p><p>　　(4) 染色體適應(yīng)度類(lèi)</p><p>　　為方便選擇操作中根據(jù)染色體適應(yīng)度的大小對(duì)父種群進(jìn)行配對(duì)操作以形成配對(duì)庫(kù)，我們建立了染色體適應(yīng)度類(lèi)，記錄染色體編號(hào)及其適應(yīng)度值。</p><p>　　public class FitnessValue //染色體適應(yīng)度類(lèi)</p><

96、;p><b>　　{</b></p><p>　　internal int chromosomeno; //記錄染色體號(hào)</p><p>　　internal float fitnessval; //記錄染色體適應(yīng)度</p><p><b>　　}</b></p>&

97、lt;p>　　(5) 教室基本信息類(lèi) </p><p>　　在為課元安排教室的時(shí)候經(jīng)常要查詢(xún)教室的容量、教室類(lèi)型。為保存從數(shù)據(jù)庫(kù)讀取的教室的信息，我們建立了教室基本信息類(lèi)。在排課時(shí)，為每個(gè)校區(qū)建立相應(yīng)的教師信息表。</p><p>　　public class ClassRoomInf//創(chuàng)建教室基本信息類(lèi)</p><p><b>　　{</b

98、></p><p>　　internal int classroomno; //教室編號(hào)</p><p>　　internal int roomcapacity; //教室容量 </p><p>　　internal short roomtype; //教室類(lèi)型</p><p><b&

99、gt;　　}</b></p><p>　　4.2.2 教室調(diào)度算法</p><p>　　根據(jù)江西財(cái)經(jīng)大學(xué)的校區(qū)分布情況，在系統(tǒng)中建立了三個(gè)教室信息表，分別為蛟橋園教室信息表、楓林園教室信息表、麥廬園教室信息表。教室信息表用來(lái)記錄教室編號(hào)、類(lèi)型、容量，類(lèi)型為ClassRoomInf。建立了三個(gè)教室時(shí)間表，行為教室，列為時(shí)間段，用來(lái)記錄某個(gè)時(shí)間段某教室的占用情況。</p&g

100、t;<p>　　為了使教室資源得到最好的利用，在排課之前，先利用排序函數(shù)(SortFunction())對(duì)教室信息表按教室容量進(jìn)行升序排序。在為課元分配教室時(shí)，從教室信息表的第一條記錄開(kāi)始檢索，從小到大依次匹配，匹配成功則返回該教室編號(hào)。這樣可以減少教室的浪費(fèi)，除非沒(méi)有小教室，只有大教室。教室調(diào)度算法具體描述如下：</p><p>　　(1) 初始化i=0，countfalse=0(記錄失敗次數(shù))；

101、</p><p>　　(2) 判斷i是否小于該校區(qū)教室的總數(shù)，若不小于則結(jié)束，沒(méi)有找到要求的教室，提示錯(cuò)誤；</p><p>　　(3) 判斷第i個(gè)教室的教室類(lèi)型、容量是否符合要求，若不符合，轉(zhuǎn)(6)；</p><p>　　(4) 判斷countfalse是否小于50，若小于，判斷當(dāng)前時(shí)間下，該教室是否可用；若可用，轉(zhuǎn)(5)；否則重新產(chǎn)生一個(gè)可用的時(shí)間(該時(shí)間老師沒(méi)

102、有安排課程)，countfalse=countfalse+1，轉(zhuǎn)(4)；</p><p>　　(5) 判斷教室已占用的時(shí)間段數(shù)目是否小于15，若小于，則教室i在該時(shí)間段被分配且重置countfalse=0；否則轉(zhuǎn)(6)；</p><p>　　(6) i=i+1，轉(zhuǎn)(2)。</p><p>　　該算法可以有效避免一次判斷時(shí)，某時(shí)間段一個(gè)教室不可用則該教室不可用的判斷，

103、在嘗試50次后如果該教室仍不可用，則我們可以認(rèn)為該教室基本上在每個(gè)時(shí)間段都被安排了課，則選擇下一個(gè)教室。同時(shí)，一個(gè)教室可用，但是這個(gè)教室在20個(gè)時(shí)間段中已經(jīng)安排了15或更多個(gè)時(shí)間段，則說(shuō)明該教室已經(jīng)負(fù)荷很重，若再給這個(gè)教室安排課程，很容易出現(xiàn)教室利用的沖突。為了避免這種情況的發(fā)生，如果某教室被安排的時(shí)間段超過(guò)15，則我們不再為該教室安排課程。</p><p>　　4.2.3 基因初始化算法</p>

104、<p>　　基因是染色體的基本組成單位，在排課問(wèn)題中，染色體相當(dāng)于一個(gè)課表，基因相當(dāng)于課表中的一個(gè)課元。填充一個(gè)基因就是為課元分配教室和時(shí)間片。具體算法描述如下：</p><p>　　(1) 產(chǎn)生一個(gè)隨機(jī)數(shù)，其值在0到19之間，作為一個(gè)時(shí)間片；</p><p>　　(2) 根據(jù)該時(shí)間片，利用教室調(diào)度算法調(diào)用一個(gè)空閑的教室類(lèi)型容量都符合要求的教室；</p><

105、p>　　(3) 判斷該課元的周學(xué)時(shí)；</p><p>　　(4) 初始化countfalse=0(記錄失敗次數(shù))；</p><p>　　(5) 根據(jù)周學(xué)時(shí)的大小，產(chǎn)生隨機(jī)數(shù)(0-19)。若周學(xué)時(shí)為6，則產(chǎn)生兩個(gè)隨機(jī)數(shù)(時(shí)間片)；周學(xué)時(shí)為5或4，則產(chǎn)生一個(gè)隨機(jī)數(shù)(時(shí)間片)；</p><p>　　(6) 各時(shí)間片整除4，結(jié)果若有相等(即同一天同一課程安排了兩次)，

106、則轉(zhuǎn)(4)；</p><p>　　(7) 判斷在這些時(shí)間片教室是否可用及老師是否安排課程，若不可用或已安排，則判斷countfalse是否小于50，若小于則countfalse=countfalse+1，轉(zhuǎn)(5)；若不小于，則轉(zhuǎn)(1)；</p><p>　　(8) 將教室時(shí)間表中該教室對(duì)應(yīng)的時(shí)間片置為1(已占用)，老師的arrangetime數(shù)組對(duì)應(yīng)的時(shí)間段置為1(已排課)，并結(jié)束。<

107、;/p><p>　　同時(shí)，對(duì)于周學(xué)時(shí)為3的課程(包括周學(xué)時(shí)位5的課程，為其安排的一個(gè)時(shí)間段)，必需保證安排在下午或晚上，如果在上午，則重新安排，轉(zhuǎn)(1)。</p><p>　　在該算法中，避免了教室容量，教室類(lèi)型與課程要求不匹配的沖突，同時(shí)我們把老師不能上課的時(shí)間視為在該時(shí)間老師已經(jīng)被安排課程，利用每個(gè)老師的arrangetime數(shù)組，判斷某時(shí)間段老師是否空閑來(lái)安排安排時(shí)間，這樣就可以為每個(gè)老

108、師分配可用的時(shí)間，并避免同一時(shí)間同一老師只能上一門(mén)課的沖突。在分配合理的教室和時(shí)間段后，將該教室的相應(yīng)時(shí)間段設(shè)置為占用，實(shí)現(xiàn)了同一時(shí)間同一教室只能上一門(mén)課，同一時(shí)間同一班級(jí)只能上一門(mén)課的約束。在為每條染色體填充基因的時(shí)候，我們課元的開(kāi)課校區(qū)傳遞相應(yīng)的教室信息表、教室時(shí)間表，這樣就保證了每個(gè)課元的被安排在教學(xué)任務(wù)書(shū)規(guī)定的校區(qū)。這樣填充的課表滿足所有的硬性約束，是一個(gè)可行的課表。</p><p>　　4.2.4 沖

109、突檢測(cè)算法</p><p>　　在初始化課表時(shí)，產(chǎn)生的每一個(gè)課表均是滿足所有硬性約束的可行課表。但是在進(jìn)行交叉操作室，我們交換交叉點(diǎn)處兩個(gè)課元的上課時(shí)間，其他不變。這樣可能造成同一時(shí)間同一教師只能上一門(mén)課的約束。所以這里的沖突檢測(cè)函數(shù)只要檢測(cè)同一時(shí)間同一教師是否只上一門(mén)課。</p><p>　　(1) 初始化i=0；</p><p>　　(2) 判斷i是否小于課元總

110、數(shù)，是則結(jié)束，沒(méi)有沖突；</p><p>　　(3) 初始化j=i+1；</p><p>　　(4) 判斷j是否小于課元總數(shù)，若不小于，則轉(zhuǎn)(8)；</p><p>　　(5) 比較課元i與課元j的教師是否相同，相同則轉(zhuǎn)(7)；</p><p>　　(6) j=j+1，轉(zhuǎn)(4)；</p><p>　　(7) 判斷課元i

111、與課元j的時(shí)間片是否有相同的，有則結(jié)束，返回沖突；</p><p>　　(8) i=i+1，轉(zhuǎn)(2)。</p><p>　　4.3 排課問(wèn)題中遺傳算法的設(shè)計(jì)</p><p>　　4.3.1 遺傳算法的編碼</p><p>　　在遺傳算法中如何描述問(wèn)題的可行解，即把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就稱(chēng)為編

112、碼。要利用遺傳算法對(duì)課表進(jìn)行優(yōu)化，首先要考慮的是如何表現(xiàn)的問(wèn)題，即如何對(duì)染色體編碼，使其適用于遺傳算法的操作。編碼方法確定后，遺傳算法通過(guò)對(duì)染色體編碼的操作，不斷搜索出適應(yīng)度高的個(gè)體，并在種群中逐漸增加其數(shù)量，最終尋找出問(wèn)題的最優(yōu)解或近似最優(yōu)解。</p><p>　　編碼方法是一種會(huì)影響到遺傳算法的交叉算子、變異算子的運(yùn)算方法。一個(gè)好的編碼方法使交叉操作、變異操作可以簡(jiǎn)單的實(shí)現(xiàn)和執(zhí)行。經(jīng)典的遺傳算法通常采用二進(jìn)制