網(wǎng)絡(luò)化考試中智能組卷方法研究*

張宗飛

（臺(tái)州職業(yè)技術(shù)學(xué)院電氣信息學(xué)院，浙江臺(tái)州318000)

網(wǎng)絡(luò)化考試中智能組卷方法研究*

張宗飛

（臺(tái)州職業(yè)技術(shù)學(xué)院電氣信息學(xué)院，浙江臺(tái)州318000)

教育信息化背景下，眾多行業(yè)已經(jīng)或準(zhǔn)備實(shí)施網(wǎng)絡(luò)化考試，對(duì)網(wǎng)絡(luò)化考試系統(tǒng)功能也提出了更高要求，文章對(duì)網(wǎng)絡(luò)化考試系統(tǒng)中的一項(xiàng)核心功能——組卷進(jìn)行研究，提出了一種智能化的組卷方法。該方法首先對(duì)題庫(kù)建立一個(gè)目標(biāo)狀態(tài)矩陣；然后按照量子進(jìn)化算法求解多目標(biāo)約束組合優(yōu)化問(wèn)題的方法從矩陣中選取最優(yōu)化的行組合，從而生成一份最接近用戶各項(xiàng)需求的試卷；最后使用《面向?qū)ο蟪绦蛟O(shè)計(jì)》課程試題庫(kù)進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，該方法能夠根據(jù)用戶需求自動(dòng)完成組卷過(guò)程，而且組卷效率和成功率都比較高。

網(wǎng)絡(luò)化考試；智能組卷；組卷目標(biāo)；試題庫(kù)

一、引言

隨著教育信息化的發(fā)展，對(duì)標(biāo)準(zhǔn)化考試提出了新的要求，建立網(wǎng)絡(luò)化考試系統(tǒng)是教育信息化背景下實(shí)行標(biāo)準(zhǔn)化考試的一項(xiàng)重要內(nèi)容[1]，而智能組卷作為網(wǎng)絡(luò)化考試系統(tǒng)的核心功能之一，引起了許多專家的重視，成為網(wǎng)絡(luò)化考試系統(tǒng)研究的一個(gè)重要方向。在早期的計(jì)算機(jī)自動(dòng)組卷方法中，常用的有隨機(jī)選取法和回溯試探法[2]，兩種方法雖然算法結(jié)構(gòu)簡(jiǎn)單，但是組卷時(shí)間長(zhǎng)，成功率低，智能性差，得到的試卷質(zhì)量不高，不能滿足隨機(jī)性、科學(xué)性、合理性的組卷需求。

智能組卷是指根據(jù)用戶提出的多項(xiàng)組卷要求，自動(dòng)地從試題庫(kù)中選擇滿足各項(xiàng)需求的試題構(gòu)成試卷的過(guò)程，智能組卷實(shí)質(zhì)上是一類多目標(biāo)約束組合優(yōu)化問(wèn)題。據(jù)此，近年來(lái)一些研究者提出了使用遺傳算法來(lái)求解智能組卷問(wèn)題[3,4]，但是由于此類問(wèn)題具有NP難度，限制了遺傳算法的優(yōu)化性能，難以獲得滿意的組卷性能。

量子進(jìn)化算法 (Quantum Evolutionary Algorithm，QEA)是量子計(jì)算理論與進(jìn)化計(jì)算原理相結(jié)合的產(chǎn)物，是一種新發(fā)展起來(lái)的智能優(yōu)化算法[5]。QEA使用量子比特編碼來(lái)表示染色體，增加了種群的多樣性，從而避免了早熟收斂；通過(guò)量子門更新染色體，保證了進(jìn)化方向，提高了尋優(yōu)能力和尋優(yōu)速度。QEA這種獨(dú)特的編碼和進(jìn)化機(jī)制，使得算法在求解組合優(yōu)化問(wèn)題時(shí)具有明顯的優(yōu)勢(shì)，尋優(yōu)能力和尋優(yōu)速度都要優(yōu)于遺傳算法。本文使用QEA來(lái)求解智能組卷問(wèn)題，使用QEA的尋優(yōu)機(jī)制快速高質(zhì)地完成智能組卷過(guò)程。

二、組卷問(wèn)題的模型構(gòu)建

1.組卷指標(biāo)選擇

