基于遺傳算法的自動(dòng)排課系統(tǒng)畢業(yè)設(shè)計(jì)

1、.摘要隨著科學(xué)技術(shù)和社會(huì)信息技術(shù)的不斷提高，計(jì)算機(jī)科學(xué)的日漸成熟，其強(qiáng)大的功能已為人們深刻認(rèn)識(shí)，它在人類社會(huì)的各個(gè)領(lǐng)域發(fā)揮著越來越重要的作用，給人們的生活帶來了極大的便利，成為推動(dòng)社會(huì)發(fā)展的首要技術(shù)動(dòng)力。排課是學(xué)校教學(xué)管理中十分重要、又相當(dāng)復(fù)雜的工作之一。解決好教學(xué)工作中的排課問題對(duì)整個(gè)教學(xué)計(jì)劃的進(jìn)行，有著十分重要的意義。首先對(duì)排課的已有算法作了相關(guān)的調(diào)查研究，決定采用遺傳算法。通過設(shè)計(jì)實(shí)現(xiàn)基于遺傳算法的自動(dòng)排課系統(tǒng)，研究了遺傳算法在排課系統(tǒng)中的應(yīng)用。關(guān)鍵詞：遺傳算法、自動(dòng)排課、Java。. v.AbstractAlong with science technical and communit

2、y 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 arrangemen

3、t is an important and complicated working in school,so solving the problem is of great importance for teaching programming.Investigated and studied the algorithm existed, determine that adoptgenetic algorithm. ThroughDesign Implementation theAuto CourseArrangementManagement System Base onGenetic Alg

4、orithm, researched the application of genetic algorithmin theCourseArrangementManagement System.Keywords: Genetic Algorithm Auto Course Arrangement ManagementJava. v.第一章 緒論1.1排課系統(tǒng)研究背景排課是學(xué)校教學(xué)管理中十分重要、又相當(dāng)復(fù)雜的管理工作之一，其實(shí)質(zhì)就是為學(xué)校所設(shè)置的課程安排時(shí)間和地點(diǎn)，從而使整個(gè)教學(xué)能夠有計(jì)劃有秩序的進(jìn)行。迄今為止，對(duì)課程表的研究工作已經(jīng)進(jìn)行了長達(dá)四十多年之久，取得了豐碩的成果。但是，仍然存在許多不足

5、之處，例如規(guī)模大、約束(條件)復(fù)雜以及規(guī)律不斷變化等，因此課程表問題至今仍未完全解決。課程表的編排是一個(gè)涉及多種因素的組合規(guī)劃問題，它要保證在課程安排中教師、學(xué)生、教室不能產(chǎn)生沖突(所謂沖突，就是將需上不同課程的兩個(gè)或多個(gè)班安排在了同一時(shí)間、同一教室，或?yàn)橥唤處熢谕粫r(shí)間段安排了多門課程等情況)，并且要滿足教師的要求和資源限制等約束條件。目前，國內(nèi)的大部分學(xué)校仍然采用手工排課的方法。手工排課工作的主要手段是“擺牌”，就是在一個(gè)畫有空課表的版面上將有課名的小牌擺在適當(dāng)?shù)奈恢蒙?，邊擺邊觀察，邊調(diào)整，憑借經(jīng)驗(yàn)將各門課擺在合理的位置上，最后形成一個(gè)有效的課程表。這種辦法沒有一定的規(guī)律，沒有理論指導(dǎo)，

6、更沒有數(shù)據(jù)模型，具有很大的盲目性。所以，要為上千名學(xué)生和上百名教師安排出合理的課程表，往往需要花費(fèi)教務(wù)處人員很多的時(shí)間，工作量大，排出的課程表不宜調(diào)整。隨著中國教育體制改革的不斷深入，學(xué)生人數(shù)的不斷上升，課程設(shè)置不斷向深度和廣度發(fā)展，手工排課的缺點(diǎn)就越來越突出。由于計(jì)算機(jī)具有運(yùn)算速度快、處理能力強(qiáng)等特點(diǎn)，很自然地就進(jìn)入到這一應(yīng)用領(lǐng)域中。用計(jì)算機(jī)進(jìn)行排課能夠快速地得到滿足約束條件的可行結(jié)果，具有排課時(shí)間短、省人力和質(zhì)量高的優(yōu)點(diǎn)，不但能使教務(wù)人員從繁雜的排課任務(wù)中解脫出來，而且對(duì)于推動(dòng)教學(xué)的發(fā)展也起到非常重要的作用。每個(gè)學(xué)期開學(xué)時(shí)，教務(wù)管理工作中的課程表安排問題，都是教務(wù)處面臨的一項(xiàng)艱巨任務(wù)。排課

7、問題是一個(gè)非常棘手卻又亟待解決的問題，通常都是使用傳統(tǒng)的人工手動(dòng)排課方法。手工排課不僅勞動(dòng)強(qiáng)度大，而且排課效率低，很難排出一個(gè)讓人滿意的課程表。時(shí)間，教師，教室，班級(jí)，課程等限制問題更是難以解決，使用計(jì)算機(jī)進(jìn)行自動(dòng)排課已經(jīng)成為近年來的熱點(diǎn)話題。教學(xué)管理的信息化需要計(jì)算機(jī)輔助排課，而排課理論的研究和軟件技術(shù)的成熟己為我們提供了計(jì)算機(jī)自動(dòng)排課的重要手段，研究一種準(zhǔn)確、高效、實(shí)用、自動(dòng)化程度高的排課系統(tǒng)己經(jīng)成為可能。1.2排課系統(tǒng)國內(nèi)外現(xiàn)狀排課問題是NP完全問題，許多學(xué)者分別在理論、啟發(fā)式搜索技術(shù)應(yīng)用求解、專家系統(tǒng)應(yīng)用求解和遺傳算法應(yīng)用求解上作了很多研究。國外從20世紀(jì)50年代末就對(duì)排課問題展開了研

8、究。1963年Gotlieb在他的文章中提出了排課問題的數(shù)學(xué)模型2，它標(biāo)志著排課問題的研究正式跨越了科學(xué)的殿堂。之后，人們對(duì)排課問題的算法做了許多探索，但由于排課問題是NP完全問題，并且易受實(shí)際問題邊界的影響，大多數(shù)求解結(jié)果都不夠理想。Ferland3等人和吳金榮4把排課問題化成整數(shù)規(guī)劃來解決，但計(jì)算量很大，其僅僅適用于規(guī)模很小的課表編排，對(duì)于大規(guī)模復(fù)雜的排課情況，至今沒有一個(gè)切實(shí)可行的算法;何永太5和胡順仁6等人試圖用圖論中的染色問題來求解排課問題，可惜圖的染色問題本身也是NP完全問題。由于問題的復(fù)雜，許多文章利用啟發(fā)式函數(shù)來解決排課問題，大多數(shù)啟發(fā)方法都是模擬手工排課的過程來實(shí)現(xiàn)的。由于實(shí)

