王文星， 趙新慧

(遼寧石油化工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院, 遼寧 撫順 113001)

基于遺傳算法的組卷技術(shù)研究與改進(jìn)

王文星， 趙新慧

(遼寧石油化工大學(xué) 計(jì)算機(jī)與通信工程學(xué)院, 遼寧 撫順 113001)

優(yōu)化了自動(dòng)組卷的約束條件，并針對(duì)知識(shí)點(diǎn)的考核層次問題進(jìn)行了算法改進(jìn)。在初始化種群時(shí)使用知識(shí)點(diǎn)權(quán)重分級(jí)表，按知識(shí)點(diǎn)權(quán)重順序來(lái)選取試題生成初始種群中的染色體，使種群從最初時(shí)起就滿足對(duì)知識(shí)點(diǎn)的考核層次要求，并在遺傳算子的設(shè)計(jì)中保持了種群知識(shí)點(diǎn)的穩(wěn)定性。結(jié)果表明，改進(jìn)算法在保證知識(shí)點(diǎn)覆蓋率的同時(shí)，能提高重要知識(shí)點(diǎn)的覆蓋率。

自動(dòng)組卷； 遺傳算法； 知識(shí)點(diǎn)權(quán)重； 考核層次

計(jì)算機(jī)自動(dòng)組卷技術(shù)減輕了試卷命題人負(fù)擔(dān)，并且提高了試卷的質(zhì)量和科學(xué)性。目前計(jì)算機(jī)自動(dòng)組卷方法有隨機(jī)抽題法[1]、回溯法[2]和遺傳算法[3-4]等。隨機(jī)抽題法簡(jiǎn)單，但具有很大的隨意性和不確定性[5]；回溯法適用于狀態(tài)類型和試題量比較小的情況；遺傳算法模擬生物進(jìn)化過(guò)程搜索最優(yōu)解，適用于處理傳統(tǒng)搜索方法難以解決的非線性、多約束的復(fù)雜問題[5]，在自動(dòng)組卷方面應(yīng)用廣泛。經(jīng)驗(yàn)表明，約束條件越多，自動(dòng)組卷的效率就越低[6]。自動(dòng)組卷遺傳算法研究主要關(guān)注點(diǎn)在約束條件優(yōu)化上[7-8]，或只考慮知識(shí)點(diǎn)的均勻分布但未考慮知識(shí)點(diǎn)的考核層次[1,9]。文獻(xiàn)[10]要求人為指定知識(shí)點(diǎn)分配的分值，文獻(xiàn)[11]指定不同考核層次占用的分值，增加了人工干預(yù)并且?guī)в腥藶橹饔^性。文獻(xiàn)[12]使用了知識(shí)點(diǎn)分級(jí)帶權(quán)重選取策略解決知識(shí)點(diǎn)的考核層次問題，不過(guò)選取結(jié)果過(guò)于均勻，重點(diǎn)不夠突出，而且計(jì)算方法和知識(shí)點(diǎn)數(shù)量有關(guān)。本文優(yōu)化了自動(dòng)組卷約束條件，并針對(duì)知識(shí)點(diǎn)的考核層次問題對(duì)遺傳算法進(jìn)行改進(jìn)。

1 試卷的數(shù)學(xué)模型

1.1 試題屬性定義

組卷要考慮的因素有試卷難度、試卷區(qū)分度、題型、試題曝光度、知識(shí)點(diǎn)覆蓋率和考核層次等。同時(shí)，對(duì)試卷還有一些特別的要求，如試卷中不能出現(xiàn)與上次試卷相同的試題，如果有A、B卷的話，也不能有重復(fù)試題。組卷涉及的條件很多，有些條件需嚴(yán)格滿足要求，有些條件特殊情況才會(huì)用到。為提高組卷成功率及速度，可對(duì)這些條件進(jìn)行取舍或優(yōu)化。一般的考試，在組卷時(shí)考試題型、各題型試題分和試題數(shù)量是可以確定的。用題量來(lái)控制卷面分和答題時(shí)間，就可以不用考慮總分約束和時(shí)間約束問題。最終優(yōu)化的試題屬性如下。

