【正文】 這將是我大學(xué)四年里一段十分美好的回憶。 39 在本文中，遺傳算法被充分應(yīng)用在排課中，對使用遺傳算法研究及實現(xiàn)排課系統(tǒng)的編碼模式進行了深入地討論，以對課表進行最大優(yōu)化為目標(biāo)，對傳統(tǒng)編碼模式進行了修正和改進。 然后處理班級 +教師 +課程 +時間片記錄，先讀取第一列，依次判斷每行是哪種課程屬性，還有就是判斷就看它是哪個班級，用指定的教學(xué)樓里的教室去填充它（當(dāng)然得根據(jù)教師和班 30 級的情況，例如人數(shù)問題），如果不是，就檢查下一行，直到處理完這列； 對上面的處理迭代執(zhí)行，直到 25個時間片都處理完。本文將用此策略進行雜交遺傳，這樣可以保證將好的個體保留到下一代。 (2)選擇率 為使優(yōu)勢個體的特性得以保留， 應(yīng)確保適應(yīng)度值高的優(yōu)良個體被選入下一代，故構(gòu)造如 29 下選擇率及選擇數(shù)計算公式： 期望的選擇率： Pselect=Fit(i)/FitSum 其中 Fit (i)為某個個體適應(yīng)度值， FitSum 為種群的適應(yīng)度值總和， i=1, 2,隨機選擇一個數(shù)， 滿足條件就交換此點的染色體。而適應(yīng)度函數(shù)值越大，則課程表的安排越合理、有效。因此，如何把這些“期望 ”轉(zhuǎn)化為具體的“值”，是使排課系統(tǒng)得以智能化的關(guān)鍵所在。 (6)取其中任意的重復(fù)課數(shù)且為 1的位。//后 25 位作為掩碼來表示有重復(fù)課的時間 //片，前 7 位用來標(biāo)識重復(fù)課的總節(jié)數(shù) }TEACHER_INFOR。 關(guān)聯(lián)容器的使用方法如圖 47 所 示： 22 圖 47 容器結(jié)構(gòu)圖 Chart 47 vessel structure chart 完成種群初始化后，個體的數(shù)據(jù)結(jié)構(gòu)如下圖示： 圖 48 個體結(jié)構(gòu)圖 Chart 48 individual structure chart 沖突檢測及排除 對每一個課程表二維數(shù)組 kcb (25,bjs)進行沖突檢測，然后用自動定位變異算子消除沖突。如產(chǎn)生的隨機數(shù)對應(yīng)的時間片中己有數(shù)據(jù)，則重新產(chǎn)生，直到將所有教師編碼無重復(fù)地填入該行中。在大多數(shù)，每周上 6學(xué)時的課程不會太多，大多數(shù)時 4 學(xué)時和 2 學(xué)時； 通過以上把課程與教師等同的處理后，原課表的五要素 (班級、教室、課程、時間、教師 )轉(zhuǎn)化為四要素 (班級、課程、時間）和班級。 我們給了 15bit去表示教師 ， 15bit能表示 215個數(shù)，足矣滿足任何一所高校的教師編號，所以，在數(shù)據(jù)庫里，教師表里教師編號的數(shù)據(jù)項要為短整型。 (3)遺傳操作 :包括選擇 算子 、交叉 算子 和變異 算子，產(chǎn)生子代，逐漸優(yōu)化。 這些關(guān)系用 ER 圖表示如圖 41， 42， 43: 圖 41 院管理 ER圖 Chart 41 the ER chart of college management 13 圖 42 校管理 ER圖 Chart 42 the ER chart of school management 圖 43 總 ER 圖 Chart 43 the overall ER chart 邏輯模型設(shè)計 在邏輯模型設(shè)計中 ， 并不是劃分 數(shù)據(jù) 的 粒度 越小越精確就會 越好，而是要符合設(shè)計現(xiàn)狀要求和系統(tǒng)實現(xiàn)便捷，也就是說，范式越高也不一定越好。 圖 32 排課系統(tǒng)數(shù)據(jù)流 第 2 層 Chart 32 the second layer of timetabling system data flow chart 根據(jù)登錄者不同的身份，進入不同的功能模塊，分別進行不同的操作，學(xué)院身份進入圖33的學(xué)院管理模塊，落實學(xué)院開課任務(wù)書，教務(wù)處身份進入圖 15的校管理模塊，匯聚校開課任務(wù)書，并且進行排課。 所以，可知 在三類約束條件之中，前兩者是衡量排課方案是否切實可行的基本 標(biāo)準(zhǔn)，軟約束是衡量排課方案 是否人性化 的標(biāo)準(zhǔn)，通常判別一個排課方案的優(yōu)劣標(biāo)準(zhǔn)有多個。然后，對這個（班級，教師，課程，時間）記錄做變換，讓位置表去填充它，當(dāng)然是按條件填充，就可以完成整個排課的大部分工作了，從而得到課表。這一模塊由學(xué)院排課工作人員來設(shè)置，如設(shè)置學(xué)年學(xué)期就是設(shè)置即將排課的學(xué)年學(xué)期，合并本學(xué)院的兩個班級組成一個新班一塊上一門公共課，設(shè)置一門課程則為 6 上課周數(shù)、每周上課節(jié)次、有哪位老師講授等等信息 。 (4)“固定課”問題 :有的教師因為某些原因需要安排特定的教學(xué)時一段，如 教室受到其他課程的影響，或者 某學(xué)院部門領(lǐng)導(dǎo)，因工作性質(zhì)關(guān)系，須指定安排上課時間為“星期五的第 6節(jié)”，這樣的要求在編排課程表時必須滿足，即“ 固定 時段”問題。 教師和課程問題 每個課程都有自己的編號、名稱以及開課學(xué)院 。 (4)下午 7, 8 節(jié)課 4:205:50。 (5)課表確定后，進行課表的查詢。要想編排好學(xué)校的課程表，需要綜合考慮學(xué)校的教師、教室、學(xué)生、班級、時間等多方面因素，反復(fù)調(diào)整，避免沖突 。文 [1]中提到編碼時染色體上基因片存儲信息大小為 11 字節(jié)，而本文的編碼方式一個基因片只用了 6 字節(jié)，輕裝運行，經(jīng)試驗得出，速度更快。 Timetabling。 本科畢業(yè)論文（設(shè)計） 題 目 基于遺傳算法的 高校 排課系統(tǒng) 學(xué) 院 計算機與信息科學(xué)學(xué)院、軟件學(xué)院 專 業(yè) 網(wǎng)絡(luò)工程 年 級 200X 級 學(xué) 號 姓 名 指 導(dǎo) 老 師 成 績 200X 年 4 月 30 日 ............................................................................................................................. 1 ..................................................................................................................... 2 業(yè)務(wù)需求分析 ................................................................................................... 2 數(shù)據(jù)需求分析 .................................................................................................. 3 時間問題 ................................................................................................. 3 教師和課程問題 .................................................................................... 4 教室的問題 ............................................................................................. 5 功能需求分析 ................................................................................................... 5 院管理模塊 ............................................................................................. 5 校管理模塊 ............................................................................................. 6 自動排課模塊 ......................................................................................... 6 排課過程的約束條件 ....................................................................................... 7 .................................................................................................................... 9 問題陳述 .......................................................................................................... 9 數(shù)據(jù)流程圖 ...................................................................................................... 9 ................................................................................................................... 12 數(shù)據(jù)庫設(shè)計 .................................................................................................... 12 概念模型設(shè)計 ...................................................................................... 12 邏輯模型設(shè)計 ...................................................................................... 13 數(shù)據(jù)庫的物理 設(shè)計 .............................................................................. 17 自動排課系統(tǒng)的設(shè)計 ..................................................................................... 18 遺傳算法的思想 ................................................................................... 18 構(gòu)建基因編碼和染色體 ....................................................................... 19 初始化種群 .......................................................................................... 21 沖突檢測及排除 .................................................................................. 22 構(gòu)造適應(yīng)度函數(shù) .................................................................................. 23 遺傳算子 ............................................................................................... 26 設(shè)置控制參數(shù) ....................................................................................... 28 教室位置填充設(shè)計 ......................................................................................... 29 功能模塊的設(shè)計 ...................................................................................