混沌遺傳算法在自動組卷中的應用研究

徐新華

(泰州師范高等專科學校，江蘇 泰州 225300)

遺傳算法作為一種隨機優化算法在多目標優化等眾多領域取得廣泛的應用，尤其適用于處理非線性問題求解和最優化問題.遺傳算法同時具有內在的并行性、全局尋優和收斂速度快的特點，這些都適宜于處理自動組卷的問題.魏平[1]等采用傳統的遺傳算法(SGA)來實現試題庫的自動組卷，取得了較好的實際效果.

但標準遺傳算法(SGA)有它的局限性.算法初期，模式集中在適應度較低的個體上，若采用較小的交叉率和變異率，種群很難產生出優秀新個體.算法后期，模式開始朝適應度高的個體集中，倘若采用較大的交叉率和變異率，容易破壞優良模式，使算法陷入局部收斂.基本遺傳算法通常只有一個種群，且交叉概率和變異概率這兩個參數是固定的，存在早熟及收斂速度緩慢等問題，對于復雜的優化問題通常難以獲得高質量的解；并且要為某個特定的優化問題設置好交叉概率和變異概率需要經過反復試驗.

目前已經有很多研究人員對遺傳算法進行改進并應用到組卷中，以提高組卷運行效率.王淑佩[2]等將自適應遺傳算法與小生境技術相結合提出了一種自適應調整種群適應值分布的基于小生境技術的遺傳算法；劉彬[3]等對題型確定過程中的知識進行改進，相對于簡單遺傳算法均取得了較好的結果；魏平[4]等采用穩態策略的單親遺傳算法求解組卷問題，通過突變算子的引入，使整個種群保持在最有可能獲得成功的狀態，加快了算法向全局最優值的逼近速度.

本文提出一種基于混沌序列的改進型遺傳算法，來解決計算機組卷中約束優化問題.通過模擬實驗，結果表明該方法有效解決了自動組卷中的約束優化問題，具有很好的性能和實用性.

1 自然數編碼策略

按照一定的編碼方法和編碼策略，科學、合理、準確地為每道試題進行編碼是高效組卷的首要工作，完整的試題編碼能大大提高組卷算法的效率和成功率.在確定編碼方案時，本系統采用了分段的自然數編碼策略.每一段編碼反映一種題型，各個題型各自進行自然數編碼，題型組之間的編碼是獨立的.另外，由于在自動組卷過程中不是對試題信息進行操作，而是操作試題的編碼.試題編碼代表一道試題的特性.

一般題庫中試題的屬性項有：試題編號、試題類型、考查知識點、難度、區分度、認知層次、試題內容、操作說明、答題時間、建議分值、已使用次數、最近使用時間等.其中最重要的是知識點、認知層次、試題類型、試題難度和試題區分度等五個基本特征，故取這五個基本特征組成試題編碼.

用兩位編碼(00-99)表示100個知識點.認知層次則按了解、理解、掌握和綜合分類，分別編碼1-4.表征題型的編碼有相對隨意性，本系統如下編碼：“單項選擇題(A1)”賦1，“多項選擇題(A2)”賦2，“配對題”賦3，“填空題”賦4等.試題難度編碼將分為五個等級，依次為：易賦1，較易賦2、中賦3、較難賦4和難賦5.試題區分度是指對學生學科能力的鑒別力，亦分五級，差賦1、較差賦2、中賦3、良賦4和優賦5.

將上述知識點、認知分類、試題類型、試題難度和試題區分度等五維特征編碼結合起來，同時考慮到相同特征的試題有多個，需加上相同特征題目的順序號，就構成每道試題的7位編號.如編碼“5221231”表示該試題屬于知識點“52”、認知層次是“了解”、題型是“填空題”、難度系數“較易”、試題區分度“中”、同知識點同題型試題編號“1”.

