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

關(guān)鍵詞： 組卷； 粒子群優(yōu)化算法； 改進(jìn)與優(yōu)化； QTI標(biāo)準(zhǔn)

中圖分類號(hào)： TN915?34； TM417 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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

在網(wǎng)絡(luò)化考試中，組卷算法是考試系統(tǒng)構(gòu)建中必不可少的環(huán)節(jié)。試卷的質(zhì)量很大程度上影響并決定了一次考試是否有效。一個(gè)合適的組卷算法能夠滿足用戶對(duì)考試指標(biāo)的限制和要求，并且具有一定的隨機(jī)性和合理性，是一個(gè)典型的多目標(biāo)優(yōu)化問題，涉及多重評(píng)估需求[1]?？荚囅到y(tǒng)的教師用戶希望在出題的時(shí)候能夠滿足一些特定的指標(biāo)，比如每種題型的數(shù)目和試卷總體的難度、區(qū)分度指標(biāo)。如何從海量試題庫(kù)中篩選出一組滿足特定評(píng)估需求的試題形成一套標(biāo)準(zhǔn)的科學(xué)的試卷在網(wǎng)絡(luò)化考試和計(jì)算機(jī)輔助教學(xué)的研究中具有重要意義[2]。

1 QTI標(biāo)準(zhǔn)

QTI（Question and Test Interoperability）是美國(guó)高等教育協(xié)會(huì)機(jī)構(gòu)EDUCAUSE制定的國(guó)際通用網(wǎng)絡(luò)學(xué)習(xí)標(biāo)準(zhǔn)的項(xiàng)目組的規(guī)范之一，包括若干個(gè)規(guī)范文本，主要用來(lái)解決網(wǎng)絡(luò)教育中測(cè)試數(shù)據(jù)的共享，作為一種標(biāo)準(zhǔn)的定義格式，可以在不同系統(tǒng)和用戶之間被使用。QTI規(guī)范能夠表述測(cè)試過(guò)程的各個(gè)環(huán)節(jié)，包括試題的描述、評(píng)估、重用和自適應(yīng)測(cè)試[3]。使用QTI標(biāo)準(zhǔn)可以使試題實(shí)現(xiàn)跨平臺(tái)和跨系統(tǒng)的重用，并且可以共享測(cè)評(píng)結(jié)果。QTI具有更為廣泛的適應(yīng)性，便于資源共享和評(píng)價(jià)結(jié)果的交互，同時(shí)便于用戶的使用和擴(kuò)展，主要包括ASI模型、結(jié)果規(guī)范模型、試題構(gòu)成要素的QTI XML表示[4]。

2 粒子群優(yōu)化算法的改進(jìn)

2.1 粒子群優(yōu)化算法的組卷模型

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

2.2 改進(jìn)方案

系統(tǒng)目前采用的組卷算法是遺傳算法，在組卷中，遺傳算法需要不斷根據(jù)適應(yīng)度函數(shù)判斷效果，并且當(dāng)題型和參數(shù)要求較多的時(shí)候比較慢，因?yàn)樾枰?jīng)過(guò)反復(fù)的迭代和篩選，其中得到的大多數(shù)結(jié)果因?yàn)檫_(dá)不到條件限制，適應(yīng)度低而被淘汰。所以需要多次迭代才能得到最終結(jié)果[6]。同時(shí)，現(xiàn)階段的考試系統(tǒng)還存在一些問題，比如試題共享存儲(chǔ)，這些都需要進(jìn)一步改進(jìn)[7]。

（1） 改進(jìn)編碼方案

系統(tǒng)采用實(shí)數(shù)編碼的方式，由于試題本身在數(shù)據(jù)庫(kù)存儲(chǔ)的時(shí)候具有ID屬性，根據(jù)題號(hào)作為編碼也是比較自然的處理辦法，并且易于理解，從整體流程上來(lái)說(shuō)，減少了編碼解碼的操作，組卷效率更高[8]。

