宋婷 陳矛 吳超 張龔釗

摘 要：針對局部搜索算法容易陷入局部最優(yōu)，無法自適應(yīng)多種約束條件下排課的問題，提出一種基于多類迭代局部搜索的自動化排課算法。首先，通過多類分類器依據(jù)排課問題特征對排課問題進(jìn)行分類，指導(dǎo)迭代局部搜索的鄰域選擇及參數(shù)設(shè)置。然后，在迭代局部搜索的過程中，使用基于序列的貪婪算法獲得可行解。最后，采用以問題特性為導(dǎo)向的雙溫控制模擬退火算法在鄰域中搜索局部最優(yōu)解，并通過特定的擾動策略對當(dāng)前最優(yōu)解進(jìn)行擾動后作為新的初始解進(jìn)行迭代，最終達(dá)到全局最優(yōu)。該算法在兩個(gè)國際著名的數(shù)據(jù)集，即第二屆國際時(shí)間表大賽基于課程的時(shí)間表數(shù)據(jù)集和Lewis 60數(shù)據(jù)集上進(jìn)行了測試。實(shí)驗(yàn)結(jié)果表明，與當(dāng)前文獻(xiàn)中求解該問題的其他性能較優(yōu)算法相比，所提出的算法具有更高的求解效率和質(zhì)量。

關(guān)鍵詞：自動化排課;多類;迭代局部搜索;模擬退火;最優(yōu)化

中圖分類號：TP301.6（算法理論）

文獻(xiàn)標(biāo)志碼：A

Abstract： Focusing on the issue that local search algorithm is prone to fall into the local optimum and does not adapt to the course arrangement under multiple constraints， an automated course arrangement algorithm based on multi-class iterated local search was proposed. Firstly， the course arrangement problems were classified by the multi-class classifier according to the characteristics of the problems to guide the neighborhood selection and parameter setting of the iteration local search. Then， in the process of iterated local search， the sequence-based greedy algorithm was used to obtain the feasible solutions. Finally， the problem characteristics oriented two-temperature control simulated annealing algorithm was used to search for local optimal solution in the neighborhood and the current optimal solution was perturbed by a specific strategy and iterated as the new initial solution to achieve global optimization. The proposed algorithm was tested on two internationally famous datasets， which are the second international timetabling competition dataset and Lewis 60 dataset. The experimental results show that， compared with the existing efficient algorithms in current literatures， the proposed algorithm has higher efficiency and solution quality.

Key words： automated course arrangement; multi-class; Iterated Local Search （ILS）; Simulated Annealing （SA）; optimization

0 引言

自動排課問題是一個(gè)包含教室、課程、時(shí)間、班級、教學(xué)資源等多種因素的組合優(yōu)化問題，已被證明是一個(gè)非確定多項(xiàng)式（Non-deterministic Polynomial， NP）完全問題[1]。由于該類問題的復(fù)雜性，引起了越來越多學(xué)者的關(guān)注和研究。2002年，英國和意大利合作組織了五年一屆的國際時(shí)間表競賽（International Timetabling Competition，? ITC）[2]，旨在為研究者提供一個(gè)可以普遍接受的基準(zhǔn)來縮小研究與實(shí)踐之間的差距。排課問題通常被定義為在特定約束條件下，盡可能合理地安排有限的教育資源。其約束可被分為兩類：在任何情況下都不能違反的約束稱為硬約束;而那些可以違反，但應(yīng)盡可能地減少違反值的約束被稱為軟約束。滿足了所有硬約束的課程表被稱為可行解，而最優(yōu)的課程表（最優(yōu)解）則是指在滿足所有硬約束的條件下，最小化軟約束的違反值。

對于這類NP難問題，確定型算法只適用于在合理的時(shí)間內(nèi)解決小規(guī)模問題實(shí)例。因此，ITC競賽及其后大多數(shù)的相關(guān)研究都集中在快速近似啟發(fā)式算法和元啟發(fā)式算法上，以尋求在給定的時(shí)間范圍內(nèi)獲取可行的最優(yōu)解決方案。典型的算法有基于圖著色的方法[3]、模擬退火（Simulated Annealing， SA）算法[4]、禁忌搜索算法[5]、變鄰域搜索算法[6]、遺傳算法[7]、蟻群算法[8]、蜂群算法[9]、和聲搜索算法[10]等。但所有方法都還未能達(dá)到所給定問題解的下界，對問題最優(yōu)解的進(jìn)一步探討仍在進(jìn)行。在這些算法中，雖然模擬退火（SA）算法是一個(gè)簡單且易于實(shí)現(xiàn)的通用框架，但它對于排課這類組合優(yōu)化問題的求解確實(shí)非常有效。例如，第一屆國際時(shí)間表競賽的冠軍和第二屆國際時(shí)間表競賽的三個(gè)類別組的冠軍均采用了基于SA的算法。

