尚英武

（咸陽職業(yè)技術(shù)學(xué)院 咸陽 712000）

1 引言

調(diào)度是由一組有限的資源執(zhí)行一組給定的任務(wù)的問題［1］。作為典型的調(diào)度問題，大學(xué)課程調(diào)度問題引起了人工智能和運(yùn)籌學(xué)的高度重視。在經(jīng)典的排課問題中，一系列事件（如課程和考試）被分配到一些“課堂時(shí)間”的時(shí)段，以滿足一系列約束［2～3］。

排課算法問題可以是考試或課程安排。在考試安排中，一個(gè)目標(biāo)是盡可能均勻地分散考試，而在課程安排中學(xué)生要求考試時(shí)間盡可能緊湊［4］。本文考慮了針對(duì)課程計(jì)劃的大學(xué)排課問題。由于課程、講師以及教室數(shù)量的激增，對(duì)于每個(gè)學(xué)期的課程計(jì)劃對(duì)高校教務(wù)人員來說總是一項(xiàng)復(fù)雜的工作［5］。

大學(xué)排課問題是NP問題，包括兩個(gè)主要決定:講師分配和課程安排［6］。這兩個(gè)安排需要考慮到講師的專業(yè)資格、對(duì)課程和上課次數(shù)的限制，講師加班的合理分配以及對(duì)教室安排的可行性［7］。而且，課程安排還應(yīng)避免教師時(shí)間表和課堂上的沖突。

可將大學(xué)排課問題的約束條件可以分為兩類:硬約束條件和軟約束條件。只要滿足所有的硬約束條件，就可以實(shí)現(xiàn)一個(gè)課程計(jì)劃。硬約束條件的一個(gè)典型例子是，沒有一個(gè)老師一次最多能教一門課［8］。另一方面，軟約束條件是那些雖然必要、但應(yīng)盡可能實(shí)現(xiàn)的要求。因此，軟約束條件也可以稱為首選項(xiàng)，用于評(píng)估解決方案的質(zhì)量。軟約束條件包括講師加班的合理性等［9］。排課算法的主要目標(biāo)是找到一個(gè)可行的時(shí)間表，滿足所有的硬約束，最大限度地滿足教師和課程的軟約束［10］。

本文首先描述排課問題的不同方面，然后將排課問題表示為整數(shù)線性數(shù)學(xué)模型。為了對(duì)模型進(jìn)行優(yōu)化求解，本文提出了三種基于人工免疫、遺傳和模擬退火算法的啟發(fā)式算法。最后通過仿真試驗(yàn)對(duì)模型的有效性和不同算法的性能進(jìn)行驗(yàn)證。

2 排課問題的表述

大學(xué)排課問題的對(duì)象是一組講師、一組課程和一組教室，以及待排課日期和每天固定的授課時(shí)間段［11］。在每個(gè)授課時(shí)間段，每個(gè)教室可以提供給一門課程。每位講師和對(duì)應(yīng)的專業(yè)課程之間有較為固定的對(duì)應(yīng)關(guān)系。每門課程只能在教室和授課時(shí)間的一個(gè)子集中呈現(xiàn)。排課算法的目標(biāo)是最大限度地滿足課程數(shù)量安排，并盡量減少教室的使用數(shù)量。

大學(xué)排課問題通常用整數(shù)線性規(guī)劃公式來建模。排課算法中所使用的符號(hào)和參數(shù)如表1所示。

表1 數(shù)學(xué)模型中符號(hào)的含義

排課問題的數(shù)學(xué)模型表述如下:

約束條件表述如下:

式（1）為課程調(diào)度的數(shù)學(xué)表達(dá)式。式（2）確保了每門課程都被安排。式（3）是保證教師具有教授的課程，并且確保每位教師在任何時(shí)間點(diǎn)最多只有一門課程。式（4）確保教師在他們空閑的日子能夠講課。式（5）保證一次只能在每個(gè)教室中只安排一個(gè)課程。式（6）是確保每個(gè)教師都被分配到其對(duì)應(yīng)的專業(yè)課程。式（7）指定每個(gè)課程被分配給符合條件的課堂。式（8）和式（9）定義了決策二元變量和。