9、際的排課問題存在各種各樣的限制條件與特殊要求，對(duì)這些因素處理的好壞就顯得尤為重要。進(jìn)入20世紀(jì)90年代，國外對(duì)排課問題的研究仍然非?；钴S。如印度Vastapur大學(xué)管理學(xué)院的Arabinda Tripathy、加拿大Montreal大學(xué)的Jean Aubin和JacqueSA Ferland以及Charles Fleutent等。Arabinda Tripathy的工作是針對(duì)以“人”為單位進(jìn)行課表編排的。他運(yùn)用拉格朗日松弛法和分支定界技術(shù)求解，這種方法的缺點(diǎn)是為了減少變量的個(gè)數(shù)，人為造成科目間的沖突。A.Tripathy還研究了研究生課表編排問題，他采用多重課組的方法來處理沖突(即根據(jù)學(xué)生選課

10、的矛盾情況，將人數(shù)多的課程在一星期內(nèi)開多次)。JacQuesA.Ferland等人則把排課問題分成兩個(gè)子問題:時(shí)間表問題和分組問題。在時(shí)間表問題中，根據(jù)學(xué)生注冊(cè)情況、教師和教室的可利用情況形成一個(gè)主時(shí)間表。對(duì)于選課人數(shù)較多的大課，一個(gè)星期要分成幾個(gè)時(shí)間段來上，分組問題就是將學(xué)生分給各時(shí)間段。兩個(gè)問題相關(guān)聯(lián)，通過懲罰因子來構(gòu)造啟發(fā)函數(shù)。他們研制的SAPHIR課程調(diào)度決策支持系統(tǒng)分為數(shù)據(jù)處理、自動(dòng)優(yōu)化、交互優(yōu)化等幾個(gè)模塊。該系統(tǒng)解決矛盾的主要方法也是采用多重課組。在國內(nèi)，對(duì)于排課系統(tǒng)的研發(fā)，林漳希和林堯瑞1984年發(fā)表了該課題上的實(shí)驗(yàn)性研究成果。成形的系統(tǒng)有大連理工大學(xué)1998年推出的教學(xué)調(diào)度系統(tǒng)

11、版本3.00和由清華大學(xué)計(jì)算機(jī)與信息管理中心開發(fā)的綜合教務(wù)管理系統(tǒng)TISER。這些應(yīng)用界面很友好的排課軟件己經(jīng)可以幫助排課人員大大提高工作效率。這些系統(tǒng)大多數(shù)都是模擬手工排課，以“班”為單位，只能在排課過程中輔助工作人員進(jìn)行排課，并沒有一套完善有效的自動(dòng)排課算法。當(dāng)人工輸入的條件達(dá)到一定的限制程度時(shí)，軟件運(yùn)行就有可能出現(xiàn)死鎖現(xiàn)象，使得系統(tǒng)的實(shí)際應(yīng)用非常困難19。后期人工調(diào)整的工作量并不比重新排課的工作量小很多。一旦出現(xiàn)了這種現(xiàn)象，就要把所有的數(shù)據(jù)作廢或者打亂重排，之前做的工作都付諸東流。高校的課程、教室、教師等因素都十分復(fù)雜，排課所需數(shù)據(jù)量也十分龐大，所以造成的時(shí)間、人力損失也非常巨大。課程表

12、問題又稱時(shí)間表問題，是一個(gè)多因素的優(yōu)化決策問題，也是組合規(guī)劃中的典型問題，是NP完全的1。對(duì)于排課問題的解決，研究人員己經(jīng)使用了各種不同的算法，但由于該問題的復(fù)雜性，所求解也只能是較為合理、較為滿意的解。隨著人工智能的發(fā)展，特別是在計(jì)算智能領(lǐng)域的拓展，借鑒于生物界進(jìn)化思想和遺傳算法，由于其超強(qiáng)的并行搜索能力，以及在解決優(yōu)化問題中表現(xiàn)出來的高度魯棒性，它已經(jīng)被廣泛應(yīng)用于各個(gè)領(lǐng)域。目前，很多研究人員已使用遺傳算法來求解排課問題，如文獻(xiàn)20使用遺傳算法優(yōu)化教室的合理利用，文獻(xiàn)21的用自適應(yīng)的遺傳算法求解大學(xué)課表安排問題，文獻(xiàn)22的基于遺傳算法排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)等等。這些應(yīng)用說明，使用遺傳算法來解決

13、排課問題，其結(jié)果還是令人較為滿意的。教學(xué)排課問題是學(xué)校每個(gè)排課人員最頭痛的問題。短時(shí)間內(nèi)沒有一個(gè)方法來達(dá)到學(xué)校教師滿意的結(jié)果。其最大的困難是硬件資源的限制。排課人員在硬件資源兼顧的條件下難于短時(shí)間內(nèi)排出教師滿意的課表?！案F舉法”可將所有的方式列出然后找出最佳解，但成本太高，時(shí)間太長。如一個(gè)星期有n個(gè)時(shí)段可排課，有m位教師需要參與排課平均每位教師一個(gè)星期要上i堂課。其排課的組合數(shù)有nm*i次?？梢姼F舉法的復(fù)雜度有多高。遺傳算法是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。本文試圖以遺傳算法來實(shí)現(xiàn)排課問題的最佳解。本課題研究的目的就是實(shí)現(xiàn)基于遺傳算法的排課系統(tǒng)，并在VB下具體實(shí)現(xiàn)，滿足日常需求。1.

14、3排課常用算法比較1.3.1貪心算法貪心法(greedy method)是一種改進(jìn)了的分級(jí)處理方法，逐步構(gòu)造最優(yōu)解。它從問題的某一個(gè)初始解出發(fā)，在一定的標(biāo)準(zhǔn)下做出一系列的貪心選擇(選擇一旦做出，就不可再更改)，即當(dāng)前狀態(tài)下看上去最優(yōu)的選擇逐步逼近給定的目標(biāo)以盡可能快的速度求得更好的解當(dāng)達(dá)到算法中的某一步不能再繼續(xù)前進(jìn)時(shí)則停止。貪心算法的核心是在所選擇的策略中，選一個(gè)權(quán)值最優(yōu)的策略作為當(dāng)前策略。因此貪心算法的好壞主要決定于權(quán)值的確定。在排課系統(tǒng)中，貪心算法是從排課問題的某一初始狀態(tài)出發(fā)依據(jù)給出的貪心策略朝最終排好全部課程這個(gè)目標(biāo)前進(jìn)一步，判斷是否可以求出可行解的一個(gè)解元素如果可以則繼續(xù)依據(jù)貪心策

15、略向給定目標(biāo)前進(jìn)求出下一個(gè)解元素。直到前進(jìn)不能再繼續(xù)時(shí)停止。最后由所有得到的解元素組成問題的一個(gè)可行解。此時(shí)算法結(jié)束。貪心算法的缺點(diǎn)在于解的效果比較差而最大優(yōu)勢(shì)在于極低的時(shí)間復(fù)雜度。能做到某種意義上的局部最優(yōu)。它具有不可后撤性，可以有后效性一般情況下不滿足最優(yōu)化原理。并且不適用于解決可行性問題僅適用于較容易得到可行解的最優(yōu)性問題。為了盡量減小貪心算法帶來的副作用。使得最后得到的解更接近最優(yōu)解?？梢栽谒惴ūM可能多的地方使用有效的最優(yōu)化算法(如動(dòng)態(tài)規(guī)劃)。貪心算法還可以為搜索算法提供較優(yōu)的初始界值。1.3.2回溯算法回溯算法也叫試探法它是一種系統(tǒng)地搜索問題的解的方法，可以被認(rèn)為是一個(gè)有過剪枝的DF

