畢業(yè)設計（論文）基于遺傳算法的課程安排優(yōu)化設計

1、題 目： 基于遺傳算法的課程安排優(yōu)化設計 摘要課程表規(guī)劃問題是一個np 完全問題，其規(guī)劃策略可以通過多種方法實現(xiàn)，一般啟發(fā)式搜索算法是通過在全局區(qū)間找到可行結果，通常適合于簡單的例子，對于多參數(shù)輸入和結果要求，尋找一個相當好的解決方案可能需要耗費很多時間，甚至是不可能的。遺傳算法(gas) 是基于啟發(fā)式方法的種群，該方法已經成功應用于人工智能、搜索和優(yōu)化的各個領域，遺傳算法的原理是由holland設計并進行開發(fā)的，遺傳算法具有以下特性：（1）從種群中選擇個體的機制;（2）創(chuàng)造新個體的運算;（3）通過將以前的單個方案隨機打亂，生成新解決方案的過程（4）更新個體的規(guī)則，這些特性分別被稱為選擇，雜交

2、，變異，更新。本論文擬將遺傳算法應用于課程表的多參數(shù)優(yōu)化，尋找滿足約束條件的課程規(guī)劃。關鍵字：課程表規(guī)劃，遺傳算法，選擇，雜交，變異，更新abstractmaking a class schedule is one of those np-complete problems which can be solved by many methods. the normal heuristic search algorithm finds the optimal solution based local search procedure, but it only works for simple c

3、ases. for more complex inputs and requirements, finding a considerably good solution can take a while, or it may be impossible. genetic algorithms (gas) are population based heuristic approaches. they have been applied successfully in various domains of artificial intelligence, search, and optimizat

4、ion. the promising results were obtained for many difficult optimization problems. the principles of gas were developed by holland .very briefly, gas can be characterized by the following features: (1) a mechanism for selecting individuals from the population; (2) an operator for creating new indivi

5、duals; (3) a procedure for generating new solution by random perturbations of the single previous solutions; (4) a rule for updating the population. these features are referred to as selection, crossover, mutation, and updating. in this paper, gas will be applied to optimizing the multi-parameter of

6、 schedule and searching the schedule which satisfies the requirements . key words: class schedule planning，genetic algorithms，selection，crossover，mutation， updating.目錄摘要1abstract2第一章 緒 論41.1研究目的及意義41.2研究現(xiàn)狀41.3研究內容4第二章 排課問題研究的概述52.1課程表問題的描述52.1.1時間表問題概述52.1.2課程表問題概述52.2大學課程表問題的研究情況62.2.1大學課程表問題的理論研究6

7、2.2.2大學課程表問題解決方法62.3排課的各種算法的比較7第三章 課程表的類對象93.1課程表的類對象93.2chromosome 染色體93.2.1 representation 表示93.2.2 fitness 適應度103.2.3 crossover 雜交113.2.4 mutation 突變12第四章 基于遺傳算法的課程規(guī)劃124.1遺傳算法的來源和研究發(fā)展124.2具體操作134.3課表觀察員164.4配置164.4.1 配置文件164.4.2 配置文件的例子174.4.3 解析一個配置文件184.5程序運行示意圖19第五章 結 論21致謝23參考文獻24第一章 緒 論 1.1

8、研究目的及意義排課問題的本質是將課程、教師和學生在合適的時間段內分配到合適的教室中，涉及到的因素較多，是一個多目標的調度問題，即np（nondeterministic polynomial，非確定的多項式）完全問題。np-完全問題的簡單與否，取決于問題的難易程度，只能用啟發(fā)式算法找出最優(yōu)解。然而這種算法太慢了，根本無法在計算機上實現(xiàn)。因此眾多研究者提出了多種其他排課算法，如模擬退火、禁忌搜索、進化算法等。其中，遺傳算法(genetic algorithm, 簡稱ga)是很有效的求最優(yōu)解的算法。本課題的主要目的是通過綜合研究、分析現(xiàn)有的排課優(yōu)化的解決方法，實現(xiàn)基于遺傳算法的自動排課優(yōu)化。本課題的

