基于遺傳算法的智能組卷系統(tǒng)的研究與實現(xiàn)

摘要：組卷系統(tǒng)的研發(fā)不僅涉及到組卷數(shù)學(xué)模型建立的問題，還包括對其應(yīng)用適合的組卷算法的研究。由于遺傳算法具有全局尋優(yōu)和智能搜索的特性，所以本文將該算法引入智能組卷。然而若要尋求到真正適合的組卷算法，必須對現(xiàn)有的遺傳算法加以改進。本文對遺傳算法改進主要體現(xiàn)在以下幾個方面：編碼策略、適應(yīng)度函數(shù)的選取和遺傳算子及控制參數(shù)的設(shè)計等等。改進的遺傳算法在組卷中的應(yīng)用可以有效克服未成熟收斂，加快了收斂速度，明顯地改善了其全局尋優(yōu)能力，提高了組卷的成功率，取得了滿意的組卷效果。

關(guān)鍵詞：智能組卷；遺傳算法；數(shù)學(xué)模型；適應(yīng)度函數(shù)

1 引言

智能組卷是按照考試要求，由計算機智能地從試題庫中選取試題，組成一份符合試題各個指標(biāo)分布要求的試卷。20世紀(jì)80年代中后期，眾多研究者根據(jù)組卷問題的特點致力于組卷算法的研究，相繼產(chǎn)生了多種智能組卷方法。其中具有代表性的有弱并行法、誤差補償方法、隨機抽題法、回溯試探法和遺傳算法等等[1]。

然而，面對規(guī)模龐大的試題庫進行組卷時除遺傳算法以外各種算法往往顯得心有余而力不足，具有明顯的盲目性和隨機性，不具備智能性。而遺傳算法在全局尋優(yōu)和智能搜索方面有著無可比擬的優(yōu)勢，遺傳算法在解決能組卷這類帶有約束條件的優(yōu)化問題的上具有良好的性能。

本文結(jié)合了遺傳算法理論，首先應(yīng)用的遺傳算法在編碼策略采用分段實數(shù)編碼，克服采用二進制編碼的搜索空間過大和編碼長度過長的缺點；其次選擇算子采用模擬小生境的方法，它能夠有效地維持種群的多樣性，從而避免產(chǎn)生局部最優(yōu)解，改善未成熟收斂；最后運用自適應(yīng)理論改進交叉概率及變異概率，優(yōu)化交叉算子和變異算子，實現(xiàn)交叉和變異概率的非線性自適應(yīng)調(diào)整。改進后的算法應(yīng)用于考試系統(tǒng)的智能組卷問題，提高組卷效率和組卷成功率。

2 改進遺傳算法在組卷中應(yīng)用的流程

針對智能組卷的具體情況，本文將上述改進的遺傳算法應(yīng)用于組卷中，使得組卷算法更加高效。這種改進的智能組卷算法的具體算法流程圖如圖1所示。

3 改進遺傳算法求解組卷問題

3.1 組卷編碼方案的設(shè)計

本文采用了分段實數(shù)編碼策略。其具體思想表述如下：(1) 編碼位串中的基因表示在待選試題范圍中選中的試題編號；(2) 編碼位串分隔成多個不同的段，每一段表示一種題型；(3) 編碼位串中每個分段長度取決于試卷中要求該題型的題量，每個段表示一種題型，每一種題型單獨編碼； (4) 編碼位串的長度是根據(jù)試卷要求試題總數(shù)決定的，即任意個體中編碼的數(shù)量就是試卷中各題型試題數(shù)量相加的總和。

假設(shè)試卷中題型為A、B、C三類，試題庫中存放三種題型的待選試題數(shù)量分別為n1、n2、n3。試卷中試題總數(shù)為m，各題型試題數(shù)分別為m1、m2、m3，則具體編碼形式如圖2所示：

其中；；為選中試題編號。

例如，試題庫中題型待選試題為200道，題型待選試題為200道，題型待選試題為200道，試卷結(jié)構(gòu)要求中三個題型試題數(shù)分別為7，則一組選中試題的編碼可表示為形式如圖3所示：

第一段中編號為125表示A題型待選試題中選中題號為第125號的試題，其余各基因座上編號的意義與其相同。

3.2 種群選擇方法——小生境最優(yōu)選擇方法

小生境最優(yōu)選擇方法采用典型小生境技術(shù)[2]的思想，結(jié)合最優(yōu)保留策略[3]實現(xiàn)了種群的選擇，其具體思想如下：

