基于遺傳算法的高校網(wǎng)上排課系統(tǒng)

1、本科生畢業(yè)論文（設(shè)計）題目基于遺傳算法的高校網(wǎng)上排課系統(tǒng)An Optimized Genetic Algorithm Based University Timetabling System姓名 學(xué)號 院系 計算機(jī)科學(xué)學(xué)院 專業(yè) 計算機(jī)科學(xué)與技術(shù) 指導(dǎo)教師 職稱 講師 2010 年 5 月 20 日曲阜師范大學(xué)教務(wù)處制目 錄摘要1關(guān)鍵詞1Abstract1Key words11 引言11.1 研究背景和意義11.2 國內(nèi)外研究的現(xiàn)狀12 課程表問題22.1 課程表問題簡介22.2 課程表問題中的基本約束23 排課系統(tǒng)的具體設(shè)計實(shí)現(xiàn)23.1 模塊劃分23.2 課程表問題基本數(shù)據(jù)結(jié)構(gòu)介紹23.3 遺

2、傳算法的設(shè)計與實(shí)現(xiàn)34 結(jié)果分析65 總結(jié)8致謝8參考文獻(xiàn)8附錄9基于遺傳算法的高校網(wǎng)上排課系統(tǒng)計算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生指導(dǎo)教師摘要：大學(xué)排課問題是一種NP難的組合優(yōu)化問題。在傳統(tǒng)遺傳算法的基礎(chǔ)上，首先把問題分解以減少算法的復(fù)雜度，然后提出了適合本問題的染色體編碼方案和操作方法，以盡量減少非法個體，并采用沖突檢測和消解策略，對種群進(jìn)行優(yōu)化，提高種群的適應(yīng)度，并有效縮短了產(chǎn)生最優(yōu)解的時間。最后使用ASP.NET和C#實(shí)現(xiàn)了一個網(wǎng)上自動排課系統(tǒng)，并使用本學(xué)院的真實(shí)數(shù)據(jù)進(jìn)行測試，滿足所用的約束條件，產(chǎn)生了滿意的結(jié)果。關(guān)鍵詞：大學(xué)排課問題 遺傳算法 沖突檢測 在線 An Optimized Genet

3、ic Algorithm Based University Timetabling SystemStudent Majoring in Computer Science & Technology Tutor Abstract: University Course Timetable Problem is NP-Hard combinatorial optimization problem. Based on the traditional Genetic Algorithm, we decompensate the problem to decrease the complexity, adv

4、ance the problem-specific chromosome and operations to avoid generate illegal timetables, and use collision detection and resolution to optimize the population, increase the fitness and decrease the time needed. Finally, we implement the online timetabling system in ASP.NET and C#. The algorithm is

5、tested with real date from our college, satisfies all the constraints of problem and yield promising result.Key words: University Timetabling; Genetic Algorithm; Collision Detection; Online;1 引言1.1 研究背景和意義長期以來，在高校的教務(wù)管理中通常使用手工或者輔助軟件進(jìn)行排課，手工排課相對更為常見，一般是對上一年的課表稍加修改然后予以沿用。然而隨著專業(yè)的發(fā)展和高校的擴(kuò)招，在不同年級之間，不論從人數(shù)、授課

6、教師還是開設(shè)的課程，與原來相比都有較大的不同。因而往年的課表對于排課的借鑒作用逐步削弱，一種能滿足各種排課約束條件的自動排課軟件呼之欲出。尤其在網(wǎng)絡(luò)不斷發(fā)展的今天，在線的排課系統(tǒng)更能給教務(wù)人員帶來更多的便利。1.2 國內(nèi)外研究的現(xiàn)狀排課問題，也稱為課程表問題。目前，國內(nèi)外已經(jīng)有很多人對于這個課題進(jìn)行了研究，提出的解決方法也多種多樣。1963年，C. C. Gotlieb在其The Construction of Class-Teacher Time-Tables1一文中第一次提出了課表編排的數(shù)學(xué)模型。1975年，Even. S證明了排課問題是一個NP完全問題,無法用計算機(jī)實(shí)現(xiàn)，從理論上對時間表

