【正文】 是一種試圖在多代繁衍中保持選擇壓力的方法，其在開(kāi)始的幾代收斂較快，但仍需很長(zhǎng)的時(shí)間才能得到解。 加入變比未加入優(yōu)化函數(shù)10 2021 4000 6000代數(shù)適應(yīng)度適應(yīng)度 圖 42 加入波茲曼變比未加入優(yōu)化函數(shù) 加入波茲曼變比并加入優(yōu)化函數(shù)的條件下 ，進(jìn)行了 6 次實(shí)驗(yàn)，結(jié)果如 表 41 所示。 交叉和變異函數(shù)以班為單位，對(duì)原有的染色體破壞程度較小，尤其是變異函數(shù)， 我們發(fā)現(xiàn) 經(jīng)過(guò)變異操作適應(yīng)度一般不會(huì)降低 ，具體原因還有待探究 。 借此機(jī)會(huì)，向在百忙中抽出時(shí)間評(píng)審本文的專(zhuān)家表示衷心的感謝 ! 參考文獻(xiàn) [1] Gotlieb,.The Construction of ClassTeacher TimeTables [C], Proceedings of the IFIP Congress., 1962, NorthHolland Pub. Co., Amsterdam: 7377 [2] Erben,W. and Keppler, J. A Geic Algorithm Solving a Weekly Course Timetabling Problem[M], in Practice and Theory of Automated Timetabling, SpringerVerlag Lecture Notesin Computer Science 1153, Burke amp。 5 總結(jié) 本文在使用傳統(tǒng)遺傳算法解決時(shí)間表問(wèn)題的基礎(chǔ)上， 減小 了問(wèn)題的復(fù)雜度，提出了自己的編碼方案和操作方法，并大膽加入優(yōu)化函數(shù) ， 不僅 有效解決了陷于局部最優(yōu)解的問(wèn)題，并 且在排課時(shí)的能夠根據(jù)排課時(shí)產(chǎn)生的沖突調(diào)用相應(yīng)的優(yōu)化函數(shù)進(jìn)行優(yōu)化處理，使排課效率大大提高。 加入變比之前， 算法初期，產(chǎn)生更優(yōu)解的時(shí)間間隔比較平均，到了 算法后期（ 2500 代以后）， 隨著種群適應(yīng)度的提高，進(jìn)化壓力越來(lái)越大， 時(shí)間 間隔越來(lái)越長(zhǎng) ， 產(chǎn)生 更 優(yōu)解 就變得十分困難 。其實(shí)，波茲曼變比與模擬退火算法類(lèi)似， 它 能以一定的概率接 受 劣解 ，以保持種群的多樣性。 這樣 經(jīng)過(guò)若干代進(jìn)化的種 群中能夠始終保持進(jìn)化過(guò)程中所找到的歷代最優(yōu)個(gè)體，能夠有效防止種群整體退化現(xiàn)象。它 根據(jù)個(gè)體對(duì)于目標(biāo)函數(shù)的適應(yīng)情況，將高適應(yīng)值的個(gè)體選中，使其基因得以遺傳復(fù)制到下一代，而低適應(yīng)值的個(gè)體染色體則被淘汰。 所以我們編寫(xiě)了三個(gè)優(yōu)化函數(shù) 進(jìn)行優(yōu)化。對(duì)于排課算法來(lái)說(shuō)，可以選擇某班某節(jié)課重新安排、選擇某班多節(jié)課重新安排或某班全部課程重新安排 ，也可以選擇某班級(jí)的兩節(jié)課互相交換 。 交叉 操作 常見(jiàn)的 交叉操作有單點(diǎn)交叉、多點(diǎn)交叉、兩點(diǎn)交叉等。 ID ListListCourseClass 共 20 個(gè)時(shí)間段，表示一周的課表 一個(gè)染色體 …… .. ……. ListCourseClass 4 種群初始化 初始化是為種群中的每個(gè)個(gè)體根據(jù)本學(xué)期的課程安排隨機(jī)產(chǎn)生一份課表 。在求解完畢后再使用一個(gè)算法來(lái)完成教室的分配就可以得到最終的解。 彈性約束，即盡量滿足的約束，滿足此種約束更利于教學(xué) 英語(yǔ)這類(lèi)課程應(yīng)盡量安排在上午進(jìn)行 ； 每周 課時(shí)量較多的課程應(yīng)在一周的五天中均勻安排 ； 每周多次的課程盡量安排在同一間教室 ； 時(shí)長(zhǎng)為三個(gè) 學(xué)時(shí)的課程應(yīng)該安排在下午或晚上 ； 學(xué)校規(guī)定有統(tǒng)一活動(dòng)的時(shí)間不能安排 課程 。 從實(shí)際情況來(lái)看，由于排課問(wèn)題的復(fù)雜性和各個(gè) 學(xué)校自身教學(xué)的特殊性，國(guó)內(nèi)外研制開(kāi)發(fā)的這些軟件系統(tǒng)實(shí)用性仍然有待提高。 國(guó)內(nèi)外研究的現(xiàn)狀 排課問(wèn)題 ， 也稱為 課程表 問(wèn)題。 Technology Tutor Abstract: University Course Timetable Problem is NPHard binatorial optimization problem. Based on the traditional Geic Algorithm, we depensate the problem to decrease the plexity, advance the problemspecific chromosome and operations to avoid generate illegal timetables, and use collision detection and resolution to optimize the population, increase the fitness and decrease the time needed. Finally, we implement the online timetabling system in and C. The algorithm is tested with real date from our college, satisfies all the constraints of problem and yield promising result. Key words: University Timetabling。 關(guān)鍵詞 ： 大學(xué)排課問(wèn)題 遺傳算法 沖突檢測(cè) 在線 An Optimized Geic Algorithm Based University Timetabling System Student Majoring in Computer Science amp。 尤其在網(wǎng)絡(luò)不斷發(fā)展的今天，在線的排課系統(tǒng)更能給教務(wù)人員帶來(lái)更多的便利。 比如清華大學(xué)的 TISER 系統(tǒng)，西安交大自行開(kāi)發(fā)的排課系統(tǒng)，中山大學(xué)基于智能規(guī)劃的排課系統(tǒng)，華中科技大學(xué)的基于模糊專(zhuān)家系統(tǒng)的排課系統(tǒng)，武漢大學(xué)基于回溯算法的排課系統(tǒng)等。 硬性約束，即必須滿足的約束 教室不沖突： 一個(gè) 教室同一時(shí)間不能安排兩門(mén)課程，且 人數(shù)不能超過(guò) 教室 的最大容量 ； 班級(jí) 不沖突： 一個(gè) 班級(jí)不能在同一時(shí)間 段安排 兩門(mén)課或兩門(mén)以上的課程， 同一班級(jí)不能同一時(shí)間在不同地點(diǎn)上課 ； 教師不沖突： 一個(gè) 教師不能同一時(shí)間在不同地點(diǎn)上課。 課程表問(wèn)題基本數(shù)據(jù)結(jié) 構(gòu)介紹 Professor 類(lèi)：保存教師的基本信息和操作 StudentGroups 類(lèi)：保存班級(jí)的基本信息和操作 Room 類(lèi)： 表示教室 Course 類(lèi)： 表示一 門(mén) 課程 CourseClass 類(lèi)：表示一次課程安排，即某教師給某個(gè)班級(jí)上某節(jié)課 3 PreCourseClass 類(lèi)： 是 CourseClass 類(lèi)的子類(lèi)， 表示一次預(yù)排課，即 自動(dòng)排課前已經(jīng)確定的課程安排 GAAutomatedTT 類(lèi)：本算法的核心類(lèi)，定義了交叉、變異、計(jì)算適應(yīng)度等函數(shù)及其配套使用的數(shù)據(jù)結(jié)構(gòu) 遺傳算法的設(shè)計(jì)與實(shí)現(xiàn) 問(wèn)題分解 課程表問(wèn)題雖然是教師、教 室、班級(jí)