我們將一份試卷映射為一個染色體，染色體采用變長編碼策略進行處理，組成試卷的各個試題映射為基因，染色體中基因的個數就是試卷中試題的個數，基因的值直接用試題編碼表示.如圖1表示兩張試卷的染色體，染色體的長度為7*試題數.

圖1 兩份試卷的染色體信息圖

以上編碼策略優點體現如下：

(1)對試題進行自然數編碼所表達的變量意義清楚、明確，可以克服傳統的采用二進制編碼搜索空間過大和編碼長度過長的缺點，同時取消了個體的解碼時間，有效改善了遺傳算法的復雜性，提高了算法的運算效率.

(2)使用了分段的思想，把各類題型放在同一段，在進行遺傳操作時，保持在段內進行，這樣個體就不會進化到其它段，組卷時保證了優化目標中題型的正確匹配.

2 采用混沌機制控制遺傳操作

早熟收斂是遺傳算法在實際應用中經常遇到的一個疑難問題，它主要表現為種群中最優個體的適應度值得不到提高，種群在經過若干次迭代后仍不能找到全局最優解.引起早熟收斂的因素很多，比如選擇、交叉和變異算子的使用不當或者控制參數的選擇不當都會導致早熟收斂的發生.其實，從本質上來講，早熟收斂主要是由于群體中有效基因的缺失[5]，或者只要群體中有效基因的濃度減少到一定程度時，就會引起早熟收斂的發生，使得群體處于停滯狀態.

因此，為了預防早熟收斂，在有效基因未知的情況下，變異算子必須有能力保持同一基因位上的等位基因的多樣性，這樣才能有助于防止有效基因的缺損，從而能夠最大限度地避免早熟收斂.本文提出了基于混沌序列的動態遺傳操作，使遺傳操作具有內在的規律性，克服了簡單遺傳算法中純隨機所帶來的缺點，充分發揮了遺傳算法和混沌理論的各自優點.

(1)混沌序列的產生.桂傳志在文獻[6]提到可以利用logistic映射、立方映射和邏輯自映射函數等三種映射方法產生混沌序列，并通過實驗比較論證了三種映射方法產生混沌序列的分布均勻性.結果表明logistic映射的分布很不均勻，它的落點常超過90%；而立方映射和邏輯自映射函數相對來說要均勻一些.所以本文選用邏輯自映射函數產生混沌序列.具體公式如下：

x(n+1)=1-2x2(n)，

n=0，1，2，3…，-1

(1)

在實際工程應用過程中，只要迭代初值不為0，混沌就會發生，此時映射的定義域為[-1，1]，且x≠0，當迭代一定次數時，系統輸出將遍歷整個解空間.

(2)混沌交叉算子.用混沌序列控制交叉點的選擇.設染色體有L位長，先產生一個混沌序列xn，然后把序列xn映射到染色體基因位空間.考慮染色體編碼是以試題編碼長度7的整數倍，我們要對產生的基因位空間按以下公式做適當調整，然后在相應的位置進行基因串的交叉操作，從而得到兩個新的個體.

如果x∈[0，1]，則混沌交叉算子為

site=[(L×xn)/7]×7

(2)

其中，[…]符號表示向上取整.

在本組卷系統中，如有兩套試卷(如下)組成配對個體組(假設試卷共有12道試題，則當前染色體的編碼長度為12*7)進行單點交叉，其中X1和Y1表示一個試題：

染色體A：X1X2X3X4X5X6X7X8X9X10X11X12

染色體B：Y1Y2Y3Y4Y5Y6Y7Y8Y9Y10Y11Y12

如果式(1)、(2)所產生的一個混沌序列的當前值site1為14，則交叉位置是在第2道試題后面，則產生的下一代個體組為

染色體A'：X1X2Y3Y4Y5Y6Y7Y8Y9Y10Y11Y12

染色體B'：Y1Y2X3X4X5X6X7X8X9X10X11X12

