網絡化考試組卷算法及QTI標準應用研究

摘 要： 試卷的質量直接決定了考試的效果，優秀的考試組卷算法能夠更好的滿足用戶設定的標準。結合現有算法和項目實際需求，基于粒子群優化算法的流程，提出了五項改進措施，包括編碼方案和試卷適應度值計算方法的改進，提出了新的粒子學習過程，使粒子能夠逐代變好，更快收斂到全局最優解。在改進的粒子群優化算法中，又加入了混沌初始化和混沌擾動，通過算法實驗與改進，設計并實現一種新的組卷方法以期得到更好的結果，并采用QTI標準進行試題存儲，實現試題共享，證明在實際應用中的可行性。

關鍵詞： 組卷； 粒子群優化算法； 改進與優化； QTI標準

中圖分類號： TN915?34； TM417 文獻標識碼： A 文章編號： 1004?373X（2016）13?0112?04

Abstract： The quality of test paper directly determines the test result， so the excellent test?paper combination algorithm can better satify the standard set by the user. In combination with the practical demand of the project and existing algorithms， 5 improvement measures are proposed based on the particle swarm optimization algorithm. The computing method of test?paper fitness and coding scheme were improved. The new particle learning process was improved to make the particles better for each generation and have the performance of fast convergence to the global optimal solution. The chaos initialization and chaos disturbance are added into the improved particle swarm optimization algorithm. A new test?paper combination method was designed and implemented by means of algorithm experiment and improvement to obtain the better results. The QTI Standard is used to store the test questions and share them. The method feasibility was verified in practical application.

Keywords： test?paper combination； particle swarm optimization algorithm； improvement and optimization； QTI Standard

在網絡化考試中，組卷算法是考試系統構建中必不可少的環節。試卷的質量很大程度上影響并決定了一次考試是否有效。一個合適的組卷算法能夠滿足用戶對考試指標的限制和要求，并且具有一定的隨機性和合理性，是一個典型的多目標優化問題，涉及多重評估需求[1]。考試系統的教師用戶希望在出題的時候能夠滿足一些特定的指標，比如每種題型的數目和試卷總體的難度、區分度指標。如何從海量試題庫中篩選出一組滿足特定評估需求的試題形成一套標準的科學的試卷在網絡化考試和計算機輔助教學的研究中具有重要意義[2]。

1 QTI標準

QTI（Question and Test Interoperability）是美國高等教育協會機構EDUCAUSE制定的國際通用網絡學習標準的項目組的規范之一，包括若干個規范文本，主要用來解決網絡教育中測試數據的共享，作為一種標準的定義格式，可以在不同系統和用戶之間被使用。QTI規范能夠表述測試過程的各個環節，包括試題的描述、評估、重用和自適應測試[3]。使用QTI標準可以使試題實現跨平臺和跨系統的重用，并且可以共享測評結果。QTI具有更為廣泛的適應性，便于資源共享和評價結果的交互，同時便于用戶的使用和擴展，主要包括ASI模型、結果規范模型、試題構成要素的QTI XML表示[4]。

2 粒子群優化算法的改進

2.1 粒子群優化算法的組卷模型

采用粒子群優化算法進行組卷依據的模型：假設題庫的試題數為從中抽取試題進行組卷實驗。要求每份試卷的試題數為則每份試卷可以看作一個維度為的粒子，其中的每一維代表試卷中的一道試題。選取這樣的個粒子構成一個種群，則可以根據粒子群優化算法進行迭代和尋優。將每次的組卷結果與組卷問題中由用戶設定的指標值函數進行比較，并判斷粒子的下一步更新方向，直到得到符合要求的試卷，停止迭代[5]。

2.2 改進方案

系統目前采用的組卷算法是遺傳算法，在組卷中，遺傳算法需要不斷根據適應度函數判斷效果，并且當題型和參數要求較多的時候比較慢，因為需要經過反復的迭代和篩選，其中得到的大多數結果因為達不到條件限制，適應度低而被淘汰。所以需要多次迭代才能得到最終結果[6]。同時，現階段的考試系統還存在一些問題，比如試題共享存儲，這些都需要進一步改進[7]。

