徐海東

基于遺傳算法的自動組卷算法的研究

徐海東

自動組卷問題一直是計算機(jī)輔助教學(xué)領(lǐng)域中的一個研究熱點，如何設(shè)計一個優(yōu)良的算法讓計算機(jī)更快更好地實現(xiàn)自動組卷是研究這個問題的關(guān)鍵點。遺傳算法是現(xiàn)今比較智能的一種組卷算法，對通過對遺傳算法進(jìn)行改進(jìn)，采用分組實數(shù)編碼方案，通過證明了改進(jìn)后的遺傳算法在控制參數(shù)設(shè)置合理的情況下，能較好地實現(xiàn)自動組卷功能。

遺傳算法；自動組卷；組卷算法

0　引言

遺傳算法是一種新的全局優(yōu)化搜索算法，相較于傳統(tǒng)的組卷算法具有很多優(yōu)點，如收斂速度快、并行處理能力強(qiáng)、應(yīng)用范圍廣等等，在目前的計算機(jī)自動組卷算法有著極其重要的地位[1]。本文對通過對遺傳算法進(jìn)行改進(jìn)，采用分組實數(shù)編碼方案，通過試驗證明改進(jìn)后的遺傳算法在控制參數(shù)設(shè)置合理的情況下，能較好地實現(xiàn)自動組卷功能。

1　遺傳算法的改進(jìn)

1.1染色體編碼方案

目前在遺傳算法中采用二進(jìn)制編碼算法處理的模式最多[2]。但是在組卷問題上，對于大試題量的試題庫組卷，二進(jìn)制編碼的染色體長度太長，會造成遺傳算法的搜索空間急劇擴(kuò)大，計算量大，占用內(nèi)存多等問題[3]。已有大量實驗表明，在解決數(shù)值優(yōu)化問題，實數(shù)編碼要比二進(jìn)制編碼效率要好的多[4]。考慮到試題庫的結(jié)構(gòu)和試題特性，本文采用的是分組實數(shù)編碼方案。分組編碼就是把染色體按題型分組進(jìn)行編碼，每個編碼表示一種題型。 初始化群體時根據(jù)各類題型的試題題量要求，從試題庫中抽取滿足條件的各類型試題組成一份試卷。這樣保證了初始群體滿足題型和題量的需求。

2.2目標(biāo)函數(shù)設(shè)計

組卷問題是一個帶約束的多目標(biāo)條件下求最優(yōu)解問題[5]。本文把各個試卷參數(shù)取值的限定作為組卷的多個目標(biāo)。

如果假設(shè)難度級別為i的試題所占的分?jǐn)?shù)為 ai（i=1,2,…,n,n 為難度級別的最高值），則組卷約束要求各難度等級的試題分值總和應(yīng)該等于試卷總分，即。設(shè)Δai為試卷中難度級別為i的試題總分和實際要求總分之間的差值，所以試卷中各難度級別試題的實際分?jǐn)?shù)與設(shè)定值的偏差的平均值f1可以用公式（1）：

類似的，如果假設(shè)知識點編號為i的試題所占的分?jǐn)?shù)為bi（i=1,2,…,m,m 代表知識點的總數(shù)），則試卷總分可以用來表示。對于這一約束條件，也可以轉(zhuǎn)換為目標(biāo)函數(shù)的一部分。設(shè)Δbi為知識點編號為i的試題總分和實際要求總分之間的差值，f2為試卷中各類知識點的試題實際分?jǐn)?shù)與設(shè)定值的偏差，則f2可用公式（2）：

同樣的，f2越小說明選取的試題越符合用戶的要求，誤差越?。环粗畡t說明選取的試題離用戶的要求越遠(yuǎn)，誤差越大。

將這些平均差值當(dāng)作一個個目標(biāo)分量，組合起來就可以作為組卷算法的目標(biāo)函數(shù)。由于約束條件的多樣性，這些目標(biāo)分量往往很難被同時滿足，而且它們之間的重要性根據(jù)用戶的設(shè)定也有差異，所以可以給這些目標(biāo)分量分配權(quán)值 ri來表示第i個目標(biāo)分量的重要性，ri越大說明該目標(biāo)分量越重要。所以目標(biāo)函數(shù)f(x)可用公式（3）：