3 解決算法

由上可知，排課問題是NP問題，因此最有效的算法是啟發(fā)式算法。常見啟發(fā)式算法包括圖形著色啟發(fā)式、模擬退火、進(jìn)化算法、螢火蟲算法、兩階段啟發(fā)式算法以及蟻群算法［12～14］等?；趯?duì)上述算法的研究，本文提出了三種算法:人工免疫算法、遺傳算法和模擬退火算法，并比較這三種算法在解決課程調(diào)度問題中效率。首先闡述在算法中使用的編碼方案。

3.1 編碼方案

使用兩個(gè)二進(jìn)制矩陣和調(diào)度規(guī)則來表示解空間，如圖1所示。

第一個(gè)二進(jìn)制矩陣顯示課程和講師對(duì)應(yīng)關(guān)系，也就是把講師分配到對(duì)應(yīng)的課程在這個(gè)矩陣中，行和列分別表示課程和講師，其中“1”表示分配，而“0”表示不分配，“-”表示相應(yīng)的講師不能講授課程。

第二個(gè)矩陣表示每個(gè)講師在某個(gè)工作日是否安排上課。在這個(gè)矩陣中，行和列分別表示天和講師，其中“1”表示安排上課，“0”表示不安排上課，“-”表示當(dāng)天該講師因故（出差、調(diào)休等）不能安排上課。注意每天講師最多可以安排3門課程，因此講師的安排上課的天數(shù)取決于分配的課程數(shù)量。

圖1 編碼解決方案的示例

應(yīng)用的調(diào)度規(guī)則是把課程分配至教室和對(duì)應(yīng)的時(shí)間段。首先確定講師分配和上課日期的分配，再對(duì)教室時(shí)間段的安排進(jìn)行確定。也就是說，哪個(gè)課程安排在什么教室的哪些時(shí)間段是排課問題的硬約束條件。排課算法遵循以下規(guī)則:在該課程講師足夠分配的前提下，每個(gè)課程都分配到第一個(gè)符合課程要求的教室。如果一個(gè)講師被連續(xù)安排上課超過一天，則其授課課程將以符合該講師要求的最高優(yōu)先級(jí)安排上課時(shí)間段和教室。

以圖1為例對(duì)編碼方案進(jìn)行說明。圖1展示了一個(gè)考慮八個(gè)課程、四個(gè)講師、兩個(gè)工作日和兩個(gè)教室以及每天有四個(gè)上課時(shí)間段的排課問題。在圖1所示的解決方案中，課程1和課程6分配給講師1，課程3和7分配給講師2以及分配2、4、5和8分配給講師4。沒有課程分配給講師3。講師1和4被安排到第一天上課，講師2和4在第二天，而講師4在第一天和第二天都被安排上課。

3.2 遺傳算法

遺傳算法（Genetic Algorithm，GA）是針對(duì)傳統(tǒng)方法難以解決的一些問題而設(shè)計(jì)的。目前，遺傳算法是眾所周知的基于種群的進(jìn)化算法，可以解決離散和連續(xù)優(yōu)化問題。遺傳背后的想法來自達(dá)爾文的“適者生存”的概念，這意味著良好的父代會(huì)產(chǎn)生更好的子代。

3.2.1 算法框架

