劉青鳳

LIU Qing-feng

（安陽工學院，安陽 455000）

遺傳算法在教學任務分配中的應用

Apply the genetic algorithm in teaching task distributing

劉青鳳

LIU Qing-feng

（安陽工學院，安陽 455000）

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

遺傳算法；教學任務表；基因；染色體；種群；遺傳算子

0 引言

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

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

1 遺傳算法的基本過程

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

2 教學任務分配表三要素

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

2.1 時間

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

2.2 課程與教師

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

2.3 班級和教室

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

2.4 教師

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

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

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

圖1 基本元素關系

3 教學任務分配表遺傳算法設計

3.1 總體設計

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

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

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

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

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

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

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

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

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

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

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

3.2 遺傳算法設計步驟

3.2.1 初始化種群

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

3.2.2 構造適應度函數(shù)(countks.prg)

評估函數(shù)有兩個指標，第一，為每位教師安排課程的總課時數(shù)t應當平均，差別不要太大；第二，盡量安排少的課頭數(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ù)對應的期望值如表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 設計遺傳算子

1） 選擇操作（wheelselection.prg）

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

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

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

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

（2）計算種群中所有個體適應值之和。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）轉動輪盤m次，從中選出m個染色體。

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

隨機產生一個0～1之間的數(shù)r來模擬轉動一次輪盤后，輪盤停止轉動后指針所指向的位置。若r≤q1，這說明指針指向第1個扇形，這時選擇第一個個體teachtask1，一般若q（k-1）＜r≤q（k），這說明指針指向第k個扇形，這時選擇第k個個體。

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

圖4 教學任務適應度值表

2）雜交運算(cross1.prg)

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

3）變異操作(mutation1.prg)

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

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

4 結束語

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

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

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

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

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

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

[3] 周明,孫樹棟.遺傳算法原理及應用[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 -），女，安陽人，講師，碩士，研究方向為計算機軟件與理論。