基于定向變異遺傳算法的智能組卷算法研究

胡新源，趙當麗，李 輝，張向波，韓振興

（1.中國科學院國家授時中心，陜西 西安 710600；2.中國科學院大學，北京 100049；3.中國人民解放軍63768部隊，陜西 西安 710600）

隨著在線考核在現代教學方式中占比逐漸增大，實現準確、高效的智能組卷算法已成為現代教育研究的一個熱點。文獻[1-2]對幾種智能算法應用在組卷問題上的性能做出了比較，目前解決組卷問題主要依賴遺傳算法[3-4（]Genetic Algorithm，GA），但是由于組卷問題數學模型較復雜，導致基于標準遺傳算法（Standard Genetic Algorithm，SGA）的組卷算法存在明顯尋優能力弱、易早熟收斂陷入局部最優等GA常見問題。文獻[5]根據組卷約束條件人為選取初始種群，提高初始種群的適應度。文獻[6-8]提出混合遺傳算法以提升算法性能，文獻[9]提出一種自適應遺傳算法（Adaptive Genetic Algorithm，AGA），通過自適應調整交叉變異概率提升組卷效率。但是以上優化對于遺傳算法的性能提升均有限。文獻[10]提出一種定向變異遺傳算法（Directional Variation Genetic Algorithm，DVGA）的思想，對算法性能提升取得較好的效果。為進一步改善GA的尋優能力，該文基于以上研究基礎，結合組卷模型進一步加強算法的定向尋優能力，同時降低了組卷時間，具有良好的性能。

1 智能組卷數學模型構建

組卷算法的目的在于根據給出的限制條件，從題庫中自動抽選符合條件的試題組卷，其數學本質是在多維約束條件下求全局最優解問題[11],。解決此類問題需要確定一個目標函數及多個約束條件，在組卷問題中，約束條件即為題目的各項屬性，因此每道試題可以通過一維向量Q=(a1,a2,a3,…,an)來描述，n表示每道試題需要被約束的屬性總數。包含m道試題的題庫則構成一個m×n的矩陣D[12]，如下所示：

組卷的過程即為從題庫矩陣D中選取一個滿足各約束條件的子集矩陣的過程，該組卷模型將以難度、章節、曝光時間、題型、分數5個屬性作為約束條件，各屬性約束和目標函數的選取如下所示。

1）難度：試卷的難度約束應為試卷各試題的平均難度，用于區分考生水平。

式（2）中，ai1表示第i題的難度值，d表示預期的試卷整體難度，n表示該試卷中題目總數。

2）章節：章節用于約束試卷考察知識范圍，需對試卷逐題判斷是否屬于目標章節。

式（3）中，ai2代表第i題的考察章節，S代表指定的章節范圍。

3）曝光時間：曝光時間表示該題目距離上次被抽取用于組卷的間隔時長，需逐題判斷，用于避免題目頻繁出現。

式（4）中，ai3表示第i題的曝光時間，T代表最低未被組卷使用的間隔次數。

4）題型：通常試卷的題型結構是固定且可枚舉的，需逐題判斷整卷的各題型是否符合指定數量。

式（5）中，t代表試卷中總題型數，tn代表每個題型的預設數量，tj為形如f2的函數，用于統計試卷中各題型數量，tj中以ai4代表第i題的題型。

5）分數：分數屬性需要統計整卷所有試題分數求和，且應允許一定的誤差。

式（6）中，ai5代表第i題分數，其中P為預設試卷總分數，δ為可接受的誤差范圍。

2 基于遺傳算法的組卷

GA被廣泛應用在組卷問題中，具體思路為：針對組卷問題進行基因編碼、適應度函數的設計，選取合適的遺傳算子后即可抽取一定數量的試卷作為初始種群，進行選擇交叉變異，直到種群中最優個體滿足指定條件。種群中最優個體即為滿足約束的目標試卷。

2.1 基因編碼

GA中種群中的個體需用基因編碼表示，通常采用二進制編碼來描述個體[13]。當應用在組卷問題時，個體的基因編碼即為試卷所包含的試題編號，若采用二進制編碼時，題庫中的每個題都需要出現在編碼中，極大地浪費了編碼效率。其次，在每次交叉變異的過程中需對試題題型進行判斷，引入了大量計算。文獻[14]提出一種實數分段式編碼，以試題編號實數為基因，按試題題型分段編碼，如下所示。

式（7）中，Qi表示試卷中的第i種題型，共計t種題型，每種題型ni道。采用實數分段式編碼時，基因編碼長度僅為試卷試題總數，極大提升了編碼效率，且各題型在試卷染色體中位置固定，因此在交叉操作中可省略對題型的判斷[15]，如圖1所示。

圖1 采用實數分段式編碼的交叉操作

2.2 適應度函數

適應度函數用來評判個體的優劣性，應滿足單值、非負及合理反映個體優劣程度等要求，根據已建立的組卷模型可知適應度應為各項約束條件求加權和。

上式中，c用于保證目標函數的非負性，ωi表示各項約束條件在目標函數中的權重。其中，。

2.3 初始種群選取

