基于差分進(jìn)化算法的英語(yǔ)考試智能組卷

劉學(xué)豐

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

基于差分進(jìn)化算法的英語(yǔ)考試智能組卷

劉學(xué)豐

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

為保證英語(yǔ)大規(guī)模標(biāo)準(zhǔn)化考試質(zhì)量要求和信息化建設(shè)的需要，針對(duì)傳統(tǒng)組卷算法存在的問(wèn)題，基于差分進(jìn)化算法展開(kāi)研究。首先，在闡明影響試卷質(zhì)量指標(biāo)的基礎(chǔ)上，構(gòu)建了組卷算法數(shù)學(xué)模型；然后，研究差分進(jìn)化算法模型，主要針對(duì)變異、交叉和選擇三種操作；最后，以組卷算法和差分進(jìn)化算法模型為基礎(chǔ)，繪制了差分進(jìn)化算法智能組卷程序流程圖，并對(duì)主要步驟進(jìn)行了說(shuō)明。差分進(jìn)化算法具有原理簡(jiǎn)單、受控參數(shù)少、魯棒性強(qiáng)、收斂性和穩(wěn)定性好等特點(diǎn)，依據(jù)文中研究?jī)?nèi)容可以快速構(gòu)建適合于大學(xué)英語(yǔ)教學(xué)和考試的智能組卷系統(tǒng)。

差分進(jìn)化算法；英語(yǔ)考試；智能組卷；程序流程

0 引 言

目前的大學(xué)英語(yǔ)教學(xué)是以《大學(xué)英語(yǔ)教學(xué)大綱》為基礎(chǔ)，考試內(nèi)容及題型主要圍繞《大學(xué)英語(yǔ)四級(jí)考試大綱》進(jìn)行。大學(xué)英語(yǔ)考試是大學(xué)英語(yǔ)教育的重要組成部分，目的是對(duì)大學(xué)生實(shí)際英語(yǔ)能力進(jìn)行客觀、準(zhǔn)確的測(cè)量，為大學(xué)英語(yǔ)教學(xué)提供服務(wù)。大學(xué)英語(yǔ)考試也是一項(xiàng)大規(guī)模標(biāo)準(zhǔn)化考試，為了提高考試成績(jī)，必須保證試卷質(zhì)量，在設(shè)計(jì)上必須滿(mǎn)足教育測(cè)量理論對(duì)大規(guī)模標(biāo)準(zhǔn)化考試的質(zhì)量要求。生成試卷速度慢、質(zhì)量不高是傳統(tǒng)組卷算法的主要缺點(diǎn)，已越來(lái)越不適應(yīng)教育信息化的需要[1-2]。

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

1 組卷算法數(shù)學(xué)模型

智能組卷的過(guò)程就是通過(guò)辨識(shí)問(wèn)題中變量之間的關(guān)系而把實(shí)際問(wèn)題轉(zhuǎn)化為由數(shù)學(xué)模型并運(yùn)用計(jì)算機(jī)求解的過(guò)程，組卷質(zhì)量依賴(lài)于數(shù)學(xué)模型。因此，建立數(shù)學(xué)模型是智能組卷的基礎(chǔ)性工作。

1.1 影響試卷質(zhì)量的指標(biāo)

根據(jù)經(jīng)典測(cè)量理論(Classical Test Theory，CTT)，題庫(kù)是按照一定的教育測(cè)量理論并利用計(jì)算機(jī)技術(shù)構(gòu)成的某種學(xué)科題目的集合。智能組卷系統(tǒng)的試題來(lái)源于題庫(kù)，題庫(kù)中題目的質(zhì)量直接影響組卷的質(zhì)量，參照CTT的題目量化指標(biāo)，將影響試卷質(zhì)量的屬性指標(biāo)歸納為如下4個(gè)[7]：