智能組卷的操作對(duì)象是題庫(kù)中的試題，組卷時(shí)要求能根據(jù)各項(xiàng)指標(biāo)自動(dòng)地從題庫(kù)中抽取試題。組卷指標(biāo)由試題屬性來(lái)確定，試題的屬性有很多，通常有題型、內(nèi)容、層次、題分、知識(shí)點(diǎn)、難度、區(qū)分度、題時(shí)、曝光度、信度、效度等，這些屬性構(gòu)成了組卷的約束條件。我們的實(shí)驗(yàn)表明：約束條件過(guò)多會(huì)增加組卷難度，降低組卷效率，并且容易導(dǎo)致組卷失敗，因此本文根據(jù)試題屬性對(duì)組卷的重要性以及屬性之間的內(nèi)在聯(lián)系，選取題型、題分、難度、區(qū)分度、題時(shí)5個(gè)試題屬性作為組卷的約束條件，對(duì)它們的定義如下：

題型：題庫(kù)中試題的類型，每類題型賦給一個(gè)整數(shù)值。我們?cè)谇捌谘芯恐幸呀?jīng)開(kāi)發(fā)了《面向?qū)ο蟪绦蛟O(shè)計(jì)》課程的題庫(kù)（以下簡(jiǎn)稱本文題庫(kù)），包含判斷題、選擇題、填空題、編程題、綜合應(yīng)用題，給它們的賦值分別是1、2、3、4、5。

題分：題庫(kù)中試題的分值，每一題試題都有相應(yīng)分值。本文題庫(kù)中試題的分值為1-20的整數(shù)。

難度：題庫(kù)中試題的難易程度，每一題試題都賦給相應(yīng)的難度系數(shù)值。我們通過(guò)抽樣測(cè)試，將本文題庫(kù)中的試題難度分為難、較難、中、較易、易5個(gè)等級(jí)，并賦給難度系數(shù)為0.9、0.7、0.5、0.3、0.1。

區(qū)分度：題庫(kù)中試題對(duì)被測(cè)試對(duì)象的區(qū)分程度，每一題試題都賦給相應(yīng)的區(qū)分度系數(shù)值。我們通過(guò)抽樣測(cè)試，將本文題庫(kù)中的試題區(qū)分度分為高、中、低3個(gè)等級(jí)，并賦給區(qū)分度系數(shù)為0.8、0.5、0.3。

題時(shí)：題庫(kù)中某試題完成所需的估計(jì)時(shí)間，每一題試題都賦給一個(gè)估計(jì)完成時(shí)間。我們通過(guò)抽樣測(cè)試，獲得了本文題庫(kù)中每一試題的估計(jì)完成時(shí)間。

2.組卷模型設(shè)計(jì)

確定組卷指標(biāo)后，可以根據(jù)組卷指標(biāo)對(duì)題庫(kù)建立一個(gè)由指標(biāo)所對(duì)應(yīng)的試題屬性值構(gòu)成的目標(biāo)狀態(tài)矩陣，由上面選取的5個(gè)指標(biāo)可以獲得一個(gè)nX5的目標(biāo)狀態(tài)矩陣T：

