畢業(yè)設(shè)計-基于遺傳算法的高校網(wǎng)上排課系統(tǒng)-文庫吧
2025-10-29 13:57 本頁面
【正文】 提高種群的適應(yīng)度，并有效縮短了產(chǎn)生最優(yōu)解的時間。 最后使用 和 C實現(xiàn)了一個 網(wǎng)上自動 排課 系統(tǒng)，并使用本學(xué)院的真實數(shù)據(jù)進行測試，滿足所用的約束條件， 產(chǎn)生了滿意的結(jié)果。 關(guān)鍵詞 ： 大學(xué)排課問題 遺傳算法 沖突檢測 在線 An Optimized Geic Algorithm Based University Timetabling System Student Majoring in Computer Science amp。 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。 Geic Algorithm。 Collision Detection。 Online。 1 引 言 研究背景和意義 長期以來， 在高校的教務(wù)管理中 通常使用手工或者 輔助軟件進行排課，手工排課相對更為常見，一般是對上一年的課表稍加修改然后予以沿用。 然而 隨著專業(yè)的發(fā)展和高校的擴招， 在 不同年級之間，不論從人數(shù)、授課教師還是開設(shè)的課程， 與原來相比 都有較大的不同。因而往年的課表對于排課的借鑒作用逐步削弱，一種能滿足各種排課約束條 件的自動排課軟件 呼之欲出 。 尤其在網(wǎng)絡(luò)不斷發(fā)展的今天，在線的排課系統(tǒng)更能給教務(wù)人員帶來更多的便利。 國內(nèi)外研究的現(xiàn)狀 排課問題 ， 也稱為 課程表 問題。 目前，國內(nèi)外已經(jīng)有很多人對于這個 課題 進行了研究 ，提出的解決方法也多種多樣。 1963 年， C. C. Gotlieb 在其 The Construction of ClassTeacher TimeTables[1]一文中 第一次提出了課表編排的數(shù)學(xué)模型。 1975 年， Even. S證明 了 排課問題是一個 NP 完全問題 ,無法用計算機實現(xiàn)， 從理論上對時間表問題有了全新的認(rèn)識 。 因而，眾多的研究者們又開始考慮用其他 方 法來解決這一問題， 比如使用組合邏輯 、禁忌搜索、決策系統(tǒng)、 貪心算法、圖論、 模擬退火算法、 遺傳算法 [2,3]、免疫網(wǎng)絡(luò) [4]等。其中，遺傳算法因為其良好的 智能 性、 并行性 、簡單易用、魯棒性強等特點 ，成為一種優(yōu)秀的亞啟發(fā)式算法，并成功的應(yīng)用于例如 TSP、地圖著色、衛(wèi)星軌道控制等方面，在 解決 課程表 問題方面 也有著不俗的表現(xiàn)。 2 在國內(nèi)，雖然較國外起步較晚， 80 年代以來，清華大學(xué)、大連理工大學(xué)、 原 南京工學(xué)院、西安交通大學(xué) 等 國內(nèi)高校 都進行了相關(guān)的研究并研制了相應(yīng)的軟件。 比如清華大學(xué)的 TISER 系統(tǒng)，西安交大自行開發(fā)的排課系統(tǒng)，中山大學(xué)基于智能規(guī)劃的排課系統(tǒng)，華中科技大學(xué)的基于模糊專家系統(tǒng)的排課系統(tǒng)，武漢大學(xué)基于回溯算法的排課系統(tǒng)等。 從實際情況來看，由于排課問題的復(fù)雜性和各個 學(xué)校自身教學(xué)的特殊性，國內(nèi)外研制開發(fā)的這些軟件系統(tǒng)實用性仍然有待提高。 排課問題作為 NP 問題，它的解決也有著典型的代表性。 所以，對排課問題的研究無論從理論還是實踐上都有著重要意義。 2 課程表問題 課程表問題簡介 課程表問題是 把 教師、教室、班級、課程 的組合 安排到一天的各個時間段上 。 根據(jù)本院實際情況， 一周中每一天分為 4 個時間段，上午兩個，分別為兩個小時，下午和晚上各一個，分別為三個小時。 這樣一周共有 20 個時間段 。 課程表問題 中的基本約束 課程表問題 在實際安排中的約束條件有以下幾個方面。 硬性約束，即必須滿足的約束 教室不沖突： 一個 教室同一時間不能安排兩門課程，且 人數(shù)不能超過 教室 的最大容量 ； 班級 不沖突： 一個 班級不能在同一時間 段安排 兩門課或兩門以上的課程， 同一班級不能同一時間在不同地點上課 ； 教師不沖突： 一個 教師不能同一時間在不同地點上課。 彈性約束，即盡量滿足的約束，滿足此種約束更利于教學(xué) 英語這類課程應(yīng)盡量安排在上午進行 ； 每周 課時量較多的課程應(yīng)在一周的五天中均勻安排 ； 每周多次的課程盡量安排在同一間教室 ； 時長為三個 學(xué)時的課程應(yīng)該安排在下午或晚上 ； 學(xué)校規(guī)定有統(tǒng)一活動的時間不能安排 課程 。 另外，學(xué)校已經(jīng)安排公共課程的時間段是不能給相關(guān)班級安排課程的。 3 排課系統(tǒng)的具體設(shè)計實現(xiàn) 模塊劃分 系統(tǒng)主要分為以下幾個模塊： 系統(tǒng)登錄模塊：作用是驗證用戶身份，并轉(zhuǎn)入相應(yīng)的界面。 信息管理模塊 ：在左側(cè)菜單欄顯示的用戶的權(quán)限，用戶可以點擊各菜單使用相應(yīng)的功能。 包括： 添加教室、添加課程、添加教師、添加班級 。 信息顯示模塊：包括顯示、查詢和修改 管理員信息、教室信息、教師信息、課程信息、班級信息 。 自動排課模塊：包括 預(yù)排公共課 、 添加本學(xué)期課程安排、自動排課、顯示排課結(jié)果、顯示全系課表 。 課程表問題基本數(shù)據(jù)結(jié) 構(gòu)介紹 Professor 類：保存教師的基本信息和操作 StudentGroups 類：保存班級的基本信息和操作 Room 類： 表示教室 Course 類： 表示一 門 課程 CourseClass 類：表示一次課程安排，即某教師給某個班級上某節(jié)課 3 PreCourseClass 類： 是 CourseClass 類的子類， 表示一次預(yù)排課，即 自動排課前已經(jīng)確定的課程安排 GAAutomatedTT 類：本算法的核心類，定義了交叉、變異、計算適應(yīng)度等函數(shù)及其配套使用的數(shù)據(jù)結(jié)構(gòu) 遺傳算法的設(shè)計與實現(xiàn) 問題分解 課程表問題雖然是教師、教 室、班級 、課程四 者之
公司管理相關(guān)推薦
鄂ICP備17016276號-1