高校多校區(qū)排課的遺傳算法的改進(jìn)研究

楊秀玉 雷晶晶

摘 要：隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，教育現(xiàn)代化漸漸進(jìn)入各大高校，計(jì)算機(jī)自動(dòng)排課已經(jīng)取代了傳統(tǒng)的手工排課，但多校區(qū)辦學(xué)模式的興起，給排課帶來(lái)了新的挑戰(zhàn)?；趥鹘y(tǒng)的遺傳算法，結(jié)合部門(mén)的工作經(jīng)驗(yàn)，充分考慮各方面的因素，對(duì)其進(jìn)行改進(jìn)，實(shí)現(xiàn)教務(wù)管理的科學(xué)化。

關(guān)鍵詞：多校區(qū);排課;遺傳算法

Abstract：With the development of computer technology，the modernization of education has gradually entered major universities.Computer automatic scheduling has replaced the traditional manual scheduling，but the rise of the multi-campus mode of schooling has brought new challenges to the scheduling.Based on the traditional genetic algorithm，fully considered various factors，and improved it，to realize the scientific management of educational administration.

Key words：multi-campus;course scheduling;genetic algorithm

隨著社會(huì)經(jīng)濟(jì)的不斷發(fā)展和高等教育大眾化進(jìn)程的推進(jìn)，高校招生規(guī)模不斷擴(kuò)大，越來(lái)越多的學(xué)生參加高考進(jìn)入大學(xué)接受高等教育。由于大部分高校建校早，配套設(shè)施已經(jīng)不能滿足不斷擴(kuò)大的招生規(guī)模，形成了多校區(qū)辦學(xué)新格局。目前要保證多校區(qū)協(xié)同排課，實(shí)現(xiàn)資源共享，尋求多校區(qū)排課對(duì)資源利用的最優(yōu)化。

課表是各個(gè)學(xué)校組織與實(shí)施教學(xué)過(guò)程的主要依據(jù)，是學(xué)校教學(xué)工作有計(jì)劃、有秩序進(jìn)行的重要保證?？茖W(xué)合理地編排、調(diào)度、執(zhí)行課表是順利實(shí)施人才培養(yǎng)方案，建立良好教學(xué)秩序的基礎(chǔ)。因此，排課是高校教務(wù)工作過(guò)程中必須面對(duì)的問(wèn)題，科學(xué)、規(guī)范的排課是獲得高水平教學(xué)質(zhì)量的必要條件，也是教學(xué)管理中最為關(guān)鍵的一環(huán)。它涉及到的因素很多，是一個(gè)多約束、多目標(biāo)的優(yōu)化問(wèn)題，已經(jīng)被深入研究并被公認(rèn)是NP完全問(wèn)題。[1]目前，單校區(qū)的排課普遍采用傳統(tǒng)的遺傳算法，但多校區(qū)排課涉及老師在不同校區(qū)上課、教室分配等問(wèn)題，復(fù)雜程度明顯提升，傳統(tǒng)的遺傳算法不能滿足需求。

一、排課問(wèn)題的分析

隨著各大高校的擴(kuò)招，學(xué)生數(shù)量不斷增長(zhǎng)，教學(xué)資源也越發(fā)緊張，高校也紛紛擴(kuò)建校區(qū)，使得多校區(qū)排課成為一項(xiàng)繁重而復(fù)雜的工作。多校區(qū)辦學(xué)，一學(xué)期幾百甚至上千門(mén)課程，課程的特殊性，老師的特殊要求，學(xué)校根據(jù)現(xiàn)狀的特別指示等因素都要考慮在內(nèi)，并合理地協(xié)調(diào)安排涉及的專業(yè)、老師、學(xué)生，同時(shí)要對(duì)幾百甚至上千門(mén)課程進(jìn)行合理地組織安排。

排課本身就是處理教學(xué)環(huán)節(jié)中的各種矛盾、解決教師與學(xué)生雙邊活動(dòng)、推動(dòng)教學(xué)工作向前發(fā)展的有效工作。排課的過(guò)程中出現(xiàn)的矛盾是班級(jí)、課程、教師、時(shí)間、教室、校區(qū)在排列組合中所發(fā)生的沖突和矛盾，它們也是排課過(guò)程中的約束。課表的編排必須準(zhǔn)確無(wú)誤、科學(xué)化、合理化，以保證教學(xué)過(guò)程的正常運(yùn)轉(zhuǎn)。排課涉及的因素很多，應(yīng)堅(jiān)持以“綱”為本，以“人”為本，以“?！睘楸镜娜瓌t。以“綱”為本中的“綱”是指培養(yǎng)方案和教學(xué)任務(wù)，兩者都是排課工作的重要依據(jù)，是排課必須堅(jiān)持的基本原則;以“人”為本是指考慮學(xué)生和老師在教學(xué)運(yùn)行過(guò)程中的合理性，排課必須遵循教育教學(xué)規(guī)律，堅(jiān)持“以人為本、以學(xué)為主”和“一切為了學(xué)生，為了學(xué)生一切”的教學(xué)理念，重視學(xué)生的身心健康，考慮學(xué)生的接受能力，保障課表編排的科學(xué)性、合理性;以“?！睘楸局缚紤]本校的校情，多校區(qū)排課需將不同的校區(qū)在系統(tǒng)中進(jìn)行不同的設(shè)置，確保排課沒(méi)有人為造成的低級(jí)錯(cuò)誤。[2]