其中，n代表題庫(kù)中試題的總數(shù)，矩陣T中每行表示一題試題、每列表示題庫(kù)中全部試題的某個(gè)屬性，此時(shí)組卷問(wèn)題的求解轉(zhuǎn)換為∶根據(jù)用戶確定的組卷目標(biāo)要求，在矩陣T中尋找滿足組卷目標(biāo)要求的行組合。它的解可以用一個(gè)二進(jìn)制串來(lái)表示：(S1，S2……Sn）Si∈{0,1}，i=1，2……，n，Si=1表示第i題試題被選擇，反之表示第i題試題不被選擇。

組卷目標(biāo)要求根據(jù)組卷指標(biāo)設(shè)置，對(duì)應(yīng)著組卷約束條件，矩陣T中的試題屬性構(gòu)成的組卷約束條件如下：

三、基于量子進(jìn)化算法的智能組卷算法設(shè)計(jì)

分析組卷模型設(shè)計(jì)的結(jié)論可知，組卷問(wèn)題屬于多目標(biāo)約束組合優(yōu)化問(wèn)題，大量的研究已經(jīng)證明QEA在求解多目標(biāo)約束組合優(yōu)化問(wèn)題時(shí)效果明顯，據(jù)此我們將QEA應(yīng)用到智能組卷問(wèn)題中，設(shè)計(jì)一種能夠自動(dòng)獲得滿足用戶各項(xiàng)需求的試卷的智能組卷算法。算法設(shè)計(jì)的基本思想是對(duì)題庫(kù)中的試題編碼形成初始種群，根據(jù)適應(yīng)度值對(duì)其逐代優(yōu)化，生成一份滿足組卷要求的最優(yōu)試卷。

1.量子染色體構(gòu)造

使用QEA求解具體問(wèn)題時(shí)，首先應(yīng)對(duì)問(wèn)題的解進(jìn)行編碼構(gòu)成QEA中的量子染色體，本文對(duì)量子染色體的構(gòu)造過(guò)程如下：將狀態(tài)矩陣T映射為QEA中的個(gè)體（即量子染色體），并按照題型屬性將染色體的量子位進(jìn)行分段。對(duì)于本文題庫(kù)，共有5類題型，假設(shè)各類題型的試題數(shù)分別為n1、n2、……、n5，則量子染色體結(jié)構(gòu)如下：

2.種群初始化

隨機(jī)產(chǎn)生若干個(gè)（5）式結(jié)構(gòu)的量子染色體構(gòu)成QEA的初始種群（m為種群大小），然后將量子染色體的各量子位初始化為等概率狀態(tài)，即將量子位概率幅[αi，βi]初始化為。

3.種群觀測(cè)

種群觀測(cè)是對(duì)初始化后的量子態(tài)種群中個(gè)體的各量子位實(shí)施測(cè)量操作，目的是使各個(gè)體量子位從不確定的概率態(tài)坍塌到確定的基態(tài)，獲得觀測(cè)態(tài)個(gè)體。測(cè)量操作的過(guò)程是：對(duì)于量子染色體的每一個(gè)量子位，隨機(jī)產(chǎn)生[0，1]之間的一個(gè)常數(shù)r，若為染色體第i個(gè)量子位的概率幅），則該量子位（xi）取1，否則取0。種群觀測(cè)后，量子態(tài)種群Q(t)就轉(zhuǎn)化為了觀測(cè)態(tài)種群P(t)，P(t)，其中，觀測(cè)態(tài)個(gè)體是長(zhǎng)度為n的二進(jìn)制串（x1,x2……xn）,xi∈{0,1}。

4.適應(yīng)度函數(shù)設(shè)計(jì)

QEA中使用適應(yīng)度來(lái)衡量種群中個(gè)體的優(yōu)劣，個(gè)體的適應(yīng)度值通過(guò)適應(yīng)度函數(shù)來(lái)計(jì)算，適應(yīng)度函數(shù)通常由問(wèn)題的目標(biāo)函數(shù)轉(zhuǎn)化而得到。分析組卷約束條件可知，試卷總分是剛性約束，在每一次組卷過(guò)程都必須完全滿足，而試卷完成時(shí)間、試卷難度、試卷區(qū)分度是柔性約束，在組卷時(shí)應(yīng)盡量接近用戶指定的期望值，因此組卷的目標(biāo)函數(shù)只需考慮柔性約束。適應(yīng)度函數(shù)的設(shè)計(jì)過(guò)程如下：

step1，根據(jù)（2）、（3）、（4）式的約束條件，采用與用戶期望值的誤差百分比作為單個(gè)指標(biāo)的目標(biāo)函數(shù)：

其中，time、hard、dis分別為對(duì)應(yīng)指標(biāo)的期望值。

step2，為每個(gè)指標(biāo)分配權(quán)重并將其組合為組卷目標(biāo)函數(shù)：

其中，w1、w2、w3分別為對(duì)應(yīng)指標(biāo)的權(quán)重。

Step3，采用指數(shù)比例變換方法將目標(biāo)函數(shù)轉(zhuǎn)換成適應(yīng)度函數(shù)：

其中，ρ為放大系數(shù)。

5.染色體更新

染色體更新的作用是實(shí)現(xiàn)種群的進(jìn)化，通常使用（11）式所示的量子旋轉(zhuǎn)門來(lái)更新量子態(tài)種群中的個(gè)體，通過(guò)（12）式所示的將量子旋轉(zhuǎn)門作用于染色體的量子位，使量子位朝著目標(biāo)方向偏轉(zhuǎn)。

6.染色體交叉

染色體交叉的作用是增加種群的多樣性，防止算法陷入早熟收斂。染色體交叉的方法很多，本文根據(jù)所設(shè)計(jì)的染色體結(jié)構(gòu)特點(diǎn)，以各題型分界處為斷點(diǎn)，進(jìn)行全干擾交叉。

7.搜索停止設(shè)定

算法在解空間搜索到一定程度后，應(yīng)該能夠停止搜索，輸出最優(yōu)個(gè)體。本文以到達(dá)最大進(jìn)化代數(shù)或獲得最優(yōu)個(gè)體為搜索停止條件。最大進(jìn)化代數(shù)可事先設(shè)定，最優(yōu)個(gè)體的判定方法為：連續(xù)5代進(jìn)化中最優(yōu)個(gè)體適應(yīng)度值的變化小于給定的極小閥值δ。

四、實(shí)驗(yàn)驗(yàn)證

1.實(shí)驗(yàn)對(duì)象與環(huán)境

我們以前期研究所開(kāi)發(fā)的 《面向?qū)ο蟪绦蛟O(shè)計(jì)》課程試題庫(kù)為操作對(duì)象，對(duì)本文提出的智能組卷算法進(jìn)行驗(yàn)證，并與文[4]算法進(jìn)行比較。實(shí)驗(yàn)在一臺(tái)Intel(R)Pentium(R)4 CPU 2.60GHZ、1.00GB內(nèi)存、Microsoft Windows XP Professional SP2操作系統(tǒng)的單機(jī)上進(jìn)行，在Eclipse Standard環(huán)境中使用Java語(yǔ)言完成算法代碼。

