多種排課算法的探討與分析文獻(xiàn)綜述

1、單位代碼01學(xué)號(hào) 040101172分類號(hào)密級(jí)文獻(xiàn)綜述多種排課算法的探討與分析院（系）名稱信息工程學(xué)院專業(yè)名稱計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生姓名指導(dǎo)教師2008年3月 15日黃河科技學(xué)院畢業(yè)設(shè)計(jì)（文獻(xiàn)綜述）第II頁(yè)黃河科技學(xué)院畢業(yè)設(shè)計(jì)（文獻(xiàn)綜述）第II頁(yè)多種排課算法的探討與分析摘 要課程表的編排是學(xué)校教學(xué)管理工作中不可或缺的一部分，是教學(xué)工作順利進(jìn)行的保 證。由于學(xué)校教學(xué)工作的科目安排，不僅反映出學(xué)校的辦學(xué)思想，也體現(xiàn)學(xué)校教育管理 的水平，所以，科學(xué)、合理地編排各學(xué)科教師的授課時(shí)間，是不容忽視的。而如何實(shí)現(xiàn) 課表編排的高效與快速性，是本文所要描述的內(nèi)容。本文分別對(duì)PBIL算法，案例注入式遺傳算法、混合型

2、模擬退火算法、分支定界算 法的背景、原理、實(shí)現(xiàn)及存在優(yōu)缺點(diǎn)做了分析與比較，其中PBIL算法是一種進(jìn)化演繹算法，以學(xué)習(xí)為手段，用概率作指導(dǎo)，通過重復(fù)計(jì)算和目標(biāo)函數(shù)的收斂性求得最優(yōu)解； 案例注入式遺傳算法通過對(duì)案例庫(kù)的相似搜索，然后通過學(xué)習(xí)、復(fù)制、交叉、變異實(shí)現(xiàn) 新案例的生成；退火算法采用復(fù)雜度高者優(yōu)先、循環(huán)首次適應(yīng)算法、貪婪法、回溯法和 松弛法等多種方法，由隨機(jī)函數(shù)求得最優(yōu)解；分支定界算法是一種在問題的解空間樹上 搜索問題的解的方法。這幾種算法各有優(yōu)缺點(diǎn)，而收斂速度和最優(yōu)解是受關(guān)注的。關(guān)鍵詞：課程表，遺傳算法，分支定界算法，PBIL算法目 錄 TOC o 1-5 h z HYPERLINK l

3、bookmark6 o Current Document 1緒論.仁 HYPERLINK l bookmark8 o Current Document 2PBIL 算法2.PBIL算法描述2.22 PBIL算法的進(jìn)化過程2. HYPERLINK l bookmark10 o Current Document 3案例注入式遺傳算法 3.3.1案例注入式遺傳算法簡(jiǎn)介 3.3.2案例注入式遺傳算法組成結(jié)構(gòu).33.3案例注入式遺傳算法存在的問題 4 HYPERLINK l bookmark12 o Current Document 混合型模擬退火算法 5.4.1混合型模擬退火算法簡(jiǎn)介 5.4.2模擬退

4、火的思想5.4.3混合型模擬退火算法的前景6. HYPERLINK l bookmark14 o Current Document 分支定界算法 1.分支定界算法簡(jiǎn)介 Z.5.2分支定界法的思想7. HYPERLINK l bookmark16 o Current Document 結(jié) 論.9. HYPERLINK l bookmark18 o Current Document 參考文獻(xiàn)1.0.黃河科技學(xué)院畢業(yè)設(shè)計(jì)（文獻(xiàn)綜述）第 頁(yè)黃河科技學(xué)院畢業(yè)設(shè)計(jì)（文獻(xiàn)綜述）第 #頁(yè)1緒論隨著學(xué)生人數(shù)的不斷上升和社會(huì)的進(jìn)步，學(xué)校的課程設(shè)置也向深度和廣度發(fā)展，因 此手工排課的實(shí)現(xiàn)相應(yīng)增加了困難。 然而隨著科

