基于遺傳算法的在線考試系統(tǒng)組卷設(shè)計(jì)

胡木林

摘 要 在線考試系統(tǒng)的核心是組卷算法，利用全局擇優(yōu)的遺傳算法研究在線考試系統(tǒng)的組卷過(guò)程，解決了在線考試系統(tǒng)的核心技術(shù)。基于遺傳算法的在線考試系統(tǒng)的實(shí)現(xiàn)縮短了考試的工作流程，減輕了教師的工作量，使考試更客觀、公正、環(huán)保、高效。

關(guān)鍵詞 互聯(lián)網(wǎng)+；在線考試系統(tǒng)；遺傳算法；組卷算法

中圖分類(lèi)號(hào)：TP319 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：1671-489X（2018）12-0023-05

1 前言

2015年，國(guó)務(wù)院總理李克強(qiáng)在政府工作報(bào)告中首次提出“互聯(lián)網(wǎng)+”行動(dòng)計(jì)劃，全面實(shí)施網(wǎng)絡(luò)強(qiáng)國(guó)戰(zhàn)略。“互聯(lián)網(wǎng)+”模式已成為各行各業(yè)發(fā)展的新業(yè)態(tài)，互聯(lián)網(wǎng)教育已成為教育發(fā)展的必然趨勢(shì)。基于互聯(lián)網(wǎng)的在線無(wú)紙化考試是集考試報(bào)名、制卷、閱卷、成績(jī)統(tǒng)計(jì)與分析等為一體的多功能考試形式，因具有高效、客觀、公正、安全、環(huán)保等一系列優(yōu)點(diǎn)，成為國(guó)內(nèi)外學(xué)校教育教學(xué)改革重要課題。

在線考試系統(tǒng)的核心部分就是組卷算法，它直接決定著考試檢測(cè)的效果。近年來(lái)，組卷算法的研究一直是在線考試系統(tǒng)的研究重點(diǎn)，例如：劉洋進(jìn)行了考試系統(tǒng)中組卷算法的研究與設(shè)計(jì)[1]；沈建強(qiáng)等研究了組卷系統(tǒng)的優(yōu)化與實(shí)現(xiàn)[2]；劉彬研究了遺傳算法在試題組卷中的應(yīng)用，重點(diǎn)研究了選取的有效規(guī)則[3]。

本文重點(diǎn)研究具有全局優(yōu)化的遺傳算法，并按照試卷信度、效度、難度、區(qū)分度等評(píng)價(jià)指標(biāo)，建立目標(biāo)矩陣和目標(biāo)函數(shù)，對(duì)遺傳編碼、遺傳算子、算法終止條件等進(jìn)行詳細(xì)分析與設(shè)計(jì)。并在遺傳操作的過(guò)程中研究采用分段實(shí)數(shù)編碼方式和指數(shù)比例變換方式建立適應(yīng)度函數(shù)，確保隨機(jī)生成的試卷更科學(xué)、規(guī)范、高效。

2 選題理論

考試需要試卷，試卷質(zhì)量的好壞直接決定著檢測(cè)結(jié)果的真實(shí)性和代表性。因此，在線考試系統(tǒng)如何按照教師的要求自動(dòng)制出科學(xué)、規(guī)范、全面的試卷，就體現(xiàn)得尤為重要。系統(tǒng)設(shè)計(jì)時(shí)，采用何種智能算法決定著組卷的質(zhì)量和效率。目前，較為常用的有誤差補(bǔ)償、隨機(jī)抽取和遺傳算法等多種組卷算法，無(wú)論采用何種組卷算法，都必須要解決自動(dòng)按照設(shè)定約束條件，選擇符合要求的試題，組成考卷。試卷形成后，要按照特定評(píng)價(jià)指標(biāo)給予評(píng)價(jià)。通常，其評(píng)價(jià)指標(biāo)主要有信度、效度、難度、區(qū)分度和實(shí)用性等[4]。

