遺傳算法實(shí)現(xiàn)試題庫(kù)智能組卷方法研究

吳　迪　龔啟軍

【摘 要】智能組卷方法是當(dāng)今各大高校及相關(guān)單位試題庫(kù)系統(tǒng)中的核心內(nèi)容。本文提出了一種基于遺傳算法解決組卷問(wèn)題的改進(jìn)方法，該算法以其具有的自適應(yīng)全局尋優(yōu)和智能搜索技術(shù)且收斂速度快的特點(diǎn)解決了傳統(tǒng)組卷中編碼太長(zhǎng)、適應(yīng)度函數(shù)值計(jì)算困難等問(wèn)題，建立和描述了組卷問(wèn)題的染色體結(jié)構(gòu)和適應(yīng)度函數(shù)，設(shè)計(jì)了問(wèn)題的遺傳操作，為進(jìn)一步完善網(wǎng)絡(luò)試題庫(kù)的建設(shè)奠定了堅(jiān)實(shí)的基礎(chǔ)。

【關(guān)鍵詞】試題庫(kù) 數(shù)學(xué)模型 遺傳算法 智能組卷

一、引言

本文對(duì)組卷方法進(jìn)行了研究，使用遺傳算法建立自動(dòng)組卷的數(shù)學(xué)模型，并將遺傳算法具體應(yīng)用于試題抽取。

本文采用遺傳算法的概念，將每道試題作為一個(gè)獨(dú)立的編碼位，利用遺傳算法的三個(gè)基本操作：遺傳、交叉與變異并最終完成試題的選取，得到滿足各種條件的試題集和。遺傳算法以其具有自適應(yīng)全局尋優(yōu)和職能搜索技術(shù)，并且收斂性的特性很好滿足自動(dòng)組卷的需要，具有較高的性能。

二、遺傳算法的基本概念及設(shè)計(jì)步驟

1.遺傳算法基本概念

遺傳算法的基本思想是基于Darwin進(jìn)化論的Mendel的遺傳學(xué)說(shuō)的。由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法，因此在這個(gè)算法中要用到各種進(jìn)化和遺傳學(xué)的概念。

2.遺傳算法基本步驟

三、自動(dòng)組卷算法設(shè)計(jì)

1.組卷策略分析

組卷就是從試題庫(kù)中抽取試題，實(shí)現(xiàn)根據(jù)用戶組卷要求生成的組卷模式。組卷的過(guò)程就是從試題庫(kù)中選擇合適的試題去實(shí)現(xiàn)這些分?jǐn)?shù)分布。由于選題是有一定限制的，不是所有的試題庫(kù)中的試題都有參與選題的資格，只有那些滿足一定條件的試題才能參與選題。所以，選題組卷是在一定的約束條件下進(jìn)行的。根據(jù)上述對(duì)組卷步驟地分析，組卷的約束條件基本上有以下十個(gè)方面，即知識(shí)點(diǎn)約束、題型約束、章節(jié)約束、認(rèn)知層次約束、題量約束、分值約束、答題時(shí)間約束、難度約束、區(qū)分度約束、曝光度約束等。

針對(duì)整個(gè)試卷所有的題目構(gòu)成如下的一個(gè)十維度變量的空間：

試卷（知識(shí)點(diǎn)，題型，章節(jié)，認(rèn)知層次，題量，分值，答題時(shí)間，難度，區(qū)分度，曝光度）。為減小組卷算法的復(fù)雜度，提高組卷算法效率，對(duì)一份試卷，確定試題難度、試卷的滿分值和所用的題型，以及各種題型的題目、分?jǐn)?shù)和知識(shí)點(diǎn)分布；而對(duì)一種考試而言，難度—分?jǐn)?shù)分布曲線LD常保持相對(duì)穩(wěn)定，需要用到難度—分?jǐn)?shù)分布曲線和數(shù)學(xué)模型即可計(jì)算出不同難度級(jí)別的題目在試卷中所占的比例，再結(jié)合各知識(shí)點(diǎn)、各題型的分?jǐn)?shù)在試卷中所占的比例，將十維空間簡(jiǎn)化為五維空間——每一個(gè)試題（知識(shí)點(diǎn)，章節(jié)，題型，分值，難度）。

根據(jù)上述過(guò)程，首先解決“確定試卷知識(shí)點(diǎn)范圍”、“章節(jié)范圍”和“試卷包含的題型”三個(gè)步驟。

下一步，根據(jù)各題型所包含的題量，在各自的題型庫(kù)表中抽題，抽題采用隨機(jī)函數(shù)法。稱這樣抽取的一組題目，為一個(gè)“個(gè)體樣本”。這就似乎最初建立的試卷樣本。

