基于遺傳算法和禁忌搜索算法的排課系統(tǒng)研究

《基于遺傳算法和禁忌搜索算法的排課系統(tǒng)研究》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、基于遺傳算法和禁忌搜索算法的排課系統(tǒng)研究基于遺傳算法和禁忌搜索算法的排課系統(tǒng)研究引言　　排課是高校教學(xué)管理中十分重要而又復(fù)雜的管理工作之一，由于排課問(wèn)題涉及的因素有時(shí)間、教師、教室、課程、班級(jí)等，因此排課問(wèn)題是一個(gè)有約束條件、多目標(biāo)、模糊性極強(qiáng)的組合優(yōu)化問(wèn)題[1]。由于各學(xué)校資源差異較大，約束條件復(fù)雜，排課系統(tǒng)難以具有普遍適用性。一般教務(wù)排課仍以手工為主，計(jì)算機(jī)為輔，效率低下。研究靈活、高效、自動(dòng)化程度高的排課系統(tǒng)需求迫切，具有現(xiàn)實(shí)意義。　　國(guó)外很早就有人本文由.L.收集整理研究課表的編排問(wèn)題，一般利

2、用啟發(fā)式函數(shù)，并且大多數(shù)啟發(fā)式方法都是模擬手工排課的過(guò)程實(shí)現(xiàn)的。國(guó)內(nèi)對(duì)排課問(wèn)題的研究較晚，并且大部分學(xué)者研究的排課系統(tǒng)都依賴(lài)于各個(gè)學(xué)校的教學(xué)體制，不具有普遍適用性[2]。從實(shí)際使用情況看，國(guó)內(nèi)研究的排課系統(tǒng)軟件在性能上也達(dá)不到使用要求?！　∵z傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來(lái)的高度并行、自適應(yīng)的隨機(jī)搜索算法；而禁忌搜索算法是對(duì)局部領(lǐng)域的一種擴(kuò)展，是一種全局逐步尋優(yōu)的搜索算法。通過(guò)對(duì)比分析，遺傳算法和禁忌搜索算法在解決復(fù)雜優(yōu)化問(wèn)題中有明顯的優(yōu)勢(shì)，因而本文采用遺傳算法和禁忌搜索算法來(lái)實(shí)現(xiàn)排課

3、系統(tǒng)?！　?排課系統(tǒng)分析　　排課問(wèn)題的主要任務(wù)是將班級(jí)、教師、課程安排在一周內(nèi)某一不發(fā)生沖突的時(shí)間和教室中，保證課表在時(shí)間分配上符合一切共性和個(gè)性要求，使安排在各個(gè)目標(biāo)上盡量達(dá)到最優(yōu)?！　「鶕?jù)是否必須滿(mǎn)足，可以將約束條件分為硬約束和軟約束。硬約束是指教師、　　班級(jí)、教室在時(shí)空概念上發(fā)生了沖突，它是在排課過(guò)程中必須滿(mǎn)足的約束條件，否則將會(huì)使排課結(jié)果毫無(wú)意義。軟約束是指排課過(guò)程中需盡量滿(mǎn)足的約束條件，它能夠使課表更加合理。排課的目標(biāo)是要滿(mǎn)足所有的硬約束條件，同時(shí)盡可能多地滿(mǎn)足軟約束條件，實(shí)現(xiàn)一個(gè)使用方便、

4、效率高的排課系統(tǒng)。　　2基于遺傳算法與禁忌搜索算法的排課系統(tǒng)　　在整個(gè)排課過(guò)程中，首先需要確定教學(xué)計(jì)劃，然后根據(jù)教學(xué)計(jì)劃生成教學(xué)任務(wù)，教學(xué)任務(wù)確定了課程、教師、班級(jí)3者之間的關(guān)系。在排課問(wèn)題中，由于涉及到教師、教室、課程、班級(jí)、時(shí)間這5個(gè)因素，可以將課程、教師、班級(jí)這3個(gè)因素綁定為一個(gè)整體，作為一個(gè)元組，并對(duì)這個(gè)元組隨機(jī)分配時(shí)間與教室，生成一個(gè)可行的課表?！　”疚膽?yīng)用遺傳算法對(duì)排課問(wèn)題進(jìn)行編碼，然后再進(jìn)行選擇、交叉、變異等操作，計(jì)算適應(yīng)度函數(shù)。在遺傳算法的運(yùn)算過(guò)程中使用禁忌搜索算法來(lái)代替變異算子，從而

