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

李文蕙，劉 嵩

武漢軟件工程職業(yè)學(xué)院，湖北武漢 430205

0 引言

人工編排課程表是教務(wù)科人員在進(jìn)行教學(xué)管理中最為頭疼的工作之一。它涉及到很多的硬軟件資源和內(nèi)外部因素，如：時(shí)間、地點(diǎn)、教師、學(xué)生以及課程等。尤其是隨著高職院校的不斷擴(kuò)招而硬軟件設(shè)備沒有及時(shí)更新和增加，造成了人多教室少、課程多時(shí)間少等狀況。這些問題使得學(xué)院系部的教學(xué)管理工作無法正常進(jìn)行。傳統(tǒng)的人工排課方式存在有以下幾個(gè)方面的問題：1）人工編排課程表工作量大；2）人工編排課程表依賴于人為因素；3）人工編排課程表可維護(hù)性差；4）人工編排課程表安全性差。

編排課程表是一項(xiàng)需要認(rèn)真計(jì)劃，合理安排，科學(xué)部署以及沒有沖突的工作。在編排課程表過程中，需要最大化的利用所有資源并充分的發(fā)揮學(xué)院所能提供的資源。這些資源包括人力、物力以及時(shí)間空間等。

1 排課算法核心屬性的確定

排課問題就是指如何避免在有限的教學(xué)資源里，授課人員、班級(jí)、教室、上課時(shí)間以及課程之間發(fā)生沖突。當(dāng)授課人員、班級(jí)、教室、上課時(shí)間以及課程分別能夠確定時(shí)，就可以進(jìn)行排課工作了。排課問題主要集合描述及核心屬性為：

1）授課人員集合E={e1,e2,e3,…,ek+1,…en}。授課人員的員工號(hào)為主鍵。

2）班級(jí)集合C={c1,c2,c3…,cm}。其中，每個(gè)班級(jí)所對(duì)應(yīng)的人數(shù)為 S={s1,s2,s3,… sn}。

班級(jí)的班級(jí)號(hào)為主鍵。

3）教室集合 R={r1,r2,r3…rk,…rm+1…,rn}。

4）上課時(shí)間集合T={t1,t2,t3…,tn}。其中，一周的上課時(shí)間為星期一至星期五的白天（本校晚上不排課且不考慮特殊節(jié)假日）并以2課時(shí)為1節(jié)課，一天分為4節(jié)課。

5）課程集合D={d1,d2,d3…,dn}。課程的課程號(hào)為主鍵。

2 排課模型的建立

一個(gè)排課算法排出了一周的課程安排，其實(shí)質(zhì)就是一個(gè)包含了授課人員、班級(jí)、教室、上課時(shí)間以及課程的五維向量（a1，a2，a3，a4，a5）。

設(shè)nk為授課班級(jí)ck的一周課程的總課時(shí)數(shù)，則

一張課表可以表示為n×5的矩陣，該矩陣即為問題求解中的目標(biāo)矩陣。

在實(shí)際的排課中，教務(wù)科需要按照一定要求進(jìn)行排課才能使最終得到的課表正確并且合理。那么，排課里每一個(gè)要求其實(shí)就是一個(gè)約束條件。一般來說，一個(gè)恰當(dāng)合理的課表需要滿足以下約束條件：1）一個(gè)授課人員在同一個(gè)時(shí)間段里只能上一門課程；2）一個(gè)班級(jí)在同一個(gè)時(shí)間段里只能上一門課程；3）一個(gè)教室在同一個(gè)時(shí)間段里只能上一門課程。

為了更好的開展教學(xué)工作，保證教學(xué)質(zhì)量以及便于學(xué)生對(duì)知識(shí)的吸收和理解。在排課過程中還應(yīng)該注意一些軟約束條件。

如：1）一個(gè)授課人員每天的課時(shí)量不建議超過3節(jié)課；2）教室的座位數(shù)建議大于在該教室上課的班級(jí)人數(shù)，但是也要盡可能的避免大教室被小班級(jí)所占用。如：35人的班級(jí)使用能容納100人的教室；3）針對(duì)不同性質(zhì)的課程建議的安排合適的教室進(jìn)行。如：實(shí)訓(xùn)課程或側(cè)重動(dòng)手能力要求的課程最好能安排在機(jī)房上課；4）對(duì)于周課時(shí)多的課程，建議的分散排課；

5）在排課時(shí)盡量保證學(xué)生的上課時(shí)間比較平均。最好不要出現(xiàn)一整天沒課的情況。

在實(shí)際排課中，硬性約束條件必須達(dá)到，它的精確性必須是百分之百。但是，對(duì)于上面所涉及的軟約束條件，在實(shí)際操作中允許存在一定誤差。不同的學(xué)校可以根據(jù)其自身特點(diǎn)規(guī)定這些約束條件的重要性和對(duì)它的期望值，從而決定誤差大小。為此，可以通過對(duì)以上軟約束的設(shè)置誤差權(quán)值，則目標(biāo)函數(shù)F可表示為：

這里的fi為實(shí)際值和期望值之間的誤差必須取絕對(duì)值，以避免各項(xiàng)誤差之間抵消而產(chǎn)生錯(cuò)誤。且wi表示第i個(gè)約束條件的權(quán)值，0≤wi≤1。通過目標(biāo)函數(shù)公式可知，F(xiàn)的值越小，誤差也就越小。所得的解越優(yōu)，即最后生成的課表更接近要求。

3 遺傳算法

遺傳算法是指的一種通過模擬自然界生物進(jìn)化過程求解極值的自適應(yīng)人工智能技術(shù)。實(shí)現(xiàn)遺傳算法的過程為：初始種群生成；個(gè)體適應(yīng)度評(píng)估；選擇、交叉和變異生成新的種群。

遺傳算法描述如下：

1）隨機(jī)抽取課表生成一定數(shù)量的初始種群；2）如果設(shè)置了循環(huán)次數(shù)上限，則判斷是否達(dá)到上限值。如果達(dá)到，則停止；3）通過公式計(jì)算F的值是否達(dá)到預(yù)期設(shè)置的值，如果達(dá)到，則轉(zhuǎn)6；4）按照一定的方法對(duì)種群進(jìn)行選擇、交叉、變異從而生成新的種群；5）轉(zhuǎn)2；6）記錄種群，輸出課表。

4 結(jié)論

排課作為教學(xué)管理中比較麻煩的工作，給教務(wù)科帶來了很大的困難。通過利用遺傳算法解決排課問題，很大程度上提高了工作效率。同時(shí)，也避免了排課中遇到的矛盾和沖突。對(duì)于整個(gè)教學(xué)管理工作來說，提供了非常大的便利。

[1]薛惠鋒，許五弟.基于遺傳算法的多維快速聚類算法研究.計(jì)算機(jī)應(yīng)用究，2005(6)：58-60.

[2]王小平,曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn).西安交通大學(xué)出版社，1998：67-75.

[3]王敏.基于聚類-遺傳算法的文摘提取方法研究.硅谷，2008(4)：26-29.

[4]陳國(guó)龍，葉文輝.基于關(guān)聯(lián)度分析的遺傳算法研究及其應(yīng)用.計(jì)算機(jī)應(yīng)用研究，2005(9).