(1)編號(hào)：唯一標(biāo)識(shí)一道試題。

(2)知識(shí)點(diǎn)：試題考核的知識(shí)點(diǎn)。

(3)難度：代表一道試題的難易程度，劃分為5個(gè)等級(jí)(易、較易、中等、較難和難，對(duì)應(yīng)數(shù)字為1、2、3、4、5)。

(4)區(qū)分度：對(duì)考生水平區(qū)分程度的指標(biāo)，并不是與難度成正比。

(5)曝光度：試題被選中的次數(shù)。

(6)分值：試題的分值。

(7)最后使用時(shí)間：試題最后一次被選中的時(shí)間。

1.2 試卷的數(shù)學(xué)模型

將1份試卷映射為1個(gè)矩陣，組成試卷的每個(gè)試題映射為1個(gè)行向量。設(shè)每份試卷有n道試題，每題有如上定義的7個(gè)屬性，那么一張?jiān)嚲砭涂梢员硎緸榫仃嘢：

目標(biāo)矩陣S需要滿足以下約束條件：

1.3 組卷的目標(biāo)函數(shù)

矩陣S需要滿足用戶對(duì)試卷的要求。在定制試卷時(shí)，用戶提供期望的題型、各題型試題的分?jǐn)?shù)、各題型的題量、試卷難度及區(qū)分度。用fi表示屬性與屬性期望值之間的誤差，為反映各屬性的不同重要程度，目標(biāo)函數(shù)f取各誤差的加權(quán)和：

(1)

由式(1)可知，為了得到最優(yōu)解，f的值越小越好。

2 組卷遺傳算法改進(jìn)

2.1 染色體編碼

染色體編碼是由問題空間向遺傳算法空間的映射。在組卷題量大時(shí)二進(jìn)制編碼染色體長(zhǎng)度過(guò)長(zhǎng)，從而降低組卷效率，因此使用染色體分段實(shí)數(shù)編碼。1份試卷對(duì)應(yīng)1個(gè)染色體，試題號(hào)作為染色體中基因的值，試卷中每道題的題號(hào)對(duì)應(yīng)1個(gè)基因，染色體中基因按題型分段。

設(shè)試卷共有n道試題，k種題型，按題型將n道試題分成k段，每段代表1種題型。若第r(r=1,2,…,k)類題型包含的試題數(shù)目為ri，則染色體為：

sn1(1)sn2(2)…sn1(r1)sn2(1)sn2(2)…

sn2(r2)…snk(1)snk(2) …snk(rk)

(2)

2.2 適應(yīng)度函數(shù)

試卷中各種題型的數(shù)量、分值和考核知識(shí)點(diǎn)是在初始化種群時(shí)處理，設(shè)置適應(yīng)度函數(shù)需要處理的約束包括試題難度、試題區(qū)分度和試題曝光度。所以，適應(yīng)度函數(shù)直接由目標(biāo)函數(shù)轉(zhuǎn)化得到。

2.3 初始化種群

根據(jù)用戶設(shè)定的各種題型的數(shù)量、分值和考核知識(shí)點(diǎn)生成初始種群。另外，引入知識(shí)點(diǎn)權(quán)重表，在保證知識(shí)點(diǎn)覆蓋率的同時(shí)，加強(qiáng)對(duì)重要知識(shí)點(diǎn)的考核。

2.3.1 知識(shí)點(diǎn)權(quán)重分級(jí)表的創(chuàng)建 在教學(xué)大綱中都會(huì)規(guī)定每個(gè)知識(shí)點(diǎn)的考核要求，如“了解、理解、掌握和熟練掌握”。在考核時(shí)應(yīng)該優(yōu)先考核“熟練掌握”和“掌握”的知識(shí)點(diǎn)。在自動(dòng)組卷時(shí)，應(yīng)該能優(yōu)先選擇重要的知識(shí)點(diǎn)，不用每次組卷時(shí)人工指定。為此，需要?jiǎng)?chuàng)建一個(gè)知識(shí)點(diǎn)權(quán)重表，在選擇試題時(shí)，優(yōu)先選擇知識(shí)點(diǎn)權(quán)重大的試題，這樣就可以加強(qiáng)對(duì)重要知識(shí)點(diǎn)的考核。

