胡木林

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

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

中圖分類號：TP319 文獻(xiàn)標(biāo)識碼：B

文章編號：1671-489X（2018）12-0023-05

1 前言

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

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

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

2 選題理論

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

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

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

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

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

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

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

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

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

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

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

式中，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è)計

遺傳算法原理 遺傳算法（Genetic Algorithm，簡稱GA）是一種基于生物學(xué)進(jìn)化規(guī)律演化而來，具有全局尋優(yōu)能力的隨機(jī)化搜索方法[6]。其原理為：將問題的解表示成生物界“染色體”和二進(jìn)制編碼的串，在執(zhí)行操作之前，給出一群假設(shè)解“染色體”，并將“染色體”置于問題的“環(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)境的一個“染色體”上，將其作為問題的最優(yōu)解輸出[7]。遺傳算法流程圖如圖1所示。

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

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

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

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

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

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

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

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

Fmbhs值越小，說明試卷越符合要求。

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

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

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

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

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

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

其中β=0.03。

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

5）遺傳算子操作。

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

具體選取過程如下：

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

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

c.比較選取，若R

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

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

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

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

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

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

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

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

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

e.基因值用新題題號替換。

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

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

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

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

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

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

4 總結(jié)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

[8]莫家慶，胡忠望.基于遺傳算法的組卷系統(tǒng)的研究與實現(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]潘莉.遺傳算法在自動組卷中的應(yīng)用方法研究[D].長春：東北師范大學(xué)，2010.

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