采用空間編碼與正弦選擇算子遺傳算法求解排課問題?

錢海軍

（珠海城市職業(yè)技術(shù)學(xué)院 珠海 519000）

采用空間編碼與正弦選擇算子遺傳算法求解排課問題?

錢海軍

（珠海城市職業(yè)技術(shù)學(xué)院 珠海 519000）

遺傳算法是求解多約束、多目標(biāo)組合優(yōu)化問題的有效算法。經(jīng)典遺傳算法具有早熟特性，可以直接導(dǎo)致算法陷入局部最優(yōu)解。為了提高算法的全局搜索性能，以遺傳算法的染色體編碼設(shè)計和選擇算子設(shè)計兩個方面為切人點(diǎn)，提出基于空間編碼與正弦選擇算子遺傳算法（SCSS）。仿真實(shí)驗(yàn)證明，SCSS遺傳算法求解開放教育排課問題能夠滿足多重約束條件，為有效實(shí)現(xiàn)排課問題的智能求解提供實(shí)用性的數(shù)學(xué)方法。改進(jìn)后的遺傳算法能夠快速收斂得到問題的全局最優(yōu)解，算法全局搜索性能明顯增強(qiáng)。

遺傳算法；多約束；空間編碼；正弦選擇算子；開放教育；全局最優(yōu)解

1 引言

由美國Michigan大學(xué)Holland教授于1975年首次提出的遺傳算法［1］是求解最優(yōu)化問題的經(jīng)典方法之一［2］。該算法對于非線性、大規(guī)模、單峰函數(shù)、多峰多態(tài)函數(shù)的求解都可以獲得較好的結(jié)果。遺傳算法是一種模擬自然選擇、物種進(jìn)化的全局優(yōu)化搜索技術(shù)。其優(yōu)點(diǎn)是采用種群搜索技術(shù)在解空間進(jìn)行全局搜索以獲得全局最優(yōu)解。遺傳算法通過對種群隨機(jī)產(chǎn)生的一組個體進(jìn)行選擇、交叉、變異三種遺傳算子實(shí)現(xiàn)種群進(jìn)化。選擇算子是根據(jù)個體適應(yīng)度值來確定個體進(jìn)行交叉和變異操作，適應(yīng)度值高個體的則被選擇進(jìn)行迭代進(jìn)化，反之被淘汰；借助生物種群遺傳信息的概念，交叉算子通過染色體編碼在整個解空間進(jìn)行有效搜索，將選擇的父代個體進(jìn)行基因重組，交換兩個個體的基因座，從而產(chǎn)生大量的新個體。交叉的過程能夠增強(qiáng)最優(yōu)個體的出現(xiàn)幾率，提高全局搜索能力的同時降低對有效模式的破壞概率。變異算子是通過模擬生物遺傳和進(jìn)化過程中的變異環(huán)節(jié)實(shí)現(xiàn)對個體的變異，這個過程是新個體產(chǎn)生的重要原因之一［3］。變異算子在交叉算子的基礎(chǔ)上對產(chǎn)生的新個體內(nèi)部基因進(jìn)行微調(diào)，維持種群的多樣性［4］，使算法還具有一定的局部搜索能力。

2 算法改進(jìn)

實(shí)踐證明，經(jīng)過一定的迭代之后，種群的多樣性將有所降低，遺傳算法出現(xiàn)過早收斂［5］，較容易產(chǎn)生局部最優(yōu)解。國內(nèi)外學(xué)者針對算法內(nèi)部的每個環(huán)節(jié)進(jìn)行了大量研究，并提出了諸多有效地改進(jìn)方法［6～8］。本文在借鑒上述研究成果的基礎(chǔ)上，從染色體編碼方式與選擇算子改進(jìn)兩個方向?yàn)榍腥朦c(diǎn)，提出一種改進(jìn)的遺傳算法。

2.1 三維空間編碼設(shè)計

