楊春哲， 常涵吉

摘 要： 針對(duì)傳統(tǒng)組卷方法效率、成功率低等難題，設(shè)計(jì)基于遺傳算法的大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷方法。首先設(shè)計(jì)大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)成卷適應(yīng)度函數(shù)，采用編碼對(duì)組卷過(guò)程中題型及與其數(shù)量分布相關(guān)的約束條件進(jìn)行處理，然后設(shè)計(jì)選擇算子、交叉算子以及變異算子，將適應(yīng)度作為評(píng)價(jià)群體多樣性的指標(biāo)，求出交叉概率與變異概率，給出遺傳算法終止條件。實(shí)驗(yàn)結(jié)果表明，該方法提高了大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷方法的效率和成功率。

關(guān)鍵詞： 遺傳算法； 計(jì)算機(jī)基礎(chǔ)； 自動(dòng)組卷； 適應(yīng)度函數(shù)； 約束條件； 編碼

中圖分類(lèi)號(hào)： TN99?34； TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）11?0171?04

Genetic algorithm based automatic test paper generation

method of university computer foundation

YANG Chunzhe， CHANG Hanji

（Jilin Medical University， Jilin 132013， China）

Abstract： Since the traditional test paper generation method has the problems of low efficiency and low success rate， an genetic algorithm based automatic test paper generation method of university computer foundation is designed. The fitness function of automatic test paper generation of university computer foundation is designed. The coding is used to handle the related constraint conditions of question types and quantity distribution in the process of test paper generation. The selection operator， crossover operator and mutation operator are designed. The fitness is taken as the indicator to evaluate the population diversity. The crossover probability and mutation probability are solved， and the terminal condition of genetic algorithm is given. The experimental results show that the proposed method can improve the efficiency and success rate of automatic test paper generation method of university computer foundation.

Keywords： genetic algorithm； university computer foundation； automatic test paper generation； fitness function； constraint condition； coding

0 引 言

大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷是實(shí)現(xiàn)在線考試系統(tǒng)的核心技術(shù)，當(dāng)前很多學(xué)校機(jī)構(gòu)都對(duì)自動(dòng)組卷進(jìn)行了大量研究，盡可能使最終形成的試卷達(dá)到用戶要求，同時(shí)保證科學(xué)性[1]。在大學(xué)計(jì)算機(jī)基礎(chǔ)題庫(kù)試題質(zhì)量要求高的情況下，自動(dòng)組卷的效率和質(zhì)量只和組卷方法有關(guān)。因此，設(shè)計(jì)一種科學(xué)有效的自動(dòng)組卷方法非常關(guān)鍵，其涉及全局尋優(yōu)問(wèn)題，具有重要研究?jī)r(jià)值[2?3]。

當(dāng)前常用的自動(dòng)組卷方法有隨機(jī)生成方法和回溯試探方法。隨機(jī)生成方法通過(guò)隨機(jī)抽取的方式從試題庫(kù)中抽取試題，對(duì)其是否滿足試卷要求進(jìn)行判斷，該方法有很高的不確定性，在試題數(shù)量多的情況下，效率極低[4]?；厮菰囂椒椒ò凑漳骋粶?zhǔn)則對(duì)當(dāng)前組卷狀態(tài)進(jìn)行轉(zhuǎn)換，試探性的選擇試題破壞了選擇試題的隨機(jī)性，同時(shí)組卷所需時(shí)間長(zhǎng)。為此，提出一種新的基于遺傳算法的大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷方法。

1 遺傳算法的大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷方法

1.1 大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷模型

組卷問(wèn)題可描述為：采用相應(yīng)軟件程序把成卷要求與資料庫(kù)中試題特征參數(shù)匹配，得到符合成卷?xiàng)l件的試卷。組卷的目標(biāo)為尋找最優(yōu)解，確定最符合輸入要求的組卷策略[5]。

在大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷過(guò)程中，命題人會(huì)事先輸入多個(gè)限制條件，主要含有以下幾個(gè)方面：

1） 試卷總分：試卷的總分?jǐn)?shù)，通過(guò)命題人設(shè)定；

2） 考試時(shí)間：學(xué)生參與試卷解答時(shí)間，通過(guò)命題人設(shè)定；

3） 試卷難易程度：通過(guò)難度系數(shù)體現(xiàn)，是學(xué)生關(guān)于試題失分狀況的體現(xiàn)；