(1)信度：反映考試結(jié)果的穩(wěn)定程度，即考試結(jié)果的可信度。信度高說(shuō)明考生分?jǐn)?shù)不易受偶然性因素影響，考生分?jǐn)?shù)可以比較真實(shí)地反映出考生的實(shí)際水平。影響信度的因素包括試題難度、題目數(shù)量、題目用語(yǔ)準(zhǔn)確性等。

(2)效度：反映試卷的有效程度，即考試結(jié)果與預(yù)期要達(dá)到的考試目標(biāo)相符合的程度。效度高的試卷，能夠準(zhǔn)確地測(cè)試出考生掌握或運(yùn)用所學(xué)知識(shí)和技能的真實(shí)情況。提高效度要注意試題與考試目標(biāo)以及課程標(biāo)準(zhǔn)的一致性。

(3)難度：反映試題或試卷考查學(xué)生知識(shí)和能力水平適合的程度。難度中等時(shí)分?jǐn)?shù)呈正態(tài)分布；難度較大時(shí)呈負(fù)偏態(tài)分布；難度較小時(shí)呈正偏態(tài)分布。因?yàn)殡y度值要在考試結(jié)束后通過(guò)統(tǒng)計(jì)得到，因此，組卷時(shí)必須對(duì)難度做出比較準(zhǔn)確的估計(jì)。

(4)區(qū)分度：反映試題對(duì)于不同層次考生的鑒別能力。區(qū)分度高的試卷能對(duì)不同知識(shí)水平和能力的學(xué)生加以區(qū)分，使能力強(qiáng)的學(xué)生得高分，能力弱的學(xué)生得低分。區(qū)分度和難度有著密切的關(guān)系，只有合適的難度才會(huì)有很好的區(qū)分度。

1.2 組卷數(shù)學(xué)模型描述

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

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

S=

(1)

式中各屬性描述如下：

(1)試題編號(hào)。試題編號(hào)(a11,a21,…,an1)是試題的唯一標(biāo)識(shí)，對(duì)計(jì)算機(jī)處理極為重要。根據(jù)四級(jí)試卷結(jié)構(gòu)，試題編號(hào)由四位數(shù)字和代碼構(gòu)成[8]。第1位分別用“Ⅰ、Ⅱ、Ⅲ、Ⅳ”表示試卷的“PartⅠ、PartⅡ、PartⅢ、PartⅣ”部分；第2位分別用“A、B、C”表示PartⅡ和PartⅢ的“SectionA、SectionB、SectionC”部分，PartⅠ和PartⅣ部分用“N”補(bǔ)位；第3位和第4位用“01，02，03，…”等數(shù)字表示小題號(hào)，無(wú)小題號(hào)時(shí)用“00”補(bǔ)位。

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

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

2 差分進(jìn)化算法模型

DE是基于實(shí)數(shù)編碼的進(jìn)化算法，與遺傳算法的主要區(qū)別在變異操作，DE變異操作基于染色體的差異向量進(jìn)行，其余操作則和遺傳算法類(lèi)似。差分進(jìn)化算法主要是變異、交叉和選擇三種操作，因此數(shù)學(xué)模型圍繞三種操作構(gòu)建[9]。

2.1 變異操作

變異操作是DE算法的重要操作，通過(guò)差分方式實(shí)現(xiàn)。基本方法是在當(dāng)前種群中隨機(jī)選取兩個(gè)相異個(gè)體，將它們的差向量縮放后與另外的待變異個(gè)體進(jìn)行向量運(yùn)算，生成新個(gè)體[10-11]。

定義差分向量：

(2)

將差分向量加權(quán)后再加到第三個(gè)隨機(jī)選取的個(gè)體向量上就形成了變異向量：

(3)

式中，F(xiàn)為縮放因子，是[0,2]區(qū)間上的一個(gè)實(shí)常數(shù)，用于控制差分向量的縮放程度。

2.2 交叉操作

(4)

2.3 選擇操作

(5)

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

