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

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

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

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

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

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