4） 試卷區(qū)分度：區(qū)分度為試卷對(duì)考生情況的辨識(shí)能力，通常大小為[-1，1]，該值越大表示區(qū)分效果越好。一般情況下，當(dāng)試題區(qū)分度高于0.39時(shí)，則認(rèn)為試卷存在較好的區(qū)分度；當(dāng)試題區(qū)分度低于0.2時(shí)，則認(rèn)為試卷區(qū)分度很差。計(jì)算區(qū)分度采用的方法為：對(duì)分?jǐn)?shù)進(jìn)行排列，[Q1=27%×dh]，[dh]表示高分組的難度，[Q2=27%×dl]，[dl]表示低分組的難度，則區(qū)分度為[ξ=Q1-Q2總分?jǐn)?shù)]；

5） 試卷涵蓋度：試卷中涉及知識(shí)點(diǎn)占所學(xué)課本的比重，是根據(jù)教學(xué)大綱與考試大綱設(shè)定的；

6） 試卷試題結(jié)構(gòu)：試卷中包含的題型通常包括單選題、填空題、計(jì)算題、簡(jiǎn)答題等。

對(duì)上述組卷限制條件進(jìn)行分析。試卷的涵蓋度為最關(guān)鍵條件，在確定試題過(guò)程中，依據(jù)試題的知識(shí)點(diǎn)屬性，通過(guò)考試大綱決定知識(shí)點(diǎn)在試卷中出現(xiàn)的形式和比重；試卷難易程度通過(guò)各考生分?jǐn)?shù)情況確定，依據(jù)以往的測(cè)試結(jié)果對(duì)題庫(kù)內(nèi)各試題的難度級(jí)別進(jìn)行劃分，并賦予相應(yīng)的難度系數(shù)值[6]。

通常要求全部考生的成績(jī)服從正態(tài)分布，由于二項(xiàng)分布在一定條件下與正態(tài)分布類(lèi)似，因此，本節(jié)通過(guò)離散型隨機(jī)變量的二項(xiàng)分布體現(xiàn)試卷難度與分?jǐn)?shù)的關(guān)系，公式描述為：

[Wsg=Fgswg1-ws-g] （1）

式中：[s]為正整數(shù)，表示最大難度級(jí)別；[Wsg]表示難度級(jí)別為[g]的試題總分?jǐn)?shù)占整個(gè)試卷總分?jǐn)?shù)的比例；[Fgs]表示難度級(jí)別為[g]的試題總分?jǐn)?shù)；[wg]表示各難度級(jí)別的難度比例；[w]表示難度系數(shù)。

1.2 目標(biāo)函數(shù)

設(shè)[k]為試卷試題數(shù)量，[Fz]為試卷總分?jǐn)?shù)，按照二項(xiàng)分布試卷難度與分?jǐn)?shù)的映射關(guān)系，通過(guò)難度系數(shù)求出每個(gè)難度級(jí)別的難度比例[wg]，[T]為考試時(shí)間，[Tj]為各試題作答時(shí)間。設(shè)[PFN]為大綱內(nèi)第[N]章知識(shí)點(diǎn)占試卷的比率，[M]為總章節(jié)數(shù)，[FN]為相應(yīng)章節(jié)試題的分?jǐn)?shù)，[ζj]為試題的區(qū)分度，則大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)成卷的初始目標(biāo)函數(shù)如下：

[f=g=0swg-FgNFz+N=1MgFNFz-PFNs.t. T-j=1kTjT≤0.15j=1kζj×FNFz≥0.3] （2）

把考試時(shí)間與試卷區(qū)分度當(dāng)成目標(biāo)函數(shù)的約束條件，以減少運(yùn)行時(shí)間。

1.3 遺傳算法適應(yīng)度函數(shù)的確定

依據(jù)上述目標(biāo)函數(shù)確定適應(yīng)度函數(shù)。適應(yīng)度函數(shù)的復(fù)雜度為遺傳算法復(fù)雜度的重要構(gòu)成部分[7]，因此，當(dāng)設(shè)計(jì)適應(yīng)度函數(shù)時(shí)需確保計(jì)算時(shí)間復(fù)雜度最低，把目標(biāo)函數(shù)描述成計(jì)算最大值形式，保證適應(yīng)度函數(shù)為非負(fù)函數(shù)。上述成卷的目標(biāo)函數(shù)為求最小值函數(shù)，依據(jù)各函數(shù)特點(diǎn)，確定兩函數(shù)間的映射關(guān)系為：

