基于知識點的改進型遺傳組卷算法的研究

吳敏寧

（榆林學院 陜西 榆林 719000）

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

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

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

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

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

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

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

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

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

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

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

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

2 組卷系統(tǒng)總體設計

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

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

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

3 組卷系統(tǒng)詳細設計

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

4 基于知識點的改進型遺傳組卷算法的研究

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

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

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

4.1 初始化參數(shù)

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

4.2 題庫選題

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

4.3 按題型選擇試題過程

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

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

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

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

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

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

②運用遺傳算法求解。

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

①運用遺傳算法求解。

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

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

4.4 獲得試卷編號

終止算法，獲得試卷編號。

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

5 結(jié) 論

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

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

[2]劉藝.自動組卷算法的研究[J].渤海大學學報：自然科學版，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]潘中良，熊銀根.一種基于小生境的遺傳算法及其應用[J].中山大學學報：自然科學版，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)實現(xiàn)[D].重慶：重慶大學，2008:32-33.

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

[6]周敏.遺傳算法的若干改進及應用[D].北京：中國科學院軟件研究所，2001.