通用在線考試系統(tǒng)智能組卷遺傳算法設計

呂海燕　周立軍　宦婧　張杰

摘要：組卷算法設計是考試系統(tǒng)設計的核心。在分析通用在線考試系統(tǒng)的特點及組卷原則的基礎上，首先建立一種改進的組卷數學模型；接下來依據該模型主要從編碼方式選擇、適應度函數的確定以及遺傳算子的設計等方面詳細設計通用在線考試系統(tǒng)采用的改進的遺傳算法；最后，給出基于改進的遺傳算法的智能組卷流程。應用表明，采用該算法實現的本系統(tǒng)的組卷功能在組卷的速度和成功率都得到顯著提高，較好地滿足了各類課程的組卷需求。

關鍵詞：智能組卷；遺傳算法；組卷數據模型；組卷流程；通用在線考試系統(tǒng)

中圖分類號：TP311.13文獻標識碼：A

Abstract：Intelligent algorithm of assembling test taper is the core of the test system design. Based on analysis of the characteristics of the common online examination system and the general principles， firstly an improved test paper generated mathematical model was established. Then the improved genetic algorithm was designed mainly from the following three aspects： the coding scheme selection， the fitness function determination and the genetic operator design. Finally， the intelligent test paper process of the adopted improved genetic algorithm was shown. Applications show that the test paper speed and success rates have been significantly improved to better meet the needs of various courses of test paper.

Key words：intelligent generating；genetic algorithm；test paper generated mathematical model；test paper generate process；common online examination system

1引言

通用在線考試系統(tǒng)是我院自行開發(fā)，并且已經在軍隊院校以及各基層單位得到了廣泛應用。在考試系統(tǒng)中，組卷算法設計的好壞將直接影響著考試系統(tǒng)性能的優(yōu)劣。優(yōu)秀的組卷算法不僅應該能夠根據任課教師的各種要求及課程的特點智能生成考試試卷，還應滿足考核不同層次學生的需要，以便能夠真實、有效地反映學生的學習能力和教師的教學水平。

不論是在組卷質量還是在性能方面?zhèn)鹘y(tǒng)的組卷算法（如回溯試探法、隨機抽題及誤差補償法等）都難以滿足組卷要求。遺傳算法（GA）是對自然現象或過程進行模擬而形成的，它通過模擬達爾文的自然選擇學說和自然界的生物進化過程而形成的一種計算模型。它的收斂性也很好，可以有效解決計算量大的問題，而這些特點是處理智能組卷中所必需的，所以遺傳算法已成為目前在線考試智能組卷的首選算法。[1-2]而傳統(tǒng)的遺傳算法在收斂速度和計算全局最優(yōu)解之間存在矛盾，容易產生早熟現象、局部尋優(yōu)能力差等缺點。因此，結合遺傳算法的優(yōu)點和缺點，通用課程在線考試系統(tǒng)在實現智能組卷時采用了一種改進的遺傳算法來實現。

2智能組卷的數學建模

組卷問題的數學模型的建立是組卷算法實現的基礎，它決定了組卷算法性能的好壞。結合通用在線考試系統(tǒng)的功能特點及組卷的原則，本文建立了一個適合于本系統(tǒng)的多目標優(yōu)化組卷數學模型。

2.1試題屬性的確定

通過遺傳算法高效精確地完成組卷時，試題屬性的設置要滿足經典測量理論的需求。[2]試題屬性的設置以能把整套試卷中的試題的情況說清楚即可，屬性不能太多也不能太少。依據這一原則，本系統(tǒng)選取設置的試題屬性主要有以下幾個：

1）題號：區(qū)分試題的唯一屬性，在數據庫設計中設置為試題的主鍵。

2）題型：主要包含單選題、多選題、填空題、判斷題、改錯題、程序設計等多種題型，可根據課程特點對題型進行靈活地設計。

3）分數：該題目在試卷中所占的分值，主要依據題目的難度及所涉及的知識點來確定。

