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