由上面的公式可以看出，f（x）越小，選出的試題就越符合用戶的要求，因此組卷問題就變成目標(biāo)函數(shù)f(x)最小化問題[5]。

1.3適應(yīng)度函數(shù)設(shè)計

適應(yīng)度函數(shù)的通常是將目標(biāo)函數(shù)映射到適應(yīng)度函數(shù)[6]。因為本文設(shè)計的目標(biāo)函數(shù)是求最小值問題，所以在目標(biāo)函數(shù)F(x)轉(zhuǎn)換為適應(yīng)度函數(shù)F(x)時采用如下公式進(jìn)行轉(zhuǎn)換如公式（4）：

上述公式將組卷問題從求目標(biāo)函數(shù)的最小值問題轉(zhuǎn)換為求適應(yīng)度函數(shù)的最大值問題來求解[7]。

1.4遺傳算子設(shè)計

1）選擇算子

在遺傳算法中，由選擇算子來對試卷群體進(jìn)行選擇[8]。在選擇時應(yīng)該優(yōu)先保留優(yōu)秀的試卷個體，同時也要防止優(yōu)秀的試卷個體控制整個群體。本文采用的選擇算子為輪盤賭選擇法，它是目前遺傳算法中最常用的方法，選擇操作過程如下：

1）依次累加試卷群體中試卷個體的適應(yīng)值，得到相應(yīng)的累加和Si；

2）在區(qū)間[0，Sn]上產(chǎn)生一個服從均勻分布的隨機(jī)數(shù) ；

3）依次用Si和 R 進(jìn)行比較，第一個出現(xiàn)Si ≥ R的個體i 被選擇為復(fù)制對象；

4）重復(fù)步驟2，3直到選出滿足試卷所需要的個體數(shù)目為止。

2）交叉算子

交叉的操作過程：先將種群中的試卷染色體進(jìn)行兩兩配對，假設(shè)種群規(guī)模為M，則配對試卷染色體的個數(shù)為 M/2。在每對試卷染色體中隨機(jī)選擇一個交叉點進(jìn)行交叉，交叉過后該對試卷染色體的基因進(jìn)行互換，形成一對新的試卷個體。以分組實數(shù)編碼方案為例，交叉操作的過程如表1、表2所示：

表1　交叉前的父代試卷染色體A和B

表2　交叉后的子代試卷染色體A'和B'

交叉操作生成子代試卷染色體可能存在兩個問題：一個是基因重復(fù)[9]；另外一個是順序混亂[10]。如果出現(xiàn)這兩個問題中的任意一個，那么該染色體就是非法的。為了避免出現(xiàn)這兩個問題，本文采用如下方法：在相同的編碼段內(nèi)，將處在交叉點的基因依次與交叉點前的基因從后向前依次做比較，遇到第一個小于交叉點基因的基因則停止判斷，記錄該基因的編碼 m，然后再將交叉點前一個基因與交叉點之后的基因從前向后依次做比較，遇到第一個大于交叉點前一個基因的基因就停止判斷，并記錄該基因編碼 n。所以交叉之后的重復(fù)和排序問題就是在區(qū)間[m，n]內(nèi)做判斷。假設(shè)交叉點基因編碼為 p，那么兩層循環(huán)就在區(qū)間[m，p-1]和[p，n]內(nèi)判斷是否重復(fù)，如果有重復(fù)，就將[p，n]內(nèi)的重復(fù)基因替換成該段中沒有出現(xiàn)過的基因，替換的方式是隨機(jī)抽取一個沒有出現(xiàn)過的試題編碼。最后將 B'中的基因重新排序。比如對 B'中的第二段基因編碼，只需重新排序即可；對 B 中的第三段編碼，可以將后一個編碼為 37的基因進(jìn)行替換，然后再重新排序即可。

3）變異算子

