一種基于遺傳算法的智能組卷策略優化研究?

賀建英 王光瓊 唐青松

（1.四川文理學院智能制造學院 達州 635000）（2.達州智能制造產業技術研究院 達州 635000）

1 引言

隨著高校人才培養模式的不斷改革，“一科多考”的考核方式順理成章的被提出。在考核中提出從多維度進行考核，如考試內容、命題、評價等，且能得到多元動態考試評價體系。然而“一科多考”的提出無形中加大了教師的工作量，一門課程多次出題，多次閱卷、多次對試卷進行評價分析。繁瑣的工作讓大家不約而同想到在人工智能高速發展的今天，在線考試系統帶來的優勢。當前智能組卷技術及其相關算法是現今高校信息化建設中研究的熱點技術之一，通過高質量的試題庫和優秀的組卷策略生成滿足多種約束條件的試卷，然后使用終端設備同步在線考試?？荚囅到y的另一個優勢在于可減少教師閱卷和評卷工作量。系統的閱卷工作可以采用機器閱卷和人工閱卷相結合的方式。試卷的評價則根據系統的各項參數設置及學生的最終考試成績自動生成試卷評價信息。通過信息化建設達到無紙化考試的目的。

當前自動組卷策略主要分為四類［1］：1）隨機組卷算法；2）回溯組卷算法；3）演化式計算方法；4）遺傳算法。隨機抽取組卷算法非常簡單，對單個題的抽取速度快［2］，但因有相應的控制指標，使得組卷的成功率較低；而回溯算法是基于隨機抽取方法的算法，是基于它的一種改進方法。對少量題目和題量的自動組卷來說，組卷成功率很高。但它是基于隨機抽取算法的，故存在隨機性，導致組卷時間長，內存消耗大，難以滿足用戶實時的抽題需要；演化式計算方法主要包含遺傳算法和粒子優化算法這兩種演化式算法。遺傳算法（Genetic Algorithm，GA）是一種模擬自然界的進化規律，通過選擇、交叉、變異從上一代種群中產生下一代個體并組成新的種群，逐漸把適應度低的個體淘汰掉，達到最優的搜索查詢結果。遺傳算法在自動組卷中應用的好壞主要取決于如下幾個因素［3］：1）最大進化次數及停止進化的條件；2）評價個體質量的適應度，以得到最優秀的個體；3）通過選擇來得到優秀個體從而產生下一代，通過選擇來決定種群的進化方向；4）通過交叉算法得到兩個個體繁衍的下一代，實現基因重組；5）通過變異實現種群個體的多樣化。

本文在傳統遺傳算法的基礎上，從試題的編碼方法、建立加權目標函數來優化適應度函數、交叉算子的選擇、變異的設置以及到采用保優策略和輪盤賭相結合進行選擇操作等方面進行了優化設計。取得了很好的適應度，并能快速成功組卷，提高了組卷效率。

2 相關工作

當前許多學者對遺傳算法在自動組卷中的應用進行了研究，取得了一系列的研究成果。Gorgdberg M.W［4］建立了基于遺傳算法的智能組卷的尋優模型。陳國彬等［5］對組卷使用快速動態粗粒度并行遺傳算法，采用基于SVM（支持向量機）方式建立適應度函數對遺傳算法進行改進，取得了顯著的效果。焦翠珍等［6］提出使用十進制編碼方式來代替遺傳算法中的二進制編碼，大大縮減了組卷時間。陳宇等［7］對遺傳算法組卷過程中的約束條件的誤差進行優化，提出一種啟發式的遺傳組卷算法策略。任學惠等［8］提出一種基于遺傳算法的小生境技術，有效地約束了相似個體的繁殖。趙薈［9］提出一種優化組卷的各種約束條件來提高組卷質量和效率。肖慶理等［10］提出一種在組合遺傳算法的基礎上，對精英策略進行改進，與單個的純粒子算法、遺傳算法及其改進算法都有一定的優勢。周艷麗［11］提出使用分段交叉和變異算子，采用加權誤差的適應度函數快速收斂的方式，有效解決了組卷中的問題。路寬等［12］將群體中的所有元胞按照一定的演化規則演化之后再進行遺傳，提出一種新的元胞遺傳組卷算法。

3 組卷理論及數學模型

3.1 組卷理論

自動組卷實質上是一個目標函數和多個約束條件的組合。一般需要滿足如下指標要求：1）試題所包含的知識點；2）試題所屬的題型；3）試題在教學中的層次要求；4）試題對學生能力的要求；5）試題的難度級別；6）試題對學生能力的區分程度；7）學生完成試題所需要的時間；8）試題的難度系數；9）試題的分數；10）試題在題庫中的選中率。對生成的試卷還需要包括：1）試卷總分；2）知識點分布；3）試卷難度；4）考試時間；5）知識點；6）題型分數；7）能力層次；8）試卷區分度等多個約束條件。下面首先給出相關屬性的定義［9，13～14］：

定義1（試題難度）是指參與考試的學生群體在某一題上的失分率，如式（1）所示：

其中r是答錯該題的人數，n是做過該題的總人數。該值在系統中是動態變化的。

