畢業(yè)設(shè)計(jì)-基于遺傳算法的高校網(wǎng)上排課系統(tǒng)(編輯修改稿)
2025-01-07 13:57 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 間在時(shí)間上的組合和優(yōu)化，在實(shí)際應(yīng)用中我們發(fā)現(xiàn)，我們可以把教室根據(jù)容量進(jìn)行分類，同一容量的教室在分配中的地位是平等的，所以可以統(tǒng)計(jì)出不同容量教室的個(gè)數(shù)，遺傳算法進(jìn)行求解時(shí)，無(wú)需考慮具體教室的分配，只要求每個(gè)時(shí)間段需要某類教室的個(gè)數(shù)在該類實(shí)際個(gè)數(shù)范圍內(nèi)即可。在求解完畢后再使用一個(gè)算法來(lái)完成教室的分配就可以得到最終的解。 這樣就把問(wèn)題簡(jiǎn) 化成為教師、 班級(jí) 和課程三 者在安排課程時(shí)的組合優(yōu)化。 染色體設(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, ListListCourseClass _slotsOfStudentGroup Dictionary中的第一項(xiàng)表示班級(jí) ID，其后的 ListListCourseClass對(duì)應(yīng)該班一周的課表 ，包括 20個(gè)時(shí)間段 。其中的 ListCourseClass表示在某個(gè)時(shí)間段安排的課程。 教師的數(shù)據(jù)結(jié)構(gòu)與學(xué)生的相似： Dictionaryint, ListListCourseClass _slotsOfProfessor 圖 31 染色體示意圖 染色體直接使用類對(duì)象，省去了編碼和解碼的過(guò)程，可以直接使用類中的函數(shù)對(duì)類進(jìn)行操作 ，獲取相應(yīng)的信息 。 染色體中輔助用的數(shù)據(jù)結(jié)構(gòu) 及作用 如下： Dictionaryint, ListListCourseClass _slotsOfProfessor 教師課表， 記錄每個(gè) 教師 每周的 課表； Dictionaryint, ListListCourseClass _slotsOfStudentGroup 班級(jí)課表， 記錄每個(gè) 班級(jí) 每周 課表； Dictionaryint, Listint _freetimeOfProfessor 教師空余時(shí)間表， 記錄每個(gè) 教師 的 空余時(shí)間； Dictionaryint, Listint _freetimeOfStudentGroup 班級(jí)空余時(shí)間表， 記錄每個(gè) 班級(jí) 的 空余時(shí)間； Dictionaryint, Listint _preScheduleTime 班級(jí)預(yù)排課 時(shí)間段表， 班級(jí) 已經(jīng) 預(yù)排課時(shí)間段； Dictionaryint, Dictionaryint, Listint _CourseScheduleOfStudentGroup 課程所在時(shí)間段表， 記錄每個(gè) 班級(jí) 每 門 課程所在 的時(shí)間段 ； Dictionaryint, Listint _recordsOfBadOnesForThree 記錄未合理安排的 每周三次的課程； Dictionaryint, Listint _recordsOfBadOnesForTwo 記錄未合理安排的 每周兩次的課程 ； Dictionaryint, Dictionaryint, ListCourseClass _recordsOfBadOnesForProfessors 記錄教師出現(xiàn)沖突的課程； Dictionaryint, Listint _recordsOfBadOnesForDurationOf3 記錄未合理安排的三個(gè)課時(shí)的課程 。 ID ListListCourseClass 共 20 個(gè)時(shí)間段，表示一周的課表 一個(gè)染色體 …… .. ……. ListCourseClass 4 種群初始化 初始化是為種群中的每個(gè)個(gè)體根據(jù)本學(xué)期的課程安排隨機(jī)產(chǎn)生一份課表 。 考慮到盡量減少遺傳算法的進(jìn)化壓力，初始化的個(gè)體應(yīng)該盡量滿足所給出的約束條件。 比較所給出的約束 條件，應(yīng)該先滿足的是彈性約束的第 4 條。因?yàn)?若 在進(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í) 的課程 ，安排在下午或晚上， 再安排每周兩次 每次兩個(gè)課時(shí) 的課程 。 每次安排時(shí)，都盡量找教師和班級(jí)共同的空余時(shí)間 ， 完畢后， 把班級(jí)和教師 中相應(yīng) 的空余時(shí)間段去掉。 具體方法如下： 處理預(yù)排課信息 ， 方法是 只 去掉班級(jí)和教師空余時(shí)間表中 相應(yīng) 的 時(shí)間段 ， 但 不添加課程至課程表，以免變異時(shí)變化 ； 根據(jù)課程的性質(zhì)，包括課時(shí)數(shù)、每周上課的次數(shù)、是否是英語(yǔ) ，在空余時(shí)間段中找一個(gè) 符合約束的時(shí)間段 出來(lái) ，如果沒(méi)有隨機(jī)找一個(gè)時(shí)間段； 在班級(jí)和教師的空余時(shí)間段表中去掉該時(shí)間段，并 將其加入到班級(jí)和教師的課表中； 計(jì)算該個(gè)體的適應(yīng)度。 交叉 操作 常見(jiàn)的 交叉操作有單點(diǎn)交叉、多點(diǎn)交叉、兩點(diǎn)交叉等。在排課算法中，可以選擇某節(jié)課、某班的全部課程或某年級(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ì)較好 。 具體方法如下： 隨機(jī)生成 0100 之間的數(shù) 大于 交叉概率 進(jìn)入 2，否則跳出； 隨機(jī) 生成 需要交叉的班級(jí)； 交換 兩個(gè) 班級(jí) 的課表 ； 交換 兩個(gè) 班級(jí) 的 空余時(shí)間表 ； 交換 兩個(gè) 班級(jí)每門課程所在的時(shí)間段 ； 在教師課表中 修改 相應(yīng)的信息； 計(jì)算適應(yīng)度 。 變異操作 常見(jiàn)的變異操作有等。對(duì)于排課算法來(lái)說(shuō)，可以選擇某班某節(jié)課重新安排、選擇某班多節(jié)課重新安排或某班全部課程重新安排 ，也可以選擇某班級(jí)的兩節(jié)課互相交換 。因?yàn)樵?排課過(guò)程 中，尤其是后期，產(chǎn)生沖突的課程僅僅是某班的某幾節(jié)課，對(duì)全部課程重新安排容易造成 以前進(jìn)化 的失效和個(gè)體適應(yīng)度的過(guò)分降低。 而 具體選擇變異的課程數(shù)量還需實(shí)驗(yàn)研究， 所以我們 選擇某班級(jí)的兩節(jié)課互相交換 。 具體方法如下： 隨機(jī)生成 0100 之間的數(shù)大于變異概率進(jìn)入 2，否則跳出 5 隨機(jī)產(chǎn)生要變異的班級(jí)； 產(chǎn)生兩個(gè)變異的時(shí)間段； 兩處的課 程 若有 3 學(xué)時(shí)的， 與其 交 換的課程 的時(shí)間段 必須是 在 下午 或晚上 ，
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1