谷雅寧

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

關(guān)鍵詞 排課 混沌優(yōu)化 混沌遺傳算法

中圖分類號：G642 文獻標(biāo)識碼：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大學(xué)的John Holland教授最早提出了遺傳算法。它是一種解決NP完全問題的有效方法。De Jong首先將其用于函數(shù)優(yōu)化問題的研究中，并驗證了GA是一種解決優(yōu)化問題的有效的算法。Dorigo利用遺傳算法對高中課程進行排課，也驗證了GA是一種有效的排課算法。但是對于復(fù)雜的非線性系統(tǒng)優(yōu)化問題的求解，GA仍有許多缺陷，如進化過程的過早收斂；無法保證收斂到全局最優(yōu)解；群體中最好的染色體的丟失等。為了避免出現(xiàn)這些問題，本文把混沌引入到遺傳算法中（即混沌遺傳算法），利用混沌序列的內(nèi)在規(guī)律性，有效地引導(dǎo)交叉和變異操作。

1 建立數(shù)學(xué)模型

1.1 模型描述

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

1.2 模型中的約束條件

1.2.1 軟約束條件

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

1.2.2 硬約束條件

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

1.3 建立的數(shù)學(xué)模型

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

2 混沌遺傳算法

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

2.1 步驟

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

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

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

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

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

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

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

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

3 實驗結(jié)果及分析

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

3.1 實驗結(jié)果

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

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

參考文獻

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

[2] 王東升，曹磊.混沌、分形及其應(yīng)用[M].合肥：中國科學(xué)技術(shù)大學(xué)出版社，1995.

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