對傳統(tǒng)幾種組卷算法改進(jìn)與比較分析?

張亞妮

（寶雞職業(yè)技術(shù)學(xué)院 寶雞 721013）

對傳統(tǒng)幾種組卷算法改進(jìn)與比較分析?

張亞妮

（寶雞職業(yè)技術(shù)學(xué)院 寶雞 721013）

組卷算法也是網(wǎng)絡(luò)考試系統(tǒng)中的關(guān)鍵問題之一，論文在組卷算法方面也進(jìn)行了一定的研究，實(shí)現(xiàn)了一種改進(jìn)的隨機(jī)算法和遺傳算法，并對算法的實(shí)際效果進(jìn)行了比較分析。

遺傳算法；智能組卷

1 引言

自動組卷是考試系統(tǒng)自動化或半自動化操作的核心目標(biāo)之一，而如何保證生成的試卷最大程度地滿足用戶的不同需要，并且具有隨機(jī)性、科學(xué)性、合理性，這是現(xiàn)實(shí)中的一個難點(diǎn)［1］。尤其在交互式環(huán)境下用戶對于組卷速度要求較高，題目應(yīng)具有多樣性、不宜作弊等，因此一個良好的組卷系統(tǒng)對于考試來說起著非常重要的作用［2］。組卷算法是網(wǎng)絡(luò)考試系統(tǒng)的核心功能之一，一個優(yōu)秀的組卷算法決定了考試系統(tǒng)的實(shí)用性。本文分析多種組卷算法并對其進(jìn)行改進(jìn)，使得用戶能夠根據(jù)不同的考試要求和題庫模式選擇最適合的組卷算法。

2 改進(jìn)的隨機(jī)算法

結(jié)合一般的隨機(jī)算法與貪心算法的思想，在組卷過程中可以避免完全盲目的抽題、試驗(yàn)［3］。在抽題過程中，可以充分利用已經(jīng)選取題目的信息，輔助抽取后面的題目。具體的做法是引入貪心算法的思想，在選取下一道試題時，總是去抽取最能滿足當(dāng)前約束條件的試題。算法的關(guān)鍵就什么樣的題目是最能滿足當(dāng)前約束條件的題目以及如何與現(xiàn)有約束條件結(jié)合來確定這樣的題目［4］。

試卷的約束條件是一個二維矩陣，已選取的題目同樣能組成一個對應(yīng)的二維矩陣，可將該矩陣成為當(dāng)前約束條件矩陣［5］。初始時，已選題目數(shù)為0，當(dāng)前約束條件矩陣中的元素也全部都是0。隨著組卷過程的進(jìn)行，矩陣元素的值是不斷累加的。在理想的情況下，最終的當(dāng)前約束條件矩陣應(yīng)該與目標(biāo)約束矩陣是完全一致的。

初始當(dāng)前約束條件矩陣：

組卷過程中的當(dāng)前約束條件矩陣：

將試卷的目標(biāo)約束矩陣與當(dāng)前約束矩陣做矩陣減法運(yùn)算，將得到的矩陣稱之為目標(biāo)差矩陣。

某一時刻的目標(biāo)差矩陣：

從另一面來想，每選定一道題目，該矩陣中就會有些元素的值減小，組卷的過程就是不斷地讓這個目標(biāo)差矩陣?yán)蹨p為0的過程。這里就可以結(jié)合貪心算法的思想，每選一道題目時，都盡量使得矩陣中盡可能多的元素值和盡可能大的元素值減小，這便是組卷過程中的局部最優(yōu)。上面的示例矩陣只是為了表述方便，實(shí)際上，在組卷過程中矩陣中元素的值是均勻地減小的，目標(biāo)差矩陣不會出現(xiàn)同一約束條件中一些值特別大獲特別小的情況。

