王坤的畢業(yè)論文正式稿

1、本科生畢業(yè)論文（設計）本科生畢業(yè)論文（設計）題目基于遺傳算法的高校網(wǎng)上排課系統(tǒng)AnOptimizedGeicAlgithmBasedUniversityTimetablingSystem姓名王坤學號0611701106院系計算機科學學院專業(yè)計算機科學與技術指導教師董兆安職稱講師2010年5月20日曲阜師范大學教務處制1基于遺傳算法的高校網(wǎng)上排課系統(tǒng)計算機科學與技術專業(yè)學生王坤指導教師董兆安摘要：大學排課問題是一種NP難的組合優(yōu)化問題。在

2、傳統(tǒng)遺傳算法的基礎上，首先把問題分解以減少算法的復雜度，然后提出了適合本問題的染色體編碼方案和操作方法，以盡量減少非法個體，并采用沖突檢測和消解策略，對種群進行優(yōu)化，提高種群的適應度，并有效縮短了產(chǎn)生最優(yōu)解的時間。最后使用和C#實現(xiàn)了一個網(wǎng)上自動排課系統(tǒng)，并使用本學院的真實數(shù)據(jù)進行測試，滿足所用的約束條件，產(chǎn)生了滿意的結(jié)果。關鍵詞：大學排課問題遺傳算法沖突檢測在線AnOptimizedGeicAlgithmBasedUniversity

3、TimetablingSystemStudentMajinginComputerScienceGeicAlgithmCollisionDetectionOnline1引言1.1研究背景和意義長期以來，在高校的教務管理中通常使用手工或者輔助軟件進行排課，手工排課相對更為常見，一般是對上一年的課表稍加修改然后予以沿用。然而隨著專業(yè)的發(fā)展和高校的擴招，在不同年級之間，不論從人數(shù)、授課教師還是開設的課程，與原來相比都有較大的不同。因而往年的課表

4、對于排課的借鑒作用逐步削弱，一種能滿足各種排課約束條件的自動排課軟件呼之欲出。尤其在網(wǎng)絡不斷發(fā)展的今天，在線的排課系統(tǒng)更能給教務人員帶來更多的便利。1.2國內(nèi)外研究的現(xiàn)狀排課問題，也稱為課程表問題。目前，國內(nèi)外已經(jīng)有很多人對于這個課題進行了研究，提出的解決方法也多種多樣。1963年，C.C.Gotlieb在其TheConstructionofClassTeacherTimeTables[1]一文中第一次提出了課表編排的數(shù)學模型。1975

5、年，Even.S證明了排課問題是一個NP完全問題無法用計算機實現(xiàn)，從理論上對時間表問題有了全新的認識。因而，眾多的研究者們又開始考慮用其他方法來解決這一問題，比如使用組合邏輯、禁忌搜索、決策系統(tǒng)、貪心算法、圖論、模擬退火算法、遺傳算法[23]、免疫網(wǎng)絡[4]等。其中，遺傳算法因為其良好的智能性、并行性、簡單易用、魯棒性強等特點，成為一種優(yōu)秀的亞啟發(fā)式算法，并成功的應用于例如TSP、地圖著色、衛(wèi)星軌道控制等方面，在解決課程表問題方面也有著