基于知識(shí)點(diǎn)的改進(jìn)型遺傳組卷算法的研究

吳敏寧

（榆林學(xué)院 陜西 榆林 719000）

隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，網(wǎng)絡(luò)應(yīng)用范圍的不斷擴(kuò)大，教育領(lǐng)域與計(jì)算機(jī)技術(shù)的結(jié)合愈見緊密，無紙化在線考試系統(tǒng)已成為深化教學(xué)改革，推進(jìn)教學(xué)創(chuàng)新，提高教務(wù)效率的重要平臺(tái)[1]。自動(dòng)組卷是無紙化在線考試系統(tǒng)中一個(gè)重要模塊，自動(dòng)組卷策略的研究也得到眾多專家學(xué)者的注意。自動(dòng)組卷是按照一定的組卷要求，由計(jì)算機(jī)自動(dòng)從試題庫中選擇試題，組成符合特定總分、總時(shí)間要求和試題題型、試題數(shù)量、知識(shí)點(diǎn)、難度等約束條件要求的試卷。組卷問題是一個(gè)在一定約束條件下的多目標(biāo)參數(shù)優(yōu)化問題，采用傳統(tǒng)的數(shù)學(xué)方法求解十分困難，自動(dòng)組卷的效率和質(zhì)量完全取決于試題庫設(shè)計(jì)以及抽題算法的設(shè)計(jì)。由于自動(dòng)組卷要求生成的試卷能最大程度地滿足用戶的不同需要并具有隨機(jī)性、合理性，因此本項(xiàng)目就如何設(shè)計(jì)一個(gè)算法從試題庫中既快又好地抽出一組最符合考試要求的試題進(jìn)行了研究和設(shè)計(jì)。

總之，本項(xiàng)目將針對(duì)在線考試問題進(jìn)行研究與實(shí)踐，研究采用先進(jìn)的開發(fā)技術(shù)，目的是設(shè)計(jì)出滿足在線考試系統(tǒng)要求的，簡(jiǎn)單的、高效的、可行的、滿足用戶需求的自動(dòng)組卷策略。

1 組卷系統(tǒng)需求分析

設(shè)計(jì)一個(gè)性能良好的組卷管理系統(tǒng)，明確用戶需求非常重要。通過對(duì)用戶傳統(tǒng)卷面考試方式的業(yè)務(wù)流程進(jìn)行調(diào)研，對(duì)用戶生成試卷、組織試卷，管理試卷、輸出試卷和安全問題等要求進(jìn)行了詳細(xì)的探討，確定出用戶目前的主要需求如下：

1）用戶界面友好，使用方便。

2）組卷時(shí)，用戶需要輸入正確的用戶名和密碼進(jìn)行身份驗(yàn)證，只有經(jīng)過授權(quán)的用戶才能登錄組卷管理子系統(tǒng)進(jìn)行操作。

3）組卷前，按試卷需求用戶需給出考試藍(lán)圖，考試藍(lán)圖可修改。

4）組卷時(shí)，用戶根據(jù)考試藍(lán)圖，設(shè)置組卷參數(shù)，組卷的各個(gè)屬性指標(biāo)如難度系數(shù)、區(qū)分度、知識(shí)點(diǎn)等可根據(jù)學(xué)生的水平來決定，用戶可以確定各種題型的題目個(gè)數(shù)、難度、知識(shí)點(diǎn)、區(qū)分度、分值、時(shí)間等。

5）用戶可以選擇多種組卷方式，不同的組卷方式滿足不同的要求，最終能生成滿足用戶需求的試卷。

6）用戶通過一次參數(shù)設(shè)置，選擇其中一種組卷方式，能組成多套滿足用戶的試卷，可供上機(jī)考試，并且要求試卷質(zhì)量好，試卷知識(shí)點(diǎn)重復(fù)率低。

7）用戶能根據(jù)設(shè)置的參數(shù)生成試卷，并能轉(zhuǎn)換保存成word文檔，可套入已有考試模板打印輸出，供紙質(zhì)考試使用。

8）能進(jìn)行系統(tǒng)備份操作與系統(tǒng)恢復(fù)功能，避免由于系統(tǒng)崩潰導(dǎo)致信息丟失，需保證數(shù)據(jù)的安全性，防止試卷失密，具備有效的系統(tǒng)備份和恢復(fù)功能。

2 組卷系統(tǒng)總體設(shè)計(jì)

該組卷系統(tǒng)結(jié)構(gòu)圖如圖1所示，為了保證試題質(zhì)量及試題庫的保密性，設(shè)置了用戶登陸權(quán)限，嚴(yán)格控制用戶登錄，經(jīng)過相關(guān)部門或領(lǐng)導(dǎo)審核批準(zhǔn)后，用戶可登陸題庫進(jìn)行組卷，通過審核方式，不僅加強(qiáng)了試題的保密性，還增強(qiáng)了教師的責(zé)任感，確保出題組卷的內(nèi)容不被泄露。