4）難度：反映試題的難易程度，從等級上大致分為容易、較易、中等、較難、難等多個等級，可通過設置范圍為0.00～1.00的難度系數來體現。試題難度可以在系統(tǒng)啟用初期由經驗豐富的教師手動設置，也可以在系統(tǒng)使用一段時間后，根據學生測試的正確率自動調節(jié)（試題的回答正確率的近似值為其難度值）。

5）知識點：試題所考核的知識點的體現。通常情況下，如果試題屬于相同知識點，則他們具有非常高的相似度，在生成試卷時，應最大限度地避免它們出現在同一試卷中。在考試系統(tǒng)數據庫設計中，該屬性作為外鍵。

6）曝光度：指本試題在歷次考試中被選中的次數，該屬性是進行考試評價和后期組卷策略調整的重要依據。

依據數學建模理論[3]，如果要組一套含有n道試題的試卷，假設每一道試題含有m項指標，那么要確定這份試卷，就要先確定一個n*m 的矩陣，如下圖1所示：

其中，矩陣中每一行為一道試題，每一列為試題的一個屬性。對于本系統(tǒng)而言，n為6，這6個屬性依次是：題號、題型、分數、難度、知識點和曝光度。

2.2組卷的約束條件

依據前述智能組卷基本原則及構建的組卷數學模型，本系統(tǒng)確定組卷的幾個重要約束條件如下幾個：試卷總分值約束；考試時間約束；題型和各題型的題量約束；考試范圍約束；知識點分數分布約束；試卷的難度約束；試卷的區(qū)分度約束：區(qū)別不同層次學生能力水平的主要標準，也是衡量試卷質量的一個重要指標。

3多目標優(yōu)化的數學模型的建立

如前所述，要組成一份試卷需要滿足多個約束條件，整張試卷需要滿足的所有約束條件集合構成了一個多維變量空間。而矩陣的維數越多求解就越復雜，也就是說，如果組卷玉樹矩陣的維數設計不合理，會在很大程度上增加組卷算法設計的難度，同時也會降低組卷的效率。[3-5]為此，本系統(tǒng)采用的組卷算法在設計時，基于以下前提：試卷的總分、完成時間、包含的題目類型、各題型的題目數量、各題型中每小題的分值由教師設置的（或者由系統(tǒng)默認）。如對于《大學計算機基礎》課程，考試通常包括選擇、填空和應用設計三種題型，同一類題型中各小題分值是一樣的，題量的設置可以根據考試時間來確定。因此，一旦固定了題量，算法就不再考慮各小題的分值和每個小題的做題時間。也就是說，可將試題的約束條件簡化到“難度”、“知識點”、“區(qū)分度”和“曝光度”這四個屬性。此時，試卷的約束條件簡化到了一個四維空間，如下圖2所示。

其中，矩陣中n行代表一套試卷的n 道試題，每一行表示一道試題相應的四個約束條件，分別是：難度、知識點、區(qū)分度和曝光度。

4算法的設計

在應用遺傳算法解決組卷問題時，將一份試卷當成一個個體或者是染色體，而試卷中的每道題當作一個基因，多份試卷則稱為一個種群。遺傳算法的組成主要有編碼方式、初始化種群、適應度函數、遺傳算子（遺傳、交叉、變異）以及終止條件（控制參數）的設定五個方面。下面主要從這個五個方面介紹本考試系統(tǒng)所采用的改進的遺傳算法的設計。

4.1編碼方式的選擇

應用遺傳算法完成組卷時，首先要解決的是個體的編碼問題，編碼用于產生初始種群。由于每道試題在題庫中按照題型不同都有唯一的自然數編號，依據該特點本系統(tǒng)組卷算法采用整數分段編碼方案。其主要思想是，整個編碼分成獨立的幾段，其中每類題型對應一段，而每段的長度則由每個題型在待生成試卷中題目的數量決定；各題型間的編碼是相互獨立，各自按照整數編碼方式進行編碼；編碼串的總長度等于待生成試卷要求的試題總數量。

整數分段編碼的優(yōu)點是：克服了二進制編碼長度過長和搜索空間過大的缺點，從而節(jié)省了個體解碼的時間，提高了遺傳算法的計算效率；同時，由于同類型的試題放在同一段內，交叉和遺傳操作均在段內進行，這樣可以在一定程度上確保優(yōu)化目標中題型匹配的正確性。