16、S(深度優(yōu)先搜索)過程。它按優(yōu)先條件向前搜索，以達(dá)到目標(biāo)，但當(dāng)搜索到某一步時(shí)發(fā)現(xiàn)原先的選擇并不優(yōu)或達(dá)不到目標(biāo)。就退回一步重新選擇。而滿足回溯條件的某個(gè)狀態(tài)點(diǎn)稱之為回溯點(diǎn)。具體到計(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)?；厮菟惴ń鉀Q排課問題時(shí)首先要描述解的形式，定義一個(gè)解空間它包含問題的所有解：其次構(gòu)造狀態(tài)空間樹，這棵樹的每條完整路徑都代表了一種解的可能：再次是構(gòu)造約束函數(shù)，通過描述合法

17、解的一般特征用于去除不合法的解，從而避免繼續(xù)搜索出這個(gè)不合法解的剩余部分：然后通過深度優(yōu)先搜索完成回溯。設(shè)置初始化的方案(給變量賦初值，讀入已知數(shù)據(jù)等)；變換方式去試探。若全部試完則轉(zhuǎn)；判斷此法是否成功(通過約束函數(shù))，不成功則轉(zhuǎn)；試探成功則前進(jìn)一步再試探；正確方案還未找到則轉(zhuǎn)；已找到一種方案則記錄并打??；退回一步(回溯)，若未退到根則轉(zhuǎn)；已退到根節(jié)點(diǎn)則排課結(jié)束或打印無排課結(jié)果?；厮莘ㄟm用于解的組合數(shù)相當(dāng)大但仍然有限的那一類問題。它的一個(gè)有重要的特性是在搜索執(zhí)行的同時(shí)產(chǎn)生解空問。在搜索期間的任何時(shí)刻僅保留從開始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑。因此回溯算法的空間需求為一個(gè)常數(shù)，即從開始節(jié)點(diǎn)起最長路徑的長度

18、。這個(gè)特性非常重要因?yàn)榻饪臻g的大小通常是最長路徑長度的指數(shù)或階乘。所以如果要存儲(chǔ)全部解空間的話。再多的空間也不夠用。其缺點(diǎn)是時(shí)間復(fù)雜度較大因此在采用時(shí)還需要謹(jǐn)慎。最好是和其它的算法結(jié)合使用。1.3.3遺傳算法遺傳算法是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，它是有美國Michigan大學(xué)J.Holland教授于1975年首先提出來的，并出版了頗有影響的專著Adaptation in Natural and Artificial Systems，GA這個(gè)名稱才逐漸為人所知，J.Hilland教授所提出的GA通常為簡單遺傳算法（SGA）。

19、遺傳算法是從代表問題可能潛在的解集的一個(gè)種群（population）開始的，而一個(gè)種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個(gè)體(individual)組成。每個(gè)個(gè)體實(shí)際上是染色體(chromosome)帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生

20、出越來越好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度（fitness）大小挑選（selection）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（geneticoperators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解。遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化的具有魯棒性的搜索算法，與傳統(tǒng)的優(yōu)化算法相比，主要有以下特點(diǎn)：1、遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象。傳統(tǒng)的優(yōu)化算法往往直接決策變量的實(shí)際植本身，而遺傳算法處理決策變

21、量的某種編碼形式，使得我們可以借鑒生物學(xué)中的染色體和基因的概念，可以模仿自然界生物的遺傳和進(jìn)化機(jī)理，也使得我們能夠方便的應(yīng)用遺傳操作算子。2、遺傳算法直接以適應(yīng)度作為搜索信息，無需導(dǎo)數(shù)等其它輔助信息。3、 遺傳算法使用多個(gè)點(diǎn)的搜索信息，具有隱含并行性。4、遺傳算法使用概率搜索技術(shù)，而非確定性規(guī)則。根據(jù)其算法特點(diǎn)，遺傳算法非常適合于應(yīng)用到排課處理中。具體應(yīng)用方式將在后面設(shè)計(jì)部分詳細(xì)說明。1.4遺傳算法國內(nèi)外現(xiàn)狀進(jìn)入90年代，遺傳算法迎來了興盛發(fā)展時(shí)期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不但它的應(yīng)用領(lǐng)域擴(kuò)大，而且利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)的能

22、力也顯著提高，同時(shí)產(chǎn)業(yè)應(yīng)用方面的研究也在摸索之中。此外一些新的理論和方法在應(yīng)用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳算法增添了新的活力。遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解擴(kuò)展到了許多更新、更工程化的應(yīng)用方面。隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個(gè)引人注目的新動(dòng)向：一是基于遺傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法。這一新的學(xué)習(xí)機(jī)制對(duì)于解決人工智能中知識(shí)獲取和知識(shí)優(yōu)化精煉的瓶頸難題帶來了希望。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)、模糊推理以及混沌理論等其它智能計(jì)算方法相互滲透和結(jié)合，這對(duì)開拓21世紀(jì)中新

23、的智能計(jì)算技術(shù)將具有重要的意義。三是并行處理的遺傳算法的研究十分活躍。這一研究不僅對(duì)遺傳算法本身的發(fā)展，而且對(duì)于新一代智能計(jì)算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。四是遺傳算法和另一個(gè)稱為人工生命的嶄新研究領(lǐng)域正不斷滲透。所謂人工生命即是用計(jì)算機(jī)模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進(jìn)化和免疫等現(xiàn)象是人工生命的重要研究對(duì)象，而遺傳算法在這方面將會(huì)發(fā)揮一定的作用，五是遺傳算法和進(jìn)化規(guī)劃（Evolution Programming,EP）以及進(jìn)化策略（Evolution Strategy,ES）等進(jìn)化計(jì)算理論日益結(jié)合。EP和ES幾乎是和遺傳算法同時(shí)獨(dú)立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自

24、然界生物進(jìn)化機(jī)制的智能計(jì)算方法，即同遺傳算法具有相同之處，也有各自的特點(diǎn)。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。1991年D.Whitey在他的論文中提出了基于領(lǐng)域交叉的交叉算子（Adjacency based crossover），這個(gè)算子是特別針對(duì)用序號(hào)表示基因的個(gè)體的交叉，并將其應(yīng)用到了TSP問題中，通過實(shí)驗(yàn)對(duì)其進(jìn)行了驗(yàn)證。D.H.Ackley等提出了隨即迭代遺傳爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一種復(fù)雜的概率選舉機(jī)制，此機(jī)制中由m個(gè)“投票者”來共同決定新個(gè)體的值（m表示群體的大?。?。實(shí)驗(yàn)結(jié)果表明，