5、學(xué)技術(shù)的日益進(jìn)步，計(jì)算機(jī)的應(yīng)用越來(lái) 越廣泛。而且計(jì)算機(jī)具有運(yùn)算快，處理能力強(qiáng)等特點(diǎn)， 很自然地會(huì)應(yīng)用到這一領(lǐng)域。而 且用計(jì)算機(jī)進(jìn)行排課能夠快速地得到滿足約束條件的可行性結(jié)果，具有排課時(shí)間短、質(zhì)量高和節(jié)約人力的優(yōu)點(diǎn)，這能使教務(wù)人員從繁雜的排課任務(wù)中解脫出來(lái)， 并對(duì)推動(dòng)教學(xué) 的發(fā)展起到非常重要的作用。所以如何用計(jì)算機(jī)實(shí)現(xiàn)高效的、快速的課程表編排工作， 成為許多人研究的目標(biāo)，而在這其中算法的分析與選擇是相當(dāng)重要的， 是實(shí)現(xiàn)高效功能 的關(guān)鍵。所以要對(duì)許多相關(guān)算法進(jìn)行探討與分析，以此找到一種高效、快速的排課算法 來(lái)實(shí)現(xiàn)課程表的編排工作。課程表的編排，實(shí)際上就是各種方案的篩選過程 。而這個(gè)過程較為復(fù)雜，用

6、人工 來(lái)編排課程表，運(yùn)算速度慢，篩選方案少， 其結(jié)果合理程度也會(huì)大打折扣。因此可以利 用計(jì)算機(jī)的優(yōu)勢(shì)來(lái)進(jìn)行課程表的編排工作。計(jì)算機(jī)編排課程表起點(diǎn)是用隨機(jī)函數(shù)選定的， 所以計(jì)算機(jī)每重復(fù)一次編排，其結(jié)果 肯定不同，因此利用計(jì)算機(jī)運(yùn)算速度快的優(yōu)勢(shì)讓其在短時(shí)間內(nèi)，進(jìn)行多次重復(fù)，就可實(shí)現(xiàn)很多次的方案篩選。在具體程序設(shè)計(jì)時(shí)加入適當(dāng)?shù)臋z索，讓計(jì)算機(jī)自動(dòng)篩選出帶有合 理參數(shù)的方案，供決策者最后確定。也可以由計(jì)算機(jī)直接根據(jù)合理參數(shù)篩選出最后結(jié)果， 如果不滿意還可讓計(jì)算機(jī)不停地進(jìn)行篩選， 直至最終得出較為滿意的結(jié)果。這就是算法 的應(yīng)用與實(shí)現(xiàn)。黃河科技學(xué)院畢業(yè)設(shè)計(jì)(文獻(xiàn)綜述)第 頁(yè)黃河科技學(xué)院畢業(yè)設(shè)計(jì)（文獻(xiàn)綜述）第

7、 頁(yè)2 PBIL算法PBIL算法描述PBIL（Populatio n-Based In creme ntal Learni ng算法是一種進(jìn)化演繹算法，它將進(jìn)化過 程由原來(lái)的生物進(jìn)化過程轉(zhuǎn)變?yōu)橐环N學(xué)習(xí)過程，用學(xué)習(xí)概率來(lái)指導(dǎo)產(chǎn)生后代，完成目標(biāo)功能的實(shí)現(xiàn)2。這種概率是整個(gè)進(jìn)化過程信息的積累。在這樣的進(jìn)化過程中，在目標(biāo)函 數(shù)的指導(dǎo)下，可以得到目標(biāo)函數(shù)值越來(lái)越小的解，并且用多次重復(fù)計(jì)算，可以得到多種不同的解，便于使用者從中挑選合適的解作為安排的方案。由此過程產(chǎn)生的結(jié)果也就更具有優(yōu)化性，因此能在許多問題中獲得更快的收斂速度和更好的結(jié)果。PBIL算法的進(jìn)化過程第1步：初始化學(xué)習(xí)概率p；第2步：由學(xué)習(xí)概率指