7、問題有了全新的認(rèn)識。因而，眾多的研究者們又開始考慮用其他方法來解決這一問題，比如使用組合邏輯、禁忌搜索、決策系統(tǒng)、貪心算法、圖論、模擬退火算法、遺傳算法2,3、免疫網(wǎng)絡(luò)4等。其中，遺傳算法因?yàn)槠淞己玫闹悄苄浴⒉⑿行?、簡單易用、魯棒性?qiáng)等特點(diǎn)，成為一種優(yōu)秀的亞啟發(fā)式算法，并成功的應(yīng)用于例如TSP、地圖著色、衛(wèi)星軌道控制等方面，在解決課程表問題方面也有著不俗的表現(xiàn)。在國內(nèi)，雖然較國外起步較晚，80年代以來，清華大學(xué)、大連理工大學(xué)、原南京工學(xué)院、西安交通大學(xué)等國內(nèi)高校都進(jìn)行了相關(guān)的研究并研制了相應(yīng)的軟件。比如清華大學(xué)的TISER系統(tǒng)，西安交大自行開發(fā)的排課系統(tǒng)，中山大學(xué)基于智能規(guī)劃的排課系統(tǒng)，華中科

8、技大學(xué)的基于模糊專家系統(tǒng)的排課系統(tǒng)，武漢大學(xué)基于回溯算法的排課系統(tǒng)等。從實(shí)際情況來看，由于排課問題的復(fù)雜性和各個學(xué)校自身教學(xué)的特殊性，國內(nèi)外研制開發(fā)的這些軟件系統(tǒng)實(shí)用性仍然有待提高。排課問題作為NP問題，它的解決也有著典型的代表性。所以，對排課問題的研究無論從理論還是實(shí)踐上都有著重要意義。2 課程表問題2.1 課程表問題簡介課程表問題是把教師、教室、班級、課程的組合安排到一天的各個時間段上。根據(jù)本院實(shí)際情況，一周中每一天分為4個時間段，上午兩個，分別為兩個小時，下午和晚上各一個，分別為三個小時。這樣一周共有20個時間段。2.2 課程表問題中的基本約束課程表問題在實(shí)際安排中的約束條件有以下幾個方

9、面。2.2.1 硬性約束，即必須滿足的約束1、教室不沖突：一個教室同一時間不能安排兩門課程，且人數(shù)不能超過教室的最大容量；2、班級不沖突：一個班級不能在同一時間段安排兩門課或兩門以上的課程，同一班級不能同一時間在不同地點(diǎn)上課；3、教師不沖突：一個教師不能同一時間在不同地點(diǎn)上課。2.2.2 彈性約束，即盡量滿足的約束，滿足此種約束更利于教學(xué)1、英語這類課程應(yīng)盡量安排在上午進(jìn)行；2、每周課時量較多的課程應(yīng)在一周的五天中均勻安排；3、每周多次的課程盡量安排在同一間教室；4、時長為三個學(xué)時的課程應(yīng)該安排在下午或晚上；5、學(xué)校規(guī)定有統(tǒng)一活動的時間不能安排課程。另外，學(xué)校已經(jīng)安排公共課程的時間段是不能給相

10、關(guān)班級安排課程的。3 排課系統(tǒng)的具體設(shè)計實(shí)現(xiàn)3.1 模塊劃分系統(tǒng)主要分為以下幾個模塊：1、 系統(tǒng)登錄模塊：作用是驗(yàn)證用戶身份，并轉(zhuǎn)入相應(yīng)的界面。2、 信息管理模塊：在左側(cè)菜單欄顯示的用戶的權(quán)限，用戶可以點(diǎn)擊各菜單使用相應(yīng)的功能。包括：添加教室、添加課程、添加教師、添加班級。3、 信息顯示模塊：包括顯示、查詢和修改管理員信息、教室信息、教師信息、課程信息、班級信息。4、 自動排課模塊：包括預(yù)排公共課、添加本學(xué)期課程安排、自動排課、顯示排課結(jié)果、顯示全系課表。3.2 課程表問題基本數(shù)據(jù)結(jié)構(gòu)介紹Professor類：保存教師的基本信息和操作StudentGroups類：保存班級的基本信息和操作Roo

