教學資源配置優化中遺傳算法的應用與改進

嚴 宏

(1.中國民用航空飛行學院,四川 廣漢 618307;2.四川大學 視覺合成圖形圖像技術國家重點學科實驗室,四川 成都 610064)

教學資源配置優化中遺傳算法的應用與改進

嚴 宏1,2

(1.中國民用航空飛行學院,四川 廣漢 618307;2.四川大學 視覺合成圖形圖像技術國家重點學科實驗室,四川 成都 610064)

對于臨時新增教學任務，教學資源安排不同于學期開始前的教學資源配置，通常具有特定的配置需求。在教學資源有限的情況下，為了使新增教學班級配置的教室更加一致或接近，避免頻繁變動教室給教學帶來的不便，使用遺傳算法進行教室資源的分配，并根據應用需求進行了改進。其中設計了更加適宜的十進制編碼，提出的適應度函數能有效地對教室資源的一致或接近程度進行量化計算。根據染色體編碼特點和優化目標，對遺傳算子進行選擇和改進，特別對單點交叉進行改進盡可能地提高交叉后的適應度，同時保持種群的多樣性。實驗結果表明，改進的遺傳算法相對于標準遺傳算法在用時更少的情況下得到的教學資源分配更加滿足優化目標，計算效率得以提高，并且成功應用于實際的教學資源配置。

資源配置；遺傳算法；十進制編碼；適應度函數；交叉算子

0 引 言

近年來，隨著部分高校招生專業的新增和招生規模的擴大，在一時難以增加相關教學資源的情況下，如何高效利用現有教學資源已成為教學實施過程中亟需解決的問題，關系著教學質量的保證和提高。教學資源配置的高效合理除了在學期開始前的排課過程中需要考慮外，對于開學后臨時增加的教學計劃，比如在職人員培訓班、補修班或者重修班，由于此時教學資源更為有限，更需要進行資源的配置優化。從本質上講，這些新增教學班級的安排其實是排課問題，而排課問題已被S. Even以及Cooper等證明為NP完全問題[1-2]。對于這類完全多項式非確定性問題，雖然可以在多項式時間內進行驗算，然后再使用窮舉法得到問題的解，但是這種方式下計算時間隨問題復雜程度呈指數增長，因此這種求解算法不具有實際的應用價值。為了滿足實際應用中對于計算性能的要求，對于NP完全問題通常采用求近似解的策略，此類算法中的遺傳算法正是通過模擬自然進化過程搜索近似最優解，具有成熟的理論作為基礎，應用較為廣泛。

由美國的J. Holland教授在1975年提出的遺傳算法[3]借鑒了基因遺傳和生物進化的思想，通過選擇、交叉、變異等遺傳算子使種群不斷進化，從而得到局部最優解或全局最優解。它是一種有效的隨機搜索優化算法，具有并行性、自適應和學習性、魯棒性以及易于與其他算法結合改進的特點，被廣泛用于排課這類資源配置的組合優化問題。

文獻[4]提出了遺傳算法在課程安排問題中多點式搜索和優化方法；文獻[5]論述了使用遺傳算法解決排課問題中教師優先權的問題；文獻[6]在遺傳算法中引入排課規則解決了按優先級排課的問題；文獻[7]在遺傳算法應用于排課過程中提出優勢群體有限策略和最優個體替換策略；文獻[8]對用于排課系統的遺傳算法在染色體編碼和交叉變異概率選擇方面進行了改進；文獻[9]主要針對多校區排課問題進行優化；文獻[10]在遺傳算法中采用了群體優勢策略。

文中論述的新增教學班級的教學資源配置優化問題雖然在實質上為排課問題，但是不同于多個班級的整體性排課，在應用環境及優化目標方面存在區別，比如上課時間事先已經確定和需要盡量固定的教室，難以完全利用針對整體性排課的編碼方式、適應度函數以及交叉和變異算子，需要進行改進以便更好地符合應用需求。

1 數學模型和優化目標

1.1 數學模型

教學資源配置在教學過程中一項常見的工作就是進行課程安排，而排課涉及到的教學資源主要是教師、教室、課程、班級和上課時段。在此設定條件下，排課過程中教學資源配置優化問題可以描述為求構成解空間的五元組(C,O,T,R,S)。其中,C表示班級，O表示課程，T表示教師，R表示教室，S表示上課時段。

對于上述開學后臨時增加的教學計劃安排問題，由于教學資源的有限性，在新增教學班級的教學資源配置優化時必然存在資源的約束性，其中與現有排課數據之間存在上課時段和教室使用方面的約束關系。對應于現有排課數據和新增教學班級安排的兩個五元組(Ci,Oi,Ti,Ri,Si)和(Cj,Oj,Tj,Rj,Sj)，必須滿足如下關系：