GA算法搜索一個(gè)由染色體數(shù)量表征的解決方案空間，其中每個(gè)染色體代表一個(gè)解決方案的編碼［15］。適應(yīng)值根據(jù)其性能分配給每個(gè)染色體。染色體越好，適應(yīng)值越高。染色體數(shù)量在一組算子控制下進(jìn)行迭代演變，直到符合迭代終止條件后形成最終最優(yōu)染色體。遺傳算法的典型迭代過程闡述如下。初始種群中最好的染色體被直接復(fù)制到下一代（繁殖）。選擇機(jī)制是從當(dāng)前種群中選出適應(yīng)值較高染色體，賦予其較高的交叉繁殖機(jī)會(huì)。選擇出染色體被交叉產(chǎn)生新的后代。經(jīng)過交叉繁殖過程后，每個(gè)后代可能會(huì)通過另一種稱為突變的機(jī)制進(jìn)行突變遺傳操作。完成上述兩個(gè)遺傳操作后，對(duì)形成的種群進(jìn)行適應(yīng)值計(jì)算，并重復(fù)上述整個(gè)過程。上述GA算法的框架如圖2所示。

圖2 GA算法框架

3.2.2 種群初始化和選擇機(jī)制

GA的解空間包含許多染色體，每個(gè)染色體代表一個(gè)可能的排課方案。在GA算法中最初的染色體組成初始種群。最初的染色體是由可能的排課方案中隨機(jī)生成的。

在初始化算法之后，通過目標(biāo)函數(shù)來評(píng)估每個(gè)染色體并計(jì)算其適應(yīng)度值。依據(jù)適應(yīng)值確定染色體k參與交叉遺傳操作機(jī)會(huì)的計(jì)算公式為

式（10）中fit（k）是染色體k的適應(yīng)度，pop是初始種群的數(shù)量。

3.2.3 交叉和突變遺傳操作

交叉遺傳操作目的是創(chuàng)造適應(yīng)度更好的子代。交叉遺傳操作通過交叉算子在父代染色體之間進(jìn)行交叉遺傳。值得注意的是，交叉操作必須避免產(chǎn)生不可行的解，即本文中的不符合約束條件的排課方案。交叉遺傳操作的步驟描述如下。

首先隨機(jī)產(chǎn)生均勻分布在0和1之間的隨機(jī)數(shù)。如果這個(gè)數(shù)字小于0.6，那么來自父代的那個(gè)講師的兩列（比如，來自圖1中教師-課程分配表和教師-上課日期分配表中對(duì)應(yīng)講師的兩列）被復(fù)制到新的排課方案中。新排課方案的其他列由父代排課方案填充。新排課方案可能需要對(duì)其不符合約束條件的地方進(jìn)行修改才是可行的排課方案。比如，在講師和課程的分配中，如果課程分配給兩名講師，則隨機(jī)選擇一名講師，另一名講師被劃掉；如果一個(gè)課程沒有分配給任何一個(gè)教師，則它被隨機(jī)分配給一個(gè)講師。

交叉操作后，每個(gè)排課方案由變異算子進(jìn)行突變。應(yīng)用突變的主要目的是為了保持群多樣化避免收斂到局部最優(yōu)。本文使用變異算子描述如下。隨機(jī)選擇一名講師，然后將其安排上課次數(shù)最多的一天和其安排上課次數(shù)最少的一天進(jìn)行交換。將上述突變操作隨機(jī)應(yīng)用到所有講師，并且不重復(fù)應(yīng)用到任何以為講師。這將導(dǎo)致了重新安排每位講師的排課方案。完成突變操作后，對(duì)種群中染色體適應(yīng)值重新計(jì)算，選擇這些新排課方案中的最佳方案。

3.3 模擬退火算法

模擬退火算法（SA）是一種基于局部搜索的元啟發(fā)式模擬退火過程［15］。SA包含一個(gè)稱為驗(yàn)收標(biāo)準(zhǔn)的機(jī)制，使其能夠擺脫局部最優(yōu)。驗(yàn)收標(biāo)準(zhǔn)決定是接受還是拒絕新生成的解決方案。在這種機(jī)制下，甚至可以接受較差的解決方案。

3.3.1 算法框架和驗(yàn)收標(biāo)準(zhǔn)