9、研究意義在于，實現(xiàn)基于遺傳算法的排課優(yōu)化問題，可以提高優(yōu)化的滿意度和靈活度。實踐證明，這種算法設計得出的課程安排可以達到了師生的高度滿意。1.2 研究現(xiàn)狀大學課程表問題（university timetable problem-utp）或者時間表問題（time table problem-ttp）是一個一直困擾各個學校的令人頭疼問題，它是運籌學典型的組合優(yōu)化問題之一。教師，教室，時間，課程和班級是五個制約該問題解決的重要因素。19世紀60年代，開始有學者從事計算機輔助排課的研究，appleby等人開始使用簡單的經驗法，來解決小規(guī)模的排課問題。遺傳算法是由美國芝加哥大學holland教授于197

10、5年所提出。其基本觀念源自于達爾文的進化論（darwins theory of evolution）中適者生存的理論，是一種通過模擬自然界生物進化過程求解極值的自適應人工智能技術。遺傳算法借用了生物遺傳學的觀點，通過自然選擇、遺傳、變異等作用機制來提高各個個體的適應性，體現(xiàn)了自然界中“物競天擇、適者生存”的進化過程。1975年，經過對該問題進行證明，s.even提出它是一個np完全問題。這意味著普通的方法比如圖著色，整數(shù)規(guī)劃，對復雜的學校排課問題并不能進行良好的解決。從70年代到90年代，有些學者開始了利用矩陣向量方法來對排課問題進行研究，能夠解決規(guī)模稍大的問題，但是仍然存在缺陷。到了90年代

11、后，國內外很多學者轉而采用遺傳算法對排課問題進行了研究，隨著遺傳算法的發(fā)展，有了一定的結果，但是仍然未能解決滿意度的問題。1.3 研究內容第一步：了解遺傳算法的概念及其對于排課優(yōu)化的重要意義。第二步：研究現(xiàn)有的排課優(yōu)化方案及存在問題。第三步：利用遺傳算法建立數(shù)學模型，定義染色體編碼方案和適應度函數(shù)。第四步：通過初始化種群、選擇、交叉、變異等過程不斷進化，最后得到最優(yōu)解。第五步：結果分析及其優(yōu)化。第二章 排課問題研究的概述22.1 課程表問題的描述2.1.1時間表問題概述時間表問題（timetableproblem）既是一個理論方面的問題也是一個來源于實踐的問題，它是實際生活中人們可以遇到的問題

12、，甚至對于我們來說很常見。比如說交通時間表問題1112（transportationtimetabling)，這個問題是如何設計城市中公交車或者有軌電車的時間表問題,使其能夠良好的運行，減緩城市交通的壓力；比賽時間表問題13(employeetimetabling)是如何設計一項大型賽事的時間表，來保證大型賽事能夠良好的進行；還有雇員工作時間表問題(employeetimetabling)，研究得是如何來安排雇員的工作，使其工作能夠達到最高的效率；當然還有我們要研究的大學課程表問題，這個問題研究的主要目的是提出一種優(yōu)秀的算法最大程度上使學校課程安排人性化、合理化。 時間表問題是一類具有多約束的

13、將有限時間資源分配給多個事件組合優(yōu)化問題。通常，一個時間表問題會有一系列事件(event)和一組有限的時空單元(time-space slot)和一組具體地點，并且還要受到一系列約束的限制，這些約束又分為硬約束和軟約束。硬約束就是我們在進行時間表安排的情況下必須無條件滿足的一系列限制，不能有任何違反，而軟約束也是一系列的限制，但是我們不一定要全部滿足，但是這些軟約束的滿足情況卻決定了我們時間表安排的合理情況。當你排一個課程表時，你必須考慮很多要求（教授、學生、班級和教室的數(shù)目，教室的大小，教室里的實驗器材等等）。這些需求可通過其重要性被分成若干組。硬約束（如果你不能解決其中一個，這個排課計劃就

