韓琳

摘要：高校教務(wù)管理工作中，排課問題是一項重要而又復(fù)雜的工作。遺傳算法是一種借鑒于生物界自然選擇規(guī)律和進(jìn)化機(jī)制體系發(fā)展起來的自適應(yīng)隨機(jī)搜索算法。具有良好的并行性、通用性、穩(wěn)定性，是一種非有效的解決NP完全問題的方法。

關(guān)鍵詞：智能排課；遺傳算法；改進(jìn)

1遺傳算法概述

遺傳算法是一種通過借鑒達(dá)爾文的生物進(jìn)化率而得來的進(jìn)化規(guī)律演化而來的智能排課方法。它的主要特點是直接對結(jié)構(gòu)對象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性等條件的限定；具有更好的全局尋優(yōu)能力；另外，其通過采用概率化的尋優(yōu)方法，能夠自動的獲取并且指導(dǎo)優(yōu)化的搜索空間，根據(jù)自身條件適應(yīng)地、有選擇的調(diào)整搜索方向，不需要確定的規(guī)則。正是因為遺傳算法的這些性質(zhì)和優(yōu)點，所以遺傳算法已經(jīng)廣泛的被人們應(yīng)用于機(jī)器學(xué)習(xí)、組合優(yōu)化、人工生命、信號處理、和自適應(yīng)控制等領(lǐng)域。是智能計算排課系統(tǒng)中的關(guān)鍵技術(shù)。另外，遺傳算法作為因生物進(jìn)化思想而受到啟發(fā)得出的一種全局優(yōu)化算法，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。

1.1遺傳算法的基本原理

遺傳算法是類似于生物進(jìn)化的一個智能排課算法。將其主要載體比喻為染色體，換句話說也就是多個基因的組合。我們通過這些多個基因的組合來決定個體的形狀以及外在的表現(xiàn)。因此，我們首先需要實現(xiàn)從表現(xiàn)型到基因型的轉(zhuǎn)化，也就是編碼工作。在第一代種群產(chǎn)生后，經(jīng)過選擇、交叉、變異等具體方法來進(jìn)行改革優(yōu)化，直到滿足優(yōu)化標(biāo)準(zhǔn)為止。

1.2遺傳算法的基本步驟

第一步：確定編碼的方案，將參數(shù)進(jìn)行結(jié)合（又稱可行解的集合轉(zhuǎn)化成染色體的結(jié)構(gòu)空間）。

第二步：為了方便計算適應(yīng)值，所以要定義具體的適應(yīng)度函數(shù)。

第三步：確定遺傳方案，通過對第一代種群進(jìn)行相關(guān)操作，也就是通過選擇、交叉、變異的方法，來確定交叉和變異的概率等對應(yīng)遺傳參數(shù)。

第四步：確定隨機(jī)產(chǎn)生對應(yīng)的初始化群體。

第五步：主要計算種群里面的個體以及染色體解碼后，所產(chǎn)生的對應(yīng)適應(yīng)值。

第六步：參照先前確定好的遺傳的策略，在進(jìn)行選擇，并選出交叉和變異算子等方法作用于群體，最終形成下一代的群體。

第七步：主要用于判別群體的性能是否能夠滿足其中具體的某一項指標(biāo)，是否完成事先約定的迭代次數(shù)，假如不能夠完成的話，需要返回到第五步或者通過修改具體遺傳方案后再返回第六步。

1.3遺傳算法的演化過程

遺傳算法采用類似基因演化的循環(huán)過程，其演算過程如下：

（1）隨機(jī)產(chǎn)生一定數(shù)目的初始種群

（2）對個體適應(yīng)度進(jìn)行評估，如果個體的適應(yīng)度符合優(yōu)化準(zhǔn)則，則輸出最佳個體及其代表的最優(yōu)解，并結(jié)束計算，否則轉(zhuǎn)向第3步

（3）依據(jù)適應(yīng)度選擇再生個體

（4）按照一定的交叉概率和交叉方法生成新的個體

（5）按照一定的變異概率和變異方法生成新的個體

（6）由交叉和變異產(chǎn)生新一代的種群，然后返回第2步

2遺傳算法解決排課問題的優(yōu)勢

（1）遺傳算法是高效智能算法。遺傳算法在已經(jīng)確定了編碼方案、適應(yīng)度函數(shù)和遺傳算子之后，又利用演化過程中所獲得的信息進(jìn)行自行組織搜索，通過選擇來看，適應(yīng)度大的個體通常具有比較高的生存概率，而適應(yīng)度小的個體則具有比較低的生存概率。遺傳算法是具有“潛在學(xué)習(xí)能力”的自適應(yīng)搜索技術(shù)。