組卷時(shí)，用戶首先需要提供考試藍(lán)圖，考試藍(lán)圖可以添加、修改、刪除、查詢、審核?？荚囁{(lán)圖確定后用戶需設(shè)置組卷參數(shù)，選擇組卷方式，生成的試卷提供給上機(jī)考試，并將生成試卷存入套卷管理庫，以便將來查詢、分析。生成試卷有兩種方法：手動(dòng)組卷、自動(dòng)組卷。手動(dòng)組卷效率比較低，自動(dòng)組卷主要取決于組卷算法，如果有好的算法支持，可以生成滿足用戶需求的較優(yōu)試卷。

圖1 組卷管理結(jié)構(gòu)圖Fig.1 Structure diagram of test paper and management

3 組卷系統(tǒng)詳細(xì)設(shè)計(jì)

試題生成包括組卷參數(shù)設(shè)置和組卷策略選擇。組卷方案的設(shè)置主要應(yīng)用在自動(dòng)組卷當(dāng)中，可以預(yù)先設(shè)置好試題的組卷方案，在自動(dòng)組卷的時(shí)候可以直接調(diào)用組卷方案，而不需要重新設(shè)置，用戶可以對(duì)試卷方案進(jìn)行新建、修改、刪除、查詢、瀏覽等操作。手動(dòng)組卷是教務(wù)人員根據(jù)知識(shí)點(diǎn)，學(xué)生的實(shí)際情況，按照試題類型、難度系數(shù)等，在組卷向?qū)У闹笇?dǎo)下生成試卷。用戶在組卷過程中可以選擇試題、瀏覽試題、查找試題、在試卷中添加、刪除試題、生成試卷，瀏覽試卷、保存、刪除試卷等操作。自動(dòng)組卷是在自動(dòng)組卷的向?qū)拢鶕?jù)考生藍(lán)圖進(jìn)行參數(shù)設(shè)置，參數(shù)設(shè)置后，審查藍(lán)圖是否合理，如果合理，組卷，如果不合理，退出修改考生藍(lán)圖，用戶也可以直接調(diào)用設(shè)置好的組卷方案進(jìn)行自動(dòng)抽取試題。在組卷過程中，用戶可以對(duì)生成尚未存盤試卷進(jìn)行調(diào)整（添加、刪除、替換試卷中的試題），瀏覽、保存、刪除試卷等操作。

4 基于知識(shí)點(diǎn)的改進(jìn)型遺傳組卷算法的研究

組卷算法是建立在遺傳算法的基礎(chǔ)上，結(jié)合隨機(jī)數(shù)組卷算法的優(yōu)點(diǎn)，以題型為單位篩選含有此題型的知識(shí)點(diǎn)，多次篩選知識(shí)點(diǎn)，篩選方式采用隨機(jī)算法，得到的知識(shí)點(diǎn)更接近需求，根據(jù)篩選結(jié)果重新組合試卷目標(biāo)，種群編碼[2]采用分區(qū)分別編碼，減少種群染色體編碼長度，適應(yīng)度函數(shù)充分考慮各參數(shù)對(duì)試卷質(zhì)量的影響，采用分別定標(biāo)和設(shè)定比重；用最佳個(gè)體保持法和適應(yīng)度比例相結(jié)合的方法計(jì)算樣本的選擇概率[3]，交叉操作是用模擬三點(diǎn)交叉的方法進(jìn)行兩點(diǎn)交叉進(jìn)行，為使算法盡快收斂，終止條件不單以遺傳代數(shù)作為條件，增加了若干代內(nèi)最優(yōu)個(gè)體適應(yīng)度的比較，并以比較結(jié)果作為條件[4]。

本系統(tǒng)自動(dòng)組卷算法流程圖如圖2所示，主要有初始化參數(shù)、題庫選題、按題型選題3大步。

圖2 基于知識(shí)點(diǎn)的遺產(chǎn)算法流程圖Fig.2 Flow chart of improved genetic algorithm base on the knowledge points

4.1 初始化參數(shù)

首先根據(jù)題型編碼，從數(shù)據(jù)庫選擇考查范圍中包含該題型的試題的知識(shí)點(diǎn)，并記錄知識(shí)點(diǎn)總數(shù)；逐個(gè)檢查并記錄題型知識(shí)點(diǎn)分布狀況的最小值，初始化題型返回信息，如題型名稱等信息[5]。然后檢查經(jīng)過初始化參數(shù)的題型現(xiàn)有知識(shí)點(diǎn)總數(shù)，若總數(shù)與題型考查范圍的知識(shí)點(diǎn)總數(shù)不一致，則按照劃分等級(jí)相同或者相近的基本原則對(duì)知識(shí)點(diǎn)-難度，知識(shí)點(diǎn)分類進(jìn)行合并[6]。