Si=Sj→Ti≠Tj

(1)

Si=Sj→Ri≠Rj

(2)

上述兩個關系式中，式(1)表示不同教學班級在同一時段的教師不應相同，否則造成沖突，同樣式(2)表示不同教學班級在同一時段安排的教室應該分屬不同的教室。在實際的教學資源配置過程中，對于這類新增的教學班級，通常已通過教師上課時間的協調或外聘教師等方法做好上課時段和上課教師的安排，那么上述約束關系式(1)可以不予考慮，而約束關系式(2)必須滿足，否則將引起教室使用方面的沖突。

1.2 優化目標

對于這類新增的教學班級，由于講授的內容和參加學習的人員早已確定，對應于五元組(C,O,T,R,S)中課程O和班級C的值得以確定，而從以上論述可知對于新增教學班級的上課時段和上課教師已做好安排，即五元組(C,O,T,R,S)中上課時段S和教師T的值得以確定，那么就需要對五元組中還未確定的教室進行組合配置。

而對于這類新增教學班級的教室配置，滿足上述式(2)這個硬性約束的解是可行解，求解的目標是從可行解中找出更加優化的解，優化的目標是盡量配置為同一教室或者相近的教室，也就是說最好將教室這個教學資源配置為同一教室，這樣可以避免給參與教學的教師和學生帶來教室變動的不便，也是為了盡量減少教室安排帶來其他方面的事宜，如減輕物業管理工作量。在教室資源緊張難以配置為同一教室的情況下，不同時段配置的教室變動盡量減少，使教師和學生在教學任務的參與當中更加方便高效，這是文中使用遺傳算法進行優化的目標，也是遺傳算法中適應度函數設計的參考依據。

2 算法設計及流程

使用遺傳算法求解問題通常包含如下的關鍵步驟：染色體編碼、種群初始化、適應度函數的設計、選擇操作、交叉操作、變異操作以及終止條件的確定。

2.1 可行解空間及染色體編碼

在優化求解問題中，滿足所有約束條件的解便是該問題的一個可行解，而所有的可行解便構成了可行解空間。優化解便是其中能夠更好滿足優化目標的可行解，因此尋求優化解需要確定可行解空間，非可行解即使能更好地滿足優化目標也不能稱之為優化解。

從上述論述可知，可行解中五元組(C,O,T,R,S)的C,O,T和S已確定，剩下R對應的教室應不和現有的排課數據沖突，而文中針對的教務管理系統能夠提供接口獲取在指定時段內空閑的所有教室，也就是說能獲取上課時段S內滿足約束的空閑教室R，從而組成五元組構成可行解。

為了便于描述并且不失一般性，假設新增教學班級有N個上課時段，這些時段按時間先后的順序排序并表示成S1,S2,…,SN，那么可以通過系統接口獲取各個上課時間段對應的空間教室集合，同樣對應時間先后順序依次表示為{R1},{R2},…,{RN}，依次選取各個集合中的教室組成五元組(Ci,Oi,Ti,Ri,Si)，通過這樣的組合方式形成的所有五元組就構成了可行解空間。

遺傳算法采用仿生過程搜索優化解，模擬的是基因重組與進化的過程，把待解決問題的解轉換成特定形式的編碼，這種形式編碼中特定一段對應的稱之為基因，這樣若干基因中組成一個染色體，一個染色體便可以對應優化問題的一個解。染色體編碼是把優化問題的解從其解空間中的形式轉換到遺傳算法所能處理的搜索空間中的形式，這個過程是應用遺傳算法進行優化過程的首要步驟，關系到后續遺傳操作算子的設計和效率,也和遺傳算法的收斂速度緊密相關。

為了減小染色體編碼的長度，縮小搜索空間，對于五元組中已確定的C,O,T和S不再編碼，而只對各個上課時段的教室進行編碼。為了實現存取的高效，將獲取的各個時段空閑教室集合分別采用數組方式存儲，那么對各個時段的配置教室就只需對相應的數組下標進行編碼。文中采用十進制編碼而并未采用最為常見的二進制編碼方法[11]，原因在于二進制編碼除了編碼較長、搜索空間較大和編解碼比較費時的缺點，還存在漢明懸崖(HammingCliff)的問題[12]，即相鄰整數的二進制代碼之間有很大的漢明距離，使得遺傳算法的交叉和突變都難以跨越，而使用十進制編碼對于數組下標來說更加直接高效。具體的編碼方式為每一個可行解對應的染色體由多個基因構成，每個基因對應課程安排中的一個上課時段，其十進制編碼經過解碼轉換后為對應時段空閑教室集合中配置教室的所在下標。染色體的編碼方式和空閑教室集合的存儲方式如圖1所示。

