混沌遺傳算法在自動(dòng)組卷中的應(yīng)用研究

徐新華

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

遺傳算法作為一種隨機(jī)優(yōu)化算法在多目標(biāo)優(yōu)化等眾多領(lǐng)域取得廣泛的應(yīng)用，尤其適用于處理非線性問(wèn)題求解和最優(yōu)化問(wèn)題.遺傳算法同時(shí)具有內(nèi)在的并行性、全局尋優(yōu)和收斂速度快的特點(diǎn)，這些都適宜于處理自動(dòng)組卷的問(wèn)題.魏平[1]等采用傳統(tǒng)的遺傳算法(SGA)來(lái)實(shí)現(xiàn)試題庫(kù)的自動(dòng)組卷，取得了較好的實(shí)際效果.

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

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

本文提出一種基于混沌序列的改進(jìn)型遺傳算法，來(lái)解決計(jì)算機(jī)組卷中約束優(yōu)化問(wèn)題.通過(guò)模擬實(shí)驗(yàn)，結(jié)果表明該方法有效解決了自動(dòng)組卷中的約束優(yōu)化問(wèn)題，具有很好的性能和實(shí)用性.

1 自然數(shù)編碼策略

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

一般題庫(kù)中試題的屬性項(xiàng)有：試題編號(hào)、試題類型、考查知識(shí)點(diǎn)、難度、區(qū)分度、認(rèn)知層次、試題內(nèi)容、操作說(shuō)明、答題時(shí)間、建議分值、已使用次數(shù)、最近使用時(shí)間等.其中最重要的是知識(shí)點(diǎn)、認(rèn)知層次、試題類型、試題難度和試題區(qū)分度等五個(gè)基本特征，故取這五個(gè)基本特征組成試題編碼.

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

將上述知識(shí)點(diǎn)、認(rèn)知分類、試題類型、試題難度和試題區(qū)分度等五維特征編碼結(jié)合起來(lái)，同時(shí)考慮到相同特征的試題有多個(gè)，需加上相同特征題目的順序號(hào)，就構(gòu)成每道試題的7位編號(hào).如編碼“5221231”表示該試題屬于知識(shí)點(diǎn)“52”、認(rèn)知層次是“了解”、題型是“填空題”、難度系數(shù)“較易”、試題區(qū)分度“中”、同知識(shí)點(diǎn)同題型試題編號(hào)“1”.

我們將一份試卷映射為一個(gè)染色體，染色體采用變長(zhǎng)編碼策略進(jìn)行處理，組成試卷的各個(gè)試題映射為基因，染色體中基因的個(gè)數(shù)就是試卷中試題的個(gè)數(shù)，基因的值直接用試題編碼表示.如圖1表示兩張?jiān)嚲淼娜旧w，染色體的長(zhǎng)度為7*試題數(shù).

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

以上編碼策略優(yōu)點(diǎn)體現(xiàn)如下：

(1)對(duì)試題進(jìn)行自然數(shù)編碼所表達(dá)的變量意義清楚、明確，可以克服傳統(tǒng)的采用二進(jìn)制編碼搜索空間過(guò)大和編碼長(zhǎng)度過(guò)長(zhǎng)的缺點(diǎn)，同時(shí)取消了個(gè)體的解碼時(shí)間，有效改善了遺傳算法的復(fù)雜性，提高了算法的運(yùn)算效率.

(2)使用了分段的思想，把各類題型放在同一段，在進(jìn)行遺傳操作時(shí)，保持在段內(nèi)進(jìn)行，這樣個(gè)體就不會(huì)進(jìn)化到其它段，組卷時(shí)保證了優(yōu)化目標(biāo)中題型的正確匹配.

2 采用混沌機(jī)制控制遺傳操作

早熟收斂是遺傳算法在實(shí)際應(yīng)用中經(jīng)常遇到的一個(gè)疑難問(wèn)題，它主要表現(xiàn)為種群中最優(yōu)個(gè)體的適應(yīng)度值得不到提高，種群在經(jīng)過(guò)若干次迭代后仍不能找到全局最優(yōu)解.引起早熟收斂的因素很多，比如選擇、交叉和變異算子的使用不當(dāng)或者控制參數(shù)的選擇不當(dāng)都會(huì)導(dǎo)致早熟收斂的發(fā)生.其實(shí)，從本質(zhì)上來(lái)講，早熟收斂主要是由于群體中有效基因的缺失[5]，或者只要群體中有效基因的濃度減少到一定程度時(shí)，就會(huì)引起早熟收斂的發(fā)生，使得群體處于停滯狀態(tài).

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

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

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

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

