楊 潔，郭喜鳳，馮貴良

（河北北方學(xué)院信息科學(xué)與工程學(xué)院，河北 張家口 075000）

1 引 言

考試是教學(xué)活動(dòng)中必不可少的一個(gè)環(huán)節(jié)，通過(guò)考試可以檢驗(yàn)學(xué)生掌握知識(shí)的情況。隨著計(jì)算機(jī)技術(shù)的發(fā)展以及網(wǎng)絡(luò)的普及，對(duì)傳統(tǒng)的教學(xué)方式產(chǎn)生了根本性的變革。很多課程已經(jīng)開(kāi)始采用在線考試方式，很多出卷方式也由計(jì)算機(jī)自動(dòng)完成代替教師手工組卷。衡量一個(gè)考試系統(tǒng)最重要的標(biāo)準(zhǔn)就是其自動(dòng)組卷算法的好壞。合理的組卷算法能夠按一定要求由計(jì)算機(jī)自動(dòng)從題庫(kù)中選擇題目，組合成一套覆蓋全部知識(shí)點(diǎn)范圍、難易適中、符合要求題量和分值等約束條件的試卷。

試卷質(zhì)量的好壞直接影響考試成績(jī)是否能反映學(xué)生的學(xué)習(xí)成果。在線考試系統(tǒng)中組卷算法是決定組卷質(zhì)量的核心因素，組卷質(zhì)量決定了試卷的質(zhì)量。因此，組卷算法的性能是本文所要討論的內(nèi)容。

2 組卷算法概述

目前國(guó)內(nèi)外考試系統(tǒng)種類(lèi)繁多，常用的組卷算法有以下四種：

2.1 隨機(jī)抽取算法

這種算法基本思想主要采取兩種隨機(jī)策略，一種是由計(jì)算機(jī)隨機(jī)抽取，滿足條件的試題放入試題庫(kù)，此過(guò)程不斷重復(fù)，直到組卷完畢為止。另一種是根據(jù)既定的指標(biāo)，隨機(jī)從試題庫(kù)中尋找試題和指標(biāo)比較，符合的放入試卷中，不符合的則放棄，重新抽取試題，如此循環(huán)，直到組卷完畢或者宣告此次組卷失?。?］。該方法實(shí)現(xiàn)簡(jiǎn)單，對(duì)于單道題的抽取運(yùn)行速度較快，應(yīng)用廣泛。但是對(duì)于整個(gè)組卷過(guò)程來(lái)說(shuō)組卷成功率低，只能尋找滿足約束條件的題目，沒(méi)有優(yōu)化試卷的功能。尤其是當(dāng)題庫(kù)中各類(lèi)型平均出題量較低時(shí)，組卷往往以失敗而告終。

2.2 基于項(xiàng)目反映的自動(dòng)組卷算法

這種算法是由適用性測(cè)試方法發(fā)展而來(lái)的，該方法的思想是盡可能的選擇符合被測(cè)試者實(shí)際水平的試題。該自動(dòng)組卷算法需要先評(píng)估被測(cè)試者的能力，在組卷過(guò)程中按照能力約束條件找出符合其平均能力的試題，然后通過(guò)循環(huán)修正試題的總體難度以達(dá)到最終的測(cè)試目的。該方法在實(shí)踐運(yùn)用中由于教師水平不同，試題庫(kù)范圍不同，很難確定各種試題的難度和分值等屬性，不能得到一個(gè)標(biāo)準(zhǔn)的約束條件，使得組卷的成功率下降。

2.3 回溯試探法