通過分析，經(jīng)典的遺傳算法采用二進(jìn)制染色體編碼方式，在變異操作過程中，二進(jìn)制編碼的各個基因座權(quán)重不同，導(dǎo)致變異的基因座越靠向高位，編碼串的改變量越大，則變異后越容易丟失最優(yōu)個體［9］。本文基于經(jīng)典遺傳算法的原理，結(jié)合開放大學(xué)遠(yuǎn)程開放教育教學(xué)特征與排課問題的數(shù)學(xué)模型，提出基于三維空間的遺傳算法染色體編碼方案。

2.1.1 排課問題數(shù)學(xué)建模［10］

1）根據(jù)開放教育教學(xué)特征，建立排課問題數(shù)學(xué)模型，假設(shè)：

教師集合 Professors=｛J1，J2，…，Jm，…，JM｝，其中，1≤m≤M ；

教室集合 Classrooms=｛R1，R2，…，Rp，…，RP｝，其中，1≤p≤P；教室可容納人數(shù)Y；

課程集合 Courses=｛C1，C2，…，Cs，…，CS｝，其中，1≤s≤S；

時間集合 Times=｛T1，T2，…，Tq，…，TQ｝，其中，1≤q≤Q；

班級集合 Stugroups=｛G1，G2，…，Gn，…，GN｝，其中，1≤n≤N ；班級人數(shù)X=｛x1，x2，…，xn，…，xN｝；

2）排課問題屬于一種非線性、資源時空組合問題，建立硬約束條件［11］，如表1所示。

表1 遠(yuǎn)程開放教育排課問題硬約束條件

3）建立排課問題軟約束條件［11］。

S1：教學(xué)效果較好的時間段安排較重要的課程，可以有效提高教學(xué)質(zhì)量。開放教育教學(xué)安排的一般在周一至周五晚上，周六、周日全天。由于成人參與學(xué)習(xí)的特點(diǎn)，可以認(rèn)為到課率較高的時間，教學(xué)效果也較好。數(shù)據(jù)分析可知，除周末外，教學(xué)質(zhì)量較好的時間序列為：星期一、星期四、星期二、星期三、星期五。

假設(shè) αi(i=1，2，3，4，5)表示授課時間段的優(yōu)先級；數(shù)學(xué)描述如表2所示。

表2 S1軟約束條件變量

假設(shè) βj(j=1，2，3，4，5，6)表示課程重要程度，其中：“1”表示通識課，“2”表示專業(yè)拓展課，“3”表示綜合實(shí)踐、“4”表示專業(yè)課，“5”表示專業(yè)基礎(chǔ)課，“6”表示公共基礎(chǔ)課。則優(yōu)化目標(biāo)為

S2：滿足部分教師提出的課程安排的要求。假設(shè)職稱的級別系數(shù)為 εi(i=1，2，3)，“1”表示高職職稱，”2”表示中級職稱，”3”表示初級職稱；教師在規(guī)定時間段上課的意愿程度系數(shù)為δj(j=0，1，2)，其中“2”表示愿意，“1”表示可以接受，“0”表示不愿意；則優(yōu)化目標(biāo)為

S3：多學(xué)時課程授課時間應(yīng)保證一定的間隔時間。假設(shè)一門課程的授課時間間隔為i天的教學(xué)效果系數(shù)為 λi(i=1，2，3，4，5)，設(shè)定1，2，3，4，5天的系數(shù)值分別為1，4，5，3，2，βj為課程的權(quán)重。則優(yōu)化目標(biāo)為

S4：同一課表，班級課程安排盡量保證均勻分布。某班級周課時分布均勻程度為

其中，ed表示班級GN在第d周上課的課時數(shù)，N表示班級的總數(shù)，則優(yōu)化目標(biāo)為

S5：教室利用率最大化，即根據(jù)班級學(xué)生的人數(shù)分配教室。假設(shè)班級人數(shù)XN與教室可容納的學(xué)生人數(shù)為YS的比值等于1，則教室利用率越高。約束條件優(yōu)化目標(biāo)為

2.1.2 染色體編碼設(shè)計