14、是不可行的）：l 一個班級只能放在一個空教室里l 沒有教授和學生可以在同一時間上一門以上的課l 一個教室要有足夠的位子安排所有的學生l 如果要在一個教室排課，此教室要有這門課程所需要的設備（例如電腦）軟約束（即使不能解決，計劃仍是可行的）l 一些教授對上課時間的偏好l 一些教授對上課地點的偏好l 學生或教授的在時間和地點上的班級分配當然，硬的和軟的約束取決于有關情況。在這個程序中，只有硬約束落到了實處。2.1.2課程表問題概述本文主要研究的是時間表問題中的課程表問題。這個問題是來源于學校日常生活，和學生的日常生活息息相關。隨著學校規(guī)模擴大，學生的數(shù)量急劇增加，學校的教育資源顯得越來越有限，這個

15、問題就顯得越發(fā)突出。所以對這個問題的研究具有現(xiàn)實意義，但是它又不缺乏理論性，1975年，s.even對該問題進行了研究，并指出大學課程表問題是一個np完全問題，這就說明了該問題沒有真正意義上的最優(yōu)解，人們的求解只有可能是相似最優(yōu)解，也就是說求解獲得的答案只可能不斷接近最優(yōu)解，但是不可能是最優(yōu)解。于是人們就嘗試用各種方法去解決這個問題，如圖著色、分支定界、整數(shù)規(guī)劃等，經過實踐證明，遺傳算法和模擬退火算法是兩種解決該問題比較理想的方法。本文在后面主要介紹了遺傳算法。 那什么是課程表問題？雖然已經從感性上已經了解了這個問題，但是下面將給出一個較為嚴格的定義方便深入理性的理解這個問題。carter和l

16、aporte這樣定義：“課程表問題是一個多元分配問題，它研究的就是如何把學生和老師分配給課程，課程單元或者班級，如何把事件（上課事件）分配給教室和時間” 。 簡單一些的說大學課程表問題研究的就是如何把一系列的課程分給有限的教室和一周內有限的上課時間單元，如何把學生和老師分配給課程。當然實際研究的時候并沒有理論上說得這么簡單，它會受到多種約束的影響，有硬約束也有軟約束，這我們在上一小節(jié)已經提到了。 2.2 大學課程表問題的研究情況2.2.1大學課程表問題的理論研究大學課程表問題在20世紀50年代末就已經開始被人們所重視，將它作為一個科學問題來研究，但是一直到1963年才由gotlieb提出了該問

17、題的數(shù)學模型和形式化描述，這標志著排課問題正式被作為科學問題來被人們所研究，到了1975年s.even在他的論文中提出并證明大學課程表問題是一個np完全問題，把該問題理論化，同時也說明該問題有解，并能夠找到解。但是根據(jù)計算和難解性理論，目前還沒有解決np完全問題的多項式算法。到1979年，schmidt和stroheim在文獻中就列出了300多篇有關大學課程表問題的已發(fā)表文獻。現(xiàn)在每年外國的關于運籌學的雜志上依然總會出現(xiàn)一些關于該問題的論文。 2.2.2大學課程表問題解決方法至今已經有很多算法被拿來研究用于嘗試解決該問題。起初，圖論是研究大學課程表問題的一個主要武器，圖著色技術被廣泛的用來嘗試

18、解決該問題。舉個例子，1994年，burke,elliman和weare6就研究出一種啟發(fā)式的圖著色方法，該方法把考試進程分成若干組，然后把它們放在一起安排，以求找到一種能夠解決考試時間表問題的方法。但是圖著色技術本身就是一個np完全問題，所以對解決該問題幫助不大。后來carter,m.w.和laporte15嘗試采用按序分派的方法解決該問題，這種方法需要按啟發(fā)順序把事件分出先后順序，然后再嘗試尋找一個可行的解決方案。ferland等人18和吳金榮17把排課問題轉化成整數(shù)規(guī)劃問題來解決，但計算量很大，只適合一些理論中的簡單情況對于解決復雜問題是不可行的。許多文章11121314試圖利用啟發(fā)式函