該算法是對(duì)隨機(jī)抽取算法的改進(jìn)，是以深度優(yōu)先的方式搜索問(wèn)題解的過(guò)程。根據(jù)事先約定的約束條件隨機(jī)的在試題庫(kù)中抽取試題進(jìn)行取舍。回溯選取法把產(chǎn)生的每一個(gè)狀態(tài)類(lèi)型紀(jì)錄下來(lái)，當(dāng)搜索失敗時(shí)釋放上次紀(jì)錄的狀態(tài)類(lèi)型，然后再重新進(jìn)行試探，通過(guò)不斷的回溯試探直到試卷生成完畢或退回出發(fā)點(diǎn)為止［2］。當(dāng)試卷題量和試題庫(kù)規(guī)模比較小時(shí)，該算法效率較高，避免了隨機(jī)抽取法的盲目性，組卷成功率較高。但是如果試題庫(kù)比較大，回溯試探法可能會(huì)進(jìn)行多次無(wú)效的試探，導(dǎo)致組卷時(shí)間過(guò)長(zhǎng)，而且該算法選取的試題缺乏隨機(jī)性，不能作為理想的智能組卷算法。

2.4 遺傳算法

遺傳算法是一種并行的、能夠有效優(yōu)化的算法。它從解釋自然界中生物的進(jìn)化論入手，模擬達(dá)爾文的自然進(jìn)化模型，從代表問(wèn)題潛在解集的一個(gè)種群開(kāi)始，按照優(yōu)勝略汰的原則，逐步演化出更好的最優(yōu)解［3］。運(yùn)用遺傳算法，需要在每代通過(guò)適應(yīng)度挑選最優(yōu)個(gè)體，然后通過(guò)選擇、交叉、變異、遷移等操作進(jìn)行不斷的所謂 “生存選擇”，最后收斂到一個(gè)最適應(yīng)約束條件的個(gè)體上，產(chǎn)生出最接近問(wèn)題的解。遺傳算法逐漸被用于求解最優(yōu)化的問(wèn)題中，該算法容錯(cuò)性強(qiáng)，搜索空間沒(méi)有特殊要求，適用范圍廣。但在進(jìn)化過(guò)程中容易陷入局部最優(yōu)解，發(fā)生 “早熟”現(xiàn)象。

3 組卷建模

3.1 試題屬性約束

組卷工作要考慮多方面的因素：要覆蓋教學(xué)大綱覆蓋的知識(shí)點(diǎn)，明確考試目標(biāo)，試題的數(shù)量和題型分布。同時(shí)，題庫(kù)中的每個(gè)試題都由屬性值約束。根據(jù)教育測(cè)量理論，試題的屬性約束包括：難度 （D）、區(qū)分度 （Q）、知識(shí)點(diǎn) （K）、題型 （TY）、認(rèn)知度 （S）、章節(jié) （U）、時(shí)間 （T）。其中，影響試題質(zhì)量的主要因素是試題難度和區(qū)分度。

試題的難度就是被測(cè)試者對(duì)該試題的失分率。難度系數(shù)用公式表達(dá)如下：

其中，D表示試題的難度系數(shù)，T表示該題的分值，表示被測(cè)試者在該題目的平均得分。從上式可以看出，平均分越大，該題目的難度系數(shù)越小。當(dāng)平均分為滿分時(shí)，難度系數(shù)為0，當(dāng)平均分為0時(shí)，難度系數(shù)為1，難度系數(shù)的取值范圍為：0≤D≤1。

試題的區(qū)分度是為了區(qū)分被測(cè)試者掌握知識(shí)水平的高低。高區(qū)分度的題目，如果被測(cè)試者能回答正確，說(shuō)明水平就高，反之說(shuō)明水平不高。根據(jù)研究，區(qū)分度的估算方法是：將學(xué)生按題目的得分成績(jī)排序，將排名前25%的平均成績(jī)記為H，排名后25%的平均成績(jī)記為L(zhǎng)，F(xiàn)記為該題目的總成績(jī)，則區(qū)分度用Q表示為：

當(dāng)區(qū)分度高于0.5時(shí)，認(rèn)為該題目區(qū)分度很好；低于0.2時(shí)該區(qū)分度較差，該題目不能使用；區(qū)分度位于二者之間則認(rèn)為區(qū)分度一般，需要改進(jìn)題目質(zhì)量。

