劉青鳳

LIU Qing-feng

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

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

Apply the genetic algorithm in teaching task distributing

劉青鳳

LIU Qing-feng

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

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

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

0 引言

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

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

1 遺傳算法的基本過程

遺傳算法是John.H.Holland根據(jù)生物進(jìn)化的模型提出的一種優(yōu)化算法，它是基于進(jìn)化過程中的信息遺傳機(jī)制和優(yōu)勝劣汰的自然選擇原則的搜索算法。它是從代表問題可能潛在解集的一個(gè)種群開始的，而一個(gè)種群由經(jīng)過基因編碼的一定數(shù)目的個(gè)體組成。每個(gè)個(gè)體實(shí)際上是染色體帶有特征的實(shí)體。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xià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)解。

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

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

2.1 時(shí)間

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

2.2 課程與教師

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

2.3 班級(jí)和教室

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

2.4 教師

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

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

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

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

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

3.1 總體設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

圖2 初始種群中的兩個(gè)個(gè)體

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

3.2.1 初始化種群

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

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

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

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

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

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

3.2.3 設(shè)計(jì)遺傳算子

1） 選擇操作（wheelselection.prg）

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

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

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

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

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

（3）計(jì)算每個(gè)樣本的選擇概率。p=（maxv-v）/sumv；

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

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

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

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

圖3 表示6個(gè)染色體的輪盤

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

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

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

3）變異操作(mutation1.prg)

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

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

4 結(jié)束語

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

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

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

采用遺傳算法解決教務(wù)方面的問題還是一個(gè)較新的研究領(lǐng)域，本文只是針對(duì)教學(xué)任務(wù)分配方面作一嘗試，具有一定的局限性，對(duì)于比較復(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].國(guó)防工業(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].北京:中國(guó)水利水電出版社,2003.

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

TH166

A

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

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

2010-01-27

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