如前所述，在整數分段編碼中，每一段代表一種題型，而每個基因就是被選中的試題編號。如《大學計算機基礎》課程試題庫中共有4種題型：單項選擇題、填空題、判斷題和應用設計題，共600道題，它們分別用符號X、K、P和Y表示，X類題型有300個，K類題型有100個， P類題型有100個，Y類題型有100個。各類題型在待組試卷中的試題數分別是s1（1≤s1≤300），s2（1≤s2≤100），s3（1≤s3≤100），s4（1≤s4≤100），編碼的總長度S為待組試卷中的總題數，即s=∑4i=1si。編碼方案如下表1所示。

4.2初始化種群的生成

在遺傳算法搜索過程中，種群規(guī)模大小的設置對算法的收斂速度和求解最優(yōu)解的幾率有很大影響。通用在線考試系統(tǒng)為了加快算法的收斂速度，在生成初始種群時，采用了不完全隨機的方式，使初始種群中的個體一開始就滿足時間、題量、題型和分數的要求，從而在一定程度上提高了算法的搜索效率。種群初始化后，再對種群中個體的相似度進行比較，將相似度高的個體進行刪除，從而避免了初始種群中出現過多的相似度高的個體，使初始種群的規(guī)模進一步減小。

4.3適應度函數的確定

組卷要求與染色體之間的差別是通過適應度函數來反應的，適應度函數是指導遺傳算法的主要信息來源，同時它也是區(qū)分優(yōu)劣個體的一個很好的工具。[5-7]要想保持群體多樣性需要有一個良好的適應度函數，它能有效防止群體的早熟問題。通常情況下，個體的好壞與適應度函數值成正比，即適應度函數值越大，則個體越好。

如前所述，由于考試時間、題量、題型和分數題型要求在初始化種群時已經考慮。因此，適應度函數在確定時，僅需再考慮難度系數、知識點分數分布和試卷區(qū)分度這幾個指標即可。由此確定的適應度函數僅與試卷難度系數（用P表示）、知識點分數分布（SPD）和試卷區(qū)分度（用D表示）有關。也就是說，試卷期望難度系數EP與試卷實際難度系數P之差Ep、用戶的期望知識點分數分布ESPD與實際知識點分數分布SPD之差ES、和試卷期望區(qū)分度ED與試卷實際區(qū)分度D之差ED，越小越好。系統(tǒng)的適應度函數設計如下：

F=（Esw1+Epw2+EDwa）（1）

適應度函數F的值越小，則個體的適應度就越高。其中，Es=∑ki=1|ESPD-SFD|，即各章節(jié)知識點分數分布期望值偏差的絕對值之和，Ed=|ED-D|，Ep=|EP-D|，w1+w2+w3=1。

4.4遺傳進化中的選擇操作

遺傳算法模擬自然界中的選擇機制對群體中的個體按照其適應度值的大小進行優(yōu)勝劣汰操作時，是通過選擇算子來實現的。選擇算子的強度不能太大，也不能太小，選擇強度要適中才有利于算法搜索問題最優(yōu)解。選擇強度太大的算子，會使群體喪失多樣性從而陷入局部最優(yōu)，影響問題求解結果；而選擇強度過小算子，會使種群的進化速度會十分緩慢，影響問題求解速度。[12-13]本系統(tǒng)采用了最優(yōu)保持策略與輪盤賭選擇策略相結合的方法，從而在一定程度上避免了輪盤賭選擇策略的隨機性。

輪盤賭算法：

設種群由M個個體組成，其中個體Mi的適應度用Fi表示，則此個體的選中率用Pi表示，則：

Pi=Fi/∑Mi=1Fi（2）