開放教育專業(yè)規(guī)劃能夠確定排課問題數(shù)學(xué)模型中的教師集合Professors、課程集合Courses與班級集合Stugroups。作為已知參數(shù)，三個集合可以被組合成一個課程元祖，用 CPS（Courses、Professors、Stugroups）描述。如圖1所示，空間三維坐標(biāo)體系內(nèi)，X軸為T（時間片），坐標(biāo)值對應(yīng)一周內(nèi)11個教學(xué)時間段，即 X1～X11；Y軸為 R（教室），坐標(biāo)值對應(yīng)學(xué)校全部可用的教室總數(shù)R，即Y1～YR；Z軸代表一個課程元組CPS。

圖1 三維空間染色體編碼方案

從圖1可以看出，由空間三維坐標(biāo)構(gòu)成的黑色小立方體可以確定一個課程基因，該課程基因表示在某授課時間片TQ，某班級GN，在教室RP安排課程CS的授課事件。全部課程基因組成一條染色體，即表示一個課程表的排課方案。在時間片TQ和教室RP確定的條件下，課程基因（授課事件）數(shù)為

為了較直觀地描述該三維空間染色體編碼方案，將課程基因總數(shù)的求解映射為一個三維數(shù)組Timetable[][][]=｛(JM，GN，CS)，TQ，RP｝，圖形化描述該數(shù)據(jù)結(jié)構(gòu)如圖2所示。

圖2 圖形化編碼方案

具體的染色體編碼設(shè)計采用十進(jìn)制編碼。三位數(shù)組中的各數(shù)組元素按照表5、表6所示的時間模式編碼表、教室編碼表和班級編碼表，分別映射成為十進(jìn)制數(shù)表示相應(yīng)的排課信息。

1）時間模式編碼表及含義

表5 時間模式編碼表

模式編碼表中的星期一至星期日分別用十進(jìn)制數(shù)1～7表示；每天有3個教學(xué)時間段，分別用1～3表示?？紤]到開放教育教學(xué)安排的特殊性及多學(xué)時課程的教學(xué)特點(diǎn)，實(shí)際時間段的編碼再添加4位數(shù)字位，共6位十進(jìn)制數(shù)表示某課程的教學(xué)時間段，并能夠從該編碼中直接獲取該課程的學(xué)時數(shù)。例如：編碼430000表示該課程在每周四晚上上課；編碼235300表示該課程每周二晚上和周五晚上上課；編碼136273表示該課程每周一晚上、周六下午和周日晚上上課。

2）教室編碼表及含義

表6 教室編碼表

教室編碼第1位用來區(qū)分教室類型，“0”表示普通教室，“1”表示多媒體機(jī)房，“2”表示專業(yè)實(shí)訓(xùn)室；第2～3位為教室按照樓層的流水號。因?yàn)閷W(xué)校僅有一幢教學(xué)樓，所以教室編碼不涉及跨區(qū)域教室。

3）班級編碼

開放教育實(shí)行春、秋兩季本、?？仆瑫r招生。按照學(xué)校開放教育的實(shí)際情況，以專業(yè)作為劃分班級的最基本單位。班級編碼由“入學(xué)年度”、“專業(yè)代碼”、“區(qū)分位”三個標(biāo)識位組合而成。例如：編碼201520111表示2015級工商企業(yè)管理?？?；具體各專業(yè)代碼可提前進(jìn)行預(yù)編碼處理。

2.2 適應(yīng)度函數(shù)設(shè)計

適應(yīng)度函數(shù)應(yīng)滿足規(guī)范性、單值、連續(xù)，計算簡單，通用性較好等特性。分析可知，適應(yīng)度函數(shù)值是非負(fù)的，任何情況下越大越好。目標(biāo)函數(shù)O(x)與適應(yīng)度函數(shù)值Fit(x)之間的關(guān)系存在映射問題，即當(dāng)求O(x)最大值點(diǎn)時，O(x)與Fit(x)的變化方向相同；當(dāng)求O(x)最小值點(diǎn)時，O(x)與Fit(x)的變化方向相反，此時目標(biāo)函數(shù)值越小，適應(yīng)度函數(shù)值則越大。排課問題的求解依賴于多目標(biāo)優(yōu)化，即滿足多個硬約束條件與盡量多的軟約束條件，達(dá)到資源分配的最優(yōu)化。本文提出加權(quán)約束適應(yīng)度函數(shù)模型，即：

