基于遺傳算法的中職排課系統(tǒng)設計與實現(xiàn)

王濤

摘 要：文章從排課系統(tǒng)研究現(xiàn)狀出發(fā)，分析了影響排課問題的要素、條件與求解目標，采用基于遺傳算法解決排課問題的框架，并設計了基于遺傳算法的排課系統(tǒng)。

關鍵詞：遺傳算法；中等職業(yè)學校；排課系統(tǒng)

中圖分類號：G640 文獻標識碼：A 文章編號：1002-4107（2015）11-0066-02

一、排課系統(tǒng)研究背景

在學校日常教學管理中十分重要，而又相當復雜的工作就是排課，其本質(zhì)就是為學校的每一門課程及與其對應的教師安排時間和地點，從而使學校的日常教學工作能夠有秩序地進行。

編排課程表是混合諸多因素的規(guī)劃題目，要確保教師、學生、教室三者之間沒有沖突，而且要考慮教師的實際需求及資源的局限等條件。

排課問題已經(jīng)被證明是NP完全問題[1]，是諸多學者研究的熱點，研究者主要運用理論研究、啟發(fā)式搜索、專家系統(tǒng)求解等方法來解決這個問題。近年來最多的是使用遺傳算法來求解這個問題。

教學排課效率低滿意度低是學校教務人員最頭痛的問題，其最大的困難是硬件條件的局限。教務人員很難在同時兼顧硬件資源與軟件資源的情況下快速編排任課教師、學生都滿意的課表。

“窮舉法”將所有的出路擺出，然后找到最佳的解決方案，但造價高，耗時長。如某一周有n個時間段可安排課時，有m個教師需要排課，這些教師每個星期要上i堂課，如果使用窮舉法我們就可以得出一共有nm*i種組合結(jié)果，可見窮舉法太繁復，不適合實際應用。

遺傳算法是一種通過模擬自然進化過程搜索最優(yōu)解的方法[2]。本文試圖以遺傳算法來實現(xiàn)排課問題的最佳解。

本課題研究的目的就是實現(xiàn)基于遺傳算法的排課系統(tǒng)，滿足日常教學需求。

二、遺傳算法在排課系統(tǒng)中的應用

（一）排課問題描述

在排課問題中將各種因素有序地安排在一周的時間內(nèi)且不發(fā)生沖突是我們的首要任務，這些因素包括班級、教室、課程、教師、時間。據(jù)此，我們給出如下描述。

學校有J間教室，B個班，K門課程，L位教師，S個時間段。

1.教室表述為J（J1，J2，…，Jn）集合，不同教室容納的人數(shù)為（X1，X2…Xr）。

2.班級表述為B（B1，B2，…，Bn）集合，不同班級的人數(shù)為（K1，K2，…Kc）。

3.課程表述為K（K1，K2，…，Kn）集合，每門課對應Bi個班，1位教師，（1≤Bi

4.教師表述為L（L1，L2，…，Ln）集合，每位教師對應Km門課，Cn個班（1≤Km

5.時間表述為S（S1，S2，…，Sn）集合，一般情況下一周有五天上課，根據(jù)職業(yè)高中的實際情況每天為6節(jié)課，即上午4節(jié)，下午2節(jié)，則時間集合包含30個時間段。例如11代表周一第一節(jié)課，12代表周一的第二節(jié)課，21代表周二的第一節(jié)課，按此推導，這些課節(jié)構成一個時間集合P（11，12，13，…，56）。

（二）約束條件

1.一張正確的課表應至少滿足以下硬約束條件。

（1）某一個教師、班級、教室在同一個時間節(jié)點內(nèi)不能安排兩門課程。

（2）教室必須容下上課的學生數(shù)，即Kc≤Xr。

2.硬性約束是必須滿足的，否則教學無法正常進行

下去，但在實際教學當中為了使教學效果更好還應當有些軟約束。這些條件在特殊情況下也可以不滿足，這些軟約束條件可能是：

（1）把重要理論課程安排在上午進行，把動手課程安排在下午進行，這樣符合學生的注意力規(guī)律。

（2）在滿足學生上課時間要求的情況下盡可能滿足教師對課程時間的要求。

（3）一門課要在一周的幾個分散的時間段進行，就是說每周三課時的課不能安排在一天上完，也不能安排在相鄰的三天上完，要使學生有時間預習消化，教師有時間備課批改。

（4）教師每天的課不能太多，否則影響教學效果。

（5）同第（4）條，學生上課時間不能一天是滿課，一天又沒有課的情況。

這些軟性條件對于不同學校是不同的，筆者在這里列出的這些軟性約束條件主要是針對中等職業(yè)學校的實際教學需要，在筆者的排課系統(tǒng)中，只是給我們定義的約束條件給出一個解決方案，如果有其他的要求就需要另外考慮[3]。

三、遺傳算法分析

（一）遺傳算法的循環(huán)過程

遺傳算法的演算過程是模擬染色體交叉變異，生物進化淘汰的過程。

（1）隨機產(chǎn)生一定數(shù)目的初始種群。

（2）評價個體適應度情況，如果個體符合適應度條

件，則個體代表的解可以使用，輸出結(jié)果結(jié)束計算，否則轉(zhuǎn)向下一步。

（3）依據(jù)適應度選擇再生個體。