19、數(shù)來解決排課問題，但是大多數(shù)啟發(fā)方法都是模擬手工排課的過程來實現(xiàn)的。但是由于實際的排課問題存在各種各樣的限制條件與特殊要求，處理不好這些限制和要求就無法找到理想的排課方案。 最后，啟發(fā)式算法被引入大學課程表問題，而且在一定程度上獲得成功，在解決大學課程表問題上取得了不錯的成績。啟發(fā)式算法主要包括三種：禁忌搜索(tabusearch)，模擬退火算法(simulatedannealing)和進化算法(evolutionaryalgorithms)。 1.禁忌搜索(tabusearch) 禁忌搜索是一種主要研究研究具有各種特殊要求的真實世界時間表問題的算法。它由glover在1986年提出，進而慢慢

20、形成一種獨特而又完整的算法。經過研究表明這種算法如果能夠正確恰當選擇參數(shù)（禁忌列表，初始化解決方案和目標函數(shù)）那么它在解決大學課程表問題上將有很出色的表現(xiàn)。1998年，nonobe和ibaraki13開發(fā)出一種基于禁忌搜索的處理一般問題的解決系統(tǒng)，這種系統(tǒng)對于滿足約束問題特別是高中課程表問題有著出人意料的良好效果。后來在2002年，alvarez.valdes,crespo和tamarit14研制出了一種基于禁忌搜索的具有友好界面的系統(tǒng)，這個系統(tǒng)經過一系列實驗也取得不錯成績。現(xiàn)在關于這項技術的研究還在繼續(xù)，我們這里就不再贅述了。 2.模擬退火算法(simulatedannealing) 模擬退

21、火算法是一種被廣泛研究的算法，它也經常被用來解決時間表問題和大學課程表問題。它是一種模擬固體退火過程的算法。它由kirkpatrick等人于1982年提出，后來就專門用來解決大規(guī)模組合優(yōu)化問題，它是一種解決np完全組合優(yōu)化問題的有效的近似算法。現(xiàn)在一些研究表明，模擬退火算法在課程表問題15和考試時間表問題6上的實現(xiàn)是高度依賴于各種設定與參數(shù)（解決方案空間，降溫時間表，鄰居產生和評估函數(shù)）。因此使用這種算法的時候需要謹慎的選擇參數(shù)。 3.進化算法(evolutionaryalgorithms) 進化算法和遺傳算法現(xiàn)在已經被廣泛用來研究時間表問題和大學課程表問題。遺傳算法最早是由colorni7等

22、人在90年代初期引入用來解決課程表問題的，一開始他們引進了矩陣表示方案和交叉、變異算子。后來colorni8又把遺傳算法成功應用到米蘭一所較大的學校的課程排布問題中。paechter9等人對ttp問題進行了研究，提出了時域置換法和放置查找法，并針對較大規(guī)模的實際ttp問題比較了這二種算法的性能。burke3對將進化算法分階段的用于utp問題做了初步的研究，得到一些頗有價值的成果。遺傳算法是本文研究的重點，后面第四章我們將更加詳細的講解遺傳算法。另外基于知識學習的技術也漸漸的參與到對于時間表問題和課程表問題的求解上來。基于知識學習的技術是一種模仿人類思維過程的技術，人類在解決問題的時候總是先在大

23、腦中尋找一個相似的問題，然后對這個相似問題進行分析學習，然后對這個相似問題進行改進以求獲得當前新問題的解決方案。這種技術有一個很至關的重要問題，就是如何能清晰地表示經驗和知識，并將其存入知識庫以便后來之用。這種技術主要包括兩種：一種是基于規(guī)則的系統(tǒng)，另一種是基于案例推理的系統(tǒng)(case-basedreasoning，cbr)。現(xiàn)在大多數(shù)用來解決時間表問題的基于知識學習的系統(tǒng)都是基于規(guī)則的，很少有基于案例推理的系統(tǒng)。本文主要講述的是前一種基于規(guī)則的系統(tǒng)。2.3 排課的各種算法的比較至今為止有很多的方法技術和算法都已經被用來嘗試解決時間表問題或者大學課程表問題，他們效果各異，有的完成很出色，有的則