(1)根據(jù)適應(yīng)度的大小把整個種群分解成若干個小生境，即子種群，每個小生境由兩對具有相似適應(yīng)度的個體組成，即父代個體。父代個體的配對僅限于各個小生境內(nèi)部獨立進行；(2)在每個小生境的遺傳操作后，運用父代種群參與競爭選擇策略[4]，即種群中所有父代個體與所有子代個體參與競爭選擇，從中找出當(dāng)前種群中適應(yīng)度最好的和最差的個體；(3)根據(jù)精英保留策略，若當(dāng)前的最好個體優(yōu)于迄今為止的最佳個體，則予以保留，即使當(dāng)代最好個體作為最佳個體直接進入下一代，否則仍保持原有最佳個體不進行交叉變異操作，直接進入下一代；(4)為了保證種群的多樣性、加快進化速度，采用刪去當(dāng)前最差個體，用迄今為止的最佳個體所代替的方法進行調(diào)節(jié)。

對其余的個體在每個小生境內(nèi)，按照文獻[5]提出的兩兩競爭選擇策略進行操作，產(chǎn)生下一代個體。當(dāng)種群中有部分個體基因相似時，通過調(diào)整局部搜索技術(shù)對這部分個體采用相同的變異機制對它們的基因進行細微變異，提高種群的多樣性，盡可能在局部范圍搜索出優(yōu)等個體。這種選擇方式的主要目是有效地維持種群的多樣性、避免基因缺失、提高全局收斂性和算法的收斂速度。

遺傳算法中選擇操作的目的是為了避免丟失有用遺傳信息，提高算法的全局收斂性和計算效率。種群選擇方法的優(yōu)劣，直接影響到遺傳算法的計算結(jié)果。實驗表明，在消除染色體同質(zhì)，改善種群多樣性上該方法優(yōu)于排序型擇優(yōu)選擇算子，故本文采用模擬小生境法選擇方法。

3.3 交叉算子

根據(jù)分段實數(shù)編碼策略的特點，本文采用段內(nèi)交叉操作，即在雙親染色體中的各題型在其各自編碼段內(nèi)進行交叉。具體實現(xiàn)步驟：

步驟1：隨機選取兩個雙親染色體，計算交叉概率，并產(chǎn)生[0，1]的隨機數(shù)，將隨機數(shù)與交叉概率相比較確定是否進行交叉操作。

步驟2：根據(jù)題型確定出交叉點個數(shù)，即有幾種題型就有幾個交叉點。

步驟3：在相同題型范圍內(nèi)產(chǎn)生一個隨機數(shù)，即一個交叉位置。

步驟4：判斷交叉點所在的段，檢驗兩個雙親染色體該段內(nèi)是否有相同題號。若有，則各自保留該題號并記錄相同題目數(shù)n；若沒有，則n=0，轉(zhuǎn)向步驟6。

步驟5：將相同題號移到該段的段首位置，然后執(zhí)行步驟6。

步驟6：根據(jù)步驟3中產(chǎn)生的交叉位置在該題型編碼段內(nèi)，進行交叉操作。

步驟7：是否處理完所有題型，若處理完畢，交叉結(jié)束。否則轉(zhuǎn)向步驟3。

例如任意選取兩個雙親染色體，組卷中兩雙親染色體（無相同題號）的交叉操作生成子代的形式如圖4所示。組卷中兩雙親染色體（具有相同題號）的交叉操作生成子代的形式如圖5所示。

3.4 變異算子

遺傳算法應(yīng)用于不同的問題中，其編碼策略需要與之相適應(yīng)的遺傳操作。針對分段實數(shù)編碼策略的特點，本文采用段內(nèi)基本位變異操作，即各題型在各自段內(nèi)進行變異。具體實現(xiàn)步驟：

步驟1：隨機選取一個雙親染色體，計算變異概率，并產(chǎn)生[0，1]的隨機數(shù)，將隨機數(shù)與變異概率相比較確定是否進行變異操作。

步驟2：根據(jù)題型確定出變異點個數(shù)，即有幾種題型就有幾個變異點。

步驟3：在相同題型范圍內(nèi)產(chǎn)生一個隨機數(shù)，即一個變異位置。

步驟4：在該題型下的待選試題中，隨機選取一道試題，并判斷該試題是否存在于變異個體中，若不存在，則替換變異位置上的試題。否則重復(fù)步驟4。

步驟5：是否處理完所有題型，若處理完畢，變異結(jié)束。否則轉(zhuǎn)向步驟3。

4 實驗條件和實驗結(jié)果分析

4.1 參數(shù)設(shè)定