解決排課問題的算法通常由兩階段組成：首先構(gòu)建一個(gè)可行的排課方案，然后盡可能地減少軟約束違反值。通常，時(shí)間表問題可以等同于一個(gè)圖著色問題，對于大多數(shù)ITC競賽的排課問題實(shí)例而言，獲得可行的排課方案幾乎不能構(gòu)成挑戰(zhàn)。 因此參賽算法的主要焦點(diǎn)都集中在最小化軟約束違反值上。

近年來，Lewis等[11]創(chuàng)建了一組60個(gè)僅包含硬約束的測試數(shù)據(jù)集，其創(chuàng)建目的在于將注意力聚焦于尋求可行解，以對不同算法進(jìn)行更公平的比較。而傳統(tǒng)基于序列的技術(shù)只能為一小部分測試實(shí)例找到可行解。針對該問題，已經(jīng)有多種不同的算法提出來求取這些測試實(shí)例的可行解。包括混合模擬退火算法[12]、基于團(tuán)的算法[13]、基于事件插入的啟發(fā)式算法[14]、基于模擬退火的元啟發(fā)式算法[15]、memetic算法[16]等。迄今為止，這些方法依然無法完全解決所有樣本。因此，Lewis等[11]的這組測試實(shí)例，直到今天仍然是評估不同方法的一個(gè)具有挑戰(zhàn)性的基準(zhǔn)數(shù)據(jù)集。

本文提出了一種多類迭代局部搜索（Multi-class Classification Iterated Local Search， MC-ILS）算法，該算法分別針對ITC競賽數(shù)據(jù)集和Lewis60數(shù)據(jù)集尋找可行的排課方案。該算法經(jīng)過測試，并與當(dāng)前文獻(xiàn)中成績較好的算法進(jìn)行了比較。計(jì)算結(jié)果表明，所提算法具有優(yōu)異的性能和更強(qiáng)的適應(yīng)性，無論是在最小化軟約束違反值的ITC競賽數(shù)據(jù)集，還是在更難的硬約束條件下尋找可行解，均優(yōu)于其他對比算法。

1 自動化排課問題模型

1.1 問題定義

排課問題的求解本質(zhì)上是一個(gè)解決教室R={r1， r2，…， rm}、課時(shí)P={p1， p2，…， pn}、課程C={c1， c2，…， ct}等教育資源矛盾的多因素優(yōu)化決策過程。

在模型中，定義X為候選解課表，每周d天，每天h節(jié)，一周總時(shí)段數(shù)n=d×h。xij為安排在ri教室pj時(shí)段的課程，事件G={g1，g2，…，gs}是綁定了教師、學(xué)生和第幾次課信息的課程集合，|G|=∑ti=1cli，cli為第i個(gè)課程每周需上的次數(shù)。conij為課程ci和cj的沖突情況，有沖突為1，無沖突為0。exclij為課程ci是否可安排到時(shí)段pj，可安排為1，不可安排為0。stui為課程ci的學(xué)生數(shù)，rmi為教室ri的座位數(shù)，rni為課程ci分配的房間數(shù)。dmi為課程ci要求的最小工作日，dni為X中課程ci的實(shí)際工作日。Cri為專業(yè)i的課程集合，Cr={Cr1，Cr2，…，Crs}為專業(yè)的集合，cpi， j為Cri里的課程是否被安排在pj時(shí)段，安排為1，未安排為0。

根據(jù)要解決的問題及參數(shù)定義，具體的硬約束和軟約束描述及相應(yīng)的數(shù)學(xué)表達(dá)式如下。

1.2 硬約束及其數(shù)學(xué)表達(dá)

2 基本迭代局部搜索算法

