基于遺傳算法的自動(dòng)組卷模型及改進(jìn)研究

羅宇，羅曼，夏德奇

(中國(guó)氣象局氣象干部培訓(xùn)學(xué)院湖南分院，長(zhǎng)沙410125)

基于遺傳算法的自動(dòng)組卷模型及改進(jìn)研究

羅宇，羅曼，夏德奇

(中國(guó)氣象局氣象干部培訓(xùn)學(xué)院湖南分院，長(zhǎng)沙410125)

針對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)化慢、易早熟等問(wèn)題，建立多重約束目標(biāo)組合優(yōu)化模型，對(duì)編碼策略、種群初始化和遺傳算子進(jìn)行改進(jìn)。實(shí)驗(yàn)表明：相較于標(biāo)準(zhǔn)遺傳算法，改進(jìn)遺傳算法可明顯提升所得試卷的最大適應(yīng)度（0.79提升至0.84）和平均適應(yīng)度（0.74提升至0.83），改善早熟現(xiàn)象，提升算法執(zhí)行速度。

0 引言

在氣象教育培訓(xùn)領(lǐng)域，考試是培訓(xùn)過(guò)程中的重要環(huán)節(jié)。隨著計(jì)算機(jī)輔助教學(xué)技術(shù)迅速發(fā)展，智能組卷已成為一項(xiàng)被廣泛研究和實(shí)際應(yīng)用的課題。如何綜合考慮章節(jié)比例、題型比例、知識(shí)點(diǎn)覆蓋、試卷難度及區(qū)分度等多重約束條件，生成一套能夠評(píng)價(jià)學(xué)員知識(shí)和能力的試卷是組卷算法的核心問(wèn)題。目前傳統(tǒng)的組卷算法多為隨機(jī)組卷算法[1-3]或回溯試探組卷算法[4-5]。由于此類算法中的組卷模型存在成功率低、算法結(jié)構(gòu)復(fù)雜和組卷時(shí)間長(zhǎng)等問(wèn)題，不能很好滿足目前試題資源日益增長(zhǎng)現(xiàn)狀。基于仿生的遺傳算法（Generic Algo?rithm，GA）作為一種隨機(jī)搜索算法，可在潛在的解決方案中逐步求得近似的全局最優(yōu)解，其在組合優(yōu)化問(wèn)題求解領(lǐng)域得有較多應(yīng)用[6-7]。在此基礎(chǔ)上許多學(xué)者嘗試?yán)眠z傳算法解決自動(dòng)組卷問(wèn)題，取得較好效果。相關(guān)研究表明，引入遺傳算法可顯著改善組卷效率和質(zhì)量[8-11]。但由于其算法本身缺陷，可能導(dǎo)致組卷算法出現(xiàn)早熟、后期搜索效率低甚至組卷失敗等問(wèn)題[12]。

本文采用多重約束目標(biāo)組合優(yōu)化模型，對(duì)題型分布、難度系數(shù)、區(qū)分度、章節(jié)分值等約束條件進(jìn)行量化，實(shí)現(xiàn)自動(dòng)組卷問(wèn)題數(shù)學(xué)建模。同時(shí)采用基于試卷的分組編碼策略、均勻化初始種群和自適應(yīng)遺傳算子[13-14]，改進(jìn)標(biāo)準(zhǔn)遺傳算法在自動(dòng)組卷應(yīng)用上的不足，實(shí)現(xiàn)算法優(yōu)化。

1 自動(dòng)組卷算法數(shù)學(xué)建模

自動(dòng)組卷時(shí)，需從題庫(kù)中抽取一組試題P，使其屬性變量A（題型、難度、區(qū)分度、分值、所屬章節(jié)及知識(shí)點(diǎn)等）在對(duì)應(yīng)取值范圍V內(nèi)滿足約束條件R，即將自動(dòng)組卷抽象為多重約束目標(biāo)組合優(yōu)化問(wèn)題。本文中選取知識(shí)點(diǎn)、難度、區(qū)分度和所屬章節(jié)4個(gè)屬性加以量化，并結(jié)合對(duì)應(yīng)約束條件構(gòu)造適應(yīng)度函數(shù)。

知識(shí)點(diǎn)屬性涉及試題的具體考核內(nèi)容。令Ktotal為題庫(kù)知識(shí)點(diǎn)總數(shù)，K為試卷中不重復(fù)知識(shí)點(diǎn)數(shù)量和，n為試卷中題目總數(shù)，定義知識(shí)點(diǎn)適應(yīng)度函數(shù)：

難度屬性反映試題難易程度，對(duì)應(yīng)取值范圍為[0，1]。對(duì)于客觀性試題，難度計(jì)算方法為：

對(duì)于主觀題，難度計(jì)算方法為：