圖1 染色體的編碼方式和空閑教室集合的存儲方式

基因編碼的十進制整數Di并未直接用于表示所選教室的下標Ei，而是需要進行如下轉換：

Ei=DiMODAi

其中，Ai為基因對應時段空閑教室集合中教室的總數，即存儲教室集合的數組大小。

由于每個時段的空閑教室總數不同，那么每個基因對應數組的大小不一，選擇這種取模的方式，可以在隨機生成初始種群和后續交叉及變異操作中不用分別考慮每個數組的下標越界問題，編碼和轉換的方法更加統一和高效。

2.2 初始種群的生成

在確定好染色體編碼方式后，遺傳算法首先需要獲得一組處于初始狀態的染色體，這組染色體是后續選擇、交叉、變異等操作的基礎，是最終優化解獲取的數據來源，通常被稱為初始種群。進行初始種群的生成主要涉及兩個方面的問題：種群規模的大小和初始種群各染色體的生成方式。其中，種群規模的大小直接影響到遺傳算法的收斂性和計算效率。規模太小，染色體多樣性的欠缺容易導致收斂到局部最優解；規模太大，計算復雜費時且難以收斂。

文中根據文獻[12]中種群規模的建議范圍，將群體規模設定為200。根據上述對編碼方式的描述可知，在不考慮數組下標越界問題的情況下，可以使用隨機生成的十進制無符號整數作為基因編碼，按照新增教學計劃所需的上課時段總數生成相同數量的基因，然后將這些基因連接從而生成初始種群中的染色體。

2.3 適應度函數的實現

使用遺傳算法進行優化求解，目標是為了獲取更好滿足優化目標的可行解，體現為通過遺傳算法使初始種群通過進化后得到對于優化目標來說更加優秀的染色體，在此過程中就需要度量指標去計算染色體的優化程度。在遺傳算法的命名慣例中，適應度是群體中各個染色體優劣程度的量化指標。文中優化的目標是讓可行解中各個時段選擇的教室盡量一致或接近，其程度可以通過教學樓、樓層以及樓層中位置這三個參數計算。這個問題可以分解為逐次分析每個時段與后續時段在教室配置方面的一致或接近程度，并使用以下目標函數進行量化：

f(Ri,Ri+1)=0.5b(Ri,Ri+1)+0.3e(Ri,Ri+1)+ 0.2m(Ri,Ri+1)

其中，Ri和Ri+1分別表示前后兩個時段配置的教室；b(Ri,Ri+1)、e(Ri,Ri+1)和m(Ri,Ri+1)三個函數分別對前后兩個教室的所在教學樓、所在樓層以及樓層中位置的一致或接近程度進行量化計算，前面對應的系數可以實現按權重求和，系數對應的權重目前根據實際工作經驗對教學樓、所在樓層以及樓層中位置的重要性來確定，待以后研究中再進行優化改進。f(Ri,Ri+1)的值越小，表示前后兩個教室越接近，當f(Ri,Ri+1)的值為零時，前后兩個教室相同。而遺傳算法中染色體的適應度越大，該染色體對應可行解能更好地滿足優化目標，也就是說染色體表示各個時段配置的教室更加接近，所以需要將目標函數進行適當的轉換形成如下的適應度函數：

Fit(R1,R2,…,RN)=

該適應度函數的設計思路為依次將前N-1個時段的目標函數f累加，然后除以N-1求平均值，這樣針對上課時段總數不同的情況更加公平，最后通過乘以系數β(文中取0.05)進行指數比例變換。這樣當各個時段配置的教室越接近時，適應度越大，特別是在所有配置的教室相同時，適應度取得理想的最大值1，可以確定得到該種情況下教學資源配置的最優解。

2.4 遺傳算子的實現

2.4.1 選擇算子

從本質上講，達爾文的自然選擇學說是遺傳算法的理論基礎，其中選擇是在群體中選擇生命力強的個體產生新的群體的過程，為保留優良個體和種群多樣性提供驅動力。目前，遺傳算法中常用的選擇算子有輪盤賭選擇[13]、隨機競爭選擇、最佳保留選擇、穩態復制等。

文中使用最佳保留選擇作為選擇算子，具體操作為：將所有個體按適應度從大到小排序，然后按一定比例選出前面適應度較大的個體直接復制到下一代，不足種群規模的個體用隨機生成的方法補充。最佳保留選擇的實現簡單高效，既保留了進化過程中出現的優良個體并及時淘汰不良個體，又實現了個體的多樣性，避免了優化過程過早地陷入局部最優解。文中使用的最佳保留選擇比例因子為0.3。