24、只在某些特定情況下才能有不錯的效果。傳統(tǒng)的算法比如說圖論和整數(shù)規(guī)劃在應付簡單時間表問題和課程表問題時可以較容易的編碼，通常情況下可以圓滿地完成任務。但是他們通常對于大型的復雜約束時間表或者課程表問題顯得束手無策。人工智能領域的全局搜索技術（包括遺傳算法，禁忌搜索，還有模擬退火算法）在各個問題領域都取得了很不錯的效果。他們都能夠處理各個級別的問題，既可以是簡單的問題，也可以是復雜的大型問題。但是他們也有自己的問題需要注意，在使用他們的時候不同場合參數(shù)的初始化往往不同，這是一個既重要又難以處理的問題。研究表明基于啟發(fā)方式的混合算法，在處理問題時候往往會比單獨一種算法有更好的更出色的效果。可以看出啟

25、發(fā)式算法是解決時間表問題和大學課程表問題各種算法中的翹楚。但是當他們之間作比較的時候，一些研究表明，當算法使用的環(huán)境不同，表示的方法不同和選擇的算子不同的時候他們往往會有完全不同的表現(xiàn)。1995年，ross和corne在解決一個時間表問題時，對遺傳算法、模擬退火算法和隨機爬山算法進行比較，得出結論隨機爬山算法在解決問題的質量上略勝一籌3。colorni、dorigo和maniezzo在1998年，對遺傳算法、模擬退火算法、禁忌搜索和輔以局部搜索的遺傳算法進行比較，得出結論禁忌搜索的效果更佳，但是輔以局部搜索的遺傳算法給出了一系列的高質量解決方案，給用戶更多的靈活性，以滿足各種不同的要求。雖然在

26、不同的環(huán)境下，各種啟發(fā)算法會有不同的表現(xiàn)。但是大家都一致認為遺傳算法在解決現(xiàn)實生活中問題的時候具有足夠的靈活性，可以給出一系列的較優(yōu)解以滿足人們各種方面不同的需要。本文將著重研究的就是遺傳算法，一種改進的混合算法，希望能夠對解決時間表問題有較好的作用。 大學課程表問題作為一個典型時間安排問題已經成為了一個具有豐富知識和經驗的應用領域。現(xiàn)在幾乎所有的用來解決時間表問題的基于知識學習系統(tǒng)都是基于規(guī)則的。本文試圖講述一個使用基于規(guī)則進行初始化，并用該技術用來指導算法進行改進的遺傳算法。 第三章 課程表的類對象33.1 課程表的類對象professor 教授教授類有id和name（教授的名字）。還包括

27、一個教授所教課的鏈表students group 學生組學生組類有id和name（學生組的名字），及這個學生組的學生數(shù)目。還包括這個學生組要參加的課的鏈表。classroom 教室教室類有id和name（教室的名字），也有座位的數(shù)目、有關設備（電腦）的信息。如果教室有電腦，預計為每個座位都有電腦。id是內部自動生成的。course 課程課程類有id和name（課程的名字）。course class 課（單門課的信息）課類包含哪位教授教的這節(jié)課，這節(jié)課上的什么課程，參加這節(jié)課的學生組列表。還有教室需要的座位數(shù)（即學生組的學生數(shù)目之和），是否需要電腦，這節(jié)課持續(xù)的小時數(shù)。3.2 chromosom