其中，M為考生總數(shù)，mj為答對(duì)第j題人數(shù)，xij為第i位考生在第j題上的得分，wj為第j題的滿分分值。令β為組卷期望難度，采用正態(tài)分布建立難度適應(yīng)度函數(shù)：

區(qū)分度屬性指試題對(duì)被試者情況的分辨能力的大小，反映試題區(qū)分不同水平受試者的程度，其計(jì)算方法為：

試題所屬章節(jié)一般由考綱中各章節(jié)題目分值確定。假設(shè)題庫(kù)中試題共涉及N個(gè)章節(jié)，考綱中各章節(jié)所占分值為Sj，組卷生成試卷中各章節(jié)分值為sj，其適應(yīng)度函數(shù)可有正態(tài)分布建立：

由上述定義的目標(biāo)函數(shù)可知，自動(dòng)組卷所得試卷的各項(xiàng)屬性和屬性的期望值偏差越小，所得目標(biāo)函數(shù)值越大。因此組卷算法的多目標(biāo)優(yōu)化即在綜合考慮知識(shí)點(diǎn)、難度、區(qū)分度和所屬章節(jié)4個(gè)約束條件下，求得總的適應(yīng)度函數(shù)：

其中wi為各屬性適應(yīng)度函數(shù)的權(quán)重，滿足其具體取值，可根據(jù)不同考試需求進(jìn)行設(shè)置。由各屬性目標(biāo)函數(shù)定義可知，F(xiàn)(x)∈(0 ,1)，其取值越大意味著組卷生成的試卷質(zhì)量越好。

2 算法設(shè)計(jì)

2.1 面向試卷的實(shí)數(shù)分段編碼策略

編碼策略是應(yīng)用遺傳算法時(shí)需解決的首要問(wèn)題，也是設(shè)計(jì)遺傳算法是的關(guān)鍵步驟之一。不同的編碼方式會(huì)影響交叉、變異等遺傳算子的運(yùn)算方式，進(jìn)而決定算法進(jìn)化效率。在自動(dòng)組卷應(yīng)用中，標(biāo)準(zhǔn)遺傳算法一般采用面向題庫(kù)的二進(jìn)制編碼策略[9-10]，即題庫(kù)中某一題選中時(shí)表示為1，未選中表示為0。該編碼策略操作簡(jiǎn)單、易于理解、搜索效率高，但在進(jìn)化過(guò)程中，不易控制各題型的數(shù)量比例，導(dǎo)致組卷算法失敗或過(guò)早收斂。且采用二進(jìn)制編碼策略時(shí)，組卷算法的搜索空間取決于題庫(kù)大小，若題庫(kù)較大，會(huì)導(dǎo)致搜索空間過(guò)大，極大影響進(jìn)化后期搜索效率。

為解決上述不足，采用面向試卷的實(shí)數(shù)分段編碼策略，將一份試卷映射成一條染色體，每一被選中的試題對(duì)應(yīng)染色體上的一個(gè)基因，其編碼直接利用其在題庫(kù)中的編號(hào)表示。同時(shí)根據(jù)試卷對(duì)題型的要求，將染色體上基因分段，每段對(duì)應(yīng)一類題型（圖1）。考慮到同一題型試題分值一般相同，采用該編碼策略可以很好滿足試卷對(duì)總分和各題型數(shù)量的要求，簡(jiǎn)化約束條件和算法流程。基因段之間相互獨(dú)立，確保初始化、交叉和變異等遺傳操作在不同試卷的相同基因段內(nèi)進(jìn)行（圖2，加粗邊框內(nèi)為交叉部分），保證進(jìn)化所得的各染色體中各題型數(shù)量和總分正確匹配，避免非法解對(duì)算法搜索效率的影響。

圖1 面向試卷的實(shí)數(shù)分段編碼

圖2 不同試卷間的交叉操作

2.2 優(yōu)化初始種群

初始種群的特性會(huì)明顯影響算法結(jié)果和效率。標(biāo)準(zhǔn)遺傳算法一般采用隨機(jī)方法生成初始化群體，容易造成解空間過(guò)大，進(jìn)化迭代次數(shù)過(guò)多，組卷結(jié)果較難把握。

針對(duì)上述問(wèn)題，在面向試卷的實(shí)數(shù)分段編碼策略基礎(chǔ)上，采取不放回抽樣方法使初始種群所處解空間盡量分散，并優(yōu)化初始種群適應(yīng)度。即對(duì)于大小為m的初始種群，隨機(jī)產(chǎn)生n組染色體，計(jì)算各染色體總體適應(yīng)度，保留適應(yīng)度最大的作為初始染色體，并循環(huán)m次產(chǎn)生初始種群。該方法在不顯著增加種群初始化復(fù)雜度的情況下可明顯加快遺傳算法收斂速度，減少迭代次數(shù)，增強(qiáng)進(jìn)化效率。