8、導(dǎo)產(chǎn)生k個(gè)解；第3步：計(jì)算上一步產(chǎn)生的k個(gè)解的目標(biāo)函數(shù)值，并從中找出一個(gè)最優(yōu)解，設(shè)為B；第4步：用目標(biāo)函數(shù)值中的最優(yōu)解 B修正學(xué)習(xí)概率P；第5步：返回到第2步循環(huán)，直至滿足一定的結(jié)束條件為止。由于實(shí)際問題中的每一個(gè)解，往往需要多位取值，此時(shí)若仍用二進(jìn)制位表示，會(huì)造 成許多不便，所以會(huì)經(jīng)常使用其他類型的編碼方法進(jìn)行操作。如任意整數(shù)編碼，二維表。在課表的編排過程中會(huì)涉及多種約束條件，而求解過程就是排除約束條件間的沖突 矛盾，同時(shí)要盡量合乎現(xiàn)實(shí)情況。這里會(huì)出現(xiàn)課表編排問題中的兩個(gè)條件：硬約束條件和軟約束條件。其中：硬約束條件是必須滿足的條件，軟約束條件是盡量滿足的條件。課程表安排問題是組合規(guī)劃中典型

9、的優(yōu)化決策問題，已被證明是NP難題，至今為止，人們沒有找到求解此問題的精確方法 。在PBIL算法的求解中需要首先確定樣本 集，這關(guān)系到算法實(shí)現(xiàn)的復(fù)雜度和問題實(shí)現(xiàn)的可行性。而樣本集的確定是一個(gè)復(fù)雜而重要的問題，這也給算法實(shí)現(xiàn)帶來(lái)了不便，因此解決這個(gè)問題很是關(guān)鍵。3案例注入式遺傳算法3.1案例注入式遺傳算法簡(jiǎn)介基于案例的推理(Case-Based Reasoning, CBR)技術(shù)最先是由美國(guó)耶魯大學(xué) Roger Schank教授在他的論著Dynamic Memory中提出的，之后被逐步推廣到機(jī)械 CAD、 醫(yī)療衛(wèi)生、企業(yè)管理、軍事等領(lǐng)域并得到了成功的應(yīng)用 5。CBR是一種基于知識(shí)學(xué)習(xí)的技術(shù)，通過

10、對(duì)先前案例的查找，在案例庫(kù)中找到一個(gè) 與當(dāng)前案例最為相似的案例，然后對(duì)這個(gè)最相似的案例進(jìn)行學(xué)習(xí)，通過對(duì)該案例的解決 方案進(jìn)行修改來(lái)獲取當(dāng)前問題的解決方案。而解決的新案例會(huì)根據(jù)需要最終決定是否被 存入到案例庫(kù)中。對(duì)基于案例的推理技術(shù)來(lái)說，它可以通過對(duì)先前案例的學(xué)習(xí)來(lái)解決當(dāng) 前問題，以此加快解決問題的速度，另外由于其自身具備學(xué)習(xí)的能力，隨著解決問題數(shù) 目的不斷增加，案例庫(kù)中的案例也在不斷地增加，因此從庫(kù)中檢索到能夠解決當(dāng)前問題 的方法的概率也隨之增大，從而可以進(jìn)一步提高解決問題的速度。因此，考慮利用基于案例的推理來(lái)改進(jìn)遺傳算法的初始化操作， 并在進(jìn)化自然選擇 階段使用基于案例的推理替換適應(yīng)度較差的