模擬退火算法通過對(duì)初始解決方案進(jìn)行處理，并進(jìn)行一系列的移動(dòng)，獲得最佳解決方案。算法想法是通過一個(gè)算法操作由當(dāng)前的解決方案x生成一個(gè)新的解決方案s。驗(yàn)收規(guī)則是用來確定接受或拒絕這個(gè)新的解決方案。驗(yàn)收規(guī)則由溫度參數(shù)t控制。首先計(jì)算兩個(gè)解決方案的客觀值之間的差異。如果Δ≤0，則接受該解決方案；否則，以等于exp(Δti)的概率接受解決方案。在每個(gè)溫度ti，算法繼續(xù)進(jìn)行固定次數(shù)的移動(dòng)。SA移動(dòng)時(shí)，溫度ti逐漸下降。溫度下降的計(jì)算公式為

式（11）中初始溫度通常設(shè)定為50，α=0.97。SA算法總體框架如圖3所示。

圖3 SA算法框架

3.3.2 移動(dòng)操作

本文通過以下過程從當(dāng)前的排課方案中產(chǎn)生一個(gè)新的排課方案。隨機(jī)選擇一門課程，并將其分配給另一位合格的講師。值得注意的是，課程重新分配會(huì)影響兩名教師，一名課程減少，另一名課程添加。因此，這兩位講師上課的天數(shù)可能需要更新。基于這個(gè)新的課程安排，兩位教師的上課日期的安排也被更新。

3.4 人工免疫算法

人工免疫算法（AIA）是一種基于總體的元啟發(fā)式算法，它通過幾種編碼的解決方案進(jìn)行并行搜索［16］。AIA的基本思想來自對(duì)自然生物體的生理免疫系統(tǒng)的模擬。免疫系統(tǒng)是防御外來病毒（抗原）的身體。這是由一組抗體完成的。在檢測(cè)到抗原的情況下，鑒定該抗原的抗體通過克隆增殖。也就是說，無論何時(shí)抗原滲透到體內(nèi)，他們首先認(rèn)識(shí)到這些抗體更有資格與抗原的侵入作斗爭(zhēng)，然后系統(tǒng)在下一代產(chǎn)生更多的這些抗體的變異。

每種抗體的質(zhì)量由親和力值表示。親和力較強(qiáng)的抗體可以更好地與抗原作用?？乖侵刚诳紤]的問題。每個(gè)抗體是一個(gè)可行的解決方案，親和力是抗體獲得的目標(biāo)函數(shù)值。

3.4.1 算法框架

AIA用抗體種群搜索問題空間。每個(gè)抗體依據(jù)其性能將被賦予一個(gè)親和力值?？贵w越是理想，親和力值越高。使用免疫算子，包括克隆選擇算子和親和力成熟算子，從當(dāng)前的種群中產(chǎn)生新的種群。

克隆選擇旨在繁殖消除抗原的更好抗體。親和力成熟算子由超突變和受體編輯組成。超突變對(duì)應(yīng)于產(chǎn)生類似的但不完全相同的新解決方案。較低的抗體應(yīng)該以較高的速率超突變，而較高的抗體則以較低的突變率。受體編輯是確定超突變率的機(jī)制。

AIA算法框架為:首先使用一個(gè)用戶定義的親和函數(shù)計(jì)算每個(gè)抗體的克隆數(shù)量；隨后所有增殖的克隆體都聚集在一個(gè)突變池中；然后突變池的克隆被超突變產(chǎn)生新的抗體；最后對(duì)新種群進(jìn)行評(píng)估，整個(gè)過程重復(fù)。初始的染色體是由可行解隨機(jī)生成的。

3.4.2 克隆選擇過程

親和力值測(cè)量是衡量每種抗體消除抗原的能力。親和力值越高意味著與抗原作用的抗體越好。假設(shè)優(yōu)化問題作為抗原和編碼方案的抗體。更好的抗體可以更好地對(duì)抗優(yōu)化問題。設(shè)定每個(gè)抗體的親和力等于目標(biāo)函數(shù)值。