2.3 自適應(yīng)遺傳算子

交叉和變異是遺傳算法的重要步驟，交叉概率（Pc）和遺傳概率（Pm）對(duì)算法性能有決定性影響[13-14]。標(biāo)準(zhǔn)遺傳算法一般使用固定的Pc和Pm，以便在進(jìn)化初期快速篩選掉適應(yīng)度較差的個(gè)體，進(jìn)而提升種群的平均適應(yīng)度。但在進(jìn)化后期，固定概率容易破化較優(yōu)解，降低種群差異性，使算法陷入局部最優(yōu)解，出現(xiàn)早熟現(xiàn)象。

為改善上述不足，在進(jìn)化過(guò)程中采用自適應(yīng)機(jī)制，根據(jù)各代的適應(yīng)度情況，對(duì)Pc和Pm進(jìn)行動(dòng)態(tài)調(diào)整。對(duì)于適應(yīng)度較高的個(gè)體，對(duì)應(yīng)較低的Pc和Pm，使其更易進(jìn)入下一代繼續(xù)進(jìn)化；對(duì)于適應(yīng)度較低的個(gè)體，對(duì)應(yīng)較高的Pc和Pm，使其更容易在交叉變異中重組基因，進(jìn)而克服早熟，并提高搜索效率。自適應(yīng)算子采用線性函數(shù)：

式中 f為個(gè)體適應(yīng)度，fm和 fa分別為群體最大適應(yīng)度和平均適應(yīng)度，k1和k2為系數(shù)，可根據(jù)不同問(wèn)題靈活取值。同時(shí)，為進(jìn)一步加快算法收斂速度，在進(jìn)化過(guò)程中用適應(yīng)度最好的個(gè)體替換適應(yīng)度最差個(gè)體，便于更優(yōu)個(gè)體基因遺傳到下一代。

3 實(shí)驗(yàn)與分析

參照《地面氣象觀測(cè)人員上崗資格考試大綱（2013）》，構(gòu)造模擬題庫(kù)對(duì)標(biāo)準(zhǔn)遺傳算法（standard ge?netic algorithm，SGA）和改進(jìn)遺傳算法（improved genetic algorithm，IGA）進(jìn)行實(shí)驗(yàn)。題庫(kù)包括6章內(nèi)容，涉及120個(gè)知識(shí)點(diǎn)，其中填空題1792道，單項(xiàng)選擇題2145道，多項(xiàng)選擇題670道，名詞解釋題112道，簡(jiǎn)答題156道。組卷要求：總分 100，各章分值為{8，14，50，10，10，8}，各題型分值為{23，35，20，6，16}；試卷難度 0.6，區(qū)分度0.6，知識(shí)點(diǎn)、難度、區(qū)分度和所屬章節(jié)4個(gè)約束條件權(quán)重分別為{0.15，0.35，0.35，0.15}。標(biāo)準(zhǔn)遺傳算法交叉概率為0.5，變異概率為0.005，自適應(yīng)算子系數(shù)依次分別為0.5和0.005，初始種群規(guī)模為50，最大進(jìn)化代數(shù)為500。標(biāo)準(zhǔn)遺傳算法和改進(jìn)遺傳算法組卷最大適應(yīng)度和平均適應(yīng)度對(duì)比分別如圖3和圖4所示。由圖可知，在初始種群相同，進(jìn)化代數(shù)同為500的情況下，改進(jìn)遺傳算法最終所得最大適應(yīng)度和平均適應(yīng)度分別為0.85和0.83，均高于標(biāo)準(zhǔn)遺傳算法（0.79和0.74），說(shuō)明改進(jìn)遺傳算法不僅近似最優(yōu)解優(yōu)于標(biāo)準(zhǔn)遺傳算法，且所得種群總體質(zhì)量明顯更優(yōu)。同時(shí)，標(biāo)準(zhǔn)遺傳算法進(jìn)化速度相較改進(jìn)遺傳算法慢（表1），且在適應(yīng)度達(dá)到某一局部最優(yōu)解之后基本停止進(jìn)化，陷入早熟。

圖3 SGA和IGA組卷最大適應(yīng)度對(duì)比

圖4 SGA和IGA組卷平均適應(yīng)度對(duì)比

表1 SGA和IGA不同進(jìn)化代數(shù)時(shí)最大適應(yīng)度對(duì)比

4 結(jié)語(yǔ)