25、SIGH與單點(diǎn)交叉、均勻交叉的神經(jīng)遺傳算法相比，所測(cè)試的六個(gè)函數(shù)中有四個(gè)表現(xiàn)出更好的性能，而且總體來講，SIGH比現(xiàn)存的許多算法在求解速度方面更有競爭力。H.Bersini和G.Seront將遺傳算法與單一方法（simplex method）結(jié)合起來，形成了一種叫單一操作的多親交叉算子（simplex crossover），該算子在根據(jù)兩個(gè)母體以及一個(gè)額外的個(gè)體產(chǎn)生新個(gè)體，事實(shí)上他的交叉結(jié)果與對(duì)三個(gè)個(gè)體用選舉交叉產(chǎn)生的結(jié)果一致。同時(shí)，文獻(xiàn)還將三者交叉算子與點(diǎn)交叉、均勻交叉做了比較，結(jié)果表明，三者交叉算子比其余兩個(gè)有更好的性能。國內(nèi)也有不少的專家和學(xué)者對(duì)遺傳算法的交叉算子進(jìn)行改進(jìn)。2002年，戴

26、曉明等應(yīng)用多種群遺傳并行進(jìn)化的思想，對(duì)不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進(jìn)行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問題。2004年，趙宏立等針對(duì)簡單遺傳算法在較大規(guī)模組合優(yōu)化問題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法（Building-block Coded Parallel GA，BCPGA）。該方法以粗粒度并行遺傳算法為基本框架，在染色體群體中識(shí)別出可能的基因塊，然后用基因塊作為新的基因單位對(duì)染色體重新編碼，產(chǎn)生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。2005年

27、，江雷等針對(duì)并行遺傳算法求解TSP問題,探討了使用彈性策略來維持群體的多樣性,使得算法跨過局部收斂的障礙,向全局最優(yōu)解方向進(jìn)化。1.5研究目標(biāo)及內(nèi)容1.5.1研究目標(biāo)對(duì)遺傳算法進(jìn)行研究，進(jìn)而將其應(yīng)用到排課系統(tǒng)中，利用計(jì)算機(jī)來模擬手工排課工作，可以抽象問題中的各個(gè)要素，數(shù)學(xué)表達(dá)各種約束條件，并根據(jù)課表的組織形式和普遍存在的規(guī)律，縮減了問題空間的搜索范圍，有效組織了排課知識(shí)，使其在一定程度上呈現(xiàn)智能化。1.5.2研究內(nèi)容學(xué)校排課問題本質(zhì)上是時(shí)間表問題的一類典型應(yīng)用實(shí)例，是為了解決課程安排對(duì)時(shí)間和空間資源的有效利用并避免相互沖突。在排課過程中需要考慮課程教學(xué)效果、滿足教師特殊要求等多項(xiàng)優(yōu)化指標(biāo)，將各

28、門課程安排到相應(yīng)的時(shí)間和教室。1）排課問題具體研究的內(nèi)容如下：（1）遺傳算法的理論（2）排課問題的建模（3）遺傳算法在自動(dòng)排課中的應(yīng)用方法（4）排課算法的實(shí)現(xiàn)2）排課問題具體研究的重點(diǎn)和難點(diǎn)如下：（1）深入理解遺傳算法理論。（2）排課問題的建模，包括排課問題的要素以及排課過程的約束條件等。（3）遺傳算法在排課問題中的應(yīng)用方法，包括基因編碼、初始種群的產(chǎn)生、適應(yīng)度函數(shù)、控制參數(shù)的設(shè)定等。（4）排課問題本身的求解規(guī)模過于龐大，各要素之間的關(guān)聯(lián)層出不窮，以及人們對(duì)多個(gè)課表優(yōu)劣評(píng)定的準(zhǔn)則存在差異，在求解排課問題的過程中，會(huì)面對(duì)難以窮盡的組合和多個(gè)模糊目標(biāo)的優(yōu)化問題，實(shí)際解決時(shí)會(huì)受到一些制約。3）排課問

29、題具體研究方法如下：采用循序漸進(jìn)的方法進(jìn)行研究，首先必須要學(xué)習(xí)遺傳算法，在學(xué)習(xí)的基礎(chǔ)上進(jìn)行深入研究，對(duì)現(xiàn)行的遺傳算法進(jìn)行一些改進(jìn)，然后對(duì)排課問題進(jìn)行建模，分析排課問題的要素和約束條件。最后將遺傳算法應(yīng)用到排課系統(tǒng)中，提出一種具體的應(yīng)用方法并實(shí)現(xiàn)排課算法。研究過程中要借助于大量的文獻(xiàn)資料，必須要先學(xué)習(xí)理論，在理論的基礎(chǔ)上再進(jìn)行實(shí)踐。4）排課問題具體研究步驟如下：（1）大量閱讀關(guān)于遺傳算法的相關(guān)文獻(xiàn)，理解算法原理。（2）研究排課問題，對(duì)排課問題進(jìn)行建模。（3）對(duì)遺傳算法進(jìn)行一些改進(jìn)。（4）提出遺傳算法在自動(dòng)排課中的應(yīng)用方法。（5）進(jìn)行系統(tǒng)的概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)。（6）編碼實(shí)現(xiàn)排課算法。（7）對(duì)系統(tǒng)進(jìn)

30、行測(cè)試和運(yùn)行。（8）對(duì)系統(tǒng)進(jìn)行回歸測(cè)試和功能完善。5）排課問題研究用到的工具與框架如下：（1）MyEclipse6.0；（2）開發(fā)的環(huán)境：JDK1.5；（3）UML建模工具：PowerDesigner12.5；（4）MS SQL Server 2000；1.5.3研究意義排課系統(tǒng)是教學(xué)管理系統(tǒng)中的一項(xiàng)重要內(nèi)容，排課結(jié)果的優(yōu)劣直接影響到學(xué)校的正常教學(xué)秩序，甚至影響教學(xué)質(zhì)量。排課管理的主要任務(wù)是把全校各年級(jí)所開設(shè)的課程進(jìn)行匯總，然后根據(jù)教學(xué)計(jì)劃和教學(xué)資源制訂全校各班級(jí)的課程表，優(yōu)化配置各種教學(xué)資源，使教學(xué)工作科學(xué)、高效順利的進(jìn)行。研究的意義就在于設(shè)計(jì)一個(gè)好的智能排課系統(tǒng)，從而減輕了教學(xué)管理工作者的

31、勞動(dòng)強(qiáng)度，提高了工作效率，規(guī)范了教學(xué)管理工作流程。. v.第二章 相關(guān)技術(shù)基礎(chǔ)本章介紹開發(fā)中用到的相關(guān)技術(shù)。2.1MyEclipse Enterprise Workbench 介紹MyEclipse企業(yè)級(jí)工作平臺(tái)（MyEclipseEnterprise Workbench ，簡稱MyEclipse）是對(duì)Eclipse IDE的擴(kuò)展，利用它我們可以在數(shù)據(jù)庫和JavaEE的開發(fā)、發(fā)布，以及應(yīng)用程序服務(wù)器的整合方面極大的提高工作效率。它是功能豐富的JavaEE集成開發(fā)環(huán)境，包括了完備的編碼、調(diào)試、測(cè)試和發(fā)布功能，完整支持HTML, Struts, JSF, CSS, JavaScript, SQL,

