遺傳算法在高校排課系統(tǒng)中的應(yīng)用

王園園

(淮北職業(yè)技術(shù)學(xué)院 教務(wù)處，安徽 淮北235000)

摘要：對于排課的問題研究應(yīng)該歸于NP-完全問題的研究，它是綜合化的問題，具有一定的目標(biāo)性和約束性。對于排課的算法，和列表尋優(yōu)、模擬退火等算法相比，遺傳算法是最佳的。遺傳算法通過整合當(dāng)下教學(xué)資源，以交叉、變異以及選擇等方式進(jìn)行遺傳和變異，為解決高校排課系統(tǒng)中存在的問題，深入研究了遺傳算法在高校排課系統(tǒng)中的應(yīng)用。

關(guān)鍵詞：排課系統(tǒng)；遺傳算法；自動(dòng)排課系統(tǒng)；人工智能

收稿日期：2015-05-25

作者簡介：王園園(1982-)，女，安徽淮北人，淮北職業(yè)技術(shù)學(xué)院講師，碩士，研究方向?yàn)榫W(wǎng)絡(luò)技術(shù)。

中圖分類號：TP301.5;TP311.521文獻(xiàn)標(biāo)識碼：A

受眾多因素影響，高校排課很久以來受到人們的關(guān)注，但是實(shí)際排課過程中使用軟件的情況卻十分少見，原因之一就是很難選擇適當(dāng)?shù)乃惴ā?975年S.Even就排課問題展開了研究，他認(rèn)為排課問題一定要通過“窮舉法”的方式得出答案。但是這種方法也難以實(shí)現(xiàn)，因?yàn)楦F舉法本身所耗費(fèi)的成本和時(shí)間都較多，難以通過計(jì)算機(jī)來解決問題。例如，一個(gè)教師要參與一周S時(shí)段的課程安排，而他要一周大概約有M節(jié)課，如果這個(gè)學(xué)校有N個(gè)教師需要進(jìn)行排課，那么就有SN*M種可能性，顯而易見，算法耗費(fèi)時(shí)間較多。所以，為了解決該問題，筆者對列表尋優(yōu)、模擬退火等算法進(jìn)行了分析，同時(shí)提出了遺傳算法(Genetic Algorithm, 簡稱GA)。[1]41-44

遺傳算法可以認(rèn)為是一種解決排課困難的最優(yōu)方法，是由美國芝加哥大學(xué)的知名教授Holland提出。1962年Holland教授把遺傳算法結(jié)合生物遺傳、變異等理論知識，總結(jié)出了遺傳算法，同時(shí)將其轉(zhuǎn)移到圖像管理、函數(shù)優(yōu)化以及生產(chǎn)處理等廣泛的領(lǐng)域。

一、關(guān)于遺傳算法排課系統(tǒng)的發(fā)展概況

由于當(dāng)下許多高校生源擴(kuò)招，而學(xué)生數(shù)量的增多帶來的問題之一就是學(xué)校教師排課困難。排課發(fā)生矛盾非常常見，經(jīng)常有一些教師被迫“分身”上課，而有的課程安排不僅教室安排有問題，教師的安排上也發(fā)生沖突。因此上課混亂現(xiàn)象時(shí)有發(fā)生。只有解決排課問題才能更好的促進(jìn)教學(xué)效率的提高，最大程度地發(fā)揮教學(xué)的作用。

對于NP完全問題的認(rèn)證，自1970年開始就多次被提及。然而，課表的編排隨著課表信息的增加而不斷變化，其中潛在的問題也不斷誘發(fā)了不同的解集。本文對于高校教學(xué)管理系統(tǒng)的排課方法進(jìn)行了分析和研究。

二、以生物學(xué)和計(jì)算機(jī)為基礎(chǔ)的遺傳算法

從生物學(xué)角度出發(fā)，遺傳算法可以理解為是一種建立在生物進(jìn)化上的算法，其搜索假設(shè)的方法已經(jīng)逐漸從簡單到復(fù)雜過渡，以變異和重組來生成最終的假設(shè)。[2]93-94進(jìn)化是生物成功地適應(yīng)自然的方法，而以此為基礎(chǔ)研究出的算法以假設(shè)的生成測試柱狀展開搜索，有些假設(shè)則會以變體的形式在之后被涉及和考慮到。

三、遺傳算法

遺傳算法的演示過程和基因演化的過程差不多，大體如下：

1.以隨機(jī)的方式構(gòu)成數(shù)量相當(dāng)?shù)某跏挤N群；

2.評測和估算個(gè)體的適應(yīng)度，符合優(yōu)化標(biāo)準(zhǔn)的可以輸出其最優(yōu)解，完成計(jì)算過程，不符合者繼續(xù)下一步；

3.以適應(yīng)度為根據(jù)對再生個(gè)體進(jìn)行重新選取 ；

4.根據(jù)相應(yīng)的交叉方法和概率重新生成個(gè)體；

5.根據(jù)相應(yīng)的變異方法和概率重新生成個(gè)體；[3]