試題的難度 難度作為試題的評(píng)價(jià)指標(biāo)之一，是指試卷中試題的難易程度，用該題的通過(guò)率或平均得分率[5]來(lái)衡量，一般用P表示。主觀題難度系數(shù)和客觀題難度系數(shù)的計(jì)算方法如下。

1）主觀性試題的難度，基本公式：

2）客觀性試題的難度，基本公式：

上述公式是基于理論分析與推導(dǎo)，實(shí)際應(yīng)用中，信度按以下方法計(jì)算。

主觀題信度按克朗巴赫公式法估算：

式中，K指整個(gè)測(cè)驗(yàn)的題數(shù)，Sx2指測(cè)驗(yàn)的總得分方差，Si2指每道題的得分方差。

客觀題的信度按庫(kù)德—理查遜公式估算：

試題的效度 效度是指測(cè)量的有效性程度，用R表示。在教育考試領(lǐng)域，相較于信度而言，效度的衡量結(jié)果更加重要。在測(cè)量理論中，效度為有效分?jǐn)?shù)方差與實(shí)得分?jǐn)?shù)方差之比，即：

由上式可知，誤差方差越小，有效分?jǐn)?shù)方差越大，效度越高。

區(qū)分度 區(qū)分度用來(lái)反映試題區(qū)分不同水平參試者的程度，同時(shí)用來(lái)衡量考試試題對(duì)參試者水平差異的鑒別能力，即通過(guò)考試，能把優(yōu)秀、中等、差等不同層次的學(xué)生真正區(qū)分開(kāi)。區(qū)分度越高，層次劃分越合理；反之，區(qū)分度越低，考試分?jǐn)?shù)分布就會(huì)出現(xiàn)某一區(qū)間相對(duì)集中，層次劃分越不合理。區(qū)分度用D表示，通常采用鑒別指數(shù)法計(jì)算：

式中，PH指高分組（即得分最高的27%）該題的正確率，PL指低分組（即得分最低的27%）該題的正確率。

試題區(qū)分度介于-1～+1之間，若值大于0.4，該題的區(qū)分度很好；若值介于0.3～0.39，該題的區(qū)分度較好；若值介于0.2～0.29，該題區(qū)分度較差，需修改；若值小于0.19，該題區(qū)分度差，需要淘汰刪除該題。

3 遺傳算法組卷設(shè)計(jì)

遺傳算法原理 遺傳算法（Genetic Algorithm，簡(jiǎn)稱(chēng)GA）是一種基于生物學(xué)進(jìn)化規(guī)律演化而來(lái)，具有全局尋優(yōu)能力的隨機(jī)化搜索方法[6]。其原理為：將問(wèn)題的解表示成生物界“染色體”和二進(jìn)制編碼的串，在執(zhí)行操作之前，給出一群假設(shè)解“染色體”，并將“染色體”置于問(wèn)題的“環(huán)境”中，根據(jù)生物學(xué)領(lǐng)域中適者生存的規(guī)律，比較選擇適應(yīng)“環(huán)境”能力較強(qiáng)的染色體進(jìn)行復(fù)制、交叉、變異，產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群，一代代地進(jìn)化，收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，將其作為問(wèn)題的最優(yōu)解輸出[7]。遺傳算法流程圖如圖1所示。

基于遺傳算法的組卷算法設(shè)計(jì)

1）約束條件的數(shù)學(xué)模型。組卷就是按照設(shè)定的多約束條件、多指標(biāo)優(yōu)化求最優(yōu)解的過(guò)程。建立基于遺傳算法的自動(dòng)組卷系統(tǒng)數(shù)學(xué)模型，就是把衡量試題質(zhì)量的約束屬性設(shè)定為實(shí)際組卷的約束條件。組卷中抽取的每道試題，都由n項(xiàng)指標(biāo)確定。本文以最具有代表性的分值、所屬的知識(shí)點(diǎn)、難度系數(shù)和題型等四個(gè)指標(biāo)為例建立模型。每道題的數(shù)學(xué)模型用一個(gè)四維向量（d1，d2，d3，d4）來(lái)表示，其中d1，d2，d3，d4分別對(duì)應(yīng)試題的分值、知識(shí)點(diǎn)、難度系數(shù)、題型四個(gè)屬性指標(biāo)[8]。若該試卷共有m道試題，則m×4的矩陣就表示該試卷的數(shù)學(xué)模型，如式（8）所示，也稱(chēng)為試卷目標(biāo)矩陣。

