摘? 要：在線考試系統(tǒng)的算法主要體現(xiàn)在組卷設(shè)計模塊當中，要實現(xiàn)自主組卷，并且組卷成功率高。生成的試卷在滿足試卷的基本約束條件基礎(chǔ)上，還要體現(xiàn)試卷的難度控制以及考試區(qū)分度。這就需要通過算法來進行設(shè)計實現(xiàn)。本文就多種算法進行對比，分析優(yōu)劣，選取了遺傳算法與蟻群算法混合優(yōu)化，實現(xiàn)組卷設(shè)計模塊。對兩種算法實現(xiàn)在線考試組卷模塊的思想和實現(xiàn)方法進行了詳細闡述。

關(guān)鍵詞：隨機算法;遺傳算法;蟻群算法;工作流程;區(qū)分度

中圖分類號：TP18;TP391.6? ? ? ?文獻標識碼：A 文章編號：2096-4706（2019）20-0023-03

Abstract：The algorithm of online examination system is mainly embodied in the design module of generating test papers. To achieve self-generating test papers，and the success rate of generating test papers is high. On the basis of satisfying the basic constraints of the test paper，the generated test paper should also reflect the difficulty control and the test discrimination. This requires the design and implementation of the algorithm. This paper compares several algorithms，analyses their advantages and disadvantages，and chooses the hybrid optimization of genetic algorithm and ant colony algorithm to realize the test paper design module. This paper elaborates on the idea and implementation method of two algorithms to realize online examination paper module.

Keywords：stochastic algorithm;genetic algorithm;ant colony algorithm;workflow;discrimination

1? 在線考試系統(tǒng)組卷模塊算法對比分析

1.1? 在線考試系統(tǒng)模塊簡單說明

在線考試系統(tǒng)，要完成一個通過瀏覽器登錄，進行身份驗證，獲得權(quán)限，通過服務(wù)器獲取考卷，實現(xiàn)在線考試并且自動閱卷統(tǒng)計等基本功能。相關(guān)的主要模塊一般包含考生情況管理模塊、口令登錄模塊、組卷模塊、閱卷模塊、報表與維護模塊等。實現(xiàn)在線考試，這一基本功能，已經(jīng)屢見不鮮。對在線考試系統(tǒng)的主要研究側(cè)重于通過算法的優(yōu)化，實現(xiàn)試卷的生成。算法優(yōu)化的主要目的是提升試卷的總體質(zhì)量（難度、區(qū)分度的設(shè)置與控制），提升試卷生成的成功率，降低試卷生成算法執(zhí)行時間等。

1.2? 試卷生成模塊相關(guān)算法優(yōu)劣分析

1.2.1? 隨機算法

隨機算法是最早出現(xiàn)的試卷生成應(yīng)用算法之一，是采用隨機數(shù)的方式，在滿足基本約束的條件下，從題庫當中進行試題的抽取。這種算法的實現(xiàn)非常簡單，而且試卷生成的速度也很快。但是相對而言，隨機算法的缺點也非常明顯。因為算法簡單，抽取是采用隨機的方式，所以對試題庫的題量要求很高，如果題庫數(shù)目不充足，就會出現(xiàn)試卷試題大量重復的現(xiàn)象。同時也由于在前面的算法中只采用隨機方式進行抽取，試卷后面的試題抽取可能無法滿足約束條件，頻繁出現(xiàn)試卷組卷失敗的現(xiàn)象。即便解決了題庫數(shù)量的問題，試卷組卷失敗后，需要進行重新隨機算法試卷生成，大量的重復會耗費大量的試卷生成時間。這兩點對在線考試系統(tǒng)而言，弊端較大，目前隨機算法只在一些小型的在線考試系統(tǒng)中采用，應(yīng)用范圍小。

1.2.2? 回溯算法