二、遺傳算法的基本原理

遺傳算法是計(jì)算數(shù)學(xué)中用于解決最佳化的搜索算法，其特點(diǎn)是搜索群體和種群中個(gè)體之間的信息交換，可以用于對(duì)傳統(tǒng)方法非線性的、難以解決的、復(fù)雜問(wèn)題的處理[3]。

遺傳算法的基本思想是從問(wèn)題可能潛在解集的一個(gè)初始種群開(kāi)始，再逐代演化產(chǎn)生出越來(lái)越好的近似解。在每一代根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度大小挑選，利用自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出新的解集種群。這個(gè)過(guò)程將使得種群像自然進(jìn)化一樣的后代，比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼，可以作為問(wèn)題近似最優(yōu)解。

基本遺傳算法的構(gòu)成要素：

（1）染色體編碼?；具z傳算法使用固定長(zhǎng)度的二進(jìn)制符號(hào)串來(lái)表示群體中的個(gè)體。初始群體中各個(gè)個(gè)體的基因值可用均勻分布的隨機(jī)數(shù)來(lái)生成。

（2）適應(yīng)度函數(shù)?；具z傳算法按與個(gè)體適應(yīng)度成正比的概率來(lái)決定當(dāng)前群體中個(gè)體遺傳到下一代群體中的機(jī)會(huì)。遺傳算法是以適應(yīng)度函數(shù)為唯一反饋標(biāo)準(zhǔn)，也就是通過(guò)適應(yīng)度函數(shù)值的大小來(lái)判斷染色體的優(yōu)劣，決定染色體是否保留到下一代。[4]

（3）遺傳算子。基本遺傳算法使用選擇、交叉、變異三種遺傳算子。

三、排課遺傳算法的改進(jìn)

（一）減小排課問(wèn)題維度

多校區(qū)排課屬于涉及課程、班級(jí)、教師、教室、時(shí)間、校區(qū)的六元組合問(wèn)題，多校區(qū)課表就是將這些六種因素進(jìn)行合理整合，在滿足各種約束條件下，保證教學(xué)任務(wù)的順利完成。以{K、C、L、R、T、U}表示六元組合。

考慮到六維變量的復(fù)雜性，即使處理小規(guī)模的問(wèn)題也很繁雜，因此本文將六維變量簡(jiǎn)化為二維變量。任課老師教授哪些課程是由各二級(jí)學(xué)院相應(yīng)的教研室主任在前一學(xué)期期末就在教學(xué)計(jì)劃的落實(shí)里安排好了的，各個(gè)專業(yè)所對(duì)應(yīng)的班級(jí)在某學(xué)期需要開(kāi)設(shè)的課程也是由培養(yǎng)方案確定好的，因此，班級(jí)C、課程K、教師L的組合基本已經(jīng)確定，由Q來(lái)表示，Q={C，K，L};教室R已經(jīng)包含了校區(qū)U的信息，用時(shí)間與教室的笛卡爾積用N表示，N=T*R;進(jìn)行Q與N的組合，則六元組合的排課問(wèn)題簡(jiǎn)化為（Q，N）二元組問(wèn)題。

（二）改進(jìn)傳統(tǒng)的二進(jìn)制染色體編碼方式

染色體的編碼方式極大地影響著交叉、變異等遺傳算子的運(yùn)算方法和程序?qū)崿F(xiàn)的時(shí)間復(fù)雜度。遺傳算法的編碼方式很多，傳統(tǒng)的也是最常見(jiàn)的是二進(jìn)制編碼，由于二進(jìn)制編碼不太適用于多約束且復(fù)雜的高校課程編排，因此根據(jù)實(shí)際需求，改進(jìn)遺傳算法采用二維資源片十進(jìn)制編碼方式進(jìn)行編碼。它便于計(jì)算適應(yīng)度函數(shù)，減小時(shí)間和程序復(fù)雜程度，方便生成初始種群，便于檢測(cè)交叉和變異中的沖突。

