張順利，馮廣麗，任鵬飛

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

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

1 常用的組卷策略

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

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

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

該算法的優(yōu)點(diǎ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)；將題庫中所有屬于指定課程在指定的知識(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)頁上顯示試題；完成后在網(wǎng)頁上顯示答案.

1.2 回溯法

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

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

根據(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].國內(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é)構(gòu)特征.本系統(tǒng)中采用真值編碼方案，將一份試卷映射為一個(gè)染色體，由組成試卷的各個(gè)題目的題號(hào)作為染色體的基因值，且將同一題型的基因放在一起.例如,一個(gè)試卷中包含5個(gè)選擇題、5個(gè)填空題和2個(gè)編程題，各種題型的題目在對(duì)應(yīng)題庫中的題號(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è)體間的競爭，也為了適應(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)保存法使簡單遺傳算法具有全局收斂性[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.