（2） 加入混沌初始化和混沌擾動(dòng)

在改進(jìn)中采用由Logistic映射產(chǎn)生的混沌系統(tǒng)，組卷問題上，利用混沌的遍歷性，在粒子初始化的時(shí)候生成一系列多于要求種群數(shù)目的個(gè)體，并根據(jù)適應(yīng)度值從中選出符合種群規(guī)定數(shù)目的一組質(zhì)量較優(yōu)的個(gè)體子集，不僅保證了種群個(gè)體的隨機(jī)分布，也保證了個(gè)體質(zhì)量。利用Logistic映射，在粒子學(xué)習(xí)的過(guò)程中加入混沌擾動(dòng)。粒子當(dāng)前時(shí)刻的位置通過(guò)前一時(shí)刻的位置和當(dāng)前速度進(jìn)行更新后，對(duì)粒子進(jìn)行范圍調(diào)整，使之不超過(guò)問題的最大范圍，之后加入一個(gè)擾動(dòng)的變量，并檢查加入擾動(dòng)之后的個(gè)體是否優(yōu)于之前的個(gè)體?；煦鐢_動(dòng)可以幫助粒子跳出局部最優(yōu)解，避免粒子早熟。

（3） 慣性權(quán)值的自適應(yīng)改進(jìn)

在算法實(shí)現(xiàn)的過(guò)程中，進(jìn)行粒子學(xué)習(xí)之前，先調(diào)用函數(shù)得到最新的慣性權(quán)值，在進(jìn)化的過(guò)程中智能調(diào)整。當(dāng)適應(yīng)度值較小的時(shí)候，即低于平均適應(yīng)度值的時(shí)候，取較大的慣性權(quán)值，目的是在全局尋優(yōu)。當(dāng)適應(yīng)度值較大的時(shí)候，即高于平均適應(yīng)度值的時(shí)候，根據(jù)迭代的情況，取較小的適應(yīng)度值，目的是不斷微調(diào)，尋找到最優(yōu)解。

（4） 改進(jìn)粒子學(xué)習(xí)過(guò)程

計(jì)算出自適應(yīng)改進(jìn)的慣性權(quán)值等參數(shù)，參照標(biāo)準(zhǔn)遺傳算法中最常使用的賭輪選擇方法進(jìn)行選擇，賭輪選擇主要是依據(jù)各個(gè)指標(biāo)值占總值的比例進(jìn)行選擇，所以又稱適應(yīng)度成比例選擇。值越大的個(gè)體，被選擇的機(jī)會(huì)也越高。因?yàn)槭菍?duì)學(xué)習(xí)結(jié)果進(jìn)行過(guò)檢驗(yàn)的，所以可以保證粒子在學(xué)習(xí)之后可以變好，同時(shí)也具有一定的隨機(jī)性和不確定性，有利于保持種群的多樣化。學(xué)習(xí)之后，還要加上以上所述的混沌擾動(dòng)過(guò)程，避免粒子陷入局部最優(yōu)解。

（5） 改進(jìn)適應(yīng)度的計(jì)算方法

在組卷問題中，適應(yīng)度值的計(jì)算主要考慮試題類型的符合程度，試題狀態(tài)的符合程度，試卷難度和區(qū)分度的符合程度等。這里對(duì)試卷難度和區(qū)分度的計(jì)算采用一種加分?jǐn)?shù)權(quán)值的方法。在計(jì)算難度和區(qū)分度的時(shí)候加上分值的權(quán)值，有利于組卷過(guò)程中的總體控制。

3 改進(jìn)算法實(shí)現(xiàn)

在算法改進(jìn)與實(shí)現(xiàn)部分，共設(shè)計(jì)并實(shí)現(xiàn)了4種算法，分別為標(biāo)準(zhǔn)遺傳算法、改進(jìn)遺傳算法、標(biāo)準(zhǔn)粒子群優(yōu)化算法和改進(jìn)粒子群優(yōu)化算法。部分實(shí)驗(yàn)參數(shù)設(shè)置如下：

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

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

