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

吳敏寧

（榆林學院 陜西 榆林 719000）

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

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

1 組卷系統需求分析

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

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

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

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

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

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

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

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

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

2 組卷系統總體設計

該組卷系統結構圖如圖1所示，為了保證試題質量及試題庫的保密性，設置了用戶登陸權限，嚴格控制用戶登錄，經過相關部門或領導審核批準后，用戶可登陸題庫進行組卷，通過審核方式，不僅加強了試題的保密性，還增強了教師的責任感，確保出題組卷的內容不被泄露。

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

圖1 組卷管理結構圖Fig.1 Structure diagram of test paper and management

3 組卷系統詳細設計

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

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

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

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

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

4.1 初始化參數

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

4.2 題庫選題

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

4.3 按題型選擇試題過程

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

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

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

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

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

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

②運用遺傳算法求解。

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

①運用遺傳算法求解。

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

記錄總數為K，若K

4.4 獲得試卷編號

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

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

5 結 論

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

[1]李香英.高校題庫建設與試卷生成系統[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]余紅朝.基于遺傳算法的組卷研究及題庫系統實現[D].重慶：重慶大學，2008:32-33.

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

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