輪盤賭算法的操作過程如下：首先根據公式（1）計算群體中各個個體（每套試卷）的適應度值Fi，根據公式（2）計算出每個個體被選中的概率Pi；接下來計算群體中各個個體的累積率Qk=∑ki=1Pi并以此構建一個輪盤；求出Qk之后，依據 Qk的值來選擇參與進入下一代的個體：確定一個[0，1]之間的值r（可隨機產生），比較Qk與r的值的大小，若r≤Qi，就選擇個體M1；若Qk-1≤r≤Qk，則選擇個體Mk參與下一代群體；如上反復執(zhí)行，直到產生M個個體，即M套試卷。

在遺傳算法的進化過程中，通過執(zhí)行選擇、交叉及變異等操作從而不斷生成越來越多的優(yōu)良個體。但是，由于選擇、交叉及變異操作的隨機性，會導致適應度好的個體經常被破壞，從降低算法的收斂性和執(zhí)行效率。[8]因此，為盡可能地使適應度好的個體保留到下一代群體中。通用考試系統(tǒng)在實現選擇操作時，將輪盤賭選擇策略和最優(yōu)保留策略結合起來實現進化過程中的選擇操作。

4.5遺傳進化中的交叉操作

傳統(tǒng)遺傳算法在實現交叉操作時，采用的是恒定不變的交叉概率，這會導致遺傳算法在解決復雜的優(yōu)化問題時，效率很低且容易出現早收斂現象。[9]本系統(tǒng)為了加速算法搜索速度，并有效地防止早收斂現象，采用了Srinvivas提出的自適應交叉概率Zc。自適應交叉概率Zc的計算公式如下：

Zc=11+exp（-k1（Fmax-Favg））（3）

其中，k1為大于0的常數，本系統(tǒng)選擇的是k1=0.6，Fmax表示種群中個體的最大適應度值，Favg表示群體中大于平均適應度的那部分個體的平均適應度值，Zc在[0.6，1]之間取值。

在算法的進化過程中。交叉概率Zc會根據Fmax-Favg的不同而自動調整，當群體趨于分散時，也就是Fmax-Favg增大時，交叉概率Zc增大，而對應的變異概率減小，從而使種群生成優(yōu)良個體的能力增強；反之，當群體趨于收斂時，也就是當Fmax-Favg減小時，交叉概率Zc減小，而對應的變異概率增大，從而使群體保持多樣性的能力增強。

基于上述自適應調整交叉概率的交叉操作過程如下：

1）設種群規(guī)模為N，將群體中的個體隨機進行兩輛交配，則會產生[]對個體組；

2）對種群中的個體隨機生成交叉點，如果個體的編碼長度為L，則有L-1個位置會成為交叉點；

3）如前所述在整數分段編碼方案中，每一種題型對應一段編碼，交叉操作在編碼段內獨立進行，這樣可以保證每種題型的試題數量不變。即若交叉點在第i個基因段內，則前i個基因段保持不變，只需從第i+1個基因段開始逐個基因進行交換。

采用此方式可避免基因段內進行交叉后出現試題重復的弊端。執(zhí)行完交叉操后，再按照適應度函數分別計算兩個新生個體的適應度，并將其與父代個體的適應度進行比較，若兩者適應度相同，則將其丟棄；若不同則對它進行變異操作。

4.6遺傳進化中的變異操作

通過交叉與變異操作的相互配合，使得遺傳算法有了較高的搜索能力。交叉操作是算法的核心，在進化過程中對算法的局部搜索能力起關鍵性作用；而變異操作則是影響算法的全局搜索能力的主要因素。[10]在進化過程中，當算法的搜索過程陷入局部最優(yōu)時，通過有效的變異操作可跳出局部最優(yōu)，從而達到全局尋優(yōu)的目的。但變異概率過大也有破壞掉最優(yōu)解的可能，因此，不能盲目地進行變異操作。同交叉操作一樣，本系統(tǒng)采用了Srinvivas提出的自適應變異概率，其計算公式如下：

Zm=11+exp（-k2（Fmax-Favg））（4）

同前述自動調整交叉概率的計算公式一樣，其中，k2為大于0的常數，這里選擇k2=0.9，Fmax表示種群中個體的最大適應度值，Favg表示群體中大于平均適應度的那部分個體的平均適應度值，Pm在[0，0.5]之間取值。