具體實(shí)施時，從得到的目標(biāo)差矩陣中，找出每一個約束條件上值最大的一個，其對應(yīng)的狀態(tài)空間可以組成一個一維的矩陣，如在上面的示例中，得到的一維矩陣將是［單選，較易，了解，知識點(diǎn)3，小節(jié)5］，而這個矩陣就是最能滿足當(dāng)前約束條件的題目所應(yīng)該滿足的條件，符合這個條件的題目就是當(dāng)前的局部最優(yōu)解。因?yàn)樵诩s束條件矩陣中，每一行代表了一個約束條件，而當(dāng)前題目矩陣的每一行是該約束的當(dāng)前滿足情況，那么目標(biāo)差矩陣中每一行的最大值，就是該約束條件中最亟需滿足的。在選取題目時，優(yōu)先選擇滿足這個差距最大的值，以使目標(biāo)差矩陣盡快地趨進(jìn)于0，從而選定題目盡快地趨近給定約束矩陣。這時選取每一道題目時就帶有很強(qiáng)的目的性，在滿足這個一維矩陣條件情況下的題目中隨機(jī)選擇一道。因?yàn)樵诿恳粋€約束條件上都是差距最大的，一次選題的成功率會明顯提高。在理想的情況下，整張?jiān)嚲淼念}目能夠一次選題成功，其選題效率的提高是顯而易見的。

3 改進(jìn)遺傳算法

有很多人已經(jīng)研究過采用遺傳算法來解決組卷問題，用基本的遺傳算法解決組卷問題，會產(chǎn)生早期的盲目搜索、過早收斂、收斂于局部最優(yōu)解、局部搜索能力不強(qiáng)等弊病，這是由傳統(tǒng)遺傳算法的缺陷造成的［6］。在組卷應(yīng)用中可以對遺傳算法進(jìn)行改進(jìn)，采用整數(shù)編碼和競爭選擇方法［7］。這種方法不僅避免了遺傳算法中經(jīng)常出現(xiàn)的“早熟現(xiàn)象”，而且有效地解決了智能組卷中的約束優(yōu)化問題，具有很好的性能和實(shí)用性。在求解時，關(guān)鍵完成以下幾個方面：

1）確定編碼方案

一份試卷就是組卷算法的一個最終可行解，因此將一份試卷映射成一個染色體，每個試題映射為染色體中的基因。通常情況下，基因的值用試題在題庫中的題號表示，因?yàn)樵趯?shí)際實(shí)現(xiàn)中將采用面向?qū)ο蟮哪Ｐ蜆?gòu)建算法，基因的值就可以是一個試題的元數(shù)據(jù)對象，而試題在試題庫中的編號作為一個試題的標(biāo)識。這樣一個染色體的編碼可表示為：{q1，q2，…，qm}，式中 qi為試題的題號或者一個試題的元數(shù)據(jù)對象，且同種題型的試題編號組在一起形成段，每一段反映一個題型：

{(q1，q2，…，qm)，(qm+1，qm+2，…，qm+p)，…，(…)}

在一個染色體中，每一段長度由約束條件中該題型的數(shù)量決定；在試題庫中每一段長度由題庫內(nèi)該題型的數(shù)量決定。這樣易于用面向?qū)ο蟮哪Ｐ蛯?shí)現(xiàn)，克服了二進(jìn)制編碼的編碼、解碼的過程，明顯縮短了求解時間，在進(jìn)化時表現(xiàn)出很好的搜索性能。

2）初始群體的生成

組卷算法的初始群體并不是完全隨機(jī)生成的，而是根據(jù)某一個較強(qiáng)的約束條件，來確定初始群體。在編碼方案中，根據(jù)題型將試題也就是基因分成了不同的段，因此在初始化群體時也是根據(jù)題型分別初始化染色體的每一段，使得初始化后群體中的每一個染色體根據(jù)題型約束自然分段。這個劃分也為簡化后面的進(jìn)化操作奠定了基礎(chǔ)。

根據(jù)組卷約束條件中題型分布的要求，計(jì)算出各類型的試題應(yīng)該抽取的數(shù)目，隨機(jī)在題型相同但其他條件任意的試題庫子集中抽取試題組成一個染色體，然后重復(fù)此過程，直到達(dá)到事先指定的種群規(guī)模，這些染色體構(gòu)成了初始群體。

