【正文】 在論文的撰寫過程中老師們給予我很大的幫助，幫助解 決了不少的難點，使得論文能夠及時完成，這里一并表示真誠的感謝。老師們認(rèn)真負(fù)責(zé)的工作態(tài)度，嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神和深厚的理論水平都使我收益匪淺。 最后，我要特別感謝我的導(dǎo)師趙達(dá)睿老師、和研究生助教熊偉麗老師。四年的風(fēng)風(fēng)雨雨，我們一同走過，充滿著關(guān)愛，給我留下了值得珍藏的最美好的記憶。感謝老師四年來對我孜孜不倦的教誨，對我成長的關(guān)心和愛護(hù)。從這里走出，對我的人生來說，將是踏上一個新的征程，要把所學(xué)的知識應(yīng)用到實際工作中去。 最后，我要感謝我的父母對我的關(guān)系和 理解，如果沒有他們在我的學(xué)習(xí)生涯中的無私奉獻(xiàn)和默默支持，我將無法順利完成今天的學(xué)業(yè)。 其次，我要感謝大學(xué)四年中所有的任課老師和輔導(dǎo)員在學(xué)習(xí)期間對我的嚴(yán)格要求，感謝他們對我學(xué)習(xí)上和生活上的幫助，使我了解了許多專業(yè)知識和為人的道理，能夠在今后的生活道路上有繼續(xù)奮斗的力量。從他身上，我學(xué)到了許多能受益終生的東西。 首先，我要特別感謝我的知道郭謙功老師對我的悉心指導(dǎo)，在我的論文書寫及設(shè)計過程中給了我大量的幫助和指導(dǎo)，為我理清了設(shè)計思路和操作方法，并對我所做的課題提出了有效的 改進(jìn)方案。這期間凝聚了很多人的心血，在此我表示由衷的感謝。本次畢業(yè)設(shè)計是對我大學(xué)四年學(xué)習(xí)下來最好的檢驗。 首先非常感謝學(xué)校開設(shè)這個課題，為本人日 后從事計算機方面的工作提供了經(jīng)驗，奠定了基礎(chǔ)。 本人愿意按照學(xué) 校要求提交學(xué)位論文的印刷本和電子版，同意學(xué)校保存學(xué)位論文的印刷本和電子版，或采用影印、數(shù)字化或其它復(fù)制手段保存設(shè)計（論文）；同意學(xué)校在不以營利為目的的前提下，建立目錄檢索與閱覽服務(wù)系統(tǒng)，公布設(shè)計（論文）的部分或全部內(nèi)容，允許他人依法合理使用。 本聲明的法律后果由本人承擔(dān)。盡我所知，除文中已經(jīng)注明引用的內(nèi)容外，本設(shè)計（論文）不含任何其他個人或集體已經(jīng)發(fā)表或撰寫過的作品成果。 學(xué)位論文作者（本人簽名）： 年 月 日 學(xué)位論文出版授權(quán)書 本 人及導(dǎo)師完全同意《中國博士學(xué)位論文全文數(shù)據(jù)庫出版章程》、《中國優(yōu)秀 碩士學(xué)位論文全文數(shù)據(jù)庫出版章程》 (以下簡稱“章程” )，愿意將本人的學(xué)位論文提交“中國學(xué)術(shù)期刊（光盤版）電子雜志社”在《中國博士學(xué)位論文全文數(shù)據(jù)庫》、 《中國優(yōu)秀碩士學(xué)位論文全文數(shù)據(jù)庫》中全文發(fā)表和以電子、網(wǎng)絡(luò)形式公開出版，并同意編入 CNKI《中國知識資源總庫》，在《中國博碩士學(xué)位論文評價數(shù)據(jù)庫》中使用和在互聯(lián)網(wǎng)上傳播，同意按“章程”規(guī)定享受相關(guān)權(quán)益。對本文的研究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式注明并表示感謝。2020 年 05 期 . [13]張春梅 ,行飛 .用自適應(yīng)的遺傳算法求解大學(xué)課表安排問題 [J].內(nèi)蒙古大學(xué)學(xué)報 :自然科學(xué)版 ,2020,33(4):459464. [14] 江齊 , 蘭競 . 遺傳 算法在排 課問題中 的運用 [J]. 重慶大學(xué)學(xué) 報 : 自然科學(xué)版 ,2020,28(11):5861. [15]唐勇 ,唐雪飛 ,王 玲 .基于遺傳算法的排課系統(tǒng) [J].計算機應(yīng)用 ,2020,22(10):9394. [16]陳行平 ,陳江 ,陳啟華 .基于遺傳算法的高校排課系統(tǒng)設(shè)計 [J].紹興文理學(xué)院學(xué)報 ,2020,24(10):2528. [17]王小平 ,曹立明 .遺傳算法 :理論、應(yīng)用與軟件實現(xiàn)西安 [M].西安 :西安交通大學(xué)出版社 ,2020. [18],”Geic Algorithms in Timetabling and Scheduling”,. Thesis,Department of Artificial Intelligence, University of Edinburgh, UK,1994. [19] . Burke, . Elliman, . Weare, A Geic Algorithm Based University Timetabling System, EastWest Conference on Computer Technologies in Education, Crimea, Ukraine, 1994, pp. 3540. [20] GAREY M R,JOHNSON D and Intractability:A guide to the theory of NP pleteness[M].Sanfrancisco: ＆ Co Ltd,1979. 附 錄 附錄 A：英文原文（單獨裝訂） 附錄 B：中文譯文（單獨裝訂 ） 33 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下進(jìn)行的研究工作所取得的成果。排課表問題的一種矩陣解法 [J]。大連鐵道學(xué)院 。1999 年 03 期 . [11]魏靜波 。回溯算法與計算機智能排課 [J]。河南大學(xué)學(xué)報 (自然科學(xué)版 )。2020 年 01 期 . [9]蘇仰娜 。自動排課系統(tǒng)的研究與實現(xiàn) [J]。面向公共機房的智能排課系統(tǒng)設(shè)計與實現(xiàn) [J]。華北電力大學(xué)（河北） 。2020 年 . [6]蘭慧 。高校排課系統(tǒng)算法設(shè)計與實現(xiàn) [D]。哈爾濱工程大學(xué) 。2020 年 . [4]佟林 。基于遺傳算法的自動排課問題的研究 [D]。西南交通大學(xué) 。2020 年 . [2]陳本慶 。使用遺傳算法編排課程表的研究與應(yīng)用 [D]。在此，還要感謝一部分在我寫作期間給予我意見和建議以及關(guān)心的同學(xué)們。后來，戴老師一次次的叮囑和認(rèn) 真指導(dǎo)，在他耐心的啟發(fā)、深厚理論知識的支持及嚴(yán)謹(jǐn)?shù)膶I(yè)教學(xué)態(tài)度下，使得我在寫作的過程中得到了強大的鼓勵和信心，并一鼓作氣堅持下來，完成到最后。謝謝！ 31 敬謝詞 這篇論文是在由指導(dǎo)老師戴亞濱老師的悉心指導(dǎo)下完成的。 此 次畢業(yè)設(shè)計是在戴亞濱老師的精心指導(dǎo)下，我進(jìn)行了理論與實踐的結(jié)合，通過這次設(shè)計，我的動手能力有了很大的提高，使我學(xué)習(xí)到了怎樣去查找翻閱有關(guān)理論資料和技術(shù)手冊，怎樣把理論知識與實踐相結(jié)合，使我對軟件開發(fā)有了一個宏觀的掌控和了解，肯定會對今后的工作產(chǎn)生深遠(yuǎn)的影響。個體數(shù)較多的種群中最有個體要比個體數(shù)較少的具有更高適應(yīng)度值，實驗結(jié)果令人滿意，證明了利用新的二進(jìn)制編碼和教室填充方法是可以的。實驗平臺是 Visual C++ 和 SQL server 2020。 (5)“特殊課”問題：像體育課，要跟硬件設(shè)施有關(guān)，故要妥善處理。 (3)“多學(xué)時”問題 :對于有些課程既可能只上一次，既 2 學(xué)時課程，而有些課程可能上多次，如 4 學(xué)時、 6 學(xué)時等，多學(xué)時的課程如何處理也是在編排課程表時必須解 決的問題。在處理課程與教師時要注意以下幾個問題 : (1)“授一班多門課”問題 :同一教師可以只上一門課，也可上多門課，如果同 一教師在同一個班級教授多門課程，那么把課程和教師作同一變量考慮就會引起課程的混亂，此問題須分情況解決，我們將在系統(tǒng)設(shè)計中，學(xué)院安排開課任務(wù)時解決此問題。如普通教室、語音室、操場、實驗室或機房等等。每個課程都要有授課教師。為了避免這種沖突產(chǎn)生，在本系統(tǒng)開發(fā)中引進(jìn)了一個沖突檢測函數(shù) fConflict()，當(dāng)排完一位教師的所有課程之后，系統(tǒng)就會用該函數(shù)對此教師課程安排的沖突情況進(jìn)行檢測并作修正。 24 圖 12 主界面 Chart 12 main interface 學(xué)院管理模塊 學(xué)院管理本院的一些教師分配。對于每一類期望值及其在總的期望值中的比例，都可以根據(jù)每一所學(xué)校的具體情況進(jìn)行必要的調(diào)整，使排課系統(tǒng)更加實用、有效。在進(jìn)化過程中，沖突必須完全消除。 如表 417所示 表 417 離散度期望值 Table 417 fitness of Discrete degree 兩課時間差 1 1 11 1 2 2 224 0、 1 113 10 7 5 期望值 0 2 4 6 10 檢查每個班級的一門課程及下一門課程的時間，算出時間差加入 F[i]（ i=0,1,2， .......n）依次計算，得出這個班級課程離散程度離散期望值 F[i] 然后，計算 F5=? F[i] 23 (2) 適應(yīng)度值 定義課表的適應(yīng)度函數(shù) Fit 為 : Fit=K1?F1+K2?F2+K3?F3+K4?F4+K5?F5 其中 Kl, K2, K3， K4， K5 為控制上述各種期望值對總期望值的影響參數(shù) (權(quán)重 )。 一門課在一周內(nèi)分散安排，提供可引導(dǎo)性學(xué)習(xí)環(huán)境。 以下共列出了相關(guān)期望值定義的 5個表 :表 41表 41表 41表 416，其中的數(shù)字分別取值于 010，是對影響期望值的各因素進(jìn)行的賦值，這些取值經(jīng)過了系統(tǒng)模塊的反復(fù)測試和調(diào)整。適應(yīng)度值實際上反映了排課人員對課表理想化編排的一種期望。而這個要求是一個模糊的不確定問題。消除冗余數(shù)據(jù)雖然能提高空間的利用率，但同時也會提高檢索的代價，因此，這三方面必須權(quán)衡，選擇一個折中方案。 這些關(guān)系用 ER圖表示如圖 8， 9， 10: 16 圖 8 院管理 ER圖 圖 9 校管理 ER圖 圖 10 總 ER圖 邏輯模型設(shè)計 在邏輯模型設(shè)計中，并不是劃分?jǐn)?shù)據(jù)的粒度越小越精確就會越好，而是要符合設(shè)計現(xiàn)狀要求和系統(tǒng)實現(xiàn)便捷，也就是說，范式越高也不一定越好。這會將數(shù)據(jù)庫的概念結(jié)構(gòu)轉(zhuǎn)換為邏輯結(jié)構(gòu)方法簡單，易于實現(xiàn)。 關(guān)聯(lián)容器的使用方法如圖 6所 示： 圖 6 容器結(jié)構(gòu)圖 完成種群初始化后，個體的數(shù)據(jù)結(jié)構(gòu)如下圖示： 15 圖 7 個體結(jié)構(gòu)圖 4 數(shù)據(jù)庫問題 數(shù)據(jù)庫設(shè)計 數(shù)據(jù)庫設(shè)計是建立系統(tǒng)數(shù)據(jù)庫及其應(yīng)用系統(tǒng)的重要環(huán)節(jié)，系統(tǒng)的各個部分能否緊密地結(jié)合在一起以及如何結(jié)合，關(guān)鍵在數(shù)據(jù)庫，只有對數(shù)據(jù)庫進(jìn)行合理的邏輯設(shè)計和有效的物理設(shè)計才能開發(fā)出完善而高效的排課系統(tǒng)。 另外，在初始化種群時，基于容器的容器使其更加簡捷。按種群規(guī)模的大小 ZQS，產(chǎn)生一定數(shù)量的個體，每個個體都存放到 一個按序編號的表中，由這些個體組成初始種群。如此循環(huán) bjs 次，產(chǎn)生了與班級數(shù)目對等的染色體數(shù)目。如產(chǎn)生的隨機數(shù)對應(yīng)的時間片中己有數(shù)據(jù)，則重新產(chǎn)生，直到將所有教師編碼無重復(fù)地填入該行中。 對每一個課程表可以形成一個二維數(shù)組 kcb (25,bjs)，每一列就表示一個班級的課表。其中 ZQS 為種群大小。 為了更好地闡述排課遺傳算法，定義排課遺傳算法名詞： a.“基因” —— 混合型的教師編碼，即 TIT25 時間片中的值； b.“染色體” —— 班級名稱與 TlT25 中的“基因”組成的串； c.“個體” —— 由 bjs（班級數(shù)）個染色體組合而成的二維數(shù)據(jù)表，即對應(yīng)于一張課表。在大多數(shù)，每周上 6 學(xué)時的課程不會太多，大多數(shù)時 4 學(xué)時和 2 學(xué)時； 通過以上把課程與教師等同的處理后，原課表的五要素 (班級、教室、課程、時間、教師 )轉(zhuǎn)化為四要素 (班級、課程、時間）和班級。 染色體的表示 對于每一門課程既可能只上一次 (規(guī)定 2 學(xué)時課占用一個時間片 )，也可能 上多次，如 4學(xué)時、 6學(xué)時等。區(qū)分：計算機專業(yè)的實驗課是和非計算機專業(yè)的上節(jié)實驗課不同的，他們有自己的實驗室，屬于專業(yè)實驗課。 為了解決“特定資源”沖突問題，可在教師編碼中加上 2B表示該教師所教授的課程的性質(zhì)。 我們給了 15bit 去表示教師， 15bit 能表示 215個數(shù)，足矣滿足任何一所高校的教師編號，所以，在數(shù)據(jù)庫里，教師表里 教師編號的數(shù)據(jù)項要為短整型。下面我們給了很清晰的解釋： 圖 4 編碼結(jié)構(gòu)圖 下面我們對每個字段給予解釋： 有些教師的課程是固定在某個時間段的，所以在排課過程中，判斷第一位就可以得知可否移動此基因片。 12 混合式編碼 構(gòu)造合適的基因結(jié)構(gòu)是遺傳算法能否順利實現(xiàn)的關(guān)鍵，設(shè)定混合式的教師編碼作為本系統(tǒng)遺傳算 法的“基因”。 (5)班級 +課程 +教師 +時間的記錄集的產(chǎn)生。 (3)遺傳操作 :包括選擇算子、交叉算子和變異算子，產(chǎn)生子代，逐漸優(yōu)化。 (1)沖突檢測和消除 :初始化種群后，先對其進(jìn)行各類沖突的檢測，如存在