11、m類：表示教室Course類：表示一門課程CourseClass類：表示一次課程安排，即某教師給某個班級上某節(jié)課PreCourseClass類：是CourseClass類的子類，表示一次預(yù)排課，即自動排課前已經(jīng)確定的課程安排GAAutomatedTT類：本算法的核心類，定義了交叉、變異、計算適應(yīng)度等函數(shù)及其配套使用的數(shù)據(jù)結(jié)構(gòu)3.3 遺傳算法的設(shè)計與實(shí)現(xiàn)3.3.1 問題分解課程表問題雖然是教師、教室、班級、課程四者之間在時間上的組合和優(yōu)化，在實(shí)際應(yīng)用中我們發(fā)現(xiàn)，我們可以把教室根據(jù)容量進(jìn)行分類，同一容量的教室在分配中的地位是平等的，所以可以統(tǒng)計出不同容量教室的個數(shù)，遺傳算法進(jìn)行求解時，無需考慮具體

12、教室的分配，只要求每個時間段需要某類教室的個數(shù)在該類實(shí)際個數(shù)范圍內(nèi)即可。在求解完畢后再使用一個算法來完成教室的分配就可以得到最終的解。這樣就把問題簡化成為教師、班級和課程三者在安排課程時的組合優(yōu)化。3.3.2 染色體設(shè)計在消去教室這一因素后，排課過程中對約束條件判斷，除了關(guān)于教師的硬性約束條件外，所有的彈性約束條件和預(yù)排課約束都是針對班級來說的。所以，我們在設(shè)計染色體時以班級為中心。染色體中班級的數(shù)據(jù)結(jié)構(gòu)如下：Dictionaryint, ListList _slotsOfStudentGroupDictionary中的第一項(xiàng)表示班級ID，其后的ListList對應(yīng)該班一周的課表，包括20個時

13、間段。其中的List表示在某個時間段安排的課程。教師的數(shù)據(jù)結(jié)構(gòu)與學(xué)生的相似：Dictionaryint, ListList _slotsOfProfessorIDListList 共20個時間段，表示一周的課表一個染色體.List圖 31 染色體示意圖染色體直接使用類對象，省去了編碼和解碼的過程，可以直接使用類中的函數(shù)對類進(jìn)行操作，獲取相應(yīng)的信息。染色體中輔助用的數(shù)據(jù)結(jié)構(gòu)及作用如下：Dictionaryint, ListList _slotsOfProfessor 教師課表，記錄每個教師每周的課表；Dictionaryint, ListList _slotsOfStudentGroup班級課表

14、，記錄每個班級每周課表；Dictionaryint, List _freetimeOfProfessor 教師空余時間表，記錄每個教師的空余時間；Dictionaryint, List _freetimeOfStudentGroup 班級空余時間表，記錄每個班級的空余時間；Dictionaryint, List _preScheduleTime 班級預(yù)排課時間段表，班級已經(jīng)預(yù)排課時間段；Dictionaryint, Dictionaryint, List _CourseScheduleOfStudentGroup課程所在時間段表，記錄每個班級每門課程所在的時間段；Dictionaryint,

15、List _recordsOfBadOnesForThree 記錄未合理安排的每周三次的課程；Dictionaryint, List _recordsOfBadOnesForTwo記錄未合理安排的每周兩次的課程；Dictionaryint, Dictionaryint, List _recordsOfBadOnesForProfessors 記錄教師出現(xiàn)沖突的課程；Dictionaryint, List _recordsOfBadOnesForDurationOf3 記錄未合理安排的三個課時的課程。3.3.3 種群初始化初始化是為種群中的每個個體根據(jù)本學(xué)期的課程安排隨機(jī)產(chǎn)生一份課表?？紤]到盡量