28、e 染色體首先我們應該考慮，當我們處理遺傳算法時如何以遺傳運算可行的方式來表達我們的解法，例如雜交和突變。此外，我們應該知道如何判斷我們的解法有多好。換句話說，我們應該能夠計算出我們解法的適應度3.2.1 representation 表示怎么來用染色體表示一個課程表呢？好，我們需要一個存儲槽（時空槽）對應每個小時，每個教室，每一天。還有，我們假設只能在周一到周五（總共5天的早上9點到晚上9點之間上課（總共12個小時）。我們可以使用一個 12*5*number_of_rooms 大小的向量組。每一個槽都應該是一個鏈表，因為在該算法運行時，我們允許多個課在同一個時空槽里。我們使用一個輔助的has

29、h圖用來獲取一節(jié)課開始時的地址。一門課的每個小時都在向量中有一個單獨的表目，但在hash圖中每門課只有一個表目。例如，假如一節(jié)課從下午1點開始并持續(xù)3小時，它必須進入1點、2點、3點的槽。圖3-1 染色體表示每一條染色體表示一種可能的排課結果，至于排課結果的優(yōu)劣，則由適應度函數(shù)評估染色體的適應值來決定。染色體代表課程表類，它存儲課程表的兩個屬性：/ 時空槽的項代表一個教室的一小時vectorlist _slots;/ 課程表染色體，存儲class占用的第一個時空槽地址hash_map _classes;此外，染色體應該存儲它的適應度和遺傳操作要使用的參數(shù)。/ 染色體的適應度float _fit

30、ness;/ 課需求滿意度的標準vector _criteria;3.2.2 fitness 適應度遺傳算法在進化中是以每個個體的適應度值為依據(jù)來選取下一代種群的。適應度函數(shù)設定的好壞直接影響到遺傳算法的收斂速度和能否找到最優(yōu)解。在本系統(tǒng)中，適應度值的設計只與硬約束有關：l 每門課有0到5分l 如果一門課用了一個空教室，我們就增加它的分數(shù)l 如果一門課需要電腦而它所在的教室有電腦或者不需要電腦，我們就增加它的分數(shù)l 如果一門課被安排在有足夠椅子的教室里，我們就增加它的分數(shù)l 如果一位教授沒有其他課，我們就增加這門課的分數(shù)l 如果要上課的學生組里的任何一個人在同一時間沒有其它課，就加一分l 一個

31、課程表的總分是所有門課分數(shù)的總和l 適應度= schedule_score/maximum_score，maximum_score = number_of_classes*5適應度由單精度浮點數(shù)表示（float），值在0到1之間。3.2.3 crossover 雜交一個雜交操作結合了hash圖中雙親的數(shù)據(jù)，并根據(jù)新hash圖的內容創(chuàng)造出一個向量槽。雜交操作以隨機的一些部分來分割hash圖中的雙親。部分數(shù)由染色體參數(shù)里的雜交數(shù)決定。它交替復制雙親的一些部分給新的染色體，形成新的向量槽。圖3-2 雜交/ 執(zhí)行雜交操作并且返回后代的指針schedule* crossover(const schedu

32、le& parent2) const 3.2.4 mutation 突變突變操作非常簡單。它只須隨便移一門課到另外一個隨機選擇的槽里。在一個簡單操作里，要被移動的課的數(shù)目由染色體參數(shù)里的突變大小決定。/ 執(zhí)行突變操作void mutation(); 第四章 基于遺傳算法的課程規(guī)劃44.1 遺傳算法的來源和研究發(fā)展19世紀達爾文通過艱辛的考察多年的研究，最終提出了一個具有劃時代意義的理論進化論。按照進化論，地球上的每一物種從誕生開始就開始了漫長的進化。生物種群總是從低級，簡單的類型逐步發(fā)展到高級，復雜的類型，從簡單單細胞生物逐步發(fā)展成為高級多細胞生物。每種生物為了生存需要不停的斗爭，包括同一種群