2.實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)中，試卷參數(shù)設(shè)置為：試卷總分設(shè)定值為100，試卷完成時(shí)間期望值為120，試卷難度期望值為0.6，試卷區(qū)分度期望值為0.5；本文算法參數(shù)設(shè)置為：種群大小為50，搜索停止閥值δ為0.01,最大進(jìn)化代數(shù)T為300，組卷指標(biāo)權(quán)重系數(shù)w1、w2、w3分別為0.4、0.3、0.3，適應(yīng)度函數(shù)的指數(shù)比例放大系數(shù)ρ為10；文[4]算法參數(shù)設(shè)置為：種群大小為80，交叉概率、變異概率按文[4]中自適應(yīng)設(shè)置，最大進(jìn)化代數(shù)T為300。

3.實(shí)驗(yàn)結(jié)果與分析

分別運(yùn)行本文算法和文[4]算法進(jìn)行組卷測(cè)試，以運(yùn)行時(shí)間、進(jìn)化代數(shù)、組卷成功率為指標(biāo)來(lái)比較算法的性能，實(shí)驗(yàn)進(jìn)行組卷50次，運(yùn)行結(jié)果如表1所示。

表1 兩種算法的實(shí)驗(yàn)結(jié)果

由于量子進(jìn)化算法和遺傳算法都能對(duì)解空間進(jìn)行全局搜索，并且在搜索過(guò)程中逐步向包含最優(yōu)解的方向調(diào)整搜索空間，從而易于找到最優(yōu)解，因此在實(shí)驗(yàn)結(jié)果中可以看出兩種算法的組卷成功率都比較高。通過(guò)表1數(shù)據(jù)對(duì)兩種算法進(jìn)行比較，可以得出：本文算法的組卷效率明顯高于文[4]算法，組卷成功率也略好，表明本文算法的尋優(yōu)性能優(yōu)于文[4]算法。

五、結(jié)束語(yǔ)

自動(dòng)、高效的組卷過(guò)程和滿足用戶需求的組卷結(jié)果是教育信息化背景下對(duì)網(wǎng)絡(luò)化考試系統(tǒng)組卷功能的要求，本文研究了網(wǎng)絡(luò)化考試系統(tǒng)中的組卷問(wèn)題，將組卷轉(zhuǎn)化為多目標(biāo)約束組合優(yōu)化問(wèn)題進(jìn)行求解，提出了一種智能化的組卷方法，并使用《面向?qū)ο蟪绦蛟O(shè)計(jì)》課程試題庫(kù)對(duì)方法的有效性進(jìn)行了實(shí)驗(yàn)驗(yàn)證。

[1]雍丹,趙丹維.開(kāi)放教育網(wǎng)絡(luò)化考試的影響因素及對(duì)策探討[J].中國(guó)教育信息化,2012(15):33-35.

[2]代保新.基于智能組卷的在線考試系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].長(zhǎng)春:吉林大學(xué),2014.

[3]肖理慶,徐曉菊.改進(jìn)遺傳算法智能組卷研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(10):3970-3974.

[4]許永達(dá).基于改進(jìn)遺傳算法的智能組卷研究[J].計(jì)算機(jī)與數(shù)字工程,2013,41(2):176-178.

[5]Han K H,Kim J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization [J].IEEE Trans on Evolutionary Computation,2002(6):580-593.

（編輯：魯利瑞）

G434文獻(xiàn)標(biāo)識(shí)碼：A

：1673-8454（2015）16-0079-03

浙江省教育廳科研項(xiàng)目（編號(hào)：Y201329790）；全國(guó)教育信息技術(shù)研究課題（編號(hào)：146232200）。