用遺傳算法求解排課問題

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

一、概述

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

二、算法設計

（一）染色體設計

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

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

其中相關變量的具體解釋如下：

c是課程的集合中的一個元素，具有名稱、周理論學時和實驗學時等屬性；

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

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

l是指學生的專業和學期；

p是教師的工號；

r是一個結構體，包含教室的編號，類型和容量等；

s為了簡化問題，s取課程班的學生人數。

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

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

… … … … … … …

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

（二）約束條件

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

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

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

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

：同一個教室在同一個時間只能有一門課

：同一門課的兩個時間槽不能在同一天

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

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

=（ci=cj）（di=dj）

（三）適應度函數設計

對于基因上的每一個約束條件C，計算函數：

1如果約束被破壞

f（c）=

0約束沒有被破壞

總適應度的計算方法如下：

其中ai代表約束Ci的權重。可以看出為了較好的解決問題，應使適應度函數最小化。為了簡化問題對于硬約束我們使用一個常量α，對于軟約束使用一個常量β，這樣一來適應度函數為：

（四）選擇操作

選擇是指在群體中選擇生命力強的個體產生新群體的過程。這里采用最佳保留選擇的方法，這種方法的步驟是：

首先采用輪盤賭方法進行選擇操作：

Step1計算每一個個體的適應度f（Ci）

Step2計算整個種群的適應度的和

Step3計算每一個個體進入下一代的概率f（Ci）/

其次是將當前群體中適應度最高的個體完整復制到下一代中。這種方法的優點是能夠保證算法結束時得到的結果是歷代出現過的最高適應度的個體。

（五）交叉操作交叉操作的步驟是：選擇兩個染色體中的行號相同的兩行；隨機交換它們的d值、t值或者r值。交叉在算法中起著關鍵作用，是產生新個體的主要方法，能夠使群體分布擴充。

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

三、結束語

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

【參考文獻】

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

［2］張文修等.遺傳算法的數學基礎.西安交通大學出版社，第2版，2003.

項目名稱：“基于遺傳算法的醫學院校排課系統”，校級項目。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文