【正文】 . . . .. . 普通本科畢業(yè)論文(設計)題 目: 學分制模式下基于遺傳算法的排課系統(tǒng)的設計 學習好幫手摘 要排課問題是一個多約束、多目標的優(yōu)化問題，其實質是時間表問題，已經被確認為NP完全問題。遺傳算法作為一種隨機搜索算法，利用群體搜索技術，對解決NP問題非常有效。本文將遺傳算法應用于學分制模式下的排課系統(tǒng)中，通過對排課因素和約束條件的深入分析，制定了排課問題的優(yōu)化目標，設計出了適合于遺傳操作的編碼模型，給出了合理的適應度值的計算方法。通過對初始種群進行選擇、交叉、變異等過程不斷進化，取得了優(yōu)化的課表。在排課系統(tǒng)設計中，本文采用了面向對象的方法，設計了課表安排中的教室調度算法、基因填充算法、沖突檢測算法，使得排課得以實現(xiàn)。利用真實的數(shù)據(jù)進行系統(tǒng)測試，并分析了各參數(shù)對遺傳操作及結果的影響?！娟P鍵詞】學分制模式；排課系統(tǒng)；遺傳算法；多目標優(yōu)化Design of the Course Arrangement System Based on Genetic Algorithms in Credit ModeAbstract：The problem of course arrangement is an optimization problem with multiconstraints and multiobjective, which is actually a timetable problem and has been proved to be a NPpleted problem. As a ramdom searching algorithm, the genetic algorithm(GA) using colony searching technology is very suitable for NPpleted problem.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 first. Then the coding mode for genetic operations is designed and the putation method for reasonable fitness is given. An optimized course table is gotten through the operations of selection, rebination and mutation on the initial colony.Based on the objectoriented method, this design makes use of classroom schedule algorithm, genetic fill algorithm and conflict detecting algorithm to arrange course. The experiments are carried out using real data to analyse the influence of all parameters on the genetic operations and results.Keywords：Credit Mode。 Course Arrangement System。 Genetic Alogrithm。 Multiobjective Optimization目 錄1 引言 12 遺傳算法 2 遺傳算法研究的內容 3 遺傳算法的基本術語 4 遺傳算法的基本思想 5 遺傳算法的基本操作 63 排課系統(tǒng)的需求分析 8 排課系統(tǒng)的業(yè)務流程分析 8 排課因素分析 10 排課的約束條件 114 基于遺傳算法的排課算法的描述 12 排課問題的目標分析 12 排課系統(tǒng)中的基本算法 15 排課算法的面向對象的應用 15 教室調度算法 17 基因初始化算法 18 沖突檢測算法 19 排課問題中遺傳算法的設計 19 遺傳算法的編碼 19 初始種群的產生 20 遺傳操作的設計 20 適應度函數(shù)的設計 225 實驗及結果分析 22 排課系統(tǒng)開發(fā)環(huán)境 22 參數(shù)設置對排課效率的影響 23 結果分析 266 總結與展望 27參考文獻 29 學習好幫手. . . .. .1 引言排課問題是高校日常教學工作和其他各項活動的基礎。課程表不僅是老師和學生上課的依據(jù)，也對學校的其他工作的安排有一定影響。利用計算機輔助排課，是教學管理實現(xiàn)科學化，現(xiàn)代化的重要課題之一。目前高校招生逐年擴張，學生人數(shù)不斷增加，再加上大多數(shù)高校實行學分制，課程開設逐漸向著廣度和深度擴展，但學校的教學資源及設備卻得不到及時補充，這些都給教務處排課人員造成很大的壓力。單純采用勞動強度大、效率低的手工排課，已成為提高教學管理質量的瓶頸。隨著計算機在教學工作中的普及應用，利用計算機進行自動排課已經成為一個重要的研究課題。排課問題不僅是教學管理工作中必需面對的問題，而且也是運籌學中研究的一個問題——時間表問題 (TimeTable Problems，簡記TTPS)。排課問題的研究始于20世紀50年代末，但直到1963年，Gotlieb在他的文章中對排課問題進行了形式化描述并提出了排課問題的數(shù)學模型[1]，才標志著排課問題的研究進入科學的殿堂。但由于在實踐中遇到的困難，人們對排課問題的解是否存在產生了疑問。1976年，S Even和Cooper等人證明了排課問題是NP完全問題[2,3]，這雖然回答了在排課實踐中遇到困難的原因，但同時宣布計算機解決排課問題無法實現(xiàn)，因為計算機難解性理論指出，現(xiàn)代計算機尚未找到解決NP完全問題的多項式算法。我國對排課問題的研究始于20世紀80年代初期，所用方法從模擬手工排課到運用人工智能構建專家系統(tǒng)或決策支持系統(tǒng)。吳金榮把排課問題化成整數(shù)規(guī)劃來解決[4]，但計算量很大，而且僅僅適用于規(guī)模很小的排課問題。何永太、胡順仁等人試圖用圖論中的染色問題來求解排課問題[5,6]，但染色問題本身也是排課問題?；趯＜蚁到y(tǒng)的求解算法將專家系統(tǒng)知識引入排課問題的求解[7]，能有效組織排課過程中的知識。但由于實際排課問題存在各種各樣的限制條件與特殊要求，至今沒有一個有效地普遍適用的排課算法。隨著現(xiàn)代智能優(yōu)化技術的出現(xiàn)和發(fā)展，模擬退火算法、禁忌搜索算法、蟻群算法、遺傳算法等被應用到排課問題中。模擬退火算法(Simulated Annealing)是Kirkpatrick等人于1983年首先提出的，它是人們從自然界固體退火過程中得到啟發(fā)并從中抽象出來的一種隨機優(yōu)化算法。模擬退火法用于求解優(yōu)化問題的出發(fā)點是基于物理中固體物質的退火過程與一般優(yōu)化問題間的相似性。在對固體物質進行退火處理時，常先將它加溫使其粒子可自由運動，以后隨著溫度的逐漸下降，粒子逐漸形成低能態(tài)晶格。若在凝結點附近的溫度下降速率足夠慢，則固體物質一定會形成最低能量的基態(tài)。優(yōu)化問題也存在類似過程。模擬退火法被用來解決許多實際應用中的優(yōu)化問題，取得了不錯的效果，用其解決排課問題[8]，現(xiàn)在還處在模型實驗階段，還有許多問題要解決。禁忌搜索的思想最早由Glover于1986年提出，它是對局部領域搜索的一種擴展，是一種全局逐步尋優(yōu)算法，是對人類智力過程的一種模擬。禁忌搜索算法通過引入一個靈活的存儲結構和相應的禁忌準則來避免迂回搜索，并通過藐視準則來赦免一些被禁忌的優(yōu)良狀態(tài)，進而保證多樣化的有效探索以最終實現(xiàn)全局優(yōu)化。文獻[9]中提出了結合網絡流算法與禁忌搜索算法的優(yōu)勢，求解排課問題的方案，雖然得出了可行解，但結果不夠理想，很多優(yōu)化因素沒有考慮。蟻群算法是隨著仿生學的發(fā)展而發(fā)展起來的，它通過模擬蟻群覓食的過程中尋找最短路徑的方法來求解優(yōu)化問題。文獻[10]提出了基于二部圖的排課模型，并揉合蟻群算法AS、ACS、MMAS三個不同模型的優(yōu)點，提出一種面向排課問題的改進型蟻群算法，但是問題求解復雜，操作繁瑣。上述算法都是一定程度上的啟發(fā)搜索算法，但是搜索過程的啟發(fā)信息依賴于實際情況，排課問題求解只能針對個別的實際問題，且沒有引入目標優(yōu)化技術，更不用說人性化方面的考慮。正是因為如此，具有智能性、并行性和高魯棒性的遺傳算法迅速應用于排課問題，并得到了很快的發(fā)展。本文正是在上述背景下展開的，在分析和實踐的過程中，針對江西財經大學排課問題的具體情況，結合排課問題中常見的約束及優(yōu)化目標，采用了一種適應于排課問題的編碼方法，并將遺傳算法應用到課表的優(yōu)化，以此獲得最終的排課方案。2 遺傳算法遺傳算法(Genetic Algorithm, GA)是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局優(yōu)化概率搜索算法。它出現(xiàn)在20世紀60年代，最早是由美國密執(zhí)安大學的John Holland教授與其同事、學生研究形成的一個比較完整的理論和方法，在一系列研究工作的基礎上，80年代由Goldberge進行歸納總結，形成了遺傳算法的基本框架。經過20余年的發(fā)展，計算機智能已經成為人工智能研究的一個重要方向，以及后來人工生命研究的興起，使遺傳算法受到廣泛關注。從1985年在美國卡內基梅隆大學召開的第一屆國際遺傳會議(International Conference on Genetic Algorithms：ICGAs，85)，到1997年5月，IEEE的Transaction on Evolutionaly Computation創(chuàng)刊，遺傳算法作為系統(tǒng)優(yōu)化、自適應和學習的高性能計算和建模方法的研究日趨成熟[3]。遺傳算法是一種借鑒生物界自然選擇和進化機制發(fā)展起來的高度并行、隨機、自適應的搜索算法。其主要特點是群體搜索策略和種群中個體之間的信息交換。由于其具有健壯性，特別適合于處理傳統(tǒng)搜索算法解決不好的復雜的和非線性問題。簡單的講，它使用了群體搜索技術，從而產生新一代的種群，并逐步使種群進化到近似最優(yōu)解的狀態(tài)。遺傳算法是多學科結合與滲透的產物，從產生至今已廣泛地運用于包括工程設計、制造業(yè)、人工智能、計算機科學、生物工程、石油勘探、自動控制、社會科學、商業(yè)和金融等各個領域。 遺傳算法研究的內容遺傳算法的研究主要集中在編碼方法、適應函數(shù)、遺傳算子、遺傳算法參數(shù)選擇、全局收斂性和搜索效率的數(shù)學基礎、欺騙問題、收斂性分析、局部收斂及混合遺傳算法等[8]。本文在將遺傳算法應用到排課問題中時，對遺傳算法的編碼、適應函數(shù)的設計、遺傳算子、遺傳算法參數(shù)的選擇等進行了分析[11]。(1) 編碼方法遺傳算法的編碼在許多問題的求解中，對算法的性能有很重要的影響。簡單二進制編碼的采用得到了Holland早期理論結果（Schema定理、最小字母表原理）的支持，但仍有很多不足之處?；疑幋a可用于克服二進制編碼映射的不連續(xù)問題。動態(tài)參數(shù)編碼的提出是為了克服搜索效率與表示精度間的矛盾，同時對克服過早收斂現(xiàn)象也有所幫助。此外，多值編碼、實值編碼、區(qū)間值編碼、Delta編碼、對稱編碼以及將以往的合成編碼分解成多個相對獨立編碼的獨立編碼策略等多種編碼方法也都被證明各有優(yōu)缺點。這些編碼方法的提出是啟發(fā)式的，缺乏一個理論基礎來判斷各種編碼方法的好壞并指導它們的設計。為解決二進制編碼帶來的“組合爆炸” 和遺傳算法的早熟收斂問題，提出了十進制編碼。根據(jù)Holland教授提出的編碼應該有利于交叉變異操作的編碼原則[4]，本文設計了適用于排課問題的編碼模型。(2) 適應函數(shù)的設計在遺傳算法中，適應度值是用來區(qū)分群體中個體好壞的標志。遺傳算法正是根據(jù)適應值對個體進行選擇的。在實際操作中，適應函數(shù)的設計對算法的收斂性及收斂速度的影響較大。本文根據(jù)排課問題的求解目標，并考慮系統(tǒng)與排課者的交互，設計了合理的適應度函數(shù)。(3) 遺傳算子遺傳算法的三個算子分別是選擇、交叉和變異。選擇體現(xiàn)“適者生存”的原理，通過適應值選擇優(yōu)質個體而拋棄劣質個體。雜交能使個體之間的遺傳物質進行交換從而產生更好的個體。變異能恢復個體失去的或未開發(fā)的遺傳物質，以防止個體在形成最優(yōu)解過程中過早收斂。① 選擇策略是遺傳算法中的很重要的一個環(huán)節(jié)。由于其對遺傳搜索過程具有較大的影響，很多人早就意識到它在遺傳算法中的重要性。所以近年來，不同的遺傳策略相繼被提出。P