32、 Hibernate。Eclipse是著名的跨平臺(tái)的自由集成開發(fā)環(huán)境（IDE）。最初主要用來Java語言開發(fā)，但是目前亦有人通過插件使其作為其他計(jì)算機(jī)語言比如C+和Python的開發(fā)工具。Eclipse的本身只是一個(gè)框架平臺(tái)，但是眾多插件的支持使得Eclipse擁有其他功能相對(duì)固定的IDE軟件很難具有的靈活性。許多軟件開發(fā)商以Eclipse為框架開發(fā)自己的IDE。Eclipse 最初由OTI和IBM兩家公司的IDE產(chǎn)品開發(fā)組創(chuàng)建，起始于1999年4月。IBM提供了最初的Eclipse代碼基礎(chǔ)，包括Platform、JDT 和PDE。目前由IBM牽頭，圍繞著Eclipse項(xiàng)目已經(jīng)發(fā)展成為了一個(gè)龐

33、大的Eclipse聯(lián)盟，有150多家軟件公司參與到Eclipse項(xiàng)目中，其中包括Borland、Rational Software、Red Hat及Sybase等。Eclipse是一個(gè)開發(fā)源碼項(xiàng)目，它其實(shí)是 Visual Age for Java的替代品，其界面跟先前的Visual Age for Java差不多，但由于其開放源碼，任何人都可以免費(fèi)得到，并可以在此基礎(chǔ)上開發(fā)各自的插件，因此越來越受人們關(guān)注。近期還有包括Oracle在內(nèi)的許多大公司也紛紛加入了該項(xiàng)目，并宣稱Eclipse將來能成為可進(jìn)行任何語言開發(fā)的IDE集大成者，使用者只需下載各種語言的插件即可。2.2.1 Eclipse開發(fā)

34、環(huán)境Eclipse開發(fā)環(huán)境被稱為Workbench，它主要由三個(gè)部分組成:透視圖(Perspective)、編輯窗口(Editor)和視圖(View)15。所有文件的顯示和編輯都包含在編輯窗口里。默認(rèn)情況下打開的多個(gè)文件是以標(biāo)簽(Tag)方式在同一個(gè)窗口中排列的。視圖是配合編輯窗口并提供了多種相關(guān)信息和瀏覽方式。視圖是任何IDE開發(fā)環(huán)境的核心，用好視圖也就是用好工DE開發(fā)環(huán)境。透視圖可以自定義每個(gè)視圖中包含的視圖種類，也可自定義一個(gè)新透視圖。一個(gè)透視圖包括一個(gè)或多個(gè)編輯窗口和視圖。2.2.2Eclipse的主要特點(diǎn)Eclipse的主要特點(diǎn)有以下幾方面:(l)開放的可擴(kuò)展的IDEEclipse平

35、臺(tái)是一個(gè)開放的可擴(kuò)展的功E。Eclipse平臺(tái)是建造模塊和構(gòu)造并運(yùn)行集成軟件開發(fā)工具的基礎(chǔ)。Eclipse平臺(tái)允許工具建造者獨(dú)立開發(fā)與其它工具無縫集成的工具，用戶甚至無須去分辨一個(gè)工具功能在哪里結(jié)束，而另一個(gè)工具功能在哪里開始。(2)成功的底層圖形界面從Java誕生至今，己經(jīng)在太多的領(lǐng)域取得成功，然而它卻很少在圖形接口程序上嶄露頭角。究其原因，Java語言缺省的圖形接口開發(fā)包AWT和SWING實(shí)在是難辭其咎，無論速度和外觀，它們都難以讓人接受。如今，E。 1ipse組織編寫的SWT開發(fā)包，為Java程序員提供了AWT和SWING之外的一個(gè)更好的選擇。SWT本身僅僅是Eclipse組織為了開發(fā)E

36、clipse集成開發(fā)環(huán)境所編寫的一組底層圖形接口API?；蛟S是無心插柳，又或是有意為之。至今為止，SWT無論是在性能和外觀上，都超越了Sun公司提供的AWT和SWING。目前， EclipseIDE版本已經(jīng)開發(fā)到了3.2版本，SWT已經(jīng)十分穩(wěn)定。這里穩(wěn)定包含兩層意思:指性能上的穩(wěn)定，其中的關(guān)鍵是源于SWT的設(shè)計(jì)理念。SWT最大化了操作系統(tǒng)的圖形構(gòu)API，就是說，只要操作系統(tǒng)提供了相應(yīng)圖形的構(gòu)件，SWT才自己去做一個(gè)模擬的實(shí)現(xiàn)。可以看出S盯性能上的穩(wěn)定大多時(shí)候取決于相應(yīng)操作系統(tǒng)圖形構(gòu)件的穩(wěn)定性。指 SWTAPI包中的類，方法的名稱和結(jié)構(gòu)已經(jīng)少有改變，程序員不用擔(dān)心由于Eclipse組織開發(fā)進(jìn)度過

37、快(EclipseIDE每天都會(huì)發(fā)布一個(gè)Nightly版本)，而導(dǎo)致自己的程序代碼變化過大。從一個(gè)版本的SWT更新至另一個(gè)版本，通常只是需要簡單將SWT包換掉就可以了。(3)強(qiáng)大的插件加載功能可以通過不斷地加載插件來實(shí)現(xiàn)同其它產(chǎn)品的合作。整個(gè)E。 1ipse體系結(jié)構(gòu)就像一個(gè)大拼圖，可以不斷地向上加插件，同時(shí)，現(xiàn)有插件上還可以再加插件，進(jìn)而實(shí)現(xiàn)功能的擴(kuò)展。目前，Eclipse已經(jīng)開始提供C語言開發(fā)的功能插件。更難能可貴的是，Eclipse是一個(gè)開放源代碼的項(xiàng)目，任何人都可以下載Eclipse的源代碼，并且在此基礎(chǔ)上開發(fā)自己的功能插件。也就是說，只要有人需要，就會(huì)有建立在Eclipse。之上的CO

38、BOL、Perl、Python等語言的開發(fā)插件出現(xiàn)。同時(shí)可以通過開發(fā)新的插件擴(kuò)展現(xiàn)有插件的功能，例如在現(xiàn)有的Java開發(fā)環(huán)境中加入Tomcat服務(wù)器插件。Ec11spe插件可以無限擴(kuò)展，而且有著統(tǒng)一的外觀、操作和系統(tǒng)資源管理，這也是Ec11pse的潛力所在。(4)可以通過導(dǎo)入一些CVS相關(guān)的插件來實(shí)現(xiàn)版本管理控制的便宜性Eclipse平臺(tái)提供了對(duì)于直接從工作區(qū)進(jìn)行團(tuán)隊(duì)開發(fā)操作的支持。這種支持允許開發(fā)人員并發(fā)地與幾個(gè)獨(dú)立的資源庫以及不同版本的代碼或項(xiàng)目進(jìn)行交互。工作區(qū)中的資源允許團(tuán)隊(duì)支持組件處理版本和配置管理問題。當(dāng)然，單個(gè)工作區(qū)也可以同時(shí)訪問不同類型的資源庫。Eclipse平臺(tái)并沒有提供它自己