（3） 改進(jìn)粒子群優(yōu)化算法的主要參數(shù)：慣性權(quán)值：慣性權(quán)值最大值：個(gè)體學(xué)習(xí)因子的最大值：個(gè)體學(xué)習(xí)因子的最小值：群體學(xué)習(xí)因子的最大值：群體學(xué)習(xí)因子的最小值：速度最大值：

3.1 參數(shù)取值分析

慣性權(quán)值用來(lái)保持個(gè)體原來(lái)的速度， cpbest和cgbest用來(lái)決定向其他個(gè)體學(xué)習(xí)的力度。慣性權(quán)值較大，利于跳出局部最優(yōu)點(diǎn)，慣性權(quán)值較小，利于幫助算法快速收斂。

以如下試卷指標(biāo)進(jìn)行實(shí)驗(yàn)：難度3.0，區(qū)分度3.0，試題數(shù)量10，單選題數(shù)4，多選題數(shù)3，簡(jiǎn)答題數(shù)3，公有試題數(shù)為7，私有試題數(shù)為3。先對(duì)慣性權(quán)值和進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)初期，設(shè)速度最大值個(gè)體學(xué)習(xí)因子最小值個(gè)體學(xué)習(xí)因子最大值群體學(xué)習(xí)因子最小值群體學(xué)習(xí)因子最大值表1為慣性權(quán)值的實(shí)驗(yàn)結(jié)果，其中，橫向表示慣性權(quán)值的最小值縱向表示慣性權(quán)值的最大值設(shè)速度最大值慣性權(quán)值最小值0.1，慣性權(quán)值最大值個(gè)體學(xué)習(xí)因子的試探范圍為2～3，群體學(xué)習(xí)因子的試探范圍為1～2。結(jié)果數(shù)據(jù)由程序運(yùn)行20次的時(shí)間和平均適應(yīng)度值組成。學(xué)習(xí)因子實(shí)驗(yàn)結(jié)果如表2所示。由表2可以看出，個(gè)體學(xué)習(xí)因子為2.3，群體學(xué)習(xí)因子為1.3時(shí)，效果會(huì)好一些，設(shè)置繼續(xù)后續(xù)實(shí)驗(yàn)。

設(shè)速度最大值如表3所示，第一列表示速度最大值第二列表示按上述參數(shù)運(yùn)行程序20次得到的時(shí)間，第三列表示這20次的平均適應(yīng)度值。題庫(kù)的總試題數(shù)為6 000，以此進(jìn)行實(shí)驗(yàn)。當(dāng)時(shí)，時(shí)間和平均適應(yīng)度值比較好。

3.2 改進(jìn)結(jié)果的分析與評(píng)價(jià)

（1） 單次運(yùn)行結(jié)果

單次運(yùn)行結(jié)果比較如圖1所示。為便于查看，將程序各運(yùn)行20次，從中選出迭代次數(shù)最大的兩組進(jìn)行畫圖比較。橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為每次迭代后的適應(yīng)度值，因?yàn)槌绦蛟O(shè)置的可接受閾值為80 000，所以設(shè)置坐標(biāo)的最大值為80 000。

（2） 多次運(yùn)行結(jié)果

多次運(yùn)行結(jié)果如表4所示，將標(biāo)準(zhǔn)遺傳算法，改進(jìn)遺傳算法，標(biāo)準(zhǔn)粒子群優(yōu)化算法和改進(jìn)粒子群優(yōu)化算法進(jìn)行比較。表中的數(shù)據(jù)時(shí)間都是以ms為單位，時(shí)間是20次程序運(yùn)行結(jié)果的總和。指標(biāo)值是運(yùn)行結(jié)果的平均值，為便于比較，時(shí)間和指標(biāo)值都通過(guò)四舍五入的方法保留2位小數(shù)。

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