根據已建立的組卷模型可知，組卷約束條件分為難度、題型、分數等需要統計整卷判斷和章節、曝光時間等逐題判斷兩種類型。由于目標試卷中每道試題必定滿足第二類需逐題判斷的約束條件，因此當確定約束條件后，可根據指定的章節及曝光時間對題庫進行篩選形成基因庫G。結合編碼結構的題型設置，從中抽取一定數量的試卷作為初始種群，可使得初始種群有一個較高的適應度，加速算法收斂。

2.4 遺傳算子設計

GA中的遺傳算子分為選擇算子、交叉算子、變異算子三部分。

選擇算子控制著進化過程中的篩選作用，為了符合優勝劣汰的規律同時又不喪失種群物種多樣性，通常采用輪盤賭方法。同時為了避免最優個體在進化過程中丟失，采用精英策略保留當代最優個體，使最優個體無需經過選擇交叉及變異直接進入下一代。

交叉算子用于模擬種群進化過程中的繁衍過程，通常采用單點交叉的方式，通過選擇算子選取父母個體以交叉概率Pc進行交叉。

變異算子用來模擬種群進化過程中個體產生基因突變的情況，用于維持種群的多樣性，決定了算法的搜索能力，通常采用單點變異，種群中個體以概率Pm進行變異，由于組卷模型存在題型約束，因此變異結果應從同題型試題中抽取。

2.5 終止條件

組卷即為求適應度函數最大值的過程，當種群中最優個體達到指定要求或達到指定的進化次數后停止進化，最優個體即為滿足預設目標的試卷。

3 基于定向變異遺傳算法的組卷

3.1 遺傳算子的改進

GA中交叉概率Pc和變異概率Pm對于算法尋優能力和收斂速度有著重要影響，自AGA被提出以來，眾多優秀的改進自適應遺傳算法陸續被提出[16]，該文采用基于Sigmoid曲線改進的自適應遺傳算子來進一步提升算法尋優能力。

上式中，A=9.903 438，Pcmax、Pcmin表示交叉概率最大值及最小值，Pmmax、Pmmin表示變異概率最大值及最小值，f′表示進行交叉的父母個體中較大的適應度，favg表示當代種群平均適應度，fmax表示當代種群最大適應度，f表示發生變異個體的適應度。

3.2 變異操作的改進

根據前文實數分段式編碼結構及GA流程可知，在一次完整的組卷過程中，交叉操作只會改變各試卷的試題組合，而不會從總題庫中抽取新的試題，僅在變異操作過程中會引入新的試題。因此，從基因庫G中抽取試題作為變異結果，可確保由變異操作產生的新試題，在章節及曝光時間等需逐題判斷的約束條件下直接滿足目標。且由于初始種群也在基因庫G中選取，因此在一次完整的組卷過程中，種群個體的基因即各試題始終滿足章節及曝光時間等需逐題判斷的約束條件，適應度函數中關于章節及曝光時間的權重系數ω2、ω3可置為0，從而可以使得該組卷模型從五維約束條件簡化為三維約束條件。

由于GA基于優勝劣汰的法則，當種群進化到中后期往往存在嚴重同化現象即陷入局部最優，此時由于種群同化嚴重，交叉操作已幾乎不能產生新試卷個體，主要依賴變異產生優良試卷個體跳出局部最優，而隨機變異會使得種群在長時間內無法跳出局部最優。因此需對變異方向加以控制，使其只能朝著更優定向變異。定向變異是指當發生變異時，計算發生變異個體變異前的適應度f(x)與變異后的適應度f′(x)，僅當f(x)

基于以上約束目標屬性及適應度的DVGA的組卷算法，不僅縮小了組卷過程尋優的搜索空間，同時還限定了變異方向，使得個體只能朝著全局最優發生變異，種群更易跳出局部最優，極大地提升了算法的尋優能力，同時簡化了組卷過程的計算量，從而提升了組卷效率。

3.3 改進遺傳算法

基于上述對遺傳算子和變異操作過程的改進，可得到基于DVGA的組卷算法流程如圖2所示。

圖2 基于DVGA的組卷算法流程

4 仿真驗證

為了驗證文中提出的基于DVGA的組卷算法對組卷性能的提升，進行如下實驗，設置參數如表1所示。

表1 參數設置

結合上述流程圖進行編程仿真，可以得到在相同條件下，各算法最大適應度如圖3所示。

圖3 3種算法種群最大適應度比較

同時，以表1條件進行20次試驗，分別對SGA、AGA、DVGA平均組卷準確率、收斂代數及運行時間進行比較，可得到表2及圖4結果。

表2 3種算法組卷準確率比較

圖4 3種算法收斂代數及算法耗時

從圖3可以看出，該文提出的DVGA相比于AGA及SGA，具有更強的尋優及跳出局部最優的能力。表2及圖4表明，該文提出的DVGA準確率及組卷效率相較于SGA及AGA均取得較大的提升。

5 結束語

智能組卷問題本質是對多約束多目標的問題尋求最優解。該文充分利用組卷模型中約束條件的特性，優先篩選出帶有部分最優特性的優良基因庫，使變異從中產生且定向只可朝著最優變異，極大地縮短了組卷時間，提高了組卷效率。