蟻群遺傳算法在高校智能排課系統(tǒng)中的應用

摘 要:大學課程表問題(UTP)是阻礙各個學校的教學資源多目標組合優(yōu)化問題。它的解決不僅有助于對運籌學中多目標優(yōu)化類問題的研究，而且對解決我國現(xiàn)階段教育中教學資源相對稀少、而學生又相對較多的現(xiàn)狀尤其具有現(xiàn)實意義。采用蟻群算法和遺傳算法混合建立高校智能排課系統(tǒng)，可以有效地減少搜索空間，使種群在遺傳過程按規(guī)則分區(qū)，在區(qū)間中噴灑信息素，染色適應度與種群區(qū)間交互，形成正反饋系統(tǒng)，驅(qū)動整個算法得到排課較優(yōu)解。

關(guān)鍵詞:智能排課系統(tǒng); 排課;遺傳算法;蟻群算法

中圖分類號:TN911.2; TP311.51 文獻標識碼:A

文章編號:1004-373X(2010)14-0121-03

Application of Ant-colony Genetic Algorithm in Smart Course Schedule Systems of Colleges

LI Yu-ji1， LU Cai-wu2， LIU Guan3

(1.Department of Information and Control Engineering， Xi’an University of Architecture and Technology， Xi’an 710055， China;

2. Department of Management， Xi’an University of Architecture and Technology， Xi’an 710055， China;

3. Graduate School， Xi’an University of Architecture and Technology， Xi’an 710055， China)

Abstract: Almost all the universities have been plagued with their timetable problems- teaching resources multi-objective combinatorial optimization problems for a long time. The solution of the problems will not only help the universities to study the multi-objective optimization in operations research， but also have the practical significance for solving the lack of teaching resource at the present stage and dealing with the current situation of students over the school. The smart course schedule system with the hybrid application of the ant colony algorithm and genetic algorithm can effectively reduce the search volume， so that the rule-based partition of the populations， the pheromone spray in the range of section， dyeing fitness and population interact are executed in the genetic process to form a positive feedback system， and then drive the whole algorithm to obtain the better schedule result.

Keywords: smart course schedule system; course schedule; genetic algorithm; ant-colony algorithm

當前我國高校的排課軟件系統(tǒng)很少，涉及到自動排課算法的系統(tǒng)更少，這些系統(tǒng)只能在排課過程中輔助工作人員進行排課，并沒有一套完善有效的自動排課策略(算法)，它決定了這些系統(tǒng)要么沒有真正的排課功能，要么排完課后，會出現(xiàn)有的課程無法安排，仍然需要工作人員進行大量的調(diào)整工作。而且大部分僅局限于輔助人工排課，并沒有任何“智能”的成分。另一方面，僅有的幾套自動排課系統(tǒng)卻由于產(chǎn)生了太多的“甩課”(因無法安排時間或者教室而不能排入課表的課程)，系統(tǒng)的實際使用非常困難，往往由于“甩課”太多，使后期人工調(diào)整的工作量具大。

在算法選擇過程中，如果僅采用簡單的循環(huán)遍歷各個元素以避免沖突的方法，排課效率低下;簡單的隨機散列方法，又難以有效控制找到合理方案。并且二者通常情況下得到課表的適應度都非常低。可能產(chǎn)生:一位老師或一個班級一天內(nèi)連續(xù)上課，之后一天又沒有課;同一門課程一天內(nèi)持續(xù)上，以后幾天又沒有這門課程;采用遺傳算法，理論上能夠得到較為合理地排課方案，也存在因為過早收斂得不到解決方案或者得不到最優(yōu)方案的情況。為了解決這些問題，將蟻群算法與遺傳算法相結(jié)合使用，可以有效地減少搜索空間，并能夠得到比較滿意的結(jié)果。

1 高校排課問題的描述

Carter和Laporte提出:高校排課問題是一個多元分配問題，它研究的就是如何把學生和老師分配給課程，課程單元或者班級，如何把事件(上課事件)分配給教室和時間[1] 。從上述定義來看，高校排課問題研究的就是如何把一系列的課程分配給有限的教室和一周內(nèi)有限的上課時間單元，以及如何把學生和老師分配給課程。

1.1 排課問題所涉及的元素

課程的編排不僅涉及參與課程的主體學生和教師，時間和教室也是在課程編排過程中的重要因素。所以排課問題所設(shè)計的元素主要有以下5種(排課問題概念模型見圖1):