結(jié)合實(shí)際分析，采用二維資源片十進(jìn)制編碼代替?zhèn)鹘y(tǒng)的二進(jìn)制編碼形式進(jìn)行編碼。以某高校為例，由于該校兩小節(jié)課由同一位老師授課，且教室不會(huì)改變，班級(jí)不會(huì)改變，把兩小節(jié)課合并成一大節(jié)課，因此把兩小節(jié)課作為一個(gè)時(shí)間片，允許排課的時(shí)間為周一至周五，每天不超過(guò)四大節(jié)課，一周總共20個(gè)時(shí)間片，把{11，12，13，14，21，22，…，52，53，54}作為時(shí)間片集合，其中集合{11}表示星期一的第1節(jié)課，集合{21}表示星期二的第1大節(jié)課。把{R1，R2，R3，…，Rn}作為教室集合，教室和時(shí)間的笛卡爾積共有20*n個(gè)資源片空間{（R1，11），（R2，11），（R3，11），…，（Rn，54）}。

采取此種編碼方式進(jìn)行排課可以確保一項(xiàng)信息只被分配到一個(gè)資源片，盡量避免了資源沖突，會(huì)更容易地產(chǎn)生初始種群，能縮短種群產(chǎn)生的時(shí)間，提升了實(shí)用性和排課效率。

（三）遺傳算子的改進(jìn)

1.選擇算子

選擇的目的是尋找進(jìn)化過(guò)程中最好的個(gè)體，確保目前保留下來(lái)的個(gè)體是最優(yōu)的。在此過(guò)程中若遇到更好的，就代替之前保留的，如果遇到?jīng)]當(dāng)前的個(gè)體好，就不選擇遇到的這個(gè)。選擇方法是計(jì)算染色體被選中的概率，保留概率大的。選中某一染色體的概率為：A/B。其中A代表該染色體的適應(yīng)度值，B代表所有染色體的適應(yīng)度值之和。

2.交叉算子

傳統(tǒng)的遺傳算法中有單點(diǎn)交叉和多點(diǎn)交叉兩種，由于要將遺傳算法應(yīng)用于多校區(qū)排課的實(shí)際問(wèn)題中，兩種交叉都有增加沖突的可能，會(huì)降低進(jìn)化效率，因此提出使用元素對(duì)交叉，找到染色體中的相同基因片，交叉其中的資源部分，以此得到更優(yōu)的個(gè)體，減少?zèng)_突的概率。[5]

元素對(duì)交叉，交叉前檢測(cè)有無(wú)沖突，若無(wú)沖突進(jìn)行交叉，若有沖突再次選取交叉基因。隨機(jī)取出1對(duì)染色體，采用分步交叉方式，產(chǎn)生交叉位，交換該課程中兩個(gè)染色體基因中的資源，也就是改變上課的時(shí)間教室。該交叉方法，僅對(duì)部分交叉，避免了發(fā)生沖突。

3.變異算子

變異可以避免在選擇時(shí)漏掉最優(yōu)解，維護(hù)種群的多樣性。變異和交叉一樣，變異前檢測(cè)有無(wú)沖突，若無(wú)沖突進(jìn)行變異，若有沖突重新選擇變異位。變異算子的采用與交叉算子相對(duì)應(yīng)，依據(jù)變異概率選出染色體，變換資源。

參考文獻(xiàn)：

[1]周芬.遺傳算法在多校區(qū)排課系統(tǒng)中的應(yīng)用[J].科技信息，2010（06）：234.

[2]李祥.多校區(qū)高校二級(jí)教學(xué)管理?xiàng)l件下的排課模式探討[J].科教文匯（中旬刊），2016（02）：132-133.

[3]梁宇滔.基于遺傳算法的多校區(qū)排課系統(tǒng)分析與設(shè)計(jì)[J].佛山科學(xué)技術(shù)學(xué)院學(xué)報(bào)（自然科學(xué)版），2011，29（06）：75-78.

[4]凌敏.基于遺傳算法的多校區(qū)排課系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].湖南大學(xué)，2015.

[5]李琳.多校區(qū)高校自動(dòng)排課系統(tǒng)的研究與設(shè)計(jì)[D].電子科技大學(xué)，2013.

基金項(xiàng)目：2019年中央高校建設(shè)世界一流大學(xué)（學(xué)科）和特色發(fā)展引導(dǎo)專項(xiàng)資金支持（D201903）

作者簡(jiǎn)介：楊秀玉（1993—），女，四川內(nèi)江人，碩士，研究實(shí)習(xí)員，研究方向：教學(xué)管理。