5、得到更優(yōu)的個(gè)體解，最終生成有效的課表?！　?.1遺傳算法編碼　　遺傳算法的編碼方法有很多種，針對(duì)排課系統(tǒng)，本文采用混合式編碼方式，將混合式編碼作為排課系統(tǒng)遺傳算法的基因。該基因由教師編號(hào)、課程編號(hào)、班級(jí)編號(hào)組成，每個(gè)教師都有一個(gè)唯一的教師編號(hào)，用八位數(shù)字表示。課程編號(hào)用一位數(shù)字表示，表示該教師教的第幾門(mén)課程。班級(jí)編號(hào)也用一位數(shù)字表示，表示該教師教的第幾個(gè)班級(jí)。這種編碼方式解決了特定時(shí)段教師課程的安排問(wèn)題和普通時(shí)段課程的分配問(wèn)題。系統(tǒng)只要按照算法流程對(duì)編碼進(jìn)行處理，對(duì)結(jié)果進(jìn)行不斷的篩選，就可以得到完善的

6、課程表，通過(guò)混合式編碼將教師、課程、班級(jí)這3個(gè)因素的關(guān)系表示出來(lái)?！　』旌鲜骄幋a在時(shí)間上主要采用時(shí)間片劃分，上課時(shí)間分為周一到周五，一天有10節(jié)課（上午4節(jié)，下午4節(jié)，晚上2節(jié)），上課方式為一個(gè)課次兩個(gè)相鄰小節(jié)。所以以一個(gè)課次為一個(gè)時(shí)間片，一天可劃分為5個(gè)時(shí)間片。這樣一周就可劃分為25個(gè)時(shí)間片?？梢詷?gòu)造一個(gè)三維矩陣來(lái)表示排課系統(tǒng)，其中X坐標(biāo)表示時(shí)間片，Y坐標(biāo)表示教師、班級(jí)和課程，Z坐標(biāo)表示教室，通過(guò)三維矩陣將影響排課系統(tǒng)的5個(gè)因素聯(lián)系起來(lái)。　　2.2遺傳算法適應(yīng)度函數(shù)　　適應(yīng)度函數(shù)用于評(píng)價(jià)某個(gè)染色體的

7、適應(yīng)度，隨著排課的進(jìn)行，課表空間在不斷變化，個(gè)體的適應(yīng)度也隨著課表空間的改變而改變，本文采用的方法是調(diào)整隨機(jī)生成的初始群體，但是在遺傳算法運(yùn)行過(guò)程中，交叉和變異都可能產(chǎn)生沖突，為了減少?zèng)_突，可以引入負(fù)適應(yīng)度值來(lái)降低沖突個(gè)體被選入的概率，同時(shí)記錄沖突未消除的個(gè)體，并在下次迭代中繼續(xù)消除。對(duì)有時(shí)間段沖突的兩個(gè)個(gè)體，可以用個(gè)體的沖突時(shí)間段與該個(gè)體的空閑時(shí)間段互換來(lái)消除沖突，這樣就消除了遺傳算法運(yùn)行過(guò)程中存在的沖突，增加了個(gè)體的適應(yīng)度?！　?.3遺傳算法運(yùn)行　　2.3.1選擇操作　　首先采用計(jì)算機(jī)模擬方法計(jì)算

8、個(gè)體的選擇概率，這種方法的基本思想就是用事件發(fā)生的頻率來(lái)決定事件的概率。接著采用輪盤(pán)選擇法進(jìn)行下一代個(gè)體的選擇。其基本思想就是將整個(gè)群體根據(jù)個(gè)體的適應(yīng)度不同分布在輪盤(pán)上，適應(yīng)度大的個(gè)體占的比例多。在選擇算法過(guò)程中隨機(jī)轉(zhuǎn)動(dòng)輪盤(pán)，指針?biāo)竻^(qū)域的個(gè)體被選中并生存。這種選擇方法對(duì)適應(yīng)度大的個(gè)體選中的機(jī)會(huì)較大，實(shí)現(xiàn)了個(gè)體的優(yōu)勝劣汰。　　傳統(tǒng)遺傳算法的缺陷是初始種群分布不均勻，為了改進(jìn)這個(gè)缺陷，本文采用分區(qū)域的初始種群選擇，將整個(gè)解空間分成m個(gè)區(qū)域，初始化種群時(shí)，分