用遺傳算法求解排課問題

【摘要】遺傳算法是解決排課問題的新途徑；介紹了一種遺傳算法求解排課問題的染色體設(shè)計(jì)，適應(yīng)度函數(shù)設(shè)計(jì)，交叉和變異操作。

一、概述

排課是一個(gè)NP完全的時(shí)間表問題（TTP），傳統(tǒng)的算法面臨這種問題顯得捉襟見肘。由于適用于大規(guī)模、并行問題，并具有自組織、自適應(yīng)等智能特征，所以遺傳算法為機(jī)械化解決這個(gè)問題開辟了新途徑。時(shí)間表調(diào)度可以被看做確定性的約束滿足問題，因此解決排課問題可以通過給系統(tǒng)中所有變量賦值，滿足相應(yīng)的約束條件。本文的算法設(shè)計(jì)按照這個(gè)思路進(jìn)行。

二、算法設(shè)計(jì)

（一）染色體設(shè)計(jì)

染色體（chromosome）由課程班的集合表示。一個(gè)課程班由課程（c）、星期（d）、時(shí)間（t）、教師（p）、教室（r）、層次（l）和一個(gè)學(xué)生列表（s）組成。因此染色體可如下表示：

Chrom={（ci，di，ti，pi，ri，li，si）│i=1，…N}

其中相關(guān)變量的具體解釋如下：

c是課程的集合中的一個(gè)元素，具有名稱、周理論學(xué)時(shí)和實(shí)驗(yàn)學(xué)時(shí)等屬性；

d取值范圍為1-5，表示星期一到星期五；

t取值范圍為整數(shù)1-6，7-10中連續(xù)兩個(gè)或者三個(gè)間隔，例如1-3，7-8（t也可以是時(shí)間段，例如8：00-10：00）；

l是指學(xué)生的專業(yè)和學(xué)期；

p是教師的工號(hào)；

r是一個(gè)結(jié)構(gòu)體，包含教室的編號(hào)，類型和容量等；

s為了簡(jiǎn)化問題，s取課程班的學(xué)生人數(shù)。

于是染色體可以用一個(gè)N*7矩陣來表示（N是課程數(shù)）：

c1，d1，t1，p1，r1，l1，s1，

… … … … … … …

cN，dN，tN，pN，rN，lN，sN

（二）約束條件

排課需要考慮許多約束條件，諸如教師數(shù)量、學(xué)生數(shù)量、教室的數(shù)量和類型、課程的理論和實(shí)驗(yàn)學(xué)時(shí)等。這些約束條件可以分為如下兩種類型：

硬約束：是指不可破壞的約束，例如同一名教師不能在同一個(gè)時(shí)間上兩門以上課；

軟約束：這種約束即使破壞，排課方案仍可接受，例如同一名教師在同一天在兩個(gè)連續(xù)時(shí)間槽有課。

一個(gè)排課問題的約束可以用C來表示，其中C是斷言的集合{C1，C2，…，Cn}。通常這些斷言作為參數(shù)，并盡量被滿足來獲得問題的解決。如果某一斷言Ci未被滿足，則給其指派一個(gè)懲罰ai，懲罰的大小依賴于約束的類型和重要性。實(shí)驗(yàn)中使用的約束的例子如下：

：同一個(gè)教室在同一個(gè)時(shí)間只能有一門課

：同一門課的兩個(gè)時(shí)間槽不能在同一天

于是對(duì)于任意兩個(gè)染色體（ci，di，ti，pi，ri，li）和（cj，dj，tj，pj，rj，lj），它們違反以上約束的情形表示為：

=（di=dj）（ti=tj）（pi=pj）

=（ci=cj）（di=dj）

（三）適應(yīng)度函數(shù)設(shè)計(jì)

對(duì)于基因上的每一個(gè)約束條件C，計(jì)算函數(shù)：

1如果約束被破壞

f（c）=

0約束沒有被破壞

總適應(yīng)度的計(jì)算方法如下：

其中ai代表約束Ci的權(quán)重。可以看出為了較好的解決問題，應(yīng)使適應(yīng)度函數(shù)最小化。為了簡(jiǎn)化問題對(duì)于硬約束我們使用一個(gè)常量α，對(duì)于軟約束使用一個(gè)常量β，這樣一來適應(yīng)度函數(shù)為：

（四）選擇操作

選擇是指在群體中選擇生命力強(qiáng)的個(gè)體產(chǎn)生新群體的過程。這里采用最佳保留選擇的方法，這種方法的步驟是：

首先采用輪盤賭方法進(jìn)行選擇操作：

Step1計(jì)算每一個(gè)個(gè)體的適應(yīng)度f（Ci）

Step2計(jì)算整個(gè)種群的適應(yīng)度的和

Step3計(jì)算每一個(gè)個(gè)體進(jìn)入下一代的概率f（Ci）/

其次是將當(dāng)前群體中適應(yīng)度最高的個(gè)體完整復(fù)制到下一代中。這種方法的優(yōu)點(diǎn)是能夠保證算法結(jié)束時(shí)得到的結(jié)果是歷代出現(xiàn)過的最高適應(yīng)度的個(gè)體。

（五）交叉操作交叉操作的步驟是：選擇兩個(gè)染色體中的行號(hào)相同的兩行；隨機(jī)交換它們的d值、t值或者r值。交叉在算法中起著關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法，能夠使群體分布擴(kuò)充。

（六）變異操作變異操作的方法是：隨機(jī)選取染色體矩陣中的某些行，然后把它們的日期d或時(shí)間槽t，或者教室r的值進(jìn)行修改，要注意的是修改要遵守相關(guān)的約束。變異操作能夠改變個(gè)體的結(jié)構(gòu)，維持群體的多樣性，有利于防止出現(xiàn)早熟現(xiàn)象。

三、結(jié)束語(yǔ)

遺傳算法的應(yīng)用日益廣泛，但是研究表明因?yàn)閷?shí)際情形諸如約束條件的不同，解決各種時(shí)間表問題的方案也不相同，遺傳算法在實(shí)際應(yīng)用的時(shí)候需要根據(jù)實(shí)際情況作出必要的變形和改進(jìn)，設(shè)計(jì)適合實(shí)際情形的目標(biāo)函數(shù)、交叉和變異操作，使問題得到較好的解決。

【參考文獻(xiàn)】

［1］雷英杰等.MATLAB遺傳算法工具箱及應(yīng)用.西安電子科技大學(xué)出版社，第1版，2005.

［2］張文修等.遺傳算法的數(shù)學(xué)基礎(chǔ).西安交通大學(xué)出版社，第2版，2003.

項(xiàng)目名稱：“基于遺傳算法的醫(yī)學(xué)院校排課系統(tǒng)”，校級(jí)項(xiàng)目。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文