遺傳算法在智能排課系統中的應用

韓琳

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

關鍵詞：智能排課；遺傳算法；改進

1遺傳算法概述

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

1.1遺傳算法的基本原理

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

1.2遺傳算法的基本步驟

第一步：確定編碼的方案，將參數進行結合（又稱可行解的集合轉化成染色體的結構空間）。

第二步：為了方便計算適應值，所以要定義具體的適應度函數。

第三步：確定遺傳方案，通過對第一代種群進行相關操作，也就是通過選擇、交叉、變異的方法，來確定交叉和變異的概率等對應遺傳參數。

第四步：確定隨機產生對應的初始化群體。

第五步：主要計算種群里面的個體以及染色體解碼后，所產生的對應適應值。

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

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

1.3遺傳算法的演化過程

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

（1）隨機產生一定數目的初始種群

（2）對個體適應度進行評估，如果個體的適應度符合優化準則，則輸出最佳個體及其代表的最優解，并結束計算，否則轉向第3步

（3）依據適應度選擇再生個體

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

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

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

2遺傳算法解決排課問題的優勢

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

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

（3）遺傳算法具有并行性。由于遺傳算法是采用種群的方式來進行搜索的，因此它具備可以同時搜索空間內的多個區域的能力，并且相互之間可以進行信息交流。這種搜索方式雖然每次只能夠執行與種群規模互成比例的計算，但實際上，根據 Goldberg DE 的推算，以及他進行的 O（N3）次的有效搜索之后，這才使得遺傳算法能夠用較少的計算來獲取較大的收益。

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

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

3遺傳算法的改進

3.1遺傳算法的不足

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

3.2遺傳算法的改進方法

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

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