定義2（試題區分度）是指把該試題學生的得分從高到低排序，從前后各取一定比例的考生得分的平均值分別作為高分組h和低分組l。如式（2）所示：

其中d∈[0,1]，k為該試題的實際分值。

定義3（試題的知識點覆蓋率）設N為該試題所包含的知識點個數，M為一套試卷中要求應該包含的知識總數。此時其覆蓋率表示為式（3）所示：

其中N應是去重后的知識點個數即N≤M。

定義4（試題選中率）指試題被選中的頻率，可通過規定在某一段時間內使用過的不能再次使用，或者通過試題選中的頻率來控制。如式（4）所示：

其中Xc為試題被選中的次數，P為總的選中試題的個數。實際操作時，在條件都滿足的情況下優先考慮選擇選中率低的試題。

定義5（試卷的信度）指試卷測試結果的可靠程度。由試卷的真實方差和成績方差的比值進行定義，受測量偏差的影響。如式（5）所示：

其中Pn為試卷總的題數為第i題的方差，S2是組成的該套試卷的方差。當C＜0.7時，說明該試卷不可信。

定義6（試卷的效度）即試卷測試結果的正確性。如式（6）所示：

其中r＞0.4，Yi和Zi分別為第i個考生在本次測試與校標測試中的成績。Yi、Y'、Zi、Z'分別表示兩次測試的標準差與均值。Pt為參考考試的總人數。

定義7（試卷難度）指每個試題的難度與其分值相乘后的累加結果與總分值的比值。如式（7）所示：

其中Qi為第i題的試題難度，ki為第i個題的分值，n為總的試題數量，K為總分。

定義8（試卷區分度）通過試卷中每個試題的區分度與該試題分值相乘后的累加值與該套試卷總分的比值。如式（8）所示：

其中di為第i個試題的區分度。

3.2 智能組卷問題數學模型

智能組卷的實質就是滿足用戶的需求，通過用戶給定的初始值生成滿足多種條件約束的試卷。本文以《大學英語》為例建立試題庫。總共包含570道試題，題型包括聽力（單選）、單選題、閱讀理解（單選）、完型填空（單選）、翻譯、英文寫作。試題分布數分別為50、350、70、30、30、40。從試題庫中生成試卷時，假定需要組成一份試卷的試題數目為m，而對從試題庫中抽取的每一個試題都要符合選擇試題的指標屬性等相關條件。所生成的一套試卷用矩陣則可以表示為一個m*7的矩陣，如式（9）所示。

通過矩陣得到如下生成一套試卷的約束條件［6～7］：

1）試卷總分約束條件：

K值由用戶確定。

2）知識點層次分數分布約束條件：考試中根據大綱要求，有些知識點需要重點掌握，有些只要求理解，有些知識僅僅只是了解。故在知識點的考察方面就需要有側重點進行考核。設三個層次的知識點集合分別為Z1、Z2、Z3，對應的分數范圍為[S1,H1]，[S2,H2]，[S3,H3]，得到式（11）的約束條件：

其中 f1i、f2i、f3i分別為該試題在三個層次上的的知識點分布覆蓋率。其中試卷三個層次總的知識點覆蓋率約束為

表明生成的試卷中實際包含的知識點數與期望包含的知識點數的比值。已有研究表明該值大于80%時該生成的試卷達到要求。

3）試卷區分度分數約束條件：

其中 f4i為每題的區分度。

4）試卷難度系數對應的分數分布約束條件：

其中 f5i為每題的難度。

5）試卷的試題選中率分數條件約束：

其中 f6i為每題的選中率，其值越低，則生成的試卷間的差別越大。

6）試卷完成時間約束條件：

T的值應該小于等于用戶需求設定的考試時間。

7）試題題型分數分布約束條件：

其中 f7i為每題的題型。

3.3 目標函數的建立

根據生成試卷的多種約束條件，在組卷中均希望對每一個個體試題能得到最為理想的值，即期望值。然而往往真實值和期望值之間會存在一定的偏差。根據多種約束條件，設L表示試題層次知識點，D表示試題的區分度，O表示試題的難度，C為試題知識點。則試題的期望值與真實值的偏差分別表示為 EL、ED、EO、EC、EB，分別由式（18）～（21）所示［15］。

其中Lj表示第 j個層次中知識點的目標分數，j=1,2,3。m1為生成的試卷中知識點的總個數。

其中Di表示試卷中區分度為i的目標分數。m2為生成的試卷中區分度的總個數。

其中Oi為難度系數為i的目標分數。m3為難度級別的總個數。

其中Ci為選中率為為i的目標分數。

大學英語考試試題有一特點，當題型為聽力題時，根據同一場考試，聽力試題相同的原則，只要探測到某一個試卷個體中已經生成滿足條件的聽力試題部分，則在后續的遺傳中對該組試題直接遺傳，不再做任何操作使其進化。通過相關條件的約束，最后得到在組卷過程中的目標函數為式（23）所示：

其中ωi是各個約束條件在組成試卷時所占的權重，且

4 基于遺傳算法的自動組卷策略

4.1 編碼方案

