基于自適應技術的教育類課程考試智能組卷方法

羅少華

(西安思源學院， 教育學院， 陜西， 西安 710038)

0 引言

在大數據管理日益成熟的條件下，通過計算機技術對教學題庫進行深入的數據挖掘，自動生成高質量的考試試卷，對于輔助教學的研究具有重要意義[1-2]。當前教學領域中用于組織試卷內容的各種考試題目管理系統算法陳舊且隨機性過強，嚴重影響了試卷的生成速度和知識考核質量[3-4]。為了解決這些問題，本文提出并設計一種經過優化的并行遺傳算法，將自適應技術引入到遺傳算法的種群遷移過程中，加快種群間優秀個體的遷移速度，進而實現高質量試卷的快速自動生成。仿真實驗結果表明，優化后的并行遺傳算法適應度更高、運行速度更快，對于智能組卷具有較強的實用性。

1 問題描述

1.1 約束指標

試卷內容的組織需要綜合題量、考察知識點、考察題型、考試時間、區分度、難度系數、試卷總分、章節考察均衡等多種因素進行。試卷的內容必須滿足幾個方面的要求，包括出題頻率、題目相關性、能力要求(記憶、運用、邏輯運算)、層次要求(熟悉、掌握、理解等)等。對于自動組卷的過程，組卷需求越多則效率會相應地降低。為了改善題庫管理系統試卷生成模塊的通用性和普適性進行了大量的同質分析，總結出試卷生成約束所涉及的幾個指標如下:

(1)題目難度，即試卷題目對于參考人員的答題難易度，用于體現試卷的學習成果考察層次。

(2)區分度，用于對參考人員的學習水平進行區分，需要說明的是，區分度與試卷題目難度不成正比關系。

(3)試卷總分與考試時間。這兩項指標是對考試的基本要求，用于體現得分標準與特定的答題時間需求。

(4)章節契合度，用于體現試卷整體上考察知識點分布的契合度。

1.2 目標矩陣

假定m為試卷中題目的數量，am1為單個題目分值，am2為單個題目難度系數，am3為區分度，am4為單個題目答題時間，am5為題目類型，am6為題目對應的知識點，則解空間中Dm×6的目標矩陣的表達式為

(1)

2 算法及其流程

2.1 算法機理

以粗粒度處理為前提的并行遺傳算法依據處理器群的規模將原始種群分割成多個體形較大的子種群，單個處理器中的子種群獨立開展遺傳繁殖，在經歷一定代數的進化過程后，各子種群間進行優良細胞的交換，從而實現子種群的并行遺傳和共同進化。現有的研究結果表明，粗粒度并行遺傳算法相較于其他算法在遺傳結果方面具有較大優勢。

本文所設計的粗粒度并行遺傳算法的優點在于算法流程通暢且易于實現，其收斂性弱于傳統遺傳算法，最優解所在進化代數比傳統遺傳算法高，由此可以證明多子種群并行遺傳能夠實現種群的多樣性，同時，該算法最優解方差較小，又說明了其穩定性高于傳統遺傳算法。粗粒度并行遺傳算法在優化目標數量較多的情況下能夠提供合理的參數設定方案，因此有較高概率在不增加計算步驟的基礎上取得更好的運算結果。

通過本文所設計的算法處理多峰值模型時，需要在設定的進化代數按照一定比例完成子種群細胞遷移。在子種群進化的前半階段中，子種群的組成細胞是被隨機選定的，各子種群的適應度存在較大差異，只發生小規模的細胞遷移，因此，算法收斂以較慢的速度進行；而在子種群進化的后半階段各子種群的適應度大多很快就會實現局部最優的狀態，子種群適應度差異較小，且正在發生大規模、高頻率的細胞遷移，很容易止步于局部最優解。由此可見，細胞遷移的規模和頻率能夠決定子種群間的數據交互量，是算法性能的決定因素。

運用統計學原理對子種群適應度差異進行量化統計，在運算過程中監測細胞遷移的頻率和數量，能夠在很大程度上加快并行遺傳算法的收斂過程，同時繞過局部最優解，縮小數據交換帶寬。

2.2 算法流程

子種群細胞遷移的過程中各子種群進行最優細胞互換，為了提升各子種群適應度差異的計算速度，篩選出各子種群的最優細胞，基于方差對子種群最優細胞的適應度差異進行計算，即

(2)

式中:Pi代表進化到第i代的子種群的適應度分布率，其數值范圍為(0，1)，數值越大、離散度越高;fj代表經過i代進化后第j個子種群中最優細胞的適應度;fmax代表i代進化后種群中全部最優細胞的適應度;n代表子種群數量。

假定t為遷移闕值，在Pi≥t的條件下細胞開始遷移,則遷移細胞數量的自適應性表達式為

Ni=Pi(pN)

(3)

式中，Ni代表進化到第i代是發生細胞遷移的子種群數量，p代表假設的最高遷移率，N代表子種群細胞數量。

所設計的算法流程如圖1所示。

圖1 算法流程

2.3 遷移拓撲

由于細胞的多樣性特征，子種群間只交換基因最好的細胞，在這種條件下一對一的遷移模式能夠加快收斂速度并提高解的精度，因此選取圖2所示的環狀拓撲遷移模型為研究對象。

圖2 環狀拓撲遷移模型

3 組卷算法設計及優化

3.1 編碼策略

為了控制信息的長度，減輕通信載荷，細胞使用非固定長度實數進行編碼，通過向量X=(x1,…,xm)T視為單個細胞用于代表一個解。在細胞內部依據題目類型分段進行編碼。

3.2 種群初始化