這種算法是建立在隨機算法的基礎(chǔ)上的，針對隨機算法試卷生成率低，進行的算法改進。就是在執(zhí)行隨機算法的同時，進行每一步狀態(tài)的記錄。當隨機算法在N步驟無法進行，組卷失敗后，退回到試卷生成的上一狀態(tài)，重新進行試卷的生成，提高了組卷的成功率。但是這種算法也出現(xiàn)了新的問題，狀態(tài)的記錄與回溯，耗費了大量的算法運行時間，提升了時間復雜度。同時也喪失了隨機算法單次組卷的快速優(yōu)勢，實現(xiàn)方法相對也比較復雜，目前的實際應(yīng)用也不多。

1.2.3? 遺傳算法

遺傳算法是在智能化的在線考試系統(tǒng)開發(fā)中，大量應(yīng)用的一種算法。它是借用遺傳學的思想，通過編碼的方式確定染色體，形成種群，再通過交叉算子的選擇、交叉、變異等計算過程，從種群中選取具有優(yōu)勢的下一代，也就是更貼近理想解的集合。遺傳算法是借用遺傳學思想，通過數(shù)學的迭代計算方式，利用計算機編碼來實現(xiàn)完成。這種算法前期的收斂性能好，能夠很快地獲取前期優(yōu)勢的解集，在試卷生成中，我們要與適應(yīng)度這個目標函數(shù)的貼近度來進行判斷。但是在后期，由于種群接近優(yōu)勢解，所以競爭能力降低，算法效率降低，迭代次數(shù)設(shè)置成為難題。如果設(shè)置過大，則會出現(xiàn)兩個問題，一方面，試卷不能生成，但迭代次數(shù)沒有完成仍然需要無用的大量計算;另一方面，迭代作用減弱，對優(yōu)勢解集的幫助不大。如果迭代次數(shù)過小，無法進行充分計算，試卷生成概率降低。也就是說，遺傳算法對比前兩種算法具有一定的優(yōu)勢，全局搜索能力佳，前期算法效率高，應(yīng)用較廣，但是也存在一定的弊端。本文提出遺傳算法與蟻群算法混合實現(xiàn)組卷模塊設(shè)計的設(shè)計思想。

2? 用遺傳算法與蟻群算法混合實現(xiàn)組卷模塊思想分析

2.1? 算法對比結(jié)果

從上文我們可以看出，在組卷模塊中，相對于隨機算法和回溯算法而言，使用遺傳算法具有一定的先進性。遺傳算法使用遺傳學思想，通過編碼確定染色體，利用初始化種群操作確定初始群體數(shù)量，然后利用適應(yīng)度函數(shù)實現(xiàn)優(yōu)化目標，再通過遺傳算子，進行選擇交叉變異等操作。但遺傳算法在試卷生成中也遇到了問題，雖然遺傳算法具有全局優(yōu)勢，前期優(yōu)勢解集獲得速度快，但是后期算子的競爭速度變慢，迭代次數(shù)設(shè)置難以標準化。簡單地說，就是遺傳算法在運算的前期，運算效率高，但是在后期需要耗費大量的時間，整體的運算次數(shù)設(shè)置難以實現(xiàn)精準化，所以也存在一定的弊端。

2.2? 算法混合的作用

為了彌補遺傳算法的不足，我們發(fā)現(xiàn)蟻群算法具有快速收斂，魯棒性強等特點，而且這種算法具有較高的融合性，可以實現(xiàn)與其它算法的配合，完成最優(yōu)解集的求解過程。

2.2.1? 蟻群算法簡單說明

利用蟻群覓食中尋找路徑的特性，應(yīng)用于最優(yōu)解集的求解。其算法思想簡單描述為：螞蟻在搬運食物的過程中，通過分泌信息熵這種具有揮發(fā)性氣味的特殊元素，來進行路徑選擇。相對而言路徑短的，在一定時間內(nèi)，完成搬運的次數(shù)多，經(jīng)過的螞蟻也就較多，分泌的信息熵濃度較高，同時揮發(fā)的也較少，利用螞蟻辨認信息熵的特性，進行路徑的選擇。從這種思想我們也可以得出，這種算法具有正反饋機制。從實現(xiàn)過程來分析，也就是信息熵濃度越高，路徑被選擇概率越高，完成最優(yōu)路徑選擇越快。也就意味著算法的后期，運行效率高，實現(xiàn)優(yōu)勢解集求解優(yōu)勢大。