（2）遺傳算法具有群體搜索策略。群體中各個個體之間的信息交換是單獨存在的，并不依賴于初始參數(shù)的特點，并具有較好的通用性、穩(wěn)定性。

（3）遺傳算法具有并行性。由于遺傳算法是采用種群的方式來進(jìn)行搜索的，因此它具備可以同時搜索空間內(nèi)的多個區(qū)域的能力，并且相互之間可以進(jìn)行信息交流。這種搜索方式雖然每次只能夠執(zhí)行與種群規(guī)?；コ杀壤挠嬎?，但實際上，根據(jù) Goldberg DE 的推算，以及他進(jìn)行的 O（N3）次的有效搜索之后，這才使得遺傳算法能夠用較少的計算來獲取較大的收益。

（4）遺傳算法在解決排課問題這類具有多重約束的組合優(yōu)化問題時，幾乎能夠得到基本滿足各種需求的課表。

（5）遺傳算法解法之所以能夠被各級各類的學(xué)校所認(rèn)可，是因為它能夠較好地解決并能滿足各類學(xué)校對課表編排的其他特殊要求，通過評價函數(shù)值、適應(yīng)度函數(shù)值的方式使復(fù)雜的排課約束條件能夠得以量化，這有利于解決類似于排課這種模糊不清并且不確定的問題。

3遺傳算法的改進(jìn)

3.1遺傳算法的不足

我們在利用遺傳算法解決實際問題的過程中，發(fā)現(xiàn)出現(xiàn)了一些現(xiàn)象，例如：種群發(fā)散和早熟現(xiàn)象，換句話說，也就是會有不收斂或者過早收斂的現(xiàn)象。一方面，我們利用數(shù)學(xué)概率知識來分析遺傳算法知識，同時認(rèn)為收斂的過程是一個無限逼近的過程，但是計算過程卻屬于有限自動機(jī)，并且在數(shù)學(xué)概率運算的作用下，種群的產(chǎn)生、遺傳和變異都是隨機(jī)抽取的，而在算法進(jìn)化的過程中可能由于概率的隨機(jī)性而丟失優(yōu)勢個體，容易造成種群的適應(yīng)能力下降，從而導(dǎo)致不收斂或過早收斂現(xiàn)象。另一方面，由于優(yōu)勢個體的優(yōu)勢作用，導(dǎo)致它會優(yōu)先進(jìn)行繁殖，從而致使劣勢個體的淘汰，因此會造成部分基因的丟失，降低了種群的多樣性，正是由于這些原因，這才會產(chǎn)生早熟現(xiàn)象或容易造成局部最優(yōu)現(xiàn)象。所以，通常情況下運用基本遺傳算法在解決實際問題時所求得的最終結(jié)果通常存在一定局限現(xiàn)象，并不是最佳結(jié)果；除此之外，采用簡單遺傳算法具有不可避免多次對某一個可行解的搜索，因此會造成另外的負(fù)面效應(yīng)，會導(dǎo)致那只是選擇了局部的最優(yōu)解，而并非整體最優(yōu)解，這也是影響運行效率的一個因素。

3.2遺傳算法的改進(jìn)方法

鑒于上述兩類情況，本文給出了兩類對策：首先是最優(yōu)個體替換，其次是對淘汰的個體進(jìn)行有限的回收。經(jīng)過改進(jìn)的遺傳算法更能滿足現(xiàn)實需要，具有更為良好的性能。

最優(yōu)個體保留原則 ：改進(jìn)的遺傳算法在排課過程中的應(yīng)用與實現(xiàn)由于遺傳算法具有隨機(jī)性的特點，如果采用簡單遺傳算法，在種群進(jìn)化過程中難免出現(xiàn)適應(yīng)度最高的個體丟失現(xiàn)象，若采用最優(yōu)個體保留原則即可降低此類現(xiàn)象出現(xiàn)的概率。最優(yōu)個體保留原則，即對每代中的最優(yōu)個體進(jìn)行選擇，使其進(jìn)入子代，而對子代中具有最差適應(yīng)度個體進(jìn)行剔除，以此維持整個種群的規(guī)模的穩(wěn)定。規(guī)定種群數(shù)量是對種群中具有最大適應(yīng)度的個體進(jìn)行記錄，進(jìn)而進(jìn)行母體的交叉、變異操作。從中得到個個體，并加上在上一代群體中具有最高適用度的個體，以此維持整個種群的規(guī)模的恒定。通過這種方式的修訂可以確保種群序列適應(yīng)值具有單調(diào)不減性的特征。