基于差分進化算法的英語考試智能組卷

劉學豐

(渤海大學，遼寧 錦州 121013)

基于差分進化算法的英語考試智能組卷

劉學豐

(渤海大學，遼寧 錦州 121013)

為保證英語大規模標準化考試質量要求和信息化建設的需要，針對傳統組卷算法存在的問題，基于差分進化算法展開研究。首先，在闡明影響試卷質量指標的基礎上，構建了組卷算法數學模型；然后，研究差分進化算法模型，主要針對變異、交叉和選擇三種操作；最后，以組卷算法和差分進化算法模型為基礎，繪制了差分進化算法智能組卷程序流程圖，并對主要步驟進行了說明。差分進化算法具有原理簡單、受控參數少、魯棒性強、收斂性和穩定性好等特點，依據文中研究內容可以快速構建適合于大學英語教學和考試的智能組卷系統。

差分進化算法；英語考試；智能組卷；程序流程

0 引 言

目前的大學英語教學是以《大學英語教學大綱》為基礎，考試內容及題型主要圍繞《大學英語四級考試大綱》進行。大學英語考試是大學英語教育的重要組成部分，目的是對大學生實際英語能力進行客觀、準確的測量，為大學英語教學提供服務。大學英語考試也是一項大規模標準化考試，為了提高考試成績，必須保證試卷質量，在設計上必須滿足教育測量理論對大規模標準化考試的質量要求。生成試卷速度慢、質量不高是傳統組卷算法的主要缺點，已越來越不適應教育信息化的需要[1-2]。

智能組卷是利用人工智能技術，由計算機自動從試題庫中選擇試題，組成符合要求的試卷，是考試系統智能化或半智能化操作的核心目標之一，是計算機輔助教學的重要組成部分[3]。智能組卷的效率與質量主要取決于組卷算法。如何設計算法從題庫中既快又好地抽出一組最符合考試要求的試題，是全局尋優和快速收斂問題。差分進化算法(Differential Evolution，DE)是基于群體智能的隨機并行優化算法，遵循達爾文的“適者生存、優勝劣汰”的進化原則[4-5]。特有的記憶能力使其可以動態跟蹤當前的搜索情況，以調整搜索策略，實現自適應尋優，因此具有較強的全局收斂性和魯棒性，能夠求解利用常規的數學規劃方法所無法求解的復雜環境中的優化問題，非常適宜處理試題庫智能組卷[6]。文中基于差分進化算法研究英語考試智能組卷問題，為軟件系統開發提供支持。

1 組卷算法數學模型

智能組卷的過程就是通過辨識問題中變量之間的關系而把實際問題轉化為由數學模型并運用計算機求解的過程，組卷質量依賴于數學模型。因此，建立數學模型是智能組卷的基礎性工作。

1.1 影響試卷質量的指標

根據經典測量理論(Classical Test Theory，CTT)，題庫是按照一定的教育測量理論并利用計算機技術構成的某種學科題目的集合。智能組卷系統的試題來源于題庫，題庫中題目的質量直接影響組卷的質量，參照CTT的題目量化指標，將影響試卷質量的屬性指標歸納為如下4個[7]：

(1)信度：反映考試結果的穩定程度，即考試結果的可信度。信度高說明考生分數不易受偶然性因素影響，考生分數可以比較真實地反映出考生的實際水平。影響信度的因素包括試題難度、題目數量、題目用語準確性等。

(2)效度：反映試卷的有效程度，即考試結果與預期要達到的考試目標相符合的程度。效度高的試卷，能夠準確地測試出考生掌握或運用所學知識和技能的真實情況。提高效度要注意試題與考試目標以及課程標準的一致性。

(3)難度：反映試題或試卷考查學生知識和能力水平適合的程度。難度中等時分數呈正態分布；難度較大時呈負偏態分布；難度較小時呈正偏態分布。因為難度值要在考試結束后通過統計得到，因此，組卷時必須對難度做出比較準確的估計。

(4)區分度：反映試題對于不同層次考生的鑒別能力。區分度高的試卷能對不同知識水平和能力的學生加以區分，使能力強的學生得高分，能力弱的學生得低分。區分度和難度有著密切的關系，只有合適的難度才會有很好的區分度。

1.2 組卷數學模型描述

組織一份試卷時，要確定試卷的滿分值、試題難度、試題數量、知識點分布以及考查的能力層次等參數指標。結合英語考試的實際情況，建立由9項核心屬性的智能組卷數學模型，一份試卷的參數指標變成了一個9維空間向量，即：試題(試題編號，分值，難度系數，能力層次，知識點，題型，區分度，答題時間，使用頻率)。一道試題由9個參數指標(屬性)決定，即由一個9維向量空間(a1,a2,a3,a4,a5,a6,a7,a8,a9)的特征決定。

