網(wǎng)上考試系統(tǒng)中組卷策略的實(shí)現(xiàn)

張順利，馮廣麗，任鵬飛

(1. 河南工程學(xué)院 計(jì)算機(jī)科學(xué)與工程系，河南 鄭州 451191;2. 河南工程學(xué)院 電氣信息工程系,河南 鄭州 451191)

組卷是指從龐大的試題庫(kù)中按照給定的要求抽選試題組成試卷的過程，組出的試卷要滿足知識(shí)點(diǎn)均勻分布在指定范圍內(nèi)的要求，試卷難度、區(qū)分度、每種題型的數(shù)量等也要符合組卷參數(shù)的要求.所以，組卷的過程實(shí)際上是求多目標(biāo)最優(yōu)解的過程.在網(wǎng)絡(luò)環(huán)境下，組卷策略的好壞在很大程度上影響著組卷效率.理論上,能找到全局最優(yōu)解的算法往往以時(shí)間的延長(zhǎng)為代價(jià)，要使考試系統(tǒng)具有良好的性能和應(yīng)用價(jià)值, 除了合理的試題庫(kù)結(jié)構(gòu)外，還必須設(shè)計(jì)合理的組卷策略.

1 常用的組卷策略

目前,中國(guó)國(guó)內(nèi)的考試系統(tǒng)采用的組卷算法多為隨機(jī)函數(shù)法和回溯法.

1.1 隨機(jī)函數(shù)法

該算法的核心思想是利用計(jì)算機(jī)提供的隨機(jī)函數(shù)或人為設(shè)計(jì)的隨機(jī)函數(shù)，根據(jù)組卷參數(shù)的要求，從題庫(kù)中抽取符合控制指標(biāo)的試題放入試卷中.該算法結(jié)束的條件有兩種,組卷成功或無法從題庫(kù)中抽取滿足條件的試題.

該算法的優(yōu)點(diǎn)是簡(jiǎn)單、單題抽取效率高、試題分布比較均勻，缺點(diǎn)是多個(gè)試卷控制指標(biāo)之間有時(shí)是相互限制的，很難從全局最優(yōu)化角度抽取試卷，甚至?xí)斐山M卷不成功的情況.

該算法在對(duì)試卷質(zhì)量要求不高、組卷參數(shù)較少的情況下比較適用，比如學(xué)生的自測(cè)環(huán)節(jié).這是因?yàn)閷W(xué)生自測(cè)題的選取沒有教師的參與，而學(xué)生不可能對(duì)組卷參數(shù)有很深的理解.另外,自測(cè)環(huán)節(jié)對(duì)考試公平性的要求較低，不需要很多的參數(shù)控制，只要求學(xué)生輸入要自測(cè)的知識(shí)點(diǎn)或章節(jié)便可以組卷.

實(shí)現(xiàn)步驟：學(xué)生選擇課程和知識(shí)點(diǎn)或章節(jié)范圍，并輸入題型和題目個(gè)數(shù)(m)；將題庫(kù)中所有屬于指定課程在指定的知識(shí)點(diǎn)或章節(jié)范圍內(nèi)的試題號(hào)放入一個(gè)數(shù)組中；用隨機(jī)函數(shù)隨機(jī)產(chǎn)生m個(gè)互不相同的隨機(jī)數(shù)作為數(shù)組的下標(biāo),然后決定抽取的試題號(hào)；在網(wǎng)頁(yè)上顯示試題；完成后在網(wǎng)頁(yè)上顯示答案.

1.2 回溯法

該算法的核心思想是采用深度搜索或廣度搜索的方法對(duì)題庫(kù)進(jìn)行遍歷，當(dāng)找到符合要求的解時(shí)，算法終止。回溯法可以系統(tǒng)地搜索一個(gè)問題的所有解或任一解，它適用于組卷指標(biāo)比較簡(jiǎn)單，出題量較小的組卷.

該算法的優(yōu)點(diǎn)是比隨機(jī)法進(jìn)了一步，組卷成功率較高，缺點(diǎn)是程序結(jié)構(gòu)比較復(fù)雜，選取的試題缺乏靈活性，組卷時(shí)間較長(zhǎng).

根據(jù)以上分析，隨機(jī)法和回溯法組卷應(yīng)用于實(shí)際的網(wǎng)上考試并不太合適，經(jīng)過大量的文獻(xiàn)閱讀和分析，本系統(tǒng)決定使用一種改進(jìn)的遺傳算法.

