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

四川大學(xué)錦城學(xué)院 計(jì)算機(jī)與軟件學(xué)院 宋亞靜 徐 艷

隨著教育的不斷發(fā)展，因其復(fù)雜和多樣性，排課越來(lái)越成為很多學(xué)校的難題，它是一個(gè)典型的多組合優(yōu)化問(wèn)題，問(wèn)題的解就是求出時(shí)間，教室，班級(jí)，教師，課程之間的對(duì)應(yīng)關(guān)系，正常來(lái)排的話會(huì)出現(xiàn)多組不同的解，每組解中有時(shí)還會(huì)出現(xiàn)例如課程沖突，時(shí)間沖突等各種各樣的問(wèn)題，本文將針對(duì)這些問(wèn)題利用遺傳算法進(jìn)行優(yōu)化，得出最佳排課方案。

1 約束條件

1.1 硬約束條件

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

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

教師集合為T(mén)={t1，t2，...，tn2，tm2}，{x1，x2...xm2}為所對(duì)應(yīng)老師教的課程數(shù)，其中1≤n2≤m2；

班級(jí)集合為C={c1，c2，...，cn3，cm3}，{y1，y2...ym3}為所對(duì)應(yīng)班級(jí)的學(xué)生人數(shù)，其中1≤n3≤m3；

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

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

同一時(shí)間，教師只可能教一門(mén)課程，不可能同時(shí)教兩門(mén)。

將一師一課設(shè)為A，A≤1，A只能取0或1，當(dāng)A=1時(shí)，意為教師tn2在dn1這個(gè)時(shí)間在rn5這個(gè)教室上ln4這門(mén)課程；當(dāng)A=0時(shí)，結(jié)果不成立。

同一時(shí)間，班級(jí)只可能學(xué)一門(mén)課程，不可能同時(shí)學(xué)兩門(mén)。

將一班一課設(shè)為B，B≤1，B只能取0或1，當(dāng)B=1時(shí)，意為班級(jí)cn3在dn1這個(gè)時(shí)間由tn2這個(gè)教師在上ln4這門(mén)課程；當(dāng)B=0時(shí)，結(jié)果不成立。

1.1.2 生態(tài)地理資料 以《云南農(nóng)業(yè)地理》《云南省種植業(yè)區(qū)劃》和《云南省農(nóng)業(yè)氣候資料集》[7-9]等資料為基礎(chǔ)，分析整理云南128個(gè)縣(市、區(qū))的生態(tài)氣候類(lèi)型和稻作種植業(yè)區(qū)劃。

同一時(shí)間，教室只可能上一門(mén)課程，不可能同時(shí)上兩門(mén)。

將一室一課設(shè)為C，C≤1，C只能取0或1，當(dāng)C=1時(shí)，意為教室rn5在dn1這個(gè)時(shí)間由教師tn2在上ln4這門(mén)課程；當(dāng)B=0時(shí)，結(jié)果不成立。

每個(gè)教室能容納的人數(shù)必須大于每個(gè)班級(jí)的學(xué)生人數(shù)，即zm5≥ym3，否則該教室不可為當(dāng)時(shí)上課的班級(jí)所使用。

1.2 軟約束條件

軟約束指的就是對(duì)硬約束后的課表進(jìn)行細(xì)化，使之更貼近現(xiàn)實(shí)，如：學(xué)生大多都不想每天的課集中在一起，所以排表時(shí)應(yīng)該注意分散，同理教師每周的課程也應(yīng)被均勻分配到周一到周五；有些課對(duì)上課環(huán)境有要求也應(yīng)盡量滿足；應(yīng)為班級(jí)分配與之學(xué)生人數(shù)相當(dāng)?shù)慕淌遥苊赓Y源浪費(fèi)；晚上注意力下降，盡量少安排或不安排專(zhuān)業(yè)課等。軟約束分的情況較多，每個(gè)學(xué)校情況不同，應(yīng)視具體情況而定。

2 遺傳算法

2.1 基本原理

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

2.2 遺傳算法流程