作為試卷的評(píng)分指標(biāo)，試題難度D越大，試題區(qū)分度就越小。當(dāng)D＝0.5時(shí)，區(qū)分度Q最大，說(shuō)明試題分?jǐn)?shù)分布比較廣泛。

3.2 組卷問(wèn)題數(shù)學(xué)模型

智能組卷的數(shù)學(xué)模型相當(dāng)于是一個(gè)多目標(biāo)和多約束條件組合的優(yōu)化問(wèn)題。根據(jù)以上約束條件，可以將試卷題目做一個(gè)二維矩陣：

其中，n為試題總量，每一行代表一個(gè)試題，每一列都是該題目的屬性約束。目標(biāo)函數(shù)是將多個(gè)目標(biāo)依照各自權(quán)重組合成單一目標(biāo)來(lái)優(yōu)化處理以期找到問(wèn)題的近似最優(yōu)解。故能否成功組卷就是在一個(gè)試題庫(kù)A＝ ｛a1，a2，…，an｝中能否找到一個(gè)接滿足試卷的所有約束條件，其目標(biāo)函數(shù)為：

其中，權(quán)重w1＋w2＋…＋w7＝1。

4 基于分層遺傳算法的實(shí)現(xiàn)

在傳統(tǒng)遺傳算法中，因?yàn)榉N族多樣性過(guò)早喪失，交叉操作的搜索能力減弱，當(dāng)種族出現(xiàn)過(guò)早收斂時(shí)，很難有效的增加種群多樣性，會(huì)導(dǎo)致早熟現(xiàn)象發(fā)生［4］。為了保持種群的多樣性，我們采用分層次種群協(xié)同進(jìn)化的策略。該策略就是隨機(jī)生成多個(gè)種群，每個(gè)種群有多個(gè)個(gè)體，種群獨(dú)立操作，隔多代之后，各種群再進(jìn)行遷移操作以保持種群的多樣性，這樣可以得到質(zhì)量更高的解。該算法和一般的遺傳算法類(lèi)似，只是在初始種群的時(shí)候進(jìn)行了分化處理，生成多個(gè)子種群，這樣，每個(gè)子種群有各自的樣本，可以得到更優(yōu)的結(jié)果，自適用度更高。

分層次的遺傳算法主要由編碼、選擇、交叉和變異組成［5］。

4.1 編碼

在求解過(guò)程中將問(wèn)題進(jìn)行編碼主要是為了提高搜索性能。已有大量數(shù)據(jù)表明，在多約束條件下，采用整數(shù)編碼的遺傳算法效率較高，因此，本算法中采用整數(shù)編碼的方式。將每套試卷的結(jié)果映射到一個(gè)染色體上，即一個(gè)試題代表一個(gè)染色體基因。根據(jù)試題的類(lèi)型設(shè)置段數(shù)，每段編碼的基因個(gè)數(shù)正好等于該類(lèi)型試題庫(kù)中的序號(hào)。同時(shí)，染色體采用長(zhǎng)編碼策略處理，染色體中的基因個(gè)數(shù)即為試卷中試題的總數(shù)，且題型間的編碼方式是獨(dú)立的。

4.2 選擇

改進(jìn)的遺傳算法的選擇操作在子種群內(nèi)部進(jìn)行，根據(jù)其平均適應(yīng)度對(duì)子種群進(jìn)行選擇。其中，適應(yīng)度高的子種群被選擇進(jìn)入下一次迭代過(guò)程，反之則被淘汰。

4.3 交叉算子

該算法的交叉不僅是種群內(nèi)部的交叉，子種群間和子種群內(nèi)也同時(shí)進(jìn)行交叉。種群內(nèi)部進(jìn)行交叉操作后，兩子種群間也要進(jìn)行段間交叉算子的方法。完成交換后子種群數(shù)增加一倍，為了保證種群數(shù)目的不變，在做交叉算子的兩種群間進(jìn)行適應(yīng)度比較，適應(yīng)度較大的保留，反之淘汰。