2 遺傳算法

由于遺傳算法具有搜索結(jié)果全局近優(yōu)、快速、易實(shí)現(xiàn)等特點(diǎn),成為求多目標(biāo)最優(yōu)問題的主流算法.

算法的核心是吸取自然界生物系統(tǒng)的“適者生存，優(yōu)勝劣汰”的進(jìn)化思想，先選定一組非劣解的組合作為解的初始群體，然后對(duì)初始群體中的個(gè)體進(jìn)行“選擇”、“雜交”和“變異”,得到新的個(gè)體,從而形成一個(gè)臨時(shí)的新群體，將臨時(shí)新群體中差的個(gè)體淘汰，得到較優(yōu)良的新群體.不斷重復(fù)該過程，直到找到一個(gè)比較滿意的解.

本系統(tǒng)中所使用的遺傳算法的基本執(zhí)行過程如圖1所示.

圖1 遺傳算法流程圖Fig.1 Genetic algorithm flowchart

其中，MAXF表示滿意的個(gè)體的適應(yīng)函數(shù)值；MAXGEN表示最大代數(shù)； SIZE表示群體規(guī)模；Pc表示雜交概率；Pm表示變異概率.

3 遺傳算法在組卷過程中的具體實(shí)現(xiàn)

傳統(tǒng)型遺傳算法存在很多缺點(diǎn).例如,在初始化群體時(shí)適應(yīng)值較低；算法經(jīng)過若干代演化運(yùn)算后，能達(dá)到一定的收斂點(diǎn)，但收斂速度較慢，一般需經(jīng)過200代到300代； 在收斂過程中易陷于局部最優(yōu).因此,最后求得的結(jié)果適應(yīng)值較低，有時(shí)很難滿足組卷的要求[1].國(guó)內(nèi)外學(xué)者對(duì)遺傳算法做了大量的研究和探索，提出了許多有益的改進(jìn)措施.例如,對(duì)適應(yīng)度進(jìn)行變換[2]，改進(jìn)新的遺傳算子[3]等.本系統(tǒng)采用改進(jìn)的遺傳算法，具體方案如下.

3.1 編碼方案

遺傳算法不是直接在問題的解空間上求解問題，而是利用解的某種編碼進(jìn)行求解，所以首先要設(shè)計(jì)編碼方案.編碼方案有很多種，目前較常用的是二進(jìn)制編碼方案和真值編碼方案.二進(jìn)制編碼方案的優(yōu)點(diǎn)是簡(jiǎn)單明了，但編碼太長(zhǎng)，且編碼本身不便于反映問題的結(jié)構(gòu)特征.本系統(tǒng)中采用真值編碼方案，將一份試卷映射為一個(gè)染色體，由組成試卷的各個(gè)題目的題號(hào)作為染色體的基因值，且將同一題型的基因放在一起.例如,一個(gè)試卷中包含5個(gè)選擇題、5個(gè)填空題和2個(gè)編程題，各種題型的題目在對(duì)應(yīng)題庫(kù)中的題號(hào)分別為12341235078，315215612365,1051(注意：要求各基因的知識(shí)點(diǎn)編號(hào)不相同)，則染色體編碼為：

123412350783152156123651051.

這種編碼方式的優(yōu)點(diǎn)是編碼本身已經(jīng)滿足了知識(shí)點(diǎn)不重復(fù)、題型、題量和總分約束；每種題型邏輯上單獨(dú)編碼，編碼短，便于提高遺傳算法的局部搜索能力，雜交、變異操作容易實(shí)現(xiàn).

3.2 產(chǎn)生初始化群體

假設(shè)每種題型中每個(gè)小題的分值相同，教師在設(shè)置組卷參數(shù)時(shí)可以通過控制題型和題量保證總分約束條件的滿足，該約束條件在此不做考慮，所以初始種群中的個(gè)體只需滿足各題型的題目數(shù)約束條件和知識(shí)點(diǎn)不重復(fù)約束條件即可.

