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

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

2、，變異，更新。本論文擬將遺傳算法應(yīng)用于課程表的多參數(shù)優(yōu)化，尋找滿足約束條件的課程規(guī)劃。關(guān)鍵字：課程表規(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研究?jī)?nèi)容4第二章 排課問(wèn)題研究的概述52.1課程表問(wèn)題的描述52.1.1時(shí)間表問(wèn)題概述52.1.2課程表問(wèn)題概述52.2大學(xué)課程表問(wèn)題的研究情況62.2.1大學(xué)課程表問(wèn)題的理論研究6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28、e 染色體首先我們應(yīng)該考慮，當(dāng)我們處理遺傳算法時(shí)如何以遺傳運(yùn)算可行的方式來(lái)表達(dá)我們的解法，例如雜交和突變。此外，我們應(yīng)該知道如何判斷我們的解法有多好。換句話說(shuō)，我們應(yīng)該能夠計(jì)算出我們解法的適應(yīng)度3.2.1 representation 表示怎么來(lái)用染色體表示一個(gè)課程表呢？好，我們需要一個(gè)存儲(chǔ)槽（時(shí)空槽）對(duì)應(yīng)每個(gè)小時(shí)，每個(gè)教室，每一天。還有，我們假設(shè)只能在周一到周五（總共5天的早上9點(diǎn)到晚上9點(diǎn)之間上課（總共12個(gè)小時(shí)）。我們可以使用一個(gè) 12*5*number_of_rooms 大小的向量組。每一個(gè)槽都應(yīng)該是一個(gè)鏈表，因?yàn)樵谠撍惴ㄟ\(yùn)行時(shí)，我們?cè)试S多個(gè)課在同一個(gè)時(shí)空槽里。我們使用一個(gè)輔助的has

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

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

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

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

33、內(nèi)部的斗爭(zhēng)，不同種群之間的斗爭(zhēng)，和自然無(wú)機(jī)環(huán)境進(jìn)行斗爭(zhēng)。有些生物生存了下來(lái)，并繁衍壯大，因?yàn)樗哂信c眾不同但是能夠適應(yīng)環(huán)境適合生存的特點(diǎn)；有的生物消亡了，不再存在于地球，留給我們只是化石和無(wú)邊的猜測(cè)，這是因?yàn)樗荒軌蜻m應(yīng)環(huán)境，不能在生物競(jìng)爭(zhēng)中取勝。達(dá)爾文通過(guò)研究考察發(fā)現(xiàn)了這一過(guò)程，并將它稱為“物競(jìng)天擇，適者生存”。 生物學(xué)家通過(guò)研究發(fā)現(xiàn)有的生物之所以繁衍壯大，有的生物之所以消亡，就是因?yàn)樗麄兙哂辛艘恍﹦e的種群沒(méi)有的特點(diǎn)，而這些特點(diǎn)又是遺傳基因決定的，遺傳基因上有大量的遺傳信息，這些遺傳信息就是決定生物身上各種性征，而這些性征有一部分又能夠決定生物在自然界的競(jìng)爭(zhēng)中勝敗，而競(jìng)爭(zhēng)的勝敗直接決定了某一

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

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

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

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

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

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

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

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

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

43、ng, required) - 學(xué)生組的名稱l size (number, required) - 學(xué)生人數(shù) 5. #class l professor (number, required) 綁定的教授編號(hào)l course (number, required) 綁定的課程編號(hào) l group (number, required) 綁定的學(xué)生組編號(hào)，每門課都綁定多個(gè)學(xué)生組 l duration (number, optional) 課的持續(xù)時(shí)間 （單位小時(shí)），默認(rèn)值為1l lab (boolean, optional) 這門可是否需要教室里有電腦，默認(rèn)值為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 解析一個(gè)配置文件由configuration類來(lái)解析一個(gè)配置文件。parsefile打開(kāi)并分析一個(gè)配置文件。它尋找對(duì)象標(biāo)識(shí)符并且調(diào)用合適的方法來(lái)分析對(duì)象。parsefile清空之前解析了的對(duì)象。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); 解析一個(gè)文件：configuration:getinstance().parsefile( gaschedule.cfg ) 除了課程類，解析的對(duì)象都被放在一個(gè)hash圖里，所以他們可以被快速輕易的訪問(wèn)private:hash_map _professors;hash_map _studentgroupshash_map _courseshash_map _rooms; list _courseclasses; configuration類也包含檢索已經(jīng)解析了的信息和對(duì)象的方法public:inline professor* getprofessorbyid(int id) /.inline int getnumberofprofessors() const /.inline studentsgroup* getstudentsgroupbyid(int id) /.inline int getnumberofstudentgroups() const /.inline course* getcourse