遺傳算法在教學(xué)任務(wù)分配中的應(yīng)用

劉青鳳

LIU Qing-feng

（安陽工學(xué)院，安陽 455000）

遺傳算法在教學(xué)任務(wù)分配中的應(yīng)用

Apply the genetic algorithm in teaching task distributing

劉青鳳

LIU Qing-feng

（安陽工學(xué)院，安陽 455000）

本文通過對教學(xué)任務(wù)表中三要素的分析，利用遺傳算法實現(xiàn)了教學(xué)任務(wù)表的分配工作，從而使人們從繁雜的手工操作中解脫出來，提高了工作效率。

遺傳算法；教學(xué)任務(wù)表；基因；染色體；種群；遺傳算子

0 引言

在學(xué)校的日常教學(xué)管理工作中，教學(xué)任務(wù)表的設(shè)計是最重要也是最基本的環(huán)節(jié)，而課表則是實施教學(xué)計劃的具體表現(xiàn)方式。教學(xué)任務(wù)的分配和課表的制作是進(jìn)行教學(xué)管理的開始，它們在執(zhí)行教學(xué)計劃這一教學(xué)管理中心環(huán)節(jié)中起著極其重要的作用，通過它們對教學(xué)活動和教學(xué)秩序?qū)嵤┛茖W(xué)的組織和管理，因此，課程編排問題在一定程度和深度上影響著學(xué)生學(xué)習(xí)培養(yǎng)與教學(xué)質(zhì)量的提高。

目前，由計算機(jī)進(jìn)行排課的軟件已經(jīng)很多，而教學(xué)任務(wù)表的設(shè)計還停留在手工階段。對于那些只擁有幾百名學(xué)生，數(shù)十名教師的小規(guī)模學(xué)校來說，手工進(jìn)行計劃表的設(shè)計還能應(yīng)付，但隨著我國教育體制改革的深入，學(xué)生人數(shù)不斷增加，專業(yè)設(shè)置、課程設(shè)置不斷向深度和廣度發(fā)展，教師隊伍也在不斷壯大，如果還要拿出教師名單、班級課程去進(jìn)行逐個手工填寫，工作量大、效率低下的缺點(diǎn)就顯露無遺。本文將使用遺傳算法來解決教學(xué)任務(wù)表的合理分配。

1 遺傳算法的基本過程

遺傳算法是John.H.Holland根據(jù)生物進(jìn)化的模型提出的一種優(yōu)化算法，它是基于進(jìn)化過程中的信息遺傳機(jī)制和優(yōu)勝劣汰的自然選擇原則的搜索算法。它是從代表問題可能潛在解集的一個種群開始的，而一個種群由經(jīng)過基因編碼的一定數(shù)目的個體組成。每個個體實際上是染色體帶有特征的實體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)是某種基因組合決定的。初始種群產(chǎn)生以后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解。在每一代，根據(jù)問題域中個體的適應(yīng)度大小挑選個體，并借助代表自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。這個過程導(dǎo)致種群象自然進(jìn)化一樣，后代種群比前代更加適應(yīng)于環(huán)境，末代種群中最優(yōu)個體經(jīng)過解碼，可以作為問題的近似最優(yōu)解。

2 教學(xué)任務(wù)分配表三要素

排課涉及的相關(guān)問題主要包括：時間、班級、課程、教室和教師5個要素，而教學(xué)任務(wù)分配表所涉及到的有班級、課程和教師3個要素，對這些問題的透徹分析和適當(dāng)?shù)奶幚硎情_始算法設(shè)計的基礎(chǔ)。

2.1 時間

在排課問題中涉及關(guān)于時間的概念有學(xué)年、學(xué)期、周、天、課時。根據(jù)大專院校的教學(xué)特點(diǎn)，工作日為周一至周五共5天，一天安排6節(jié)課，上課方式為一次兩節(jié)課，即每天分三個時間段。關(guān)于時間片的設(shè)計在課程表編排時很重要，在教學(xué)任務(wù)計劃表的編排過程中未涉及，這里不再贅述。

2.2 課程與教師

在教學(xué)計劃中，課程是學(xué)生上課的具體內(nèi)容。課程有自己的編號、課程名、課程類型等，每門課程都有指定的教師，這樣可以把課程和教師作為同一變量來考慮。

2.3 班級和教室

一般情況下，學(xué)校安排各班級的理論課程均在各自的固定教室，在這種情況下，把班級和教室當(dāng)作一個變量等同考慮，

2.4 教師

每個教師都擁有自己的編號、姓名、可任課程、最大課時數(shù)等。在分配教學(xué)任務(wù)時，在不超過最大工作量的前提下，盡量平均分配每位教師的周課時數(shù)。

教學(xué)任務(wù)分配實際上是計算領(lǐng)域中一個有約束的組合優(yōu)化問題，它將班級、課程與任課教師組成一維，使排課最終形成班級、教室和時間的三維，其關(guān)系如圖2所示。