2.3 初始化種群

算法初始化為后續(xù)選擇算子、交叉算子、變異算子提供基礎(chǔ)染色體群。經(jīng)典的遺傳算法通過隨機(jī)搜索的方式［12］產(chǎn)生初始種群。這些隨機(jī)產(chǎn)生的初始種群在可行解空間上會出現(xiàn)較均勻的散步與較集中的聚集兩種極端情況。

1）隨機(jī)搜索法

本文通過一維多峰函數(shù)對初始種群的隨機(jī)搜索方式進(jìn)行測試，進(jìn)一步說明這種由隨機(jī)搜索方式產(chǎn)生的初始化種群對遺傳算法的影響。

例如一維多峰函數(shù)

在解的表示方式、初始種群規(guī)模、算子、算法終止條件等算法控制參數(shù)相同的情況下求解該函數(shù)的最大值，以此觀察隨機(jī)搜索產(chǎn)生的初始化種群對遺傳算法的計算結(jié)果的影響。通過Matlab求解得到圖3計算結(jié)果。

圖3 一維多峰函數(shù)測試結(jié)果

圖3 （a）、（b）分別為采用同一隨機(jī)搜索方式產(chǎn)生經(jīng)過20次迭代產(chǎn)生初始化種群的遺傳算法程序計算結(jié)果。圖3（b）顯示，經(jīng)過種群迭代，隨機(jī)搜索方式產(chǎn)生的個體呈現(xiàn)小范圍集聚，且略微偏向左側(cè)，導(dǎo)致算法計算結(jié)果較早收斂，形成局部最優(yōu)。分析可知，在遺傳算法的遺傳代數(shù)與算子一定的情況下隨機(jī)搜索方式產(chǎn)生的初始種群會引起遺傳算法的不穩(wěn)定的計算結(jié)果。

2）可行解空間網(wǎng)格劃分法

隨機(jī)搜索法產(chǎn)生的初始化種群在均勻散步的狀態(tài)下具有較高的多樣性，經(jīng)過遺傳算子操作收斂于全局最優(yōu)解可能性較大；但同時，隨機(jī)搜索產(chǎn)生的分布集中的初始種群會較集中地落在某些子空間中，從而導(dǎo)致遺傳操作收斂到子空間的局部最優(yōu)解，算法搜索產(chǎn)生停滯，搜索空間無法擴(kuò)大，算法無法收斂到最優(yōu)解［11］。由于隨機(jī)搜索法產(chǎn)生的種群適應(yīng)度較低，且具有不穩(wěn)定性質(zhì)。為了能夠提高初始種群的群體適應(yīng)度，本文運(yùn)用空間網(wǎng)格劃分法產(chǎn)生初始化種群。具體步驟如下：

步驟1：將目標(biāo)空間進(jìn)行網(wǎng)格化劃分。參考點(diǎn)落入可行解空間的所有網(wǎng)格，且將每個網(wǎng)格作為一個參考對象。根據(jù)種群的規(guī)?？刂茀⒖键c(diǎn)的數(shù)量，通過參考點(diǎn)的組合求解多目標(biāo)優(yōu)化的可行解。

步驟2：在可行解空間，將m維向量構(gòu)成的目標(biāo)空間劃分為k等份。這樣得到m*k個目標(biāo)子空間，k的值根據(jù)計算精度要求與可行解空間的大小進(jìn)行設(shè)定。m*k個目標(biāo)子空間對應(yīng)k?m可行解子空間，產(chǎn)生k?m個網(wǎng)格。

步驟3：將每個網(wǎng)格映射為個體目標(biāo)函數(shù)值，可以得到初始種群數(shù)為k?m。

步驟4：設(shè)某個體目標(biāo)函數(shù)的解空間為[Xmin，Xmax]，依二分法求均值的思路，在解空間搜索i個點(diǎn)，則目標(biāo)函數(shù)值為