39、的代碼管理解決方案，它總是依靠外部系統(tǒng)。E1ipse平臺(tái)只對(duì)一個(gè)源代碼管理系統(tǒng)提供內(nèi)置支持一一并發(fā)版本控制系統(tǒng)CVS。(5)充分的幫助文檔值得提出的還有，在下載了Eclipse的多國語言翻譯包之后，所有的菜單和聯(lián)機(jī)幫助文檔都己經(jīng)翻譯成了中文，使用起來比較方便。2.2 SQL Server 2005Microsoft SQL Server 2005是軟件開發(fā)中使用非常廣泛的數(shù)據(jù)庫管理系統(tǒng)，它是由美利堅(jiān)合眾國的微軟公司開發(fā)并推出的數(shù)據(jù)庫開發(fā)、管理系統(tǒng)。它是由一系列的圖形工具整合在一起構(gòu)成的，這些圖形工具主要有服務(wù)器管理、企業(yè)管理器和查詢分析器。服務(wù)器管理的主要功能是啟動(dòng)和關(guān)閉數(shù)據(jù)庫服務(wù)。企業(yè)管理器

40、的主要功能是創(chuàng)建、修改和備份數(shù)據(jù)庫。查詢分析器的主要功能是交互執(zhí)行標(biāo)準(zhǔn)T-SQL語句、SQL函數(shù)和存儲(chǔ)過程，而且具有圖形化的查詢分析功能。SQL Server 2005作為一款數(shù)據(jù)庫開發(fā)與分析的軟件，能夠方便快捷的為可伸縮性的電子商務(wù)、企業(yè)ERP和數(shù)據(jù)倉庫等創(chuàng)建出優(yōu)秀的解決方案。在SQL SERVER的2005版出現(xiàn)時(shí)，Internet網(wǎng)絡(luò)已興起，所以它為網(wǎng)絡(luò)應(yīng)用程序的開發(fā)和設(shè)計(jì)做了很多工作，能很好的適應(yīng)網(wǎng)路應(yīng)用程序的數(shù)據(jù)管理和數(shù)據(jù)分析。在開發(fā)電子商務(wù)、數(shù)據(jù)倉庫應(yīng)用時(shí)，如果采用由SQL SERVER 2005作為核心組件之一的Windows DNA（Distributed Internet A

41、rchitecture）架構(gòu)，能夠使得整個(gè)應(yīng)用的開發(fā)周期大大縮短。另外，SQL SERVER 2005全方位支持HTTP和XML(Extensible Markup Language)擴(kuò)展標(biāo)示語言。SQL Server 2005具有著性能高和企業(yè)級(jí)可伸縮性的特點(diǎn)。SQL Server 2005安裝部署與Windows NT操作系統(tǒng)之上，與操作系統(tǒng)一起提供了對(duì)多處理器、大內(nèi)存和64位硬件平臺(tái)的支持。而且SQL Server 2005還支持WindowsNT的多路群集，為較大規(guī)模的應(yīng)用提供了良好的支持。在可管理性和易用性方面，SQL Server的上一個(gè)版本7.0在行業(yè)內(nèi)就處于領(lǐng)先地位，而升級(jí)版的

42、2005不僅在可管理性和易用性方面做了大量改進(jìn)，而且在性能、擴(kuò)展性和安全性方面也做了許多改進(jìn)。SQL Server 2005能為具有商務(wù)活動(dòng)的網(wǎng)絡(luò)站點(diǎn)提供優(yōu)異的性能，具有商務(wù)活動(dòng)的網(wǎng)絡(luò)站點(diǎn)對(duì)性能、可管理性、易用性都有較高的要求，而SQL Server 2005能夠很好的做到這些。SQL Server 2005的特點(diǎn)歸納后如下：1SQL Server 2005的數(shù)據(jù)分析性能是非常高效的SQL Server 2005具有高效的數(shù)據(jù)操作機(jī)制。SQL Server 2005在處理查詢時(shí)，能夠智能優(yōu)化SQL語句，對(duì)Where條件中的多個(gè)條件進(jìn)行分析，找出最佳的過濾及交叉順序，并且可以將優(yōu)化好的SQL語句

43、緩存起來，下次再有同樣的SQL查詢時(shí)將直接使用緩存的優(yōu)化過的SQL語句。2SQL Server 2005的業(yè)務(wù)擴(kuò)展性是靈活的數(shù)據(jù)倉庫技術(shù)直接回答的是業(yè)務(wù)問題，其實(shí)現(xiàn)方式也是以解決一個(gè)個(gè)業(yè)務(wù)需求的形式組織的。隨著新業(yè)務(wù)的出 業(yè)務(wù)需求建設(shè)新的模型，這種堆疊形式的建設(shè)方式為整個(gè)系統(tǒng)隨業(yè)務(wù)的發(fā)展而平穩(wěn)發(fā)展提供了良好的條件。3 SQL Server 2005的安全性是與操作系統(tǒng)集成在一起的Microsoft SQL Server 2005的安全性是與操作系統(tǒng)集成在一起的，從而可以利用windows的強(qiáng)大功能，為數(shù)據(jù)庫用戶實(shí)現(xiàn)更高的安全性。操作系統(tǒng)提供了OLAP管理器，通過OLAP管理器強(qiáng)大而專業(yè)的管理功

44、能，實(shí)現(xiàn)對(duì)用戶權(quán)限的更為細(xì)致和專業(yè)的劃分和控制。Microsoft SQL Server 2005具有細(xì)致而全面的安全設(shè)置選項(xiàng)。數(shù)據(jù)庫用戶具有不同的級(jí)別劃分，數(shù)據(jù)庫管理員可以根據(jù)實(shí)際情況，對(duì)數(shù)據(jù)庫用戶進(jìn)行細(xì)致的級(jí)別劃分，使得數(shù)據(jù)系統(tǒng)的安全性更有保障。由高到低的級(jí)別依次為服務(wù)器級(jí)、數(shù)據(jù)庫級(jí)、多維數(shù)據(jù)集挖掘模型級(jí)、維度成員級(jí)和單元級(jí)。4SQL Server 2005的易用性SQL Server 2005的企業(yè)管理器是圖形化工具，界面顯示與操作方式都與Windows操作系統(tǒng)的類似，在當(dāng)前Windows普及的背景下，開發(fā)人員可以很快上手并熟悉，基本不用化太多時(shí)間專門的學(xué)習(xí)SQL Server 2005

45、軟件的使用。SQL Server 2005可以對(duì)工作負(fù)載進(jìn)行動(dòng)態(tài)優(yōu)化，根據(jù)最優(yōu)的參數(shù)設(shè)置進(jìn)行智能調(diào)節(jié)，從而盡可能減輕數(shù)據(jù)維護(hù)管理人員的工作量。SQL Server 2005還為開發(fā)人員提供了各種常用操作的向?qū)С绦蚣肮δ軓?qiáng)大的圖形化編輯器。向?qū)С绦蚩梢宰岄_發(fā)人員能夠在圖形化界面下，按向?qū)У牟僮魈崾局鸩酵瓿上嚓P(guān)操作，極大的方便了開發(fā)人員的使用。圖形化編輯器更是使得開發(fā)人員可以通過幾次選擇操作，就能完成本來需要手敲的腳本，大大提高了開發(fā)人員的開發(fā)效率，而且降低了出錯(cuò)率。SQL Server 2005還提供了將數(shù)據(jù)導(dǎo)入導(dǎo)出向?qū)?，可以方便的將?shù)據(jù)庫中導(dǎo)出到Excel、txt等格式文件中，也可以這些格式文