33、內部的斗爭，不同種群之間的斗爭，和自然無機環(huán)境進行斗爭。有些生物生存了下來，并繁衍壯大，因為它具有與眾不同但是能夠適應環(huán)境適合生存的特點；有的生物消亡了，不再存在于地球，留給我們只是化石和無邊的猜測，這是因為它不能夠適應環(huán)境，不能在生物競爭中取勝。達爾文通過研究考察發(fā)現(xiàn)了這一過程，并將它稱為“物競天擇，適者生存”。 生物學家通過研究發(fā)現(xiàn)有的生物之所以繁衍壯大，有的生物之所以消亡，就是因為他們具有了一些別的種群沒有的特點，而這些特點又是遺傳基因決定的，遺傳基因上有大量的遺傳信息，這些遺傳信息就是決定生物身上各種性征，而這些性征有一部分又能夠決定生物在自然界的競爭中勝敗，而競爭的勝敗直接決定了某一

34、種生物的生存和發(fā)展。但是一種生物的壯大就需要生物能夠把自己的性征傳給下一代，而這一過程是通過遺傳基因來做到的。 遺傳基因是有一定組合規(guī)律的，這些組合的特異性決定了生物體的多樣性，基因結構的穩(wěn)定性保證了生物物種的穩(wěn)定性，而基因的雜交和變異是生物產生了進化的可能。生物的遺傳是通過父代向子代傳遞基因來實現(xiàn)的，而這種遺傳信息的改變決定了生物體的變異。遺傳算法采用類似基因演化的循環(huán)過程，其演算過程如下： 1）隨機產生一定數(shù)目的初始種群 2）對個體適應度進行評估，如果個體的適應度符合優(yōu)化準則，則輸出最佳個體及其代表的最優(yōu)解，并結束計算，否則轉向第3步。 3）依據(jù)適應度選擇再生個體 4）按照一定的交叉概率和

35、交叉方法生成新的個體 5）按照一定的變異概率和變異方法生成新的個體 6）由交叉和變異產生新一代的種群，然后返回第2步。如圖1所示：圖3-3 遺傳算法示意圖4.2 具體操作遺傳算法相當簡單。對于每一代，它執(zhí)行兩個基本操作：1、從當前種群里隨機選擇n對父母，并且通過在每對父母里執(zhí)行雜交操作產出n個新的染色體2、從當前種群里隨機選擇n對父母，并且用新的代替他們。如果它是種群里最優(yōu)的染色體之一，算法就不選擇新的染色體這兩個操作會一直重復直到最優(yōu)的染色體的適應度達到1（意味著課表里的所有課程都達到要求）。正如之前提到的，遺傳算法一直追蹤種群里的m個最優(yōu)染色體，同時當他們屬于最優(yōu)染色體時保證它們不會被代替

36、。/ 遺傳算法class algorithmprivate:/ 染色體的種群vector _chromosomes;/ 表明染色體是否屬于最優(yōu)染色體群vector _bestflags;/ 最優(yōu)染色體vector _bestchromosomes;/ 當前存儲的最優(yōu)染色體數(shù)目int _currentbestsize;/ 在每一代人被后代所取代的染色體數(shù)目int _replacebygeneration;/ 指向算法觀察員scheduleobserver* _observer;/ 種群里的染色體原型schedule* _prototype;/ 當前的一代int _currentgeneratio

37、n;/ 算法的執(zhí)行狀態(tài)algorithmstate _state;/ 算法狀態(tài)的同步ccriticalsection _statesect;/ 指向算法的全局實例static algorithm* _instance;/ 全局實例創(chuàng)建和毀滅的同步化static ccriticalsection _instancesect;public:/ 返回算法全局實例的引用static algorithm& getinstance();static void freeinstance();/ 初始化遺傳算法algorithm(int numberofchromosomes, int replacebyge

38、neration, int trackbest,schedule* prototype, scheduleobserver* observer);algorithm();/ 開始執(zhí)行void start();/ 停止執(zhí)行void stop();/ 返回種群里最優(yōu)染色體的指針schedule* getbestchromosome() const;/ 返回當前這一代inline int getcurrentgeneration() const return _currentgeneration; / 返回算法觀察員的指針inline scheduleobserver* getobserver()