目標(biāo)矩陣建立后，需建立目標(biāo)函數(shù)。在組卷過(guò)程中，授課教師根據(jù)專(zhuān)業(yè)不同，確定考試的章節(jié)和知識(shí)點(diǎn)，并確定相關(guān)章節(jié)在本次考試中所占的分值以及在組卷時(shí)本章所允許的分?jǐn)?shù)誤差。假設(shè)試題庫(kù)中共有N章知識(shí)內(nèi)容，Zi（i=1，2，...，N）、Yi（i=1，2，...，N）、Wi（i=1，2，...，N）

分別表示生成試卷各章節(jié)所占的分?jǐn)?shù)、組卷時(shí)設(shè)定各章節(jié)應(yīng)占的分?jǐn)?shù)和用戶(hù)允許各章節(jié)的分?jǐn)?shù)誤差，則生成試卷后是否滿(mǎn)足要求，可以用式（9）、式（10）來(lái)表達(dá)：

fzw越小，則說(shuō)明分?jǐn)?shù)誤差越小，生成的試卷質(zhì)量越高，越滿(mǎn)足使用要求。設(shè)生成試卷的難度系數(shù)為scndxs，則計(jì)算公式如式（11）所示：

式中，di1指第i題的難度系數(shù)，N指試卷的總題數(shù)。

若教師指定的難度系數(shù)為zdndxs，則難度系數(shù)誤差ndwc為：

根據(jù)式（10）（11）（12）可以得出目標(biāo)函數(shù)（Fmbhs）表達(dá)式為：

Fmbhs值越小，說(shuō)明試卷越符合要求。

2）遺傳編碼。遺傳算法的操作對(duì)象是群體中的個(gè)體，并對(duì)個(gè)體不斷優(yōu)化。因此，必須對(duì)個(gè)體用基因鏈碼的形式表示出來(lái)，這種編制基因鏈碼的過(guò)程稱(chēng)為編碼。編碼技術(shù)是遺傳算法的關(guān)鍵技術(shù)，對(duì)遺傳算法的成功實(shí)現(xiàn)起著至關(guān)重要的作用。編碼的方案和策略對(duì)遺傳算子產(chǎn)生直接影響，特別是交叉和變異算子的功能設(shè)計(jì)[9]。常見(jiàn)的編碼方法有二進(jìn)制編碼、實(shí)數(shù)編碼、多參數(shù)編碼和DNA編碼等。

實(shí)數(shù)編碼技術(shù)解決了二進(jìn)制編碼方式搜索空間過(guò)大和編碼過(guò)長(zhǎng)的缺點(diǎn)，能很大程度地提高求解速度和組卷效率。因此，本文以實(shí)數(shù)編碼進(jìn)行研究，將每一份試卷映射成為單獨(dú)的一個(gè)染色體，每一種題型作為一個(gè)基因的編碼串，被選中的每一道試題作為染色體的一個(gè)基因，且該基因?yàn)槌橹性囶}的序號(hào)。編碼的過(guò)程實(shí)際上就是將同種類(lèi)型的試題標(biāo)號(hào)組合成段，使得每一段編碼表示一種題型，每種類(lèi)型的試題單獨(dú)進(jìn)行實(shí)數(shù)編碼，編碼后染色體的個(gè)數(shù)實(shí)為試卷題目的總數(shù)。假設(shè)要組成的試卷有選擇題、判斷題、客觀題三種題型，每種題型均有五道題目，表1為采用分段實(shí)數(shù)編碼組卷后兩張?jiān)嚲淼娜旧w。