（4）按照一定的交叉概率和交叉方法生成新的個體。

（5）按照一定的變異概率和變異方法生成新的個體。

（6）由（4）和（5）產(chǎn)生新的種群，在判斷適應度。如圖1所示。

圖1 遺傳算法示意圖

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

BEGIN：

I = 0；

Initialize P（I）；

Fitness P（I）；

While（not Terminate-Condition）

{I + +：GA-Operation P（I）；Fitness P（I）；}END.

（二）染色體編碼

在排課系統(tǒng)的實現(xiàn)過程中首先要解決的是將實際的課表變成虛擬的編碼，就是如何將課表轉(zhuǎn)化為染色體，使它可以進行遺傳操作。在前人的方法中，常將染色體設計成浮點數(shù)或二進制編碼，在實踐中，將每個教師的課表設計成一個單獨的染色體，結(jié)構如下面表述。

教師ID班級ID課程ID教室上課時間安排。

在本設計中染色體用十進制數(shù)來編碼，例如：某一位教師編號為1234，要上“職業(yè)生涯規(guī)劃”這門課，這門課的編號為7025，周學時為3，班級為01201、01202，上課時間是隨機產(chǎn)生的，教室要選擇大于兩班總?cè)藬?shù)的，以此編碼生成的染色體為：“12340120101202702502204

213451”其中02204代表上課教室，213451代表上課時間是周二第一節(jié)、周三第四節(jié)、周五第一節(jié)。

使用上面的編碼方式，對染色體的后11位進行交叉操作，這樣教師課程受影響，教師課表內(nèi)含其他教師課程的情況都不會發(fā)生，也使得演化后的染色體編碼更加合理。不過產(chǎn)生排課課表的優(yōu)劣還需要適應度函數(shù)進行判斷。

工作中適應度值就是課程編排人員對課表的期望。因此，把這些期望轉(zhuǎn)化為具體數(shù)值就顯得很重要，它是實現(xiàn)智能化的關鍵。

按照排課系統(tǒng)的要求，個體適應度評價函數(shù)的設計是一種獎懲并存的機制[4]。詳細來說就是我們設計了獎勵機制，比如教師在某個時間段上課比較方便，如果恰好有這么一個解，那么我們就獎勵這個個體，該個體適應度值即加大了。相反懲罰（減去一個權值）的情況有，如果個體中有存在不滿足硬約束的條件，那么就對該個體進行懲罰。有些解是我們不需要的，為了能夠優(yōu)先進化更好的解，因此它的適應度值需要降低。比如說在同一時間某個教師被安排了兩門不一樣的課在一個個體中，這就違反了硬約束條件；綜合上述對排課多目標的分析，則采用以下適應度的函數(shù)：

fitness_value+reward_value-conflict_penalty_value=fitness

其中，reward_value表示獎勵值，偏好設置根據(jù)教師偏好時間設置來指定分別為很滿意（獎勵+20）、還可以（獎勵+10）、沒有意見（獎勵+0）、不滿意（獎勵-10）、非常不滿意（獎勵-20）；fitness_value表示適應度的基礎值，它是一個適應度函數(shù)的初始值，引入此值是為避免整體適應度值為負在基于獎懲模式情況下：Conflict_penalty_value代表沖突懲罰值，包含了任課教師與時間的沖突，教室和時間的沖突還有班級和時間的沖突，在相關類中該值的設定已經(jīng)被指定。在自動排好的課表中如其中的安排符合教師的喜好，并是教師事先設定好那么就直接對相應的結(jié)果進行獎勵相應的值，就是說結(jié)果適應度值的高低，取決于教師是否滿意。以此類推不符合教師期望的教師不滿意，它的適應度值自然就低。如果在程序中出現(xiàn)班級在同一時間上多門課的情況、教師同一時間上多門課的情況、教室同一時間多班級使用的情況、教室類型與課程需要不符合的情況，這些都需要設定相應的懲罰值，在適應度上減去相應的值。確保這樣的結(jié)果不會出現(xiàn)在生成的課表上。

排課系統(tǒng)的設計使用了前臺界面操作與后臺數(shù)據(jù)庫處理相結(jié)合的方式。使得日常的管理操作和數(shù)據(jù)庫中數(shù)據(jù)的存儲相區(qū)分開來，使得兩者不會發(fā)生錯誤的干擾，增加了各個用戶的獨立性。這樣的結(jié)構給軟件的開發(fā)和維護帶來了方便。

由于本系統(tǒng)尚在完善階段，存有瑕疵，如在安全性能方面，在線共享方面等。這也激勵筆者在今后的學習工作中要逐步地完善提升。排課系統(tǒng)為保證以優(yōu)質(zhì)的課表供師生使用，仍需嚴格的測試。

參考文獻：

[1]吳金榮.解課程表問題的分支定界算法[D].北京：中國

科學院數(shù)學與系統(tǒng)科學研究院，2002.

[2]胡順仁，鄧毅，王錚.基于高校排課系統(tǒng)中的圖論問題研

究[J].計算機工程與應用，2002，（4）.

[3]劉繼清，陳傳波.模擬退火算法在排課中的應用[J].武

漢船舶職業(yè)技術學院學報，2003，（6）.

[4]李增智，王云嵐，陳靖.課程表問題的一種混合型模擬退

火算法[J].西安交通大學學報，2003，（4）.