16、減少遺傳算法的進(jìn)化壓力，初始化的個體應(yīng)該盡量滿足所給出的約束條件。比較所給出的約束條件，應(yīng)該先滿足的是彈性約束的第1、2、4條。因?yàn)槿粼谶M(jìn)化中出現(xiàn)此種沖突，只能選擇上午（第1條）、隔一天或兩天（第2條）、下午或晚上（第4條）的時間段來消解沖突，并且還要滿足三項(xiàng)硬性約束，所以選擇余地比較小。我們先把待安排的課程進(jìn)行分類，分別是：預(yù)排課程、每周三次每次兩個課時的課程、每周兩次每次兩個課時的課程、每周一次每次三個課時的課程。在初始化時，先根據(jù)預(yù)排課表，把班級、教師、教室中的相應(yīng)的空余時間段去掉，然后安排每周三次每次兩個課時的課程，三次課分別安排在周一、周三、周五，然后安排每周一次每次三個課時的課程，

17、安排在下午或晚上，再安排每周兩次每次兩個課時的課程。每次安排時，都盡量找教師和班級共同的空余時間，完畢后，把班級和教師中相應(yīng)的空余時間段去掉。具體方法如下：1、 處理預(yù)排課信息，方法是只去掉班級和教師空余時間表中相應(yīng)的時間段，但不添加課程至課程表，以免變異時變化；2、 根據(jù)課程的性質(zhì)，包括課時數(shù)、每周上課的次數(shù)、是否是英語，在空余時間段中找一個符合約束的時間段出來，如果沒有隨機(jī)找一個時間段；3、 在班級和教師的空余時間段表中去掉該時間段，并將其加入到班級和教師的課表中；4、 計算該個體的適應(yīng)度。3.3.4 交叉操作常見的交叉操作有單點(diǎn)交叉、多點(diǎn)交叉、兩點(diǎn)交叉等。在排課算法中，可以選擇某節(jié)課、某

18、班的全部課程或某年級的全部課程進(jìn)行交叉。若是只是選擇某班的某節(jié)課進(jìn)行交叉，因?yàn)橐恢艿乃姓n程安排之間也有關(guān)聯(lián)，在一個個體中某課程的時間段在另一個個體中未必空余，在教師的安排上也可能產(chǎn)生新的沖突，而且單點(diǎn)交叉面積較小，也限制了其產(chǎn)生新基因的作用。若交叉某班的全部課程，可以避免課程的沖突，可能產(chǎn)生教師安排上的沖突。若交叉某年級的全部課程，因?yàn)椴煌昙壷g有重疊的教師更多，產(chǎn)生沖突的可能性就更大。綜上所述，我們選擇某班的全部課程進(jìn)行交叉，在實(shí)驗(yàn)中的效果也相對較好。具體方法如下：1、 隨機(jī)生成0-100之間的數(shù)大于交叉概率進(jìn)入2，否則跳出；2、 隨機(jī)生成需要交叉的班級；3、 交換兩個班級的課表；4、

19、交換兩個班級的空余時間表；5、 交換兩個班級每門課程所在的時間段；6、 在教師課表中修改相應(yīng)的信息；7、 計算適應(yīng)度。3.3.5 變異操作常見的變異操作有等。對于排課算法來說，可以選擇某班某節(jié)課重新安排、選擇某班多節(jié)課重新安排或某班全部課程重新安排，也可以選擇某班級的兩節(jié)課互相交換。因?yàn)樵谂耪n過程中，尤其是后期，產(chǎn)生沖突的課程僅僅是某班的某幾節(jié)課，對全部課程重新安排容易造成以前進(jìn)化的失效和個體適應(yīng)度的過分降低。而具體選擇變異的課程數(shù)量還需實(shí)驗(yàn)研究，所以我們選擇某班級的兩節(jié)課互相交換。具體方法如下：1、 隨機(jī)生成0-100之間的數(shù)大于變異概率進(jìn)入2，否則跳出2、 隨機(jī)產(chǎn)生要變異的班級；3、 產(chǎn)生