46、件中導(dǎo)入數(shù)據(jù)。. v.第三章 系統(tǒng)分析與初步設(shè)計(jì)系統(tǒng)分析與初步設(shè)計(jì)是軟件開發(fā)中的一個(gè)重要階段，是建立系統(tǒng)初步模型的。3.1系統(tǒng)分析的工作步驟 問題提出可行性分析下達(dá)初步設(shè)計(jì)任務(wù)書組織隊(duì)伍，明確分工 制定初步設(shè)計(jì)大綱下達(dá)各子系統(tǒng)設(shè)計(jì)任務(wù)書需求調(diào)查與分析確定系統(tǒng)功能目標(biāo)設(shè)計(jì)系統(tǒng)總體結(jié)構(gòu)功能模型設(shè)計(jì) 信息分類編碼設(shè)計(jì) 初步建立信息模型 界面劃分及內(nèi)外接口要求 確定系統(tǒng)配置 實(shí)施進(jìn)度計(jì)劃 組織機(jī)構(gòu)設(shè)計(jì) 經(jīng)費(fèi)預(yù)算 經(jīng)濟(jì)效益分析編寫分析階段文檔資料 修改 評(píng)審圖 3-1 系統(tǒng)分析的工作步驟首先，是問題提出，即需求的提出，要解決做什么的問題。我們遇到了什么問題，我們的需求是什么。為完成我們的需求，我們需要做

47、的系統(tǒng)都需要什么功能。系統(tǒng)分析的核心是目標(biāo)分析與需求分析。目標(biāo)分析是進(jìn)行組織系統(tǒng)的目標(biāo)分析和計(jì)算機(jī)系統(tǒng)目標(biāo)分析；需求分析是對(duì)功能需求和信息需求進(jìn)行分析。這個(gè)階段的主要目標(biāo)是針對(duì)要開發(fā)的開發(fā)項(xiàng)目，明確系統(tǒng)開發(fā)的目標(biāo)和用戶的信息需求，提出系統(tǒng)的邏輯方案。這個(gè)階段的成果是系統(tǒng)方案說明書或稱總體方案, 系統(tǒng)方案說明書是整個(gè)系統(tǒng)分析階段的工作總結(jié)，是系統(tǒng)分析人員和用戶交流的主要手段，是系統(tǒng)設(shè)計(jì)階段工作的重要依據(jù)。3.2問題提出即需求提出排課是學(xué)校教學(xué)管理中十分重要、又相當(dāng)復(fù)雜的管理工作之一，其實(shí)質(zhì)就是為學(xué)校所設(shè)置的課程安排時(shí)間和地點(diǎn)，從而使整個(gè)教學(xué)能夠有計(jì)劃有秩序的進(jìn)行。迄今為止，對(duì)課程表的研究工作已經(jīng)

48、進(jìn)行了長達(dá)四十多年之久，取得了豐碩的成果。但是，仍然存在許多不足之處，例如規(guī)模大、約束(條件)復(fù)雜以及規(guī)律不斷變化等，因此課程表問題至今仍未完全解決。課程表的編排是一個(gè)涉及多種因素的組合規(guī)劃問題，它要保證在課程安排中教師、學(xué)生、教室不能產(chǎn)生沖突(所謂沖突，就是將需上不同課程的兩個(gè)或多個(gè)班安排在了同一時(shí)間、同一教室，或?yàn)橥唤處熢谕粫r(shí)間段安排了多門課程等情況)，并且要滿足教師的要求和資源限制等約束條件?？紤]到排課的特殊性和復(fù)雜性，我們決定采用基于遺傳算法進(jìn)行排課。所以簡單說，實(shí)現(xiàn)基于遺傳算法的排課系統(tǒng)，就是用戶提出的需求。因?yàn)槭钱厴I(yè)設(shè)計(jì)，用戶假定為某高校。3.3系統(tǒng)的可行性分析l 經(jīng)濟(jì)可行性經(jīng)

49、濟(jì)可行性研究的目的是使新系統(tǒng)能達(dá)到以最小的開發(fā)成本取得最佳的經(jīng)濟(jì)效益。需要作投資估算，對(duì)開發(fā)中所需人員、硬軟件支持以及其它費(fèi)用進(jìn)行估算，并對(duì)系統(tǒng)投入使用后帶來的經(jīng)濟(jì)效益進(jìn)行估計(jì)。由于該學(xué)校硬件基礎(chǔ)設(shè)施較好，具備開發(fā)的基本條件，資金到位，而且開發(fā)是從大處著眼，從小處實(shí)施，開發(fā)費(fèi)用相對(duì)比較透明，易與控制，系統(tǒng)開發(fā)完成后將給學(xué)校帶來的經(jīng)濟(jì)效益是明顯的。因此在經(jīng)濟(jì)上是可行的。l 技術(shù)可行性技術(shù)可行性研究就是弄清現(xiàn)有技術(shù)條件能否順利完成開發(fā)工作，硬軟件配置能否滿足開發(fā)的需要，開發(fā)的風(fēng)險(xiǎn)等。l 社會(huì)可行性該系統(tǒng)使用人員學(xué)歷相對(duì)較高、經(jīng)驗(yàn)豐富、素質(zhì)較高，因此在管理上，人員素質(zhì)上都是可行的?？尚行苑治龅淖詈蟪?/p>

50、果是寫出可行性分析報(bào)告?？尚行苑治鰣?bào)告包括下列內(nèi)容：1) 學(xué)校的戰(zhàn)略目標(biāo)，新系統(tǒng)的總體目標(biāo)及主要功能；2) 擬定新系統(tǒng)的總體方案；3) 從技術(shù)、經(jīng)濟(jì)、社會(huì)等方面論證技術(shù)方案的可行性；4) 制定投資規(guī)劃和開發(fā)計(jì)劃在系統(tǒng)初步調(diào)查的基礎(chǔ)上，明確了存在的主要問題和建立新系統(tǒng)的初步設(shè)想，進(jìn)一步對(duì)系統(tǒng)目標(biāo)、范圍等因素進(jìn)行分析研究。3.4系統(tǒng)功能目標(biāo)基于遺傳算法的排課系統(tǒng)，在充分調(diào)查高校教學(xué)排課管理后，經(jīng)過分析，得出以下功能目標(biāo)：l 基礎(chǔ)信息管理1) 特殊教室管理：搜索、查看、添加、修改和刪除特殊教室信息。2) 教師信息管理：搜索、查看、添加、修改和刪除教師信息。3) 課程信息管理：搜索、查看、添加、修改和

