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

方錦烽

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

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

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

一、引言

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

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

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

（一）構造性方法

在排課問題中，有優先分配規則等構造性方法，如陳誼等基于劃分等價類設計基于優先級的自動排課算法，孫建平等使用關聯規則進行排課的處理。

（二）局部搜索算法

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

（三）人工智能方法

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

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

三、發展與展望

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

參考文獻：

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

[2]孫建平，梅曉勇，肖政宏，等.關聯規則在高校智能排課系統中的應用[J].計算機應用，2002，22（5）：37-8.

[3]唐勇，唐雪飛，王玲.基于遺傳算法的排課系統[J].計算機應用，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].計算機應用，2013，33（1）：207-210.

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