在一些組卷算法中，通過在抽取試題的過程中在題庫中設(shè)置標(biāo)志位，來避免同一個染色體和不同染色體之間中出現(xiàn)重復(fù)試題的情況。但是這樣在同一時刻只能進(jìn)行一套試卷的抽題操作，即使不在原題中設(shè)置標(biāo)志位，也會增加訪問題庫的頻率，影響種群初始化的速度。因此在多人在線考試系統(tǒng)中，這并不是一種十分理想的做法［8］。利用隨機(jī)函數(shù)在一定程度上保證生成的初始個體將均勻地分布在整個解空間上，并保證隨機(jī)產(chǎn)生的各個體間有明顯的差距、初始群體含有較豐富的模式、增強(qiáng)了搜索收斂于全局最優(yōu)點(diǎn)的可能［9］。同時，在后面的進(jìn)化操作中，要避免新的染色體中出現(xiàn)相同試題。

通過這個初始化操作，每個染色體時間上都已經(jīng)滿足了一個約束條件——題型，因此在后面的進(jìn)化操作中就可以省去題型這個約束條件。

3）適應(yīng)度函數(shù)的確定

在遺傳算法中，以適應(yīng)度函數(shù)的大小來區(qū)分群體中個體的優(yōu)劣一般情況下，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的，其值越大個體越好，對前面的組卷模型來說是最小化問題［10］。在組卷的適應(yīng)度函數(shù)中，應(yīng)該計(jì)算染色體的整體適應(yīng)度，要同時考慮組卷的各個指標(biāo)，使得組卷的各項(xiàng)指標(biāo)均向要求的值收斂。

4）遺傳操作

遺傳操作主要包括交叉、變異和選擇3個操作，這3個操作也稱為遺傳算子，遺傳算子決定了群體的進(jìn)化行為。

（1）優(yōu)選父代自適應(yīng)交叉操作。算法在進(jìn)行交叉操作時，提高被交叉父代個體的質(zhì)量，以期望產(chǎn)生高質(zhì)量的子代。具體操作為：從上代群體中隨機(jī)選擇兩個個體，保留適應(yīng)值大的個體（如二者適應(yīng)值相同，則隨機(jī)保留一個），再進(jìn)行一次上述兩兩優(yōu)選操作。對保留下來的兩個個體進(jìn)行交叉。交叉采用二進(jìn)制編碼遺傳算法中的多點(diǎn)交叉方式，且規(guī)定交叉在兩個個體的各個相同題型段內(nèi)同時進(jìn)行。

交叉概率采用改進(jìn)式自適應(yīng)方式產(chǎn)生，采用改進(jìn)式不但在進(jìn)化后期表現(xiàn)良好，而且在進(jìn)化初期提高群體中表現(xiàn)優(yōu)良個體的交叉率，使得它們不會處于一種近似停滯不前的狀態(tài)，降低進(jìn)化走向局部最優(yōu)解的可能性。改進(jìn)式自適應(yīng)交叉概率由下式確定：

式中：Fc為要交叉的兩個串中較大的適應(yīng)值；Fmax、Favr為上代群體中個體的最大適應(yīng)值及群體的平均適應(yīng)值；pc1=0.9，pc2=0.6。

（2）自適應(yīng)變異操作。變異采用段內(nèi)單位置替換式變異，即在個體的各個不同題型段內(nèi)隨機(jī)選取一位進(jìn)行替換，且規(guī)定該位被替換后的試題不能與該個體的其他位試題重復(fù)。變異概率采用改進(jìn)式自適應(yīng)變異概率，使變異在進(jìn)化初期和后期都有很好的表現(xiàn)，其具體表達(dá)式為

式中Fmax、Favr為上代群體中個體的最大適應(yīng)值及群體的平均適應(yīng)值；Fm為要變異個體的適應(yīng)值；pm1=0.1，pm2=0.001。

（3）選擇操作。為了保證搜索達(dá)到的最佳個體不會被各種遺傳操作破壞，并保留上代群體的優(yōu)良特性，算法把上代群體全部復(fù)制并保留到匹配池中。

5）終止條件

組卷系統(tǒng)可以采用下面3種類型的停止標(biāo)準(zhǔn)：最簡單的標(biāo)準(zhǔn)是在固定進(jìn)化次數(shù)后停止。另一種停止標(biāo)準(zhǔn)是基于群體中收斂的程度。即已生成的所有個體的平均適應(yīng)度與最好個體的平均適應(yīng)度的比 ≥0.99則算法終止。第三種停止標(biāo)準(zhǔn)是算法執(zhí)行一段時間后，如果沒有新的更好解產(chǎn)生，則停止。

