遺傳算法在排課系統中的應用

四川大學錦城學院 計算機與軟件學院 宋亞靜 徐 艷

隨著教育的不斷發展，因其復雜和多樣性，排課越來越成為很多學校的難題，它是一個典型的多組合優化問題，問題的解就是求出時間，教室，班級，教師，課程之間的對應關系，正常來排的話會出現多組不同的解，每組解中有時還會出現例如課程沖突，時間沖突等各種各樣的問題，本文將針對這些問題利用遺傳算法進行優化，得出最佳排課方案。

1 約束條件

1.1 硬約束條件

此系統的約束條件分為硬約束和軟約束兩種，其中硬約束具體是指由于資源的局限性而必須滿足的條件，不滿足這些條件該課表就會發生沖突。本文主要考慮時間、教師、班級、課程、教室五個元素，對這5個元素求笛卡兒積即D×T×C×L×R得出所有的排列組合，一種結果稱為一個單元；對時間，教室求笛卡兒積得出的結果稱為時間-教室對，記為D×R={d1×r1，d1×r2，...，dm1×rm5}，教師，班級，課程不變，只需要找出最佳的時間-教室對，即可滿足問題最優解。如下是對元素的數學描述：

時間集合為D={d1，d2，...，dn1，dm1}，其中1 ≤n1≤m1；

教師集合為T={t1，t2，...，tn2，tm2}，{x1，x2...xm2}為所對應老師教的課程數，其中1≤n2≤m2；

班級集合為C={c1，c2，...，cn3，cm3}，{y1，y2...ym3}為所對應班級的學生人數，其中1≤n3≤m3；

課程集合為L={l1，l2，...，ln4，lm4}，其中1≤n4≤m4；

教室集合為R={r1，r2，...，rn5，rm5}，{z1，z2...zm5}為每個教室可容納的人數，其中1≤n5≤m5。

同一時間，教師只可能教一門課程，不可能同時教兩門。

將一師一課設為A，A≤1，A只能取0或1，當A=1時，意為教師tn2在dn1這個時間在rn5這個教室上ln4這門課程；當A=0時，結果不成立。

同一時間，班級只可能學一門課程，不可能同時學兩門。

將一班一課設為B，B≤1，B只能取0或1，當B=1時，意為班級cn3在dn1這個時間由tn2這個教師在上ln4這門課程；當B=0時，結果不成立。

1.1.2 生態地理資料 以《云南農業地理》《云南省種植業區劃》和《云南省農業氣候資料集》[7-9]等資料為基礎，分析整理云南128個縣(市、區)的生態氣候類型和稻作種植業區劃。

同一時間，教室只可能上一門課程，不可能同時上兩門。

將一室一課設為C，C≤1，C只能取0或1，當C=1時，意為教室rn5在dn1這個時間由教師tn2在上ln4這門課程；當B=0時，結果不成立。

每個教室能容納的人數必須大于每個班級的學生人數，即zm5≥ym3，否則該教室不可為當時上課的班級所使用。

1.2 軟約束條件

軟約束指的就是對硬約束后的課表進行細化，使之更貼近現實，如：學生大多都不想每天的課集中在一起，所以排表時應該注意分散，同理教師每周的課程也應被均勻分配到周一到周五；有些課對上課環境有要求也應盡量滿足；應為班級分配與之學生人數相當的教室，避免資源浪費；晚上注意力下降，盡量少安排或不安排專業課等。軟約束分的情況較多，每個學校情況不同，應視具體情況而定。

2 遺傳算法

2.1 基本原理

自然界有一個很神奇的現象就是生物的進化大體上都朝著好的方向發展，眾所周知人類的基因組合是隨機無約束的，但隨機的結果卻總是朝一個方向進行，遺傳算法（Genetic Algorithms，GA）就是基于這樣的自然現象產生的，它是一種基于自然選擇，借助生物進化優勝劣汰的機制和基因重組、突變的遺傳機制的全局搜索算法，從一組隨機產生的初始值（種群）開始，種群中每個個體都是經編碼的有特征的染色體，初始值產生后根據優勝劣汰的法則不斷迭代進化，每一代都選擇適應度較高的個體遺傳到下一代，產生新種群，最后一代種群中最優的個體經過解碼操作（基因型向表現型的映射），可以近似作為該種群的最優解。