設一套有n道試題的試卷，可以用(n×9)的矩陣表示：

S=

(1)

式中各屬性描述如下：

(1)試題編號。試題編號(a11,a21,…,an1)是試題的唯一標識，對計算機處理極為重要。根據四級試卷結構，試題編號由四位數字和代碼構成[8]。第1位分別用“Ⅰ、Ⅱ、Ⅲ、Ⅳ”表示試卷的“PartⅠ、PartⅡ、PartⅢ、PartⅣ”部分；第2位分別用“A、B、C”表示PartⅡ和PartⅢ的“SectionA、SectionB、SectionC”部分，PartⅠ和PartⅣ部分用“N”補位；第3位和第4位用“01，02，03，…”等數字表示小題號，無小題號時用“00”補位。

(4)能力層次。《大學英語課程教學要求》將大學階段的英語教學要求分為三個能力層次，即一般要求、較高要求和更高要求，每個能力層次有其對應的編碼。ai4表示第i道試題的能力層次編碼，所選擇的試題應滿足指定的能力層次要求。

(9)使用頻率。ai9表示第i道試題單位時間內使用的次數，這里的單位時間可以是年，也可以是學期。如果使用頻率較高，表明學生考過該題的可能性就大。因此，組卷初步完成后，要考察使用頻率，將使用頻率較高的試題替換掉。

2 差分進化算法模型

DE是基于實數編碼的進化算法，與遺傳算法的主要區別在變異操作，DE變異操作基于染色體的差異向量進行，其余操作則和遺傳算法類似。差分進化算法主要是變異、交叉和選擇三種操作，因此數學模型圍繞三種操作構建[9]。

2.1 變異操作

變異操作是DE算法的重要操作，通過差分方式實現。基本方法是在當前種群中隨機選取兩個相異個體，將它們的差向量縮放后與另外的待變異個體進行向量運算，生成新個體[10-11]。

定義差分向量：

(2)

將差分向量加權后再加到第三個隨機選取的個體向量上就形成了變異向量：

(3)

式中，F為縮放因子，是[0,2]區間上的一個實常數，用于控制差分向量的縮放程度。

2.2 交叉操作

(4)

2.3 選擇操作

(5)

從式(5)可以看出，變異操作實際是將兩個不同父代個體的差值加權后加到第三父代個體，從而得到一個新個體。因此，DE具有很好的幾何意義。

3 智能組卷程序流程

組卷問題實質是多重約束條件的最優求解問題，滿足條件的最優解不惟一。計算機智能組卷是以數學模型為基礎進行軟件開發。

基于差分進化算法的英語考試智能組卷程序流程如圖1所示[13-14]。

圖1 智能組卷程序流程圖

對圖1的各步驟描述如下[15-16]：

(1)初始化組卷參數。包括組卷算法數學模型的參數和DE算法參數。組卷算法數學模型的參數包括等難度系數、能力層次、知識點、題型、區分度、答題時間、使用頻率等；DE算法參數包括種群的大小、最大迭代次數、變異算子、交叉算子等。

(6)

式中，rand[0,1]為[0,1]區間的均勻隨機數。

(7)

式中，ck表示試題k；k表示試題編號。

(4)計算個體適應度值。適應度是以數值的方式來評估個體向量相對于整個群體的優劣程度的指標。適應度值的計算需要適應度函數，也稱評價函數。DE算法的適應度函數不受連續可微的約束，可以任意設定區域，為了保證適應性能好的個體被選擇的機會大，適應度函數的取值必須非負，設計盡可能簡單，使計算的時間復雜度最小。

(5)判斷是否滿足算法終止條件。最大進化代數可作為DE的終止條件，還需要其他判定準則。一般當目標函數值小于閾值時程序終止，閾值常選為10-6；或者通過判斷種群中的最優值連續若干代并沒有明顯變化時，也可以作為終止條件。

(6)差分進化操作。依據差分進化算法模型進行變異、交叉、選擇操作。

4 結束語

智能組卷是大學英語考試自動化的核心工作，如何保證生成的試卷最大程度地滿足考試需要，并具有隨機性、科學性、合理性等特點是實現過程中的難點。DE算法通過變異算子來探索新解，利用交叉算子進行局部開發，利用貪婪選擇策略進行保優，使種群向最優區域靠攏。與其他算法相比，具有基本原理簡單、受控參數少、魯棒性強、收斂性和穩定性好等特點。依據文中的研究內容可以快速構建適合于大學英語教學和考試的智能組卷系統。同時也必須注意，DE算法的理論基礎還比較貧乏，為了使智能組卷系統更科學合理，擴展DE算法和其他算法相結合，是未來智能組卷算法的發展方向。