班級集:R={r1，r2，r3，…，rn};教師集:T={t1，t2，…，tn};教室集:S={s1，s2，…，sn};課程集:C={c1，c2，…，cn};時間集:M={m1，m2，…，mn}

它們組成一個授課任務(wù)集合D={r，t，s，c，m}，r∈R，t∈T ，s∈S，c∈C，m∈M。

圖1 排課問題概念模型

1.2 排課過程中所要遵循的約束條件

一個可用的課表，應當完全遵循以下的基本約束:

(1) 班級約束:一個班級在一個時間內(nèi)最多只能有一門課程;

(2) 教師約束:一位教師在一個時間內(nèi)最多只能有一門課程;

(3) 教室約束:一個教室在一個時間內(nèi)最多只能有一門課程。

另外除了以上的基本約束條件外，一個完美的課程表還應該考慮以下的“人性化”約束條件:

(1) 班級的每周上課時間分布均勻;

(2) 教師的每周授課時間分布均勻;

(3) 同一班級相鄰時間段的上課地點不能相距太遠;

(4) 同一教師相鄰時間段的上課地點不能相距太遠。

2 應用蟻群遺傳算法解決排課問題

2.1 遺傳算法

遺傳算法(genetic algorithm，GA)是近幾年發(fā)展起來的一種嶄新的全局優(yōu)化算法。1962年霍蘭德(Holland)教授首次提出了GA算法的思想，它借用了仿真生物遺傳學和自然選擇機理，通過自然選擇、遺傳、變異等作用機制，提高各個個體的適應性[2] 。從某種程度上說遺傳算法是對生物進化過程進行的數(shù)學方式仿真。

這一點體現(xiàn)了自然界中“物競天擇、適者生存”進化過程[3] 。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進行評價，把問題的解表示成染色體，并基于適應值來選擇染色體，使適應性好的染色體有更多的繁殖機會。并且在執(zhí)行遺傳算法之前，給出一群染色體，也即是假設(shè)解。然后把這些假設(shè)解置于問題的“環(huán)境”中，也即一個適應度函數(shù)中來評價。并按適者生存的原則，從中選擇出較適應環(huán)境的染色體進行復制，淘汰低適應度的個體，再通過交叉，變異過程產(chǎn)生更適應環(huán)境的新一代染色體群。對這個新種群進行下一輪進化，直到最適合環(huán)境的值。

遺傳算法的運行過程是典型的迭代過程，其必須完成的工作內(nèi)容和基本參數(shù)步驟如圖2所示。

圖2 遺傳算法流程圖

(1) 選擇編碼策略，把參數(shù)集合和數(shù)域轉(zhuǎn)換為位串結(jié)構(gòu)空間;

(2) 定義適應值函數(shù);

(3) 確定遺傳策略，包含選擇群體大小，選擇、交叉、變異方法，以及確定交叉概率pe變異概率pm等遺傳參數(shù);

(4) 隨機初始化生成群體;

(5) 計算群體中個體位串解碼后的適應值;

(6) 按照遺傳策略，運用選擇、交叉和變異算子作用于群體，形成下一代群體。

2.2 蟻群算法

蟻群算法是模擬真實蟻群覓食過程尋求最短路經(jīng)的原理，由意大利學者M Dorigo等人首先提出的[4] 。最初的蟻群算法稱為螞蟻系統(tǒng)(ant system)，對于解決旅行商問題(TSP)及二次分配問題取得了較好的效果。經(jīng)過改進后稱為蟻群算法。

自然界中的螞蟻是以外激素(pheromone)為媒進行信息傳遞的，從而螞蟻個體能相互協(xié)作，完復雜的任務(wù)。蟻群的行為表現(xiàn)出一種信息正反饋現(xiàn)象:某一路徑上經(jīng)過的螞蟻越多，則后到者選擇該路徑的概率就越大[5] 。

2.3 蟻群遺傳算法

遺傳算法、蟻群算法作為2大仿生優(yōu)化算法，有其各自的優(yōu)點和不足。

遺傳算法具有大范圍快速全局搜索能力，但對系統(tǒng)中的反饋信息利用不夠，當求解到一定范圍時往往做大量無用的冗余迭代，求精確解效率低。蟻群算法原理是一種正反饋機制，但初期信息素匱乏，求解速度慢。

將遺傳算法與蟻群算法的融合[6] ，采用遺傳算法生成信息素分布，利用蟻群算法求精確解，優(yōu)勢互補，期望獲得優(yōu)化性能和時間性能的雙贏。將遺傳算法與蟻群算法的混合來解決排課問題，不僅采用遺傳算法生成初始信息素分布，在蟻群算法尋優(yōu)中，采用交叉和變異的策略，改善解的質(zhì)量。