4.4 變異算子

因?yàn)樽儺愃阕邮怯行「怕适录a(chǎn)生的，為了提高搜索速度在改進(jìn)算法中采用單點(diǎn)變異算子。隨機(jī)選取一個(gè)染色體，然后生成0-1的隨機(jī)數(shù)r，當(dāng)r小于其變異概率則在每段隨機(jī)生成一個(gè)變異點(diǎn)，即在該類(lèi)題型段中隨機(jī)選取一個(gè)未被選中的題目并標(biāo)記為選中，同時(shí)該題置換成未選中，反之不進(jìn)行變異操作。

5 數(shù)據(jù)分析

下表1為傳統(tǒng)遺傳算法和改進(jìn)后的算法在考試系統(tǒng)中組卷成功率數(shù)據(jù)的對(duì)比，其中1表示傳統(tǒng)算法，2表示改進(jìn)后的遺傳算法：

表1 個(gè)題型平均約束條件對(duì)比

通過(guò)以上數(shù)據(jù)表明，實(shí)際應(yīng)用中遺傳算法中易出現(xiàn)收斂速度慢、穩(wěn)定性差、易早熟的特點(diǎn)。通過(guò)修改遺傳算法中的算子以及對(duì)適應(yīng)度函數(shù)進(jìn)行尺度變化可以避免早熟現(xiàn)象的發(fā)生。但在單種群基礎(chǔ)上的改進(jìn)只能控制個(gè)體進(jìn)化，很難達(dá)到理想結(jié)果，選擇多種群進(jìn)化可以改善遺傳算法的全局收斂性，控制早熟度。改進(jìn)的遺傳算法在全局搜索性能和收斂速度上都有明顯的優(yōu)勢(shì)，組卷質(zhì)量較高。能夠滿足實(shí)際的需求。

6 總 結(jié)

隨著計(jì)算機(jī)技術(shù)的發(fā)展和普及，計(jì)算機(jī)輔助教學(xué)已經(jīng)作為一門(mén)新的教學(xué)方式越來(lái)越受到廣大教育工作者的關(guān)注。智能組卷作為計(jì)算機(jī)輔助教學(xué)的核心也是大家關(guān)注的焦點(diǎn)。組卷算法是評(píng)價(jià)一個(gè)組卷好壞的重要因素［6］。

分層次的遺傳算法由于種群的多樣性，提高了局部收斂度和全局的搜索能力，基于該算法的自動(dòng)組卷系統(tǒng)組卷質(zhì)量高，知識(shí)點(diǎn)分布均勻，試題難易適中，降低了試卷的重復(fù)率，同時(shí)降低了人工組卷中由于人為因素所造成的失誤。真正實(shí)現(xiàn)了教考分離和考務(wù)自動(dòng)化。

［1］路平，王敏娟，萬(wàn)昆.試題庫(kù)自動(dòng)組卷策略研究［J］.電腦開(kāi)發(fā)與應(yīng)用，2001，14（02）：9-11.

［2］王宇穎，侯爽，郭茂祖.題庫(kù)系統(tǒng)市局自動(dòng)生成算法研究［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2003，35（03）：342-346.

［3］趙忠平，楊浩.智能組卷系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.山西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，22（02）：28-32.

［4］蘇小紅，楊博，王亞?wèn)|.基于進(jìn)化穩(wěn)定策略的遺傳算法［J］.軟件學(xué)報(bào)，2003，14（11）：1863-1868.

［5］劉彬等.智能組卷系統(tǒng)試題庫(kù)結(jié)構(gòu)的研究［J］.信息技術(shù)，2002，3（07）：2-4.

［6］劉樹(shù)剛.一種 web測(cè)試中的組卷策略及其改進(jìn)［J］.煙臺(tái)大學(xué)學(xué)報(bào)，2004，17（01）：59-64.