課程排課問題算法研究綜述

方錦烽

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

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

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

一、引言

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

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

課程排課算法主要有構(gòu)造性方法和近似方法，由于課程的排課問題屬于NP-hard問題，因而在求解時，大部分文獻采用近似方法進行求解，因為近似方法可以在合理的時間內(nèi)產(chǎn)生比較滿意的次優(yōu)解，該類方法廣泛應(yīng)用于較大規(guī)模的排課問題，近似方法又具體分為局部搜索算法和人工智能方法。

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

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

（二）局部搜索算法

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

（三）人工智能方法

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

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

三、發(fā)展與展望

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

參考文獻：

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

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

[3]唐勇，唐雪飛，王玲.基于遺傳算法的排課系統(tǒng)[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]王念橋，姚四改.基于改進粒子群優(yōu)化算法的排課問題[J].計算機應(yīng)用，2013，33（1）：207-210.

[6]譚保華，彭偉.基于蟻群遺傳算法的高校排課系統(tǒng)[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.