基于遺傳算法智能組卷的考試系統(tǒng)設(shè)計(jì)及實(shí)現(xiàn)＊

張烈超 劉開(kāi)文

（武漢交通職業(yè)學(xué)院，湖北 武漢 430065）

智能化組卷策略是網(wǎng)絡(luò)考試系統(tǒng)的核心技術(shù)，也是實(shí)現(xiàn)網(wǎng)絡(luò)考試系統(tǒng)的重點(diǎn)和難點(diǎn)。智能組卷遇到的主要問(wèn)題是保證生成的試卷具有隨機(jī)性、合理性、科學(xué)性的同時(shí)，必須最大程度地滿足用戶的需求，如診斷、評(píng)估考生的知識(shí)、能力掌握情況，提高考試的信度和效度。因此，在網(wǎng)絡(luò)交互環(huán)境中，題庫(kù)試題質(zhì)量要求比較高的前提下，組卷算法設(shè)計(jì)的優(yōu)劣直接決定了其執(zhí)行效率及質(zhì)量，故而選擇一個(gè)高效、科學(xué)算法是智能組卷的關(guān)鍵。［1］

組卷問(wèn)題的實(shí)質(zhì)是一個(gè)在一定約束條件下的多目標(biāo)參數(shù)優(yōu)化問(wèn)題，它的約束條件難以用數(shù)學(xué)形式來(lái)描述，采用傳統(tǒng)的數(shù)學(xué)方法求解十分困難。［2］文獻(xiàn)［1］［2］中提到的 隨機(jī)選取法和回朔試探法等組卷策略在求解大量試題或者復(fù)雜度較高的問(wèn)題時(shí)有明顯的缺陷，而采用人工智能算法之一的遺傳算法，求解此類組卷問(wèn)題則取得了較好的效果。［3］本文利用遺傳算法作為求解智能組卷問(wèn)題的策略，應(yīng)用于考試系統(tǒng)，并取得了較好的效果。

1 智能組卷相關(guān)問(wèn)題

1.1 試卷構(gòu)成要素

智能組卷考試系統(tǒng)中需要考慮的一項(xiàng)重要的內(nèi)容就是：如何從現(xiàn)有的試題庫(kù)構(gòu)建滿足教學(xué)要求的試卷。通常情況下，構(gòu)成一套試卷需要考慮很多因素，而且試卷中的每一道試題又包含多個(gè)屬性，其中，與組卷有關(guān)的屬性可能有以下幾項(xiàng)內(nèi)容：（1）題型；（2）知識(shí)點(diǎn)；（3）試題難度系數(shù)；（4）總分。［4］組卷過(guò)程中，由上述幾個(gè)屬性共同決定題庫(kù)中某道題目能否被抽中。生成一份n道題的試卷就是從試題庫(kù)用智能算法抽取n道符合要求的n道題，組成一個(gè)n×4的矩陣，矩陣中的每一列代表一個(gè)屬性，每一行代表一道題。［5］

該矩陣應(yīng)滿足以下約束條件：（1）題型：為考察學(xué)生的思維水平、分析運(yùn)算以及科學(xué)表達(dá)等能力，一份試卷應(yīng)包含足夠的客觀性試題及一定數(shù)量的非客觀性試題。綜合考慮上述兩方面的要求，本課題設(shè)計(jì)的試題庫(kù)包含了單選題、多選題、判斷題、填空題、綜合題等題型；（2）難度：針對(duì)不同考試對(duì)象及不同階段的考試，設(shè)置不同的難度，但應(yīng)保證試卷的區(qū)分能力。將試題按照容易（0.1～0.4）、中等（0.5～0.7）、難（0.8～0.9）三個(gè)難度等級(jí)［6］加以區(qū)別，此外試卷的難度系數(shù)為該套試卷所有題目分?jǐn)?shù)＊難度系數(shù)／總分；（3）分?jǐn)?shù)：每套試卷的分?jǐn)?shù)為100分，另外，對(duì)于綜合題型在保持總分不變并采用隨機(jī)確定分?jǐn)?shù)，可以加快算法收斂及題目的分配策略；（4）知識(shí)點(diǎn)：考試的內(nèi)容領(lǐng)域涉及多個(gè)知識(shí)點(diǎn)，每個(gè)知識(shí)點(diǎn)可對(duì)應(yīng)多道題型，并采用隨機(jī)方式選擇相應(yīng)的知識(shí)點(diǎn)并保證一定的覆蓋率，特別是重點(diǎn)內(nèi)容的覆蓋。

