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

賀建英 王光瓊 唐青松

（1.四川文理學(xué)院智能制造學(xué)院 達州 635000）（2.達州智能制造產(chǎn)業(yè)技術(shù)研究院 達州 635000）

1 引言

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

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

本文在傳統(tǒng)遺傳算法的基礎(chǔ)上，從試題的編碼方法、建立加權(quán)目標(biāo)函數(shù)來優(yōu)化適應(yīng)度函數(shù)、交叉算子的選擇、變異的設(shè)置以及到采用保優(yōu)策略和輪盤賭相結(jié)合進行選擇操作等方面進行了優(yōu)化設(shè)計。取得了很好的適應(yīng)度，并能快速成功組卷，提高了組卷效率。

2 相關(guān)工作

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

3 組卷理論及數(shù)學(xué)模型

3.1 組卷理論

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

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

其中r是答錯該題的人數(shù)，n是做過該題的總?cè)藬?shù)。該值在系統(tǒng)中是動態(tài)變化的。

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

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

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

其中N應(yīng)是去重后的知識點個數(shù)即N≤M。

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

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

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

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

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

其中r＞0.4，Yi和Zi分別為第i個考生在本次測試與校標(biāo)測試中的成績。Yi、Y'、Zi、Z'分別表示兩次測試的標(biāo)準(zhǔn)差與均值。Pt為參考考試的總?cè)藬?shù)。

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

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

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

其中di為第i個試題的區(qū)分度。

3.2 智能組卷問題數(shù)學(xué)模型

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

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

1）試卷總分約束條件：

K值由用戶確定。

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

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

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

3）試卷區(qū)分度分?jǐn)?shù)約束條件：

其中 f4i為每題的區(qū)分度。

4）試卷難度系數(shù)對應(yīng)的分?jǐn)?shù)分布約束條件：

其中 f5i為每題的難度。

5）試卷的試題選中率分?jǐn)?shù)條件約束：

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

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

T的值應(yīng)該小于等于用戶需求設(shè)定的考試時間。

7）試題題型分?jǐn)?shù)分布約束條件：

其中 f7i為每題的題型。

3.3 目標(biāo)函數(shù)的建立

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

其中Lj表示第 j個層次中知識點的目標(biāo)分?jǐn)?shù)，j=1,2,3。m1為生成的試卷中知識點的總個數(shù)。

其中Di表示試卷中區(qū)分度為i的目標(biāo)分?jǐn)?shù)。m2為生成的試卷中區(qū)分度的總個數(shù)。

其中Oi為難度系數(shù)為i的目標(biāo)分?jǐn)?shù)。m3為難度級別的總個數(shù)。

其中Ci為選中率為為i的目標(biāo)分?jǐn)?shù)。

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

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

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

4.1 編碼方案

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

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

圖1 基因編碼方式

4.2 相關(guān)操作的建立

在前面的分析中已經(jīng)得知應(yīng)滿足的因素中包括適應(yīng)度函數(shù)、進化次數(shù)、結(jié)束條件以及變異的相關(guān)操作（選擇、交叉、變異）等。

4.2.1 適應(yīng)度函數(shù)

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

4.2.2 選擇操作

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

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

4.2.3 交叉操作

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

4.2.4 變異操作

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

4.2.5 結(jié)束操作

本文采用最簡單的遺傳代數(shù)達到規(guī)定的值時結(jié)束算法。

5 實驗與分析

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

表1 試卷結(jié)構(gòu)設(shè)置參數(shù)

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

圖2 算法收斂速度的比較

圖3 所耗費時間比較

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

6 結(jié)語

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