(3)混沌變異算子.用混沌序列控制變異基因位.根據式(1)所產生的一個混沌序列的當前值x(k)，再利用式(3)把混沌變量xi(k)映射到染色體基因位空間，即混沌變異算子為：

Si(k)=[Nxi(k)]i=1，2，…，n(n?N)

(3)

式中，N表示染色體編碼長度，[…]表示取整.對相應基因位上的基因進行變異.結合試卷染色體編碼位的取值范圍，不能進行簡單的變異，即0變為1、1變為0；而是根據試題編碼位上每一位的可能取值范圍進行變換(如試題編碼的第6位表示區分度，其取值是在1～5之間).

結合前面示例，對染色體A'進行上述變異，從而生成新的個體A''=X'1X'2Y'3…Y'12，在試題庫中搜索變異得到的試題是否存在，如果不存在則重新進行變異，如果存在則計算新個體的適應度值f(A'').

說明：混沌雖然具有類隨機性、遍歷性以及初值敏感性，通過迭代混沌映射可以生成統計特性呈隨機分布的偽隨機序列，但混沌不是隨機，混沌具有短期可預測性質[7]，即總存在整數N和映射f，使得混沌序列{xn}可以用映射xn+N=f(xn，xn+1，…，xn+N-1)描述.

3 基于混沌序列的改進型遺傳算法的執行流程

{ 設置當前代數計數器t←1；

初始化種群P(0)={X1，X2，…，Xn}；

計算P(0)中各個體的適應度Fi(i=1，2…M)；

while(不滿足終止條件) //終止條件與SGA中相同

{ 根據個體適應度以及選擇策略，計算種群內個體選擇概率Pi；根據Pi從父體P(t)中選擇N1(≤N)個個體；

將父輩群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進入下一代；

確定基于混沌序列的混沌交叉算子；

按交叉概率Pc對父個體的配對個體組再進行交叉操作，重組新個體組；

基于混沌序列映射產生混沌變異算子；

按變異概率Pm對新個體進行換位，產生下一代個體；

計算新一代群體P(t+1)中各個體的適應度，如果生成的新個體的適應度值大于原個體，則替換原個體，否則原個體保持不變；

t=t+1； //代數增1

}

}

4 小結

本文提出了基于混沌序列的改進型遺傳算法，并指出在組卷系統實現的過程.首先對染色體采用分段自然數編碼策略；然后，將混沌機制同時引入到遺傳算法的交叉和變異階段，對在交叉階段交叉基因座由混沌交叉算子來確定，在變異階段變異個體的變異基因位由混沌變異算子來給出.這種改進型遺傳算法將混沌優化的遍歷性、規律性與遺傳算法的全局性相結合，可以有效地克服遺傳算法隨機性大、未成熟收斂等不足.

當然，目前我們給出的算法還相當粗糙，其中參數設置調整需要靠經驗試湊，對算法實現的收斂性等尚未給出嚴密的數學分析和證明.相信隨著上述問題的解決，將會產生較為精致的全局優化方法，為解決實際問題提供有效的便利工具.

參考文獻：

[1]魏平，張元.一種求解組卷問題的遺傳算法[J].寧波大學學報，2002，15(2):47-50.

[2]王淑佩，易葉青.基于改進自適應遺傳算法的組卷研究[J].科學技術與工程，2006，6(4):468-473.

[3]劉彬，李勇，糜長軍.智能組卷系統中專家知識的表示與實現[J].計算機工程與應用，2002，38(17):229-231.

[4]魏平，干海光，熊偉清.基于進化穩定策略的單親遺傳算法求解組卷問題[J].微電子學與計算機，2005，22(1):l05-109.

[5]揮為民，席裕庚.遺傳算法的運行機理分析[J].控制理論與應用，1996(3):297-304.

[6]桂傳志.混沌序列在優化理論中的應用[D].南京：南京理工大學，2006.

[7]王開.確定性隨機理論及在混沌密碼學中的應用研究[D].南京：東南大學，2004.