【正文】 的目的就是實(shí)現(xiàn)基于遺傳算法的排課系統(tǒng)，并在 VB 下具體實(shí)現(xiàn)，滿足日常需求。 遺傳算法是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。其排課的組合數(shù)有 nm*i 次。 “窮舉法”可將所有的方式列出然后找出最佳解，但成本太高，時(shí)間太長。其最大的困難是硬件資源的限制。 教學(xué)排課問題是學(xué)校每個(gè)排課人員最頭痛的問題。目前，很多研究人員已使用遺傳算法來求解排課問題，如文獻(xiàn) [20]使用遺傳算法優(yōu)化教室的合理利用，文獻(xiàn) [21]的用自適應(yīng)的遺傳算法求解大學(xué)課表安排問題，文獻(xiàn) [22]的基于遺傳算法排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)等等。對于排課問題的解決，研究人員己經(jīng)使用了各種不同的算法，但由于該問題的復(fù)雜性，所求解也只能是較為合理、較為滿意的解。高校的課程、教室、教師等因素都十分復(fù)雜，排課所需數(shù)據(jù)量也十分龐大，所以造成的時(shí)間、人力損失也非常巨大。后期人工調(diào)整的工作量并不比重新排課的工作量小很多。這些系統(tǒng)大多數(shù)都是模擬手工排課，以“班”為 單位，只能在排課過程中輔助工作人員進(jìn)行排課，并沒有一套完善有效的自動排課算法。成形的系統(tǒng)有大連理工大學(xué) 1998 年推出的教學(xué)調(diào)度系統(tǒng)版本 和由清華大學(xué)計(jì)算機(jī)與信息管理中心開發(fā)的綜合教務(wù)管理系統(tǒng) TISER。該系統(tǒng)解決矛盾的主要方法也是采用多重課組。兩個(gè)問題相關(guān)聯(lián)，通過懲罰因子來構(gòu)造啟發(fā)函數(shù)。在時(shí)間表問題中，根據(jù)學(xué)生注冊情況、教師和教室的可利用情況形成一個(gè)主時(shí)間表。 還研究了研究生課表編排問題，他采用多重課組的方法來處理沖突 (即根據(jù)學(xué)生選課的矛盾情況，將人數(shù)多的課程在一星期內(nèi)開多次 )。 Arabinda Tripathy 的工作是針對以“人”為單位進(jìn)行課表編排的。 進(jìn)入 20 世紀(jì) 90 年代，國外對排課問題的研究仍然非常活躍。由于問題的復(fù)雜，許多文章利用啟發(fā)式函數(shù)來解決排課問題，大多數(shù)啟發(fā)方法都是模擬手工排課的過程來實(shí)現(xiàn)的。 Ferland[3]等人和吳金榮 [4]把排課問題化成整數(shù)規(guī)劃來解決，但計(jì)算量很大，其僅僅適用于規(guī)模很小的課表編排，對于大規(guī)模復(fù)雜的排課情況，至今沒有一個(gè)切實(shí)可行的算法 。 1963 年 Gotlieb 在他的文章中提出了排課問題的數(shù)學(xué)模型 [2]，它標(biāo)志著排課問題的研究正式跨越了科學(xué)的殿堂。 排課系統(tǒng)國內(nèi)外現(xiàn)狀 排課問題是 NP 完全問題，許多學(xué)者分別在理論、啟發(fā)式搜索技術(shù)應(yīng)用求解、專家系統(tǒng)應(yīng)用求解和遺傳算法應(yīng)用求解上作了很多研究。時(shí)間，教師，教室，班級，課程等限制問題更是難以解決，使用計(jì)算機(jī)進(jìn)行自動排課已經(jīng)成為近年來的熱點(diǎn)話題。排課問題是一個(gè)非常棘手卻又亟待解決的問題，通常都是使用傳統(tǒng)的人 工手動排課方法。用計(jì)算機(jī)進(jìn)行排課能夠快速地得到滿足約束條件的可行結(jié)果，具有排課時(shí)間短、省人力和質(zhì)量高的優(yōu)點(diǎn)，不但能使教務(wù)人員從繁雜的排課任務(wù)中解脫出來，而且對于推動教學(xué)的發(fā)展也起到非常重要的作用。 隨著中國教育體制改革的不斷深入，學(xué)生人數(shù)的不斷上升，課程設(shè)置不斷向深度和廣度發(fā)展，手工排課的缺點(diǎn)就越來越突出。這種辦法沒有一定的規(guī)律，沒有理論指導(dǎo)，更沒有數(shù)據(jù)模型，具有很大的盲目性。 目前，國內(nèi)的大部分 學(xué)校 仍然采用手工排課的方法。但是，仍然存在許多不足之處，例如規(guī)模大、約束 (條件 )復(fù)雜以及規(guī)律不斷變化等，因此課程表問題至今仍未完全解決。 Abstract II Abstract Along with science technical and munity information technical increases continuously, calculator science is gradually mature, its mighty function has behaved deep cognition, and it has entered the human social each realm erupts to flick the more and more important function, bringing our life biggest of convenience. Curriculum arrangement is an important and plicated working in school, so solving the problem is of great importance for teaching programming. Investigated and studied the algorithm existed, determine that adopt geic algorithm. Through Design Implementation the Auto Course Arrangement Management System Base on Geic Algorithm, researched the application of geic algorithm in the Course Arrangement Management System. Keywords: Geic Algorithm Auto Course Arrangement Management Java. 第一章 緒論 1 第一章 緒論 排課 系統(tǒng)研究背景 排課是學(xué)校教學(xué)管理中十分重要、又相當(dāng)復(fù)雜的管理工作之一，其實(shí)質(zhì)就是為學(xué)校所設(shè)置的課程安排時(shí)間和地點(diǎn)，從而使整個(gè)教學(xué)能夠有計(jì)劃有秩序的進(jìn)行。 通過 設(shè)計(jì)實(shí)現(xiàn) 基于遺傳算法的自動排課系統(tǒng)，研究了遺傳算法在排課系統(tǒng)中的應(yīng)用。解決好教學(xué)工作中的排課問題對整個(gè)教學(xué)計(jì)劃的進(jìn)行，有著十分重要的意義。摘要 I 摘 要 隨著科學(xué)技術(shù)和社會信息技術(shù)的不斷提高，計(jì)算機(jī)科學(xué)的日漸成熟，其強(qiáng)大的功能已為人們深刻認(rèn)識，它在人類社會的各個(gè)領(lǐng)域發(fā)揮著越來越重要的作用 ， 給人們的生活帶來了極大的便利 ， 成為推動社會發(fā)展的首要技術(shù)動力。 排課是學(xué)校教學(xué)管理中十分重要、又相當(dāng)復(fù)雜的工作之一。首先對排課的已有算法作了相關(guān)的調(diào)查研究， 決定采用遺傳算法 。 關(guān)鍵詞： 遺傳算法 、 自動 排課 、 Java。迄今為止，對課程表的研究工作已經(jīng)進(jìn)行了長達(dá)四十多年之久，取得了豐碩的成果。課程表的編排是一個(gè)涉及多種因素的組合規(guī)劃問題，它要保證在課程安排中教師、學(xué)生、教室不能產(chǎn)生沖突 (所謂沖突，就是將需上不同課程的兩個(gè)或多個(gè)班安排在了同一時(shí)間 、同一教室，或?yàn)橥唤處熢谕粫r(shí)間段安排了多門課程等情況 )，并且要滿足教師的要求和資源限制等約束條件。手工排課工作的主要手段是“擺牌”，就是在一個(gè)畫有空課表的版面上將有課名的小牌擺在適當(dāng)?shù)奈恢蒙?，邊擺邊觀察，邊調(diào)整，憑借經(jīng)驗(yà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é)期開學(xué)時(shí)，教務(wù)管理工作中的課程表安 排 問題 ， 都是教務(wù)處面臨的一項(xiàng)艱巨任務(wù)。手工排課不僅勞動強(qiáng)度大，而且排課效率低，很難排出一個(gè)讓人滿意的課程表。教學(xué)管理的信息化需要計(jì)算機(jī)輔助排課，而排課理論的研究和軟件技術(shù)的成熟己為我們提供了計(jì)算機(jī)自動畢業(yè)設(shè)計(jì)論文 2 排課的重要手段，研究一種準(zhǔn)確、高效、實(shí)用、自動化程度高的排課系統(tǒng)己經(jīng)成為可能。 國外從 20 世紀(jì) 50 年代末就對排課問題展開了研究。之后，人們對排課問題的算法做了許多探索，但由于排課問題是 NP 完全問題，并且易受實(shí)際問題邊界的影響，大多數(shù)求解結(jié)果都不夠理想。何永太 [5]和胡順仁 [6]等人試圖用圖論中的染色問題來求解排課問題 ，可惜圖的染色問題本身也是 NP 完全問題。由于實(shí)際的排課問題存在各種各樣的限制條件與特殊要求，對這些因素處理的好壞就顯得尤為重要。如印度 Vastapur大學(xué)管理學(xué)院的 Arabinda Tripathy、加拿大 Montreal 大學(xué)的 Jean Aubin 和JacqueSA Ferland 以及 Charles Fleutent 等。他運(yùn)用拉格朗日松弛法和分支定界技術(shù)求解，這種方法的缺點(diǎn)是為了減少變量的個(gè)數(shù)，人為造成科目間的沖突。 等人則把排課問題分成兩個(gè)子問題 :時(shí)間表問題和分組問題。對于選課人數(shù)較多的大課，一個(gè)星期要分成幾個(gè)時(shí)間段來上，分組問題就是將學(xué) 生分給各時(shí)間段。他們研制的 SAPHIR 課程調(diào)度決策支持系統(tǒng)分為數(shù)據(jù)處理、自動優(yōu)化、交互優(yōu)化等幾個(gè)模塊。 在國內(nèi)，對于排課系統(tǒng)的研發(fā)，林漳希和林堯瑞 1984 年發(fā)表了該課題上的第一章 緒論 3 實(shí)驗(yàn)性研究成果。這些應(yīng)用界面很友好的排課軟件己經(jīng)可以幫助排課人員大大提高工作效率。當(dāng)人工輸入的條件達(dá)到一定的限制程度時(shí)，軟件運(yùn)行就有可能出現(xiàn)死鎖現(xiàn)象，使得系統(tǒng)的實(shí)際應(yīng)用非常困難 [19]。一旦出現(xiàn)了這種現(xiàn)象，就要把所有的數(shù)據(jù)作廢或者打亂重排，之前做的工作都付諸東流。 課程表問題又稱時(shí)間表問題，是一個(gè)多因素的優(yōu)化決策問題，也是組合規(guī)劃中的典型問題，是 NP 完全的 [1]。 隨著人工智能的發(fā)展，特別是在計(jì)算智能領(lǐng)域的拓展，借鑒于生物界進(jìn)化思想和遺傳算法，由于其超強(qiáng)的并行搜索能力，以及在解決優(yōu)化問題中表現(xiàn)出來的高度魯棒性，它已經(jīng)被廣泛應(yīng)用于各個(gè)領(lǐng)域。這些應(yīng)用說明，使用 遺傳算法來解決排課問題，其結(jié)果還是令人較為滿意的。短時(shí)間內(nèi)沒有一個(gè)方法來達(dá)到學(xué)校教師滿意的結(jié)果。排課人員在硬件資源兼顧的條件下難于短時(shí)間內(nèi)排出教師滿意的課表。如一個(gè)星期有 n 個(gè)時(shí)段可排課，有 m 位教師需要參與排課．平均每位教師一個(gè)星期要上 i 堂課。可見窮舉法的復(fù)雜度有多高。 本文試圖以 遺傳算法 來實(shí)現(xiàn)排課問題的最佳解。 畢業(yè)設(shè)計(jì)論文 4 排課常用算法 比較 貪心算法 貪心法 (greedy method)是一種改進(jìn)了的分級處理方法，逐步構(gòu)造最優(yōu)解。貪心算法的核心是在所選擇的策略中，選一個(gè)權(quán)值最優(yōu)的策略作為 當(dāng)前策略。 在排課系統(tǒng)中， 貪心算法是從排課問題的某一初始狀態(tài)出發(fā)．依據(jù)給出的貪心策略朝最終排好全部課程這個(gè)目標(biāo)前進(jìn)一步，判斷是否可以求出可行解的一個(gè)解元素．如果可以則繼續(xù)依據(jù)貪心策略向給定目標(biāo)前進(jìn)．求出下一個(gè)解元素。最后由所有得到的解元素組成問題的一個(gè)可行解。 貪心算法的缺點(diǎn)在于解的效果比較差．而最大優(yōu)勢在于極低的時(shí)間復(fù)雜度。它具有不可后撤性，可以有后效性．一般情況下不滿足最優(yōu)化原理。為了盡量減小貪心算法帶來的副作用?？梢栽谒惴ūM可能多的地方使用有效的最優(yōu)化算法 (如動態(tài)規(guī)劃 )。 回溯算法 回溯算法也叫試探法．它是一種系統(tǒng)地搜索問題的解的方法，可以被認(rèn)為是一個(gè)有過剪枝的 DFS(深度優(yōu)先搜索 )過程。就退回一步重新選擇。具體到計(jì)算機(jī)智 能排課系統(tǒng)中，選優(yōu)條件即為排課數(shù)學(xué)模型中的約束條件群 (需求集中的元素特征與資源集中的元素特征相互作用形成的數(shù)學(xué)關(guān)系 )若不滿足約束條件群，該選擇即為不優(yōu)或達(dá)不到目標(biāo) 當(dāng)遍歷該步驟的所有可能仍未滿足約束條件群．則該狀態(tài)滿足了回溯條件，該狀態(tài)點(diǎn)即為回溯點(diǎn)。 ①設(shè)置初始化的方案 (給變量賦初值，讀入已知數(shù)據(jù)等 )； ②變換方式去試探。 回溯法適用于解的組合數(shù)相當(dāng)大但仍然有限的那一類問題。在搜索期間的任何時(shí)刻．僅保留從開始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑。這個(gè)特性非常重要．因?yàn)榻饪臻g的大小通常是最長路徑長度的指數(shù)或階乘。再多的空間也不夠用。最好是和其它的算法結(jié)合使用 。 遺傳算法 是從代表問題可能潛在的解集的一個(gè)種群（ population）開始的，而一個(gè)種群則由經(jīng)過基因（ gene）編碼的一定數(shù)目的個(gè)體 (individual)組成。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)， 如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)畢業(yè)設(shè)計(jì)論文 6 生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（ generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度（ fitness）大小挑選（ selection）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（ geic operators）進(jìn)行組合交叉（ crossover）和變異（ mutation），產(chǎn)生出代表新的 解集的種群。 遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比，主要有以下特點(diǎn)： 遺傳算法以決策變量的編碼作為運(yùn)算對象。 遺傳算法 直接以適應(yīng)度作為搜索信息，無需導(dǎo)數(shù)等其它輔助信息。 遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。 具體應(yīng)用方式將在后面設(shè)計(jì)部分詳細(xì)說明。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不但它的應(yīng)用領(lǐng)域擴(kuò)大，而且利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高，同時(shí)產(chǎn)業(yè)應(yīng)用方面的研究也在摸索之中 。遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解擴(kuò)展到了許多更新、更工程化的應(yīng)用方面。這一新的學(xué)習(xí)機(jī)制對于解決人工智能中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。第一章 緒論 7 三是并行處理的遺傳算法的研究十分活躍。四是遺傳算法和另一個(gè)稱為人工生命