種群規(guī)模為50，終止條件為目標(biāo)函數(shù)值 或最大迭代次數(shù)500次；常數(shù)Pcmax=0.05，Pcmax=0.8；Pmmin=0.005，Pmmax=0.05；適應(yīng)度函數(shù)中常數(shù)c=0.05。試卷的滿分值為100分，答題時間為120分鐘。其它約束條件設(shè)置如下所示：

(1)題型及分?jǐn)?shù)設(shè)置。

(2)難度系數(shù)設(shè)置。

試卷總的難易度系數(shù)設(shè)置為0.5。

(3)區(qū)分度系數(shù)設(shè)置。

試卷總的區(qū)分度設(shè)置為0.5。

(4)知識點設(shè)置。

本系統(tǒng)中的知識點和章節(jié)聯(lián)系?？季V中考試內(nèi)容共分十章，知識點在這十章中均勻分配，每章各占10%。

(5)權(quán)重設(shè)置。

由于本文適應(yīng)度函數(shù)是結(jié)合權(quán)重系數(shù)變化法的思想，重新設(shè)計了目標(biāo)函數(shù)。從試卷的多個指標(biāo)的內(nèi)在含義以及對組卷的重要程度的分析，可以將其分成三類：

·難度、區(qū)分度；·知識點、章節(jié)；·題型、總時間、總分?jǐn)?shù)。

所以，該函數(shù)為所有偏差的分層加權(quán)求和，第一類權(quán)重系數(shù)設(shè)為1，第二類權(quán)重系數(shù)設(shè)為2，第三類權(quán)重系數(shù)設(shè)為3。其中，1+2+3＝1 。

4.2 組卷結(jié)果

在以上實驗條件下，運用改進的遺傳算法連續(xù)五次進行智能組卷后所得試卷的總分平均為100分，試卷的時間平均為119.7分鐘，試卷的平均迭代次數(shù)為216，目標(biāo)函數(shù)值為0.009919，平均耗費CPU時間為18.279秒。其中最優(yōu)的一次組卷所組得試卷的考試時間為120分鐘，總分?jǐn)?shù)為100分，其它各項指標(biāo)分布如下所示。

(1)難度～分?jǐn)?shù)分布

根據(jù)前節(jié)計算試卷總的難易度公式，得出實際組卷總的難易度系數(shù)為0.492。

(2)區(qū)分度～分?jǐn)?shù)分布

根據(jù)前節(jié)計算試卷總的區(qū)分度公式，得出實際組卷總的區(qū)分度為0.488。

(3)章節(jié)～分?jǐn)?shù)分布

由表中數(shù)據(jù)可以看出，所得試卷的各項指標(biāo)分布與組卷要求中的各項指標(biāo)分布相差甚小，滿足了組卷的要求。實驗表明，基于改進遺傳算法的組卷算法能夠滿足實際考試需求，而且生成試卷的質(zhì)量較好。

4.3 隨機抽題算法與遺傳算法效率比較

為了檢驗改進算法的組卷效率，在相同的條件下分別采用傳統(tǒng)的隨機抽題算法、改進的遺傳算法進行50次組卷實驗，每次成功組卷的次數(shù)及其耗時如表1所示。利用MATLAB生成的進化代數(shù)與最優(yōu)適應(yīng)度關(guān)系圖如圖6所示。

從以上圖表中的數(shù)據(jù)可知，隨機選取算法組卷的速度較慢，特別是當(dāng)題庫中試題數(shù)量較多時組卷的成功率也較低。而基于文中改進遺傳算法的組卷算法一方面通過對遺傳算法的改進提高了算法的尋優(yōu)能力及尋優(yōu)速度。另一方面通過對編碼方式及遺傳操作的設(shè)計，使算法更加符合組卷問題的特點，表現(xiàn)出更好的尋優(yōu)效率，在保證組卷質(zhì)量的基礎(chǔ)上，提高了組卷速度。

參考文獻:

[1] 吳美娟.網(wǎng)絡(luò)考試系統(tǒng)的組卷算法及安全策略研究[D].長沙：中南大學(xué)，2006

[2] Jelasity M， Dombi J. GAS， a concept on modeling species in genetic algorithm.Artificial Intelligence， 1998， 99 (1)：1-19

[3] Rodolph G.Convergence propertiesof canonical genetic algorithms.Neural Networks， 1994， 5：96-101

[4] 徐宗本，聶贊坎等.父代種群參與競爭遺傳算法幾乎必然收斂[J].應(yīng)用數(shù)學(xué)學(xué)報，2002， 25(1)：167-175

[5] 高瑋.改進的快速遺傳算法及其性能研究.系統(tǒng)工程與電子術(shù)，2003，25 (11)：1427-1430