在遺傳算法中，變異算子一般采用小概率對某個試卷染色體的某一段基因里的基因值做變動，變異點采用隨機(jī)的方式生成[11]。并不是所有的試卷染色體都會采用變異操作，而是根據(jù)變異概率來確定變異[12]。假設(shè)變異概率為pm，pm的取值在區(qū)間[0，1]內(nèi)。如果pm過小，則不利于新的試卷個體的生成，從而使遺傳算法過早陷入局部最優(yōu)，產(chǎn)生“早熟”現(xiàn)象；如果pm過大，遺傳算法就變成了隨機(jī)搜索算法。

為了解決上述問題，本文根據(jù)試卷群體的進(jìn)化情況設(shè)計了適應(yīng)度函數(shù)，以自適應(yīng)的方式來動態(tài)地調(diào)整變異概率pm。變異概率計算公式如公式（6）：

其中km為變異概率系數(shù)，取值區(qū)間為[0.01， 0.05]， F為變異試卷個體的適應(yīng)度值，F(xiàn)max為試卷群體中所有試卷個體的適應(yīng)度最大值， ˉ為試卷群體中所有試卷個體的適應(yīng)度的平均值。

2　.實驗結(jié)果及分析

本文為了驗證上述遺傳算法的可行性和有效性，以《數(shù)據(jù)庫結(jié)構(gòu)》課程為例，通過上面實現(xiàn)的基于安卓的自動組卷系統(tǒng)對算法進(jìn)行了性能測試。

本次實驗?zāi)M題庫中共有 400道題，其中選擇題 150題，填空題 150 題，問答題50題，綜合題50 題。期望生成的試卷中包含 33道題，這4種類型的題目在試卷中數(shù)量比例為 15：10：5：3，試卷題型數(shù)量結(jié)構(gòu)如表3 所示：

表3　試卷題型數(shù)量結(jié)構(gòu)

題目難度-分?jǐn)?shù)分布情況如表4所示：

表4　題目難度-分?jǐn)?shù)分布情況

知識點-分?jǐn)?shù)分布情況如表5所示：

表5　題目知識點-分?jǐn)?shù)分布情況

測試過程：

固定最大迭代次數(shù) MaxGen=200，群體規(guī)模PopSize=80，最佳適應(yīng)度閾值 Fitness=0.85[14-15]。算法的終止條件是迭代次數(shù)達(dá)到 MaxGen 或者最好的試卷適應(yīng)度值大于或等于 Fitness。調(diào)整交叉概率pc和變異概率pm，觀察它們對組卷效率和算法收斂性的影響。 當(dāng)pc = 0.3時，對pm取不同的值分別運行組卷程序 20次，實驗結(jié)果如表 6所示：

表6　變異概率pm對組卷成功率和算法收斂性的影響

由實驗數(shù)據(jù)可以看出當(dāng)pm > 0.5和pm < 0.0001時，組卷效率和算法收斂性都明顯下降，因為變異率取值太大雖然可以增加試卷群體的多樣性，但同時也會破壞群體中的優(yōu)秀試卷個體；變異率取值太小則新的試卷個體產(chǎn)生的速率又太慢。所以pm的取值最好在區(qū)間[0.01，0.05]之間。

3）當(dāng)pm = 0.03時，對pc取不同的值分別運行組卷程序 20次，實驗結(jié)果如表7所示：

表7　交叉概率pc對組卷成功率和算法收斂性的影響

數(shù)（次）數(shù)（次）（秒）適應(yīng)度值0.2　16　179.1　1.965　0.85 0.4　20　162.2　1.632　0.87 0.6　20　162.5　1.636　0.85 0.8　19　161　1.651　0.86 1.0　17　180.6　2.013　0.86

由實驗數(shù)據(jù)可以看出當(dāng)pc在區(qū)間[0.4，0.6]之間時，組卷效率和算法收斂性比較好。

4）控制交叉概率pc為 0.4，變異概率pm為 0.02，組卷系統(tǒng)的組卷算法分別使用傳統(tǒng)的遺傳算法和改進(jìn)后的遺傳算法進(jìn)行 20 次組卷實驗。實驗結(jié)果如表 8所示：

表8　傳統(tǒng)遺傳算法和改進(jìn)后的遺傳算法實驗結(jié)果