解決排課問題的蟻群遺傳算法如下:

(1) 初始化群體，利用遺傳算法隨機產(chǎn)生排課問題的一個解;矩陣 A 表示一個染色體，每個染色體就是一個排課方案。

A =a11 a12 a13 … a1n

a21 a22 a23 … a2n

a31 a32 a33 … a3n

    

am1 am2 am3 … amn

(2) 計算排課問題隨機解上每個個體的適應度值。

(3) 引入蟻群算法的思想，將解矩陣等分成若干空間，在各個空間“噴灑”信息素[7] 。建立適應度與信息素的相應關(guān)系，使得適應度強的染色體，在所屬區(qū)間內(nèi)留下較強的信息素;信息素強的區(qū)間內(nèi)，染色體所選取的概率較大[8] 。

(4) 采用適應度排序方法，選擇將進入下一代的個體。

(5) 分別按照概率Pc對下代個體進行交叉操作，按照概率Pm對下代個體進行變異操作。

(6) 判斷新的染色體是否滿足滿足排課問題約束條件，是則結(jié)束迭代，否則進入步驟(2)。

(7) 解得排課問題的較優(yōu)解。

2.4 效果評估

分別在任務(wù)數(shù)為100，500，1000時利用仿真技術(shù)對循環(huán)遍歷算法、遺傳算法、蟻群遺傳算法所應用的時間和適應度進行模擬實驗。其中設(shè)定條件:

(1) 循環(huán)遍歷算法以得到可行解為結(jié)束條件;

(2) 遺傳算法和蟻群遺傳算法需要完成150次循環(huán)迭代;

(3) 教室為無差別教室。

得到運行時間結(jié)果如表1所示。

表1 3種排課算法運行時間比較

任務(wù)數(shù) 算法

循環(huán)遍歷算法遺傳算法蟻群遺傳算法

1001.232.539.5

500110.2162.9188.4

1 0001 179.3633.0667.3

得到適應度結(jié)果比較如表2所示。

表2 3種排課算法適應度比較

任務(wù)數(shù) 算法

循環(huán)遍歷算法遺傳算法蟻群遺傳算法

10052186231

50064287362

1 00058298374

3 結(jié) 語

在求解過程中的選擇交叉步驟中，普通的遺傳算法直接從上一代中選取2個染色體進行交叉，這樣可能因為局部收斂而得不到較優(yōu)解。在此引入了蟻群算法的思想，將信息素的濃度關(guān)聯(lián)到個體適應度，在選取下一代個體操作中，能夠更全面地選取適應度高的個體進行交叉變異操作，達到全局選取，更快地選取最優(yōu)個體，改善了解得質(zhì)量。另外在考慮教室之間的容量大小，電教室與普通教室之間的差別上，還需要做更加深入的研究。

參考文獻

[1]CARTER M W， LAPORTE G. Recent developments in practical course timetabling[ M] //BURKE E K， CARTER W. The Practice and Theory of Automated Timetabling. Berlin: Springer-Verlag， 1997: 3-19.

[2][日]玄光南.遺傳算法與工程設(shè)計[M].程潤偉，江定偉，譯.北京:科學出版社，2000.

[3]段海濱.蟻群算法原理及其應用[M].北京:科學出版社，2005.

[4]王凌.智能優(yōu)化算法及其應用[ M] .北京:清華大學出版社，2001.

[5]徐寧，李春光，張健.幾種現(xiàn)代優(yōu)化算法的比較研究[ J] .系統(tǒng)工程與電子技術(shù)，2002(12):100-103.

[6]劉秋紅，寒楓，張任.基于分層的自適應遺傳算法在UTP中的應用研究[ J] .貴州大學學報:自然科學版，2007，2(24):154-157.

[7]余樣宣，崔國華，鄒海明.計算機算法基礎(chǔ)[M].2版.武漢:華中科技大學出版社，2000.

[8]丁建立，陳增強，袁著扯.遺傳算法與螞蟻算法的融合[ J] .計算機研究與發(fā)展，2003，40(9):1351-1356.

[9]楊為民.使用遺傳算法編排課程表的研究與應用[ D] .合肥:安徽大學，2003.

[10]WANG Ling， ZHANG Liang， ZHENG Da-zhong. An effective hybrid genetic algorithm for flow shop scheduling with limited buffers[J]. Computers and Operations Research， 2006， 33: 2960-2971.