2.2.2? 兩種算法混合的思想

兩種算法混合的出發(fā)點是，在遺傳算法實現(xiàn)組卷模塊的基礎(chǔ)上，優(yōu)化組卷算法，解決遺傳算法中存在的問題。在研究過程中，發(fā)現(xiàn)了蟻群算法的特點，蟻群算法具有正反饋機制，后期尋求優(yōu)勢解集效率高，融合性強。從這些特點正好能夠解決遺傳算法后期，后代競爭效率低，算法效率低，迭代次數(shù)不容易科學設(shè)置的問題。

蟻群算法是否更加適合完成組卷模塊，替代遺傳算法呢？研究到此，是必須要考慮的問題。如果蟻群算法更具有優(yōu)越性，那么就沒必要進行算法融合，直接使用蟻群算法實現(xiàn)組卷才更有意義。蟻群算法也有自身的不足，從算法的思想我們可以看出，螞蟻是根據(jù)信息熵的濃度實現(xiàn)路徑選擇，而在初始化階段，路徑多，每條路徑的信息熵濃度概率相對平等，要完成初始化工作，需要的時間較長（需要螞蟻實現(xiàn)遍歷路徑，而且進行多次遍歷后實現(xiàn)）。這意味著，蟻群算法初期的初始化路徑需要花費較長時間。

因此，將蟻群算法融合入遺傳算法當中，在前期使用遺傳算法，實現(xiàn)快速解集的實現(xiàn)，相當于用較高的算法效率實現(xiàn)蟻群算法的初始化過程;在后期融合蟻群算法，替代遺傳算法的后期運算過程。這樣就降低了對遺傳算法迭代次數(shù)設(shè)置的精準性，同時提升了算法的整體運算效率，試卷生成時間短，能夠生成高質(zhì)量試卷。

3? 試卷難度與區(qū)分度的計算以及選取標準

所謂高質(zhì)量的試卷，是通過試卷的試題難度以及在考試中所體現(xiàn)的區(qū)分度來實現(xiàn)的。通過算法生成的試卷可以實現(xiàn)難度數(shù)值的控制，以及區(qū)分度的辨別。下面分別進行介紹。

3.1? 試卷難度

試卷的難度系數(shù)來源于不同難度試題的選取，這里為了便于理解，從試題的難度開始說明。

3.1.1? 試題難度公式

試題難度通過試題的失分率來體現(xiàn)，對于某道客觀化試題，失分率越高說明難度越大。

其中D為難度數(shù)值，PR是試題答對的人數(shù)，PA是全體參考人數(shù)（R代表right，A代表all）。公式含義便于理解。用整體1減去試題答對人員占的概率數(shù)值，那么就是做錯人數(shù)的概率數(shù)值，也就是失分概率數(shù)值，數(shù)值越大難度也就越高。

其中? 代表某道試題所有考生的得分平均數(shù)值，s容易分析出是試題的總分，用1減去概率數(shù)值，得到的是試題的相應(yīng)難度數(shù)值，同樣的數(shù)值越大代表越難，數(shù)值越小代表越簡單。

3.1.2? 試卷難度判斷公式

其中整張試卷的難度為D，用某道試題的難度系數(shù)di乘以該道試題的對應(yīng)分值si，進行求和累加，再除以試卷的總分數(shù)A。

以上為試卷難度產(chǎn)生的相應(yīng)公式說明。在研究中發(fā)現(xiàn)，初期認為難度系數(shù)處于中間數(shù)值，試卷質(zhì)量較高。但隨著研究的增多，應(yīng)該更加側(cè)重于應(yīng)用性，視考試的目的而定，不同的考試，選拔目的不同，最優(yōu)的試卷難度系數(shù)應(yīng)該是不同的。

3.2? 區(qū)分度公式說明

試卷的區(qū)分度，即是試卷試題對考生的水平考核的差度。如果體現(xiàn)出高分段、低分段、和中等分段三個階梯式表現(xiàn)，就代表區(qū)分度較佳。總分的前百分之三十為高分段，總分的后百分之三十為低分段。