1.2 數(shù)學(xué)模型

智能組卷系統(tǒng)能客觀抽出符合要求的試卷，需要用戶預(yù)先設(shè)定目標(biāo)試卷（理想試卷）評(píng)估標(biāo)準(zhǔn)。遺傳算法常引入適應(yīng)度及相關(guān)的函數(shù)來(lái)進(jìn)行評(píng)判手段，適應(yīng)度是驅(qū)動(dòng)遺傳算法不斷尋優(yōu)的動(dòng)力，適應(yīng)度函數(shù)用來(lái)評(píng)判試卷種群中個(gè)體的優(yōu)劣程度的關(guān)鍵指標(biāo)，針對(duì)試卷的題數(shù)，總分等要求在初始化種群時(shí)已經(jīng)預(yù)先考慮，此處只需考慮知識(shí)點(diǎn)分布及難度系數(shù)。適應(yīng)度函數(shù)跟知識(shí)點(diǎn)分布及試卷難度系數(shù)有關(guān)，相關(guān)評(píng)判函數(shù)如下：

上述（1）式為試卷難度系數(shù)公式，其中i＝1，2……K，K是目標(biāo)試卷所含的題目數(shù)，Di，Si分別是第i題的難度系數(shù)和分?jǐn)?shù)；（2）式為知識(shí)點(diǎn)覆蓋率計(jì)算公式，例如，考試的內(nèi)容領(lǐng)域包含K個(gè)知識(shí)點(diǎn)，而一個(gè)個(gè)體（即待評(píng)的試卷）中所有題目知識(shí)點(diǎn)的并集中包含M個(gè)（M≤K），則知識(shí)點(diǎn)的覆蓋率為M／K；（3）式為適應(yīng)度評(píng)判函數(shù)，此處適應(yīng)度函數(shù)跟知識(shí)點(diǎn)分布［即（2）式］及試卷難度系數(shù)［即（1）式］有關(guān)。其中，EP為用戶的期望難度系數(shù)，D為試卷難度系數(shù)，w1為知識(shí)點(diǎn)分布的權(quán)重，w2為難度系數(shù)所占權(quán)重。當(dāng)w1＝0時(shí)退化為只限制試題難度系數(shù)，當(dāng)w2＝0時(shí)退化為只限制知識(shí)點(diǎn)分布。由評(píng)判目標(biāo)可知，用戶的期望難度系數(shù)與試卷難度系數(shù)之差越小越好，試題知識(shí)點(diǎn)覆蓋率越大越好。

1.3 遺傳算法

遺傳算法（Genetic Algorithm，簡(jiǎn)稱GA）是一類借鑒生物界的進(jìn)化規(guī)律演化而來(lái)的非數(shù)值模擬的計(jì)算模型，利用優(yōu)勝劣汰的自然遺傳機(jī)制，使種群中的個(gè)體不斷朝著最優(yōu)解的方向移動(dòng)，最終搜索到問(wèn)題的最優(yōu)解，常用來(lái)解決多約束條件下的最優(yōu)問(wèn)題。［7］

遺傳算法執(zhí)行的特點(diǎn)是從代表問(wèn)題可能潛在的解集的一個(gè)種群開(kāi)始的，通過(guò)編碼，產(chǎn)生初始種群，再予以遺傳、交叉、變異操作，并對(duì)每個(gè)染色體通過(guò)適應(yīng)度評(píng)判函數(shù)進(jìn)行評(píng)估。遵循適者生存的原理，利用“優(yōu)勝劣汰”的自然選擇機(jī)制，不斷進(jìn)行迭代以產(chǎn)生新解或稱新個(gè)體，通過(guò)不斷進(jìn)化，使種群中的個(gè)體不斷朝著最優(yōu)解的方向移動(dòng)，最終搜索到問(wèn)題的最優(yōu)解。［8］

由于遺傳算法具有內(nèi)在的并行性，可有效解決模型計(jì)算量大的問(wèn)題。因此，遺傳算法非常適合處理試題庫(kù)智能組卷問(wèn)題。［9］

1.4 遺傳算法實(shí)施流程圖

算法實(shí)施流程如圖1所示：

圖1 算法實(shí)施流程圖

2 遺傳算法在智能組卷中的解決思路及實(shí)現(xiàn)

利用遺傳算法進(jìn)行自動(dòng)組卷是根據(jù)出卷者給定的約束條件（本課題僅考慮試卷以下的屬性：題目數(shù)量、試卷總分、試題知識(shí)點(diǎn)分布、試題難度系數(shù)、試卷題型比例等），搜索試題庫(kù)中與出題要求相匹配的試題，從而抽取符合目標(biāo)要求的試題組合。

