基于知識點約束的遺傳算法組卷策略的研究

耿 霞

(天津市信息中心，天津 300201)

遺傳算法GA(Genetic Algorithm)是一種模擬自然界生物進化過程的隨機搜索、優化方法。它是模擬達爾文的遺傳選擇和自然淘汰生物進化過程的計算模型[1]，采用簡單的編碼技術來表示各種復雜的結構，并通過一組編碼表示簡單的遺傳操作和優勝劣汰的自然選擇來指導學習和確定搜索的方向。由于遺傳算法采用種群的方式組織搜索，這使得它可以同時搜索解空間內的多個區域，而且用種群組織搜索方式使得其特別適合大規模并行。目前，該算法已滲透到許多領域，并成為解決各領域復雜問題的有力工具。

1 遺傳算法用于組卷的優勢

作為一種優化與搜索算法，遺傳算法相比于其他算法應用于組卷系統所具有的優勢在于[2]：

(1)遺傳算法的操作對象是一組可行解，而非單個可行解，搜索軌道有多條，而非單條，因而具有良好的并行性。

(2)遺傳算法只需要利用目標的取值信息，而無需梯度等高價值信息，因而適用于任何大規模、高度非線性的不連續多峰函數的優化以及解析式的目標函數的優化，具有很強的通用性。

(3)遺傳算法擇優機制是一種“軟”選擇，加上其良好的并行性，使它具有良好的全局優化性和穩健性。

(4)遺傳算法操作的可行解是經過編碼化的，目標函數解釋為編碼化個體的適應值，因而具有良好的可操作性和簡單性。

2 基于遺傳算法的組卷策略

組卷中決定一道試題，即是決定1個包含有試題唯一標識(ID)、題型、難度、區分度、考核點、考核點類型、能力層次、建議分值的 8 維向量(a1，a2，a3，a4，a5，a6，a7，a8)，決定一份試卷 n道題，就決定了 1個 n×6的矩陣S：

這就是問題求解中的目標狀態矩陣。建立問題的目標矩陣后，依據遺傳算法的基本流程，對本研究的組卷策略進行詳細闡述。

2.1 染色體編碼及群體的初始化

用遺傳算法求解問題，首先要將問題的解空間映射成一組代碼串[3]。有文獻用二進制編碼，用1表示該題被選中，0表示未被選中。這種編碼簡單明了，但是進行交換等遺傳操作時，各題型的題目數難以精確控制。當題庫中題量很大時，編碼冗長。已有大量實驗表明，在解決數值優化問題時，采用實數編碼的遺傳算法的效率要好得多，因此，本研究采用實數編碼。在組卷中所得的可行解就為一份試卷，所以本研究將一份試卷映射為1個染色體，組成試卷的各個試題映射為基因，基因的值直接用試題的ID表示，這樣染色體的編碼可表示為：(G1，G2，G3…，Gn)，其中 Gi(i=1～n，n 為試卷的總題目數)為試題的ID。編碼時應將同一題型的試題放在一起，并保證每條染色體上的基因不重復，即每套試卷中不能出現重復試題。

試題的難度分為4檔，本研究采用離散型隨機變量的二項分布函數B(n，p)建立 1個由試卷的期望平均分P計算難度分布的模型。

離散型隨機變量的二項分布函數B(n，p)：

其中，k=0，1，2，…，n，n 為整數，p＞0，q＞0，p+q=1。

2.2 適應度函數

在遺傳算法中，以適應度大小來區分群體中個體的優劣。一般而言，適應值越大的個體越好，越容易被保留而繁衍下一代：適應值越小的個體越差，更容易被淘汰。適應值的選取是遺傳算法設計的關鍵，它直接決定算法的優劣以及該組卷策略的科學性。本研究提出的自動組卷模型是基于知識點分布的，采用如下方法設定適應度函數F，F分別由 f1，f2和f33個子函數組成。

f1表示章節分數分布適應函數。 設 Ci、Xi、ei(i=1，2，…，m，m為章的數目)分別表示用戶要求的各章應占的分數、實際生成試卷中各章所占的分數、用戶允許各章的分數誤差。生成的試卷滿足用戶關于內容分數分布要求的程度可以用式(2)值的大小來評價：

其中m為總章數，Xi為實際分配的分值，Ci為預期值，ei為允許誤差。

式(2)采用方差來統計章節分數分布的偏差，而不用di的差的絕對值來表示，是因為f1是用來評價某份試卷對每一章的適應度的誤差，只是簡單地將誤差值累加，不能充分表現該試卷每一章的偏差。

f2表示知識點的覆蓋率和考核點類型的分配比例的適應值函數。本研究以考核點的覆蓋率作為一項“軟”約束條件，即考核點覆蓋率越大。該試卷的適應度越大；同時根據命題的經驗，如果一份試卷的考核點類型分布比例越接近5:3:2，那么該套試卷的命題比例越科學，其試卷的考后成績越容易呈正態分布，故本研究將這2個參數也作為適應度函數之一：

其中n為本章總分數，a是考核點為重點的分值分配，b是考核點為次重點的分配分值，c是考核點為一般的分配分值，tc為該套試卷所占的不重復考核點數，tm為該門課程總考核點數。

f3表示難度分布適應度函數。設 Ai、Si、ei(i=1，2，…，n，n為難度等級數)分別表示用戶期望的每個難度等級應占的分數、實際試卷中各等級所占的分數、允許誤差。生成的試卷滿足用戶關于難度分數分布要求的程度可以用式(4)值的大小來評價：

