方錦烽

[摘 要] 以高校課程排課問(wèn)題為研究對(duì)象，分析了常見(jiàn)的幾類(lèi)排課問(wèn)題求解算法以及算法應(yīng)用情況，并對(duì)課程排課算法的未來(lái)發(fā)展提出展望。

[關(guān) 鍵 詞] 課程排課；局部搜索算法；人工智能方法

[中圖分類(lèi)號(hào)] G712 [文獻(xiàn)標(biāo)志碼] A [文章編號(hào)] 2096-0603（2018）23-0068-01

一、引言

課程排課問(wèn)題就是在各種資源約束條件下能夠滿(mǎn)足一系列給定目標(biāo)的分配問(wèn)題，該問(wèn)題主要有硬性和軟性?xún)纱蠹s束，硬性約束主要包括一個(gè)班級(jí)或教師不能在同一時(shí)刻有多門(mén)課程、教室的座位數(shù)不能少于學(xué)生人數(shù)等，軟性約束主要包括班級(jí)或教師前后課程的教室間距離、教師利用率等，該約束主要用于問(wèn)題求解算法評(píng)價(jià)。

二、課程排課算法研究綜述

課程排課算法主要有構(gòu)造性方法和近似方法，由于課程的排課問(wèn)題屬于NP-hard問(wèn)題，因而在求解時(shí)，大部分文獻(xiàn)采用近似方法進(jìn)行求解，因?yàn)榻品椒梢栽诤侠淼臅r(shí)間內(nèi)產(chǎn)生比較滿(mǎn)意的次優(yōu)解，該類(lèi)方法廣泛應(yīng)用于較大規(guī)模的排課問(wèn)題，近似方法又具體分為局部搜索算法和人工智能方法。

（一）構(gòu)造性方法

在排課問(wèn)題中，有優(yōu)先分配規(guī)則等構(gòu)造性方法，如陳誼等基于劃分等價(jià)類(lèi)設(shè)計(jì)基于優(yōu)先級(jí)的自動(dòng)排課算法，孫建平等使用關(guān)聯(lián)規(guī)則進(jìn)行排課的處理。

（二）局部搜索算法

局部搜索算法是使用人工智能技術(shù)，對(duì)基本局部搜索算法進(jìn)行推廣擴(kuò)展發(fā)展而來(lái)的，目的是克服基本算法容易陷入局部最優(yōu)的缺點(diǎn)，目前形成了以模擬退火算法、禁忌搜索算法等為代表的算法。模擬退火算法由Kirkpatrick等在1983年提出，它對(duì)物理中固體物質(zhì)退火的過(guò)程進(jìn)行模擬，使用Metropolis接收準(zhǔn)則以一定概率接受新的較差解或繼續(xù)在當(dāng)前的領(lǐng)域內(nèi)進(jìn)行搜索；禁忌搜索算法由Glover和Hansen在1986年提出，該算法使用一個(gè)禁忌表保持以前達(dá)到過(guò)的局部最優(yōu)點(diǎn)，在接下來(lái)的搜索中利用禁忌表中的信息不再搜索這些點(diǎn)，從而避免陷入局部最優(yōu)。如Bellio以及Song使用了模擬退火算法，在算例分析中，大部分算例都能在合理的時(shí)間內(nèi)找出可行解；Burke等使用禁忌搜索算法求解排課問(wèn)題，Lu等使用了自適應(yīng)禁忌搜索算法，初始解通過(guò)快速貪婪啟發(fā)式生成，并和另外五種參考算法進(jìn)行了比較。

（三）人工智能方法