20、兩個變異的時間段；4、 兩處的課程若有3學(xué)時的，與其交換的課程的時間段必須是在下午或晚上，若是進(jìn)入7，否則退出；5、 判斷兩個時間段內(nèi)是否都已經(jīng)安排課程，若是，進(jìn)入7，否則進(jìn)入6；6、 若只有一個時間段有課，進(jìn)入7，否則說明兩個時間段都沒有安排課程，直接跳出；7、 交換課程，并修改染色體中相關(guān)的輔助數(shù)據(jù)結(jié)構(gòu)；8、 計算適應(yīng)度。3.3.6 計算適應(yīng)度根據(jù)所有的約束條件，適應(yīng)度的計算共分成6個部分。1、 記錄三個課時的課程是否安排在下午和晚上，否則fitness0減一2、 記錄同一時間一位教師是否只上一門課，若是，fitness1加一3、 記錄同一時間一個班級是否只上一門課，若是，fitness2

21、加一4、 記錄相鄰兩天是否有相同的課，有，則fitness3減一5、 記錄一天內(nèi)是否有相同的課程，有，則fitness3減26、 記錄每天需要的教室數(shù)是否符合條件，即是否比教室總數(shù)少，少則fitness4加一7、 每天需要的各種類型的教室是否符合條件，即是否比相應(yīng)類型的教室總數(shù)少，少fitness5則加一其中fitness0的最優(yōu)值bestfitness0是0，fitness1的最優(yōu)值bestfitness1是教師總數(shù)*每周總時間段數(shù)，fitness2的最優(yōu)值bestfitness2是班級總數(shù)*每周總時間段數(shù)，fitness3的最優(yōu)值bestfitness3是0，fitness4的最優(yōu)值bes

22、tfitness4是每周總時間段數(shù)，fitness5的最優(yōu)值bestfitness5是每周總時間段數(shù)*教室類型數(shù)。適應(yīng)度的計算公式為：當(dāng)fitness為1時，得到一次滿足所有條件的課程安排。3.3.7 優(yōu)化函數(shù)在只使用傳統(tǒng)遺傳算法的實(shí)驗(yàn)中，我們發(fā)現(xiàn)，產(chǎn)生的個體對于硬性約束1、2的滿足性較好，但對于彈性約束2、4和硬性約束3的滿足性較差，其中彈性約束2最不易滿足，原因在于若要滿足彈性約束2，需要調(diào)整多門或多次課程，并且在調(diào)整中可能產(chǎn)生新的沖突。所以我們編寫了三個優(yōu)化函數(shù)進(jìn)行優(yōu)化。當(dāng)然，優(yōu)化函數(shù)在消解一種沖突時可能產(chǎn)生新的沖突，所以最難滿足的條件的優(yōu)化函數(shù)我們放在最后執(zhí)行，對于產(chǎn)生的新的沖突，我們

23、把它交給下一代來消解，逐代減少沖突，提高種群的適應(yīng)度，實(shí)踐證明這是可行的，也取得了良好的效果。1、根據(jù)彈性約束第2條進(jìn)行優(yōu)化優(yōu)化第2條方法是，根據(jù)“課程所在時間段表”，每周兩次的課程將任意一次課程提前或延后一天。每周三次的課程直接安排在周一、周三和周五。至于安排在該天的哪一個時間段，則在盡量隨機(jī)安排在學(xué)生和教師都空余的時間段，如果沒有，隨機(jī)找一個時間段，然后把兩節(jié)課進(jìn)行交換。2、根據(jù)彈性約束第4條進(jìn)行優(yōu)化優(yōu)化第4條方法是，從班級的空余時間段表中找一個下午或晚上的時間段，并且盡量隨機(jī)安排在學(xué)生和教師都空余的時間段，如果沒有，隨機(jī)找一個下午或晚上的時間段，然后把兩節(jié)課進(jìn)行交換。3、 根據(jù)硬性約束第