[f*=1（1+f）] （3）

式中： [f*]表示適應(yīng)度函數(shù)；[f]表示目標(biāo)函數(shù)。

針對(duì)任意個(gè)體，判斷考試時(shí)間和試卷區(qū)分度是否符合約束條件，如果兩者符合約束條件，則進(jìn)行適應(yīng)度計(jì)算；反之，停止計(jì)算。

1.4 遺傳算法編碼

通過(guò)基因分段式編碼實(shí)現(xiàn)問(wèn)題解的編碼描述，采用編碼對(duì)組卷過(guò)程中的題型及其數(shù)量分布相關(guān)的約束條件進(jìn)行處理，由此實(shí)現(xiàn)問(wèn)題的簡(jiǎn)化。詳細(xì)編碼過(guò)程為：先對(duì)每種題型進(jìn)行獨(dú)立編碼，組成相應(yīng)基因段，基因段的個(gè)數(shù)取決于題型的種數(shù)，這里用[K]描述；基因段中基因數(shù)取決于題庫(kù)中此種題型的試題數(shù)量。若題庫(kù)中存在[ε]道試題，則編碼為[a1，a2，…，aε]，其中：

[ai=1， 第i道試題被選中0， 第i道試題未被選中] （4）

對(duì)于被選中的全部試題需滿足[i=1εai=k]，[k]為試卷中的試題數(shù)量；被選中的每種題型試題需滿足[i=1u1ai=b1，i=1u2ai=b2，…，i=1uKai=bK]。其中，[u1，u2，…，uK]表示題庫(kù)內(nèi)相應(yīng)題型的試題數(shù)量；[b1，b2，…，bK]表示試卷中每種題型試題需要的數(shù)量。

1.5 遺傳算子設(shè)計(jì)

遺傳算子包括選擇算子、交叉算子以及變異算子，下面對(duì)其進(jìn)行設(shè)計(jì)。

1） 選擇算子。在進(jìn)行遺傳選擇時(shí)，通過(guò)最佳個(gè)體保存法與適應(yīng)度比例選擇法獲取算子[8]。具體過(guò)程為：先挑出最好的個(gè)體，并將其復(fù)制至下一代中，然后根據(jù)每個(gè)個(gè)體被選擇概率與其適應(yīng)度間的函數(shù)關(guān)系實(shí)現(xiàn)剩余個(gè)體的挑選。求出被選擇概率，其計(jì)算公式如下：

[P*i=Eii=1ZEi] （5）

式中：[Z]用于描述種群大??；[Ei]用于描述適應(yīng)度。

2） 交叉算子。在進(jìn)行交叉時(shí)，結(jié)合編碼方案進(jìn)行分析，選用單點(diǎn)交叉方式，交叉主要在同種題型組卷時(shí)進(jìn)行。

3） 變異算子。變異算子能夠?qū)崿F(xiàn)局部檢索，為輔助型算子，在初始種群形成時(shí)已符合各項(xiàng)約束條件。為了不改變約束條件，在同種題型中進(jìn)行兩點(diǎn)變異，也就是每種題型在自身編碼段中進(jìn)行變異。

1.6 自適應(yīng)交叉與變異概率

交叉概率[po]與變異概率[pv]對(duì)遺傳算法有極大影響，本節(jié)將適應(yīng)度作為評(píng)價(jià)群體多樣性的指標(biāo)，使[po]與[pv]隨適應(yīng)度的變化而變化。依次求出交叉概率[po]與變異概率[pv]：