（1） 改進編碼方案

系統采用實數編碼的方式，由于試題本身在數據庫存儲的時候具有ID屬性，根據題號作為編碼也是比較自然的處理辦法，并且易于理解，從整體流程上來說，減少了編碼解碼的操作，組卷效率更高[8]。

（2） 加入混沌初始化和混沌擾動

在改進中采用由Logistic映射產生的混沌系統，組卷問題上，利用混沌的遍歷性，在粒子初始化的時候生成一系列多于要求種群數目的個體，并根據適應度值從中選出符合種群規定數目的一組質量較優的個體子集，不僅保證了種群個體的隨機分布，也保證了個體質量。利用Logistic映射，在粒子學習的過程中加入混沌擾動。粒子當前時刻的位置通過前一時刻的位置和當前速度進行更新后，對粒子進行范圍調整，使之不超過問題的最大范圍，之后加入一個擾動的變量，并檢查加入擾動之后的個體是否優于之前的個體。混沌擾動可以幫助粒子跳出局部最優解，避免粒子早熟。

（3） 慣性權值的自適應改進

在算法實現的過程中，進行粒子學習之前，先調用函數得到最新的慣性權值，在進化的過程中智能調整。當適應度值較小的時候，即低于平均適應度值的時候，取較大的慣性權值，目的是在全局尋優。當適應度值較大的時候，即高于平均適應度值的時候，根據迭代的情況，取較小的適應度值，目的是不斷微調，尋找到最優解。

（4） 改進粒子學習過程

計算出自適應改進的慣性權值等參數，參照標準遺傳算法中最常使用的賭輪選擇方法進行選擇，賭輪選擇主要是依據各個指標值占總值的比例進行選擇，所以又稱適應度成比例選擇。值越大的個體，被選擇的機會也越高。因為是對學習結果進行過檢驗的，所以可以保證粒子在學習之后可以變好，同時也具有一定的隨機性和不確定性，有利于保持種群的多樣化。學習之后，還要加上以上所述的混沌擾動過程，避免粒子陷入局部最優解。

（5） 改進適應度的計算方法

在組卷問題中，適應度值的計算主要考慮試題類型的符合程度，試題狀態的符合程度，試卷難度和區分度的符合程度等。這里對試卷難度和區分度的計算采用一種加分數權值的方法。在計算難度和區分度的時候加上分值的權值，有利于組卷過程中的總體控制。

3 改進算法實現

在算法改進與實現部分，共設計并實現了4種算法，分別為標準遺傳算法、改進遺傳算法、標準粒子群優化算法和改進粒子群優化算法。部分實驗參數設置如下：

（1） 對比算法1（遺傳算法）的主要參數：交叉率CROSSRATE=0.7；變異率MUTERATE=0.05；種群數量POPULATIONSIZE=40；最大適應度值FITSCORE=80 000。

（2） 對比算法2（改進遺傳算法）的主要參數：初始的交叉概率CROSSRATE=0.7；自適應改進的最大交叉概率crossMax=0.9；自適應改進的最小交叉概率crossMin=0.5；初始的變異概率MUTERATE=0.05；自適應改進的最大變異概率：mutationMax=0.1；自適應改進的最小變異概率：mutationMin=0.01；種群數量：POPULATIONSIZE = 40 ；目的適應度：FITSCORE =80 000。

（3） 改進粒子群優化算法的主要參數：慣性權值：慣性權值最大值：個體學習因子的最大值：個體學習因子的最小值：群體學習因子的最大值：群體學習因子的最小值：速度最大值：

3.1 參數取值分析

慣性權值用來保持個體原來的速度， cpbest和cgbest用來決定向其他個體學習的力度。慣性權值較大，利于跳出局部最優點，慣性權值較小，利于幫助算法快速收斂。