(1)

在實(shí)際工程應(yīng)用過(guò)程中，只要迭代初值不為0，混沌就會(huì)發(fā)生，此時(shí)映射的定義域?yàn)閇-1，1]，且x≠0，當(dāng)?shù)欢ù螖?shù)時(shí)，系統(tǒng)輸出將遍歷整個(gè)解空間.

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

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

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

(2)

其中，[…]符號(hào)表示向上取整.

在本組卷系統(tǒng)中，如有兩套試卷(如下)組成配對(duì)個(gè)體組(假設(shè)試卷共有12道試題，則當(dāng)前染色體的編碼長(zhǎng)度為12*7)進(jìn)行單點(diǎn)交叉，其中X1和Y1表示一個(gè)試題：

染色體A：X1X2X3X4X5X6X7X8X9X10X11X12

染色體B：Y1Y2Y3Y4Y5Y6Y7Y8Y9Y10Y11Y12

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

染色體A'：X1X2Y3Y4Y5Y6Y7Y8Y9Y10Y11Y12

染色體B'：Y1Y2X3X4X5X6X7X8X9X10X11X12

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

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

(3)

式中，N表示染色體編碼長(zhǎng)度，[…]表示取整.對(duì)相應(yīng)基因位上的基因進(jìn)行變異.結(jié)合試卷染色體編碼位的取值范圍，不能進(jìn)行簡(jiǎn)單的變異，即0變?yōu)?、1變?yōu)?；而是根據(jù)試題編碼位上每一位的可能取值范圍進(jìn)行變換(如試題編碼的第6位表示區(qū)分度，其取值是在1～5之間).

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

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

3 基于混沌序列的改進(jìn)型遺傳算法的執(zhí)行流程

{ 設(shè)置當(dāng)前代數(shù)計(jì)數(shù)器t←1；

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

計(jì)算P(0)中各個(gè)體的適應(yīng)度Fi(i=1，2…M)；

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

{ 根據(jù)個(gè)體適應(yīng)度以及選擇策略，計(jì)算種群內(nèi)個(gè)體選擇概率Pi；根據(jù)Pi從父體P(t)中選擇N1(≤N)個(gè)個(gè)體；

將父輩群體中最佳個(gè)體保留下來(lái)，不參加交叉和變異操作，使之直接進(jìn)入下一代；

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

按交叉概率Pc對(duì)父?jìng)€(gè)體的配對(duì)個(gè)體組再進(jìn)行交叉操作，重組新個(gè)體組；

基于混沌序列映射產(chǎn)生混沌變異算子；

按變異概率Pm對(duì)新個(gè)體進(jìn)行換位，產(chǎn)生下一代個(gè)體；

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

t=t+1； //代數(shù)增1

}

}

4 小結(jié)

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

當(dāng)然，目前我們給出的算法還相當(dāng)粗糙，其中參數(shù)設(shè)置調(diào)整需要靠經(jīng)驗(yàn)試湊，對(duì)算法實(shí)現(xiàn)的收斂性等尚未給出嚴(yán)密的數(shù)學(xué)分析和證明.相信隨著上述問(wèn)題的解決，將會(huì)產(chǎn)生較為精致的全局優(yōu)化方法，為解決實(shí)際問(wèn)題提供有效的便利工具.

參考文獻(xiàn)：

[1]魏平，張?jiān)?一種求解組卷問(wèn)題的遺傳算法[J].寧波大學(xué)學(xué)報(bào)，2002，15(2):47-50.

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

[3]劉彬，李勇，糜長(zhǎng)軍.智能組卷系統(tǒng)中專家知識(shí)的表示與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用，2002，38(17):229-231.

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

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

[6]桂傳志.混沌序列在優(yōu)化理論中的應(yīng)用[D].南京：南京理工大學(xué)，2006.

[7]王開(kāi).確定性隨機(jī)理論及在混沌密碼學(xué)中的應(yīng)用研究[D].南京：東南大學(xué)，2004.