基于遺傳算法的大學(xué)計算機基礎(chǔ)自動組卷方法

楊春哲， 常涵吉

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

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

中圖分類號： TN99?34； TP391 文獻標(biāo)識碼： A 文章編號： 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é)計算機基礎(chǔ)自動組卷是實現(xiàn)在線考試系統(tǒng)的核心技術(shù)，當(dāng)前很多學(xué)校機構(gòu)都對自動組卷進行了大量研究，盡可能使最終形成的試卷達到用戶要求，同時保證科學(xué)性[1]。在大學(xué)計算機基礎(chǔ)題庫試題質(zhì)量要求高的情況下，自動組卷的效率和質(zhì)量只和組卷方法有關(guān)。因此，設(shè)計一種科學(xué)有效的自動組卷方法非常關(guān)鍵，其涉及全局尋優(yōu)問題，具有重要研究價值[2?3]。

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

1 遺傳算法的大學(xué)計算機基礎(chǔ)自動組卷方法

1.1 大學(xué)計算機基礎(chǔ)自動組卷模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 遺傳算法編碼

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

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

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

1.5 遺傳算子設(shè)計

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

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

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

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

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

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

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

交叉概率[po]與變異概率[pv]對遺傳算法有極大影響，本節(jié)將適應(yīng)度作為評價群體多樣性的指標(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]表示被計算個體的適應(yīng)度；[Emax]，[E]分別表示上一代種群內(nèi)個體最大適應(yīng)度與平均適應(yīng)度；[λ1]，[λ2]，[λ3]，[λ4]均為系數(shù)，且[λ1=λ2=1]，[λ3=0.2]，[λ4=0.4]。

1.7 終止條件

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

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

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

3） 達到既定進化代數(shù)。

1.8 自動組卷過程

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

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

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

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

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

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

2 自動組卷實驗結(jié)果分析

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

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

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

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

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

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

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

3 結(jié) 論

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

參考文獻

[1] 陳國彬，張廣泉.基于改進遺傳算法的快速自動組卷算法研究[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] 吳愛婷，官伯然.一種基于遺傳算法的超寬帶天線自動設(shè)計方法[J].微波學(xué)報，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] 李瑞森，張樹有，伊國棟，等.可拓集成模式的工程圖學(xué)試題庫組卷方法研究[J].圖學(xué)學(xué)報，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] 王寧，蔡順燕.基于隨機相位重構(gòu)的智能組卷混疊均衡算法[J].科技通報，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)文，張春輝，王飛，等.一種基于改進遺傳算法的醫(yī)學(xué)題庫自動組卷設(shè)計與實現(xiàn)[J].中國醫(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] 徐海東.基于遺傳算法的自動組卷算法的研究[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].計算技術(shù)與自動化，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] 潘剛，楊清平，蒲國林，等.遺傳算法在智能組卷系統(tǒng)中的應(yīng)用研究[J].云南民族大學(xué)學(xué)報（自然科學(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é)報，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