4.2 題庫選題

以該科目全部題型和知識(shí)點(diǎn)作為查詢條件，從試題庫中選擇試題集合。

4.3 按題型選擇試題過程

主要運(yùn)用遺傳操作，同時(shí)結(jié)合隨機(jī)數(shù)組卷算法試題選擇的不確定優(yōu)點(diǎn)，算法具體描述如下：

1） 檢查題型的平均難度 Check（PJ），如果 Check（SM）為難度的最大值或最小值，則轉(zhuǎn)到步驟2）；否則，轉(zhuǎn)步驟3）。

2）選擇該難度的所有試題，記試題總數(shù)為 M，設(shè)Q（N）表示題型要求的試題數(shù)，若M≤Q（N），轉(zhuǎn)下面的步驟①；否則，轉(zhuǎn)步驟②。

①選擇這M道試題，然后從試題庫中選擇其他知識(shí)點(diǎn)該難度的試題，設(shè)總數(shù) K，若 K≥Q（N）-M，則轉(zhuǎn)到 a）；否則，轉(zhuǎn)到 b）。

a運(yùn)用隨機(jī)數(shù)組卷算法選擇Q（N）-M道試題。

b選擇全部的K道試題，若Check（SM）為最低難度，則終止運(yùn)算；否則，按難度梯度（從高到低）選擇試題進(jìn)行補(bǔ)充。原則是在保證試卷質(zhì)量的前提下，優(yōu)先考慮題型的考查范圍內(nèi)的試題。

②運(yùn)用遺傳算法求解。

3）設(shè)M表示當(dāng)前試題總數(shù)，Q（N）表示題型要求的試題數(shù)，若 M>Q（N），則轉(zhuǎn)到①；否則，轉(zhuǎn)到②。

①運(yùn)用遺傳算法求解。

②選擇這M道試題，并調(diào)整試卷指標(biāo)，從試題庫中選擇該題型其他試題，

記錄總數(shù)為K，若K

4.4 獲得試卷編號(hào)

終止算法，獲得試卷編號(hào)。

圖中的 NZ（X）、NZ（Y）分別是過濾知識(shí)點(diǎn)后當(dāng)前的知識(shí)點(diǎn)總數(shù)和預(yù)設(shè)要求的知識(shí)點(diǎn)總數(shù)的函數(shù)。Chech（PJ）、Chech（SM）分別是檢查題型平均難度是否為最高值或者是最低值函數(shù)和檢查題型現(xiàn)有試題數(shù)目和預(yù)設(shè)要求的試題數(shù)目的關(guān)系函數(shù)。

5 結(jié) 論

該組卷系統(tǒng)自動(dòng)組卷策略采用的是基于知識(shí)點(diǎn)的遺傳算法，首先按題型對(duì)知識(shí)點(diǎn)進(jìn)行多次篩選，然后對(duì)試題難度進(jìn)行判斷，再按照遺產(chǎn)算法進(jìn)行組卷，該自動(dòng)組卷算法降低了試卷中知識(shí)點(diǎn)的重復(fù)率，提高了試卷的質(zhì)量，使得無紙化考試系統(tǒng)的效率、可靠性、穩(wěn)定性提高。

[1]李香英.高校題庫建設(shè)與試卷生成系統(tǒng)[D].濟(jì)南：山東大學(xué)，2007.

[2]劉藝.自動(dòng)組卷算法的研究[J].渤海大學(xué)學(xué)報(bào)：自然科學(xué)版，2005（5）:124-128.LIU Yi.Research of automatic test paper generation algorithm[J].Journal of Bohai University： Natural Science Edition，2005（5）:124-128.

[3]潘中良，熊銀根.一種基于小生境的遺傳算法及其應(yīng)用[J].中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2001（5）:44-46，51.PANG Zhong-liang，XIONG Yin-gen.A method based on Niche Genetic Algorithm and its application[J].Journal of Sun Yat-Sen University： Natural Science Edition，2001，5:44-46，51.

[4]余紅朝.基于遺傳算法的組卷研究及題庫系統(tǒng)實(shí)現(xiàn)[D].重慶：重慶大學(xué)，2008:32-33.

[5]陳宇，治平.發(fā)式遺傳算法組卷模型研究[J].計(jì)算技術(shù)與自動(dòng)化，2006（5）:39.CHEN Yu，ZHIPing.Research ofHair-style genetic algorithmtestmodel[J].ComputingTechnologyandAutomation，2006（5）:39.

[6]周敏.遺傳算法的若干改進(jìn)及應(yīng)用[D].北京：中國科學(xué)院軟件研究所，2001.