局部搜索算法的基本思想是首先找到一個(gè)或一組初始解，然后按照一定的策略在鄰域中搜索新的可行解，并根據(jù)特定的接受準(zhǔn)則更新當(dāng)前解，最終找到最優(yōu)解。局部搜索算法具有結(jié)構(gòu)簡單，易理解易實(shí)現(xiàn)的優(yōu)點(diǎn)，但由于其搜索性能過于依賴鄰域結(jié)構(gòu)和初始解，容易陷入局部最優(yōu)。

模擬退火算法作為一種經(jīng)典的局部搜索算法，其靈感源自物理中固體退火原理，固體的結(jié)晶狀態(tài)通常是內(nèi)能最小的狀態(tài)。將固體加溫至充分高，此時(shí)，固體內(nèi)部粒子呈隨機(jī)排列狀態(tài)，內(nèi)能增大;再讓其逐步降溫冷卻，此過程使得粒子趨于有序，每個(gè)溫度都能達(dá)到平衡態(tài)，最后常溫時(shí)達(dá)到內(nèi)能最小的基態(tài)。根據(jù)Metropolis準(zhǔn)則，粒子在溫度T下趨于平衡的概率為exp（-ΔE/（kT）），其中：E是溫度T處的內(nèi)能，ΔE是變化量，k是玻爾茲曼常數(shù)。與之相對應(yīng)，模擬退火算法的過程是首先找到一個(gè)初始解作為當(dāng)前解，并設(shè)定一個(gè)初始溫度值T，然后按照一定的策略在鄰域中搜索新的候選解，計(jì)算候選解與當(dāng)前解之間的差值ΔE，按照概率exp（-ΔE/（kT））接受候選解為新的當(dāng)前解。在不斷迭代的過程中對溫度T逐步降溫，不斷減少差解的接受概率，最終找到近似解。

迭代局部搜索算法是對局部搜索算法的一種改進(jìn)，通過對局部尋優(yōu)策略的迭代調(diào)用來跳出局部最優(yōu)。在每次迭代中使用前面局部搜索得到的最優(yōu)解作為本次搜索的初始解，以此反復(fù)來獲取全局最優(yōu)解。

3 多類迭代局部搜索求解排課問題

基本迭代局部搜索算法主要用于函數(shù)優(yōu)化，將其應(yīng)用于自動化排課問題，需要在算法框架、初始化方法、鄰域設(shè)計(jì)、模擬退火等方面進(jìn)行改進(jìn)。

3.1 算法主框架

在啟發(fā)式算法的設(shè)計(jì)中，待解決問題自身的特征往往決定了算法的具體設(shè)計(jì)細(xì)節(jié)，需要對每一個(gè)具體問題設(shè)計(jì)專門的解決辦法，很難用一個(gè)通用算法解決所有問題。本文提出一種多類迭代局部搜索（MC-ILS）算法來求解排課問題，通過對各種排課問題特征的分析抽取并用多類分類器進(jìn)行分類，指導(dǎo)迭代局部搜索過程，實(shí)現(xiàn)自動化排課。具體步驟如下：

3.2 多類分類器

不同的排課問題具有不同的條件和約束，需要依據(jù)是否有軟沖突、房間數(shù)、時(shí)段數(shù)、課時(shí)約束等特征條件，對算法步驟中的實(shí)現(xiàn)進(jìn)行參數(shù)調(diào)整和過程選擇。針對該問題，采用超啟發(fā)算法雖然可以提高排課算法的適應(yīng)度，但也帶來算法和時(shí)間復(fù)雜度的提升。本文采用基于決策樹的多類分類器實(shí)現(xiàn)局部搜索算法的選擇和參數(shù)的設(shè)定，簡化算法結(jié)構(gòu)和運(yùn)行時(shí)間。決策樹構(gòu)造如圖1所示。

決策樹第一層節(jié)點(diǎn)（問題類型）根據(jù)軟硬約束構(gòu)造，判別僅存在硬約束還是軟硬約束均存在，第二層節(jié)點(diǎn)（問題難度）根據(jù)房間數(shù)和事件數(shù)等條件構(gòu)造。為簡單起見，計(jì)算所有樣例事件數(shù)與房間數(shù)的比值，依據(jù)中值分為難易兩類，在實(shí)踐中此種劃分并不總是精確，因此需要再通過第三層節(jié)點(diǎn)（問題特征）對問題進(jìn)行更精確的劃分。當(dāng)決策樹構(gòu)造完畢后，就采用決策樹算法對不同算例進(jìn)行分類。