混沌遺傳算法在高校排課系統上的應用

谷雅寧

摘 要 排課問題有很多制約因素，其目的是要找出各因素間的最佳對應關系，因此高校排課問題就是一個非線性組合優化問題。遺傳算法是解決非線性組合優化問題的有效智能算法，但是遺傳算法可能會陷入局部最優的局面，并且收斂速度比較慢。為了彌補這些缺陷，本文利用混沌的遍歷性、隨機性、內在規律性和遺傳算法的反演性，采用混沌遺傳算法來解決高校排課問題。實驗結果表明：當運行趨于穩定狀態時，該混沌遺傳算法比遺傳算法收斂速度快、能更有效地求得全局最優解。

關鍵詞 排課 混沌優化 混沌遺傳算法

中圖分類號：G642 文獻標識碼：A DOI：10.16400/j.cnki.kjdks.2016.12.007

Abstract There are many constraints in the course of scheduling， the purpose is to find out the best correspondence between the various factors， so the problem is a nonlinear combinatorial optimization problem. Genetic algorithm is an effective intelligent algorithm to solve nonlinear combinatorial optimization problems， but the genetic algorithm may fall into the local optimal situation， and the convergence speed is relatively slow. In order to make up these defects， this paper uses the chaos of the ergodic， random， intrinsic regularity and genetic algorithm inversion， using chaos genetic algorithm to solve the problem of college course arrangement. The experimental results show that the chaotic genetic algorithm can get the global optimal solution faster than the genetic algorithm when the operation is stable.

Keywords course scheduling； chaos optimization； chaos genetic algorithm

美國Michigan大學的John Holland教授最早提出了遺傳算法。它是一種解決NP完全問題的有效方法。De Jong首先將其用于函數優化問題的研究中，并驗證了GA是一種解決優化問題的有效的算法。Dorigo利用遺傳算法對高中課程進行排課，也驗證了GA是一種有效的排課算法。但是對于復雜的非線性系統優化問題的求解，GA仍有許多缺陷，如進化過程的過早收斂；無法保證收斂到全局最優解；群體中最好的染色體的丟失等。為了避免出現這些問題，本文把混沌引入到遺傳算法中（即混沌遺傳算法），利用混沌序列的內在規律性，有效地引導交叉和變異操作。

1 建立數學模型

1.1 模型描述