24、3條進(jìn)行優(yōu)化優(yōu)化第3條方法是，從教師的空余時間段表中找一個時間段安排沖突的課程，并且盡量隨機(jī)安排在學(xué)生和教師都空余的時間段，如果沒有，隨機(jī)找一個空余時間段，然后把兩節(jié)課進(jìn)行交換。3.3.8 選擇函數(shù)選擇操作是用于模擬生物界去劣存優(yōu)的自然選擇現(xiàn)象。它根據(jù)個體對于目標(biāo)函數(shù)的適應(yīng)情況，將高適應(yīng)值的個體選中，使其基因得以遺傳復(fù)制到下一代，而低適應(yīng)值的個體染色體則被淘汰。因此選擇的本質(zhì)是篩選，而功能則是定向進(jìn)化。經(jīng)過選擇算子多次的定向積累，種群中的個體就會迅速向使目標(biāo)函數(shù)值高的區(qū)域靠攏，形成高質(zhì)量解種群。適應(yīng)度越高的染色體被選擇的可能性越大,其遺傳基因在下一代群體中的分布就越廣,其子孫在下一代出現(xiàn)的數(shù)量

25、就越多。常用的選擇函數(shù)有輪盤賭選擇法、錦標(biāo)賽選擇法、隨機(jī)遍歷選擇法等。為使種群盡快收斂，我們使用的是錦標(biāo)賽選擇法。具體方法如下：1、 從種群中隨機(jī)選擇N個體進(jìn)行適應(yīng)度的比較，將其中適應(yīng)度最高的遺傳到下一代，N一般取2；2、 重復(fù)M次上述過程，從而得到下一代種群。在選擇操作中，我們采用了精英保留的策略，每代中保留3%的最優(yōu)個體，剩余的個體由選擇函數(shù)從子種群中選出。這樣經(jīng)過若干代進(jìn)化的種群中能夠始終保持進(jìn)化過程中所找到的歷代最優(yōu)個體，能夠有效防止種群整體退化現(xiàn)象。3.3.9 自適應(yīng)選擇函數(shù)在遺傳算法執(zhí)行的不同階段，個體間差異也不同，若用相同的選擇策略可能會導(dǎo)致問題的出現(xiàn)：1、當(dāng)個體差異較大時，高選

26、擇壓力可能在淘汰掉劣勢個體的同時也遺失了存在于劣勢個體中的部分優(yōu)良基因。2、當(dāng)個體差異很小時，可能會由于選擇壓力不夠而使搜索趨于隨機(jī)化而導(dǎo)致收斂速度慢。因此，我們采用一種隨算法的執(zhí)行、種群和個體地變化而動態(tài)變化的自適應(yīng)選擇策略。常用的變比技術(shù)有排名變比、西格瑪變比、波茲曼（Boltzmann）變比等。排名變比可以很好的防止收斂過快，但也可能使得收斂太慢。西格瑪變比是一種試圖在多代繁衍中保持選擇壓力的方法，其在開始的幾代收斂較快，但仍需很長的時間才能得到解。與西格瑪變比相比，波茲曼變比在運(yùn)行期間的選擇壓力會隨時變化，開始時選擇壓力較小以保持種群的多樣性，當(dāng)開始接近收斂到最優(yōu)解時，希望只有較好的個