克隆每個(gè)抗體進(jìn)入突變池的概率與其親和力值成正比例關(guān)系。因此親和力越高的抗體越有可能具有更多的克隆。變異池具有固定數(shù)量的克隆體，其中一部分是當(dāng)前種群中最好的抗體的克隆體，剩余部分是采用選擇機(jī)制選擇部分抗體的克隆體。

3.4.3 親和力成熟過程

親和力成熟過程的主要功能是對(duì)池中存在的所有克隆體進(jìn)行隨機(jī)更改。每個(gè)克隆根據(jù)親和值經(jīng)歷不同的變化率。較低的克隆經(jīng)歷較高的變化率，而較好的克隆受到輕微的變化。這些改變基于超突變過程完成。

首先對(duì)低速率的超突變過程進(jìn)行描述。隨機(jī)選擇一門課程，并重新分配給另一位具有最高優(yōu)先級(jí)的合格講師。課程的重新分配影響到兩個(gè)講師，一個(gè)課程減少，另一個(gè)課程增加，這兩位講師的上課天數(shù)可能會(huì)發(fā)生變化，因此要對(duì)講師的上課日期安排進(jìn)行更新?；趯?duì)所有課程的本地搜索進(jìn)行上述隨機(jī)、不重復(fù)重新分配。通過重新分配每個(gè)課程來產(chǎn)生n個(gè)新的排課方案。從中選擇出最佳的排課方案。

對(duì)于高速率的超突變過程，本文使用GA中定義的變異算子。通過定義一個(gè)標(biāo)準(zhǔn)來確定是否使用高速率超突變的變異算子。如果滿足式（12），則進(jìn)行低速率超突變，否則使用變異算子進(jìn)行高速率超突變。

本文使用類似于模擬退火的驗(yàn)收標(biāo)準(zhǔn)的方法來確定是否接收新的排課方案，這導(dǎo)致除了接受更好的新排課方案外，可能還會(huì)接受較差的排課方案。通過這個(gè)驗(yàn)收策略使得算法容易避免陷入局部最小值。同時(shí)為了保證算法效率，算法應(yīng)用了精英克隆策略，意味著最好抗體將直接被復(fù)制到下一代。

4 仿真驗(yàn)證

利用兩組實(shí)例的計(jì)算評(píng)估模型的性能和所提出的算法。第一組由較少講師和課程數(shù)量組成，用于評(píng)估模型解決問題的能力以及算法的一般性能。該組包括10對(duì)課程講師組合（m，n）:（20，5），（20，7），（40，10），（40，15），（60，10），（60，15），（80，15），（80，20），（100 ，20）和（100，25）。

第二組包括較多講師和課程的數(shù)量組成，通過這些實(shí)例比較所提出的算法的性能。該組實(shí)例包括6個(gè)組合（m，n）:（100，20），（100，30），（200，30），（200，50），（300，50）和（300，70）。

兩組實(shí)例的其他參數(shù)假設(shè)還有:200間教室、每周有5個(gè)工作日以及每天有3個(gè)時(shí)間上課段。我們通過隨機(jī)生成問題的其他參數(shù)為每個(gè)排課問題生成10個(gè)實(shí)例。

模型和算法分別在CPLEX和JAVA中實(shí)現(xiàn)。它們運(yùn)行在4.0 GHz Intel Core 2 Duo和8 GB RAM內(nèi)存的個(gè)人電腦上。該模型允許最多600s的計(jì)算時(shí)間。算法的停止條件被設(shè)置為固定為nm秒級(jí)別的CPU運(yùn)行極限。隨著課程或講師的數(shù)量的增加，這個(gè)停止標(biāo)準(zhǔn)需要更多的時(shí)間。相對(duì)百分比偏差（RPD）被用作模型性能指標(biāo)。RPD計(jì)算方法為