用于課程排課的人工智能方法主要有遺傳、粒子群、多智能體等幾種算法，遺傳算法由Holland在1975年提出，它通過(guò)模擬生物遺傳和自然選擇的機(jī)理，用人工的方式構(gòu)造的一種優(yōu)化搜索算法，該算法包括初始種群、選擇/交叉/變異、適應(yīng)度函數(shù)等關(guān)鍵要素。粒子群優(yōu)化算法由Kennedy和Eberhart在1995年提出，它對(duì)鳥(niǎo)群的捕食行為進(jìn)行模擬，通過(guò)粒子在解空間內(nèi)追隨最優(yōu)的粒子進(jìn)行搜索。蟻群優(yōu)化算法是上個(gè)世紀(jì)90年代由Dorigo、Maniezzo和Colorni在研究螞蟻尋找路徑的自然行為的基礎(chǔ)上提出的，該算法最初用于求解旅行商問(wèn)題，后來(lái)在組合優(yōu)化方面得到了廣泛應(yīng)用。多智能體是分布式人工智能的研究熱點(diǎn)技術(shù)，該技術(shù)能夠充分體現(xiàn)人類(lèi)的社會(huì)智能，對(duì)動(dòng)態(tài)和開(kāi)發(fā)的現(xiàn)實(shí)環(huán)境具有良好的靈活性和適應(yīng)性。

唐勇等設(shè)計(jì)了基于遺傳算法的排課系統(tǒng)，并使用Matlab進(jìn)行編程，Alsmadi等提出了機(jī)器學(xué)習(xí)系統(tǒng)模型，并用遺傳算法進(jìn)行求解，該方法具有盡可能少地破壞軟性約束以及消除使用外部教室的優(yōu)點(diǎn)，Akkan等提出了雙目標(biāo)優(yōu)化模型，并使用混合多目標(biāo)遺傳算法求解，王念橋和姚四改提出了離散粒子群的排課算法，解決了粒子群算法后期收斂速度慢、易早熟的缺點(diǎn)。譚保華和彭偉將蟻群算法和遺傳算法相結(jié)合，結(jié)果發(fā)現(xiàn)該算法可以有效地減少搜索空間，使種群在遺傳過(guò)程中按規(guī)則分區(qū)。Babaei等使用了多智能體、元啟發(fā)式方法求解排課問(wèn)題。

三、發(fā)展與展望

以上回顧了近來(lái)學(xué)術(shù)界對(duì)課程排課問(wèn)題求解算法的研究情況，其中的絕大部分算法都是使用單一算法進(jìn)行問(wèn)題的求解，而且一般只考慮到單個(gè)目標(biāo)的情況，在接下來(lái)的課程排課問(wèn)題研究中，重點(diǎn)將是混合算法以及多目標(biāo)優(yōu)化的應(yīng)用。

參考文獻(xiàn)：

[1]陳誼，楊怡，張國(guó)龍，等.基于優(yōu)先級(jí)自動(dòng)排課算法PCSA的設(shè)計(jì)與實(shí)現(xiàn)方案[J].北京工商大學(xué)學(xué)報(bào)（自然科學(xué)版），2002，20（2）：32-5.

[2]孫建平，梅曉勇，肖政宏，等.關(guān)聯(lián)規(guī)則在高校智能排課系統(tǒng)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2002，22（5）：37-8.

[3]唐勇，唐雪飛，王玲.基于遺傳算法的排課系統(tǒng)[J].計(jì)算機(jī)應(yīng)用，2002，22（10）：93-4.

[4]Akkan C，Gülcü A.A bi-criteria hybrid Genetic Algorithm

with robustness objective for the course timetabling problem[J].Comput Oper Res，2018（90）：22-32.

[5]王念橋，姚四改.基于改進(jìn)粒子群優(yōu)化算法的排課問(wèn)題[J].計(jì)算機(jī)應(yīng)用，2013，33（1）：207-210.

[6]譚保華，彭偉.基于蟻群遺傳算法的高校排課系統(tǒng)[J].計(jì)算機(jī)仿真，2008，25（12）：294-297.

[7]Babaei H，Karimpour J，Hadidi A.A survey of approaches for university course timetabling problem[J].Computers & Industrial Engineering，2015（86）：43-59.