由圖示可以看出，教學(xué)任務(wù)分配表的設(shè)計就是將班級、課程和教師三個要素合成一維的過程，它是課程表編排的前提和基礎(chǔ)，它的變動將影響到排課的全局。

圖1 基本元素關(guān)系

3 教學(xué)任務(wù)分配表遺傳算法設(shè)計

3.1 總體設(shè)計

本階段實現(xiàn)班級、課程和教師的三維合一。

3.1.1 數(shù)據(jù)表設(shè)計

本過程所用表集合及其屬性如下：

教學(xué)任務(wù)表teachtask.dbf(任務(wù)編號，課程號，課程名，班級號，教師號，周次數(shù)，教室類型)，教學(xué)任務(wù)分配即要填寫本表中每一個任務(wù)要分配給的教師號，正是本文要完成的工作。

教師表teacher.dbf（教師號，姓名，性別，職稱，出生日期，可任課程號，已排課時數(shù)，最大課時數(shù)，期望值），本表是計算適應(yīng)度函數(shù)的重要依據(jù)。

課程表course.dbf（課程號，課程名，周次數(shù)）

班級表class.dbf（班級號，教室號，學(xué)生人數(shù)，專業(yè)，）

教室表classroom.dbf（教室號，座位數(shù)）

評價表eva.dbf(f,v,p ,q) 本表是對所選m個樣本進(jìn)行評價。其中f的值為樣本表名稱teachtask&i(i=1,2……m)；v為評估值（越小越好），p為樣本的選擇概率，用maxv表示v的最大值，sumv表示maxv-v之和，則p=(maxv-v)/sumv；q為累計概率。

選擇樣本表taskselection.dbf(任務(wù)名，q，r)本表存放進(jìn)行輪盤賭程序操作時，所選中的表。其中，任務(wù)名為teachtask&i(I=1，2……m)，q同評價表eva.dbf中的屬性，r為輪盤賭程序中的隨機(jī)參數(shù)，該值與q值比較，確定是否選擇對應(yīng)的任務(wù)表。

圖2 初始種群中的兩個個體

3.2 遺傳算法設(shè)計步驟

3.2.1 初始化種群

復(fù)制教學(xué)任務(wù)表teachtask.dbf到teachtask&i.dbf，作為一個“個體”，每張表中的一行，稱為一個“染色體”，在表的教師號字段列隨機(jī)填寫可任該課程的教師號，所填寫的教師號稱為“基因”。從第一個個體的第一個染色體開始填充基因，直到種群規(guī)模為M的M個個體全部填寫完成為止，這樣就形成了M個初始的教學(xué)任務(wù)表。本過程即選擇M=20張教學(xué)任務(wù)表teachtask1……teachtask20，每張表中，將各教學(xué)任務(wù)安排教師來擔(dān)任，即為每個班的各門課程安排一位教師。并限定教師的最大課時數(shù)和該教師可任課程，安排課程應(yīng)在此范圍內(nèi)。在此限定條件下，為每項任務(wù)隨機(jī)安排教師。此運(yùn)行結(jié)果，相應(yīng)產(chǎn)生M=20個教師教學(xué)統(tǒng)計表teacher1……teacher20，其中統(tǒng)計出每位教師的總課時數(shù)和所任課頭數(shù)。

3.2.2 構(gòu)造適應(yīng)度函數(shù)(countks.prg)

評估函數(shù)有兩個指標(biāo)，第一，為每位教師安排課程的總課時數(shù)t應(yīng)當(dāng)平均，差別不要太大；第二，盡量安排少的課頭數(shù)。計算教師課時數(shù)的平均值av，用各自總課時數(shù)t與平均數(shù)av的差。對每個個體teachtask&i，計算s(i)=∑(abs(t(j)-av))(j=1，2……k k為教師人數(shù)；i=1，2……m。 m為個體數(shù))。教師課頭數(shù)對應(yīng)的期望值如表1所示。

表1 教師課頭數(shù)期望值

計算總期望值b(i)= ∑a(j) (j=1,2……k i=1,2……m)

每個個體的評估函數(shù)值為：v(i)=sqrt(s(i)+b(i))值越小，價值越高。

3.2.3 設(shè)計遺傳算子

1） 選擇操作（wheelselection.prg）

本過程采用輪盤賭的方法選擇父本。

輪盤賭選擇模擬博彩游戲中的輪盤賭。一個輪盤被劃分為n個扇形，每個扇形表示群體中的一個個體，而每個扇形的面積與它所表示的個體的適應(yīng)值成正比，如圖4所示。為了選擇種群中的個體，想像有一個指針指向輪盤，轉(zhuǎn)動輪盤，當(dāng)輪盤停止后，指針?biāo)傅膫€體被選擇。因此一個個體的適應(yīng)值越大，表示該染色體的扇形面積越大，它被選擇的可能性也就越大。實現(xiàn)步驟如下：

由于評估函數(shù)v（i）的值越小，價值越高，而輪盤賭是概率越大越容易被選中，所以

（1）用最大適應(yīng)值maxv減去每個樣本的適應(yīng)值作為每個樣本的適應(yīng)值maxv（i）-v（i）；