[po=λ1?Emax-EoEmax-E，Eo>Eλ2，Eo

[pv=λ3?Emax-EvEmax-E，Ev>Eλ4，Ev

式中：[Eo]，[Ev]表示被計(jì)算個(gè)體的適應(yīng)度；[Emax]，[E]分別表示上一代種群內(nèi)個(gè)體最大適應(yīng)度與平均適應(yīng)度；[λ1]，[λ2]，[λ3]，[λ4]均為系數(shù)，且[λ1=λ2=1]，[λ3=0.2]，[λ4=0.4]。

1.7 終止條件

本文大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷方法選擇下述三種終止條件：

1） 搜尋到最優(yōu)解，也就是出現(xiàn)用戶滿意的試卷；

2） 相鄰兩代最大適應(yīng)度值的改變率低于閾值；

3） 達(dá)到既定進(jìn)化代數(shù)。

1.8 自動(dòng)組卷過(guò)程

基于遺傳算法的大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷方法詳細(xì)實(shí)現(xiàn)過(guò)程如下：

1） 確定初始參數(shù)和初始群體，接收用戶自動(dòng)組卷請(qǐng)求；

2） 求出群體中不同個(gè)體的適應(yīng)值，依據(jù)個(gè)體適應(yīng)值和選擇策略形成下一代父體；

3） 執(zhí)行交換與變異操作，形成新一代群體，求出當(dāng)前群體中不同個(gè)體的適應(yīng)值；

4） 對(duì)新一代最優(yōu)個(gè)體與上一代最優(yōu)個(gè)體適應(yīng)值進(jìn)行比較，若降低，則用上一代最佳個(gè)體替換當(dāng)前最佳個(gè)體；

5） 輸出當(dāng)前代數(shù)、最優(yōu)目標(biāo)函數(shù)值及最優(yōu)個(gè)體編碼，求出不同難度級(jí)別和分?jǐn)?shù)等指標(biāo)。

2 自動(dòng)組卷實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文提出遺傳算法的可行性與有效性，針對(duì)大學(xué)計(jì)算機(jī)基礎(chǔ)課程，通過(guò)ASP+SQL Server 2000，依據(jù)遺傳思想編寫(xiě)程序，進(jìn)行自動(dòng)組卷實(shí)驗(yàn)。假設(shè)題庫(kù)共存在五種題型、六個(gè)章節(jié)、七個(gè)難度系數(shù)與四個(gè)認(rèn)知層次。題庫(kù)中有700題，其題型題量分布、章節(jié)題量分布、難度題量分布和認(rèn)知層次題量分布情況如表1～表4所示。

假設(shè)組卷要求為：試卷總分為120分，選題需達(dá)到題型與題量要求，不同題型分?jǐn)?shù)已給出。所有章節(jié)的分值誤差、難度分值誤差及不同認(rèn)知層次分值誤差都在±2分以?xún)?nèi)。詳細(xì)要求如表5～表8所示。

自動(dòng)組卷結(jié)果分析：

1） 在交叉概率為0.8，變異概率為0.1的情況下，令群體規(guī)模依次取20，30，40，50，60，運(yùn)行代數(shù)在20～100范圍內(nèi)變化，則不同群體規(guī)模和代數(shù)下最佳適應(yīng)度值改變情況如表9所示。

分析表9可知，群體規(guī)模對(duì)遺傳算法收斂性有很大的影響。在群體規(guī)模較小的情況下（20和30），參與遺傳算法的試題較少，搜索空間受到限制，適應(yīng)度值小，得到有效試卷的機(jī)會(huì)很小。在群體規(guī)模達(dá)到40的情況下，適應(yīng)度值明顯升高，而當(dāng)群體規(guī)模為50和60時(shí)，適應(yīng)度值無(wú)顯著區(qū)別，基本不增長(zhǎng)，說(shuō)明群體規(guī)模達(dá)到40時(shí)，即可達(dá)到收斂，而群體規(guī)模越大，則程序運(yùn)行速度越低，所以本文實(shí)驗(yàn)設(shè)定群體規(guī)模為40。除此之外，還可以看出，在運(yùn)行代數(shù)為60代的情況下適應(yīng)度值已實(shí)現(xiàn)收斂，所以將運(yùn)行代數(shù)設(shè)置為60代。

2） 令最大迭代數(shù)為60代，交叉概率為0.8，變異概率為0.1，群體規(guī)模為40。經(jīng)50次調(diào)試運(yùn)行，獲取大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷結(jié)果。為了驗(yàn)證本文方法的有效性，將隨機(jī)生成方法和回溯試探方法作為對(duì)比，在題庫(kù)量是700題的情況下，對(duì)三種方法的組卷時(shí)間、組卷成功率進(jìn)行比較，結(jié)果如表10所示。

分析表10可知，本文方法成功概率為100%，且所需時(shí)間明顯低于隨機(jī)生成方法和回溯試探方法，性能優(yōu)于其他兩種方法，驗(yàn)證了本文基于改進(jìn)遺傳算法的大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷設(shè)計(jì)與實(shí)現(xiàn)方法的優(yōu)越性。