針對(duì)標(biāo)準(zhǔn)遺傳算法易早熟、收斂速度慢等不足，本文對(duì)組卷問(wèn)題基于多重約束目標(biāo)組合優(yōu)化建模后，提出一種綜合利用基于試卷的分組編碼策略、均勻化初始種群和自適應(yīng)遺傳算子的改進(jìn)遺傳算法。實(shí)驗(yàn)表明，相較于標(biāo)準(zhǔn)遺傳算法，改進(jìn)遺傳算法可明顯改善組卷質(zhì)量，克服早熟問(wèn)題，提升搜索效率。目前該算法已應(yīng)用于湖南省氣象教育培訓(xùn)考試系統(tǒng)，體現(xiàn)出很好的穩(wěn)定性和實(shí)用性。

[1]應(yīng)繼儒,胡立新,龍毅.試題庫(kù)隨機(jī)抽選數(shù)學(xué)模型的構(gòu)建與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用,2000,20（1）:46-47.

[2]王萌,金漢均,王曉榮.集合隨機(jī)抽選法在智能組卷中的研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2006,27（19）:3583-3585.

[3]謝深泉,胡寧?kù)o.數(shù)據(jù)庫(kù)設(shè)計(jì)和自動(dòng)組卷中的幾個(gè)問(wèn)題[J].湘潭大學(xué)自然科學(xué)學(xué)報(bào),2002,24（3）:27-31.

[4]李靜梅,李靜,焦平.一種可調(diào)整式的多元變量漸近尋優(yōu)組卷策略[J].應(yīng)用科技,2009,36（10）:53-57.

[5]龔?fù)耆?基于最小回溯代價(jià)的只能組卷算法[D].湖南:湖南大學(xué)軟件學(xué)院,2005.

[6]Xing Huanlai,Qu Rong.A Compact Genetic Algorithm for the Network Coding Based Resource Minimization Problem[J].Applied Intelligence,2012,36（4）:809-823.

[7]Xing Huanlai,Qu Rong.A Nondominated Sorting Genetic Algorithm for Bi-Objective Network Coding Based Multicast Routing Problems[J].Information Sciences,2013,233（6）:36-53.

[8]毛秉毅.基于遺傳算法的智能組卷系統(tǒng)數(shù)據(jù)庫(kù)結(jié)構(gòu)的研究[J].計(jì)算機(jī)工程與應(yīng)用,2003,28（6）:230-232.

[9]李軍.基于遺傳算法的智能組卷系統(tǒng)研究[D].天津:天津大學(xué),2008.

[10]梁興建.程序設(shè)計(jì)類大學(xué)課程的智能組卷策略研究[D].成都:電子科技大學(xué),2009.

[11]韋大歡.改進(jìn)型遺傳算法智能組卷系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].軟件,2011,32（10）:35-37,43.

[12]付旭輝,康玲.遺傳算法的早熟問(wèn)題探究[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版）,2003,31（7）:53-54.

[13]吳浩揚(yáng),朱長(zhǎng)純,常炳鍋,等.基于種群過(guò)早收斂程度定量分析的改進(jìn)自適應(yīng)遺傳算法[J].西安交通大學(xué)學(xué)報(bào),1999,33（11）:27-30.

[14]曲志堅(jiān),張先偉,曹雁鋒,等.基于自適應(yīng)機(jī)制的遺傳算法研究[J].計(jì)算機(jī)應(yīng)用研究,2015,32（11）:3222-3225,3229.

羅宇（1984-），男，四川巴中人，工程師，碩士，研究方向?yàn)榇髿膺b感與探測(cè)

羅曼（1986-），女，湖南長(zhǎng)沙人，助理工程師，碩士，研究方向?yàn)闅庀蠼逃嘤?xùn)技術(shù)

夏德奇（1965-），男，湖南邵陽(yáng)人，副高級(jí)工程師，本科，研究方向?yàn)閼?yīng)用氣象

2017-06-20

2017-10-10

Automatic Test Paper Generation;Genetic Algorithm;Multi-Objective Optimization;Adaptive

Research on the Application and Improvement of Automatic Test Paper Generation Based on Genetic Algorithm

LUO Yu,LUO Man,XIA De-qi

（China Meteorological Training Center Hunan Branch,Changsha 410125）

In order to solve the problems of slow evolution and premature convergence in standard genetic algorithm,presents an improved genetic al?gorithm based on multi-objective optimization model through modified gene coding,population initialization and genetic operators.The ex?perimental results indicate that the improved genetic algorithm can achieve better synthesized execution speed,as well as promotes better max fitness(0.79 to 0.84)and average fitness(0.74 to 0.83)of test papers than standard genetic algorithm.

自動(dòng)組卷；遺傳算法；多目標(biāo)優(yōu)化；自適應(yīng)

湖南省氣象局重點(diǎn)科研課題（No.XQKJ15A006）、中國(guó)氣象局氣象干部培訓(xùn)學(xué)院科研項(xiàng)目（內(nèi)2014-012）

1007-1423（2017）29-0020-04

10.3969/j.issn.1007-1423.2017.29.005