排課系統(tǒng)算法分析

郭高星

摘要 排課問題歷史由來已久，存在于每所學(xué)校中，是教學(xué)工作正常有序開展的基本保證。針對(duì)現(xiàn)在的排課算法進(jìn)行分析，找出最優(yōu)算法是很難的，只能是不同的學(xué)校根據(jù)自身的特點(diǎn)找出一個(gè)可行性高的算法來設(shè)計(jì)排課系統(tǒng)。

關(guān)鍵詞 計(jì)算機(jī) 排課 算法

為了保證教學(xué)順利有序地進(jìn)行，嚴(yán)格執(zhí)行教學(xué)計(jì)劃是教學(xué)管理的中心環(huán)節(jié)，為了達(dá)到對(duì)學(xué)生的培養(yǎng)目的、提高教學(xué)質(zhì)量，合理安排的課表起著解決性的作用。隨著計(jì)算機(jī)的廣泛應(yīng)用，深入到每一所學(xué)校中，每個(gè)學(xué)校都在深入發(fā)展信息化管理，在此基礎(chǔ)上，排課問題也從原來的手工排課逐漸被計(jì)算機(jī)智能排課所取代。

下面是幾種比較著名的算法介紹：

1.Genetic Algorithm簡(jiǎn)稱GA（遺傳算法）

遺傳算法是由美國(guó)Michigan大學(xué)的J.Holland教授在1975年首先提出，是借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)化搜索方法。這種算法的主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。

遺傳算法是從代表問題可能潛在的解集的一個(gè)種群開始的，而一個(gè)種群則由經(jīng)過基因編碼的一定數(shù)目的個(gè)體組成。每個(gè)個(gè)體實(shí)際上是染色體帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡(jiǎn)化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度大小選擇個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼，可以作為問題近似最優(yōu)解。

遺傳算法包括選擇、交叉和變異三種操作。經(jīng)過幾十年的發(fā)展，遺傳算法得到了改進(jìn)和優(yōu)化，在解決排課問題中發(fā)揮了巨大的作用。

2.Backtracking（回溯算法）

回溯算法也叫試探法，它是一種系統(tǒng)地搜索問題的解的方法?；厮菟惴ǖ幕舅枷胧牵簭囊粭l路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試。

回溯算法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。而回溯法在用來求問題的任一解時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯法，它適用于解一些組合數(shù)較大的問題。

3. Simulate Anneal Arithmetic ，簡(jiǎn)稱SAA（模擬退火算法）

模擬退火算法是1983年Kirkpatrick等人提出的，它來源于固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部粒子隨溫升變?yōu)闊o序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T時(shí)趨于平衡的概率為e-ΔE/（kT），其中E為溫度T時(shí)的內(nèi)能，ΔE為其改變量，k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題，將內(nèi)能E模擬為目標(biāo)函數(shù)值f，溫度T演化成控制參數(shù)t，即得到解組合優(yōu)化問題的模擬退火算法：由初始解i和控制參數(shù)初值t開始，對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代，并逐步衰減t值，算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解，這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。退火過程由冷卻進(jìn)度表（Cooling Schedule）控制，包括控制參數(shù)的初值t及其衰減因子Δt、每個(gè)t值時(shí)的迭代次數(shù)L和停止條件S。

模擬退火法多被用來解決實(shí)際應(yīng)用中的優(yōu)化問題，所以用其來解決排課問題，也取得了一定的成功。

除了以上一些算法之外，國(guó)內(nèi)外還有很多學(xué)者，從課元，資源匹配，分組優(yōu)化策略等不同的角度對(duì)排課問題做出了研究?；谡n元相關(guān)運(yùn)算的高校排課算法，從課元的角度來分析了排課問題；基于課元與回溯算法的實(shí)驗(yàn)室智能排課與預(yù)約，將課元問題和回溯算法結(jié)合起來設(shè)計(jì)算法。智能排課系統(tǒng)及多約束條件下的資源分配模型，提出了資源分配的排課模型。排課表問題中的分組優(yōu)化決策算法將排課問題按照分組優(yōu)化的策略來研究。基于資源匹配的一種大學(xué)排課方法，是一種基于資源匹配的方式來進(jìn)行大學(xué)的排課。

終上所述，迄今為止，還沒有一個(gè)真正意義上好的算法來解決自動(dòng)排課這一問題，雖然已經(jīng)有了各種排課系統(tǒng)來完成排課這一任務(wù)，但是算法的好壞還是有待實(shí)際使用中來檢驗(yàn)的。