為了避免出現(xiàn)由于知識(shí)點(diǎn)密度大而導(dǎo)致的題目相似度高的情況，實(shí)現(xiàn)組卷時(shí)知識(shí)點(diǎn)考核的均勻分布，對(duì)各章的知識(shí)點(diǎn)進(jìn)行分級(jí)組織。首先按大類劃分若干一級(jí)知識(shí)點(diǎn)，然后在一級(jí)知識(shí)點(diǎn)下再劃分若干二級(jí)知識(shí)點(diǎn)。在選擇知識(shí)點(diǎn)時(shí)，先選擇一級(jí)再選擇二級(jí)。二級(jí)知識(shí)點(diǎn)的權(quán)重直接按大綱要求指定，假設(shè)考核層次為“了解、理解、掌握和熟練掌握”，則相應(yīng)權(quán)重可設(shè)置為1、2、3、4。一級(jí)知識(shí)點(diǎn)權(quán)重由其包含的二級(jí)知識(shí)點(diǎn)權(quán)重生成，原則上一級(jí)知識(shí)點(diǎn)權(quán)重要能體現(xiàn)其二級(jí)知識(shí)點(diǎn)的最高權(quán)重；一級(jí)知識(shí)點(diǎn)權(quán)重要與其二級(jí)知識(shí)點(diǎn)的數(shù)量有關(guān)。因此，本文定義一級(jí)知識(shí)點(diǎn)權(quán)重計(jì)算公式為：

(3)

式中，xi為第i個(gè)知識(shí)點(diǎn)的權(quán)重；ki為加權(quán)系數(shù)(放大權(quán)重值差距)。

根據(jù)式(3)可創(chuàng)建課程的知識(shí)點(diǎn)權(quán)重分級(jí)表，對(duì)一級(jí)知識(shí)點(diǎn)和二級(jí)知識(shí)點(diǎn)按權(quán)重分別降序排序。

2.3.2 初始化種群算法 根據(jù)用戶指定的題型、題數(shù)和題分，使用知識(shí)點(diǎn)權(quán)重分級(jí)表，按知識(shí)點(diǎn)權(quán)重順序來(lái)生成初始種群，算法如下：

步驟1 根據(jù)題型k和試題數(shù)n生成試卷染色體結(jié)構(gòu)(k段共n個(gè)基因)；

步驟3 為了避免因知識(shí)點(diǎn)序列固定而導(dǎo)致高分值試題考核知識(shí)點(diǎn)可預(yù)測(cè)，對(duì)試卷知識(shí)點(diǎn)表中前t(t為高分值試題數(shù)量)個(gè)知識(shí)點(diǎn)進(jìn)行混排；

步驟4 依次從試卷知識(shí)點(diǎn)表中取出知識(shí)點(diǎn)，按照染色體中基因題分降序順序，為染色體中基因分配取出的知識(shí)點(diǎn)；

步驟5 根據(jù)染色體基因所分配的知識(shí)點(diǎn)和題型信息，為染色體中所有基因隨機(jī)選擇一道符合知識(shí)點(diǎn)和題型要求并滿足最后使用時(shí)間限制要求的試題；

步驟6 重復(fù)步驟4和步驟5，直到生成指定數(shù)量的試卷染色體種群。

2.4 遺傳算子的設(shè)計(jì)

2.4.1 選擇算子 為提高種群進(jìn)化的效率，采用將前10%的優(yōu)良個(gè)體直接選擇進(jìn)入下一代，剩余個(gè)體采用輪盤賭的選擇策略。

2.4.2 交叉算子 采用分段單點(diǎn)交叉方法：種群中的染色體任意兩兩配對(duì)；給每對(duì)染色體生成1個(gè)[0,N-2]的隨機(jī)數(shù)r，將r后的兩道題互換，得到下一代。交叉后生成的子代有可能會(huì)出現(xiàn)重復(fù)的題號(hào)問題，解決方法是將重復(fù)的題號(hào)換成具有相同知識(shí)點(diǎn)并且在該段中沒有出現(xiàn)過(guò)的題號(hào)。

