遺傳算法在智能排課系統(tǒng)中的應(yīng)用

韓琳

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

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

1遺傳算法概述

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

1.1遺傳算法的基本原理

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

1.2遺傳算法的基本步驟

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

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

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

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

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

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

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

1.3遺傳算法的演化過(guò)程

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

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

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

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

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

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

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

2遺傳算法解決排課問(wèn)題的優(yōu)勢(shì)

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

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

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

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

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

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

3.1遺傳算法的不足

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

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

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

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