混沌遺傳算法在高校排課系統(tǒng)上的應(yīng)用

谷雅寧

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

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

中圖分類號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：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

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

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

1.1 模型描述

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

1.2 模型中的約束條件

1.2.1 軟約束條件

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

1.2.2 硬約束條件

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

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

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

2 混沌遺傳算法

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

2.1 步驟

（1）編碼。二進(jìn)制編碼不能很好地反映排課問題的特點(diǎn)，且交叉和變異較難操作。本文采用浮點(diǎn)數(shù)編碼，因?yàn)槠渥匀恢庇^、交叉和變異操作較容易、解碼操作也非常容易、節(jié)省時(shí)空開銷、計(jì)算效率高。

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

3.1 實(shí)驗(yàn)結(jié)果

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

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

參考文獻(xiàn)

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

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

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