3 結(jié) 論

本文提出基于遺傳算法的大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷方法。介紹了大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷模型，給出通過(guò)遺傳算法實(shí)現(xiàn)大學(xué)計(jì)算機(jī)基礎(chǔ)自動(dòng)組卷的詳細(xì)過(guò)程。經(jīng)實(shí)驗(yàn)驗(yàn)證，所提方法效率和成功率較高。

參考文獻(xiàn)

[1] 陳國(guó)彬，張廣泉.基于改進(jìn)遺傳算法的快速自動(dòng)組卷算法研究[J].計(jì)算機(jī)應(yīng)用研究，2015，32（10）：2996?2998.

CHEN Guobin， ZHANG Guangquan. New algorithm for intelligent test paper composition based on improved genetic algorithm [J]. Application research of computers， 2015， 32（10）： 2996?2998.

[2] 吳愛(ài)婷，官伯然.一種基于遺傳算法的超寬帶天線自動(dòng)設(shè)計(jì)方法[J].微波學(xué)報(bào)，2015，31（3）：22?26.

WU Aiting， GUAN Boran. An automation design method of the ultra?wideband antenna based on the genetic algorithm [J]. Journal of microwaves， 2015， 31（3）： 22?26.

[3] 李瑞森，張樹(shù)有，伊國(guó)棟，等.可拓集成模式的工程圖學(xué)試題庫(kù)組卷方法研究[J].圖學(xué)學(xué)報(bào)，2016，37（6）：851?856.

LI Ruisen， ZHANG Shuyou， YIN Guodong， et al. Research on the test paper generating method of engineering graphics based on the extension and integration mode [J]. Journal of graphics， 2016， 37（6）： 851?856.

[4] 王寧，蔡順燕.基于隨機(jī)相位重構(gòu)的智能組卷混疊均衡算法[J].科技通報(bào)，2016，32（5）：236?239.

WANG Ning， CAI Shunyan. Smart group aliasing equalization algorithm based on the random phase reconstruction [J]. Bulletin of science and technology， 2016， 32（5）： 236?239.

[5] 席衛(wèi)文，張春輝，王飛，等.一種基于改進(jìn)遺傳算法的醫(yī)學(xué)題庫(kù)自動(dòng)組卷設(shè)計(jì)與實(shí)現(xiàn)[J].中國(guó)醫(yī)學(xué)物理學(xué)雜志，2016，33（8）：861?864.

XI Weiwen， ZHANG Chunhui， WANG Fei， et al. Design and implementation of improved genetic algorithm for automatic test paper generation [J]. Chinese journal of medical physics， 2016， 33（8）： 861?864.

[6] 徐海東.基于遺傳算法的自動(dòng)組卷算法的研究[J].微型電腦應(yīng)用，2016，32（3）：60?62.

XU Haidong. Research on automatic test paper based on genetic algorithm [J]. Microcomputer applications， 2016， 32（3）： 60?62.

[7] 呂海燕，周立軍，宦婧，等.通用在線考試系統(tǒng)智能組卷遺傳算法設(shè)計(jì)[J].計(jì)算技術(shù)與自動(dòng)化，2016，35（4）：85?90.

L? Haiyan， ZHOU Lijun， HUAN Jing， et al. Design of intelligent test paper generating genetic algorithm for common online examination system [J]. Computing technology and automation， 2016， 35（4）： 85?90.

[8] 潘剛，楊清平，蒲國(guó)林，等.遺傳算法在智能組卷系統(tǒng)中的應(yīng)用研究[J].云南民族大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，25（6）：579?584.

PAN Gang， YANG Qingping， PU Guolin， et al. Application of the genetic algorithm in the intelligent test paper generation system [J]. Journal of Yunnan University of Nationalities （natural sciences edition）， 2016， 25（6）： 579?584.

[9] 楊秀霞，張曉鋒，張毅.基于加速遺傳算法的艦船電力系統(tǒng)故障恢復(fù)[J].電工技術(shù)學(xué)報(bào)，2005，20（5）：53?57.

YANG Xiuxia， ZHANG Xiaofeng， ZHANG Yi. Shipboard power system service restoration based on the accelerated genetic algorithm [J]. Transactions of China electrotechnical society， 2005， 20（5）： 53?57