2.4.2 交叉算子

模仿兩個染色體通過交配而重組形成新的個體的過程，遺傳算法使用交叉算子來產生新的染色體，是區別于其他進化算法的重要特征。交叉算子的設計包括交叉點定位和基因交換方式兩方面的內容。標準遺傳算法中的交叉算子是使用單點交叉[14]，文中實現也采用此交叉算子并在如何確定交叉點的位置方面進行了改進，不再簡單地直接使用隨機確定的交叉點位置，而是從交換后是否可以得到一個適應度更大的染色體來考慮，具體流程描述如下：

(1)對于隨機配對的兩個染色體a和b，按交叉概率Pc進行下面的交叉互換操作。

(2)隨機選擇一個位置作為參考點i。

(3)從參考點i開始向后搜索一個位置k使得交叉配對的兩個染色體a和b滿足條件：

(4)如果向后未找到符合條件的位置k，則從參考點i向前搜索符合步驟(3)中條件的位置k；

(5)如果向前還是未找到符合條件的位置k，則k=i；

(6)使用k為交叉點位置，交換交叉配對的兩個染色體的部分基因。

使用上述交叉算子，除了未找到符合條件的交叉點k的情況，都能夠使交叉互換后的一個染色體在位置k和k+1上對應的教室相同，從而進一步提高適應度，得到更加優良的個體。另外對于交叉互換后的另一個染色體也保持了原有的單點交叉方式，用于維持種群的多樣性。

2.4.3 變異算子

模仿生物遺傳和進化過程中某些基因發生變異的環節，遺傳算法使用變異算子在種群中產生出新的染色體，可以改善局部搜索能力和維持群體的多樣性。針對文中染色體采用十進制編碼的特點，為了更好地改善局部搜索能力以及防止搜索陷入局部次優解，設計的變異算子在借鑒現有常用變異算子的基礎上實現針對性的改進，流程如下：

(1)按變異概率Pm選取進行變異操作的染色體；

(2)隨機選擇一個位置作為變異位置；

(3)根據位置的奇偶性分別對變異位置的十進制編碼進行加1和減1，然后按編碼范圍取模，將所得結果替代原有十進制編碼。

2.5 終止條件的確定

在種群的進化過程中需要制定優化終止的條件，從而能在適當的時間內得到優化解，滿足計算性能方面的可行性。文中在常見的進化終止代數的基礎上，還考慮到可能出現所有配置教室相同的最優解，設計的適應度函數將會出現最大值1，因此制定了以下兩個條件：

(1)進化代數達到指定的最大進化代數；

(2)出現了適應度等于1的個體。

當這兩個條件其中之一滿足時，種群的進化過程終止，輸出種群中適應度最大的個體對應的優化解。

2.6 遺傳算法的實現

在上述幾個遺傳算法重要步驟的基礎上，進一步確定各個步驟的執行條件和順序，總結實現的遺傳算法流程，如圖2所示。

圖2 遺傳算法流程

3 實驗結果及分析

將針對文中應用環境進行改進的遺傳算法(DGA)和標準遺傳算法(SGA)進行實驗對比，試驗中SGA使用和DGA一樣的適應度函數，但是在染色體編碼方面使用二進制編碼，編碼方法將DGA初始種群中的十進制編碼轉換為二進制編碼，這樣可以使對比實驗在相同初始種群的條件下進行，更加公平。

SGA中選擇算子使用經典遺傳算法中常采用的輪盤賭選擇[13]，交叉算子和變異算子分別使用針對二進制編碼單點交叉和基本位變異。另外，DGA和SGA使用如下相同的參數：上課時段數為32，群體規模設為200，最大進化代數設為500，交叉概率Pc設為0.6，變異概率Pm設為0.05。

為了對比DGA與SGA在進化中的適應度變化情況，每進化5代就記錄種群中的最大適應度。考慮到遺傳算法的隨機性，DGA與SGA的對比實驗一共進行20次，取這20次數據的平均值作對比，結果如圖3所示。

從圖3中可以看出，DGA相對于SGA在進化過程中能產生更為優化的解，而且SGA相對較快地收斂到一個適應度較小的解，體現了SGA早熟的缺點。

為了對比DGA和SGA的用時，在上述實驗中每進化5代就記錄一個總共耗費時間，對比結果如圖4所示。