6.以變異和交叉的方式構(gòu)成新的種群，然后返回第2步，如圖1所示：

圖1　遺傳算法示意圖

以下是遺傳算法的偽代碼。

ALOGRITHM GA(i)

Begin

t=0;

Initialize P(t);

P(t)={X1(t), X2(t),…, Xn(t)}

Evaluate P(t);

f(P(T))={f(X1(t), f(X2(t), …, f(Xn(t)) };

while (not terminate condition) do

Pc(t)=crossover{P(t)};

Pm(t)=mutation{ Pc(t)};

Evaluate [Pm(t)];

P(t+1)=select{ Pm(t)UQ};

t=t+1;

if t mod t=0 then Qi=Xbest;

od

print Xbest,f(Xbest);

end

通常情況下遺傳算法是經(jīng)過下列操作完成的：

(1)初始化[Initialize]

必須進(jìn)行初始化操作,以便給遺傳操作提供一個(gè)初始種群。

在算法設(shè)計(jì)時(shí)，因?yàn)檫M(jìn)行遺傳操作時(shí)僅僅針對老師，在初始化的過程中，時(shí)間和教室如何安排要被重復(fù)考慮到，其中包含了在教室內(nèi)安排最合理的人數(shù)(即防止能夠容納200人的教室被30人所占用的情況發(fā)生)及安排合理上課時(shí)間。

(2)選擇[Select]

生物界中自然選擇能夠剔除劣品保留優(yōu)品，選擇算法亦是如此。它能夠?qū)⑴f種群內(nèi)適應(yīng)能力強(qiáng)的染色體挑選出來，準(zhǔn)備進(jìn)一步的配對，使得在交叉與變異運(yùn)算之后能夠得到新的種群。染色體適應(yīng)能力越強(qiáng)，越容易被選擇，選擇操作包含了錦標(biāo)賽選擇法(tournament selection)、輪盤賭選擇法(roulette wheel selection)和局部選擇法(local selection)等幾種方法。[4]31-33本文運(yùn)用了截?cái)噙x擇法(truncation selection)，它屬于局部選擇法。

(3)交叉[Crossover]

經(jīng)過選擇得出結(jié)果之后，父個(gè)體由選出的兩條染色體組成，然后隨機(jī)選取一個(gè)值(用r表示)，同事先設(shè)置的交叉率值(用t表示)對比，當(dāng)r

(4)變異[Mutate]

任意將染色體內(nèi)的上課時(shí)間進(jìn)行更改，任意選擇時(shí)間內(nèi)的一點(diǎn)進(jìn)行改動(dòng)，但是不能超出設(shè)定的范圍，這一過程稱為變異。變異運(yùn)算類似于自然界中生物的遺傳，因?yàn)榄h(huán)境或其他無意的原因而導(dǎo)致的基因突變，雖然變異之后，染色體的適應(yīng)能力會發(fā)生改變，但是它保證了這一物種擁有多種類型的遺傳基因，保證了搜索范圍的最大化，提高了最優(yōu)解獲取的可能性。

設(shè)置變異概率pm，在變異過程中隨機(jī)數(shù)r會首先產(chǎn)生，如果r>pm，那么不能進(jìn)行變異操作，反之則執(zhí)行變異操作。這一過程與交叉相同。

四、沖突問題的處理

沖突問題在排課過程中是無法避免的問題，無論排課的方法是什么，最常見的突出問題為同一時(shí)間同一老師被安排了兩門課程。[5]37-38本文利用了沖突檢測函數(shù)fConflict()來防止沖突發(fā)生，如果確定了一名老師需要上的課，沖突檢測函數(shù)就會自動(dòng)檢查該老師是否存在排課沖突，同時(shí)根據(jù)結(jié)果進(jìn)行更正。

排課是高校教學(xué)管理工作中較為復(fù)雜的工作，遺傳算法可以很好地解決高校排課系統(tǒng)中出現(xiàn)的問題，采用適應(yīng)度函數(shù)以及染色體編碼方案可以得到我們想要的結(jié)果，當(dāng)進(jìn)化代數(shù)不斷上升時(shí)，適應(yīng)度函數(shù)的值也不斷增加，而染色體編碼的方案，將被運(yùn)用于更為復(fù)雜的排課中。

參考文獻(xiàn)：

[1]業(yè)寧,梁作鵬,董逸生. 一種基于遺傳算法的TTP問題求解算法[J].東南大學(xué)學(xué)報(bào)：自然科學(xué)版,2013(1).

[2]唐勇,唐雪飛,王玲.基于遺傳算法的排課系統(tǒng)[J]. 計(jì)算機(jī)應(yīng)用,2012(1).

[3]張燕,宋錦斌.基于遺傳算法的排課系統(tǒng)[J].計(jì)算機(jī)知識與技術(shù),2011(11).

[4]王小平,曹立明.遺傳算法：理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2012.

[5]孫建平,梅曉勇.關(guān)聯(lián)規(guī)則在高校智能排課系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2012(5).

責(zé)任編輯：凈草