通過解空間網(wǎng)格化劃分產(chǎn)生的初始點(diǎn)，包括全局最優(yōu)點(diǎn)與局部最優(yōu)點(diǎn)必然全部落在網(wǎng)格節(jié)點(diǎn)或者節(jié)點(diǎn)之間，種群進(jìn)化搜索過程中，算法能夠被較容易地搜索到最優(yōu)點(diǎn)。這種方法產(chǎn)生的初始種群包含最優(yōu)解組合的概率明顯增強(qiáng)，且技術(shù)性地避免了相似個體的被選取，以減少種群數(shù)量。該方法與算法的選擇、交叉、變異算子結(jié)合，可以提高算法搜索效率與收斂于全局最優(yōu)解的概率。

2.4 選擇、交叉、變異操作

經(jīng)典遺傳算法的選擇策略是基于個體適應(yīng)度的比例擇優(yōu)選擇策略。設(shè)計的選擇算子不同將導(dǎo)致個體不同的選擇概率，從而產(chǎn)生的種群亦有不同。傳統(tǒng)選擇排序算子的概率值依據(jù)經(jīng)驗(yàn)設(shè)定，適應(yīng)度概率較高的個體會以較高的概率進(jìn)化到下一代種群當(dāng)中，但同樣也存在被淘汰的情況；輪盤選擇方法則無法處理個體適應(yīng)度值非負(fù)數(shù)的情況，通用性較差。而在排序選擇方法中，概率分布無規(guī)律可循，容易引起局部收斂［13］，造成算法搜索緩慢的問題。

2.4.1 正弦選擇算子

本文提出一種基于最優(yōu)個體保留策略的正弦函數(shù)選擇算子，可以有效提高算法的搜索精度。改進(jìn)的選擇算子選擇策略分兩步進(jìn)行。

步驟1：基于個體適應(yīng)度值，將當(dāng)前代種群中適應(yīng)度最高的個體直接復(fù)制到下一代。假設(shè)第k代最優(yōu)個體為 Amax(k)，第 k+1代最劣個體Amin(k+1)。保留Amax(k)，并直接替換Amin(k+1)，Amax(k)不參與交叉、變異遺傳操作。第k+1代的種群數(shù)為

SA(k+1)=SA(k+1)+Amax(k)-Amin(k+1)

步驟2：對當(dāng)前代（第k代）種群的其它個體采用改進(jìn)的正弦函數(shù)選擇算子進(jìn)行選擇與復(fù)制操作 。 根 據(jù) 正 弦 函 數(shù) f(θi)=sin(θi) 的 特 性 ，當(dāng)θ ∈[0，π]，f(θ)在 [0，1]區(qū)間呈現(xiàn)單調(diào)遞增。假設(shè)種群個體的適應(yīng)值為 f1，f2，…，fn，fi∈[fmin，fmax]，i=1，2，...n 。 將 fi∈[fmin，fmax] 等 比 例 映 射 到θ∈[0，]，則可以設(shè)計選擇概率：

μ為比例調(diào)節(jié)系數(shù)，作用是保證選擇概率在［0，1］區(qū)間內(nèi)均勻分布，降低產(chǎn)生偏差的幾率。

步驟3：結(jié)合輪盤賭選擇方法進(jìn)行選擇運(yùn)算。

2.4.2 自適應(yīng)交叉算子［14］

經(jīng)典遺傳算法會由于進(jìn)化過程中交叉概率Pc和變異概率Pm保持不變導(dǎo)致算法性能的下降。依據(jù)經(jīng)驗(yàn)知識與算法規(guī)則可知，在種群迭代初期，設(shè)置較大的交叉概率能夠明顯增強(qiáng)算法的搜索能力；在種群迭代后期，交叉概率設(shè)定小一點(diǎn)則可以有效避免優(yōu)良基因被淘汰，從而加快算法的收斂［15］。為了提高算法的性能，降低最優(yōu)個體（適應(yīng)度高）被淘汰的幾率，本文應(yīng)用最優(yōu)個體保留策略，最優(yōu)個體被保留，不參與交叉和變異操作，剩余個體參與交叉和變異操作，防止陷于局部最優(yōu)。采用自適應(yīng)交叉概率為