以如下試卷指標進行實驗：難度3.0，區分度3.0，試題數量10，單選題數4，多選題數3，簡答題數3，公有試題數為7，私有試題數為3。先對慣性權值和進行實驗。實驗初期，設速度最大值個體學習因子最小值個體學習因子最大值群體學習因子最小值群體學習因子最大值表1為慣性權值的實驗結果，其中，橫向表示慣性權值的最小值縱向表示慣性權值的最大值設速度最大值慣性權值最小值0.1，慣性權值最大值個體學習因子的試探范圍為2～3，群體學習因子的試探范圍為1～2。結果數據由程序運行20次的時間和平均適應度值組成。學習因子實驗結果如表2所示。由表2可以看出，個體學習因子為2.3，群體學習因子為1.3時，效果會好一些，設置繼續后續實驗。

設速度最大值如表3所示，第一列表示速度最大值第二列表示按上述參數運行程序20次得到的時間，第三列表示這20次的平均適應度值。題庫的總試題數為6 000，以此進行實驗。當時，時間和平均適應度值比較好。

3.2 改進結果的分析與評價

（1） 單次運行結果

單次運行結果比較如圖1所示。為便于查看，將程序各運行20次，從中選出迭代次數最大的兩組進行畫圖比較。橫坐標為迭代次數，縱坐標為每次迭代后的適應度值，因為程序設置的可接受閾值為80 000，所以設置坐標的最大值為80 000。

（2） 多次運行結果

多次運行結果如表4所示，將標準遺傳算法，改進遺傳算法，標準粒子群優化算法和改進粒子群優化算法進行比較。表中的數據時間都是以ms為單位，時間是20次程序運行結果的總和。指標值是運行結果的平均值，為便于比較，時間和指標值都通過四舍五入的方法保留2位小數。

由表4中的數據可見，不管是改進遺傳算法還是改進PSO 算法，都比原算法有更好的效果。在時間、迭代次數和指標值方面都有一定程度的優化。改進算法平均用時更少，迭代次數更少，得到最優解的次數更多。而粒子群優化算法與遺傳算法相比，在時間上有顯著的優越性。

4 組卷系統的設計與實現

4.1 系統功能描述

組卷系統的開發主要滿足教師用戶功能，包含四個主要的功能模塊：試題管理、試卷管理、試卷評閱和結果反饋。

（1） 試題管理

錄入試題：試題的題型有單選、多選、簡答、問答四種。用戶可以設置試題的主要指標，如難度、分值、狀態等。題目里可以包含圖片或者公式，并可以進行簡單的格式調整。

（2） 試卷管理

查詢試卷：可以根據試卷的不同參數指標對試卷進行查詢。組卷：可以設置試卷的指標，由系統自動從題庫中選擇試題進行組卷，也可以由用戶自己錄入試題組卷。瀏覽試卷：對發布的試卷進行瀏覽，查看試卷中的試題。

（3） 試卷評閱

可以通過輸入的試卷名稱或者用戶名稱進行查詢，對查詢到的試卷可以進行查看。如果試卷未經過評閱，可以進行評閱，需要評閱的一般為試卷中的主觀題部分。對于已閱試卷，可以進行查看。

（4） 結果反饋

可以通過輸入的試卷名稱或者用戶名稱進行查詢，對查詢到的試卷可以查看評閱結果。

4.2 系統設計

（1） 功能模塊設計

功能模塊分解如圖2所示。重點完成的部分為試題管理和試卷管理。在試題管理的導入試題中，應用QTI 技術，規范化XML，實現試題共享。

（2） QTI的設計與應用

在系統的實現中，采用QTI形式進行試題存儲。單選題、多選題和主觀題的共同點是：每個Item中都包含兩個主要節點，即試題描述presentation和試題答案reprocessing。但是在細節處理上各有不同，包括標識符，存儲形式和表現形式等。