3　總結(jié)

上述實驗結(jié)果證明，只要適當(dāng)控制算法的參數(shù)，改進(jìn)后遺傳算法具有較好的組卷效果，并且比傳統(tǒng)的遺傳算法組卷成功率更高，收斂速度更快。

[1] 張建國. 智能教學(xué)系統(tǒng)中的自動組卷算法研究[D]. 河南:河南大學(xué).2009:12-14.

[2] 秦金亮. 標(biāo)準(zhǔn)化題庫建設(shè)的數(shù)學(xué)模型建構(gòu)[J]. 山西師范大學(xué)學(xué)報,2000,14(2): 21-22

[3] 周文勝,潘中柱. 一種實用的隨機(jī)組卷算法的設(shè)計思想[J]. 湖南科技學(xué)院學(xué)報,2005,11(2):115-116.

[4] 管寶云,尹琦. 基于混合智能算法的自動組卷問題研究[J]. 天津工業(yè)大學(xué)學(xué)報,2006,4(1):32-33.

[5] S.S.Guttormsen & H.Kruemut. Using New Learning Technologies with Multimedia[J].IEEE Multimedia July-September,2000,36(7):40-51.

[6] 陳熙,吳成秋,賀棟梁.試卷分析與評價的指標(biāo)體系及其應(yīng)用[J]. 微處理機(jī),2006,14(5):31-32.

[7] 柳國杰,陳軍. 教育測量中難度與區(qū)分度的計算方法[J].信陽師范學(xué)院學(xué)報,2003,3(2):5-7.

[8] 趙立新,陳文藝,郭子君. 試卷質(zhì)量的定量評價[J]. 華南農(nóng)業(yè)大學(xué)學(xué)報,2004,3(4):21-22.

[9] 林雪明,張鈞良,蔣偉鋼. 基于知識點的試題庫組卷算法的建立[J]. 微機(jī)發(fā)展,2001,11(2):77-80.

[10] 田茁,李太浩. 遺傳算法在試題組卷中的應(yīng)用[J]. 長春師范學(xué)院學(xué)報,2005, 24(3):555-557.

[11] 陳宇,陳治平. 啟發(fā)式遺傳算法組卷模型研究[J]. 計算機(jī)技術(shù)與自動化,2006,25(1):11-12.

[12] 劉明明，許勇.基于Web的在線考試系統(tǒng)分析與評價[J].管理觀察,2009,3(5):235-238

[13] 王琪，張冬梅.試論在線考試系統(tǒng)的設(shè)計與實現(xiàn)[J].教育信息化,2002,5(11):37-38

[14] 沈建強(qiáng)，張寶明，鄒軒.組卷系統(tǒng)的優(yōu)化與實現(xiàn)[J].計算機(jī)應(yīng)用,2003,6(S1) : 25-28

[15] 路平，王敏娟，萬昆.試題庫白動組卷策略研究[J].電腦開發(fā)與應(yīng)用,2001,2(02) : 56-58

Research on Automatic Test Paper Based on Genetic Algorithm

Xu Haidong
(Mechanical and Electrical College,Xiangyang Vocational and Technical College,Xiangyang 441050,China)

The problem of auto-forming test paper has become a research hotspot in the computer-assisted instruction field. How to design a better algorithm to help the computer realize an auto-forming test paper has become the key point of this problem. The genetic algorithm is a kind of intelligent test paper algorithm,which can be used to solve that kind of problems of optimization about multi restrain conditions and multi objectives. In this paper,the genetic algorithm is improved based on the deeply research on the genetic algorithm,and according to the lots of experiment results,the improved genetic algorithm is verified that it can realize the auto-forming test paper better under the reasonable control parameters.

Genetic Algorithm; Automatic Test Paper; Test Paper Algorithm

TP311

A

1007-757X(2016)03-0060-03

徐海東 （1975-11），上海人，男，襄陽職業(yè)技術(shù)學(xué)院，機(jī)電學(xué)院，碩士，助講，研究方向：計算機(jī)科學(xué)，襄陽，441050

（2015.07.15）