其中，C1為調(diào)解系數(shù)，其值為（0，1）的隨機(jī)數(shù)，通過在計算機(jī)程序中設(shè)置rand隨機(jī)函數(shù)產(chǎn)生；C2為（0，1）之間的常量；fmax表示種群當(dāng)前代t中的最優(yōu)個體適應(yīng)度函數(shù)值；favg表示t中個體的平均適應(yīng)度函數(shù)值；fc表示經(jīng)過交叉操作的個體中適應(yīng)度函數(shù)值的最大值。

2.4.3 自適應(yīng)變異算子［14］

種群個體具備的基因差異性對于整個種群的進(jìn)化的起著至關(guān)重要的作用。優(yōu)良個體之間的基因基因重組可以保證進(jìn)化過程中種群的優(yōu)良基因被保留下來，基因較差的個體則會被淘汰，這就是優(yōu)勝劣汰的選擇過程?？梢詫ΨN群中不同個體設(shè)定不同的變異概率。對于種群中的優(yōu)良個體，設(shè)定較小的變異概率，從而保證優(yōu)良個體通過交叉操作后能夠，優(yōu)良基因被保存和累積；對于種群中的較差個體，設(shè)定較大的變異概率，通過交叉操作增強(qiáng)種群的搜索能力［16］。基于上述分析，算法的變異操作采用自適應(yīng)變異概率以提高種群的多樣性，增強(qiáng)算法維持搜索的能力。在種群迭代初期，自適應(yīng)概率能夠在個體性能較差的條件下，造成較大的擾動來擴(kuò)大算法的解空間；隨著迭代次數(shù)的增加，自適應(yīng)變異概率能夠逐步減少成為一個0～1之間的常量，以保證算法的平滑收斂。采用自適應(yīng)變異概率為

其中，M1為調(diào)解系數(shù)，其值為（0，1）的隨機(jī)數(shù)，通過在計算機(jī)程序中設(shè)置rand隨機(jī)函數(shù)產(chǎn)生；M2為（0，1）之間的常量；fmax、favg含義同上；fm表示經(jīng)過交叉操作的個體中適應(yīng)度函數(shù)值的最大值。

3 仿真實(shí)驗(yàn)

課程編排可以歸結(jié)為教學(xué)資源分配的數(shù)學(xué)問題［17～18］。排課問題被證明是一種NP問題［19］。遺傳算法的整體搜索策略與求解優(yōu)化設(shè)計對求解問題類型具有較強(qiáng)魯棒性，即算法本身的搜索策略與求解優(yōu)化技術(shù)不依賴于具體求解問題所涉及的領(lǐng)域知識［20］，僅在算法進(jìn)化過程中，對問題的目標(biāo)函數(shù)求解方向與適應(yīng)度函數(shù)有所影響。本文以某開放大學(xué)2015年秋季的排課數(shù)據(jù)作為算法訓(xùn)練樣本求解排課問題。數(shù)據(jù)集如表7所示。

表7 訓(xùn)練數(shù)據(jù)集

3.1 Matlab仿真參數(shù)設(shè)置

本文利用Matlab遺傳算法工具箱，編寫仿真程序?qū)Ρ?數(shù)據(jù)集進(jìn)行訓(xùn)練。在提出的改進(jìn)遺傳算法中，交叉概率Pc與變異概率Pm具有自適應(yīng)性，故無需設(shè)置。其他參數(shù)設(shè)置如下：

1）仿真實(shí)驗(yàn)中，種群規(guī)模過小會導(dǎo)致目標(biāo)函數(shù)值產(chǎn)生較大的波動；種群過大則可能造成收斂時間較多，消耗資源。NIND表示種群規(guī)模，本文設(shè)置為200。

2）MAXGEN表示最大遺傳代數(shù)，該參數(shù)過大會導(dǎo)致過早收斂，無法搜索到全局最優(yōu)解。根據(jù)訓(xùn)練樣本的數(shù)量，本文設(shè)置為800。

3.2 Matlab仿真結(jié)果

算法仿真實(shí)驗(yàn)中，利用本文提出的空間編碼與正弦選擇算子遺傳算法（SCSS）與Pillay N等［21］提出的改進(jìn)遺傳算法進(jìn)行適應(yīng)度函數(shù)值對比。