4 實(shí)驗(yàn)結(jié)果及分析結(jié)論

本網(wǎng)絡(luò)考試系統(tǒng)采用Java語言編寫，實(shí)現(xiàn)了隨機(jī)和遺傳2種組卷算法，并利用中華人民共和國衛(wèi)生部測試題庫進(jìn)行了算法測試。為了便于對算法進(jìn)行對比測試，測試版的軟件同時給出了隨機(jī)算法和遺傳算法組卷的入口。

題庫中共有試題3875道試題，在題型、難度、認(rèn)知層次等試題屬性上的分布情況如表1所示。

表1 試題庫狀態(tài)分布

試驗(yàn)的軟硬件環(huán)境分別為：操作系統(tǒng)：Window 2003 Server；Web 服務(wù)器：Tomcat5.0.29；數(shù)據(jù)庫：MySQL 4.1；PC 機(jī)：一臺；CPU：迅馳 1.4G；內(nèi)存：768M；Web服務(wù)器和數(shù)據(jù)庫服務(wù)器位于同一臺PC機(jī)上。

當(dāng)試卷要求題目總數(shù)為20道，只有題型、難度和認(rèn)知層次3個約束條件下，具體約束條件如表2。

表2 組卷約束條件

隨機(jī)算法得到的組卷結(jié)果如表3，用時0.431s。

表3 隨機(jī)算法組卷結(jié)果

遺傳算法得到的組卷結(jié)果如表4，用時35.15s。

表4 遺傳算法組卷結(jié)果

當(dāng)試卷要求題目總數(shù)為40道題時，得到的組卷結(jié)果與以上基本一致，隨機(jī)算法用時增加到0.93s，遺傳算法在種群規(guī)模60迭代代數(shù)為40的情況下用時增加到57.77s。

在同樣的條件下40道題，分別對隨機(jī)算法和遺傳算法連續(xù)測試20次，得到的組卷結(jié)果與以上一致。隨機(jī)算法平均用時0.9s，遺傳算法平均用時55s。

當(dāng)試卷要求題目總數(shù)為60道，約束條件包括題型、難度、認(rèn)知層次、知識點(diǎn)分布、章節(jié)分布5個條件，具體約束條件如表5。

表5 組卷約束條件

遺傳算法得到的測試結(jié)果如表6，用時72.0s。

表6 遺傳算法組卷結(jié)果

將種群規(guī)模和迭代代數(shù)都增加到60時，遺傳算法得到的結(jié)果如表7。

表7 遺傳算法組卷結(jié)果

在5個約束條件下抽取60道題目，分別對隨機(jī)算法和遺傳算法連續(xù)測試20次，組卷結(jié)果的平均情況與以上結(jié)果基本一致，隨機(jī)算法平均用時1.4s，遺傳算法平均用時75s。

測試結(jié)果表明，隨機(jī)算法與遺傳算法哪個效率高并不是絕對的，隨著約束條件的改變，各自的表現(xiàn)也有所不同。

加入了貪心算法思想的隨機(jī)算法在組卷速度上有著明顯的優(yōu)勢。當(dāng)約束條件較少，試卷要求的題目數(shù)量與題庫題目數(shù)量相比是很少時，其組卷的各項(xiàng)指標(biāo)都能夠100%地達(dá)到要求的約束，用時也極少，最少的不足1s，最多也不過5、6s。當(dāng)約束條件擴(kuò)充時，用時上并沒有增加許多，但是組卷質(zhì)量卻有所下降。這是因?yàn)樗惴ㄔ谧詈鬅o法找到最合適的題目時會削弱約束條件，以保證組卷成功，這時組出的試卷各項(xiàng)指標(biāo)并不是與約束條件完全吻合的。多次試驗(yàn)也表明，約束增加后試卷之間重復(fù)題目的數(shù)量也開始增多，試題的隨機(jī)性顯著下降。