11、個(gè)體， 以此來(lái)加快遺傳算法的收斂速度，以 便更快、更好地解決問題。3.2案例注入式遺傳算法組成結(jié)構(gòu)案例注入式遺傳算法是一種混合式遺傳法，它分為2個(gè)主要模塊：案例模塊與遺傳算模塊，它的基本結(jié)構(gòu)如圖3.1所示。遺傳算法模塊圖3.1案例注入式遺傳算法結(jié)構(gòu)該模塊完成以下幾個(gè)功能：案例相似性的比較分析、案例的查找、案例的存儲(chǔ)刪除。 遺傳算法模塊的主體與一般遺傳算法結(jié)構(gòu)基本一致，整個(gè)過程遵循自然選擇策略，包括：復(fù)制、變異和交叉操作；適應(yīng)度的評(píng)估；評(píng)估后再進(jìn)行復(fù)制、變異和交叉操作。如此反復(fù)直到適應(yīng)度最終滿足使用者的要求。在此基礎(chǔ)上，結(jié)合基于案例的推理對(duì)算法進(jìn)行 調(diào)整：首先，對(duì)遺傳算法的初始化部分采用了案例注

12、入式的方法，從而加快了遺傳算法的收斂速度。其次，在遺傳算法進(jìn)行中，經(jīng)過復(fù)制、交叉和變異操作后可以選擇一代中 最好的案例存人案例庫(kù)以豐富案例庫(kù)。3.3案例注入式遺傳算法存在的問題對(duì)于遺傳算法而言，種群初始化過程非常重要，它需要盡可能地囊括所有的優(yōu)秀個(gè) 體，但與此同時(shí)種群又不能過大，因?yàn)榉N群過大會(huì)增加算法的運(yùn)算量和復(fù)雜度8,9。因此，大多數(shù)的遺傳算法往往采用隨機(jī)方式來(lái)初始化種群，這樣做的目的是為了獲得更多的優(yōu)秀解決方案，產(chǎn)生無(wú)偏向搜索空間。然而對(duì)于解決類似課程表問題的系統(tǒng)來(lái)說，在系統(tǒng)頻繁遇到的都是相似、相關(guān)問題的情況下，如果每次初始化都需要從頭開始的話， 勢(shì)必造成運(yùn)算量變大和復(fù)雜度增加等情況，從而

13、影響算法的性能。浪費(fèi)大量的系統(tǒng)時(shí)間， 這也是影響遺傳算法性能的主要原因。黃河科技學(xué)院畢業(yè)設(shè)計(jì)(文獻(xiàn)綜述)第 頁(yè)黃河科技學(xué)院畢業(yè)設(shè)計(jì)(文獻(xiàn)綜述)第 頁(yè)4混合型模擬退火算法4.1混合型模擬退火算法簡(jiǎn)介基于概率型啟發(fā)式算法(HA)的混合型模擬退火算法采用了復(fù)雜度高者優(yōu)先、循環(huán) 首次適應(yīng)算法、貪婪法、回溯法和松弛法等多種方法，該算法所排出的課程表可作為模 擬退火算法的初始解10。模擬退火可對(duì)概率型啟發(fā)式算法的排課結(jié)果做進(jìn)一步優(yōu)化， 克服了啟發(fā)式算法不具有全局收斂性的缺點(diǎn)。所以，混合型模擬退火算法具有啟發(fā)式算法充分利用領(lǐng)域知識(shí)、計(jì)算量小、優(yōu)化快速和模擬退火的全局收斂性，數(shù)值實(shí)驗(yàn)也證明 了它的有效性和可行

14、性。中小學(xué)課表問題有它的特點(diǎn)和難點(diǎn)，第一階段采用基于概率論的啟發(fā)式算法，該階 段又分兩步：第一步：用基于概率論的啟發(fā)式方法排出每個(gè)班每門課每天上幾節(jié)，可得到多種排法；第二步：采用啟發(fā)式方法，排出每個(gè)班每天每一節(jié)上什么課，可得到多個(gè) 不同的課表。第二階段運(yùn)用模擬退火方法，對(duì)概率型啟發(fā)式算法所排出的課表做進(jìn)一步 優(yōu)化，使其盡可能滿足所有約束條件。在第一階段中所采用的啟發(fā)式規(guī)則包括：復(fù)雜度高者優(yōu)先、循環(huán)首次適應(yīng)算法、貪婪法、回溯法和松弛法，這些啟發(fā)式規(guī)則可增強(qiáng)搜索的目的性，提高算法的效率。4.2模擬退火的思想模擬退火算法是基于 Monte Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是 基于物

