遺傳與蟻群混合算法實(shí)現(xiàn)在線考試系統(tǒng)組卷設(shè)計(jì)研究

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

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

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

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

1.2.1? 隨機(jī)算法

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

1.2.2? 回溯算法

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

1.2.3? 遺傳算法

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

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

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

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

2.2? 算法混合的作用

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

2.2.1? 蟻群算法簡單說明

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

2.2.2? 兩種算法混合的思想

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

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

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

3? 試卷難度與區(qū)分度的計(jì)算以及選取標(biāo)準(zhǔn)

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

3.1? 試卷難度

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

3.1.1? 試題難度公式

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

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

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

3.1.2? 試卷難度判斷公式

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

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

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

試卷的區(qū)分度，即是試卷試題對考生的水平考核的差度。如果體現(xiàn)出高分段、低分段、和中等分段三個(gè)階梯式表現(xiàn)，就代表區(qū)分度較佳?？偡值那鞍俜种疄楦叻侄?，總分的后百分之三十為低分段。

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

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

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

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

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

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

4? 混合算法流程圖

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

5? 結(jié)? 論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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