一、引言隨著計(jì)算機(jī)在教學(xué)領(lǐng)域的應(yīng)用和發(fā)展，試題庫(kù)的編制和應(yīng)用也越來(lái)越顯示出其重要性，而智能組卷是試題庫(kù)系統(tǒng)研制的一個(gè)難點(diǎn)。智能組卷要求用戶只需輸入極少的參數(shù)值就可由計(jì)算機(jī)自動(dòng)生成一種試卷模式，并據(jù)此抽題組成試卷，最終形成一份既符合用戶要求又符合教學(xué)要求的試卷。一個(gè)自動(dòng)組卷系統(tǒng)的性能評(píng)價(jià)主要取決于組卷算法和相對(duì)于算法的試題庫(kù)的庫(kù)結(jié)構(gòu)。因此，試題庫(kù)的庫(kù)結(jié)構(gòu)設(shè)計(jì)和組卷算法的設(shè)計(jì)師智能型試卷自動(dòng)生成系統(tǒng)的重要內(nèi)容。本文提出了一種用改進(jìn)的遺傳算法來(lái)求解試題庫(kù)組卷問(wèn)題的方法和一種使組卷效率更高、速度更快、數(shù)據(jù)冗余度更小的試題庫(kù)結(jié)構(gòu)。二、智能型試卷自動(dòng)生成系統(tǒng)的組卷問(wèn)題綜合遺傳算法的特點(diǎn)，系統(tǒng)所采用的試題庫(kù)結(jié)構(gòu)要全面客觀反映試題的本質(zhì)，并且易于遺傳算法操作，使組卷實(shí)現(xiàn)智能化，組卷效率高、速度快、數(shù)據(jù)冗余度小。因此，所確定的試題結(jié)構(gòu)（或試題的屬性）如下：章節(jié)：試題內(nèi)容所屬的篇章；試題編號(hào)：試題編號(hào)具有與每一道試題一一對(duì)應(yīng)的性質(zhì)，它不參與遺傳算法在智能組卷中的運(yùn)算，僅作為參與運(yùn)算的數(shù)據(jù)結(jié)構(gòu)的不變分量，用于指示運(yùn)算結(jié)果具體記錄；試題類型：可分為判斷題、選擇題、填空題、簡(jiǎn)答題、計(jì)算題、證明題、算法設(shè)計(jì)題、編寫(xiě)程序題、綜合題，參與運(yùn)算時(shí)可用編碼值代替，并且為了在生成試卷時(shí)能夠快速選取指定類型的試題和減少冗余度，在建庫(kù)時(shí)可為每種題型建立一個(gè)庫(kù)文件；試題難度：在試卷命題過(guò)程中，針對(duì)不同的考試對(duì)象，不同階段的考試，命題難度也不同，所以應(yīng)在數(shù)據(jù)庫(kù)中增加難度系數(shù)。用平均失分率來(lái)表示，取值范圍是0.0-1.0，值越大難度越大；試題的內(nèi)容：不參與組卷運(yùn)算的過(guò)程；已出題次數(shù)：為了使遺傳算法更好的應(yīng)用于組卷，應(yīng)加一字段來(lái)表明已經(jīng)出題次數(shù)，以此決定此題再出的概率，這一結(jié)夠?qū)Τ鲱}的影響是：結(jié)構(gòu)中的值越大，在出此題的概率越小，提高命題質(zhì)量；試題內(nèi)容相關(guān)性：在試卷命題過(guò)程中避免相同內(nèi)容的試題太多，從而無(wú)法對(duì)學(xué)生所學(xué)的知識(shí)進(jìn)行全面的考核，因此可用平均相關(guān)系數(shù)ρ和相關(guān)性分布η兩個(gè)指標(biāo)來(lái)考核。一份試卷的平均相關(guān)系數(shù)應(yīng)在3~7之間；考查點(diǎn)：為了適應(yīng)不同教材的需要，可按大綱要求將某門(mén)課的內(nèi)容分為不同的考查點(diǎn)，選題時(shí)以考查點(diǎn)為依據(jù)，統(tǒng)一試卷中不能有考查點(diǎn)重復(fù)的試題，它是和相關(guān)性密切相關(guān)的結(jié)構(gòu)；題分：試題的分?jǐn)?shù)；能力層次：可分為識(shí)記、理解、應(yīng)用、綜合等；估時(shí)：完成該題所需時(shí)間的估計(jì)值；試題答案：不參與組卷運(yùn)算的過(guò)程。經(jīng)過(guò)應(yīng)用，這種結(jié)構(gòu)能很好的配合遺傳算法實(shí)現(xiàn)智能組卷。2.2智能型組卷自動(dòng)生成系統(tǒng)中組卷的功能要求考試內(nèi)容由用戶決定，可以按篇章為單位決定，也可以按題類或考查點(diǎn)為單位決定；考試時(shí)間由用戶決定；整卷的難度系數(shù)由用戶根據(jù)學(xué)生的水平?jīng)Q定，一般取0.2~0.5；每份試卷滿分由用戶指定，其中主觀題、客觀題所占的分?jǐn)?shù)比例由用戶指定；試卷各篇章內(nèi)容所占分?jǐn)?shù)比例應(yīng)與教學(xué)時(shí)數(shù)成比例；各種題型的題目數(shù)由用戶確定，但要注意總分達(dá)到滿分的要求；全卷分?jǐn)?shù)按知識(shí)能力層次要求的分布由用戶指定，如：識(shí)記：20%，理解：30%，應(yīng)用：35%，綜合：15%；各題類內(nèi)容中，對(duì)層次必須滿足一個(gè)分?jǐn)?shù)比例表；全卷的區(qū)分度、期望值等由用戶指定。2.3智能型試卷自動(dòng)生成系統(tǒng)中組卷的數(shù)學(xué)模型組卷中決定一道試題，就決定它的上述12個(gè)屬性，也就是說(shuō)決定一個(gè)12維的向量（a1，a2，a3，，……a12）（ai相當(dāng)于2.1節(jié)的第i個(gè)屬性），決定一份試卷有n道試題，實(shí)際上就是決定一個(gè)n*12階矩陣；s=[這就是一個(gè)問(wèn)題求解中的目標(biāo)狀態(tài)矩陣，從2.2節(jié)中指出的組卷的功能要求可以看出，目標(biāo)狀態(tài)矩陣應(yīng)滿足如下相應(yīng)的約束條件：試卷總分由用戶給定，即試卷分?jǐn)?shù)的約束?？荚噧?nèi)容可以按篇章為單位決定，也可以按題類或考查點(diǎn)為單位決定，因此，在計(jì)算總分時(shí)可以先計(jì)算各篇章為單位決定考試內(nèi)容為例來(lái)計(jì)算總分，其他類推。Mk（第k篇章的題分）=k=1nckai，9，其中ck=考試時(shí)間=由用戶指定，即試卷總時(shí)間的約束；試卷難度=由用戶給定，即試卷難度約束；j為能力層次，即能力層次約束。j的取值可為：識(shí)記、理解、應(yīng)用、綜合等，具體總類和所占的分值由用戶給定。同理，教學(xué)要求、各種題型比例、區(qū)分度、期望值等等約束條件，和上面類似由用戶組卷時(shí)給定。但根據(jù)我們的經(jīng)驗(yàn)，指標(biāo)過(guò)多對(duì)組卷問(wèn)題增加難度降低效率，因此在組卷是可以根據(jù)用戶組卷要求給出相應(yīng)的約束條件?？梢钥闯觯M卷問(wèn)題的實(shí)際是求多約束條件的最優(yōu)解，而且滿足條件的最優(yōu)解不是唯一的。3改進(jìn)遺傳算法在智能型試卷自動(dòng)生成系統(tǒng)中的應(yīng)用3.1遺產(chǎn)算法的基本思想大自然的生物進(jìn)化中，一個(gè)生物群體要經(jīng)過(guò)交配、變異、自然選擇的過(guò)程，形成下一代群體，如此循環(huán)下去，不斷凈化，最后生存下來(lái)的總是最優(yōu)的。將這種思想運(yùn)用下去，就形成了遺傳算法，它的基本結(jié)構(gòu)可描述為：隨機(jī)初始化種群=p(0)={X1,X2,……,Xn|,gen=0;}計(jì)算p(0)中個(gè)體的適應(yīng)度值。while(不滿足終止準(zhǔn)則)do{根據(jù)個(gè)體的適應(yīng)度值及選擇策略從p(gen)中選擇生成下一代父體p(gen)；執(zhí)行雜交、變異和再來(lái)生產(chǎn)新的種群p(gen+1)；計(jì)算p(gen+1)中個(gè)體的適應(yīng)度值；gen=gen+1}經(jīng)典的遺傳算法存在搜索后期效率低和易形成未成熟收斂的情況。為此，人們嘗試了許多改進(jìn)方法，包括設(shè)計(jì)不同的選擇、交叉及變異算子，改變算法結(jié)構(gòu)，設(shè)計(jì)自適應(yīng)交叉和變異概率，將遺傳算法與其它優(yōu)化智能方法相結(jié)合等。根據(jù)遺傳算法，在采用遺傳算法尋優(yōu)時(shí)，通常按以下主要步驟進(jìn)行：基因編碼；初始群體生成；群體中個(gè)體適應(yīng)度值的計(jì)算；對(duì)群體中個(gè)體進(jìn)行遺傳操作（即選擇、交叉和變異）適應(yīng)度值的再次計(jì)算；如果滿足終止條件，迭代停止，輸出問(wèn)題的最優(yōu)解；否則，轉(zhuǎn)向步驟4上述遺傳算法的每一步都對(duì)優(yōu)化搜索的收斂速度和解的質(zhì)量有影響。3.2改進(jìn)型遺傳算法在智能型試卷自動(dòng)生成系統(tǒng)中應(yīng)用針對(duì)試題組卷的具體情況，我們對(duì)簡(jiǎn)單遺傳算法進(jìn)行改進(jìn)后應(yīng)用于智能型試卷自動(dòng)生成系統(tǒng)中，下面給出具體的解決方案：確定編碼方案用遺傳算法求解問(wèn)題，一般不是直接在問(wèn)題的解空間上，而是利用解的某種編碼表示的。在智能型試卷自動(dòng)生成系統(tǒng)中，由于在建庫(kù)時(shí)為每種題型建立了一個(gè)庫(kù)文件，故每種題型可各自獨(dú)立編碼。因此，編碼方案可采用分組實(shí)數(shù)編碼策略，就是根據(jù)各題型各自進(jìn)行實(shí)數(shù)編碼，然后對(duì)每一個(gè)題型再采用傳統(tǒng)二進(jìn)制編碼策略進(jìn)行處理，但題型組之間的編碼是獨(dú)立的，每一組編碼反映一種題型。這樣，可以克服以往采用二進(jìn)制編碼搜索空間過(guò)大和編碼長(zhǎng)度過(guò)長(zhǎng)的缺點(diǎn)。生成初始群體p(0)為了加快遺傳算法的收斂并減少迭代次數(shù)，試卷初始種群p(0)完全隨機(jī)的方法產(chǎn)生，而是根據(jù)題型（或各篇章內(nèi)容或各考查點(diǎn)）所占分?jǐn)?shù)比例、總分的要求。確定適應(yīng)度函數(shù)適應(yīng)度函數(shù)是用來(lái)評(píng)判試卷群體中個(gè)體的優(yōu)劣程度的指標(biāo)，遺傳算法利用適應(yīng)度值這一信息來(lái)指導(dǎo)搜索方向。我們采用以下形式的適應(yīng)度函數(shù)：F=1/（1+）i=1……n其中ei對(duì)應(yīng)為第i組卷因素對(duì)組卷約束的誤差，ki為權(quán)值系數(shù)，且ki>0。這種采用加權(quán)誤差適應(yīng)度函數(shù)可以較好的反映求解智能組卷問(wèn)題的特征，當(dāng)試卷個(gè)體對(duì)各項(xiàng)組卷約束條件的誤差越小時(shí)，它的適應(yīng)度值就越大，表示試卷個(gè)體越接近組卷目標(biāo)。智能型試卷自動(dòng)生成系統(tǒng)中對(duì)遺傳算子的改進(jìn)在簡(jiǎn)單的遺傳算法中，由于交叉后的子代個(gè)體取代進(jìn)行交叉的兩個(gè)父代個(gè)體，導(dǎo)致較快地丟棄了父代的信息，而交叉生成的新個(gè)體未必優(yōu)于父代個(gè)體，兩者均不利于算法的快速收斂。另外，由于在初始種群產(chǎn)生時(shí)題型（或篇章或考查點(diǎn)）?？偡侄紳M足要求，為了不破壞初始種群中已滿足的約束，所以此算法對(duì)交叉、變異及選擇步驟做如下的改進(jìn)：各種題型在各自的編碼組中獨(dú)立進(jìn)行交叉和變異操作，即交叉算子改進(jìn)為在相同題型組內(nèi)進(jìn)行單點(diǎn)交叉，變異算子也改進(jìn)為在同一題型組內(nèi)進(jìn)行單點(diǎn)變異。交叉后即評(píng)價(jià)新產(chǎn)生的兩個(gè)體的適應(yīng)度值，將其與父代兩個(gè)體比較，若適應(yīng)度值相同則視為無(wú)效交叉?zhèn)€體，被淘汰掉；若不同則保留，但不取代父代個(gè)體。有效交叉及變異后產(chǎn)生的新個(gè)體與未被取代的父代個(gè)體均參與評(píng)價(jià)和選擇，即從大于N小于2N個(gè)體中采用輪盤(pán)賭選擇法，同時(shí)考慮已經(jīng)出題次數(shù)（即an，6）這個(gè)約束條件，從中選出N個(gè)個(gè)體組成新的種群（N為種群規(guī)模）。智能型組卷自動(dòng)生成系統(tǒng)中遺傳算法的控制參數(shù)控制參數(shù)主要包括種群規(guī)模N，算法執(zhí)行的最大代數(shù)Maxgen，執(zhí)行不同的遺傳操作的概率（如：交叉概率Pc和變異概率Pm等）及一些輔助性的控制參數(shù)（如：用戶的組卷要求等）。遺傳算法在進(jìn)化過(guò)程中，一代代地往前進(jìn)化，由于選取最佳遺傳參數(shù)有一定的困難，參數(shù)的選取不一定十分合適，從而容易導(dǎo)致遺傳算法的局部收斂即早熟現(xiàn)象，一旦陷入早熟現(xiàn)象，進(jìn)化不能停止不前，而又無(wú)法判斷它是否是最優(yōu)解，從而陷入僵局。例如，種群規(guī)模N的值較大進(jìn)化較慢，但易搜索到全局最優(yōu)解，而N的值較小時(shí)進(jìn)化速度快，卻不易搜索到最優(yōu)解，權(quán)衡智能型試卷自動(dòng)生成系統(tǒng)的組卷效率和生成試卷的質(zhì)量，一般N取值為200左右。又如，在遺傳算法的運(yùn)用過(guò)程中，交叉概率Pc和變異概率Pm是較難選擇的兩個(gè)參數(shù)，一般來(lái)說(shuō)，交叉概率與變異概率選取越大，群體的多樣性較差。在智能型試卷自動(dòng)生成系統(tǒng)中，可采用在進(jìn)化過(guò)程中動(dòng)態(tài)定標(biāo)交叉概率和變異概率，當(dāng)群體中各個(gè)體較為集中時(shí)，增大交叉概率和變異概率。這種自適應(yīng)遺傳算法在保持試卷群體多樣性的同時(shí)，也保證了遺傳算法的收斂性并防止遺傳算法陷入局部最優(yōu)。終止條件出現(xiàn)種群滿足用戶的組卷約束要求或者是得到用戶的滿意試卷時(shí)；當(dāng)前種群中最大適應(yīng)度值與以前各代中最大適應(yīng)度值相差不大時(shí)，這時(shí)說(shuō)明進(jìn)化效果已經(jīng)不太顯著，再進(jìn)化下去沒(méi)有必要；達(dá)到指定的進(jìn)化代數(shù)；4實(shí)驗(yàn)結(jié)果及分析實(shí)驗(yàn)條件：將《數(shù)據(jù)結(jié)構(gòu)》中700道試題按要求分別建立5個(gè)庫(kù)文件，其中判斷、填空、算法設(shè)計(jì)題各100道，選擇、綜合題各200道。為了使試題的各種屬性分布合理，各可用隨機(jī)函數(shù)產(chǎn)生試題的各種屬性值。遺傳算法的控制參數(shù)為：種群規(guī)模N=200;最大代Maxgen=500;初始交叉概率Pc=0.6；變異概率Pm=0.1；智能型試卷自動(dòng)生成系統(tǒng)中約束條件：總分為100分；估計(jì)時(shí)間為120分鐘；題型分?jǐn)?shù)比例為：判斷、填空各占10%，選擇占20%，綜合題占40%，算法設(shè)計(jì)題占20%；能力層次為：識(shí)記：20%，理解：30%，應(yīng)用：35%，綜合：15%；難度為：容易：20%，中等30%，較難40%，