51、刪除課程信息。4) 班級(jí)信息管理：搜索、查看、添加、修改和刪除班級(jí)信息。l 排課設(shè)置管理1) 學(xué)期課程計(jì)劃管理：實(shí)現(xiàn)對(duì)專業(yè)課程計(jì)劃的設(shè)置和維護(hù)。2) 班級(jí)課程及任課教師管理：實(shí)現(xiàn)對(duì)班級(jí)課程的設(shè)置和維護(hù)，及班級(jí)課程的任課教師的設(shè)置和維護(hù)l 排課管理1) 自動(dòng)排課：按照選定的學(xué)期時(shí)間，根據(jù)基礎(chǔ)信息和排課設(shè)置的數(shù)據(jù)進(jìn)行基于遺傳算法的自動(dòng)排課。2) 手工排課及課表調(diào)整：能夠手工排課，可對(duì)自動(dòng)排課的結(jié)果進(jìn)行手動(dòng)修改，保存時(shí)系統(tǒng)檢測(cè)報(bào)告沖突。3) 教師及班級(jí)課表打?。喊蠢蠋煷蛴?、按班級(jí)打印課表。3.5系統(tǒng)總體結(jié)構(gòu)設(shè)計(jì)通過中學(xué)排課特點(diǎn)的研究，針對(duì)需求，將整個(gè)排課系統(tǒng)分為基礎(chǔ)信息管理、排課設(shè)置管理和排課管理三

52、部分。如圖3-2所示?；谶z傳算法的排課系統(tǒng)基礎(chǔ)信息管理排課設(shè)置管理排課管理特殊教室管理課程信息管理學(xué)期課程計(jì)劃管理教師信息管理自動(dòng)排課班級(jí)信息管理班級(jí)課程及任課教師設(shè)置手工排課及課表調(diào)整班級(jí)課表打印教師課表打印圖3-2 系統(tǒng)結(jié)構(gòu)圖. v.第四章 數(shù)據(jù)庫設(shè)計(jì)數(shù)據(jù)庫設(shè)計(jì)是應(yīng)用程序開發(fā)的重要部分。本章將詳細(xì)介紹本系統(tǒng)的數(shù)據(jù)庫設(shè)計(jì)。4.1數(shù)據(jù)庫設(shè)計(jì)原則進(jìn)行數(shù)據(jù)庫設(shè)計(jì)時(shí)，需要保證數(shù)據(jù)獨(dú)立性和數(shù)據(jù)完整性，還需要遵守3NF范式標(biāo)準(zhǔn)，這些都是基本要求。根據(jù)露天煤礦設(shè)備管理系統(tǒng)開發(fā)的實(shí)際情況，還有以下幾點(diǎn)需要注意：(l) 數(shù)據(jù)庫對(duì)象命名的規(guī)范化。在給數(shù)據(jù)庫對(duì)象起名時(shí)，為了易于識(shí)別和記憶，應(yīng)該盡可能的采用有意義

53、的單詞和縮寫字符及下劃線構(gòu)成，這樣做可以使代碼可讀性更好有利于維護(hù)。名字的長度一般不要大于30字符，起名的風(fēng)格要盡可能的使用統(tǒng)一的風(fēng)格。(2)適當(dāng)?shù)氖褂脭?shù)據(jù)冗余。并不是嚴(yán)格遵守3NF的數(shù)據(jù)庫設(shè)計(jì)就是好的，適當(dāng)?shù)氖褂脭?shù)據(jù)冗余，可以提升數(shù)據(jù)庫的運(yùn)行效率。數(shù)據(jù)冗余過多的數(shù)據(jù)庫設(shè)計(jì)，很容易產(chǎn)生“臟數(shù)據(jù)”，但冗余對(duì)查詢的效率是有提升效果的，冗余減少了不同表之間的聯(lián)合操作。所以在有些情況下，可以適當(dāng)?shù)氖褂脭?shù)據(jù)冗余，雖然這使得數(shù)據(jù)庫滿足的范式有所降低，但在能保證不出現(xiàn)“臟數(shù)據(jù)”的情況下，這樣做可以提高效率。(3)在數(shù)據(jù)庫的設(shè)計(jì)和程序開發(fā)過程中，盡量采用對(duì)數(shù)據(jù)庫性能有利的方式。比如存儲(chǔ)過程的合理使用就可以提升

54、數(shù)據(jù)庫的運(yùn)行速度。存儲(chǔ)過程可以將一系列的數(shù)據(jù)庫操作組合在一起一次性完成，減少了程序與數(shù)據(jù)庫之間交互的次數(shù)，而且也減少了對(duì)數(shù)據(jù)庫連接資源的占用。又比如索引的使用也可以提升數(shù)據(jù)庫的訪問效率。當(dāng)然索引也不是越多越好，索引的使用要根據(jù)實(shí)際，創(chuàng)建適合需求的索引，從而達(dá)到提升系統(tǒng)的運(yùn)行效率的目的。 (4)不采用或少采用表間關(guān)聯(lián)。強(qiáng)制性的表間關(guān)聯(lián)能夠保證數(shù)據(jù)的完整性和一致性。如果嚴(yán)格按照規(guī)范來進(jìn)行數(shù)據(jù)庫設(shè)計(jì)，表間關(guān)聯(lián)通常都會(huì)比較多。在對(duì)有關(guān)聯(lián)關(guān)系的表進(jìn)行操作時(shí)，數(shù)據(jù)回去檢查關(guān)聯(lián)約束，這會(huì)占用系統(tǒng)的資源。因此在本系統(tǒng)的數(shù)據(jù)庫中一般都不添加主外鍵約束，而通過系統(tǒng)的業(yè)務(wù)規(guī)則處理來實(shí)現(xiàn)約束。設(shè)計(jì)一個(gè)良好的數(shù)據(jù)庫，對(duì)

55、程序開發(fā)及實(shí)施后的運(yùn)行和維護(hù)都是非常重要的。所以設(shè)計(jì)數(shù)據(jù)庫一定要下足功夫，不能馬虎行事。4.2數(shù)據(jù)庫E-R圖采用ER圖(實(shí)體關(guān)系圖)的方法進(jìn)行數(shù)據(jù)結(jié)構(gòu)分析. ER圖設(shè)計(jì)方法是一種通過ER圖來描述現(xiàn)實(shí)世界信息結(jié)構(gòu)的DB設(shè)計(jì)方法, ER圖由實(shí)體、屬性、聯(lián)系三部分組成。（實(shí)體名）（屬性名）（聯(lián)系名）實(shí)體聯(lián)系屬性圖4-1 ER圖基本圖素本系統(tǒng)主要ER圖如圖4-2，圖中實(shí)體的屬性只畫出重要的部分。課程班級(jí)教室類型學(xué)期課程計(jì)劃m1班級(jí)課程及任課教師nmn課程名學(xué)期（時(shí)間）對(duì)應(yīng)關(guān)系教師11學(xué)期（年級(jí)）每周課時(shí)每周課時(shí)班級(jí)人數(shù)課程表關(guān)系特殊教室教室類型容量關(guān)系10-1圖4-2 主要ER圖4.3數(shù)據(jù)庫物理結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)庫設(shè)計(jì)原則：a.盡可能減少數(shù)據(jù)冗余和重復(fù)在滿足需要的前提下，應(yīng)盡量按照關(guān)系數(shù)據(jù)庫