基于遺傳算法的智能組卷系統的研究與實現

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

關鍵詞：智能組卷；遺傳算法；數學模型；適應度函數

1 引言

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

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

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

2 改進遺傳算法在組卷中應用的流程

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

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

3.1 組卷編碼方案的設計

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

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

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

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

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

3.2 種群選擇方法——小生境最優選擇方法

小生境最優選擇方法采用典型小生境技術[2]的思想，結合最優保留策略[3]實現了種群的選擇，其具體思想如下：

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

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

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

3.3 交叉算子

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

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

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

步驟3：在相同題型范圍內產生一個隨機數，即一個交叉位置。

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

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

步驟6：根據步驟3中產生的交叉位置在該題型編碼段內，進行交叉操作。

步驟7：是否處理完所有題型，若處理完畢，交叉結束。否則轉向步驟3。

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

3.4 變異算子

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

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

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

步驟3：在相同題型范圍內產生一個隨機數，即一個變異位置。

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

步驟5：是否處理完所有題型，若處理完畢，變異結束。否則轉向步驟3。

4 實驗條件和實驗結果分析

4.1 參數設定

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

(1)題型及分數設置。

(2)難度系數設置。

試卷總的難易度系數設置為0.5。

(3)區分度系數設置。

試卷總的區分度設置為0.5。

(4)知識點設置。

本系統中的知識點和章節聯系。考綱中考試內容共分十章，知識點在這十章中均勻分配，每章各占10%。

(5)權重設置。

由于本文適應度函數是結合權重系數變化法的思想，重新設計了目標函數。從試卷的多個指標的內在含義以及對組卷的重要程度的分析，可以將其分成三類：

·難度、區分度；·知識點、章節；·題型、總時間、總分數。

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

4.2 組卷結果

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

(1)難度～分數分布

根據前節計算試卷總的難易度公式，得出實際組卷總的難易度系數為0.492。

(2)區分度～分數分布

根據前節計算試卷總的區分度公式，得出實際組卷總的區分度為0.488。

(3)章節～分數分布

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

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

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

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

參考文獻:

[1] 吳美娟.網絡考試系統的組卷算法及安全策略研究[D].長沙：中南大學，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].應用數學學報，2002， 25(1)：167-175

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