（交通信息工程及控制專業(yè)論文）基于遺傳算法的排課問題研究.pdf

西南交通大學(xué)碩士研究生學(xué)位論文第1 頁 摘要 排課問題是一個有約束、多目標(biāo)的組合優(yōu)化問題，已經(jīng)被證明是一個n p 完 全問題。遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的高度并行、 隨機(jī)、自適應(yīng)搜索算法，由于其具有健壯性，特別適合于處理傳統(tǒng)搜索算法解 決不好的復(fù)雜的和非線性問題。 本文將遺傳算法應(yīng)用于排課問題求解，首先討論了排課問題的影響要素、 主要約束條件、求解目標(biāo)和組合不確定性，建立了排課問題的數(shù)學(xué)模型；其次 根據(jù)排課問題的特點將課表編排分解為時間安排和教室安排兩部分 在時間安排中分兩個步驟進(jìn)行，一是對某一門課程的時間安排( 單目標(biāo)) ， 從中找到幾個近似最優(yōu)的安排方案，二是對所有課程集合的時間安排( 多目標(biāo)) ， 尋找所有課程安排的一個先后順序排列。然后在時間安排的基礎(chǔ)上對教室進(jìn)行 安排，提出了解決“甩課 問題的“回溯”調(diào)整方法。 本文討論的模型是遺傳算法在排課問題中一種很有效的應(yīng)用，隨著對此問 題越來越多的關(guān)注，相信遺傳算法一定可以更好的解決排課問題。 關(guān)鍵詞：排課問題；遺傳算法；數(shù)學(xué)模型；時間安排；教室安排；回溯調(diào)整 西南交通大學(xué)碩士研究生學(xué)位論文第1 i 頁 l-_-_-_-_-_l_-_-_-_i-i-_-，_-_-_l_-_-_-_-_一一 a b s t r a c t t i m e t a b l i n gp r o b l e m ( t t p )i sam u l t i 一0 d j e c t i v ec o m b i n a t i o n o p t i m i z a t i o np r o b l e mw i t hc o n s t r a i n t s ，a n da l s oh a sb e e np r o v e da sa n p c o m p l e t e dp r o b l e m ；g e n e t i ca l g o r i t h m ( g a ) i sah i g h e f f e c t i v e p a r a l l e l i n g p r o c e s s i n g ，r a n d o m l y s e a r c h i n g a n d s e l f a p p l i c a b l e a l g o r i t h mb a s e do nt h ed e v e l o p m e n to ft h en a t u r ee v o l u t i o na n do p t i o n d u et oi t ss t r e n g t h ，i ti s p a r t i c u l a r l ya p p l i c a b l et oo p e r a t et h e t r a d i t i o n a ls e a r c h i n ga l g o r i t h ma n dt a c k l e t h ec o m p l i c a t e dn o n l i n e a r p r o b l e m t h ea r t i c l ea p p l i e st h eg at ot h ec l a s st i m e t a b l i n g t h ed e t e r m i n a n t f a c t o r s ，1 i m i t e dc o n d i t i o n s ，t h es o l v i n go b j e c t i v e sa n du n c e r t a i n t yo f t h ec o m b i n a t i o nh a v eb e e nd is c u s s e dt os e tu pt h em a t h e m a t i c a lm o d u l e ： s e c o n d l yt h et i m e t a b l eh a sb e e nd i v i d e di n t ot h ea r r a n g e m e n to ft i m ea n d c l a s s r o o ma c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h ep r o b l e mo fc l a s s a r r a n g e m e n t t i m e t a b li n gi sb e i n gp r o c e s s e di nt w os t e p s ，t h ef i r s ti st oa r r a n g e t h et i m ef o rs i n g u l a rc o u r s e ( s o l o - o b j e c t i v e ) a n df i n do u ts e v e r a lm o s t o p t i m a ls o l u t i o n s ，t h es e c o n di st oa r r a n g et h et i m ef o ra l lt h ec o u r s e s ( m u l t i o b j e c t i v e s ) a n df i n do u tt h es e q u e n c e so fa llt h ec o u r s e s o nt h e b a s i so ft i m e t a b l e ，t h ec l a s s r o o m sw i i ib eo r g a n i z e da n dt h ea d j u s t m e n t a p p r o a c ho fd a t i n g b a c kw i l lb ep r o p o s e dt os o l v et h ep r o b l e mo fc h a o t i c c l a s sa r r a n g e m e n t t h em o d u l ed i s c u s s e di nt h ea r t i c l ei sa ne f f e c t i v ea p p l i c a t i o no f s o l v i n gt h ep r o b l e mo fa r r a n g i n gt h ec l a s s a st h em o r ef o c u s e sb e i n g d e v o t e dt ot h ep r o b l e m ，t h eg ai sb e li e v e dt oab e t t e ra p p r o a c h k e y , o r d s ：t h ep r o b l e m m a t h e m a tic a l m o d u l e ： d a tin g 。b a c ka d j u st m e n t o fc l a s sa r r a n g e m e n t ： t i m e a r r a n g e m e n t ： g e n e t i ca l g o r i t h m ( g a ) ： c l a s s r o o m a r r a n g e m e n t ： 西南交通大學(xué)曲南交通大罕 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定， 同意學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版， 允許論文被查閱和借閱。本人授權(quán)西南交通大學(xué)可以將本論文的全部 或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等 復(fù)印手段保存和匯編本學(xué)位論文。 本學(xué)位論文屬于 1 保密口，在年解密后適用本授權(quán)書； 2 不保密一使用本授放書。 ( 請在以上方框內(nèi)打“4 ) 學(xué)位論文作者簽名：制， 日期：搠，f 西南交通大學(xué)學(xué)位論文創(chuàng)新性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是在導(dǎo)師指導(dǎo)下獨立進(jìn)行研 究工作所得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含任 何其他個人或集體已經(jīng)發(fā)表或撰寫過的研究成果。對本文的研究做出 貢獻(xiàn)的個人和集體，均已在文中作了明確的說明。本人完全意識到本 聲明的法律結(jié)果由本人承擔(dān)。 本學(xué)位論文的主要創(chuàng)新點如下： 在閱讀了大量關(guān)于排課問題求解和經(jīng)典遺傳算法設(shè)計方法的基礎(chǔ) 上根據(jù)排課問題的特點將課表編排分解為時間安排和教室安排兩部 分。在時間安排過程中，為提高算法性能，對經(jīng)典遺傳算法做了部分 改進(jìn)，包括初始種群均勻化的改進(jìn)、對自適應(yīng)交叉和變異概率的改進(jìn) 以及對選擇、交叉、變異算子的改進(jìn)。在教室安排過程中提出了“回 溯 調(diào)整方法以解決“甩課 問題，并詳細(xì)介紹了“回溯 調(diào)整的兩 種方式。 西南交通大學(xué)碩士研究生學(xué)位論文第1 頁 第1 章排課問題概述 1 1 大學(xué)課程表問題的描述 1 1 1 時間表問題概述 時間表問題( t i m et a b l ep r o b l e m ) 既是一個理論方面的問題也是一個來源 于實踐的問題，它是人們實際生活中經(jīng)常遇到的問題。比如說交通時間表問題 ( t r a n s p o r t a t i o nt i m e t a b l i n g ) ，這個問題是如何設(shè)計城市中公交車或者有軌電車 的時間表問題，使其能夠良好的運行，減緩城市交通的壓力；比賽時間表問題 ( e m p l o y e et i m e t a b l i n g ) 是如何設(shè)計一項大型賽事的時間表，來保證大型賽事能夠 良好的進(jìn)行；還有雇員工作時間表問題( e m p l o y e et i m e t a b l i n g ) ，研究的是如何來 安排雇員的工作，使其工作能夠達(dá)到最高的效率；當(dāng)然還有我們要研究的大學(xué) 課程表問題，這個問題研究的主要目的是提出一種優(yōu)秀的算法最大程度上使大 學(xué)課程安排人性化，合理化。 時間表問題是一類具有多約束的將有限時間資源分配給多個事件組合優(yōu)化 問題。通常，一個時間表問題會有一系列事件( e v e n t ) 和一組有限的時間單元 ( t i m e s l o t ) 和一組具體地點，并且還要受到一系列約束條件的限制，這些約束又 分為硬約束和軟約束。硬約束就是一系列的限制，我們在進(jìn)行時間表安排的情 況下必須無條件滿足、不能有任何違反；而軟約束也是一系列的限制，但是我 們不一定要全部滿足，但是這些軟約束的滿足情況卻決定了我們時間表安排的 合理情況。 1 1 2 時間表問題的一般數(shù)學(xué)模型 在時間表問題中n 6 1 ，設(shè)給定n 個項目和m 個資源，用吒表示將第i 個項目 分配給第j 個資源的代價，則所求問題為決定一個項目到資源的最優(yōu)分配，使 得總的代價最小且滿足k 個附加條件，即： 西南交通大學(xué)碩士研究生學(xué)位論文第2 頁 m i n f ( x ) = 辦嘞， 且嘞以，1 k k ， 她勃= 三硼囂黼，知刑引，表猻個附 加代價。 大學(xué)課程表問題概述 本文主要討論的是時間表問題中的大學(xué)課程表問題。這個問題是來源于大 學(xué)日常生活，和大學(xué)生的日常生活息息相關(guān)。隨著大學(xué)擴(kuò)招的進(jìn)行，學(xué)生的數(shù) 量急劇增加，學(xué)校的教育資源顯得越來越有限，這個問題就顯得越發(fā)突出，所 以對這個問題的研究具有現(xiàn)實意義，但是它又不缺乏理論性。1 9 7 5 年，s 。e v e n 對該問題進(jìn)行了研究，并指出大學(xué)課程表問題是一個n p 完全問題，這就說明 了該問題沒有真正意義上的最優(yōu)解，人們的求解只有可能是相似最優(yōu)解，也就 是說求解獲得的答案只可能不斷接近最優(yōu)解，但是不可能是最優(yōu)解。于是人們 就嘗試用各種方法去解決這個問題，如圖著色、分支定界、整數(shù)規(guī)劃等。經(jīng)過 實踐證明，遺傳算法和模擬退火算法是兩種解決該問題比較理想的方法。本文 在后面主要著重介紹遺傳算法。 那什么是大學(xué)課程表問題? 雖然已經(jīng)從感性上已經(jīng)了解了這個問題，但是 下面將給出一個較為嚴(yán)格的定義方便深入理性的理解這個問題。c a r t e r 和 l a p o r t e 這樣定義：“大學(xué)課程表問題是一個多元分配問題，它研究的就是如何 把學(xué)生和老師分配給課程、課程單元或者班級，如何把事件( 上課事件) 分配 給教室和時間?！毕旅鏋樵? 7 1 ： “am u l t i d i m e n s i o n a la s s i g n m e n tp r o b l e mi nw h i c hs t u d e n t s ，t e a c h e r s ( o rf a c u l t y m e m b e r s ) a l ea s s i g n e dt oc o u r s e s ，c o u r s es e c t i o no rc l a s s e s ；e v e n t s ( i n d i v i d u a l m e e t i n g sb e t w e e ns t u d e n t sa n dt e a c h e r s ) a l ea s s i g n e dt oc l a s s r o o m sa n dt i m e s 簡單一些的說，大學(xué)課程表問題研究的就是如何把一系列的課程分給有限 的教室和一周內(nèi)有限的上課時間單元，如何把學(xué)生和老師分配給課程。當(dāng)然實 際研究的時候并沒有理論上說得這么簡單，它會受到多種約束的影響，有硬約 束也有軟約束。 西南交通大學(xué)碩士研究生學(xué)位論文第3 頁 圖1 1 簡要的表示了課程表問題的邏輯模型： 圖1 1 課表問題的邏輯模型 1 2 大學(xué)課程表問題的研究情況 1 2 1 大學(xué)課程表問題的理論研究 大學(xué)課程表問題在2 0 世紀(jì)5 0 年代末就已經(jīng)開始被人們所重視，將它作為 一個科學(xué)問題來研究，但是一直到1 9 6 3 年才由c c g o t l i e b 提出了該問題的數(shù) 學(xué)模型和形式化描述，這標(biāo)志著排課問題正式被作為科學(xué)問題來被人們所研究， 到了1 9 7 6 年s e v e n 【2 】在他的論文o nt h ec o m p l e x i t yo ft i m e t a b l ea n d m u l t i - c o m m o d i t yf l o wp r o b l e m s ) ) 中提出并證明大學(xué)課程表問題是一個n p 完全 問題，把該問題理論化，同時也說明該問題有解，并能夠找到解。但是根據(jù)計 算機(jī)難解性理論，目前還沒有解決n p 完全問題的多項式算法。到1 9 7 9 年， s c h m i d t 和s t r o h e i m 在文獻(xiàn)中就列出了3 0 0 多篇有關(guān)大學(xué)課程表問題的已發(fā)表文 獻(xiàn)。 進(jìn)入2 0 世紀(jì)9 0 年代，國外對排課問題的研究仍然非?；钴S。如印度 v a s t a p u r 大學(xué)管理學(xué)院的a i a b i n d at r i p a t h y 、加拿大m o n t r e a l 大學(xué)的j e a na u b i n 和j a c q u e sa f e r l a n d 以及c h a r l e sf l e u t e n t 等。a r a b i n d at r i p a t h y 的工作是針對 以“人”為單位進(jìn)行課表編排的，他運用拉格朗日松弛法和分支定界技術(shù)求解， 這種方法的缺點是為了減少變量的個數(shù)，人為造成科目間的沖突。a t r i p a t h y 6 i 研究了研究生課表編排問題，他采用多重課組的方法來處理沖突( 即根據(jù)學(xué)生 西南交通大學(xué)碩士研究生學(xué)位論文第4 頁 選課的矛盾情況，將人數(shù)多的課程在一星期內(nèi)開多次) 。j a c q u e sa f e r l a n d 等人 則把排課問題分成兩個子問題：時間表問題和分組問題。在時間表問題中，根 據(jù)學(xué)生注冊情況、教師和教室的可利用情況形成一個主時間表，對于選課人數(shù)較 多的大課，一個星期要分成幾個時間段來上；分組問題就是將學(xué)生分給各時間 段：兩個問題相關(guān)聯(lián)，通過懲罰因子來構(gòu)造啟發(fā)函數(shù)。他們研制的s a p h i r 課 程調(diào)度決策支持系統(tǒng)分為數(shù)據(jù)處理、自動優(yōu)化、交互優(yōu)化等幾個模塊，該系統(tǒng) 解決矛盾的主要方法也是采用多重課組，這與西方的教學(xué)管理體制不可分的。 1 2 2 大學(xué)課程表問題的常用解決方法 至今已經(jīng)有很多算法被拿來研究用于嘗試解決該問題。起初，圖論是研究 大學(xué)課程表問題的一個主要武器，圖著色技術(shù)被廣泛的用來嘗試解決該問題。 如1 9 9 4 年，b u r k e ，e l l i m a n 和w e a r e 就研究出一種啟發(fā)式的圖著色方法，該方 法把考試進(jìn)程分成若干組，然后把它們放在一起安排，以求找到一種能夠解決 考試時間表問題的方法。但是圖著色技術(shù)本身就是一個n p 完全問題，所以對 解決該問題幫助不大。后來c a r t e rm w 和l a p o r t e 嘗試采用按序分派的方法解 決該問題，這種方法需要按啟發(fā)順序把事件分出先后順序，然后再嘗試尋找一 個可行的解決方案。f e d a n d 等人和吳金榮1 2 0 1 把排課問題轉(zhuǎn)化成整數(shù)規(guī)劃問題來 解決，但計算量很大，只適合一些理論中的簡單情況，對于解決復(fù)雜問題是不 可行的。許多文章試圖利用啟發(fā)式函數(shù)來解決排課問題，但是大多數(shù)啟發(fā)方法 都是模擬手工排課的過程來實現(xiàn)的，而由于實際的排課問題存在各種各樣的限 制條件與特殊要求，處理不好這些限制和要求就無法找到理想的排課方案。 最近，后啟發(fā)式算法被引入大學(xué)課程表問題，而且在一定程度上獲得成功， 在解決大學(xué)課程表問題上取得了不錯的成績。后啟發(fā)式算法主要包括三種：禁 忌搜索( t a b us e a r c h ) ，模擬退火算法( s i m u l a t e da n n e a l i n g ) 和進(jìn)化算法 ( e v o l u t i o n a r ya l g o r i t h m s ) ( 遺傳算法) 。 1 禁忌搜索( t a b us e a r c h ) 禁忌搜索是一種主要研究具有各種特殊要求的真實世界時間表問題的算 法。它由g l o v e r 在1 9 8 6 年提出，進(jìn)而慢慢形成一種獨特而又完整的算法。研 究表明：這種算法如果能夠正確恰當(dāng)選擇參數(shù)( 禁忌列表，初始化解決方案和 目標(biāo)函數(shù)) ，那么它在解決大學(xué)課程表問題上將有很出色的表現(xiàn)。1 9 9 8 年， n o n o b e 和i b a r a k i 開發(fā)出一種基于禁忌搜索的處理一般問題解決系統(tǒng)，這種系 統(tǒng)對于滿足約束問題特別是高中課程表問題有著出人意料的良好效果。后來在 西南交通大學(xué)碩士研究生學(xué)位論文第5 頁 2 0 0 2 年，a l v a r e z v a l d e s ，c r e s p o 和t a m a r i t 研制出了一種基于禁忌搜索的具有友 好界面的系統(tǒng)，這個系統(tǒng)經(jīng)過一系列實驗也取得不錯成績。現(xiàn)在關(guān)于這項技術(shù) 的研究還在繼續(xù)，我們這里就不再贅述了。 2 模擬退火算法( s i m u l a t e da n n e a l i n g ) 模擬退火算法是一種被廣泛研究的算法，也經(jīng)常被用來解決時間表問題和 大學(xué)課程表問題，是一種模擬固體退火過程的算法。它由k i r k p a t r i c k 等人于1 9 8 2 年提出，后來就專門用來解決大規(guī)模組合優(yōu)化問題，它是一種解決n p 完全組 合優(yōu)化問題的有效的近似算法?，F(xiàn)在一些研究表明，模擬退火算法在課程表問 題和考試時間表問題上的實現(xiàn)是高度依賴于各種設(shè)定與參數(shù)( 解決方案空間， 降溫時間表，鄰居產(chǎn)生和評估函數(shù)) ，因此使用這種算法的時候需要謹(jǐn)慎的選擇 參數(shù)。 3 進(jìn)化算法( e v o l u t i o n a r ya l g o r i t h m s ) 進(jìn)化算法和遺傳算法現(xiàn)在已經(jīng)被廣泛用來研究時間表問題和大學(xué)課程表問 題。遺傳算法最早是由c o l o m i 等人在9 0 年代初期引入用來解決課程表問題的， 一開始他們引進(jìn)了矩陣表示方案和交叉，變異算子，后來c o l o m i 又把遺傳算法 成功應(yīng)用到米蘭一所較大的學(xué)校的課程排布問題中。p a e c h t e r 等人對t t p 問題 進(jìn)行了研究，提出了時域置換法和放置查找法，并針對較大規(guī)模的實際t t p 問 題比較了這二種算法的性能。b u r k e 對將進(jìn)化算法分階段的用于u t p 問題做了 初步的研究，得到一些頗有價值的成果。c h u p c 和b e a s l e y 對一般的時間安排 問題中使用了遺傳算法進(jìn)行求解，他們著重于遺傳算法的全局最優(yōu)解的搜索能 力，避免了問題的局部最優(yōu)解。日本的s i g e r u t 2 2 l 用具有控制約束的遺傳算法來 解決大學(xué)排課問題，提高了遺傳算法的搜索效率。姚新使用遺傳算法優(yōu)化了教 師的合理利用，解決了在教室較少的情況下，如何對教室的利用進(jìn)行合理的分 配。針對高中課程的特點，意大利的c o l o m i1 2 7 1 等人使用遺傳算法解決了排課 問題。張春梅【2 4 l 等人對大學(xué)課程進(jìn)行分類，并對不同的課程使用具有自適應(yīng)能 力的遺傳算法進(jìn)行了安排。p h i l i p p i n e s 的h os u n g c l e e 使用遺傳算法對 p h i l i n p i n e s 大學(xué)的數(shù)學(xué)學(xué)院排課問題進(jìn)行了求解。楊宇l t i 對分別使用遺傳算法 對局部排課問題和全局排課問題進(jìn)行了求解。 另外基于知識學(xué)習(xí)的技術(shù)也漸漸的參與到對于時間表問題和課程表問題的 求解上來。基于知識學(xué)習(xí)的技術(shù)是一種模仿人類思維過程的技術(shù)，人類在解決 問題的時候總是先在大腦中尋找一個相似的問題，然后對這個相似問題進(jìn)行分 析學(xué)習(xí)，然后對這個相似問題進(jìn)行改進(jìn)以求獲得當(dāng)前新問題的解決方案。這種 技術(shù)有一個很至關(guān)的重要問題，就是如何能清晰地表示經(jīng)驗和知識，并將其存 西南交通大學(xué)碩士研究生學(xué)位論文第6 頁 入知識庫以便后來之用。這種技術(shù)主要包括兩種：一種是基于規(guī)則的專家系統(tǒng) 瞵j ，另一種是基于案例推理的系統(tǒng)( c a s e b a s e dr e a s o n i n g c b r ) 。現(xiàn)在大多數(shù)用 來解決時間表問題的基于知識學(xué)習(xí)的系統(tǒng)都是基于規(guī)則的，很少有基于案例推 理的系統(tǒng)。但是用基于案例推理的技術(shù)來解決時間表問題有自己很大的優(yōu)勢。 r o n gq u ，b s c 在2 0 0 2 年8 月提出了用基于案例推理的技術(shù)來解決時間表問題， 并在其論文中詳細(xì)講述了該技術(shù)的優(yōu)點。 1 3 排課問題各種算法的比較 至今為止有很多的方法技術(shù)和算法都已經(jīng)被用來嘗試解決時間表問題或者 大學(xué)課程表問題，他們效果各異，有的完成很出色，有的則只在某些特定情況 下才能有不錯的效果。傳統(tǒng)的算法比如說圖論和整數(shù)規(guī)劃在應(yīng)付簡單時間表問 題和課程表問題時可以較容易的編碼，通常情況下可以圓滿地完成任務(wù)。但是 他們通常對于大型的復(fù)雜約束時間表或者課程表問題顯得束手無策。人工智能 領(lǐng)域的全局搜索技術(shù)包括( 遺傳算法，禁忌搜索，還有模擬退火算法) 在各個 問題領(lǐng)域都取得了很不錯的效果。他們都能夠處理各個級別的問題，既可以是 簡單的問題，也可以是復(fù)雜的大型問題。但是他們也有自己的問題需要注意， 在使用他們的時候不同場合參數(shù)的初始化往往不同，這是一個既重要而又難以 處理的問題。研究表明基于后啟發(fā)方式的混合算法，在處理問題時候往往會比 單獨一種算法有更好的更出色的效果。 可以看出后啟發(fā)式算法是解決時間表問題和大學(xué)課程表問題各種算法中的 翹楚。但是當(dāng)他們之間作比較的時候，一些研究表明，當(dāng)算法使用的環(huán)境不同， 表示的方法不同和選擇的算子不同的時候他們往往會有完全不同的表現(xiàn)。1 9 9 5 年，r o s s 和c o m e 在解決一個時間表問題時，對遺傳算法，模擬退火算法和隨 機(jī)爬山算法進(jìn)行比較后得出結(jié)論：隨機(jī)爬山算法在解決問題的質(zhì)量上略勝一籌。 c o l o m i ，d o r i g o 和m a n i e z z o 在1 9 9 8 年對遺傳算法，模擬退火算法，禁忌搜索 和輔以局部搜索的遺傳算法進(jìn)行比較，得出結(jié)論禁忌搜索的效果更佳，但是輔 以局部搜索的遺傳算法給出了一系列的高質(zhì)量解決方案，給用戶更多的靈活性， 以滿足各種不同的要求。雖然在不同的環(huán)境下，各種后啟發(fā)算法會有不同的表 現(xiàn)，但是大家都一致認(rèn)為遺傳算法在解決現(xiàn)實生活中問題的時候具有足夠的靈 活性，可以給出一系列的較優(yōu)解以滿足人們各種方面不同的需要。本文將著重 研究的就是遺傳算法，一種改進(jìn)的混合算法，希望能夠?qū)鉀Q時間表問題有較 好的作用。 西南交通大學(xué)碩士研究生學(xué)位論文第7 頁 1 4 本文的主要研究內(nèi)容 由于排課問題是一個有約束、多目標(biāo)的組合優(yōu)化問題，屬于n p 完全問題， 無真正意義上的最優(yōu)解。而遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā) 展起來的高度并行、隨機(jī)、自適應(yīng)搜索算法，由于其具有健壯性，特別適合于 處理傳統(tǒng)搜索算法解決不好的復(fù)雜的和非線性問題。因此采用具有智能性和并 行性的遺傳算法來對排課問題進(jìn)行考慮以求獲得近似最優(yōu)解，是求解該問題的 眾多方法中的一個比較明智的選擇。本文將遺傳算法應(yīng)用于排課問題求解，主 要做下面的工作： 1 、介紹排課問題的各種算法及其比較以及經(jīng)典遺傳算法的一些基本原理及 其缺陷和改進(jìn)方法。 2 、分析排課問題的各種影響要素、約束條件及其求解難度和求解目標(biāo)，給 出排課問題的完整數(shù)學(xué)描述，并提出求解排課問題的總體思路和技術(shù)路線。 3 、根據(jù)排課問題的特點放棄尋找“絕對最優(yōu)”轉(zhuǎn)而尋求“相對最優(yōu)，考 慮將排課問題分解為時間安排和教室安排兩部分。在課程的時間安排部分又分 解為單門課程的時間安排和這個課程集的時間安排。 4 、為提高算法性能，對經(jīng)典遺傳算法做部分改進(jìn)，如初始種群的產(chǎn)生、交 叉和變異概率的改進(jìn)以及對選擇、交叉、變異算子的改進(jìn)。 5 、在教室安排部分找到解決“甩課”問題的方法。 6 、利用m a r l a b 軟件進(jìn)行仿真說明算法的可行性和有效性。 西南交通大學(xué)碩士研究生學(xué)位論文第8 頁 第2 章遺傳算法簡介 排課過程主要分為時間安排和教室安排兩個部分，這兩部分都非常重要， 套好的課表不但應(yīng)該具有合理的時間安排，而且也應(yīng)該具有合理的教室安排。 下面我們首先討論排課問題中的時間分配問題。 課表問題是一個組合規(guī)劃問題，它同樣是一個多目標(biāo)的優(yōu)化問題，對于這 類問題，隨著問題規(guī)模的擴(kuò)大，很難甚至不可能求得最優(yōu)解，我們的主要精 力應(yīng)該放在尋求滿意解上，而遺傳算法則是尋求這種滿意解的最佳工具之一。 實踐證明，遺傳算法對于組合優(yōu)化中的n p 完全問題非常有效，它對經(jīng)典的貨郎 擔(dān)問題( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 、背包問題、作業(yè)調(diào)度問題等 都有非常成功的應(yīng)用。 因此，這里我們設(shè)計的時間安排算法就是基于經(jīng)典的遺傳算法進(jìn)行了部分 改進(jìn)而形成的。首先我們簡單介紹一下經(jīng)典的遺傳算法。 2 1 遺傳算法簡介 遺傳算法( g e n e t i ca l g o r i t h m s ，g a ) 是一種借鑒生物界自然選擇和進(jìn) 化機(jī)制發(fā)展起來的高度并行、隨機(jī)、自適應(yīng)的隨機(jī)搜索算法。由于其具有健壯 性，特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜的和非線形問題。簡單的講， 它使用了群體搜索技術(shù)，將種群代表一組問題解，通過對當(dāng)前種群施加選擇、 交叉、變異等一系列遺傳操作，從而產(chǎn)生新一代的種群，并逐步使種群進(jìn)化到 包含近似最優(yōu)解的狀態(tài)。 2 1 1 遺傳算法的發(fā)展 6 0 年代，h o l l a n d 教授提出在研究和設(shè)計人工自適應(yīng)系統(tǒng)時，可以借鑒生物 的遺傳機(jī)制，以群體的方式進(jìn)行自適應(yīng)搜索；1 9 6 7 年，h o l l a n d 的學(xué)生b a g l e y 在他的博士論文中首次提出了遺傳算法一詞，并發(fā)展了復(fù)制、交叉、差異、 顯性、倒位等遺傳算子。7 0 年代初，h o l l a n d 教授提出了遺傳算法的基本定理 模式定理，奠定了遺傳算法的理論基礎(chǔ)。1 9 7 5 年，h o l l a n d i l 出版了第一部系統(tǒng) 論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著自然系統(tǒng)和人工系統(tǒng)的適配 西南交通大學(xué)碩士研究生學(xué)位論文第9 頁 ( a d a p t a t i o ni nn a t u r a la n da t i f i c i a ls y s t e m s ) ) ) ，同年，美國d ej o n g 博士在其論 文遺傳自適應(yīng)系統(tǒng)的行為分析中將選擇、交換和變異操作進(jìn)一步完善和系 統(tǒng)化，同時提出了諸如代溝等新的遺傳操作技術(shù)，建立了著名的d ej o n g 五函 數(shù)測試平臺。 8 0 年代，h o l l a n d 教授實現(xiàn)了第一個基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)分類系 統(tǒng)，開創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念，為分類器的構(gòu)造提出了一個完 整的框架。1 9 8 9 年，g o l d b e r g t l 3 j 出版了專著遺傳算法在搜索優(yōu)化和機(jī)器學(xué)習(xí) 中的應(yīng)用( g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) ) ) 系 統(tǒng)總結(jié)了遺傳算法的主要成果，對遺傳算法的基本原理及應(yīng)用做了比較詳細(xì)、 全面的論述，奠定了現(xiàn)代遺傳算法的理論和應(yīng)用基礎(chǔ)，形成了遺傳算法的基本 框架。此后，許多學(xué)者對原來的遺傳算法進(jìn)行了大量改進(jìn)和發(fā)展，提出了許多 成功的遺傳算法模型，從而使遺傳算法應(yīng)用于更廣泛的領(lǐng)域。 進(jìn)入9 0 年代后，遺傳算法作為一種實用、高效、魯棒性強的優(yōu)化技術(shù)，發(fā) 展極為迅速，在各種不同領(lǐng)域中得到廣泛應(yīng)用，引起了許多學(xué)者的關(guān)注。在最 近興起的人工生命、遺傳編程、進(jìn)化策略、進(jìn)化計算等領(lǐng)域中，研究人員將遺 傳算法與計算機(jī)科學(xué)相結(jié)合，試圖模擬自然界的自適應(yīng)、自組織和再生能力， 設(shè)計出具有生命的人工系統(tǒng)。 1 9 9 2 年，學(xué)者k o z a 將遺傳算法應(yīng)用于計算機(jī)程序的優(yōu)化設(shè)計提出了遺傳 編程的概念，他把語言程序作為遺傳群體中的個體，把問題的解編碼為一棵樹， 對樹組成的群體進(jìn)行遺傳運算，最終生成性能較好的計算機(jī)程序，并成功的把 他提出的遺傳編程方法運用于人工智能、機(jī)器學(xué)習(xí)、符號處理等方面。 現(xiàn)在無論是對遺傳算法的理論研究還是應(yīng)用研究都分外活躍。從1 9 8 5 年開 始每兩年舉辦一屆遺傳算法的國際會議、麻省理工學(xué)院從1 9 9 3 年開始出版的進(jìn) 化計算和自適應(yīng)性行為兩種雜志、i e e e 從2 0 0 0 年起出版的專門關(guān)于進(jìn) 化計算的會刊，國內(nèi)外有關(guān)遺傳算法的研究熱潮正方興未艾。 2 1 2 遺傳算法的基本思想 遺傳算法是從代表問題可能潛在解集的一個種群( p o p u l a t i o n ) 開始的， 而一個種群則由經(jīng)過基因( g e n e ) 編碼( c o d i n g ) 的一定數(shù)目的個體( i n d i v i d u a l ) 組成。每個個體實際上是染色體( c h r o m o s o m e ) 帶有特征的實體。染色體作為 遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)是某種基因組合，它決定 了個體的外部表現(xiàn)。初始種群產(chǎn)生以后，按照適者生存和優(yōu)勝劣汰的原理，逐 西南交通大學(xué)碩士研究生學(xué)位論文第1 0 頁 代( g e n e r a t i o n ) 演化產(chǎn)生出越來越好的近似解。在每一代，根據(jù)問題域中個 體的適應(yīng)度( f i t n e s s ) 大小選擇( s e l e c t i o n ) 個體，并借助于自然遺傳學(xué)的 遺傳算子( g e n e t i co p e r a t o r s ) 進(jìn)行組合交叉( c r o s s o v e r ) 和變異( m u t a t i o n ) ， 產(chǎn)生出代表新的解集的種群。這個過程將導(dǎo)致種群象自然進(jìn)化一樣，后代種群 比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼( d e c o d i n g ) ，可以 作為問題的近似最優(yōu)解。 遺傳算法采納了自然進(jìn)化模型，如選擇、交叉、變異、遷移、局域與鄰域 等。在算法計算開始時，隨機(jī)產(chǎn)生一定數(shù)目的n 個個體( 父個體1 、父個體2 、 父個體3 、) 即種群隨機(jī)的初始化，并計算每個個體的適應(yīng)度，第一代也即 初始代產(chǎn)生。如果不滿足優(yōu)化準(zhǔn)則，則開始產(chǎn)生新一代的計算。為產(chǎn)生下一代， 按照適應(yīng)度選擇個體，父代通過基因重組( 交叉) 而產(chǎn)生子代，所有子代按一 定概率變異，然后子代的適應(yīng)度又被重新計算，子代被插入到種群中將父代取 而代之，構(gòu)成新的一代( 子個體1 、子個體、子個體3 、) ，這一過程循環(huán) 執(zhí)行，直到滿足優(yōu)化準(zhǔn)則為止。 可以看出，與傳統(tǒng)搜索算法不同，遺傳算法是從一組隨機(jī)產(chǎn)生的初始解開 始搜索過程。種群中的每個個體是問題的一個解，稱為“染色體”，染色體是一 串符號，比如二進(jìn)制0 l 串。這些染色體在后續(xù)迭代中不斷進(jìn)化，稱為遺傳。在 每一代中用適應(yīng)度( f i t n e s s ) 來測量染色體的好壞。生成的下一代染色體稱 為后代( o f f s p r i n g ) 。后代是由前一代染色體通過交叉( c r o s s o v e r ) 或者變 異( m u t a t i o n ) 運算形成的。新一代形成中，根據(jù)適應(yīng)度的大小選擇部分后代， 淘汰部分后代，從而保持種群大小的穩(wěn)定性。適應(yīng)度高的染色體被選中的概率 高，這樣，經(jīng)過若干代之后，算法收斂于最好的染色體，它很可能就是問題的 最優(yōu)解或次優(yōu)解。 2 1 3 遺傳算法的一般結(jié)構(gòu) 圖2 - 1 表示了基本遺傳算法的一般結(jié)構(gòu)。由圖可以看出，最佳個體是這樣 產(chǎn)生的：首先產(chǎn)生一個初始種群，然后對這個種群中的每一個個體進(jìn)行適應(yīng)度 計算。計算后的個體進(jìn)行是否滿足優(yōu)化準(zhǔn)則判定，如果滿足，那么算法找到了 這個個體并停止，如果不滿足準(zhǔn)則，那么算法將對這個種群進(jìn)行選擇、復(fù)制( p r ) 、 交叉( p c ) 、變異操作( p m ) 。遺傳操作的目的是從初始種群中篩選出較優(yōu)異的個 體進(jìn)行演變，這其中包括復(fù)制優(yōu)秀個體重生、兩個父個體進(jìn)行交叉和單個個體 的變異三種方式，對演變后的子代群體，重新進(jìn)行優(yōu)化準(zhǔn)則判定，如此循環(huán)下 西南交通大學(xué)碩士研究生學(xué)位論文第1 1 頁 去，直到找到一個最優(yōu)個體或達(dá)到其他循環(huán)條件。 圖9 - i 遺傳算法的一般結(jié)構(gòu) 2 i 4 遺傳算法的基本操作 1 編碼( e n c o d i n g ) 遺傳算法中進(jìn)化過程是建立在編碼機(jī)制基礎(chǔ)上的，編碼對于算法的性能如 搜索能力和種群多樣性等影響很大。如何將問題的解轉(zhuǎn)換為編碼表達(dá)的染色體 是遺傳算法的關(guān)鍵問題。h o l l a n d 的編碼方法是二進(jìn)制o 、1 串表達(dá)，其優(yōu)點 是編碼、解碼操作簡單，交叉、變異等遺傳操作便于實現(xiàn)，而且便于利用模式 定理進(jìn)行理論分析等；其缺點是不便于反映所求問題的特定知識，對于一些連 續(xù)函數(shù)的優(yōu)化問題，由于遺傳算法的隨機(jī)特性而使其局部搜索能力較差，對于 一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化，二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時 西南交通大學(xué)碩士研究生學(xué)位論文第12 頁 的映射誤差，個體編碼串較短時，可能達(dá)不到精度要求；個體編碼長度較長時， 雖然能提高精度，但卻會使算法的搜索空間急劇擴(kuò)大，從而造成遺傳算法的性 能降低。 在設(shè)計和選擇編碼方法主要考慮以下一些特性： 完全性，原則上分布在所有問題域的解都可能構(gòu)造出來； 封閉性，每個基因編碼對應(yīng)一個可接受的個體，保證算法不產(chǎn)生無效個體； 緊致性，若基因編碼l 和2 都被解碼成相同的個體，若1 比2 占的空間少， 則認(rèn)為1 比2 緊致； 可擴(kuò)展性，若增加一種表現(xiàn)型，則基因型的編碼大小也相應(yīng)的增加； 多重性，多個基因型解碼成一個表現(xiàn)型( 基因多重性) ，相同的基因型被解 碼成不同的表現(xiàn)型( 表現(xiàn)多重性) ： 個體可測性，決定表現(xiàn)型與相應(yīng)基因型是受環(huán)境影響的； 模塊性，若表現(xiàn)型的構(gòu)成中有多個重復(fù)的結(jié)構(gòu)，在編碼中應(yīng)避免這種重復(fù)； 冗余性，能提高算法可靠性和魯棒性； 復(fù)雜性，包括基因型的結(jié)構(gòu)復(fù)雜性、解碼復(fù)雜性、計算時空復(fù)雜性( 基因 解碼、適應(yīng)度、再生等) 其中滿意的特性為完全性、可測性和復(fù)雜性。 2 群體設(shè)定( c o l o n ys e t t i n g ) 遺傳算法對眾多個體同時進(jìn)行，這眾多個體組成群體。在遺傳算法流程中， 繼編碼設(shè)計后的任務(wù)是初始群體的設(shè)定，并以此為起點一代代進(jìn)化直到滿足優(yōu) 化準(zhǔn)則終止進(jìn)化過程，得到最后一代( 群體) 。 3 選擇( s e l e c t i o n ) 選擇是用來確定重組或交叉?zhèn)€體，以及被選個體將產(chǎn)生多少個子代個體。首 先需要計算適應(yīng)度，適應(yīng)度計算之后是實際的選擇，按照適應(yīng)度進(jìn)行父代個體 的選擇。選擇算法現(xiàn)在主要有： 輪盤賭選擇( r o u l e t t ew h e e ls e l e c t i o n ) 隨機(jī)遍歷抽樣( s t o c h a s t i cu n i v e r s a ls a m p l i n g ) 局部選擇( 1 0 c a ls e l e c t i o n ) 截斷選擇( t r u n c a t i o ns e l e c t i o n ) 錦標(biāo)賽選擇( t o u r n a m e n ts e l e c ti o n ) 在選擇操作時會出現(xiàn)幾個問題： 在遺傳進(jìn)化的初期，通常會產(chǎn)生一些超常的個體，這些異常個體競爭力很突 出，從而控制了選擇過程，影響算法的全局優(yōu)化性能。 西南交通大學(xué)碩士研究生學(xué)位論文第13 頁 在遺傳進(jìn)化的后期，即算法接近收斂時，由于種群中個體適應(yīng)度差異較小時， 繼續(xù)優(yōu)化的潛能降低，可能獲得某個局部最優(yōu)解，這不是我們所期待的。 上述的問題，我們通常稱為遺傳算法的欺騙問題，而適應(yīng)度函數(shù)的設(shè)置就 是為了避免這些問題的產(chǎn)生。 4 適應(yīng)度函數(shù)( f i t n e s sf u n c t i o n ) 遺傳算法在進(jìn)化搜索中基本不利用外部信息，僅以適應(yīng)度函數(shù)為依據(jù)，利 用種群中每個個體的適應(yīng)度值來進(jìn)行搜索。因此適應(yīng)度函數(shù)的選取至關(guān)重要， 直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應(yīng)度函數(shù) 是由目標(biāo)函數(shù)變換而成的。適應(yīng)度函數(shù)基本有以下三種： ( 1 ) 直接將待求解的目標(biāo)函數(shù)轉(zhuǎn)化為適應(yīng)度函數(shù)，即： 若目標(biāo)函數(shù)為最大化問題f i t ( f ( x ) ) = 廠( x ) 若目標(biāo)函數(shù)為最小化問題f i t ( f ( x ) ) = - 廠( x ) 這種適應(yīng)度函數(shù)簡單直觀，但存在兩個問題，其一是可能不滿足常用的輪 盤賭選擇中概率非負(fù)的要求，其二是某些待求解的函數(shù)在函數(shù)值分布上相差很 大，由此得到的平均適應(yīng)度可能不利于體現(xiàn)種群的平均性能，從而影響算法的 性能。( 2 ) 若目標(biāo)函數(shù)為最小問題， w ，= 卜 若目標(biāo)函數(shù)為最大問題， 剛，= p 產(chǎn) 廠( x ) c n 血 其他 ，其中c 一是f ( x ) 的最大值估計。 ，其中c 曲是f ( x ) 的最小值估計。 這種方法是對第一種方法的改進(jìn)，可以稱為“喬限構(gòu)造法 ，但有時存在界 限值預(yù)先估計困難、不可能精確的問題。 ( 3 ) 若目標(biāo)函數(shù)為最小問題， f i t ( f ( x ) ) = 百巧1 麗 若目標(biāo)函數(shù)為最大問題， f i t ( f ( x ) ) = 志 c 0 ，c + 廠( x ) 0 c o , c 一廠( x ) 0 這種方法與第二種方法類似，c 為目標(biāo)函數(shù)界限的保守估計值。 適應(yīng)度函數(shù)的設(shè)計應(yīng)該滿足以下幾個條件，它應(yīng)該是非負(fù)、連續(xù)、最大化、 單值；能夠反映解的優(yōu)劣程度；應(yīng)該盡量簡單，計算量盡量?。煌ㄓ眯詮姟?5 交叉或基因重組( c r o s s o v e ro rr e c o m b i n a t i o n ) 西南交通大學(xué)碩士研究生學(xué)位論文第14 頁 基因重組是結(jié)合來自父代交配種群中的信息產(chǎn)生新的個體。重組的目的是 為了能夠在下一代產(chǎn)生新的個體，是獲取新優(yōu)良個體最重要的手段：通過交叉 重組操作，遺傳算法的搜索能力得以飛躍的提高。依據(jù)個體編碼表示方法的不 同，可以有實值重組和二進(jìn)制交叉兩種算法。其中，實值重組又有離散重組、 中間重組、線性重組、擴(kuò)展線性重組等；二進(jìn)制交叉又有單點交叉、多點交叉、 均勻交叉、洗牌交叉、縮小代理交叉等。 6 變異( m u t a t i o n ) 交叉之后子代經(jīng)歷的變異，實際上是子代基因按小概率擾動產(chǎn)生的變化。 依據(jù)個體編碼表示方法的不同，可以有實值變異和二進(jìn)制變異兩種算法。 2 2 傳統(tǒng)遺傳算法存在的缺陷及改進(jìn) 隨著理論和應(yīng)用研究的日益深入，研究者們已經(jīng)意識到，簡單采用固定不 變的進(jìn)化策略的遺傳算法對復(fù)雜的應(yīng)用場合效果并不理想，傳統(tǒng)的遺傳算法逐 漸暴露出一些缺點。為提高遺傳算法的性能，許多研究者己經(jīng)致力于對這些問 題的研究，并提出了一系列有效的解決方案。 2 2 1 初始種群的均勻化改進(jìn) 初始種群的特性對遺傳算法的計算結(jié)果和計算效率均有重要影響，要實現(xiàn) 全局最優(yōu)，初始種群在解空間中應(yīng)盡量分散。而傳統(tǒng)的遺傳算法中，初始種群 是隨機(jī)產(chǎn)生的，這種隨機(jī)性就可能導(dǎo)致初始種群在解空間分布的不均勻，從而 影響算法的性能。 因此，在產(chǎn)生初始種群時，應(yīng)盡量使它均勻分布在整個解空間中。一種方 法是，為初始種群中的個體之間設(shè)置一個距離限制，要求入選初始種群的各個 體之間的距離必須大于這個限制距離，這樣就能保證初始種群的個體之間有較 明顯的差別，使它們能較均勻地分布在解空間中，保證了初始種群含有較為豐 富的模式，從而增加搜索收斂于全局最優(yōu)解的可能。另一種方法是，首先將解 空間分割成若干個子空間，對每個子空間進(jìn)行初始種群選擇，然后將每個子空 間的初始種群進(jìn)行合并，生成總的初始種群，那么這個種群中至少包含了來自 不同子空間的個體。 西南交通大學(xué)碩士研究生學(xué)位論文第15 頁 2 2 2 編碼方式的多樣化 鐘守楠在遺傳算法的收斂性與編碼中通過對收斂性和收斂速度的分析， 說明了編碼方式對遺傳算法有著重大影響。h o l l a n d 模式定理建議采用二進(jìn)制編 碼。人們在應(yīng)用過程中，發(fā)現(xiàn)二進(jìn)制編碼方式的遺傳算法存在著h a m m i n g 懸岸、 缺乏微調(diào)功能，對于復(fù)雜或高維問題，由于個體編碼串過長而使問題無法計算 或引起早熟現(xiàn)象等問題。為進(jìn)一步改進(jìn)遺傳算法的性能，研究學(xué)者們采用 了不同的編碼方式，如：為克服h a m m i n g