畢業(yè)設(shè)計-學(xué)分制模式下基于遺傳算法

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

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

3、中，本文采用了面向?qū)ο蟮姆椒?，設(shè)計了課表安排中的教室調(diào)度算法、基因填充算法、沖突檢測算法，使得排課得以實現(xiàn)。利用真實的數(shù)據(jù)進(jìn)行系統(tǒng)測試，并分析了各參數(shù)對遺傳操作及結(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ù)語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 排課問題的目標(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 沖突檢測算法19</p><p>　　4.3 排課問題中遺傳算法的設(shè)計19</p><p>　　4.3.1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

49、/p><p>　　基因重組是結(jié)合來自父代交配種群中的信息產(chǎn)生新的個體。依據(jù)個體編碼表示方法的不同，可以有以下的算法：</p><p>　　① 實值重組(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)算，是指將個體染色體編碼串中的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

73、;/p><p>　　式中 ——所有課次的教室利用率的平均值</p><p>　　——第i個課次的教室利用率</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)度是對某一時間片上課效果好壞的量化。我們?yōu)槊恳粋€時間片賦予不同的優(yōu)度值以表示對這個時間片的偏好程度。節(jié)次優(yōu)度含有一定的主觀因素，每個人對同一時間片的偏好不同，不同的季節(jié)同一個時間片的上課效果也會有差別。我們可以讓排課人員來設(shè)置每個時間片的節(jié)次優(yōu)度，以體現(xiàn)不同人，不同學(xué)期的要求。如學(xué)年的第一個學(xué)期進(jìn)入到冬季時，上午1、2節(jié)比3、4節(jié)的節(jié)次優(yōu)度可能低些，因為天冷部分同學(xué)不愿早起上課。第二學(xué)期進(jìn)

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

76、t;/p><p>　　式中 ——全校課程的節(jié)次優(yōu)度的平均值</p><p>　　——第i個課程的第j個時間段的節(jié)次優(yōu)度</p><p>　　——第i個課程的時間段的個數(shù)</p><p>　　——所開設(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)志。我們對所有的課程的日組合優(yōu)度進(jìn)行優(yōu)度判定。例如：一個周學(xué)時為6的課程，每周上課3次，每次兩個課時，如果這三個時間片分別為周一的1、2節(jié)、周三的3、4節(jié)、周五的1、2節(jié)或者周一的3、4節(jié)、周三的1、2節(jié)、周五的3、4節(jié)，則我們認(rèn)為該課程的日組合優(yōu)度為1。如果一門周學(xué)時為4的課程，分別安排在周

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

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

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

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

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

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

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

86、;<p>　　internal string CourseNo; //課程編號</p><p>　　internal string TeacherNo; //教師編號</p><p>　　internal string ClassNo; //班級編號</p><p>　　internal char CampusNo; //開課校

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

88、p><p>　　internal sbyte WeekTime; //課程周學(xué)時</p><p><b>　　}</b></p><p>　　(2) 基因基本信息類</p><p>　　排課的任務(wù)就是為每個教學(xué)任務(wù) (課元)安排一個合適時間和教室?；蛴脕碛涗浢總€課元的具體安排的信息。本文在給課元安排教室時，只考慮

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

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

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

92、nal int TeacherNo; //教師編號</p><p>　　internal string canottime; //教師不能上課的時間對應(yīng)的字符串</p><p>　　//創(chuàng)建老師上課時間安排數(shù)組，取值為1表示該時間段已經(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é)院周四下午所有老師要開會，不能上課，其他時間都可以上課，則信息學(xué)院所有老師的canottime值為“O”。如果一名住在南昌市區(qū)的老教師，由于身體及上下班回家距離的限制，不能再

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

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

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

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

98、></p><p>　　internal int classroomno; //教室編號</p><p>　　internal int roomcapacity; //教室容量 </p><p>　　internal short roomtype; //教室類型</p><p><b&

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

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

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

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

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

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

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

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

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

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

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

110、數(shù)，是則結(jié)束，沒有沖突；</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的時間片是否有相同的，有則結(jié)束，返回沖突；</p><p>　　(8) i=i+1，轉(zhuǎn)(2)。</p><p>　　4.3 排課問題中遺傳算法的設(shè)計</p><p>　　4.3.1 遺傳算法的編碼</p><p>　　在遺傳算法中如何描述問題的可行解，即把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就稱為編

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