基于自適應(yīng)技術(shù)的教育類課程考試智能組卷方法

羅少華

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

0 引言

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

1 問題描述

1.1 約束指標(biāo)

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

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

(2)區(qū)分度，用于對參考人員的學(xué)習(xí)水平進(jìn)行區(qū)分，需要說明的是，區(qū)分度與試卷題目難度不成正比關(guān)系。

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

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

1.2 目標(biāo)矩陣

假定m為試卷中題目的數(shù)量，am1為單個題目分值，am2為單個題目難度系數(shù)，am3為區(qū)分度，am4為單個題目答題時間，am5為題目類型，am6為題目對應(yīng)的知識點，則解空間中Dm×6的目標(biāo)矩陣的表達(dá)式為

(1)

2 算法及其流程

2.1 算法機理

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

本文所設(shè)計的粗粒度并行遺傳算法的優(yōu)點在于算法流程通暢且易于實現(xiàn)，其收斂性弱于傳統(tǒng)遺傳算法，最優(yōu)解所在進(jìn)化代數(shù)比傳統(tǒng)遺傳算法高，由此可以證明多子種群并行遺傳能夠?qū)崿F(xiàn)種群的多樣性，同時，該算法最優(yōu)解方差較小，又說明了其穩(wěn)定性高于傳統(tǒng)遺傳算法。粗粒度并行遺傳算法在優(yōu)化目標(biāo)數(shù)量較多的情況下能夠提供合理的參數(shù)設(shè)定方案，因此有較高概率在不增加計算步驟的基礎(chǔ)上取得更好的運算結(jié)果。

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

運用統(tǒng)計學(xué)原理對子種群適應(yīng)度差異進(jìn)行量化統(tǒng)計，在運算過程中監(jiān)測細(xì)胞遷移的頻率和數(shù)量，能夠在很大程度上加快并行遺傳算法的收斂過程，同時繞過局部最優(yōu)解，縮小數(shù)據(jù)交換帶寬。

2.2 算法流程

子種群細(xì)胞遷移的過程中各子種群進(jìn)行最優(yōu)細(xì)胞互換，為了提升各子種群適應(yīng)度差異的計算速度，篩選出各子種群的最優(yōu)細(xì)胞，基于方差對子種群最優(yōu)細(xì)胞的適應(yīng)度差異進(jìn)行計算，即

(2)

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

假定t為遷移闕值，在Pi≥t的條件下細(xì)胞開始遷移,則遷移細(xì)胞數(shù)量的自適應(yīng)性表達(dá)式為

Ni=Pi(pN)

(3)

式中，Ni代表進(jìn)化到第i代是發(fā)生細(xì)胞遷移的子種群數(shù)量，p代表假設(shè)的最高遷移率，N代表子種群細(xì)胞數(shù)量。

所設(shè)計的算法流程如圖1所示。

圖1 算法流程

2.3 遷移拓?fù)?/h3>

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

圖2 環(huán)狀拓?fù)溥w移模型

3 組卷算法設(shè)計及優(yōu)化

3.1 編碼策略

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

3.2 種群初始化

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

3.3 調(diào)用適應(yīng)度函數(shù)

適應(yīng)度值能夠體現(xiàn)細(xì)胞的優(yōu)劣，值越大、細(xì)胞基因越好。適應(yīng)度函數(shù)大多由目標(biāo)函數(shù)轉(zhuǎn)換而來，能夠決定算法的性能。

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

適應(yīng)度函數(shù)f通過SVM原理來檢測細(xì)胞與遷移目標(biāo)種群的距離，距離最小者為最佳遷移目標(biāo)?？紤]到約束指標(biāo)在組卷過程中存在重要性的差異，因此需要評定每一個約束指標(biāo)的優(yōu)先級，優(yōu)先級越高，題目選取時所占權(quán)重越大。

f=η/F

(4)