式（13）中ALG和Max是算法計(jì)算出的排課方案和給定實(shí)例的上限。其中給定實(shí)例的上限等于為給定實(shí)例找到的最佳目標(biāo)。

4.1 算法參數(shù)設(shè)置

GA和AIA的關(guān)鍵參數(shù)是種群大小，SA的關(guān)鍵參數(shù)是降溫速率。種群大小分別設(shè)置為｛20，40，70，100｝，而溫度下降速率則被設(shè)置為｛0.95，0.90，0.85，0.8｝。針對(duì)第一組數(shù)據(jù)生成20個(gè)不同的實(shí)例。然后，我們通過不同算法分別計(jì)算。計(jì)算結(jié)果如圖4所示。

圖4 測(cè)試算法的平均RDP

由圖4可以看出，GA算法的最佳種群大小為40，而AIA為40。對(duì)于SA算法最佳溫度下降速率為0.95。

4.2 較少課程和講師數(shù)量的實(shí)驗(yàn)

通過本文模型來計(jì)算小規(guī)模排課實(shí)例。計(jì)算結(jié)果如表1所示。

表2 較少課程和講師數(shù)量的模型計(jì)算結(jié)果

由表1數(shù)據(jù)可以看出，該模型能夠在不到60s的時(shí)間內(nèi)解決m=60和n=15的實(shí)例。m=80的實(shí)例需要小于500s。但是該模型不能在600s內(nèi)解決m=100的實(shí)例。

采用三種測(cè)試算法對(duì)排課實(shí)例進(jìn)行計(jì)算，得出的平均RPD如表3所示。

表3 不同算法的RDP

由表3可以看出，AIA優(yōu)于其他算法，平均RPD為0.87%。其次為GA，為1，47%。表現(xiàn)最差的算法是SA，平均RPD為1.91%。綜上所述，AIA在小規(guī)模的排課問題中表現(xiàn)最好。

4.3 較多課程和講師數(shù)量的試驗(yàn)

在本節(jié)中，所提出的算法（GA，SA和AIA）在第4節(jié)中提到的60個(gè)較大規(guī)模的排課問題上進(jìn)行比較。表3顯示了算法的結(jié)果。圖5顯示了三種測(cè)試算法的平均RPD和最小顯著差異（LSD）間隔。

表4 不同算法的平均RPD

由表4和圖5可以看出，表現(xiàn)最好的算法是AIA，平均RPD為0.63%。其次式GA算法，平均RPD為1，66%。最后是SA算法，其平均RPD為2.89%。

圖6顯示了算法的性能與課程數(shù)量的關(guān)系。

圖6 算法的平均RPD與課程的數(shù)量

就課程數(shù)量而言，AIA在不同規(guī)模的排課問題上保持了基本穩(wěn)定的優(yōu)于其他算法的性能，而SA在大規(guī)模排課問題上性能表現(xiàn)相差較大。

5 結(jié)語

對(duì)于大學(xué)課程安排的問題，本文將目標(biāo)函數(shù)定義為安排課程來最大化教師、課程和上課日期的利用效率。首先以整數(shù)線性程序的形式對(duì)排課問題進(jìn)行數(shù)學(xué)建模。仿真實(shí)驗(yàn)證明了該模型能夠解決多達(dá)6門課程和15名教員的問題。此外，本文開發(fā)了三個(gè)先進(jìn)的啟發(fā)式來解決較大規(guī)模排課問題。算法基于人工免疫，遺傳和模擬退火算法。在仿真實(shí)驗(yàn)中對(duì)算法參數(shù)進(jìn)行優(yōu)化調(diào)整之后，通過與模型得到的最優(yōu)解進(jìn)行比較來評(píng)估它們。并且將這些算法應(yīng)用在一組較大規(guī)模的排課問題上進(jìn)行計(jì)算性能比較。實(shí)驗(yàn)結(jié)果表明，所提出的人工免疫算法優(yōu)于其他算法。