圖4 兩種遺傳算法適應(yīng)度函數(shù)值對比

實(shí)驗(yàn)中，種群每迭代50代就記錄一次種群適應(yīng)度函數(shù)值，共記錄15次。通過計算15次記錄的最佳適應(yīng)度函數(shù)值的平均值，得出圖4所示的實(shí)驗(yàn)結(jié)果。從結(jié)果可以看出，本文提出的SCSS遺傳算法能夠較好地解決開放教育排課問題。

4 結(jié)語

本文提出的基于空間編碼和正弦選擇算子遺傳算法—SCSS，從算法性能和早熟收斂兩個方面對經(jīng)典遺傳算法進(jìn)行了改進(jìn)?；谌S空間染色體編碼可以有效增強(qiáng)種群多樣性。在選擇算子的非線性變換中加入正弦三角函數(shù)，改善了算法的收斂性能。通過采用SCSS仿真求解開放教育排課問題，進(jìn)一步驗(yàn)證了SSCS遺傳算法具有較好地全局收斂性。

［1］J.H.Holland.Adaptation in natural and artificial systems［M］.Ann Arbor：The University of Michigan Press，1975.08-30.

［2］De Jong，Kenneth Alan.An analysis of the behavior of a class of genetic adaptive systems［D］.Michigan：University of Michigan，1975.05-35.

［3］周明，孫樹棟，等.遺傳算法原理及應(yīng)用［M］.北京：國防工業(yè)出版社，1999.11-13.ZHOU Ming，SUN Shudong，et al.Genetic algorithm：Theory and Application［M］.Beijing：National Defence Industry Press，1999.11-13.

［4］Muehlenbein H.How genetic algorithms really work：mutation and hill climbing［C］//In Proc，and Workshop Parallel Problem Solving from Nature，1992：15-25.

［5］劉紅，韋穗.遺傳算子的分析［J］.計算機(jī)技術(shù)與發(fā)展，2006，16（10）：80-82.LIU Hong，WEI Hui.Analysis on Genetic Operators Computer［J］.Technology and Development，2006，16（10）：80-82.

［6］Ichikawa Y，Ishii Y.Retaining diversity of genetic algorithms for multivariable optimization and neural network learning［C］//Proc of IEEE international conference on neural net-work.［s.l.］：［s.n.］，1993：1110-1114.

［7］Srinivas M，Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithm［J］.IEEE trans on systems，man and cybernetics，1994，24（4）：656-667.

［8］楊啟文，蔣靜坪，張國宏.遺傳算法優(yōu)化速度的改進(jìn)［J］.軟件學(xué)報，2001，12（2）：270-275.YANG Qiwen，JIANG Jingping，ZHANG GUOhong.Improved Optimization Speed for Genetic Algorithms［J］.Journal of Software，2001，12（2）：270-275.

［9］鄭生榮，賴家美，劉國亮，等.一種改進(jìn)的實(shí)數(shù)編碼混合遺傳算法［J］.計算機(jī)應(yīng)用，2006，26（8）：1959-1962.ZHENG Shengrong，LAI Jiamei，LIU Guoliang，et al.Improved real coded hybrid genetic algorithm［J］.Computer Applications，2006，26（8）：1959-1962.

［10］錢海軍.開放教育排課問題約束分析與數(shù)學(xué)建模［J］.軟件工程，2016，19（9）：27-29.QIAN Haijun.Constraint Analysis and Mathematical Modeling in the Open Education Timetabling［J］.Software Engineering，2016，19（9）：27-29.

［11］Shi Juan.Research on application of IGA（Immune Genetic Algorithm）to the solution of course-timetabling problem［C］//Proceedings of 2009 4th International Conference on Computer Science and Education，Nanning，China，2009：1105-1109.

［12］Guyon O，Lemaire P，Pinson*.Cut Generation for an Inte-grated Employee Timetabling and Production Scheduling Problem［J］.European Journal of Operational Research，2010，201（2）：557-567.

［13］Pandey H M，Chaudhary A，Mehrotra D.A comparative Review of Approaches to Prevent Premature Convergence in GA［J］.Applied Soft Computing，2001，24：1047-1077.