2.2 遺傳算法流程

首先隨機初始化一批可行解，計算每個個體的適應度，然后判斷當前迭代次數是都達到最大，若達到最大迭代數，輸出最優解，結束；若還沒有達到，就利用選擇，交叉，變異等操作產生新一代種群，迭代數加1，再去判斷當前迭代數是否達到最大，依此類推。

2.3 染色體編碼

對排課問題，所有可能的排課結果組成的空間稱為問題空間，每一條結果的基因型組成的空間稱為編碼空間，由問題空間向編碼空間的映射稱為編碼，反之稱為解碼，解碼一般用于末代種群的最優個體。傳統的編碼方式有浮點數編碼和二進制編碼。因二進制編碼會導致染色體串過長，所以本文利用十進制編碼方式，簡單易懂且不存在進制轉化問題。

2.4 適應度

通俗來講，適應度就是為使結果不沖突而把約束條件根據一定規則轉化成數字的形式，適應度函數是用來評估每一條產生的結果好壞的函數。函數值越大說明個體的適應能力越強，反之說明越弱。選擇適應力較強的個體遺傳到下一代，使其優秀基因能夠迭代下去。現為其制定評分體系來計算個體的適應度：若滿足一條硬約束+10，反之，-10；滿足一條軟約束+5；每個教室的資源利用率（班級總人數/教室總座位數*100%）若大于70%，+10，若資源利用率大于100%，則-10，該結果不成立；學生每天的課分散均勻（上下午都有）+5，教師每周的課分散均勻（不在同天或兩次課間差2天）+5，反之，-5。

設置初始化適應度F為20，最終的結果適應度為F(i)，硬約束和教室資源為f1，不滿足記為f2，軟約束條件即課是否分配均勻為f1’，不滿足記為f2’，公式即為：F(i)=F+f1+f2-f1’-f2’。當最終結果F(i)>20時，即為一個新的個體，大于20的值離20越遠，越接近最優值，反之，當F(i)＜20時，即為沖突，小于20的值離20越遠，被拋棄的概率就越大。

2.5 遺傳算法的操作

（1）初始化種群

本文采用隨機生成一批可行解的方式初始化種群，這種方式的好處是隨機可以使初始種群分布更均勻，但產生的種群中有可能會有些不滿足硬約束的結果，因此需對每一個結果篩選，不滿足條件的直接舍棄，再重新隨機生成，再篩選，直到種群中所有的結果都滿足條件。

（2）選擇

選擇操作用來確定哪些個體可以遺傳到下一代，遺傳算法使用選擇算子對種群中的個體進行選擇，適應度較高的被遺傳到下一代的概率較大，較低的被遺傳到下一代的概率較小，選擇的目的是為了避免基因缺失。本文采用輪盤賭法，也稱比例選擇方法進行選擇，其思想就是每個個體被選中到下一代的概率與它的適應度成正比。

（3）交叉和變異操作

交叉操作是生成新個體的主要方式，其思想就是將兩個個體的部分基因互換產生新基因個體，交叉算子分為很多種，本文采用的是單點交叉算子，如圖1所示。變異操作是指將染色體編碼中的某些基因用該基因的等位基因代替，形成一個新個體，變異操作是產生新基因的輔助方法，以較小的概率存在于遺傳算法中，保證了種群的多樣性，防止出現過早收斂。

圖1 單點交叉算子示例圖

（4）搜索終止條件

計算出一輪染色體的適應度后，利用輪盤賭法選出概率較高的個體，概率較低的個體可以通過交叉和變異重新產生新個體，再計算，直到遺傳達到最大迭代數或當連續多次前后兩代個體最佳適應度的值相差很小，終止執行。

總結：本文詳細介紹了遺傳算法在排課系統中的應用。排課問題是一個復雜的多目標優化問題，而遺傳算法在不斷的迭代之后會產生出近似最優解，收斂性較好，其次，它基于隨機概率規則，可以使搜索更為靈活，再者它的擴展性較好，可較容易的與其他方法混合使用以達到一個綜合優化的效果。在智能化的今天，越來越多求最優解的問題被大眾關注，遺傳算法也越來越被廣泛使用，它解決了數學理論很難解決的問題，是一個很不錯的求最優值的算法。