（2）計算種群中所有個體適應(yīng)值之和。sumv=∑(maxv（i）-v（i）)，i=1,2,3,……m；

（3）計算每個樣本的選擇概率。p=（maxv-v）/sumv；

（4）計算每個染色體的累計概率。q（i）=∑p（i），i=1，2，3，……m；

（5）轉(zhuǎn)動輪盤m次，從中選出m個染色體。

實現(xiàn)過程如下：

隨機(jī)產(chǎn)生一個0～1之間的數(shù)r來模擬轉(zhuǎn)動一次輪盤后，輪盤停止轉(zhuǎn)動后指針?biāo)赶虻奈恢谩Ｈ魊≤q1，這說明指針指向第1個扇形，這時選擇第一個個體teachtask1，一般若q（k-1）＜r≤q（k），這說明指針指向第k個扇形，這時選擇第k個個體。

圖3 表示6個染色體的輪盤

圖4 教學(xué)任務(wù)適應(yīng)度值表

2）雜交運(yùn)算(cross1.prg)

采用傳統(tǒng)的遺傳算法單點(diǎn)雜交的方法，以Pm=0.25的概率選出個體，如果選取的是奇數(shù)個，則刪除最后一個。對偶數(shù)個個體按順序進(jìn)行兩兩雜交。雜交的方法是：隨機(jī)產(chǎn)生一個n（每個染色體teachtask&i中有n項任務(wù)）之間的整數(shù)K，兩個染色體，均取K～n條記錄，并將對應(yīng)記錄的教師號進(jìn)行對換（如果教師不同，且課程在該教師可任課程中包括，則進(jìn)行交換，否則不進(jìn)行操作）。

3）變異操作(mutation1.prg)

經(jīng)過雜交后的種群中的每一個個體（teachtask&i的每一個染色體（表中的一條記錄），產(chǎn)生一個隨機(jī)數(shù)random()，若random()<=pm，(pm為變異率，設(shè)為0.01)，那么該基因位進(jìn)行變異，否則不變異。本過程的變異是更換任課教師：首先記錄該染色體的課程號，在teacher.dbf中查找可任該課程的教師，并找到不同于當(dāng)前染色體的教師號，更換之。

4）重新計算適應(yīng)值進(jìn)行評估(countks.prg/fit.prg)，選擇最優(yōu)個體。

4 結(jié)束語

一般的文章中，都將教學(xué)任務(wù)分配階段的工作手工操作，排課系統(tǒng)直接從課表的編排入手，本文將排課表前期的教學(xué)任務(wù)分配使用遺傳算法進(jìn)行操作，這樣設(shè)計的作用有：

1）提高了工作效率。每位教師所任課程存入數(shù)據(jù)庫中，一般是固定不變的，不需每次都重新輸入，可個別修改。然后，由計算機(jī)根據(jù)數(shù)據(jù)庫中的數(shù)據(jù)分配任務(wù)，可以大大提高工作效率。

2）公平公正。很多教師不愿擔(dān)任較差的班級，或不愿擔(dān)任較難上的課程，手工分配任務(wù)時，要考慮這些不該照顧的對象，給教學(xué)任務(wù)分配工作造成不便。利用遺傳算法，由計算機(jī)隨機(jī)進(jìn)行分配任務(wù)，可以杜絕此類事情的發(fā)生。

采用遺傳算法解決教務(wù)方面的問題還是一個較新的研究領(lǐng)域，本文只是針對教學(xué)任務(wù)分配方面作一嘗試，具有一定的局限性，對于比較復(fù)雜的問題還有待于進(jìn)一步研究。

[1] Radcliffe N.J.The Alegbra Of Genetic Algorithms.Annals Of Math,&Al,1994,10:339-384.

[2] 陳根社,陳新海.遺傳算法的研究與進(jìn)展[J].信息與控制,1994,23(4):P215-222.

[3] 周明,孫樹棟.遺傳算法原理及應(yīng)用[M].國防工業(yè)出版社,2002.5.1.

[4] Goldberg D E.Genetic Algorithm in Search, Optimization,and machine Learning.Addison-Wesley,Reading,MA,1989.

[5] Vittorio Maniezzo,Genetic Evolution of the Topology and Weight Distribution of the Neural Networks,IEEE,Trans.on Neural Networks,Vol.5,NO.1,1994,PP39-53.

[6] Zbigniew Michalewicz, David B. Fogel.曹宏慶,李艷,董紅斌,吳志健譯.如何求解問題一現(xiàn)代啟發(fā)式方法[M].北京:中國水利水電出版社,2003.

[7] 尹朝慶.人工智能與專家系統(tǒng)[M].北京:中國水利水電出版社,2002,l.

TH166

A

1009-0134(2010)10(上)-0203-03

10.3969/j.issn.1009-0134.2010.10(上).63

2010-01-27

劉青鳳（1970 -），女，安陽人，講師，碩士，研究方向為計算機(jī)軟件與理論。