4 組卷系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

4.1 系統(tǒng)功能描述

組卷系統(tǒng)的開發(fā)主要滿足教師用戶功能，包含四個(gè)主要的功能模塊：試題管理、試卷管理、試卷評(píng)閱和結(jié)果反饋。

（1） 試題管理

錄入試題：試題的題型有單選、多選、簡(jiǎn)答、問答四種。用戶可以設(shè)置試題的主要指標(biāo)，如難度、分值、狀態(tài)等。題目里可以包含圖片或者公式，并可以進(jìn)行簡(jiǎn)單的格式調(diào)整。

（2） 試卷管理

查詢?cè)嚲恚嚎梢愿鶕?jù)試卷的不同參數(shù)指標(biāo)對(duì)試卷進(jìn)行查詢。組卷：可以設(shè)置試卷的指標(biāo)，由系統(tǒng)自動(dòng)從題庫(kù)中選擇試題進(jìn)行組卷，也可以由用戶自己錄入試題組卷。瀏覽試卷：對(duì)發(fā)布的試卷進(jìn)行瀏覽，查看試卷中的試題。

（3） 試卷評(píng)閱

可以通過(guò)輸入的試卷名稱或者用戶名稱進(jìn)行查詢，對(duì)查詢到的試卷可以進(jìn)行查看。如果試卷未經(jīng)過(guò)評(píng)閱，可以進(jìn)行評(píng)閱，需要評(píng)閱的一般為試卷中的主觀題部分。對(duì)于已閱試卷，可以進(jìn)行查看。

（4） 結(jié)果反饋

可以通過(guò)輸入的試卷名稱或者用戶名稱進(jìn)行查詢，對(duì)查詢到的試卷可以查看評(píng)閱結(jié)果。

4.2 系統(tǒng)設(shè)計(jì)

（1） 功能模塊設(shè)計(jì)

功能模塊分解如圖2所示。重點(diǎn)完成的部分為試題管理和試卷管理。在試題管理的導(dǎo)入試題中，應(yīng)用QTI 技術(shù)，規(guī)范化XML，實(shí)現(xiàn)試題共享。

（2） QTI的設(shè)計(jì)與應(yīng)用

在系統(tǒng)的實(shí)現(xiàn)中，采用QTI形式進(jìn)行試題存儲(chǔ)。單選題、多選題和主觀題的共同點(diǎn)是：每個(gè)Item中都包含兩個(gè)主要節(jié)點(diǎn)，即試題描述presentation和試題答案reprocessing。但是在細(xì)節(jié)處理上各有不同，包括標(biāo)識(shí)符，存儲(chǔ)形式和表現(xiàn)形式等。

多選題與單選題的結(jié)構(gòu)類似，只是所有表示類型的字段對(duì)應(yīng)改為Multiple。此外，在答案部分，多選題有兩個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的內(nèi)容為一個(gè)選項(xiàng)字母。主觀題與選擇題的區(qū)別是，首先標(biāo)志性字段改為SimpleAnswer。其次，沒有選項(xiàng)信息，即render_choice內(nèi)容。第三，respcondition節(jié)點(diǎn)的response_type屬性為str，說(shuō)明它的答案應(yīng)該是一個(gè)字符串，而不像單選和多選中是lid屬性。

5 系統(tǒng)實(shí)現(xiàn)

整個(gè)系統(tǒng)在eclipse下使用java和jsp進(jìn)行開發(fā)，數(shù)據(jù)庫(kù)使用MySQL。開發(fā)環(huán)境是jdk?1_5_0 ?windows?i586，服務(wù)器使用apache?tomcat?6.0。