[1] 唐啟濤.基于改進的遺傳算法的智能組卷算法研究[J].計算機技術與發展,2014,24(12):241-244.

[2] 雷 茜，劉淳安．智能優化的英語試題庫組卷策略研究[J]．科學技術與工程，2009，9(24):7500-7502.

[3]ZhangYJ,LiHB.Cluster-basedpopulationinitializationfordifferentialevolutionframeworks[J].ProcediaEnvironmentalSciences,2011,10(1):517-522.

[4] 郭 鵬.差分進化算法改進研究[D].天津:天津大學,2012.

[5] 張貴軍，何洋軍，郭海鋒，等.基于廣義凸下界估計的多模態差分進化算法[J].軟件學報,2013,24(6):1177-1195.

[6] 百度文庫.差分進化算法[EB/OL].2015-03-01.http://wenku.baidu.com/link?url=k9NS6nEw09MKfwhh5WhPd5VnFoLzkEqjJwxDsM67w2INu3VwhzmrhcfjEs3IM3F3R_fTXTTPoLTBiLNBZccE3l3MdP4QvdO_s7dRyVXgp9a.

[7] 衡量試卷的標準.衡量試卷質量的四大指標[EB/OL].2015-03-01.http://www.jxteacher.com/lcez/column72487/a2a4fff0-00bc-454c-baf9-005932658190.html.

[8] 馬 寧.大學英語四級題型改革后英語學習策略探討[J].讀與寫:教育教學刊,2012,9(1):21-22.

[9]PoikolainenI,NeriF,CaraffiniF.Cluster-basedpopulationinitializationfordifferentialevolutionframeworks[J].InformationSciences,2015,297(10):216-235.

[10] 王鳳蕊，王文宏，潘全科.基于差分進化算法的智能組卷研究[J].計算機工程與設計,2009,30(8):1974-1976.

[11]AyalaHVH,dosSantosFM,MarianiVC,etal.Imagethresholdingsegmentationbasedonanovelbetadifferentialevolutionapproach[J].ExpertSystemswithApplications,2015,42(4):2136-2142.

[12] 劉淳安，趙天緒，黃梅娟.基于差分進化算法的智能組卷方法[J].計算機與數宇工程,2011,39(1):1-3.

[13]ZamudaA,BrestJ.Vectorizedproceduralmodelsforanimatedtreesreconstructionusingdifferentialevolution[J].InformationSciences,2014,278(10):1-21.

[14] 魏玉霞.差分進化算法的改進及其應用[D].廣州：華南理工大學,2013.

[15]LuXiaofen,TangKe,SendhoffB.Anewself-adaptationschemefordifferentialevolution[J].Neurocomputing,2014,146(25):2-16.

[16]SharmaH,BansalJC,AryaKV.Selfbalanceddifferentialevolution[J].JournalofComputationalScience,2014,5(2):312-323.

[17] 孫成富，趙建洋，陳劍洪.差分進化算法馬爾可夫鏈模型及收斂性分析[J].計算機技術與發展,2013,23(8):62-65.

Intelligent Test Paper Composition on English Examination Based on Differential Evolution Algorithm

LIU Xue-feng

(Bohai University,Jinzhou 121013,China)

In order to ensure the quality requirements of large-scale standardized tests in English and the needs of information construction,study is carried on based on differential evolution in the light of the problems in traditional test paper algorithm.First,a mathematical model of test paper algorithm was constructed after illustrating indicators effected papers’ quality.Then,the model of differential evolution was studied,especially for mutation,crossover and choice.Finally,the program flowchart of intelligent test paper composition based on differential evolution was drawn according to test paper algorithm and model of differential evolution algorithm,and the main steps were described.Differential evolution algorithm has many characteristics,such as simple in principle,less controlled parameters,strong robustness,good convergence and stability and so on.Intelligent test paper composition system for college English learning and test can be quickly built based on the content studied.

differential evolution;English examination;intelligent test paper composition;program flow

2015-03-08

2015-06-11

時間：2016-01-04

遼寧省教育科學“十二五”規劃項目(JG12DB243)

劉學豐(1970-)，女，副教授，碩士，研究方向為英語教育信息化。

http://www.cnki.net/kcms/detail/61.1450.TP.20160104.1608.072.html

TP311

A

1673-629X(2016)01-0181-04

10.3969/j.issn.1673-629X.2016.01.039