對(duì)于第一個(gè)約束條件，我們采取下面方法保證其成立：設(shè)X1、X2、……Xn分別為每種題型在試卷中應(yīng)有的題目數(shù)，Y1、Y2、……、Yn分別為每種題型的題目總數(shù)，分別產(chǎn)生X1個(gè)不重復(fù)的1-Y1區(qū)間的隨機(jī)整數(shù)、X2個(gè)不重復(fù)的1-Y2區(qū)間的隨機(jī)整數(shù)、……、Xn個(gè)不重復(fù)的1-Yn區(qū)間的隨機(jī)整數(shù)作為染色體的基因值即可；對(duì)于后者，在產(chǎn)生隨機(jī)題號(hào)的過程中判斷該題的知識(shí)點(diǎn)是否在試卷中出現(xiàn)過，若出現(xiàn)過則作廢該隨機(jī)數(shù)，繼續(xù)進(jìn)行即可.

3.3 適應(yīng)函數(shù)

適應(yīng)函數(shù)的值是對(duì)一個(gè)個(gè)體好壞評(píng)價(jià)的唯一指標(biāo)，適應(yīng)函數(shù)值高的個(gè)體被認(rèn)為是優(yōu)秀的個(gè)體，適應(yīng)函數(shù)的確定依據(jù)是組卷目標(biāo).

一份好的試卷應(yīng)滿足以下要求：

(1)各題分值之和等于或接近于總分(可以進(jìn)行局部調(diào)整)；

(2)題型分布滿足指定要求；

(3)知識(shí)點(diǎn)分布滿足指定的要求；

(4)難度符合指定要求；

(5)區(qū)分度符合指定要求.

在此，假設(shè)每種題型單題分值相同，則采用前面所述的編碼方法可以保障分值和題型分布的要求，只需考慮后3個(gè)指標(biāo)即可.

3.3.1 知識(shí)點(diǎn)分布合理程度的衡量

設(shè)m為試卷的總題目數(shù)，Bi(i=1,2,……,m)表示基因串上第i個(gè)題的知識(shí)點(diǎn)是否在所要求的知識(shí)點(diǎn)范圍，如果不在要求范圍，取值為1，否則取值為0.在各題目知識(shí)點(diǎn)不重復(fù)的前提下設(shè)計(jì)公式1：

(1)

可以推出，f1的值在[0,1]區(qū)間上，其值越小，生成的試卷越接近于組卷參數(shù)中對(duì)知識(shí)點(diǎn)分布的要求.

3.3.2 難度系數(shù)的衡量

設(shè)Xi(i=1,2,……,m)表示考生在第i個(gè)題的平均得分，Ai表示第i個(gè)題的滿分，Di表示第i個(gè)題的難度系數(shù)，則Di=1-X/Ai，試卷總體難度系數(shù)ND的計(jì)算方法如公式2所示：

(2)

設(shè)組卷參數(shù)中的難度系數(shù)為ND1，則設(shè)計(jì)公式3.

f2=|ND-ND1|

(3)

可以推出，f2的值在[0,1]區(qū)間上，其值越小，生成的試卷的難度系數(shù)越接近于組卷參數(shù)中難度系數(shù)的要求值.

3.3.3 區(qū)分度的衡量

區(qū)分度是指使水平高的學(xué)生得高分、水平低的學(xué)生得低分的傾向力.設(shè)P表示區(qū)分度，Rh為高分組(前27%的被測(cè)試者)在該題上的平均分，Rl為低分組(后27%的被測(cè)試者)在該題上的平均分，Ai表示該題的滿分，則P=(Rh-Rl)/Ai.

設(shè)Pi(i=1,2,……,m)是基因串上第i個(gè)題的區(qū)分度，Ai表示第i個(gè)題的滿分，則試卷的總體區(qū)分度NP的計(jì)算方法如下：

(4)

設(shè)組卷參數(shù)中的區(qū)分度為NP1，則設(shè)計(jì)公式5:

f3=|NP-NP1|

(5)

可以推出，f3的值在[0,1]區(qū)間上，其值越小，生成的試卷的總體區(qū)分度越接近于組卷參數(shù)中區(qū)分度的要求值.

最后，得到適應(yīng)函數(shù)f4=f1+f2+f3(f2和f3的計(jì)算公式中取絕對(duì)值是為了避免兩種誤差相互抵消[4])，f4在[0,3]區(qū)間，且其值越小越好.為了提高相近個(gè)體間的競(jìng)爭(zhēng)，也為了適應(yīng)“適應(yīng)函數(shù)值越大個(gè)體越優(yōu)秀”的習(xí)慣說法，本系統(tǒng)中最終采用的適應(yīng)函數(shù)如下：