多選題與單選題的結構類似，只是所有表示類型的字段對應改為Multiple。此外，在答案部分，多選題有兩個節點，每個節點的內容為一個選項字母。主觀題與選擇題的區別是，首先標志性字段改為SimpleAnswer。其次，沒有選項信息，即render_choice內容。第三，respcondition節點的response_type屬性為str，說明它的答案應該是一個字符串，而不像單選和多選中是lid屬性。

5 系統實現

整個系統在eclipse下使用java和jsp進行開發，數據庫使用MySQL。開發環境是jdk?1_5_0 ?windows?i586，服務器使用apache?tomcat?6.0。

系統設計開發中采用三層架構，劃分了較為典型的界面層、邏輯層和數據訪問層：界面層與系統用戶進行交互。獲取用戶輸入，進行合法性驗證，后臺進行處理后將結果以多種形式向用戶呈現。界面層的設計要求具有一定的安全性，過濾明顯易于驗證的非法輸入，確保不泄露程序內部信息。

用戶打開網站，通過首頁導航條的鏈接可以選擇查看試題管理、試卷管理、試卷評閱或是評測結果的頁面并進行相關操作。點擊最后一欄的“查看”，可以跳轉到試題瀏覽界面，進行試題查詢。

在試題管理頁面，可以進行試題錄入。設置參數并輸入題目和選項信息。編輯框的設置會隨著不同的題型而改變，比如，單選題和多選題有6個編輯框，簡答題和問答題有兩個編輯框。編輯框采用的是FCKEditor插件，支持富文本編輯，通過配置，可以實現插入圖片和公式等較為高級的功能。試題錄入完成后點擊“提交”按鈕，可以跳轉到試題瀏覽頁面。在試題瀏覽頁面，可以點擊“編輯”按鈕對試題重新進行編輯。通過點擊鏈接，可以查看另一個功能：試題導入。試題導入要求符合XML規范的文件，點擊導入，實現將試題保存到數據庫。

試卷評閱和評測結果兩部分主要是展示考試的效果，功能比較簡單，還需要進一步進行完善。

6 結 論

本文主要以粒子群優化算法為基礎，結合工程項目在應用中的實際需求進行改進。本文提出一種比較新的編碼和適應度值計算方法，將試題的屬性結合到編碼中，減少了數據庫的讀取，在組卷時間上會更好。同時對粒子學習過程進行了改進，與機械式的套用粒子群優化算法的公式不同，真正實現了粒子學習的本質，即每次學習的結果得到的是與最優個體之間的補償值。

在改進粒子群優化算法中，加入了混沌初始化和混沌擾動，使組卷具有更好的效果。對改進粒子群優化算法進行參數取值實驗，選擇一組比較適合的參數，通過與標準粒子群優化算法、遺傳算法和改進遺傳算法進行對比，證明改進粒子群優化算法不僅節省組卷時間，并且組卷結果也更為理想。

參考文獻

[1] 付細楚.考試系統中若干關鍵技術研究與系統實現[D].長沙：湖南大學，2005：22?24.

[2] 劉玲，鐘偉民，錢鋒.改進的混沌粒子群優化算法[J].華東理工大學學報（自然科學版），2010（2）：267?272.

[3] 劉亞瓊.基于加強學習的自動組卷算法的研究[D].天津：天津大學，2006：66?67.

[4] 孫艷霞，王增會，陳增強，等.混沌粒子群優化及其分析[J].系統仿真學報，2008（21）：5920?5923.

[5] 王成華，曾超峰.淺基礎的混沌粒子群優化設計方法[J].沈陽建筑大學學報（自然科學版），2011，27（6）：34?35.

[6] 王維博，馮全源.基于分層多子群的混沌粒子群優化算法[J].控制與決策，2010（11）：55?57.

[7] 張亮，趙娜.基于.NET的網絡考試系統設計與實現[J].現代電子技術，2010，33（8）：64?66.

[8] 司存瑞，周巖，孫米.網絡考試系統平臺的設計與實現[J].現代電子技術，2006，29（20）：44?46.