2.4.3 變異算子 采用分段變異操作，即各題型在各自分段內(nèi)進(jìn)行變異，基本步驟為：對(duì)種群中的每個(gè)個(gè)體生成1個(gè)長(zhǎng)度為n的隨機(jī)數(shù)列R={r1,r2,…,rn}，其中ri為隨機(jī)產(chǎn)生的[0,1]的實(shí)數(shù)。對(duì)每個(gè)個(gè)體的第i個(gè)基因位置上的基因，如果ri≥Pm(Pm為變異閾值)，保持該基因不變，否則進(jìn)行變異操作，選擇1個(gè)本段中沒有的題號(hào)并和原試題具有相同知識(shí)點(diǎn)和題型的試題替換原試題。

2.4.4 終止條件 遺傳算法需要多次迭代，其解盡可能接近最優(yōu)解，終止條件為產(chǎn)生適應(yīng)度達(dá)到指定要求的個(gè)體或達(dá)到指定的迭代次數(shù)。滿足條件之一算法終止。

3 算法測(cè)試

為了驗(yàn)證改進(jìn)算法，進(jìn)行如下測(cè)試：

(1)測(cè)試條件。題庫(kù)中共有5類題型：程序題、簡(jiǎn)答題、多選題、單選題和判斷題，共1 200道試題，包括21個(gè)一級(jí)知識(shí)點(diǎn)和65個(gè)二級(jí)知識(shí)點(diǎn)?！傲私狻⒗斫?、掌握和熟練掌握”各權(quán)重的二級(jí)知識(shí)點(diǎn)總數(shù)為17、22、13、13。

(2)參數(shù)設(shè)置。試卷總分100分，試卷難度0.3，試卷區(qū)分度0.5，試卷曝光度取題庫(kù)中所有試題的曝光度平均值，試卷中5類題型數(shù)量分別為3、5、10、20、10，分?jǐn)?shù)比例分別為3∶2∶2∶2∶1，一級(jí)知識(shí)點(diǎn)權(quán)重計(jì)算公式中取ki= (xi+1)/2，初始種群規(guī)模50，種群數(shù)量24，最大迭代次數(shù)100，變異概率0.005，適應(yīng)度函數(shù)中ω1=0.5、ω2=0.3、ω3=0.2。測(cè)試結(jié)果如表1所示。

表1 算法測(cè)試結(jié)果

注：各權(quán)重知識(shí)點(diǎn)的包含比例為試卷包含的各權(quán)重知識(shí)點(diǎn)數(shù)量與各權(quán)重知識(shí)點(diǎn)總數(shù)之比。

從表1可以看出，本文算法可以在保證知識(shí)點(diǎn)覆蓋面的同時(shí)，提高重要知識(shí)點(diǎn)的覆蓋率。各權(quán)重知識(shí)點(diǎn)的選取比例比較合理，權(quán)重高的知識(shí)點(diǎn)比權(quán)重低的知識(shí)點(diǎn)的覆蓋率更高。

此外，通過(guò)設(shè)置不同題型和試題數(shù)量，進(jìn)行多次測(cè)試。當(dāng)試卷題量減少時(shí)，權(quán)重低的知識(shí)點(diǎn)的覆蓋率減少的更快，而權(quán)重高的知識(shí)點(diǎn)覆蓋率減少的相對(duì)緩慢，保證了試卷對(duì)重要知識(shí)點(diǎn)的考核力度。

4 結(jié) 論

自動(dòng)組卷技術(shù)是計(jì)算機(jī)輔助教學(xué)中的一項(xiàng)重要技術(shù)。其中知識(shí)點(diǎn)考核不但要求覆蓋率大而且要優(yōu)先考核重要的知識(shí)點(diǎn)。對(duì)自動(dòng)組卷約束條件進(jìn)行優(yōu)化，在知識(shí)點(diǎn)的考核層次問題上進(jìn)行了算法改進(jìn)。結(jié)果表明，改進(jìn)算法在保證知識(shí)點(diǎn)覆蓋率的同時(shí)，提高了對(duì)重要知識(shí)點(diǎn)的覆蓋率。