假設學校有N個班，N={ni|i=1，2，3，…，N}，各個班級人數為{i|=1，2，3，…，N}；班級集合有T個教師，T={t1，t2，…，tT}；課程總數為S，S={s1，s2，…，sS；教室個數為R，R={r1，r2，…，rR}，各教室可容納人數為{x1，x2，…，xR}；時間段數為M個，M={m1，m2，…，mR}。

1.2 模型中的約束條件

1.2.1 軟約束條件

（1）滿足教師所提出的上課時間和地點的特殊要求。（2）多學時課程的周安排要錯開，一般對于每周多學時的課程應該能夠盡量將其隔1天以上安排才能保證有較好的教學效果。（3）在排課過程中較難的課程最大程度地安排在授課效果較好的節次中，比如上午上課效果要比下午效果好。

1.2.2 硬約束條件

（1）同一時間，同一班級不能同時有兩門以上的課程。（2）同一時間，同一個教師不能同時有兩門以上的課程。（3）同一時間，同一個教室不能同時有兩門以上的課程。（4）分配的教室可容納人數應該大于等于上課的班級的學生人數。

1.3 建立的數學模型

排課問題的數學模型是一個組合優化問題，其中f為目標函數。目標函數值為4時最為理想，從此可看出排課問題是一個求最大值問題。其中R1表示老師對課程有沒有特殊要求，若有則R1=1，否則R1=0。R2表示周學時的大小，若周學時大則R2=1，否則R2=0。R3表示課程的級別，若為必修課則R3=1，否則R3=0。R4表示可是課程難度級別，若課程難度大的安排在上午或課程難度小的安排在下午則R4=1，否則R4=0。Ki表示以上的權重，其中由以上各自的優先級可令K1≥K2≥K3≥K4≥0，Ki=1。教師tt在時間mm、教室rr中給班級nn講授課程ss，表示nnttssrrmm=1，反之為nnttssrrmm=0。

2 混沌遺傳算法

混沌遺傳算法是在遺傳算法的過程中加一混沌擾動，從而提高了收斂速度，找到全局最優解。

2.1 步驟

（1）編碼。二進制編碼不能很好地反映排課問題的特點，且交叉和變異較難操作。本文采用浮點數編碼，因為其自然直觀、交叉和變異操作較容易、解碼操作也非常容易、節省時空開銷、計算效率高。

（2）生成初始群體。混沌遺傳算法利用混沌的遍歷性進行粗粒度全局搜索獲得比隨機搜索有更好的效果，從而提高初始種群個體的質量和計算效率。

（3）確定個體適應度函數。確定個體適應度真正目的是確定個體在群體中的優劣。適應度越大個體越好，反之適應度越小則個體越差。根據適應度的大小對個體進行選擇，以保證適應性能好的個體有更多的機會繁衍后代，使優良特性得以遺傳。因此適應度函數設定的好壞直接影響到混沌遺傳算法的收斂速度和能否找到最優解。由于排課問題的軟約束條件有多個，因此本文采用多目標化的個體適應度函數。

（4）確定交叉概率Pc，并執行交叉操作。在混沌遺傳算法的整個進化過程中交叉操作要進行成千上萬次。遺傳算法中的交叉算子主要采用單點、對稱、大片斷基因保留、小片斷基因保序的交叉方法。而在混沌遺傳算法中， 利用混沌序列來控制交叉操作，從而提高交叉的效率。①混沌序列控制交叉頻率：交叉概率在很大程度上影響著算法的收斂速度和解的質量。混沌遺傳算法利用混沌序列對目標基因進行混沌擾動，從而加快了算法的收斂速度和解的質量。其中0.25≤Pc≤1.0比較理想。②混沌序列控制交叉點位置的選擇：由產生的一個混沌序列映射到該目標個體的基因空間，則在相應的位置進行交叉操作。

（5）確定變異概率Pm，并執行變異操作。在混沌遺傳算法中，產生的混沌序列來控制變異算子。從而提高變異的效率。①混沌序列控制變異頻率：混沌遺傳算法利用混沌序列對目標基因進行混沌擾動，從而提高了解的質量。其中0.001≤Pm≤0.1比較理想。②混沌序列控制變異點位置的選擇：由產生的一個混沌序列映射到該目標個體的基因空間，則在相應的位置進行變異操作。

（6）適應度較低個體的混沌優化。混沌遺傳算法利用混沌進行細粒度局部搜索，提高解的精度。對當前代群體中適應度較小的90%的基因加混沌擾動。這種變異可能產生比剩下10%較高適應度基因更好的基因，從而有效地避免單純的遺傳算法陷入局部最優解與早熟的問題。

（7）判斷該算法收斂準則是否滿足終止條件，若滿足則輸出搜索結果，否則返回（4），直到滿足終止條件。

2.2 混沌遺傳算法流程圖 （圖1）

3 實驗結果及分析

為了驗證本文算法在排課問題上優先于遺傳算法。選擇玉林師范學院2015-2016學年上學期排課任務為測試范例，其中種群數1000。對算法性能的考察指標包括平均運行時間、出現較優解的次數。

3.1 實驗結果

基于兩種算法的高校排課方案，迭代次數分別設定為50、100、150、200、250、270、290，每次迭代50次進行測試，運行并記錄結果。如圖2、圖3所示。3.2 實驗結果分析

我們從兩個方面來分析混沌遺傳算法的有效性。首先從出現較優解的次數方面，隨著迭代次數的增加，混沌遺傳算法和遺傳算法出現較優解的次數都趨于穩定，但是當迭代次數一定時，混沌遺傳算法出現較優解的次數明顯比遺傳算法出現較優解的次數多出2倍。其次從收斂速度方面，實驗表明，出現較優解的次數趨于穩定時，混沌遺傳算法收斂速度比遺傳算法的收斂速度快3倍。以上分析表明，本文采用的混沌遺傳算法具有收斂速度快，易趨于全局最優解等特點，故該算法應用到排課問題上是有效可行的。

參考文獻

[1] 李兵，蔣慰孫.混沌優化方法及其應用[J].控制理論與應用，1997.14（4）：613-615.

[2] 王東升，曹磊.混沌、分形及其應用[M].合肥：中國科學技術大學出版社，1995.

[3] 鄒恩，李翔飛，陳建國.混沌控制及其優化應用[M].長沙：國防科技大學出版社，2002.