基于多類(lèi)迭代局部搜索的自動(dòng)化排課算法

宋婷 陳矛 吳超 張龔釗

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

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

中圖分類(lèi)號(hào)：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 引言

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

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

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

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

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

1 自動(dòng)化排課問(wèn)題模型

1.1 問(wèn)題定義

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

在模型中，定義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，無(wú)沖突為0。exclij為課程ci是否可安排到時(shí)段pj，可安排為1，不可安排為0。stui為課程ci的學(xué)生數(shù)，rmi為教室ri的座位數(shù)，rni為課程ci分配的房間數(shù)。dmi為課程ci要求的最小工作日，dni為X中課程ci的實(shí)際工作日。Cri為專(zhuān)業(yè)i的課程集合，Cr={Cr1，Cr2，…，Crs}為專(zhuān)業(yè)的集合，cpi， j為Cri里的課程是否被安排在pj時(shí)段，安排為1，未安排為0。

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

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

2 基本迭代局部搜索算法

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

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

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

3 多類(lèi)迭代局部搜索求解排課問(wèn)題

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

3.1 算法主框架

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

3.2 多類(lèi)分類(lèi)器

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

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