同交叉操作一樣，在執(zhí)行變異操作時，各種題型也是在各自對應的編碼段內進行。首先對群體中的各個個體生成一個與其編碼長度L相同的隨機數序列R={r1，r2……r1}，其中，0≤r1≤1，0≤i≤1；對所有ri

1）查找出基因位i所在段對應的試題類型；

2）找出該基因位（題號）所代表的試題所對應的知識點、難度系數，然后隨機生成一個新的滿足要求的試題編號，從而產生一個新的染色體（試卷個體）；

3）判斷該新的基因串是否已經存在，如果存在則轉向步驟2，再次生成新的染色體。否則用此新的染色體替換原來的染色體。

4.7終止條件的設定

基于遺傳算法的實現時，就是反復從試題庫中搜索符合相應約束條件的試題直到找到最優(yōu)解的過程。如果經過反復多次選擇、交叉、變異操作后，仍然沒有找到最優(yōu)解，那么搜過過程不可能無休止地循環(huán)下去迭代下去。此時，需要設定一個終止條件來結束這種無休止無意義的搜索迭代過程。終止條件的設定主要需要考率以下三種情況：

1）設定進化迭代最大次數，當最大值出現時，算法終止。一般為150-600。

2）設定好一個適應度最高值，若該值出現，即可終止算法。

3）如果連續(xù)幾代個體適應度平均值的差異小于某一極小閾值或者當所有個體適應度函數值的方差小于某一極限閾值時，也可考慮終止算法的進行。

根據以上算法終止條件的判斷，本系統(tǒng)組卷算法采用了以下兩種終止條件：

1）種群進化到指定的迭代數，系統(tǒng)設參考范圍為500-1000代，默認值取600。

2）最優(yōu)個體的適應度與期望的最好適應度比值為96%以上，即用戶對生成的試卷滿意度為96% 。

在迭代過程中，只要滿足其中任意一個條件，都會終止算法的操作，并輸出相應的試卷；

5基于改進算法的智能組卷流程

基于改進后的遺傳算法的智能組卷流程如下圖5所示。6結論

本系統(tǒng)采用的改進的遺傳算法的智能組卷策略，主要是結合組卷問題本身的特點，在遺傳算法的染色體編碼方式選擇、初始化種群的生成以及適應度函數、交叉和變異操作的設定等方面進行了相應的改進。其中，整數分段編碼方式節(jié)省了個體解碼的時間，提高了遺傳算法的計算效率；分段交叉方式和自適應交叉概率、變異概率的應用，提高了算法的收斂速度，較好地避免了傳統(tǒng)遺傳算法的早熟問題。應用表明，本系統(tǒng)的組卷功能在組卷的速度和成功率都得到顯著提高，較好地滿足了各類課程的組卷需求。

參考文獻

[1]肖理慶，徐曉菊.改進遺傳算法智能組卷研究[J].計算機工程與設計，2012，（10）：35-39.

[2]唐啟濤.基于改進的遺傳算法的智能組卷算法研究[J].計算機技術與發(fā)展，2014，（12）：241-244.

[3]袁桂霞.自動組卷的建模和仿真研究[J].計算機仿真，2011，（28）：370-373.

[4]汪民樂.遺傳算法的收斂性研究[J].計算技術與自動化，2015，（10）：52-56.

[5]王吉權，王福林.單點交叉多子代遺傳算法[J].生物數學學報，2015，30（2）：305-311.

[6]李書全，孫雪.遺傳算法中的交叉算子的述評[J].計算機工程與應用，2012，（1）：67-71.

[7]賀榮，陳爽.在線組卷策略的研究與設計[J].計算機工程與設計，2011，（6）：2183-2183.

[8]劉淳安，趙天緒，劉燚.智能組卷的優(yōu)化模型及求解的遺傳算法[J]，科學技術與工程，2010，（10）：2754-7456.

[9]張宗飛.網絡化考試中智能組卷方法研究[J]，中國教育信息化，2015，（16）：79-81.

[10]柳良濤，谷林.自動組卷系統(tǒng)試題難度和知識點覆蓋控制算法[J].西安工程大學學報，2015，（3）：320-324.