式中，η代表懲罰因子，F(xiàn)代表細(xì)胞評估函數(shù)。經(jīng)過k+1代進(jìn)化后懲罰因子的表達(dá)式為

(5)

式中，fkmax代表最大適應(yīng)度值，fki代表經(jīng)過k代進(jìn)化后第i個細(xì)胞的適應(yīng)度，n代表子種群細(xì)胞數(shù)量。

(6)

3.4 遺傳算子

(1)算子選取

在研究的過程中基于精英保留策略來保證種群進(jìn)化的行效率，優(yōu)良細(xì)胞直接進(jìn)入下一代進(jìn)化，其余細(xì)胞通過轉(zhuǎn)輪賭的方式進(jìn)行選取。種群中當(dāng)個細(xì)胞被選中的概率為

(7)

式中，F(xiàn)it(i)代表第i個細(xì)胞的適應(yīng)度，popsize代表種群體形大小。當(dāng)任意細(xì)胞的選擇概率計算完成時，系統(tǒng)會自動隨機生成一個取值區(qū)間為(0，1)的數(shù)組，用數(shù)組的值與細(xì)胞選擇概率值進(jìn)行對比，若前者大于后者，則該細(xì)胞被選取并進(jìn)入下一代進(jìn)化，否則將被剔除。

(2)交叉算子

本文基于單點交叉法對算法進(jìn)行完善。具體過程為：在細(xì)胞序列中隨機選定一處交叉點，進(jìn)行交叉操作，互換交叉點前后細(xì)胞的部分結(jié)構(gòu)，進(jìn)而創(chuàng)建2個新的細(xì)胞。

(3)變異算子

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

3.5 遺傳的自適應(yīng)設(shè)計

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

(1)交叉概率計算

交叉概率Pc的計算式為

(8)

式中，Pc1和Pc2分別取0.9和0.6，f代表當(dāng)前細(xì)胞的自適應(yīng)度，favg代表種群所有細(xì)胞的平均自適應(yīng)度。

(2)變異概率計算

(9)

式中，Pm1和Pm2分別取0.1和0.001，f代表當(dāng)前細(xì)胞的自適應(yīng)度，favg代表種群所有細(xì)胞的平均自適應(yīng)度。

3.6 算法終止條件

在出現(xiàn)以下3種情況的條件下終止算法的運行：

(1)已經(jīng)發(fā)生的遺傳代數(shù)超過限定代數(shù)值；

(2)最優(yōu)細(xì)胞與目標(biāo)細(xì)胞的差值已經(jīng)小于閾值；

(3)當(dāng)前遺傳代的最優(yōu)細(xì)胞與上一代最優(yōu)細(xì)胞的差值已經(jīng)小于閾值。

4 應(yīng)用驗證

通過自動組卷實驗對本文所設(shè)計的與傳統(tǒng)PGA算法[5]進(jìn)行性能對比，以驗證本文所設(shè)計算法的應(yīng)用效果。

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

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

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

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

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

圖4 PGA與HPAGA收斂速度對比結(jié)果

5 總結(jié)

傳統(tǒng)的遺傳算法在自動組卷過程中普遍存在執(zhí)行效率低下、試卷質(zhì)量難以保證的問題，為此，本文基于自適應(yīng)技術(shù)對并行遺傳算法進(jìn)行了優(yōu)化，介紹了算法優(yōu)化機理及實現(xiàn)流程，闡述了算法的設(shè)計過程和優(yōu)化方式，并通過實驗證明了本文所設(shè)計的算法相較于傳統(tǒng)算法在算法性能和執(zhí)行效率上均具有明顯的優(yōu)勢?；谧赃m應(yīng)技術(shù)的并行遺傳算法實現(xiàn)了種群遷移的高效性和和遺傳效果的顯著性，能夠通過自動組卷技術(shù)的改進(jìn)對輔助教學(xué)的研究起到良好的促進(jìn)作用。