15、理退火過程與一般組合優(yōu)化問題之間的相似性11。模擬退火算法是在某一初溫下，伴隨著溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的最 優(yōu)解，即在局部最優(yōu)解能概率性地跳出，并最終趨于全局最優(yōu)。標(biāo)準(zhǔn)模擬退火算法如下：給定初始溫度t=to,隨機(jī)產(chǎn)生初始狀態(tài)S=S0，令k=0 ；repeat;repeat；產(chǎn)生新狀態(tài)sGenete(s); 血f(S?) - f(s)；if min1 , exp Af/tk random0, 1； s=s 直到抽樣穩(wěn)定準(zhǔn)則成立；退溫 tk+1 =update(t)，并令 k=k+1 ；直到算法終止準(zhǔn)則成立；輸出算法搜索結(jié)果。4.3混合型模擬退火算法的前景基

16、于知識(shí)的概率型啟發(fā)式算法(HA)和模擬退火(SA)相結(jié)合的混合型算法，該算法能 充分利用領(lǐng)域知識(shí)，計(jì)算小、優(yōu)化快速，并具有模擬退火的全局收斂性。數(shù)值實(shí)驗(yàn)進(jìn)一 步表明該算法的有效性和可行性。今后可繼續(xù)研究模擬退火的不同退溫策略，如增加升 溫或重升溫過程，以及采用兩種退溫速率策略對(duì)算法效率和性能的影響。5分支定界算法5.1分支定界算法簡(jiǎn)介分支定界(Branch And Bound)算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯算法不同，分支定界算法采用廣度優(yōu)先或最小耗費(fèi)優(yōu)先的方法搜索解空 間樹，并且，在分支定界算法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。利用分支定界算法對(duì)問題的解空間樹

17、進(jìn)行搜索，它的搜索策略是：產(chǎn)生當(dāng)前擴(kuò)展結(jié)點(diǎn)的所有孩子結(jié)點(diǎn)；在產(chǎn)生的孩子結(jié)點(diǎn)中，拋棄那些不可能產(chǎn)生可行解 (或最優(yōu)解)的結(jié)點(diǎn)；將其余的孩子結(jié)點(diǎn)加入活結(jié)點(diǎn)表；從活結(jié)點(diǎn)表中選擇下一個(gè)活結(jié)點(diǎn)作為新的擴(kuò)展結(jié)點(diǎn)。如此循環(huán)，直到找到問題的可行解(最優(yōu)解)或活結(jié)點(diǎn)表為空為止。從活結(jié)點(diǎn)表中選擇下一個(gè)活結(jié)點(diǎn)作為新的擴(kuò)展結(jié)點(diǎn)，根據(jù)選擇方式的不同，分支定界算法通常可以分為兩種形式：1、FIFO(First In First Out)分支定界算法按照先進(jìn)先出原則選擇下一個(gè)活結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，即從活結(jié)點(diǎn)表中取出結(jié)點(diǎn)的順 序與加入結(jié)點(diǎn)的順序相同。2、最小耗費(fèi)或最大收益分支定界算法在這種情況下，每個(gè)結(jié)點(diǎn)都有一個(gè)耗費(fèi)或收益。如