3）適應(yīng)度函數(shù)的確定。適應(yīng)度（值）是表示個(gè)體對(duì)環(huán)境的適應(yīng)能力和繁殖后代的能力[10]。適應(yīng)度函數(shù)是用來(lái)判斷群體中的個(gè)體優(yōu)劣程度的指標(biāo)，適應(yīng)度越大，個(gè)體越好。在遺傳算法的搜索進(jìn)化過(guò)程中，適應(yīng)度函數(shù)是用來(lái)評(píng)估個(gè)體或解優(yōu)良程度的唯一依據(jù)，是遺傳操作重要條件。為便于操作，適應(yīng)度函數(shù)值必須非負(fù)值。多數(shù)情況下，對(duì)于給定約束的優(yōu)化，目標(biāo)函數(shù)值有正有負(fù)，這就必須要建立適應(yīng)度函數(shù)和目標(biāo)函數(shù)之間的映射關(guān)系來(lái)確保適應(yīng)度函數(shù)值的非負(fù)。建立適應(yīng)度函數(shù)f（x）和目標(biāo)函數(shù)g（x）的映射關(guān)系如下：

式中dmax是一個(gè)輸入值，也可以是當(dāng)前所有代數(shù)值，或者是最近K代中g(shù)（x）的最大值，此時(shí)dmax隨著代數(shù)會(huì)有變化。

現(xiàn)建立目標(biāo)函數(shù)Fmbhs和適應(yīng)函數(shù)Fsyhs之間的映射關(guān)系式如下：

為讓優(yōu)秀的染色體有更多的機(jī)會(huì)被復(fù)制，同時(shí)避免復(fù)制過(guò)多優(yōu)秀的染色體充滿(mǎn)整個(gè)種群，提高偏差較小的染色體之間的競(jìng)爭(zhēng)力，多數(shù)采用指數(shù)比例的方法來(lái)設(shè)計(jì)適應(yīng)度函數(shù)，采用比例指數(shù)法建立的適應(yīng)度函數(shù)Fsydhs如下：

其中β=0.03。

4）產(chǎn)生初始種群。在初始種群之前，首現(xiàn)確定初始規(guī)模及群的大小M，初始規(guī)模的大小對(duì)組卷起著很大的影響：過(guò)大，算法效率較低；過(guò)小易早熟，無(wú)法達(dá)到最優(yōu)解。在實(shí)際應(yīng)用中，M一般取100左右。

5）遺傳算子操作。

①選擇算子。選擇算子是指選擇優(yōu)良的個(gè)體遺傳給下一代。目前，選擇算子方法主要有適應(yīng)度比例法、聯(lián)賽選擇法、Boltzmann選擇法等多種方法。其中，適應(yīng)度比例法又稱(chēng)輪賭選擇法，是遺傳算法中使用最多最廣的一種方法。本文研究采用適應(yīng)度比例法，其原理為：利用計(jì)算個(gè)體的適應(yīng)度函數(shù)值來(lái)劃分輪盤(pán)的比例區(qū)域，適應(yīng)度越大，所占輪盤(pán)的區(qū)域就越大，被選取遺傳的概率就越大。假設(shè)群體大小為M，第i個(gè)個(gè)體的適應(yīng)度為Si，整個(gè)種群的適應(yīng)度為Sn，那么個(gè)體i被選取的概率Pi可表示為：

具體選取過(guò)程如下：

a.計(jì)算個(gè)體的適應(yīng)度Si、整個(gè)種群適應(yīng)度Sn、個(gè)體被選中的概率Pi；

b.確定種群中個(gè)體的最大選擇概率Pmax，并且在[0，Pmax]之間生成隨機(jī)概率數(shù)R；

c.比較選取，若R

d.重復(fù)步驟b與c，至個(gè)體數(shù)目滿(mǎn)足設(shè)定的需要條件為止。