系統(tǒng)設(shè)計(jì)開發(fā)中采用三層架構(gòu)，劃分了較為典型的界面層、邏輯層和數(shù)據(jù)訪問層：界面層與系統(tǒng)用戶進(jìn)行交互。獲取用戶輸入，進(jìn)行合法性驗(yàn)證，后臺(tái)進(jìn)行處理后將結(jié)果以多種形式向用戶呈現(xiàn)。界面層的設(shè)計(jì)要求具有一定的安全性，過(guò)濾明顯易于驗(yàn)證的非法輸入，確保不泄露程序內(nèi)部信息。

用戶打開網(wǎng)站，通過(guò)首頁(yè)導(dǎo)航條的鏈接可以選擇查看試題管理、試卷管理、試卷評(píng)閱或是評(píng)測(cè)結(jié)果的頁(yè)面并進(jìn)行相關(guān)操作。點(diǎn)擊最后一欄的“查看”，可以跳轉(zhuǎn)到試題瀏覽界面，進(jìn)行試題查詢。

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

試卷評(píng)閱和評(píng)測(cè)結(jié)果兩部分主要是展示考試的效果，功能比較簡(jiǎn)單，還需要進(jìn)一步進(jìn)行完善。

6 結(jié) 論

本文主要以粒子群優(yōu)化算法為基礎(chǔ)，結(jié)合工程項(xiàng)目在應(yīng)用中的實(shí)際需求進(jìn)行改進(jìn)。本文提出一種比較新的編碼和適應(yīng)度值計(jì)算方法，將試題的屬性結(jié)合到編碼中，減少了數(shù)據(jù)庫(kù)的讀取，在組卷時(shí)間上會(huì)更好。同時(shí)對(duì)粒子學(xué)習(xí)過(guò)程進(jìn)行了改進(jìn)，與機(jī)械式的套用粒子群優(yōu)化算法的公式不同，真正實(shí)現(xiàn)了粒子學(xué)習(xí)的本質(zhì)，即每次學(xué)習(xí)的結(jié)果得到的是與最優(yōu)個(gè)體之間的補(bǔ)償值。

在改進(jìn)粒子群優(yōu)化算法中，加入了混沌初始化和混沌擾動(dòng)，使組卷具有更好的效果。對(duì)改進(jìn)粒子群優(yōu)化算法進(jìn)行參數(shù)取值實(shí)驗(yàn)，選擇一組比較適合的參數(shù)，通過(guò)與標(biāo)準(zhǔn)粒子群優(yōu)化算法、遺傳算法和改進(jìn)遺傳算法進(jìn)行對(duì)比，證明改進(jìn)粒子群優(yōu)化算法不僅節(jié)省組卷時(shí)間，并且組卷結(jié)果也更為理想。

參考文獻(xiàn)

[1] 付細(xì)楚.考試系統(tǒng)中若干關(guān)鍵技術(shù)研究與系統(tǒng)實(shí)現(xiàn)[D].長(zhǎng)沙：湖南大學(xué)，2005：22?24.

[2] 劉玲，鐘偉民，錢鋒.改進(jìn)的混沌粒子群優(yōu)化算法[J].華東理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2010（2）：267?272.

[3] 劉亞瓊.基于加強(qiáng)學(xué)習(xí)的自動(dòng)組卷算法的研究[D].天津：天津大學(xué)，2006：66?67.

[4] 孫艷霞，王增會(huì)，陳增強(qiáng)，等.混沌粒子群優(yōu)化及其分析[J].系統(tǒng)仿真學(xué)報(bào)，2008（21）：5920?5923.

[5] 王成華，曾超峰.淺基礎(chǔ)的混沌粒子群優(yōu)化設(shè)計(jì)方法[J].沈陽(yáng)建筑大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，27（6）：34?35.

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

[7] 張亮，趙娜.基于.NET的網(wǎng)絡(luò)考試系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2010，33（8）：64?66.

[8] 司存瑞，周巖，孫米.網(wǎng)絡(luò)考試系統(tǒng)平臺(tái)的設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2006，29（20）：44?46.