27、體產(chǎn)生后代。其實(shí)，波茲曼變比與模擬退火算法類似，它能以一定的概率接受劣解，以保持種群的多樣性。在文獻(xiàn)6中已經(jīng)發(fā)現(xiàn)模擬退火算法與遺傳算法結(jié)合可以很大的提高算法的效率。波茲曼變比使用一個連續(xù)變化的溫度來控制選擇率，公式如下：溫度初始化為種群中個體數(shù)量的兩倍，逐代降低的溫度為0.05，最低值為1。具體方法如下：1、 逐代降低少量的溫度，但確保不低于最低值；2、 通過循環(huán)，計算，保存，并計算平均值；3、 通過循環(huán)，使用公式計算新的適應(yīng)度。4 結(jié)果分析初始種群為200個個體，交叉概率75%，變異概率50%，數(shù)據(jù)來源于本院2008-2009學(xué)年上學(xué)期的課表1、 在未加入波茲曼變比和優(yōu)化函數(shù)的條件下的結(jié)果如

28、圖4-1所示。圖4-1 未加入變比和優(yōu)化函數(shù)2、 加入波茲曼變比未加入優(yōu)化函數(shù)的條件下的結(jié)果如圖4-2所示。圖4-2 加入波茲曼變比未加入優(yōu)化函數(shù)3、 加入波茲曼變比并加入優(yōu)化函數(shù)的條件下，進(jìn)行了6次實(shí)驗(yàn)，結(jié)果如表4-1所示。表4-1 加入波茲曼變比和優(yōu)化函數(shù)的實(shí)驗(yàn)結(jié)果代數(shù)適應(yīng)度1適應(yīng)度2適應(yīng)度3適應(yīng)度4適應(yīng)度5適應(yīng)度600.966450.972780.971510.970880.971510.9740510.993670.991130.989240.99240.993670.9936720.996830.99430.995560.99430.997460.9949330.998730.996

29、20.997460.996830.99810.9974640.999360.99810.99810.997460.999360.998735110.998730.9987310.9993660.999360.998730.9993670.999360.998730.9993680.999360.999360.999369110.99936101在實(shí)驗(yàn)一和實(shí)驗(yàn)二中，我們發(fā)現(xiàn)算法經(jīng)常收斂于局部最優(yōu)解，我們采取的方法是保留若干最優(yōu)個體，然后把其他適應(yīng)度相同的個體重新初始化的方法。加入變比之前，算法初期，產(chǎn)生更優(yōu)解的時間間隔比較平均，到了算法后期（2500代以后），隨著種群適應(yīng)度的提高，進(jìn)化壓力越來越

30、大，時間間隔越來越長，產(chǎn)生更優(yōu)解就變得十分困難。最后也沒有產(chǎn)生最優(yōu)解（適應(yīng)度為1的解），主要是由于不滿足彈性約束2，其他條件可以較好滿足。加入變比以后，由于能夠以一定概率選擇較差的解，種群的適應(yīng)度更好，產(chǎn)生更優(yōu)解的時間間隔更為平均，最后產(chǎn)生解的適應(yīng)度更高，用的時間反而更短。在實(shí)驗(yàn)三中，由于優(yōu)化函數(shù)實(shí)際是把染色體中的不良基因有目的性的進(jìn)行修正，修正時也使用隨機(jī)函數(shù)隨機(jī)選擇合適的時間段，這樣既增加了種群的適應(yīng)度，還增加了種群的多樣性，避免了收斂于局部最優(yōu)解的問題。這種變化在初始化（第0代）和進(jìn)化第1代個體的適應(yīng)度中表現(xiàn)的尤為明顯，初始化種群中最優(yōu)個體的適應(yīng)度在0.97左右，第一代的適應(yīng)度在0.99

31、2左右，僅用一代就至少提高了0.02，達(dá)到了實(shí)驗(yàn)1、2需進(jìn)化5000代才能達(dá)到的適應(yīng)度。并且在10代以內(nèi)就可以找到最優(yōu)解，使適應(yīng)度達(dá)到1，大大減少了排課時間，提高了排課效率。交叉和變異函數(shù)以班為單位，對原有的染色體破壞程度較小，尤其是變異函數(shù)，我們發(fā)現(xiàn)經(jīng)過變異操作適應(yīng)度一般不會降低，具體原因還有待探究。當(dāng)然，與實(shí)驗(yàn)1和實(shí)驗(yàn)2相比，實(shí)驗(yàn)3添加一些輔助的數(shù)據(jù)結(jié)構(gòu)和函數(shù)，占用的內(nèi)存資源更多，每代計算的時間更長，但最終用時（4min）比原來（20min）大大減低，隨著計算機(jī)內(nèi)存的不斷增大和處理器能力的不斷增強(qiáng)，這個問題就越來越不明顯了。5 總結(jié)本文在使用傳統(tǒng)遺傳算法解決時間表問題的基礎(chǔ)上，減小了問題的