3 智能組卷程序流程

組卷問(wèn)題實(shí)質(zhì)是多重約束條件的最優(yōu)求解問(wèn)題，滿(mǎn)足條件的最優(yōu)解不惟一。計(jì)算機(jī)智能組卷是以數(shù)學(xué)模型為基礎(chǔ)進(jìn)行軟件開(kāi)發(fā)。

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

圖1 智能組卷程序流程圖

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

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

(6)

式中，rand[0,1]為[0,1]區(qū)間的均勻隨機(jī)數(shù)。

(7)

式中，ck表示試題k；k表示試題編號(hào)。

(4)計(jì)算個(gè)體適應(yīng)度值。適應(yīng)度是以數(shù)值的方式來(lái)評(píng)估個(gè)體向量相對(duì)于整個(gè)群體的優(yōu)劣程度的指標(biāo)。適應(yīng)度值的計(jì)算需要適應(yīng)度函數(shù)，也稱(chēng)評(píng)價(jià)函數(shù)。DE算法的適應(yīng)度函數(shù)不受連續(xù)可微的約束，可以任意設(shè)定區(qū)域，為了保證適應(yīng)性能好的個(gè)體被選擇的機(jī)會(huì)大，適應(yīng)度函數(shù)的取值必須非負(fù)，設(shè)計(jì)盡可能簡(jiǎn)單，使計(jì)算的時(shí)間復(fù)雜度最小。

(5)判斷是否滿(mǎn)足算法終止條件。最大進(jìn)化代數(shù)可作為DE的終止條件，還需要其他判定準(zhǔn)則。一般當(dāng)目標(biāo)函數(shù)值小于閾值時(shí)程序終止，閾值常選為10-6；或者通過(guò)判斷種群中的最優(yōu)值連續(xù)若干代并沒(méi)有明顯變化時(shí)，也可以作為終止條件。

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

4 結(jié)束語(yǔ)

智能組卷是大學(xué)英語(yǔ)考試自動(dòng)化的核心工作，如何保證生成的試卷最大程度地滿(mǎn)足考試需要，并具有隨機(jī)性、科學(xué)性、合理性等特點(diǎn)是實(shí)現(xiàn)過(guò)程中的難點(diǎn)。DE算法通過(guò)變異算子來(lái)探索新解，利用交叉算子進(jìn)行局部開(kāi)發(fā)，利用貪婪選擇策略進(jìn)行保優(yōu)，使種群向最優(yōu)區(qū)域靠攏。與其他算法相比，具有基本原理簡(jiǎn)單、受控參數(shù)少、魯棒性強(qiáng)、收斂性和穩(wěn)定性好等特點(diǎn)。依據(jù)文中的研究?jī)?nèi)容可以快速構(gòu)建適合于大學(xué)英語(yǔ)教學(xué)和考試的智能組卷系統(tǒng)。同時(shí)也必須注意，DE算法的理論基礎(chǔ)還比較貧乏，為了使智能組卷系統(tǒng)更科學(xué)合理，擴(kuò)展DE算法和其他算法相結(jié)合，是未來(lái)智能組卷算法的發(fā)展方向。

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

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

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

[4] 郭 鵬.差分進(jìn)化算法改進(jìn)研究[D].天津:天津大學(xué),2012.

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

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

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

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

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

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

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

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

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

[14] 魏玉霞.差分進(jìn)化算法的改進(jìn)及其應(yīng)用[D].廣州：華南理工大學(xué),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ìn)化算法馬爾可夫鏈模型及收斂性分析[J].計(jì)算機(jī)技術(shù)與發(fā)展,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

時(shí)間：2016-01-04

遼寧省教育科學(xué)“十二五”規(guī)劃項(xiàng)目(JG12DB243)

劉學(xué)豐(1970-)，女，副教授，碩士，研究方向?yàn)橛⒄Z(yǔ)教育信息化。

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