研究表明遺傳算法是對基因的優勝劣汰。基因的長短決定了搜索效率的高低，基因過長導致搜索空間太大，遺傳效率低下。本文采用實數的編碼方式。每一個個體試題都有一個編號，該編號不會存在重復，把該編號作為遺傳算法中的編碼。按照不同的題型分段放在一起。大幅度減少了基因的長度，有效提高了搜索效率。本文中按大學英語課程考試的要求，設置六類題型。分別用L、C、R、S、T、W來表示，每類題型所生成的試題數量為m1、m2、m3、m4、m5、m6。則所生成的試卷編碼可表示為圖1所示。

其中的 li、ci、ri、si、ti、wi都是不同的實數。

圖1 基因編碼方式

4.2 相關操作的建立

在前面的分析中已經得知應滿足的因素中包括適應度函數、進化次數、結束條件以及變異的相關操作（選擇、交叉、變異）等。

4.2.1 適應度函數

適應度函數是用來評價一個群體中的單個個體優劣程度的值，該值越高其解越優，也能很好地控制搜索方向。已有研究表明，適應度的值與目標函數成反比，其目標函數的值越小，則適應度的越大。故適應度函數表示為式（24）所示［16～17］，這里t=2。

4.2.2 選擇操作

選擇操作的目的是對種群中的個體進行優勝劣汰，把優秀的個體進化遺傳到下一代。在遺傳過程中，有可能存在非常優秀的個體被淘汰的情況，故本文采用保優策略和隨機輪盤賭相結合的方式。即把種群中優秀的個體不需要做任何操作而直接遺傳到下一代，而剩下的個體則采用隨機輪盤賭的方法，通過判斷每一個個體可能被選擇的選中率來判斷是否被遺傳到下一代中。選擇率的計算可通過單個個體的適應度值與種群中每個個體的適應度值總和的比值Ci來確定。最后在［0，1］的區間上隨機生成一系列數組，如果隨機數組中的值大于個體被選擇的概率值Ci，則該個體被選中進入下一代。否則直接把該個體拋棄。Ci的表示方式如式（25）所示［4］：

其中g(xi)表示第i個個體的適應度的值，t表示種群的大小。

4.2.3 交叉操作

交叉操作是在種群中對兩個個體進行交叉操作。因聽力試題的編碼放在第一段內，根據分析，該部分題型在迭代過程中將直接遺傳到下一代。本文采用隨機在一個個體基因串的后面k-1段內和段間設置交叉點（k為基因的總段數），交叉后將生成兩個新個體。若交叉后出現相同的基因序列，則取消該交叉操作。

4.2.4 變異操作

因采用的是實數分段進行染色體編碼，不同的題型有不同的分段。故在變異操作時，對后k-1個分段內隨機選擇一個值進行變異，若變異之后的值在該段內已經存在，那么重新選擇變異點進行變異，否則直接把變異后的值替代原值。一般情況下設置基因的變異率在0.01左右。

4.2.5 結束操作

本文采用最簡單的遺傳代數達到規定的值時結束算法。

5 實驗與分析

系統采用MyEclipse10.0平臺進行設計實現，數據庫為MySql數據庫（包含570道試題）。為驗證上述算法的有效性，實驗部分采用仿真方式對本文算法和SGA算法進行比較。根據分析設置組成一套試卷的約束條件要求如下［18］：1）試卷總分100分；2）考試時間120分鐘；3）六種試題的題量和分值如表1所示；4）知識點層次分布在試卷中的比重為 60、25、15；5）試題知識點、區分度、難度、選中率、完成時間所占的權重分別為0.5、0.1、0.2、0.1、0.1；6）試卷難度0.6；7）試卷區分度0.7；8）變異率為0.01；9）交叉概率 0.6；10）初始種群規模數 30；11）種群數量15；12）最大迭代次數100。

表1 試卷結構設置參數

使用SGA算法和本文算法的仿真結果比較如圖2、圖3所示。

圖2 算法收斂速度的比較

圖3 所耗費時間比較

兩種算法均能成功執行，對兩個算法在執行過程中的收斂速度和執行時所耗費的時間兩個方面進行對比。從圖2可以看出，本文算法的收斂速度優于SGA的收斂速度，且隨著迭代次數的增加SGA的收斂速度一直比較緩慢，而本文算法的收斂速度增加的較快。從圖3可以看出，在迭代相同的次數時本文的算法在速度方面優于SGA，但迭代次數較少時，這種優勢并不明顯，隨著迭代次數增加才被明顯的表現出來。

6 結語

本文根據遺傳算法的基本原理，從試題生成的約束條件、優化適應度函數的改進方面進行研究，并對在遺傳過程中優化交叉算子的選擇、變異的設置以及到使用保優策略和輪盤賭相結合進行選擇操作等。在適應度函數中采用閾值t的方式來得到最優的適應度函數值。通過實驗可知，但t=2時可以得到最優的值。本文最后通過本文改進的遺傳算法與傳統的遺傳算法進行仿真結果比較，得到本算法有一定的優勢，能得到更優的組卷策略和效率，組卷的成功率也有所提高。