39、const return _observer; private:/ 增加染色體進最優(yōu)染色體群void addtobest(int chromosomeindex);/ 如果染色體屬于最優(yōu)染色體則返回truebool isinbest(int chromosomeindex);/ 清空最優(yōu)染色體群void clearbest();4.3 課表觀察員scheduleobserver 類處理由遺傳算法觸發(fā)的事件。這個類給應用程序的視圖窗口發(fā)送消息。當算法的執(zhí)行沒有結束或者中斷了，可以通過調用waitevent()阻塞呼叫方的線程。/ 當算法找到新的最優(yōu)染色體時啟動的句柄事件void newbestc

40、hromosome(const schedule& newchromosome); / 當算法執(zhí)行狀態(tài)發(fā)生變化時啟動的句柄事件void evolutionstatechanged(algorithmstate newstate); / 阻塞調用者進程直到算法執(zhí)行結束inline void waitevent() waitforsingleobject( _event, infinite ); 如果你計劃改變newbestchromosome方法，記住如果要顯示最優(yōu)染色體，必須作一個硬件拷貝（通過使用schedule類里的makecopy方法）因為算法會在下一代里刪除染色體。4.4 配置4.4.

41、1 配置文件對象的標識符：1. professor ( #prof tag) 教授 2. course ( #course tag) 課程 3. room ( #room tag) 教室 4. group ( #group tag) 學生組 5. course class ( #class tag) 綁定了教授、課程、學生組的課每個對象以自己的標記符開始以#end結束，所有的標記必須在單獨的行里。在對象的主題里，每行只包含一個鍵和值對（屬性）以=分開。每個屬性被一次性指定，除了#group對象里的group屬性，它可以有多個group屬性。以下是對象屬性的列表：1. #prof l id (n

42、umber, required) 教授的編號 l name (string, required) - 教授的名字2. #course l id (number, required) 課程的編號 l name (string, required) - 課程的名字3. #room l name (string, required) 教室的名字 l size (number, required) 教室的座位數(shù) l lab (boolean, optional) 教室是否有電腦，默認值為false4. #group l id (number, required) 學生組的編號 l name (stri

43、ng, required) - 學生組的名稱l size (number, required) - 學生人數(shù) 5. #class l professor (number, required) 綁定的教授編號l course (number, required) 綁定的課程編號 l group (number, required) 綁定的學生組編號，每門課都綁定多個學生組 l duration (number, optional) 課的持續(xù)時間 （單位小時），默認值為1l lab (boolean, optional) 這門可是否需要教室里有電腦，默認值為false值得注意的是 professo

44、r、 students group、 course在綁定到class前都必須先定義。4.4.2 配置文件的例子#profid = 1name = 劉備#end#courseid = 1name = c+#end#roomname = s3-402lab = truesize = 24#end#groupid = 1name = 1o1size = 19#end#classprofessor = 1course = 1duration = 2group = 1group = 2#end#classprofessor = 1course = 1duration = 2group = 3group

45、= 4#end#classprofessor = 9course = 1duration = 3group = 1lab = true#end4.4.3 解析一個配置文件由configuration類來解析一個配置文件。parsefile打開并分析一個配置文件。它尋找對象標識符并且調用合適的方法來分析對象。parsefile清空之前解析了的對象。public:void parsefile(char* filename);private:professor* parseprofessor(ifstream& file);studentsgroup* parsestudentsgroup(ifst

46、ream& file)course* parsecourse(ifstream& file);room* parseroom(ifstream& file);courseclass* parsecourseclass(ifstream& file); 解析一個文件：configuration:getinstance().parsefile( gaschedule.cfg ) 除了課程類，解析的對象都被放在一個hash圖里，所以他們可以被快速輕易的訪問private:hash_map _professors;hash_map _studentgroupshash_map _courseshash_map _rooms; list _courseclasses; configuration類也包含檢索已經解析了的信息和對象的方法public:inline professor* getprofessorbyid(int id) /.inline int getnumberofprofessors() const /.inline studentsgroup* getstudentsgroupbyid(int id) /.inline int getnumberofstudentgroups() const /.inline course* getcourse