［14］朱灝東，李紅嬋.采用三維小生境遺傳算法求解高校排課問題［J］.計算機(jī)工程與應(yīng)用，2011，47（34）：242-245.ZHU Haodong，LI Hongchan.Three-dimensional niche GA used to solve University Timetabling Problem［J］.Computer Engineering and Applications，2011，47（34）：242-245.

［15］馬清亮，胡昌華，陳新海.遺傳算法交叉和變異操作的模糊優(yōu)化［J］.計算機(jī)工程與應(yīng)用，2002，38（19）：33-34.MA Qingliang，HU Changhua，CHEN Xinhai.Fuzzy Optimization of Crossover and Mutation Opertion in Genetic Algorithm［J］.Computer Engineering and Applications，2002，38（19）：33-34.

［16］熊軍，高敦堂，都思丹，等.變異率和種群數(shù)目自適應(yīng)的遺傳算法［J］.東南大學(xué)學(xué)報（自然科學(xué)版），2004（34）：553-556.XIONG Jun，GAO Duntang，DU Sidan，et al.Genetic algorithm with mutation probability and population size adaptation［J］.Journal of Southeast University（Natural Science Edition），2004（34）：553-556.

［17］Adewumi A O，Sawyerr B A，Montaz A M.A Heuristic Solution to the University Timetabling Problem［J］.Engineer-ing Computations，2009，26（8）：972-984.

［18］朱冠宇，王乘，席大春.利用遺傳算法求解中學(xué)課表安排問題［J］.計算機(jī)工程與應(yīng)用，2004（27）：215-218.ZHU Guanyu，WANG Cheng，XI Dachun.Genetic Algorithm for Solving Curriculum Schedule Problem of Senior High School［J］.Computer Engineering and Applications，2004（27）：215-218.

［19］Shi Juan.Research on Application of IGA（Immune Genetic Algorithm）to the Solution of Course-Timetabling Problem［C］//MProc of the 4th Int.l Conf on Computer Science and Education，2009：1109-1105.

［20］Detienne B，Péridy L，Pinsoné.Cut generation for an employee timetabling problem［J］.European Journal of Operational Research，2009，197（3）：1178-1184.

［21］Pillay N，Banzhaf W.An Informed Genetic Algorithm for the Examination Timetabling Problem［J］.Applied Soft Computing，2010，10（2）：457-467.

Using a Space Coding and Sine Selection Operator GA to Solve the Timetabling Problem

QIAN Haijun
（Zhuhai City Polytechnic，Zhuhai 519000）

Genetic algorithm（GA）is an effective algorithm to solve multi-constrained and multi-objective combinatorial optimization problems.The classical genetic algorithm has the characteristics of premature convergence，which can lead to the local optimal solution.In order to improve the algorithm global searching performance，the paper proposed the genetic algorithm based on space coding and sine selection operator，or SCSS，taking the two aspects of chromosome coding design and selection operator design for the genetic algorithm as the cut-in point.The simulation results show that the SCSS genetic algorithm can solve the Open Education timetabling problem with multiple constraints，and provides a practical mathematical method to solve the problem of scheduling problem effectively.The improved genetic algorithm can quickly converge to the global optimal solution of the problem，and the global search performance of the algorithm is obviously enhanced.

genetic algorithm，multi-constrained，space coding，sine selection operator，the Open Education，the global optimal solution

TP301.6

10.3969/j.issn.1672-9722.2017.10.008

Class Number TP301.6

2017年4月17日，

2017年5月28日

2015年度廣東省教育信息技術(shù)研究“粵教云”計劃專項(xiàng)重點(diǎn)課題《基于興趣簇的云流媒體系統(tǒng)模型的研究》（編號：2015YJYZ016）；2014年度廣東遠(yuǎn)程開放教育科研基金項(xiàng)目《大數(shù)據(jù)視角下電大開放教育數(shù)據(jù)挖掘與分析對教與學(xué)的促進(jìn)研究》（編號：YJ1418）資助。

錢海軍，男，碩士，副教授，研究方向：系統(tǒng)理論，數(shù)據(jù)挖掘。