在系統搜索的開始階段，為了保證子種群的差異化，其初始化以隨機的方法進行。設定組卷過程中子種群的數量為n，利用隨機函數在符合條件的題目中隨機選取m個來構建單個細胞。

3.3 調用適應度函數

適應度值能夠體現細胞的優劣，值越大、細胞基因越好。適應度函數大多由目標函數轉換而來，能夠決定算法的性能。

以SVM(支持向量機)為理論基礎在線性可分的條件下開展分析，在出現線性不可分的情況時，需要基于非線性映射函數把處于低維度空間的不可分樣本映射至高維度特征空間，使其具有線性可分的性質，進行實現線性可分的普適性。

適應度函數f通過SVM原理來檢測細胞與遷移目標種群的距離，距離最小者為最佳遷移目標。考慮到約束指標在組卷過程中存在重要性的差異，因此需要評定每一個約束指標的優先級，優先級越高，題目選取時所占權重越大。

f=η/F

(4)

式中，η代表懲罰因子，F代表細胞評估函數。經過k+1代進化后懲罰因子的表達式為

(5)

式中，fkmax代表最大適應度值，fki代表經過k代進化后第i個細胞的適應度，n代表子種群細胞數量。

(6)

3.4 遺傳算子

(1)算子選取

在研究的過程中基于精英保留策略來保證種群進化的行效率，優良細胞直接進入下一代進化，其余細胞通過轉輪賭的方式進行選取。種群中當個細胞被選中的概率為

(7)

式中，Fit(i)代表第i個細胞的適應度，popsize代表種群體形大小。當任意細胞的選擇概率計算完成時，系統會自動隨機生成一個取值區間為(0，1)的數組，用數組的值與細胞選擇概率值進行對比，若前者大于后者，則該細胞被選取并進入下一代進化，否則將被剔除。

(2)交叉算子

本文基于單點交叉法對算法進行完善。具體過程為：在細胞序列中隨機選定一處交叉點，進行交叉操作，互換交叉點前后細胞的部分結構，進而創建2個新的細胞。

(3)變異算子

基于基本變異法進行算法的簡化，具體做法是在完成細胞的實數編碼后，從編碼串中隨機選中一個或多個編碼并改變其數值。

3.5 遺傳的自適應設計

通過自適應遺傳算法可以同時保證子種群的收斂性與多樣性。改變交叉、變異的概率會對細胞的適應度產生較大影響，在適應度數值向局部最優或整體一致的方向變化時，應增大交叉與變異的概率；而當適應度差異較大時，則應減小對應的概率值。那些適應度數值比整體平均值大的細胞都應作降概率處理并延續到下一代進化過程，其余低于平均值的細胞將會被從種群中移除。因此必須對交叉和變異的概率進行精確計算，才能保證算法的整體適應性處于較高水平。

(1)交叉概率計算

交叉概率Pc的計算式為

(8)

式中，Pc1和Pc2分別取0.9和0.6，f代表當前細胞的自適應度，favg代表種群所有細胞的平均自適應度。

(2)變異概率計算

(9)

式中，Pm1和Pm2分別取0.1和0.001，f代表當前細胞的自適應度，favg代表種群所有細胞的平均自適應度。

3.6 算法終止條件

在出現以下3種情況的條件下終止算法的運行：

(1)已經發生的遺傳代數超過限定代數值；

(2)最優細胞與目標細胞的差值已經小于閾值；

(3)當前遺傳代的最優細胞與上一代最優細胞的差值已經小于閾值。

4 應用驗證

通過自動組卷實驗對本文所設計的與傳統PGA算法[5]進行性能對比，以驗證本文所設計算法的應用效果。

實驗從計算機專業“數據庫原理”(王珊，清華大學出版社，2018)一書的練習題庫中選擇題目進行自動組卷，該題庫共包含10 521道題目，其章節題量、知識點考察、題目難度分布較為均勻。

試卷約束指標參數設定為試卷總分值100分，答題時間120 min，難度系數為0.3，區分度為0.5，章節題目契合度為0.8。種群初始體形大小為50，數量為24個，限定最高遺傳代數為100。

分別基于2種算法完成自動組卷實驗，每種算法重復200次，算法的收斂速率通過100次遺傳的平均耗時進行計算，通過本文算法所生成的“數據庫原理”試卷如圖3所示。實驗結束后對比2種算法的遺傳收斂速率及種群適應度。

經過對比，本文算法100代迭代平均耗時14.62 s，傳統PGA算法100代迭代平均耗時18.72 s。收斂速度對比如圖4所示。由此可見，本文所設計的算法在最優適應度和遺傳效率2個方面都比傳統PGA算法更具優勢，且隨著遺傳代數的增多其優勢也隨之持續擴大。應用本文算法的考試題目管理系統已在多所院校投入使用，師生們普遍反映該系統所生成的各科試卷知識點覆蓋面廣，章節分布均勻且難易程度適中，能夠科學地考查學生們對所學課程的掌握情況，因此給予一致好評。

圖3 基于本文算法所生成的“數據庫原理”試卷

圖4 PGA與HPAGA收斂速度對比結果

5 總結

傳統的遺傳算法在自動組卷過程中普遍存在執行效率低下、試卷質量難以保證的問題，為此，本文基于自適應技術對并行遺傳算法進行了優化，介紹了算法優化機理及實現流程，闡述了算法的設計過程和優化方式，并通過實驗證明了本文所設計的算法相較于傳統算法在算法性能和執行效率上均具有明顯的優勢。基于自適應技術的并行遺傳算法實現了種群遷移的高效性和和遺傳效果的顯著性，能夠通過自動組卷技術的改進對輔助教學的研究起到良好的促進作用。