f=-100(f1+f2+f3)+300

(6)

3.4 選擇算子、雜交(交叉)算子和變異算子

選擇算子使得適應(yīng)函數(shù)值高的個(gè)體有較高的存活率，用來對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作，使優(yōu)秀的個(gè)體遺傳到下一代的概率較大，差的個(gè)體遺傳到下一代的概率較小.選擇算子有很多種，本系統(tǒng)采用“賭盤選擇法”和“最優(yōu)保存法”[5]相結(jié)合的策略.已經(jīng)有學(xué)者證明，傳統(tǒng)遺傳算法只能找到局部最優(yōu)解，而不能得到全局最優(yōu)解[6]，最優(yōu)保存法使簡(jiǎn)單遺傳算法具有全局收斂性[7].所以，最優(yōu)保存策略已作為一種保證遺傳算法收斂的通用手段來使用.

最優(yōu)保存策略的基本思路為設(shè)當(dāng)代種群為oldpop，計(jì)算oldpop中各個(gè)體的適應(yīng)值，并找出最優(yōu)個(gè)體；對(duì)oldpop進(jìn)行選擇、交叉和變異操作得到新的種群newpop；計(jì)算newpop中各個(gè)體的適應(yīng)值，并找出最劣個(gè)體；用oldpop中的最優(yōu)個(gè)體替換newpop中的最劣個(gè)體,最后得到一個(gè)和原始種群規(guī)模相同規(guī)模的新種群.

各個(gè)體被選中進(jìn)行雜交和變異的概率與其適應(yīng)度函數(shù)值成正比，被選中后，進(jìn)行雜交和變異操作得到新個(gè)體.

雜交算子常用的有“單點(diǎn)交叉”、“雙點(diǎn)交叉”和“均勻交叉”[4].本系統(tǒng)中選用“均勻交叉”，每對(duì)配對(duì)的個(gè)體上的所有基因?qū)Χ及凑障嗤碾s交概率進(jìn)行雜交(進(jìn)行交叉的基因?qū)Φ臄?shù)量由交叉概率Pc決定)，形成兩個(gè)新個(gè)體.

變異算子[4]：將染色體上的某個(gè)(多個(gè))基因值用隨機(jī)產(chǎn)生的另外一個(gè)等值基因值替換，從而形成一個(gè)新的個(gè)體.變異的多少取決于變異概率Pm的大小，一般取Pm*題量.

3.5 算法結(jié)束的條件

一般有兩種結(jié)束條件，進(jìn)化到最大代數(shù)(MAXGEN)或得到較滿意的個(gè)體(最優(yōu)個(gè)體的適應(yīng)函數(shù)值達(dá)到要求值MAXF)，所以需確定MAXGEN的值，該值實(shí)際上需要通過實(shí)驗(yàn)獲得，本系統(tǒng)暫時(shí)取類似系統(tǒng)所提供的參考值50[8]，在以后的運(yùn)行過程中再根據(jù)統(tǒng)計(jì)數(shù)據(jù)進(jìn)行調(diào)整.

3.6 控制參數(shù)的取值

種群規(guī)模(SIZE)、雜交概率(Pc)和變異概率(Pm),這些參數(shù)都是算法的重要數(shù)據(jù)依據(jù).

(1)種群規(guī)模：此參數(shù)較大時(shí)組卷收斂速度較慢，但易搜索到全局最優(yōu)解，反之，則收斂速度快，但不易搜索到全局最優(yōu)解，一般取種群規(guī)模30～60[8].

(2)雜交概率(Pc)和變異概率(Pm)：這兩個(gè)參數(shù)如果取值太大，可能使算法變成純粹的隨機(jī)搜索算法[9]，Pc若過小，組卷收斂速度會(huì)變慢，參考取值為0.25～0.85；Pm若過小，則不容易產(chǎn)生新個(gè)體，參考取值為0.01～0.25[10].

在本系統(tǒng)中，采用自適應(yīng)思想[8]，在算法進(jìn)行過程中，Pc和Pm可以根據(jù)實(shí)際情況自行調(diào)整，使其隨適應(yīng)函數(shù)值的增大而變小，隨其變小而增大.設(shè)f為兩個(gè)交叉?zhèn)€體的適應(yīng)函數(shù)值的較大值，favg為群體適應(yīng)函數(shù)值的平均值，fmax為群體中適應(yīng)函數(shù)值的最大值，f′為變異個(gè)體的適應(yīng)函數(shù)值，Pc和Pm的計(jì)算方法如公式7和8所示.