②交叉算子。交叉算子是遺傳算法的核心之處，常用單點(diǎn)交叉和均勻隨機(jī)交叉。本文研究采用單點(diǎn)交叉，其原理為：先確定交叉的概率Pc，一般為0.6～0.8（執(zhí)行交換個(gè)體達(dá)到60%～80%）。同理，依據(jù)選擇算子的方式確定交叉的個(gè)體，并隨機(jī)產(chǎn)生一個(gè)斷點(diǎn)，依次兩兩進(jìn)行交換（交換雙親斷點(diǎn)之后的部分），原理如表2和表3所示。

基因交叉后如出現(xiàn)基因重復(fù)（出現(xiàn)相同兩道題）或者順序混亂（大序號(hào)題目在前，小序號(hào)題目在后），系統(tǒng)首先就要做出判斷，找出重復(fù)基因或要重新排序的基因的下標(biāo)范圍，其方法為[11]：分別將交叉點(diǎn)的基因同交叉點(diǎn)之前和之后的基因依次比較（之前的按照從后向前的順序，之后的按照從前向后的順序），找出第一個(gè)比變異點(diǎn)小的基因和第一個(gè)比變異點(diǎn)大的基因，分別記錄i1和i2，要替換重復(fù)的基因和重新排序的基因就在區(qū)間[i1，i2]內(nèi)。假設(shè)交叉點(diǎn)下標(biāo)為i，則兩層循環(huán)就在[i1，i-1]，[i，i2]這兩個(gè)區(qū)間判斷，如果出現(xiàn)重復(fù)，按約束條件隨機(jī)抽取的一個(gè)沒(méi)有出現(xiàn)的染色體（試題的編碼）將[i，i2]區(qū)間內(nèi)的重復(fù)基因替換掉。新染色體中就不再出現(xiàn)重復(fù)基因，再將新染色體的基因重新排序即可。

③變異算子。變異是產(chǎn)生新個(gè)體的另一種方法，對(duì)遺傳算法起著積極的作用，可以提高遺傳算法的全局搜索能力和保持群體的多樣性[12]。變異個(gè)體的選擇以及變異位置的確定，都是采用隨機(jī)的方法產(chǎn)生。執(zhí)行過(guò)程如下：

a.初始化搜索新題的次數(shù)為零，并設(shè)置最大次數(shù)為M；

b.隨機(jī)產(chǎn)生的概率系數(shù)Pm1，若Pm1>Pm（Pm為0.001～

0.01），基因保持不變；反之，則將依據(jù)此基因的值來(lái)確定所屬題型。

c.把搜索次數(shù)J加1，如果J>M，那么將停止新題搜索，且該基因保持不變；反之，將在此題型所包含的題號(hào)范圍內(nèi)隨機(jī)生成一個(gè)與此基因值不相同的另一整數(shù)，作為新題的題號(hào)；

d.如果選擇的新題所包含的知識(shí)點(diǎn)與本個(gè)體中的其他題目相同，則重復(fù)c的操作；

e.基因值用新題題號(hào)替換。

表4表示變異前染色體A、表5表示變異后染色體A′，變異后如出現(xiàn)基因重復(fù)（如A′中第二段的6與后面基因重復(fù)），則要重新隨機(jī)選取一個(gè)等位基因（題號(hào)）再進(jìn)行替換；若出現(xiàn)順序混亂非法時(shí)（如A′中第三段的37比后面基因36大），則首先將變異點(diǎn)同變異點(diǎn)前后的基因標(biāo)號(hào)依次比較，找出順序混亂的區(qū)間，重新進(jìn)行排序。

遺傳運(yùn)算終止條件的設(shè)計(jì) 遺傳算法是一種反復(fù)迭代的搜索過(guò)程，它通過(guò)多次進(jìn)化逐漸逼近最優(yōu)解，而不是恰好等于最優(yōu)解，因此需要確定終止條件。常用的有以下幾種方法：

1）直接規(guī)定遺傳迭代次數(shù)，即預(yù)先設(shè)置一定的次數(shù)，然后按情況增加代數(shù)（可達(dá)上千次）；