由圖4得知，DGA相對于SGA用時更少，主要原因在于針對文中應用環境，十進制編碼相對二進制編碼編解碼更加簡單高效，提高了計算效率，而且十進制編碼長度更短，這也降低了算法的空間復雜度。

圖3 DGA和SGA的適應度對比

圖4 DGA和SGA的用時對比

4 結束語

改進后的遺傳算法除了已在中國民航飛行學院教學工作中滿足了實際應用需求，還在對比試驗中相對于標準遺傳算法用時更少，而且得到的解更加優化。另外，量化教室配置優化程度的適應度函數可以在不同應用需求下進行改進，比如權重系數調整。這種根據應用環境特點改進遺傳算法的思路還可以針對其他類型的教學資源配置優化進行功能拓展。

[1]EvenS,ItaiA,ShamirA.Onthecomplexityoftimetableandmulti-commodityflowproblems[C]//ProcofIEEEsymposiumonfoundationsofcomputerscience.[s.l.]:IEEE,1975:184-193.

[2]TimB,CooperJ,KingstonH.Thecomplexityoftimetableconstructionproblems[C]//ProcofICPTAT’95.[s.l.]:[s.n.],1995.

[3]HollandJH.Adaptationinnatureandartificialsystems[M].Michigan:UniversityofMichiganPress,1975.

[4]LimkarS,KhalwadekarA,TekaleA,etal.Geneticalgorithm:paradigmshiftoveratraditionalapproachoftimetablescheduling[C]//Proceedingsofthe3rdinternationalconferenceonfrontiersofintelligentcomputing:theoryandapplications.[s.

l.]:Springer,2015:771-780.

[5]SbeityI,DboukM,KobeissiH.Combiningtheanalyticalhierarchyprocessandthegeneticalgorithmtosolvethetimetableproblem[J].EprintArxiv,2014,5(4):39-50.

[6] 郭俊恩,刁文廣.基于規則和遺傳算法的實驗室排課算法研究[J].河南大學學報:自然科學版,2014,44(3):355-359.

[7] 劉仁誠,馮秀蘭.基于改進遺傳算法的排課問題研究[J].科技通報,2013,29(5):160-163.

[8] 于 娟,尹積棟.面向排課系統的遺傳算法改進研究[J].太原理工大學學報,2012,43(5):572-574.

[9] 石 慧,彭曉紅,鄔志紅,等.求解多校區排課問題的基因對交叉遺傳算法[J].計算機工程與應用,2010,46(18):240-243.

[10] 李紅嬋,戶 剛,朱顥東.基于群體優勢遺傳算法的高校排課問題研究[J].計算機工程與應用,2011,47(10):233-236.

[11] 孫 彤,郭倩倩.基于新型免疫遺傳算法的高校排課仿真研究[J].計算機仿真,2012,29(2):386-391.

[12] 雷英杰,張善文.MATLAB遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社,2014.

[13] 祝勇仁,曹煥亞.應用遺傳算法求解排課問題[J].計算機應用與軟件,2007,24(12):130-132.

[14] 劉青鳳.遺傳算法在教學任務分配中的應用[J].制造業自動化,2010,32(10):203-205.

Application and Improvement of Genetic Algorithm for Optimization in Allocating Teaching Resources

YAN Hong1,2

(1.Civil Aviation Flight University of China,Guanghan 618307,China;2.National Key Laboratory of Fundamental Science on Synthetic Vision,Sichuan University,Chengdu 610064,China)

For temporarily added curriculum,the arrangement of teaching resources which usually has some specific requirements is different from that done before a semester begins.In the case of limited teaching resources,an improved genetic algorithm was proposed for optimizing the consistency and nearness of the classrooms allocated for temporary curriculum,with aim to avoid the inconvenience to teaching caused by frequent change of classrooms.Based on the requirement of the given application in this paper,a more efficient decimal encoding was developed.Correspondingly,a suitable fitness function was proposed to quantitatively calculate the consistency and nearness of the allocated classrooms.According to the characteristic of the chromosome encoding and the optimization goal,the algorithm selected existing genetic operators and improved them,especially the modified one-point crossover that attempts to enhance the fitness value and maintain the diversity of population.The experimental results show that the improved genetic algorithm,which has been successfully applied,can achieve more optimal solution within a shorter period of time when compared with the standard genetic algorithm.

resources allocation;genetic algorithm;decimal encoding;fitness function;crossover operator

2015-05-20

2015-08-21

時間：2016-01-

中國民用航空局民航科技創新引導資金(C2013041)

嚴 宏(1984-),男,講師,博士研究生,研究方向為最優化計算、機器學習。

TP18

A

1673-629X(2016)03-0130-05

10.3969/j.issn.1673-629X.2016.03.031