同理，該式的方差值越小，說明該試卷的難度分布越接近用戶預期要求，適應度越好。

因此， 該試卷的總體適應度值 fmin=f1+f2+f3，fmin越小越好，是最小化問題。本研究采用如下方法將目標函數fmin轉化為適應度函數 fmax：

因為指數比例既可以讓非常好的個體保持多的復制機會，同時又限制了其復制數目以免其很快控制整個群體，提高了相近個體間的競爭，所以對上述適應度函數fmax采用如下指數比例變換方法轉換為適應度函數F:

式中，β=0.06。

2.3 選擇算子

2.4 交叉算子

將以上選出的個體進行兩兩隨機配對，對每一對相互配對的個體采用有條件的“均勻交叉”，即2個配對個體的每一個基因座上的基因都按一定的交叉概率Pc和一定的條件進行交換，產生2個新個體[4]。

本研究對于交叉概率Pc的確定采用自適應的交叉概率。簡單遺傳算法中，交叉率是個常數，而實際上，優良的交叉率與遺傳代數的關系較大。在迭代初期，交叉率選擇得大一些可以造成足夠的擾動，從而增強遺傳算法的搜索能力，而在迭代后期，交叉率選得小一些可以避免破壞優良基因，從而加快收斂速度。因此，本研究選擇的交叉概率是個能隨著演化不斷調整的函數，稱為變交叉概率。交叉概率計算公式為：

Pc′是第 t代的交叉概率，Pc，max為最大交叉概率 ，取0.7，Pc，min是最小交叉概率，取值為 0.5，t為遺傳代數，tmax是最大遺傳代數。由于遺傳代數t是變化的，所以交叉概率 Pc′是隨代數 t而改變，除非 Pc′總是小于 Pmin。 每次交叉根據選擇概率判定當前是否進行交叉，如果要交叉，則隨機選出一對個體，在2個體中分別隨機選擇1個交叉位進行交叉。對2個配對個體的每一個基因座上的基因，先隨機產生 1個 0～1的實數 r1，如果 r1＜Pc并且滿足交換條件(即交換后個體的各個基因不重復)，則交換該基因座上的基因，否則不交換。

2.5 變異算子

由于普通的變異操作可能會使用戶指定范圍外的題目出現在染色體中，也會使各題型的題目數難以保證，本研究采用有條件的變異算子，即每個個體的每一個基因座上的基因都按一定的變異概率Pm在一定的范圍內進行變異。

同樣，本研究的變異概率也采用自適應變異概率。在簡單遺傳算法中，變異率是個常數。通常對于交叉率是常數的情況，群體的素質會趨于一致，這樣就形成了近親繁殖。群體基因的多樣性變差不僅會減慢進化歷程，也可能會導致進化停滯，過早收斂于局部最優解。因此，變異概率也能隨著演化不斷調整，由于概率表達式中含有遺傳代數t，這個概率稱為變動變異概率。變異概率計算公式為：

t為遺傳代數，tmax為最大遺傳代數，Pm，max為最大變異概率， 取值為 0.15，Pm，min是最小變異概率， 取值為0.01，λ為常數，取值為10。每次變異通過交叉概率判斷當前是否變異。對于個體的每一個基因座上的基因，先隨機產生 1個 0～1的實數 r1，如果 r1＜Pm，則根據一定的變異條件，即從備選題庫中抽取一道同類型同分值的試題，同時保證該題不存在于該份試卷中，替換該基因座上的基因，否則不變異。

2.6 保存最優策略

為了保證優良個體在選擇的過程中不被淘汰，對當前代進行了選擇、交叉、變異操作產生新一代后，比較新一代的最好個體與其父代的最好個體的適應值，如果下降，則以父代最好個體替換新一代的最差個體。此策略可以保證迄今為止的最優個體不會被交叉、變異等遺傳運算所破環，它是遺傳算法收斂性的一個重要保證條件。

3 試驗結果及分析

為了驗證上述算法的可行性和有效性，利用一門計算機課程的題庫進行研究，該題庫中有1000道題，其題庫結構如下。

(1)組卷10套，總分為100分，題型分配如表1所示。

表1 題型分配表

(2)預期平均分為70分，經過計算得出預期難度分配為：

易:中等偏易:中等偏難:難=20:36:31:13

(3)要求考核點覆蓋率達到70%以上，平均區分度在0.3～0.7之間，平均難度為中等偏易或中等偏難等級，考核點覆蓋率(即重點:次重點:一般)接近 5:3:2。

(4)章節分值分布如表2所示。

表2 章節分值分布表

實驗設置最大迭帶代數GenMax=100，允許誤差ei=2分，群體規模GenSize=100，結果各章的分布基本滿足預期要求，難度和考核點類型比例基本接近正態分布，平均難度維持在第2～3等級之間，區分度在0.4～0.7之間，考核點覆蓋率基本到達70%以上。目前該算法已在自學考試命題中試用，以便今后進一步推廣。

[1]余勝泉，姚顧波，何克抗.通用試題庫組卷策略算法[R].2000.

[2]曾一，冉忠，郭永林.試題庫中自動組卷的算法及試卷測評策略[J].計算機工程與設計，2006(8):3024-3027.

[3]張愛文，樊紅蓮.自適應遺傳算法用于自動組卷中的數學模型設計[J].哈爾濱理工大學學報，2006(11):18-20.

[4]MEHMET Y.Heuristic optimization methods for generating test from a question bank[M].MICAI 2007:Advances in ArtificialIntelligence， Springer Berlin/Heidelberg， 2007:1218-1229.