這個(gè)樣本至少滿足了前三個(gè)步驟的要求，即知識(shí)點(diǎn)范圍、章節(jié)、題型和題量上得到滿足，但在“知識(shí)點(diǎn)分布”、“難度”、“區(qū)分度”、“曝光度”等維度上的約束條件可能存在或多或少的偏差，但這樣做已經(jīng)具備很好的應(yīng)用遺傳算法的可能性。

我們可以選取多個(gè)樣本，然后按照遺傳算法，使個(gè)體樣本進(jìn)行演化，得到滿足章節(jié)、知識(shí)點(diǎn)、難度、題型和分值這五個(gè)約束條件的個(gè)體樣本，而曝光度約束一般不限制為一個(gè)固定值條件，而是在尋優(yōu)過(guò)程中選擇曝光度之和最小的一組解，作為最后組卷的結(jié)果。

2.自動(dòng)組卷算法的研究

試卷模式各參數(shù)實(shí)現(xiàn)之后，得到的是滿足當(dāng)前試卷模式的各道試題的具體指標(biāo)要求值。下面關(guān)鍵的步驟就是從試題庫(kù)中尋找具有這些特定屬性指標(biāo)的試題，組成試卷。

用遺傳算法求解問(wèn)題，首先要將問(wèn)題的解空間映射成一組代碼串。采用二進(jìn)制編碼，用1表示該題被選中，0表示該題未被選中，這種編碼簡(jiǎn)單明了，但在進(jìn)行交換等遺傳操作時(shí)，各題型的題目數(shù)難以精確控制，而且當(dāng)題庫(kù)中題量很大時(shí)，編碼很長(zhǎng)。本文在確定編碼方案時(shí)，采用了分組自然數(shù)編碼策略。

每一組編碼反映一種題型，各個(gè)題型各自進(jìn)行自然數(shù)編碼，即每一個(gè)題型根據(jù)組卷要求從初始化后的題型庫(kù)中選出試題組成染色體。每一被選中的試題代表一個(gè)染色體編碼，編碼直接利用試題的編號(hào)。染色體采用變長(zhǎng)編碼策略進(jìn)行處理，染色體中編碼的個(gè)數(shù)就是試卷中試題的個(gè)數(shù)，題型組之間的編碼是獨(dú)立的。

在組卷中所得的可行解就為一份試卷，所以本文將一份試卷映射為一個(gè)染色體，組成試卷的各個(gè)試題映射為基因，基因的值直接用試題的題號(hào)表示，這樣染色體的編碼可表示為：(G₁,G₂,G₃,…,G_n)，其中G_i(i=1,2,…,n，n為試卷的總題目數(shù))為試題的題號(hào)。

四、自動(dòng)組卷算法的實(shí)現(xiàn)

確定參數(shù)：最大代數(shù)MaxGen，群體規(guī)模PopSize，交叉概率Pc，變異概率Pm；

接收用戶的組卷要求；產(chǎn)生初始群體；

當(dāng)前代數(shù)gen=；計(jì)算群體中各個(gè)體的適應(yīng)值；

while(gen

{

根據(jù)個(gè)體適應(yīng)值及選擇策略從當(dāng)前群體中選擇生成下一代的父體；

執(zhí)行交換操作和變異操作生成新一代群體；

計(jì)算新一代群體中各個(gè)體的適應(yīng)值；

比較新一代的最好個(gè)體與上一代的最好個(gè)體的適應(yīng)值，如下降，則以上一代最好個(gè)體替換新一代的最差個(gè)體；

輸出當(dāng)前代數(shù)，群體的平均目標(biāo)函數(shù)，最好個(gè)體的目標(biāo)函數(shù)值；

gen++；

}

輸出最好個(gè)體的編碼，計(jì)算各章節(jié)分?jǐn)?shù)、各案難度級(jí)別的分?jǐn)?shù)等指標(biāo)，輸出這些指標(biāo)的值并與用戶的要求值相比較。具體源代碼略。

五、結(jié)束語(yǔ)

自動(dòng)組卷系統(tǒng)是計(jì)算機(jī)輔助教學(xué)的重要組成部分，綜合全文可見(jiàn)，本文主要工作是將遺傳算法引入自動(dòng)組卷問(wèn)題，并在理論和實(shí)驗(yàn)中驗(yàn)證了基于遺傳算法自動(dòng)組卷的可行性。

參考文獻(xiàn)：

[1]丁振凡.基于WWW的遠(yuǎn)程教學(xué)軟件的設(shè)計(jì).華東交通大學(xué)學(xué)報(bào),1999,16(3):10-15.

[2]王寬全,符云清.基于WWW的計(jì)算機(jī)輔助教學(xué)環(huán)境.重慶大學(xué)學(xué)報(bào)(自然科學(xué)版).

[3]JR Quinlan.Induction Of Induction Of Decision Tress.Machine Learning,1986,(1):81-106.

基金項(xiàng)目：重慶工程職業(yè)技術(shù)學(xué)院科研基金資助項(xiàng)目（07YB009）廳級(jí)課題。