[1] 金漢均，鄭世玨，吳明武．分段隨機(jī)抽取選法在智能組卷中的研究與應(yīng)用[J]．計(jì)算機(jī)應(yīng)用研究,2003,20(9):102-103.

[2] Chen L H，Mei Y D，Dong Y J，et al．Improved genetic algorithmand its application in optimal dispatch of eas-cade reservoirs[J].Journal of Hydraulic Engineering，2008，38(5)：550-556．

[3] 黃寶玲．自適應(yīng)遺傳算法在智能組卷中的應(yīng)用[J]．計(jì)算機(jī)工程，2011，37(14)：161-163．

[4] 梁亞瀾，聶長(zhǎng)海．覆蓋表生成的遺傳算法配置參數(shù)優(yōu)化[J]．計(jì)算機(jī)學(xué)報(bào)，2012，35(7)：1522-1538．

[5] 朱婧，戴青云，王美林，等. 自適應(yīng)遺傳算法在工程訓(xùn)練在線考試中的應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用,2013,49(14):227-230.

[6] Wang L, Tang D. An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem[J]. Expert Systems with Applications，2011，38(6)：7243-7250．

[7] 陳國(guó)彬，張廣泉. 基于改進(jìn)遺傳算法的快速自動(dòng)組卷算法研究[J]. 計(jì)算機(jī)應(yīng)用研究,2015,32(10):2996-2998.

[8] 張琨，楊會(huì)菊，宋繼紅，等. 基于遺傳算法的自動(dòng)組卷系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與科學(xué),2012,34(5):178-183.

[9] 魯萍，王玉英. 多約束分級(jí)尋優(yōu)結(jié)合預(yù)測(cè)計(jì)算的智能組卷策略[J]. 計(jì)算機(jī)應(yīng)用,2013,33(2):342-345.

[10] 賀榮，陳爽. 在線組卷策略的研究與設(shè)計(jì)[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2011,32(6):2183-2186.

[11] 任劍，卞燦，全惠云．基于層次分析方法與人工魚群算法的智能組卷[J].計(jì)算機(jī)應(yīng)用研究，2010，27(4)：1293-1296.

[12] 魯萍，何宏璧，王玉英. 智能組卷中分級(jí)帶權(quán)重知識(shí)點(diǎn)選取策略[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(3):67-69.

Research and Improvement of Test Paper ConstructionTechnology Based on Genetic Algorithm

Wang Wenxing, Zhao Xinhui

(SchoolofComputerandCommunicationEngineering，LiaoningShihuaUniversity，F(xiàn)ushunLiaoning113001，China)

The constraints of automatic test paper are optimized, and the algorithm is improved according to the examination hierarchy of knowledge points . The knowledge points weight grading table is used when initializing the population , and the chromosomes in the initial population are selected according to the knowledge weight order so that the population can meet the requirement of the assessment level of the knowledge points from the initial time. In the design of the genetic operators maintains the stability of the population of knowledge point .The results show that the improved algorithm can improve the coverage rate of important knowledge points while guaranteeing the coverage of knowledge points.

Automatic test paper generation; Genetic algorithms; Knowledge point weight; Assessment level

2017-06-09

2017-07-04

2016年國(guó)家級(jí)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目(201610148052)。

王文星(1995-)，男，本科生，軟件工程專業(yè)，從事軟件工程方面研究；E-mail：864862094@qq.com。

趙新慧(1973-)，男，碩士，副教授，從事軟件工程、智能信息處理等方面研究；E-mail：zhaoxinhui2002@163.com。

1672-6952(2017)06-0056-04

投稿網(wǎng)址：http://journal.lnpu.edu.cn

TP311.52

A

10.3969/j.issn.1672-6952.2017.06.012

(編輯 陳 雷)