3.2.1? 試題區(qū)分度公式舉例

其中試題區(qū)分度為T，用高分組人數(shù)ph減去低分組人數(shù)pi除以總?cè)藬?shù)A，就得出了區(qū)分度。這種公式適用于客觀化試題。當然如果在在線考試系統(tǒng)，使用主觀化試題，那么就不能使用人數(shù)比值。同樣的將公式轉(zhuǎn)型為對應(yīng)的平均得分差值和總分的比值，就仍然有效。

3.2.2? 試卷區(qū)分度公式

其中T為試卷區(qū)分度，si為分值，ti為試題區(qū)分度，相對而言區(qū)分度接近0.5為最佳。

3.3? 相關(guān)指標說明

通過設(shè)計與實驗發(fā)現(xiàn)，通常情況下，試題難度居中，能夠體現(xiàn)試卷的價值，居中的指標這里認為在0.45到0.6之間的范圍。并且試卷難度在這個范圍區(qū)間，通常試卷的區(qū)分度數(shù)值一般較高。但在一些選拔性考試當中，要根據(jù)考試需要進行難度算法設(shè)置，要以實用性為標準進行算法指標調(diào)整。通常的顧慮是難度過大或者過小，區(qū)分度數(shù)值較低。難度數(shù)值相對居中，區(qū)分度數(shù)值較高。

4? 混合算法流程圖

如圖1所示，遺傳算法與蟻群算法的融合點，是通過最小進化率數(shù)值來實現(xiàn)的。當遺傳算法的進化率多次小于最小進化率后，我們認為前期算法完成，后期的收斂速度減慢，為蟻群算法提供前期初始化數(shù)據(jù)，轉(zhuǎn)入蟻群算法進行計算，并得到最終優(yōu)勢解集。

5? 結(jié)? 論

通過多種算法的對比，得出遺傳算法在在線考試系統(tǒng)的試卷生成模塊中具有一定的優(yōu)越性，但是遺傳算法也存在后期收斂速度慢，優(yōu)勢解集求解過程長，算法時間消耗較高迭代次數(shù)設(shè)置不容易精確等問題。采用蟻群算法與遺傳算法混合，前期利用遺傳算法進行快速信息優(yōu)勢解集求解，后期利用蟻群算法的正反饋機制，節(jié)省算法運行時間，提升了試卷生成的成功率。從時間復雜度，求解成功率方面使在線考試系統(tǒng)得到了大幅優(yōu)化。

參考文獻：

[1] 趙俊普，殷進勇，金同標，等.遺傳蟻群算法在云計算資源調(diào)度中的應(yīng)用 [J].計算機工程與設(shè)計，2017，38（3）：693-697.

[2] 田增瑞，趙陽，趙袁軍，等.基于遺傳算法與蟻群算法的最佳旅游路線設(shè)計 [J].數(shù)學的實踐與認識，2016，46（24）：41-48.

[3] 黃永青，楊善林，梁昌勇.交互式蟻群遺傳算法 [J].小型微型計算機系統(tǒng)，2016，37（11）：2567-2570.

[4] 蔡延光，湯雅連.關(guān)聯(lián)運輸調(diào)度問題帶遺傳算子的自適應(yīng)蟻群算法 [J].計算機應(yīng)用研究，2015，32（8）：2313-2318+2360.

[5] 張新萍，張月琴，馮珊珊，等.一種求解圖著色問題的蟻群遺傳算法 [J].計算機應(yīng)用與軟件，2014，31（11）：207-209.

[6] 陳亞云，韓文濤，崔鶴平.遺傳算法與蟻群算法的改進融合 [J].中國農(nóng)機化學報，2014，35（4）：246-249.

[7] 劉傳領(lǐng).改進的蟻群遺傳優(yōu)化算法及其應(yīng)用 [J].計算機應(yīng)用，2013，33（11）：3111-3113+3128.

作者簡介：蘇楠（1980.07-），女，漢族，吉林人，講師，本科，研究方向：軟件技術(shù)。