基于遺傳算法的大學計算機基礎自動組卷方法

楊春哲， 常涵吉

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

關鍵詞： 遺傳算法； 計算機基礎； 自動組卷； 適應度函數； 約束條件； 編碼

中圖分類號： TN99?34； TP391 文獻標識碼： 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 引 言

大學計算機基礎自動組卷是實現在線考試系統的核心技術，當前很多學校機構都對自動組卷進行了大量研究，盡可能使最終形成的試卷達到用戶要求，同時保證科學性[1]。在大學計算機基礎題庫試題質量要求高的情況下，自動組卷的效率和質量只和組卷方法有關。因此，設計一種科學有效的自動組卷方法非常關鍵，其涉及全局尋優問題，具有重要研究價值[2?3]。

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

1 遺傳算法的大學計算機基礎自動組卷方法

1.1 大學計算機基礎自動組卷模型

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

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

1） 試卷總分：試卷的總分數，通過命題人設定；

2） 考試時間：學生參與試卷解答時間，通過命題人設定；

3） 試卷難易程度：通過難度系數體現，是學生關于試題失分狀況的體現；

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

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

6） 試卷試題結構：試卷中包含的題型通常包括單選題、填空題、計算題、簡答題等。

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

通常要求全部考生的成績服從正態分布，由于二項分布在一定條件下與正態分布類似，因此，本節通過離散型隨機變量的二項分布體現試卷難度與分數的關系，公式描述為：

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

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

1.2 目標函數

設[k]為試卷試題數量，[Fz]為試卷總分數，按照二項分布試卷難度與分數的映射關系，通過難度系數求出每個難度級別的難度比例[wg]，[T]為考試時間，[Tj]為各試題作答時間。設[PFN]為大綱內第[N]章知識點占試卷的比率，[M]為總章節數，[FN]為相應章節試題的分數，[ζj]為試題的區分度，則大學計算機基礎自動成卷的初始目標函數如下：

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

把考試時間與試卷區分度當成目標函數的約束條件，以減少運行時間。

1.3 遺傳算法適應度函數的確定

依據上述目標函數確定適應度函數。適應度函數的復雜度為遺傳算法復雜度的重要構成部分[7]，因此，當設計適應度函數時需確保計算時間復雜度最低，把目標函數描述成計算最大值形式，保證適應度函數為非負函數。上述成卷的目標函數為求最小值函數，依據各函數特點，確定兩函數間的映射關系為：

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

式中： [f*]表示適應度函數；[f]表示目標函數。

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

1.4 遺傳算法編碼

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

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

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

1.5 遺傳算子設計

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

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

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

式中：[Z]用于描述種群大小；[Ei]用于描述適應度。

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

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

1.6 自適應交叉與變異概率

交叉概率[po]與變異概率[pv]對遺傳算法有極大影響，本節將適應度作為評價群體多樣性的指標，使[po]與[pv]隨適應度的變化而變化。依次求出交叉概率[po]與變異概率[pv]：

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

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

式中：[Eo]，[Ev]表示被計算個體的適應度；[Emax]，[E]分別表示上一代種群內個體最大適應度與平均適應度；[λ1]，[λ2]，[λ3]，[λ4]均為系數，且[λ1=λ2=1]，[λ3=0.2]，[λ4=0.4]。

1.7 終止條件

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

1） 搜尋到最優解，也就是出現用戶滿意的試卷；

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

3） 達到既定進化代數。

1.8 自動組卷過程

基于遺傳算法的大學計算機基礎自動組卷方法詳細實現過程如下：

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

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

3） 執行交換與變異操作，形成新一代群體，求出當前群體中不同個體的適應值；

4） 對新一代最優個體與上一代最優個體適應值進行比較，若降低，則用上一代最佳個體替換當前最佳個體；

5） 輸出當前代數、最優目標函數值及最優個體編碼，求出不同難度級別和分數等指標。

2 自動組卷實驗結果分析

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

假設組卷要求為：試卷總分為120分，選題需達到題型與題量要求，不同題型分數已給出。所有章節的分值誤差、難度分值誤差及不同認知層次分值誤差都在±2分以內。詳細要求如表5～表8所示。

自動組卷結果分析：

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

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

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

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

3 結 論

本文提出基于遺傳算法的大學計算機基礎自動組卷方法。介紹了大學計算機基礎自動組卷模型，給出通過遺傳算法實現大學計算機基礎自動組卷的詳細過程。經實驗驗證，所提方法效率和成功率較高。

參考文獻

[1] 陳國彬，張廣泉.基于改進遺傳算法的快速自動組卷算法研究[J].計算機應用研究，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] 吳愛婷，官伯然.一種基于遺傳算法的超寬帶天線自動設計方法[J].微波學報，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] 李瑞森，張樹有，伊國棟，等.可拓集成模式的工程圖學試題庫組卷方法研究[J].圖學學報，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].科技通報，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] 席衛文，張春輝，王飛，等.一種基于改進遺傳算法的醫學題庫自動組卷設計與實現[J].中國醫學物理學雜志，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].微型電腦應用，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] 呂海燕，周立軍，宦婧，等.通用在線考試系統智能組卷遺傳算法設計[J].計算技術與自動化，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] 潘剛，楊清平，蒲國林，等.遺傳算法在智能組卷系統中的應用研究[J].云南民族大學學報（自然科學版），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] 楊秀霞，張曉鋒，張毅.基于加速遺傳算法的艦船電力系統故障恢復[J].電工技術學報，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