1/7基于遺傳算法和禁忌搜索算法的排課系統(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ó)外很早就有人本文由論文聯(lián)盟HTTP/收集整理研究課表的編排問(wèn)題，一般利用啟發(fā)式函數(shù)，并且大多數(shù)啟發(fā)式方法都是模擬手工排課的過(guò)程實(shí)現(xiàn)的。國(guó)內(nèi)對(duì)排課問(wèn)題的研究較晚，并且大部分學(xué)者研究的排課系統(tǒng)都依賴于各個(gè)學(xué)校的教學(xué)體制，不具有普遍適用性2。從實(shí)際使用情況看，國(guó)內(nèi)研究的排課系統(tǒng)軟件在性能上也達(dá)不到使用要求。遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來(lái)的高度并行、自適應(yīng)的隨機(jī)搜索算法；而禁忌搜索2/7算法是對(duì)局部領(lǐng)域的一種擴(kuò)展，是一種全局逐步尋優(yōu)的搜索算法。通過(guò)對(duì)比分析，遺傳算法和禁忌搜索算法在解決復(fù)雜優(yōu)化問(wèn)題中有明顯的優(yōu)勢(shì)，因而本文采用遺傳算法和禁忌搜索算法來(lái)實(shí)現(xiàn)排課系統(tǒng)。1排課系統(tǒng)分析排課問(wèn)題的主要任務(wù)是將班級(jí)、教師、課程安排在一周內(nèi)某一不發(fā)生沖突的時(shí)間和教室中，保證課表在時(shí)間分配上符合一切共性和個(gè)性要求，使安排在各個(gè)目標(biāo)上盡量達(dá)到最優(yōu)。根據(jù)是否必須滿足，可以將約束條件分為硬約束和軟約束。硬約束是指教師、班級(jí)、教室在時(shí)空概念上發(fā)生了沖突，它是在排課過(guò)程中必須滿足的約束條件，否則將會(huì)使排課結(jié)果毫無(wú)意義。軟約束是指排課過(guò)程中需盡量滿足的約束條件，它能夠使課表更加合理。排課的目標(biāo)是要滿足所有的硬約束條件，同時(shí)盡可能多地滿足軟約束條件，實(shí)現(xiàn)一個(gè)使用方便、效率高的排課系統(tǒng)?；谶z傳算法與禁忌搜索算法的排課系統(tǒng)在整個(gè)排課過(guò)程中，首先需要確定教學(xué)計(jì)劃，然后根據(jù)教學(xué)計(jì)劃生成教學(xué)任務(wù)，教學(xué)任務(wù)確定了課程、教師、班級(jí)3者之間的關(guān)系。在排課問(wèn)題中，由于涉及到教師、教室、課程、班級(jí)、時(shí)間這5個(gè)因素，可以將課程、教師、3/7班級(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)代替變異算子，從而得到更優(yōu)的個(gè)體解，最終生成有效的課表。遺傳算法編碼遺傳算法的編碼方法有很多種，針對(duì)排課系統(tǒng)，本文采用混合式編碼方式，將混合式編碼作為排課系統(tǒng)遺傳算法的基因。該基因由教師編號(hào)、課程編號(hào)、班級(jí)編號(hào)組成，每個(gè)教師都有一個(gè)唯一的教師編號(hào)，用八位數(shù)字表示。課程編號(hào)用一位數(shù)字表示，表示該教師教的第幾門課程。班級(jí)編號(hào)也用一位數(shù)字表示，表示該教師教的第幾個(gè)班級(jí)。這種編碼方式解決了特定時(shí)段教師課程的安排問(wèn)題和普通時(shí)段課程的分配問(wèn)題。系統(tǒng)只要按照算法流程對(duì)編碼進(jìn)行處理，對(duì)結(jié)果進(jìn)行不斷的篩選，就可以得到完善的課程表，通過(guò)混合式編碼將教師、課程、班級(jí)這3個(gè)因素的關(guān)系表示出來(lái)?；旌鲜骄幋a在時(shí)間上主要采用時(shí)間片劃分，上課時(shí)間分為周一到周五，一天有10節(jié)課，上課方式為一個(gè)課次兩個(gè)相鄰小節(jié)。所以以一個(gè)課次為一個(gè)時(shí)間片，一天可劃分為5個(gè)時(shí)間片。這樣一周就可劃分為25個(gè)時(shí)間片?？梢?/7構(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遺傳算法適應(yīng)度函數(shù)適應(yīng)度函數(shù)用于評(píng)價(jià)某個(gè)染色體的適應(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)度。2遺傳算法運(yùn)行選擇操作首先采用計(jì)算機(jī)模擬方法計(jì)算個(gè)體的選擇概率，這種方法的基本思想就是用事件發(fā)生的頻率來(lái)決定事件的概率。接著采用輪盤選擇法進(jìn)行下一代個(gè)體的選擇。其基本思想就是將整個(gè)群體根據(jù)個(gè)體的適應(yīng)度不同分布在輪盤上，適應(yīng)度大的個(gè)體占的比例多。在選擇算法過(guò)程中隨機(jī)轉(zhuǎn)動(dòng)輪盤，指針?biāo)竻^(qū)域的個(gè)體被選中并生存。這種選擇方法5/7對(duì)適應(yīng)度大的個(gè)體選中的機(jī)會(huì)較大，實(shí)現(xiàn)了個(gè)體的優(yōu)勝劣汰。傳統(tǒng)遺傳算法的缺陷是初始種群分布不均勻，為了改進(jìn)這個(gè)缺陷，本文采用分區(qū)域的初始種群選擇，將整個(gè)解空間分成M個(gè)區(qū)域，初始化種群時(shí)，分別在每個(gè)1/M小區(qū)域中隨機(jī)選擇1/M個(gè)體，最后將M個(gè)小種群合并為初始種群，這樣產(chǎn)生的種群就覆蓋了整個(gè)解空間，保證了初始種群的均勻分布。交叉操作本文采用的是兩點(diǎn)交叉，其基本思想是在兩個(gè)相互配對(duì)的編碼串中隨機(jī)選擇兩個(gè)交叉點(diǎn)，將這兩個(gè)交叉點(diǎn)之間的基因相互交換得到兩個(gè)子個(gè)體，兩個(gè)11位的父?jìng)€(gè)體，交叉點(diǎn)的位置為2、6，通過(guò)兩點(diǎn)交叉運(yùn)算得到兩個(gè)子個(gè)體。兩點(diǎn)交叉運(yùn)算如下所示父?jìng)€(gè)體111110011010子個(gè)體111101011010父?jìng)€(gè)體10101000101子個(gè)體10110000101通過(guò)這種方式解決了選課學(xué)生人數(shù)和教室座位人數(shù)之間的沖突，交叉操作產(chǎn)生的新個(gè)體遺傳到下一代。改進(jìn)的遺傳算法傳統(tǒng)的遺傳算法收斂速度慢、局部尋優(yōu)能力差、產(chǎn)生的最優(yōu)解精度不高，同時(shí)由于交叉算子使種群染色體之間存在局部相似性，這樣就很可能導(dǎo)致搜索停止。如果變6/7異率降低，還會(huì)導(dǎo)致“早熟”現(xiàn)象發(fā)生。遺傳算法在進(jìn)化過(guò)程中，每代總要維持一個(gè)較大的群體規(guī)模，從而容易使個(gè)體后代過(guò)多，造成算法“局部收斂”而不能得到全局最優(yōu)解。因此，必須對(duì)個(gè)體以變異概率進(jìn)行局部搜素，跳出局部收斂，獲得全局最優(yōu)解。禁忌搜索算法在搜索過(guò)程中可以接受劣解，具有較強(qiáng)的“爬山“能力，新解不是在當(dāng)前解領(lǐng)域中隨機(jī)產(chǎn)生的，而是從中選擇的最好解，即最好解產(chǎn)生的概率大于其它解。該算法通過(guò)引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來(lái)避免迂回搜索，并通過(guò)藐視準(zhǔn)則赦免一些被禁忌的優(yōu)良狀態(tài)，增加獲得全局最優(yōu)解的概率，因此禁忌搜索算法適合作局部搜索3。由于傳統(tǒng)的遺傳算法存在許多缺點(diǎn)，因此本文在變異階段用到了禁忌搜索算法，用TS代替變異算子，防止“早熟”現(xiàn)象發(fā)生，使個(gè)體呈現(xiàn)多樣性。改進(jìn)后的遺傳禁忌搜索算法為了使原算法優(yōu)點(diǎn)保留，弱點(diǎn)被克服或被削弱，提高算法的力度，本文先用GA進(jìn)行全局搜索，搜索出所有可能的排課情況，并將其分布在解空間的大部分區(qū)域，然后在每個(gè)個(gè)體課表中用TS進(jìn)行局部變異搜索，得到最優(yōu)排課情況4。下面給出遺傳禁忌搜索算法的算法流程，見(jiàn)圖1。7/7改進(jìn)后的遺傳禁忌搜索算法遺傳禁忌搜索算法終止條件為在種群中找到了能夠接受的最優(yōu)排課單元；最適應(yīng)種群的個(gè)體占群體比例達(dá)到了預(yù)定的比例；達(dá)到了預(yù)定進(jìn)化代數(shù)；達(dá)到了指定的最大時(shí)間。在遺傳算法的迭代中，只要滿足上述4個(gè)條件之一，算法就終止。TS運(yùn)用于GA的局部搜索中，避免了GA過(guò)度早熟的現(xiàn)象，但是如果一直調(diào)用TS會(huì)浪費(fèi)時(shí)間5，因此調(diào)用TS要根據(jù)GA的收斂情況來(lái)定，開(kāi)始時(shí)調(diào)用TS的次數(shù)很少，隨著迭代的進(jìn)行，調(diào)用TS的次數(shù)也越來(lái)越多6，因?yàn)楦鱾€(gè)排課單元越接近最優(yōu)排課單元，局部搜索的作用也越大，因此在GA中要合理地使用TS。結(jié)語(yǔ)本文介紹了國(guó)內(nèi)外排課系統(tǒng)問(wèn)題