基于遺傳算法和禁忌搜索算法的排課系統研究

《基于遺傳算法和禁忌搜索算法的排課系統研究》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、基于遺傳算法和禁忌搜索算法的排課系統研究　　引言　　排課是高校教學管理中十分重要而又復雜的管理工作之一，由于排課問題涉及的因素有時間、教師、教室、課程、班級等，因此排課問題是一個有約束條件、多目標、模糊性極強的組合優(yōu)化問題[1]。由于各學校資源差異較大，約束條件復雜，排課系統難以具有普遍適用性。一般教務排課仍以手工為主，計算機為輔，效率低下。研究靈活、高效、自動化程度高的排課系統需求迫切，具有現實意義?！　夂茉缇陀腥寺撁搜芯空n表的編排問題，一般利用啟發(fā)式函數，并且大多數啟發(fā)式方法都是模擬手工排課的過程實現的。國內對排課問題的研究較晚，并

2、且大部分學者研究的排課系統都依賴于各個學校的教學體制，不具有普遍適用性[2]。從實際使用情況看，國內研究的排課系統軟件在性能上也達不到使用要求?！　∵z傳算法是一種借鑒生物界自然選擇和進化機制發(fā)展起來的高度并行、自適應的隨機搜索算法；而禁忌搜索算法是對局部領域的一種擴展，是一種全局逐步尋優(yōu)的搜索算法。通過對比分析，遺傳算法和禁忌搜索算法在解決復雜優(yōu)化問題中有明顯的優(yōu)勢，因而本文采用遺傳算法和禁忌搜索算法來實現排課系統。　　1排課系統分析　　排課問題的主要任務是將班級、教師、課程安排在一周內某一不發(fā)生沖突的時間和教室中，保證課表在時間分配上符合

3、一切共性和個性要求，使安排在各個目標上盡量達到最優(yōu)?！　「鶕欠癖仨殱M足，可以將約束條件分為硬約束和軟約束。硬約束是指教師、　　班級、教室在時空概念上發(fā)生了沖突，它是在排課過程中必須滿足的約束條件，否則將會使排課結果毫無意義。軟約束是指排課過程中需盡量滿足的約束條件，它能夠使課表更加合理。排課的目標是要滿足所有的硬約束條件，同時盡可能多地滿足軟約束條件，實現一個使用方便、效率高的排課系統?！　』谶z傳算法與禁忌搜索算法的排課系統　　在整個排課過程中，首先需要確定教學計劃，然后根據教學計劃生成教學任務，教學任務確定了課程、教師、班級3者之間的

4、關系。在排課問題中，由于涉及到教師、教室、課程、班級、時間這5個因素，可以將課程、教師、班級這3個因素綁定為一個整體，作為一個元組，并對這個元組隨機分配時間與教室，生成一個可行的課表?！　”疚膽眠z傳算法對排課問題進行編碼，然后再進行選擇、交叉、變異等操作，計算適應度函數。在遺傳算法的運算過程中使用禁忌搜索算法來代替變異算子，從而得到更優(yōu)的個體解，最終生成有效的課表。　　遺傳算法編碼　　遺傳算法的編碼方法有很多種，針對排課系統，本文采用混合式編碼方式，將混合式編碼作為排課系統遺傳算法的基因。該基因由教師編號、課程編號、班級編號組成，每個教師

5、都有一個唯一的教師編號，用八位數字表示。課程編號用一位數字表示，表示該教師教的第幾門課程。班級編號也用一位數字表示，表示該教師教的第幾個班級。這種編碼方式解決了特定時段教師課程的安排問題和普通時段課程的分配問題。系統只要按照算法流程對編碼進行處理，對結果進行不斷的篩選，就可以得到完善的課程表，通過混合式編碼將教師、課程、班級這3個因素的關系表示出來?！　』旌鲜骄幋a在時間上主要采用時間片劃分，上課時間分為周一到周五，一天有10節(jié)課，上課方式為一個課次兩個相鄰小節(jié)。所以以一個課次為一個時間片，一天可劃分為5個時間片。這樣一周就可劃分為25個時間

6、片?？梢詷嬙煲粋€三維矩陣來表示排課系統，其中X坐標表示時間片，Y坐標表示教師、班級和課程，Z坐標表示教室，通過三維矩陣將影響排課系統的5個因素聯系起來?！　?.遺傳算法適應度函數　　適應度函數用于評價某個染色體的適應度，隨著排課的進行，課表空間在不斷變化，個體的適應度也隨著課表空間的改變而改變，本文采用的方法是調整隨機生成的初始群體，但是在遺傳算法運行過程中，交叉和變異都可能產生沖突，為了減少沖突，可以引入負適應度值來降低沖突個體被選入的概率，同時記錄沖突未消除的個體，并在下次迭代中繼續(xù)消除。對有時間段沖突的兩個個體，可以用個體的沖突時間段

7、與該個體的空閑時間段互換來消除沖突，這樣就消除了遺傳算法運行過程中存在的沖突，增加了個體的適應度?！　?.遺傳算法運行　　選擇操作　　首先采用計算機模擬方法計算個體的選擇概率，這種方法的基本思想就是用事件發(fā)生的頻率來決定事件的概率。接著采用輪盤選擇法進行下一代個體的選擇。其基本思想就是將整個群體根據個體的適應度不同分布在輪盤上，適應度大的個體占的比例多。在選擇算法過程中隨機轉動輪盤，指針所指區(qū)域的個體被選中并生存。這種選擇方法對適應度大的個體選中的機會較大，實現了個體的優(yōu)勝劣汰?！　鹘y遺傳算法的缺陷是初始種群分布不均勻，為了改進這個缺陷，

8、本文采用分區(qū)域的初始種群選擇，將整個解空間分成m個區(qū)域，初始化種群時，分別在每個1/m小區(qū)域中隨機選擇1/m個體，最后將m個小種群合并為初始種群，這樣產生的種群就覆蓋了整個解空間