基于遺傳算法的組卷技術研究與改進

王文星， 趙新慧

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

基于遺傳算法的組卷技術研究與改進

王文星， 趙新慧

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

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

自動組卷； 遺傳算法； 知識點權重； 考核層次

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

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

1.1 試題屬性定義

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

(1)編號：唯一標識一道試題。

(2)知識點：試題考核的知識點。

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

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

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

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

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

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

將1份試卷映射為1個矩陣，組成試卷的每個試題映射為1個行向量。設每份試卷有n道試題，每題有如上定義的7個屬性，那么一張試卷就可以表示為矩陣S：

目標矩陣S需要滿足以下約束條件：

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

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

(1)

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

2 組卷遺傳算法改進

2.1 染色體編碼

染色體編碼是由問題空間向遺傳算法空間的映射。在組卷題量大時二進制編碼染色體長度過長，從而降低組卷效率，因此使用染色體分段實數(shù)編碼。1份試卷對應1個染色體，試題號作為染色體中基因的值，試卷中每道題的題號對應1個基因，染色體中基因按題型分段。

設試卷共有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 適應度函數(shù)

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

2.3 初始化種群

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

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

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

(3)

式中，xi為第i個知識點的權重；ki為加權系數(shù)(放大權重值差距)。

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

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

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

步驟3 為了避免因知識點序列固定而導致高分值試題考核知識點可預測，對試卷知識點表中前t(t為高分值試題數(shù)量)個知識點進行混排；

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

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

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

2.4 遺傳算子的設計

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

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

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

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

3 算法測試

為了驗證改進算法，進行如下測試：

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

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

表1 算法測試結果

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

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

此外，通過設置不同題型和試題數(shù)量，進行多次測試。當試卷題量減少時，權重低的知識點的覆蓋率減少的更快，而權重高的知識點覆蓋率減少的相對緩慢，保證了試卷對重要知識點的考核力度。

4 結 論

自動組卷技術是計算機輔助教學中的一項重要技術。其中知識點考核不但要求覆蓋率大而且要優(yōu)先考核重要的知識點。對自動組卷約束條件進行優(yōu)化，在知識點的考核層次問題上進行了算法改進。結果表明，改進算法在保證知識點覆蓋率的同時，提高了對重要知識點的覆蓋率。

[1] 金漢均，鄭世玨，吳明武．分段隨機抽取選法在智能組卷中的研究與應用[J]．計算機應用研究,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] 黃寶玲．自適應遺傳算法在智能組卷中的應用[J]．計算機工程，2011，37(14)：161-163．

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

[5] 朱婧，戴青云，王美林，等. 自適應遺傳算法在工程訓練在線考試中的應用[J]. 計算機工程與應用,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] 陳國彬，張廣泉. 基于改進遺傳算法的快速自動組卷算法研究[J]. 計算機應用研究,2015,32(10):2996-2998.

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

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

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

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

[12] 魯萍，何宏璧，王玉英. 智能組卷中分級帶權重知識點選取策略[J].計算機應用與軟件,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年國家級大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目(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

(編輯 陳 雷)