【正文】 第一章 緒論基于遺傳算法的自動排課系統(tǒng)畢業(yè)設計第一章 緒論排課是學校教學管理中十分重要、又相當復雜的管理工作之一，其實質(zhì)就是為學校所設置的課程安排時間和地點，從而使整個教學能夠有計劃有秩序的進行。迄今為止，對課程表的研究工作已經(jīng)進行了長達四十多年之久，取得了豐碩的成果。但是，仍然存在許多不足之處，例如規(guī)模大、約束(條件)復雜以及規(guī)律不斷變化等，因此課程表問題至今仍未完全解決。課程表的編排是一個涉及多種因素的組合規(guī)劃問題，它要保證在課程安排中教師、學生、教室不能產(chǎn)生沖突(所謂沖突，就是將需上不同課程的兩個或多個班安排在了同一時間、同一教室，或為同一教師在同一時間段安排了多門課程等情況)，并且要滿足教師的要求和資源限制等約束條件。目前，國內(nèi)的大部分學校仍然采用手工排課的方法。手工排課工作的主要手段是“擺牌”，就是在一個畫有空課表的版面上將有課名的小牌擺在適當?shù)奈恢蒙?，邊擺邊觀察，邊調(diào)整，憑借經(jīng)驗將各門課擺在合理的位置上，最后形成一個有效的課程表。這種辦法沒有一定的規(guī)律，沒有理論指導，更沒有數(shù)據(jù)模型，具有很大的盲目性。所以，要為上千名學生和上百名教師安排出合理的課程表，往往需要花費教務處人員很多的時間，工作量大，排出的課程表不宜調(diào)整。隨著中國教育體制改革的不斷深入，學生人數(shù)的不斷上升，課程設置不斷向深度和廣度發(fā)展，手工排課的缺點就越來越突出。由于計算機具有運算速度快、處理能力強等特點，很自然地就進入到這一應用領(lǐng)域中。用計算機進行排課能夠快速地得到滿足約束條件的可行結(jié)果，具有排課時間短、省人力和質(zhì)量高的優(yōu)點，不但能使教務人員從繁雜的排課任務中解脫出來，而且對于推動教學的發(fā)展也起到非常重要的作用。每個學期開學時，教務管理工作中的課程表安排問題，都是教務處面臨的一項艱巨任務。排課問題是一個非常棘手卻又亟待解決的問題，通常都是使用傳統(tǒng)的人工手動排課方法。手工排課不僅勞動強度大，而且排課效率低，很難排出一個讓人滿意的課程表。時間，教師，教室，班級，課程等限制問題更是難以解決，使用計算機進行自動排課已經(jīng)成為近年來的熱點話題。教學管理的信息化需要計算機輔助排課，而排課理論的研究和軟件技術(shù)的成熟己為我們提供了計算機自動排課的重要手段，研究一種準確、高效、實用、自動化程度高的排課系統(tǒng)己經(jīng)成為可能。排課問題是NP完全問題，許多學者分別在理論、啟發(fā)式搜索技術(shù)應用求解、專家系統(tǒng)應用求解和遺傳算法應用求解上作了很多研究。國外從20世紀50年代末就對排課問題展開了研究。1963年Gotlieb在他的文章中提出了排課問題的數(shù)學模型[2]，它標志著排課問題的研究正式跨越了科學的殿堂。之后，人們對排課問題的算法做了許多探索，但由于排課問題是NP完全問題，并且易受實際問題邊界的影響，大多數(shù)求解結(jié)果都不夠理想。Ferland[3]等人和吳金榮[4]把排課問題化成整數(shù)規(guī)劃來解決，但計算量很大，其僅僅適用于規(guī)模很小的課表編排，對于大規(guī)模復雜的排課情況，至今沒有一個切實可行的算法。何永太[5]和胡順仁[6]等人試圖用圖論中的染色問題來求解排課問題，可惜圖的染色問題本身也是NP完全問題。由于問題的復雜，許多文章利用啟發(fā)式函數(shù)來解決排課問題，大多數(shù)啟發(fā)方法都是模擬手工排課的過程來實現(xiàn)的。由于實際的排課問題存在各種各樣的限制條件與特殊要求，對這些因素處理的好壞就顯得尤為重要。進入20世紀90年代，國外對排課問題的研究仍然非?；钴S。如印度Vastapur大學管理學院的Arabinda Tripathy、加拿大Montreal大學的Jean Aubin和JacqueSA Ferland以及Charles Fleutent等。Arabinda Tripathy的工作是針對以“人”為單位進行課表編排的。他運用拉格朗日松弛法和分支定界技術(shù)求解，這種方法的缺點是為了減少變量的個數(shù)，人為造成科目間的沖突。，他采用多重課組的方法來處理沖突(即根據(jù)學生選課的矛盾情況，將人數(shù)多的課程在一星期內(nèi)開多次)。:時間表問題和分組問題。在時間表問題中，根據(jù)學生注冊情況、教師和教室的可利用情況形成一個主時間表。對于選課人數(shù)較多的大課，一個星期要分成幾個時間段來上，分組問題就是將學生分給各時間段。兩個問題相關(guān)聯(lián)，通過懲罰因子來構(gòu)造啟發(fā)函數(shù)。他們研制的SAPHIR課程調(diào)度決策支持系統(tǒng)分為數(shù)據(jù)處理、自動優(yōu)化、交互優(yōu)化等幾個模塊。該系統(tǒng)解決矛盾的主要方法也是采用多重課組。在國內(nèi)，對于排課系統(tǒng)的研發(fā)，林漳希和林堯瑞1984年發(fā)表了該課題上的實驗性研究成果。這些應用界面很友好的排課軟件己經(jīng)可以幫助排課人員大大提高工作效率。這些系統(tǒng)大多數(shù)都是模擬手工排課，以“班”為單位，只能在排課過程中輔助工作人員進行排課，并沒有一套完善有效的自動排課算法。當人工輸入的條件達到一定的限制程度時，軟件運行就有可能出現(xiàn)死鎖現(xiàn)象，使得系統(tǒng)的實際應用非常困難[19]。后期人工調(diào)整的工作量并不比重新排課的工作量小很多。一旦出現(xiàn)了這種現(xiàn)象，就要把所有的數(shù)據(jù)作廢或者打亂重排，之前做的工作都付諸東流。高校的課程、教室、教師等因素都十分復雜，排課所需數(shù)據(jù)量也十分龐大，所以造成的時間、人力損失也非常巨大。課程表問題又稱時間表問題，是一個多因素的優(yōu)化決策問題，也是組合規(guī)劃中的典型問題，是NP完全的[1]。對于排課問題的解決，研究人員己經(jīng)使用了各種不同的算法，但由于該問題的復雜性，所求解也只能是較為合理、較為滿意的解。隨著人工智能的發(fā)展，特別是在計算智能領(lǐng)域的拓展，借鑒于生物界進化思想和遺傳算法，由于其超強的并行搜索能力，以及在解決優(yōu)化問題中表現(xiàn)出來的高度魯棒性，它已經(jīng)被廣泛應用于各個領(lǐng)域。目前，很多研究人員已使用遺傳算法來求解排課問題，如文獻[20]使用遺傳算法優(yōu)化教室的合理利用，文獻[21]的用自適應的遺傳算法求解大學課表安排問題，文獻[22]的基于遺傳算法排課系統(tǒng)的設計與實現(xiàn)等等。這些應用說明，使用遺傳算法來解決排課問題，其結(jié)果還是令人較為滿意的。教學排課問題是學校每個排課人員最頭痛的問題。短時間內(nèi)沒有一個方法來達到學校教師滿意的結(jié)果。其最大的困難是硬件資源的限制。排課人員在硬件資源兼顧的條件下難于短時間內(nèi)排出教師滿意的課表。“窮舉法”可將所有的方式列出然后找出最佳解，但成本太高，時間太長。如一個星期有n個時段可排課，有m位教師需要參與排課．平均每位教師一個星期要上i堂課。其排課的組合數(shù)有nm*i次?？梢姼F舉法的復雜度有多高。遺傳算法是一種通過模擬自然進化過程搜索最優(yōu)解的方法。本文試圖以遺傳算法來實現(xiàn)排課問題的最佳解。本課題研究的目的就是實現(xiàn)基于遺傳算法的排課系統(tǒng)，并在VB下具體實現(xiàn)，滿足日常需求。貪心法(greedy method)是一種改進了的分級處理方法，逐步構(gòu)造最優(yōu)解。它從問題的某一個初始解出發(fā)，在一定的標準下做出一系列的貪心選擇(選擇一旦做出，就不可再更改)，即當前狀態(tài)下看上去最優(yōu)的選擇．逐步逼近給定的目標．以盡可能快的速度求得更好的解 當達到算法中的某一步不能再繼續(xù)前進時則停止。貪心算法的核心是在所選擇的策略中，選一個權(quán)值最優(yōu)的策略作為當前策略。因此貪心算法的好壞主要決定于權(quán)值的確定。在排課系統(tǒng)中，貪心算法是從排課問題的某一初始狀態(tài)出發(fā)．依據(jù)給出的貪心策略朝最終排好全部課程這個目標前進一步，判斷是否可以求出可行解的一個解元素．如果可以則繼續(xù)依據(jù)貪心策略向給定目標前進．求出下一個解元素。直到前進不能再繼續(xù)時停止。最后由所有得到的解元素組成問題的一個可行解。此時算法結(jié)束。貪心算法的缺點在于解的效果比較差．而最大優(yōu)勢在于極低的時間復雜度。能做到某種意義上的局部最優(yōu)。它具有不可后撤性，可以有后效性．一般情況下不滿足最優(yōu)化原理。并且不適用于解決可行性問題．僅適用于較容易得到可行解的最優(yōu)性問題。為了盡量減小貪心算法帶來的副作用。使得最后得到的解更接近最優(yōu)解?？梢栽谒惴ūM可能多的地方使用有效的最優(yōu)化算法(如動態(tài)規(guī)劃)。貪心算法還可以為搜索算法提供較優(yōu)的初始界值?；厮菟惴ㄒ步性囂椒ǎ且环N系統(tǒng)地搜索問題的解的方法，可以被認為是一個有過剪枝的DFS(深度優(yōu)先搜索)過程。它按優(yōu)先條件向前搜索，以達到目標，但當搜索到某一步時．發(fā)現(xiàn)原先的選擇并不優(yōu)或達不到目標。就退回一步重新選擇。而滿足回溯條件的某個狀態(tài)點稱之為回溯點。具體到計算機智能排課系統(tǒng)中，選優(yōu)條件即為排課數(shù)學模型中的約束條件群(需求集中的元素特征與資源集中的元素特征相互作用形成的數(shù)學關(guān)系)若不滿足約束條件群，該選擇即為不優(yōu)或達不到目標 當遍歷該步驟的所有可能仍未滿足約束條件群．則該狀態(tài)滿足了回溯條件，該狀態(tài)點即為回溯點。回溯算法解決排課問題時首先要描述解的形式，定義一個解空間．它包含問題的所有解：其次構(gòu)造狀態(tài)空間樹，這棵樹的每條完整路徑都代表了一種解的可能：再次是構(gòu)造約束函數(shù)，通過描述合法解的一般特征用于去除不合法的解，從而避免繼續(xù)搜索出這個不合法解的剩余部分：然后通過深度優(yōu)先搜索完成回溯。①設置初始化的方案(給變量賦初值，讀入已知數(shù)據(jù)等)；②變換方式去試探。若全部試完則轉(zhuǎn)⑦ ；③ 判斷此法是否成功(通過約束函數(shù))，不成功則轉(zhuǎn)② ；④ 試探成功則前進一步再試探；⑤正確方案還未找到則轉(zhuǎn)② ；⑥ 已找到一種方案則記錄并打?。虎咄嘶匾徊?回溯)，若未退到根則轉(zhuǎn)② ；⑧ 已退到根節(jié)點則排課結(jié)束或打印無排課結(jié)果?；厮莘ㄟm用于解的組合數(shù)相當大但仍然有限的那一類問題。它的一個有重要的特性是在搜索執(zhí)行的同時產(chǎn)生解空問。在搜索期間的任何時刻．僅保留從開始節(jié)點到當前節(jié)點的路徑。因此．回溯算法的空間需求為一個常數(shù)，即從開始節(jié)點起最長路徑的長度。這個特性非常重要．因為解空間的大小通常是最長路徑長度的指數(shù)或階乘。所以如果要存儲全部解空間的話。再多的空間也不夠用。其缺點是時間復雜度較大．因此在采用時還需要謹慎。最好是和其它的算法結(jié)合使用。遺傳算法是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法，并出版了頗有影響的專著《Adaptation in Natural and Artificial Systems》，GA這個名稱才逐漸為人所知，（SGA）。 遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特征的實體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應度（fitness）大小挑選（selection）個體，并借助于自然遺傳學的遺傳算子（genetic operators）進行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解。遺傳算法是一類可用于復雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比，主要有以下特點： 遺傳算法以決策變量的編碼作為運算對象。傳統(tǒng)的優(yōu)化算法往往直接決策變量的實際植本身，而遺傳算法處理決策變量的某種編碼形式，使得我們可以借鑒生物學中的染色體和基因的概念，可以模仿自然界生物的遺傳和進化機理，也使得我們能夠方便的應用遺傳操作算子。 遺傳算法直接以適應度作為搜索信息，無需導數(shù)等其它輔助信息。 遺傳算法使用多個點的搜索信息，具有隱含并行性。 遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。根據(jù)其算法特點，遺傳算法非常適合于應用到排課處理中。具體應用方式將在后面設計部分詳細說明。進入90年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是遺傳算法的應用研究顯得格外活躍，不但它的應用領(lǐng)域擴大，而且利用遺傳算法進行優(yōu)化和規(guī)則學習的能力也顯著提高，同時產(chǎn)業(yè)應用方面的研究也在摸索之中。此外一些新的理論和方法在應用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳算法增添了新的活力。遺傳算法的應用研究已從初期的組合優(yōu)化求解擴展到了許多更新、更工程化的應用方面。隨著應用領(lǐng)域的擴展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向：一是基于遺傳算法的機器學習，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴展到具有獨特的規(guī)則生成功能的嶄新的機器學習算法。這一新的學習機制對于解決人工智能中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡、模糊推理以及混沌理論等其它智能計算方法相互滲透和結(jié)合，這對開拓21世紀中新的智能計算技術(shù)將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機體系結(jié)構(gòu)的研究都是十分重要的。四是遺傳算法和另一個稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應、進化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進化規(guī)劃（Evolution Programming,EP）以及進化策略（Evolution Strategy,ES）等進化計算理論日益結(jié)合。EP和ES幾乎是和遺傳算法同時獨立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進化機制的智能計算方法，即同遺傳算法具有相同之處，也有各自的特點。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點。（Adjacency based crossover），這個算子是特別針對用序號表示基因的個體的交叉，并將其應用到了TSP問題中，通過實驗對其進行了驗證。（Stochastic Iterated Genetic Hillclimbing，SIGH）采用了一種復雜的概率選舉機制，此機制中由m個“投票者