吳 迪 龔啟軍
【摘 要】智能組卷方法是當(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è)基本操作:遺傳、交叉與變異并最終完成試題的選取,得到滿(mǎn)足各種條件的試題集和。遺傳算法以其具有自適應(yīng)全局尋優(yōu)和職能搜索技術(shù),并且收斂性的特性很好滿(mǎn)足自動(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ù)用戶(hù)組卷要求生成的組卷模式。組卷的過(guò)程就是從試題庫(kù)中選擇合適的試題去實(shí)現(xiàn)這些分?jǐn)?shù)分布。由于選題是有一定限制的,不是所有的試題庫(kù)中的試題都有參與選題的資格,只有那些滿(mǎn)足一定條件的試題才能參與選題。所以,選題組卷是在一定的約束條件下進(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ì)一份試卷,確定試題難度、試卷的滿(mǎn)分值和所用的題型,以及各種題型的題目、分?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ù)法。稱(chēng)這樣抽取的一組題目,為一個(gè)“個(gè)體樣本”。這就似乎最初建立的試卷樣本。
這個(gè)樣本至少滿(mǎn)足了前三個(gè)步驟的要求,即知識(shí)點(diǎn)范圍、章節(jié)、題型和題量上得到滿(mǎn)足,但在“知識(shí)點(diǎn)分布”、“難度”、“區(qū)分度”、“曝光度”等維度上的約束條件可能存在或多或少的偏差,但這樣做已經(jīng)具備很好的應(yīng)用遺傳算法的可能性。
我們可以選取多個(gè)樣本,然后按照遺傳算法,使個(gè)體樣本進(jìn)行演化,得到滿(mǎn)足章節(jié)、知識(shí)點(diǎn)、難度、題型和分值這五個(gè)約束條件的個(gè)體樣本,而曝光度約束一般不限制為一個(gè)固定值條件,而是在尋優(yōu)過(guò)程中選擇曝光度之和最小的一組解,作為最后組卷的結(jié)果。
2.自動(dòng)組卷算法的研究
試卷模式各參數(shù)實(shí)現(xiàn)之后,得到的是滿(mǎ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)表示,這樣染色體的編碼可表示為:(G1,G2,G3,…,Gn),其中Gi(i=1,2,…,n,n為試卷的總題目數(shù))為試題的題號(hào)。
四、自動(dòng)組卷算法的實(shí)現(xiàn)
確定參數(shù):最大代數(shù)MaxGen,群體規(guī)模PopSize,交叉概率Pc,變異概率Pm;
接收用戶(hù)的組卷要求;產(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)的值并與用戶(hù)的要求值相比較。具體源代碼略。 五、結(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í)課題。