賀建英 王光瓊 唐青松

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

1 引言

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

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

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

2 相關(guān)工作

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

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

3.1 組卷理論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1）試卷總分約束條件：

K值由用戶確定。

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

其中 f1i、f2i、f3i分別為該試題在三個(gè)層次上的的知識(shí)點(diǎn)分布覆蓋率。其中試卷三個(gè)層次總的知識(shí)點(diǎn)覆蓋率約束為

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

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

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

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

其中 f5i為每題的難度。

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

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

6）試卷完成時(shí)間約束條件：

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

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

其中 f7i為每題的題型。

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

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

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

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

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

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

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

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

4 基于遺傳算法的自動(dòng)組卷策略

4.1 編碼方案

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

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

圖1 基因編碼方式

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

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

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

適應(yīng)度函數(shù)是用來(lái)評(píng)價(jià)一個(gè)群體中的單個(gè)個(gè)體優(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 選擇操作

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

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

4.2.3 交叉操作

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

4.2.4 變異操作

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

4.2.5 結(jié)束操作

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

5 實(shí)驗(yàn)與分析

系統(tǒng)采用MyEclipse10.0平臺(tái)進(jìn)行設(shè)計(jì)實(shí)現(xiàn)，數(shù)據(jù)庫(kù)為MySql數(shù)據(jù)庫(kù)（包含570道試題）。為驗(yàn)證上述算法的有效性，實(shí)驗(yàn)部分采用仿真方式對(duì)本文算法和SGA算法進(jìn)行比較。根據(jù)分析設(shè)置組成一套試卷的約束條件要求如下［18］：1）試卷總分100分；2）考試時(shí)間120分鐘；3）六種試題的題量和分值如表1所示；4）知識(shí)點(diǎn)層次分布在試卷中的比重為 60、25、15；5）試題知識(shí)點(diǎn)、區(qū)分度、難度、選中率、完成時(shí)間所占的權(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 所耗費(fèi)時(shí)間比較

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

6 結(jié)語(yǔ)

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