(7)

(8)

4 亂序引擎的使用

本系統(tǒng)采用的是一個(gè)考場(chǎng)在同一時(shí)間使用一份試卷、每個(gè)考生的考題順序都不一樣的策略，那么就存在怎樣將題號(hào)打亂的問題.

設(shè)待打亂的題目數(shù)為M，該問題的實(shí)質(zhì)是產(chǎn)生M個(gè)1～M之間的不重復(fù)的隨機(jī)數(shù).一般的算法是每產(chǎn)生一個(gè)隨機(jī)數(shù)就和前面產(chǎn)生過的隨機(jī)數(shù)進(jìn)行比較，如果有相同的隨機(jī)數(shù)已經(jīng)在序列中存在，則該隨機(jī)數(shù)作廢.可以證明，該算法的算法復(fù)雜度為O(M2)，因?yàn)樵撍惴ㄒ?jīng)常被用到(比如一場(chǎng)考試有300個(gè)人參加，則需要調(diào)用300次)，所以最好能降低其時(shí)間復(fù)雜度.本考試系統(tǒng)采用亂序引擎[11]算法完成此工作.該算法的步驟如下.

將原始題目序號(hào)放入A[1]～A[m];

i=1；

while (i<=m)

{ 產(chǎn)生一個(gè)[1,m]區(qū)間的隨機(jī)數(shù)x;

將A[x]和A[i]交換；

i++; }

由于題目序號(hào)不重復(fù)，每次又是兩兩交換，所以不可能有重復(fù)的題號(hào).該算法的時(shí)間復(fù)雜度為O(M)，且空間效率也沒有降低.

5 結(jié) 語

對(duì)遺傳算法的各個(gè)環(huán)節(jié)進(jìn)行了具體分析和描述，本算法思想已經(jīng)使用Java代碼實(shí)現(xiàn).實(shí)踐證明,使用改進(jìn)的遺傳算法實(shí)現(xiàn)組卷過程是行之有效的，具有較好的推廣價(jià)值.

參考文獻(xiàn)：

[1] 李美滿, 夏漢鑄, 易德成. 基于COM 技術(shù)的通用考試系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用, 2007, 43(1): 245-248.

[2] KREINOVICH V, QUINTANA C, FUENTES O．Genetic algorithms-what fitness scaling is optimal[J]．Cybernetics and System，1993，24(1)：9-26.

[3] 鄭金華，葉正華．基于空間交配的遺傳算法[J]．模式識(shí)別與人工智能，2003，16(4)：482-485.

[4] BESSAOU M，SLARRY P．A genetic algorithm with real-value coding to optimize multimodal continuous functions[J]．Structure Multitask Optimization，2001，23(1)：63-74.

[5] GREFENSTETTE J J．Optimization of control parameters for genetic algorithms[J]. IEEE Transactions on Systems, Man and Cybernetics, 1986, 16(1): 122-168.

[6] RUDOLPH G．Convergence properties of canonical genetic algorithms[J]．IEEE Transactions on Neural Networks，1994, 5(1)：96-101.

[7] 惲為民，席裕庚．遺傳算法的全局收斂性和計(jì)算效率分析[J].控制理論與應(yīng)用，1996,13(4):455-460.

[8] 周文舉. 一種基于知識(shí)點(diǎn)的遺傳算法組卷的改進(jìn)應(yīng)用[J].山東師范大學(xué)學(xué)報(bào)：自然科學(xué)版, 2006, 21(3):39-42.

[9] 楊路明, 陳大鑫. 改進(jìn)遺傳算法在試題自動(dòng)組卷中的應(yīng)用研究[J].計(jì)算機(jī)與數(shù)字工程，2004，32(5)：76-79.

[10] 劉韶麗. 基于智能組卷策略的網(wǎng)上考試系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].南京：東南大學(xué)，2006.

[11] 陸宏謙．基于J2EE構(gòu)架的網(wǎng)上考試系統(tǒng)的分析與設(shè)計(jì)[D].濟(jì)南：山東大學(xué), 2005.