張順利，馮廣麗，任鵬飛

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

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

1 常用的組卷策略

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

1.1 隨機函數(shù)法

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

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

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

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

1.2 回溯法

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

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

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

2 遺傳算法

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

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

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

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

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

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

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

3.1 編碼方案

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

123412350783152156123651051.

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

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

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

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

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

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

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

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

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

(3)知識點分布滿足指定的要求；

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

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

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

3.3.1 知識點分布合理程度的衡量

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

(1)

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

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

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

(2)

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

f2=|ND-ND1|

(3)

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

3.3.3 區(qū)分度的衡量

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

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

(4)

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

f3=|NP-NP1|

(5)

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

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

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

(6)

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

選擇算子使得適應(yīng)函數(shù)值高的個體有較高的存活率，用來對群體中的個體進行優(yōu)勝劣汰操作，使優(yōu)秀的個體遺傳到下一代的概率較大，差的個體遺傳到下一代的概率較小.選擇算子有很多種，本系統(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，計算oldpop中各個體的適應(yīng)值，并找出最優(yōu)個體；對oldpop進行選擇、交叉和變異操作得到新的種群newpop；計算newpop中各個體的適應(yīng)值，并找出最劣個體；用oldpop中的最優(yōu)個體替換newpop中的最劣個體,最后得到一個和原始種群規(guī)模相同規(guī)模的新種群.

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

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

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

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

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

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

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

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

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

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

(7)

(8)

4 亂序引擎的使用

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

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

將原始題目序號放入A[1]～A[m];

i=1；

while (i<=m)

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

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

i++; }

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

5 結(jié) 語

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

參考文獻：

[1] 李美滿, 夏漢鑄, 易德成. 基于COM 技術(shù)的通用考試系統(tǒng)的設(shè)計與實現(xiàn)[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]．模式識別與人工智能，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].控制理論與應(yīng)用，1996,13(4):455-460.

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

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

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

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