遺傳算法在約束條件較少、試卷要求的題目數(shù)也較少時，并沒有顯示出明顯的優(yōu)勢，甚至在組卷速度上用時是隨機(jī)算法的好幾十倍。但是隨著約束條件的增加以及試卷題目數(shù)量的增加，遺傳算法在組卷質(zhì)量上要好于隨機(jī)算法。試卷的質(zhì)量表現(xiàn)在，雖然有很多試卷指標(biāo)與要求的約束沒有達(dá)到100%的吻合，但是差距與要求的約束相差很小，都在可以接受的范圍之內(nèi)。這是因?yàn)檫z傳算法每次進(jìn)化都并行的考慮所有約束條件，并在全局范圍內(nèi)尋優(yōu)，使得各項(xiàng)指標(biāo)都能均勻地向要求的約束收斂。同時，遺傳算法還有一個優(yōu)勢就是一次同時組出多份滿意的試卷。除種群最好的個體外，排在前幾位的次好好個體也基本上能夠滿足要求。

5 結(jié)語

綜上所述，隨機(jī)算法和遺傳算法在組卷中的應(yīng)用都有相應(yīng)的優(yōu)勢和不足，選用哪一種算法并不是絕對的。在實(shí)際應(yīng)用當(dāng)中，算法的選擇應(yīng)該根據(jù)試卷的約束情況、題庫中題目數(shù)量和題目的分布情況以及對試卷指標(biāo)的誤差定義來決定。

［1］Zhouguobing，Liutingting，Liu，et al.Algorithm and strat?egy research of generating test paper for large scale online examination［C］//International Conference on Electronic and Mechanical Engineering and Information Technology，Emeit 2011，Harbin，Heilongjiang，China，12-14 August.2011：3285-3288.

［2］ Mei Y，Cheng L.Scoring Fairness in Large-Scale High-Stakes English Language Testing：An Examination of the National Matriculation English Test［M］//English Language Education and Assessment：Recent Develop?ments in Hong Kong and Chinese Mainland，2014：171-187.

［3］Yang C Y，Li Z Y，Gu Y D，et al.A Study on Improving Methods of Multi-Source and Multipath in Large-Scale Examination System Cloud Environment［J］.Applied Me?chanics&Materials，2014，687-691：2722-2727.

［4］Yu F，Liu W，Cui M.Heuristic Genetic Test Paper Algo?rithm for Online Examination System［J］.Advanced Mate?rials Research，2013，798-799：676-679.

［5］Tang H T.Strategy for Test Paper Composition Based on Genetic Algorithm［J］.Applied Mechanics&Materials，2014，513-517（513-517）：1688-1691.

［6］Tang C S，Dong Y D，Xiong R.Algorithm for random creat?ing test papers online and its realization［J］.Journal of He?fei University of Technology，2006，29（3）：296-299.

［7］Huang B L.Application of Adaptive Genetic Algorithm in Intelligent Test Paper Composition［J］.Computer Engi?neering，2011，37（14）：161-163.

［8］Li X，Wang Z，Wu X，et al.The design of adaptive test pa?per composition algorithm based on the item response theo?ry［C］//Information Technology and Artificial Intelligence Conference.IEEE，2011：157-159.

［9］Chang T Y，Ke Y R.A personalized e-course composition based on a genetic algorithm with forcing legality in an adaptive learning system［J］.Journal of Network&Com?puter Applications，2013，36（1）：533-542.

［10］Chang T Y，Ke Y R.A personalized e-course composi?tion based on a genetic algorithm with forcing legality in an adaptive learning system［J］.Journal of Network&Computer Applications，2013，36（1）：533-542.

Analysis of Several Groups of Traditional Algorithm Improvement and Comparative

ZHANG Yani
（Baoji Professional Technology Institute，Baoji 721013）

Group algorithm also is one of the key issues in the network examination system，This paper has conducted the group algorithm research，achieved an improved random algorithm and genetic algorithm，and analyzed the actual effect of the algo?rithm.

genetic algorithms，smart group volume

Class Number TP301

TP301

10.3969/j.issn.1672-9722.2017.12.009

2017年6月5日，

2017年7月27日

張亞妮，女，碩士，講師，研究方向：計(jì)算機(jī)應(yīng)用技術(shù)。