首先隨機(jī)初始化一批可行解，計(jì)算每個(gè)個(gè)體的適應(yīng)度，然后判斷當(dāng)前迭代次數(shù)是都達(dá)到最大，若達(dá)到最大迭代數(shù)，輸出最優(yōu)解，結(jié)束；若還沒(méi)有達(dá)到，就利用選擇，交叉，變異等操作產(chǎn)生新一代種群，迭代數(shù)加1，再去判斷當(dāng)前迭代數(shù)是否達(dá)到最大，依此類(lèi)推。

2.3 染色體編碼

對(duì)排課問(wèn)題，所有可能的排課結(jié)果組成的空間稱(chēng)為問(wèn)題空間，每一條結(jié)果的基因型組成的空間稱(chēng)為編碼空間，由問(wèn)題空間向編碼空間的映射稱(chēng)為編碼，反之稱(chēng)為解碼，解碼一般用于末代種群的最優(yōu)個(gè)體。傳統(tǒng)的編碼方式有浮點(diǎn)數(shù)編碼和二進(jìn)制編碼。因二進(jìn)制編碼會(huì)導(dǎo)致染色體串過(guò)長(zhǎng)，所以本文利用十進(jìn)制編碼方式，簡(jiǎn)單易懂且不存在進(jìn)制轉(zhuǎn)化問(wèn)題。

2.4 適應(yīng)度

通俗來(lái)講，適應(yīng)度就是為使結(jié)果不沖突而把約束條件根據(jù)一定規(guī)則轉(zhuǎn)化成數(shù)字的形式，適應(yīng)度函數(shù)是用來(lái)評(píng)估每一條產(chǎn)生的結(jié)果好壞的函數(shù)。函數(shù)值越大說(shuō)明個(gè)體的適應(yīng)能力越強(qiáng)，反之說(shuō)明越弱。選擇適應(yīng)力較強(qiáng)的個(gè)體遺傳到下一代，使其優(yōu)秀基因能夠迭代下去?，F(xiàn)為其制定評(píng)分體系來(lái)計(jì)算個(gè)體的適應(yīng)度：若滿足一條硬約束+10，反之，-10；滿足一條軟約束+5；每個(gè)教室的資源利用率（班級(jí)總?cè)藬?shù)/教室總座位數(shù)*100%）若大于70%，+10，若資源利用率大于100%，則-10，該結(jié)果不成立；學(xué)生每天的課分散均勻（上下午都有）+5，教師每周的課分散均勻（不在同天或兩次課間差2天）+5，反之，-5。

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

2.5 遺傳算法的操作

（1）初始化種群

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

（2）選擇

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

（3）交叉和變異操作

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

圖1 單點(diǎn)交叉算子示例圖

（4）搜索終止條件

計(jì)算出一輪染色體的適應(yīng)度后，利用輪盤(pán)賭法選出概率較高的個(gè)體，概率較低的個(gè)體可以通過(guò)交叉和變異重新產(chǎn)生新個(gè)體，再計(jì)算，直到遺傳達(dá)到最大迭代數(shù)或當(dāng)連續(xù)多次前后兩代個(gè)體最佳適應(yīng)度的值相差很小，終止執(zhí)行。

總結(jié)：本文詳細(xì)介紹了遺傳算法在排課系統(tǒng)中的應(yīng)用。排課問(wèn)題是一個(gè)復(fù)雜的多目標(biāo)優(yōu)化問(wèn)題，而遺傳算法在不斷的迭代之后會(huì)產(chǎn)生出近似最優(yōu)解，收斂性較好，其次，它基于隨機(jī)概率規(guī)則，可以使搜索更為靈活，再者它的擴(kuò)展性較好，可較容易的與其他方法混合使用以達(dá)到一個(gè)綜合優(yōu)化的效果。在智能化的今天，越來(lái)越多求最優(yōu)解的問(wèn)題被大眾關(guān)注，遺傳算法也越來(lái)越被廣泛使用，它解決了數(shù)學(xué)理論很難解決的問(wèn)題，是一個(gè)很不錯(cuò)的求最優(yōu)值的算法。