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

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

2、傳算法的設(shè)計(jì)與實(shí)現(xiàn)34 結(jié)果分析65 總結(jié)8致謝8參考文獻(xiàn)8附錄9基于遺傳算法的高校網(wǎng)上排課系統(tǒng)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生指導(dǎo)教師摘要：大學(xué)排課問(wèn)題是一種NP難的組合優(yōu)化問(wèn)題。在傳統(tǒng)遺傳算法的基礎(chǔ)上，首先把問(wèn)題分解以減少算法的復(fù)雜度，然后提出了適合本問(wèn)題的染色體編碼方案和操作方法，以盡量減少非法個(gè)體，并采用沖突檢測(cè)和消解策略，對(duì)種群進(jìn)行優(yōu)化，提高種群的適應(yīng)度，并有效縮短了產(chǎn)生最優(yōu)解的時(shí)間。最后使用ASP.NET和C#實(shí)現(xiàn)了一個(gè)網(wǎng)上自動(dòng)排課系統(tǒng)，并使用本學(xué)院的真實(shí)數(shù)據(jù)進(jìn)行測(cè)試，滿足所用的約束條件，產(chǎn)生了滿意的結(jié)果。關(guān)鍵詞：大學(xué)排課問(wèn)題 遺傳算法 沖突檢測(cè) 在線 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 研究背景和意義長(zhǎng)期以來(lái)，在高校的教務(wù)管理中通常使用手工或者輔助軟件進(jìn)行排課，手工排課相對(duì)更為常見(jiàn)，一般是對(duì)上一年的課表稍加修改然后予以沿用。然而隨著專業(yè)的發(fā)展和高校的擴(kuò)招，在不同年級(jí)之間，不論從人數(shù)、授課

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、體產(chǎn)生后代。其實(shí)，波茲曼變比與模擬退火算法類似，它能以一定的概率接受劣解，以保持種群的多樣性。在文獻(xiàn)6中已經(jīng)發(fā)現(xiàn)模擬退火算法與遺傳算法結(jié)合可以很大的提高算法的效率。波茲曼變比使用一個(gè)連續(xù)變化的溫度來(lái)控制選擇率，公式如下：溫度初始化為種群中個(gè)體數(shù)量的兩倍，逐代降低的溫度為0.05，最低值為1。具體方法如下：1、 逐代降低少量的溫度，但確保不低于最低值；2、 通過(guò)循環(huán)，計(jì)算，保存，并計(jì)算平均值；3、 通過(guò)循環(huán)，使用公式計(jì)算新的適應(yīng)度。4 結(jié)果分析初始種群為200個(gè)個(gè)體，交叉概率75%，變異概率50%，數(shù)據(jù)來(lái)源于本院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)個(gè)體，然后把其他適應(yīng)度相同的個(gè)體重新初始化的方法。加入變比之前，算法初期，產(chǎn)生更優(yōu)解的時(shí)間間隔比較平均，到了算法后期（2500代以后），隨著種群適應(yīng)度的提高，進(jìn)化壓力越來(lái)越

30、大，時(shí)間間隔越來(lái)越長(zhǎng)，產(chǎn)生更優(yōu)解就變得十分困難。最后也沒(méi)有產(chǎn)生最優(yōu)解（適應(yīng)度為1的解），主要是由于不滿足彈性約束2，其他條件可以較好滿足。加入變比以后，由于能夠以一定概率選擇較差的解，種群的適應(yīng)度更好，產(chǎn)生更優(yōu)解的時(shí)間間隔更為平均，最后產(chǎn)生解的適應(yīng)度更高，用的時(shí)間反而更短。在實(shí)驗(yàn)三中，由于優(yōu)化函數(shù)實(shí)際是把染色體中的不良基因有目的性的進(jìn)行修正，修正時(shí)也使用隨機(jī)函數(shù)隨機(jī)選擇合適的時(shí)間段，這樣既增加了種群的適應(yīng)度，還增加了種群的多樣性，避免了收斂于局部最優(yōu)解的問(wèn)題。這種變化在初始化（第0代）和進(jìn)化第1代個(gè)體的適應(yīng)度中表現(xiàn)的尤為明顯，初始化種群中最優(yōu)個(gè)體的適應(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ù)以班為單位，對(duì)原有的染色體破壞程度較小，尤其是變異函數(shù)，我們發(fā)現(xiàn)經(jīng)過(guò)變異操作適應(yīng)度一般不會(huì)降低，具體原因還有待探究。當(dāng)然，與實(shí)驗(yàn)1和實(shí)驗(yàn)2相比，實(shí)驗(yàn)3添加一些輔助的數(shù)據(jù)結(jié)構(gòu)和函數(shù)，占用的內(nèi)存資源更多，每代計(jì)算的時(shí)間更長(zhǎng)，但最終用時(shí)（4min）比原來(lái)（20min）大大減低，隨著計(jì)算機(jī)內(nèi)存的不斷增大和處理器能力的不斷增強(qiáng)，這個(gè)問(wèn)題就越來(lái)越不明顯了。5 總結(jié)本文在使用傳統(tǒng)遺傳算法解決時(shí)間表問(wèn)題的基礎(chǔ)上，減小了問(wèn)題的

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

33、我的感激之情。衷心感謝在我漫長(zhǎng)的求學(xué)過(guò)程中，給予我無(wú)私幫助的眾多老師、同學(xué)們。感謝我的家人，他們的理解和支持使我能夠完成我的學(xué)業(yè)。借此機(jī)會(huì)，向在百忙中抽出時(shí)間評(píng)審本文的專家表示衷心的感謝!參考文獻(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è)計(jì)與實(shí)現(xiàn)J，計(jì)算機(jī)應(yīng)用，2007年12月，(27)：199-2046 黃杰，陳琳，鄒鵬.一種求解極小診斷的遺傳模擬退火算法J, 軟件學(xué)報(bào),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.