2）控制目標(biāo)函數(shù)的方差實(shí)現(xiàn)終止，即當(dāng)目標(biāo)函數(shù)值和實(shí)際的目標(biāo)值之間的差異小于允許值時(shí)，遺傳終止；

3）查看適應(yīng)度的變化來(lái)確定算法是否終止，即當(dāng)最優(yōu)個(gè)體的適應(yīng)度沒(méi)有明顯變化或者變化很小時(shí)，則遺傳終止。

考慮組卷的實(shí)效，研究采用第一種和第三種的結(jié)合作為遺傳運(yùn)算的終止條件，即在預(yù)先規(guī)定的代數(shù)內(nèi)有一個(gè)個(gè)體的適應(yīng)度值已經(jīng)滿(mǎn)足要求，則就停止；反之則一直迭代，直到達(dá)到規(guī)定的代數(shù)為止，取出終止時(shí)的最優(yōu)個(gè)體作為算法最優(yōu)解輸出。流程圖如圖2所示。

4 總結(jié)

本文深入分析了在線考試系統(tǒng)組卷時(shí)試題選取的相關(guān)理論，研究了基于遺傳算法考試系統(tǒng)的目標(biāo)函數(shù)的設(shè)計(jì)、適應(yīng)度函數(shù)的設(shè)計(jì)、種群的初始化、遺傳算子的選擇、遺傳算子的交叉與變異和遺傳算法的終止條件。系統(tǒng)功能實(shí)現(xiàn)后，通過(guò)大量組卷實(shí)驗(yàn)，基于遺傳組卷算法在線考試系統(tǒng)組卷安全、方便、快捷，很大程度減輕了教師的教學(xué)負(fù)擔(dān)，提高了教學(xué)效率，具有很好的實(shí)用性。同時(shí)突破時(shí)空的界限，適應(yīng)互聯(lián)網(wǎng)教育發(fā)展趨勢(shì)。

參考文獻(xiàn)

[1]劉洋.遺傳算法在考試系統(tǒng)中組卷算法的研究與設(shè)計(jì)[J].湖南城市學(xué)院學(xué)報(bào)，2013，22（1）：75-78.

[2]沈建強(qiáng)，張寶明，鄒軒.組卷系統(tǒng)的優(yōu)化與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2003，23（s1）：38-39.

[3]劉彬.遺傳算法在試題組卷中的應(yīng)用[J].燕山大學(xué)學(xué)報(bào)，2002，26（3）：193-195.

[4]金娣，王剛.教育評(píng)價(jià)與測(cè)量[M].北京：教育科學(xué)出版社，2002：12-20.

[5]郭曉君.智能組卷策略淺析[J].科技展望，2015（32）：108.

[6]徐濤.基于遺傳算法的組卷研究與設(shè)計(jì)[J].軟件導(dǎo)刊，2014，13（12）：109-111.

[7]周艷麗.基于改進(jìn)遺傳算法的自動(dòng)組卷問(wèn)題研究[J].計(jì)算機(jī)仿真，2010（9）：319-322.

[8]莫家慶，胡忠望.基于遺傳算法的組卷系統(tǒng)的研究與實(shí)現(xiàn)[J].福建電腦，2014（6）：31-33.

[9]譚新良.基于整數(shù)編碼和自適應(yīng)遺傳算法的智能組卷算法[J].電腦與信息技術(shù)，2007（4）：33-35，62.

[10]周芳.組卷技術(shù)中遺傳算法的改進(jìn)研究[J].信息通信，2016（7）：31-32.

[11]潘莉.遺傳算法在自動(dòng)組卷中的應(yīng)用方法研究[D].長(zhǎng)春：東北師范大學(xué)，2010.

[12]林關(guān)成，吳代文.基于遺傳算法的在線考試系統(tǒng)自動(dòng)組卷策略?xún)?yōu)化[J].計(jì)算機(jī)與數(shù)字工程，2012（3）：24-26.