本課題為通過(guò)遺傳算法抽題策略的系統(tǒng)，因此，涉及到數(shù)據(jù)庫(kù)技術(shù)的試題庫(kù)建立和維護(hù)，此處略去該過(guò)程，集中討論遺傳算法抽題思路，由于遺傳算法在執(zhí)行過(guò)程中涉及到編碼、產(chǎn)生初始種群，遺傳操作（選擇、交叉，變異）、適應(yīng)度函數(shù)的條件的判別等步驟。

用遺傳算法實(shí)現(xiàn)組卷算法如下：

2.1 染色體編碼

用遺傳算法求解問(wèn)題，首先要將問(wèn)題的解空間映射成一組代碼串，即染色體的編碼問(wèn)題。

此處對(duì)染色體編碼采用了自然數(shù)編碼策略：即根據(jù)組卷要求從題型庫(kù)中選出試題組成符合要求的染色體基因段。基因編碼直接采用試題的編號(hào)。基因個(gè)數(shù)要求與組卷初始設(shè)置試題的個(gè)數(shù)保持一致，并且各題型組之間的編碼是要求相互獨(dú)立的。這樣染色體無(wú)需解碼，經(jīng)過(guò)迭代優(yōu)化之后可直接生成目標(biāo)試卷，［10］每一組編碼反映一種題型。每個(gè)染色體即為一套試卷，無(wú)需再進(jìn)行二進(jìn)制至十進(jìn)制編碼的轉(zhuǎn)換。

編碼方式具體如下［11］：構(gòu)建試卷，將試卷與染色體對(duì)應(yīng)，試卷中每道題的題號(hào)組成染色體的基因編號(hào)，題型相同的試題放在一起，不同的題型經(jīng)過(guò)分組后再按照染色體分段編碼規(guī)則組成分段基因序列，在后續(xù)的遺傳操作時(shí)也按此規(guī)則進(jìn)行，從而保證了每種題型的題目總數(shù)不變。如要組一份試卷，包含客觀題（單選題6道，多選題4道），主觀題型（填空題5道，判斷題5道，綜合題3道），則采用自然數(shù)編碼染色體結(jié)果如下：

2.2 初始種群的確定

確定初始種群（分試卷種群）的大小，種群規(guī)模的大小可以按問(wèn)題需求予以設(shè)計(jì)。此外，結(jié)合試題庫(kù)總題數(shù)、編碼題型比例、總分等要求，采用不完全隨機(jī)的方法生成試卷初始種群，使得初始種群一開(kāi)始就滿足了題數(shù)、總分等要求，并在初始處理階段對(duì)相關(guān)題型采取隨機(jī)給定分?jǐn)?shù)值，這樣可加快遺傳算法的收斂并減少迭代次數(shù)。初始種群代碼如下：

2.3 選擇操作

2.4 交叉操作

遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。由于本算法設(shè)計(jì)編碼采用的是自然數(shù)編碼，所以在進(jìn)行交叉時(shí)采用分段單點(diǎn)交叉（按題型分段來(lái)進(jìn)行交叉）。交叉過(guò)程需要注意，一是要保證試卷總分不變，二是保證交叉后沒(méi)有重復(fù)題號(hào)。交叉操作算法如下：

2.5 變異操作

變異操作在遺傳算法中起全局搜索的作用，變異概率一般較小。具體方法是對(duì)種群中的個(gè)體（染色體）串的某些位置上的基因作變動(dòng)。［13］本算法沒(méi)有采取將染色體分段進(jìn)行變異，而是根據(jù)算法條件中的要求對(duì)染色體某段內(nèi)的某個(gè)基因進(jìn)行變異。變異基因的選擇原則［14］為：與原基因所代表的題型相同、分?jǐn)?shù)相同，至少包含原題目一個(gè)有效知識(shí)點(diǎn)（與期望試卷知識(shí)點(diǎn)保持一致）。變異操作算法如下：

3 網(wǎng)絡(luò)考試系統(tǒng)體系結(jié)構(gòu)設(shè)計(jì)及應(yīng)用

3.1 智能組卷算法應(yīng)用