32、復(fù)雜度，提出了自己的編碼方案和操作方法，并大膽加入優(yōu)化函數(shù)，不僅有效解決了陷于局部最優(yōu)解的問題，并且在排課時的能夠根據(jù)排課時產(chǎn)生的沖突調(diào)用相應(yīng)的優(yōu)化函數(shù)進(jìn)行優(yōu)化處理，使排課效率大大提高。不僅提出了完整的解決方案，并且對遺傳算法解決時間表問題進(jìn)行了有益的探索，在解決其它問題時也具有借鑒意義。致謝本論文的工作是在我的導(dǎo)師董兆安老師的悉心指導(dǎo)下完成的，導(dǎo)師淵博的知識、嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度、科學(xué)的工作方法、勤奮的敬業(yè)精神給了我極大的幫助和影響，讓我受益匪淺，在本文完成之際，衷心感謝導(dǎo)師對我的關(guān)心和指導(dǎo)。在開發(fā)系統(tǒng)及撰寫論文期問，同組的馬義凱、王丙景、邢兆林同學(xué)對我論文及研究工作給予了熱情幫助，在此向他們表達(dá)

33、我的感激之情。衷心感謝在我漫長的求學(xué)過程中，給予我無私幫助的眾多老師、同學(xué)們。感謝我的家人，他們的理解和支持使我能夠完成我的學(xué)業(yè)。借此機(jī)會，向在百忙中抽出時間評審本文的專家表示衷心的感謝!參考文獻(xiàn)1 Gotlieb,.The Construction of Class-Teacher Time-Tables C, Proceedings of the IFIP Congress., 1962, North-Holland Pub. Co., Amsterdam: 73-772 Erben,W. and Keppler, J. A Genetic Algorithm Solving a Week

34、ly Course Timetabling ProblemM, in Practice and Theory of Automated Timetabling, Springer-Verlag Lecture Notesin Computer Science 1153, Burke & Ross, eds., 19963 Arvind.S.Babu , R.Chockalingam, S.Kavitha. A Hybrid Genetic Algorithm Approach to a Departmental Class Timetabling Problem Using Efficient

35、 Data StructuresJ ,2010 International Journal of Computer Applications, 2010,Volume 1 No. 17:117-121 4 Antariksha Bhaduri.University Time Table Scheduling Using Genetic Artificial Immune NetworkC, artcom, 2009 International Conference on Advances in Recent Technologies in Communication and Computing

36、, 2009:289-292,5 滕姿，鄭輝文，楊久俊.基于遺傳算法的排課系統(tǒng)的設(shè)計與實(shí)現(xiàn)J，計算機(jī)應(yīng)用，2007年12月，(27)：199-2046 黃杰，陳琳，鄒鵬.一種求解極小診斷的遺傳模擬退火算法J, 軟件學(xué)報,2004年 09期，(15)：1345-13507 （美）布克蘭德，游戲編程中的人工智能技術(shù)M，吳祖增，沙鷹，譯.北京，2006附錄實(shí)驗(yàn)一和實(shí)驗(yàn)二 的數(shù)據(jù)實(shí)驗(yàn)一實(shí)驗(yàn)二代數(shù)適應(yīng)度代數(shù)適應(yīng)度6010.6400.6230.7240.6450.8110.6820.8300.7470.8550.7690.9220.8120.9550.8210.9890.8450.10360.8640.10650.14070.10980.14220.11380.14670.11440.14830.11800.16820.12870.17430.13140.17660.13230.20550.13460.