18、果要查找一個(gè)具有最小耗費(fèi)的解， 那么要選擇的下一個(gè)擴(kuò)展結(jié)點(diǎn)就是活結(jié)點(diǎn)表中具有最小耗費(fèi)的活結(jié)點(diǎn)；如果要查找一個(gè)具有最大收益的解，那么要選擇的下一個(gè)擴(kuò)展結(jié)點(diǎn)就是活結(jié)點(diǎn)表中具有最大收益的活結(jié) 點(diǎn)。5.2分支定界法的思想分支定界算法又稱分支定界搜索法。該算法是將原始問題分解，產(chǎn)生一組子問題。 分支是將一組解分為幾組子解，定界是建立這些子組解的目標(biāo)函數(shù)的邊界。 如果某一子 組的解在這些邊界之外，就將這一子組舍棄。分支定界法原為運(yùn)籌學(xué)中求解整數(shù)規(guī)劃(或 黃河科技學(xué)院畢業(yè)設(shè)計(jì)（文獻(xiàn)綜述）第 #頁(yè)黃河科技學(xué)院畢業(yè)設(shè)計(jì)（文獻(xiàn)綜述）第 頁(yè)混合整數(shù)規(guī)劃）問題的一種方法。用該算法尋求整數(shù)最優(yōu)解的效率很高。將該算法原理

19、 用于過程系統(tǒng)綜合可大大減少需要計(jì)算的方案數(shù)目。對(duì)于分支定界算法，首先確定目標(biāo)值的上下界，邊搜索邊減掉搜索樹的某些支，提 高搜索效率。上界是已求得的可行解的目標(biāo)函數(shù)值中的最小者， 分為初始上界和在探測(cè) 過程中產(chǎn)生的動(dòng)態(tài)上界。分支定界法在求最優(yōu)解的迭代過程中， 若某結(jié)點(diǎn)估計(jì)的下界不 小于已知的上界，則不必從該節(jié)點(diǎn)往下繼續(xù)搜索。因此若能產(chǎn)生一個(gè)較好的上界，可以 消除許多不必要的列舉計(jì)算。課表編排實(shí)際上是組合優(yōu)化中一個(gè)典型的判定問題。即在給定的約束條件下，判定 該問題實(shí)例是否有解。它的難度在于，在有解的情況下要找出一個(gè)解，但是不能用近似 算法求解。利用分支定界法可有效地解決此問題。結(jié) 論隨著科學(xué)技術(shù)

20、的日益進(jìn)步，計(jì)算機(jī)的應(yīng)用與推廣也有著日新月異的變化，而其在課程編排領(lǐng)域的應(yīng)用也達(dá)到了一定的深度，由于計(jì)算機(jī)具有運(yùn)算快，處理能力強(qiáng)的特點(diǎn)， 課程的編排問題也有了更好的解決方案一一計(jì)算機(jī)編排。于是排課算法得以研究與延 伸，一種好的算法能夠快速、高效地得到滿足約束條件的可行性結(jié)果。從而使教務(wù)人員 從繁雜的排課任務(wù)中解脫出來(lái)，并對(duì)推動(dòng)教學(xué)的發(fā)展有非常重要的作用。在本文中介紹了 PBIL算法，案例注入式遺傳算法、混合型模擬退火算法、分支定界算法的原理和實(shí)現(xiàn)方法，并對(duì)存在的優(yōu)缺點(diǎn)做了分析與比較，其中PBIL算法是一種進(jìn)化算法，以學(xué)習(xí)為手段，用概率作指導(dǎo)，通過多次計(jì)算比較并參考目標(biāo)函數(shù)的收斂性 求得最優(yōu)解；案例注入式遺傳算法通過對(duì)原有案例庫(kù)的相似性搜索，然后通過復(fù)制、交叉、變異等方法實(shí)現(xiàn)新案例的生成；退火算法采用復(fù)雜度高者優(yōu)先、循環(huán)首次適應(yīng)算法、 貪婪法、回溯法和松弛法等多種方法，由隨機(jī)函數(shù)求得最優(yōu)解；分支定界算法是一種在 問題的解空間樹上搜索問題的解的算法，確定上下界進(jìn)行逐漸縮小搜索實(shí)現(xiàn)最優(yōu)解。黃河科技學(xué)院畢業(yè)設(shè)計(jì)(文獻(xiàn)綜述)第10頁(yè)黃河科技學(xué)院畢業(yè)設(shè)計(jì)(文獻(xiàn)綜述)第10頁(yè)參考文獻(xiàn)張春梅，行 飛用自適應(yīng)的遺傳算法求解大學(xué)課程表安排問題J 內(nèi)蒙古大學(xué)學(xué)報(bào)(自然科學(xué)版)，2002，33(4): 459-464.Baluja S. Genetic Algorith