用java語(yǔ)言實(shí)現(xiàn)遺傳算法并將其嵌入本課題的應(yīng)用系統(tǒng)（B／S結(jié)構(gòu)）作為抽題策略、以試題庫(kù)（基于mysql數(shù)據(jù)庫(kù)）中210道試題作為數(shù)據(jù)源，并給出要生成的試卷要求，利用遺傳算法進(jìn)行抽題。算法中的參數(shù)分別為最大演化代數(shù)：500，適應(yīng)度期望值為0.98，試卷難度系數(shù)：0.55，試卷總分：100，每套試卷試題數(shù)44。隨機(jī)抽取的1套試卷如下：

此外，通過(guò)組卷算法生成的試卷可用于無(wú)紙化考試，也可用于傳統(tǒng)考試備用試卷。

3.2 考試系統(tǒng)體系結(jié)構(gòu)設(shè)計(jì)及功能

考試系統(tǒng)功能主要包括試卷維護(hù)、抽題組卷、學(xué)生考試、考試分發(fā)、考試管理、閱卷、成績(jī)統(tǒng)計(jì)等?？荚囅到y(tǒng)體系結(jié)構(gòu)如圖2所示，相關(guān)模塊功能如下：在前期建立的試題庫(kù)中使用遺傳算法生成的試卷作為無(wú)紙化考試或傳統(tǒng)考試的試題源（為防止考生作弊現(xiàn)象，可采取生成多份試卷策略）；教師或者考試管理員通過(guò)考卷分發(fā)模塊隨意為參加考試的考生分配考卷；準(zhǔn)予參加考試的考生登錄系統(tǒng)后可以進(jìn)行在線考試；考試管理模塊可對(duì)考試過(guò)程進(jìn)行實(shí)時(shí)監(jiān)控并將相關(guān)信息存入數(shù)據(jù)庫(kù)中；考試結(jié)束后，教師通過(guò)閱卷模塊進(jìn)行評(píng)分，并可統(tǒng)計(jì)成績(jī)；考生可對(duì)個(gè)人考試成績(jī)進(jìn)行查詢。

圖2 考試系統(tǒng)體系結(jié)構(gòu)

4 結(jié)語(yǔ)

本文設(shè)計(jì)了一種基于三層架構(gòu)的網(wǎng)絡(luò)考試系統(tǒng)結(jié)構(gòu)，采用基于自然數(shù)編碼的遺傳算法智能化組卷策略，并將算法應(yīng)用于網(wǎng)絡(luò)考試系統(tǒng)中［15］。實(shí)驗(yàn)結(jié)果表明，用遺傳算法能有效的解決自動(dòng)組卷問(wèn)題，具有較好的使用性能和實(shí)用性。

本算法尚需進(jìn)一步深入研究，如引入相關(guān)機(jī)制對(duì)抽題過(guò)程中算法可能出現(xiàn)的過(guò)早收斂或者陷于局部?jī)?yōu)化的情況加以改進(jìn)，有望取得更好效果。

［1］［5］朱玉祥，苗春生，孫承佼.基于算法的試題庫(kù)智能組卷系統(tǒng)研究［J］.南京氣象學(xué)院學(xué)報(bào)，2006，（2）：282－285.

［2］［6］［9］［10］［12］［13］周文舉.基于遺傳算法的自動(dòng)組卷系統(tǒng)研究與實(shí)現(xiàn)［D］.山東師范大學(xué)碩士學(xué)位論文，2006：6－16.

［3］全惠云，范國(guó)闖，趙霆雷.基于遺傳算法的試題庫(kù)智能組卷系統(tǒng)研究［J］.武漢大學(xué)學(xué)報(bào)（自然科學(xué)版），1999，（5）：758－760.

［4］楊青.基于算法的試題庫(kù)自動(dòng)卷問(wèn)題研究［J］.濟(jì)南大學(xué)學(xué)報(bào)（自然科學(xué)版），2004，（3），228－231.

［7］Guo Tao，Kang Li－shan.A new Evolutionary Algorithm for Function Optimization［J］.Wuhan University Journal of Nature Sciences，1999，（4）：409－414.

［8］J.T.Tsai，T.K.Liu，J.H.Chou.Hybrid Taguchi－Genetic Algorithm for Global Numerical Optimization［J］.IEEETransactions on Evolutionary Computation，2004，（4），365－377.

［11］［14］實(shí)例講解遺傳算法——基于遺傳算法的自動(dòng)組卷系統(tǒng)［EB／OL］.（2011－05－19）［2013－01－12］.http：／／www.cnblogs.com／artwl／archive／2011／05／19／2051556.html.

［15］拓守恒.基于遺傳算法智能組卷的J2EE考試系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.西華大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，（5）：31－37.