基于遺傳算法實現(xiàn)智能組卷的題庫設(shè)計

摘要:遺傳算法是目前最適合解決組卷問題的算法之一，開發(fā)組卷系統(tǒng)必須依靠數(shù)據(jù)庫平臺的支持，為了保持系統(tǒng)數(shù)據(jù)的整體性、完整性和共享性，該文提出了一種使得數(shù)據(jù)庫盡可能適應(yīng)算法需要的設(shè)計思想。

關(guān)鍵詞:智能組卷;遺傳算法;題庫

中圖分類號:TP18 文獻標識碼:A文章編號:1009-3044(2009)36-10559-03

Intelligent Test Paper Based on Genetic Algorithm Design of the Item Bank

HUANG Bao-ling

(1.Computer and Control Institute， Guilin University of Electronic Science and Technology， Guilin 541000， China; 2.Liuzhou Vocational Technical College， Liuzhou 545006， China)

Abstract: Genetic algorithms are currently the most suitable algorithm to solve the problem of test paper， Development Test Paper system must rely on database platform support， in order to maintain system data integrity， integrity， and sharing nature， this paper presents a database makes possible algorithm to adapt to the needs of design.

Key words: intelligent test paper; genetic algorithm; question bank

考試是教學活動中的重要環(huán)節(jié)，考試組卷是教師的一項重要工作。但是在教師組卷的過程中，存在著大量人力財力浪費的情況。近年來，隨著教育事業(yè)的飛速發(fā)展，人工組卷考試的做法己很難滿足現(xiàn)代教育教學的需要。因此，利用計算機及相關(guān)技術(shù)，通過建立結(jié)構(gòu)合理的試題庫，依據(jù)教師提出的要求，并按照一定的組卷策略進行自動組卷，可以克服人工出題的主觀因素(如不能保證出題的科學性)，節(jié)省資源，有利于教師把注意力集中到要實現(xiàn)的教學目標上來，真正關(guān)心學生的學習困難和錯誤所在，有利于提高教學水平和質(zhì)量，促進教育教學技術(shù)的改革。

智能組卷系統(tǒng)的開發(fā)涉及到應(yīng)用的具體算法和前臺界面及后臺數(shù)據(jù)庫的設(shè)計和實現(xiàn)，本文以Access為后臺數(shù)據(jù)庫設(shè)計工具，介紹了一種基于遺傳算法實現(xiàn)智能組卷的題庫設(shè)計思路。

1 組卷問題描述

由組卷系統(tǒng)所生成的試卷必須符合考試學的基本原理，符合課程教學大綱的要求，同時還必須符合教師對本次考試的具體要求。對于組卷系統(tǒng)來說，上述三方面的要求是對命題試卷的一種模糊的約束，本組卷系統(tǒng)按照人工組卷的經(jīng)驗，將組卷要求中最重要的約束指標歸納為題型、知識點、難度、區(qū)分度、分值、答題時間等六個基本指標。假如一張試卷由m道試題組成，每道題存在以上六個屬性，那么抽題組成的試卷就構(gòu)成了如圖1的一個m×6的矩陣。

其中m是試卷所包含的試題數(shù)，每一列對應(yīng)組卷約束條件中的一個約束變量。矩陣的列元素分別滿足用戶對試卷的相關(guān)要求。所有這些指標都應(yīng)與用戶指定的要求相等或者誤差最小。組卷要做的工作就是從這個矩陣空間構(gòu)成所需的解，使解滿足給定的約束條件，即滿足在矩陣每列上提出的要求，比如知識點覆蓋比例、難度約束等等。

2 智能組卷中遺傳算法的思想

遺傳算法GA(Genetic Algorithm)是模擬自然界生物進化機制的隨機化搜索算法，是一種有效解決最優(yōu)化問題的方法，由美國Michigan大學的J.HHolland于60年代提出，適用于處理傳統(tǒng)搜索方法難于解決的復雜的組合優(yōu)化問題。智能組卷問題本身是一個組合優(yōu)化問題，使用遺傳算法進行試題抽取操作，可以有效地優(yōu)化搜索過程，加快組卷速度。

生物的進化過程主要是通過染色體之間的交叉和染色體的變異來完成的。與此相對應(yīng)，遺傳算法中最優(yōu)解的搜索過程也模仿生物的這個進化過程，使用所謂的遺傳算子作用于群體P(t)中進行選擇、交叉和變異三種遺傳操作，從而得到新一代群體P(t+1)，具體算法的實現(xiàn)步驟有如下幾點。

2.1 編碼

編碼是從表現(xiàn)型到基因型的映射。根據(jù)所求解問題的特點，確定一種將問題的解表示成字符串的編碼方式。按照一定的編碼方法和編碼策略，科學、合理、準確地為每道試題進行編碼是高效組卷的首要工作，完整的試題編碼能大大提高組卷算法的效率和成功率。常見的遺傳算法編碼方式有二進制編碼、實數(shù)編碼、自然數(shù)編碼等編碼方式。其中，二進制編碼應(yīng)用最早、最廣，當表示對象數(shù)據(jù)多時，它存在轉(zhuǎn)換復雜、編碼長度大、占用計算機內(nèi)存多等問題。所以在確定編碼方案時，筆者采用了整數(shù)(即題號)編碼策略。

2.2 初始化

在算法執(zhí)行的過程中，首次根據(jù)組卷要求從試題庫中選出試題組成試卷染色體的過程被稱為染色體初始化。這里的一個染色體就是由一張試卷的各試題組成，染色體初始種群往往是采用隨機的方法產(chǎn)生。

2.3 評估染色體

任何一個染色體個體誕生后，我們都要看其對環(huán)境的適應(yīng)度是否已經(jīng)達到擬定的目標值，或者判斷二者之間的差距是否已經(jīng)達到最小，這個過程被稱為評估。對于組卷問題而言，我們要選用合適的適應(yīng)度函數(shù)來判斷某試卷染色體是否已經(jīng)滿足用戶的需求，如總分值是否達到要求，難易度是否合適，知識點覆蓋率如何等。適應(yīng)度函數(shù)將綜合上述6個試題屬性值來衡量，如果某一染色體的適應(yīng)度函數(shù)值越大，就表示該染色體所代表的試卷越接近組卷目標。

2.4 選擇

選擇也可稱之為“復制”，其目的是為了從當前群體中選出優(yōu)良的個體，使它們有機會作為父代為下一代繁殖子孫。根據(jù)各個個體的適應(yīng)度值，按照一定的規(guī)則或方法從上一代群體中選擇出一些優(yōu)良的個體遺傳到下一代群體中。

2.5 交叉

交叉操作是遺傳算法中最主要的遺傳操作。通過交叉操作可以得到新一代個體，新個體組合了父輩個體的特性。將群體內(nèi)的各個個體隨機搭配成對，對每一個個體，以某個概率(稱為交叉概率，Crossover Rate)交換它們之間的部分染色體。交叉體現(xiàn)了信息交換的思想。

2.6 變異

變異操作是以一定的概率隨機選擇一個個體，對于選中的個體改變其基因值，在組卷問題中就是刪除掉該試題，以另一試題替代。同生物界一樣，遺傳算法中變異發(fā)生的概率很低。變異為新個體的產(chǎn)生提供了機會。

綜上所述，遺傳算法運算流程即是首先初始化染色體群體，其次，在不滿足迭代結(jié)束條件的前提下對染色體進行評估、選擇、交叉以及變異，進而生成新的優(yōu)良的染色體群體。

3 數(shù)據(jù)庫設(shè)計思路

基于上述遺傳算法的思想，為了完現(xiàn)組卷過程中各染色體的適應(yīng)性評估，必須在設(shè)計題庫時將試題的各屬性進行量化。因此，題庫建設(shè)也是一項艱巨的系統(tǒng)工程，要解決好幾個問題:1) 題庫的結(jié)構(gòu)設(shè)計問題，包括題目的各屬性值及度量標準的設(shè)置等。2) 試題的收集與編制。為了使題庫更加科學化、標準化，題庫必須具有大量的、高質(zhì)量的試題，而題目的來源主要有兩個方面:一是收集正在大量使用的優(yōu)秀試題，二是組織專家專門命題。3) 確定各個試題的屬性值。這一步是題庫開發(fā)中極為重要的一步，因為以后試卷的生成主要依靠題目的這些屬性值來確定選擇哪些題目加入到試卷中。生成的試卷的質(zhì)量在很大程度上取決于題庫中各個試題指標的可靠性。其中問題1)、3) 要在數(shù)據(jù)庫設(shè)計中由開發(fā)者解決。

據(jù)前所述，要基于遺傳算法實現(xiàn)自動組卷，第一步就是對染色體進行編碼。在編碼時，由于一個試題充當生物學當中染色體中一個基因的角色，致使試題庫中試題記錄越多，在自動組卷時其時間復雜度就越高，試題庫中的屬性越多，組卷的難度越高，以致效率就越低?；谶@一考慮，在設(shè)計數(shù)據(jù)庫時，要一方面盡可能減少試題庫中對應(yīng)的試題記錄的數(shù)量，另一方面，在滿足科學組卷需要的前提下，以教育學理論為指導，合理地控制試題屬性的數(shù)量。具體思路有如下幾點。

3.1 主要約束指標的數(shù)據(jù)實現(xiàn)

根據(jù)遺傳算法的特點，本組卷系統(tǒng)設(shè)置了六個組卷約束指標，要在組卷時由用戶提出，其中題型指標采用分表保存的辦法，其余五個約束指標要分別進行數(shù)據(jù)量化，并建立數(shù)據(jù)表進行管理，同時要與試題表建立參照關(guān)系。難度屬性分為四個檔次:容易、中等、較難、難;區(qū)分度屬性分為三個檔次:低、中、高;知識點屬性規(guī)定分為8個點，由具有豐富經(jīng)驗的任課教師來劃分;分值屬性分六個檔次:1分(單選題)、2分(填空題或判斷題)、3分(多選題)、5分(改錯題)、10分(綜合題)、15(綜合題)，其中綜合題允許有兩個檔次分值。

3.2 試題表的屬性結(jié)構(gòu)

題型一般有單選題、多選題、填空題、判斷題、綜合題等。如果所有試題放在一個數(shù)據(jù)表中，在搜索時必然帶來很大的困難，增加算法的復雜度，同時還需要增加“試題類型”屬性。所以在確定編碼方案時，筆者采用了分段的整數(shù)編碼策略。每一段編碼反映一種題型，各個題型各自進行整數(shù)編碼，題型組之間的編碼是獨立的，也分別運用遺傳算法求出最優(yōu)解。分開處理有利于減少屬性，進而提高算法的執(zhí)行效率。

盡管采用的是各種題型在試題庫中分別保存的方式，其實各表的結(jié)構(gòu)是完全相同的，如表1是試題的屬性表。

其中:

ID屬性為主碼屬性，兼有題號的功能，由系統(tǒng)自動生成，最大值表示本題型的題目數(shù)，且隨題目的錄入自動增加。

QuestionTypes為試題類型，用于與試題類型總表建立關(guān)聯(lián)。

Subject為試題的問題描述。

Knowledge表示試題內(nèi)容所屬的知識點，建庫之前要由課任教師根據(jù)教學大綱將課程內(nèi)容劃分為幾個知識點，在課程知識分布表中明確，便于出題教師選擇。本題庫規(guī)定課程有八個知識點。

Difficult為難度系數(shù)屬性，難度系數(shù)反映試題的難易程序的指標。在試題庫建設(shè)的初期，由出題教師根據(jù)經(jīng)驗設(shè)置，以后可以根據(jù)實際測試情況逐步修正。本題庫試題的難度系數(shù)分為4個級別。在具體的實現(xiàn)界面中，用戶只需要在“簡單”、“一般”，“較難”，“難”中選擇，系統(tǒng)會自動取其所對應(yīng)的具體數(shù)據(jù)。

Distinction為區(qū)分度:根據(jù)測量學理論，對于一道試題，如果Q>=0.3認為區(qū)分度比較好，Q值太小時，表明該題太易或太難，此時這道題已無法區(qū)分考生的水平。嚴格來說，區(qū)分度應(yīng)該通過測試后才得到，但對每題進行實測存在技術(shù)困難，而且實測的信度難以保證，因此，類似難度指標，我們采用預(yù)先給定經(jīng)驗值，在實際的環(huán)境中可進一步精確。本題庫的區(qū)分度分三個檔次。

Score為建議分值，表示本試題在一份標準試卷上所占的分數(shù)值。這里所說的標準試卷應(yīng)符合下述三條要求:1) 考試時間為120分鐘;2) 試卷的滿分值為100分;3) 用于學期結(jié)束評定學生成績的考試(總結(jié)性考試)。根據(jù)常用的五種題型，本組卷系統(tǒng)在用戶輸入試題界面規(guī)定可采用的相應(yīng)分值。

Time為學生解答該題所需的時間(分鐘)的預(yù)估值，包括了下面三個時間之和:讀題、審題所需的時間，進行解答書寫的時間，可能的檢查時間等。

3.3 數(shù)據(jù)庫關(guān)系設(shè)計

將組卷系統(tǒng)涉及到的所有參數(shù)進行說明和量化后，可以用數(shù)據(jù)表表示和存放，通過Access建立表間關(guān)聯(lián)關(guān)系。關(guān)系設(shè)計主要的功能是保持數(shù)據(jù)的完整性、一致性，減少數(shù)據(jù)冗余，提高應(yīng)用程序的性能，有效地對數(shù)據(jù)庫中的數(shù)據(jù)進行增加、刪除、更新等管理，使數(shù)據(jù)庫中數(shù)據(jù)與現(xiàn)實世界中的應(yīng)用需求保持一致。如圖2是一種題型與各約束指標數(shù)據(jù)表建立的關(guān)系。

由于試題已經(jīng)過分類處理，所以在組卷時，必然要根據(jù)試題類型分步實現(xiàn)試卷的生成。將各題型的最優(yōu)解(即各題型試題)組合起來形成一份完整的試卷。

4 結(jié)束語

根據(jù)分析，該思路設(shè)計下的數(shù)據(jù)庫與不經(jīng)過任何處理的試題數(shù)據(jù)庫相比，在用遺傳算法實現(xiàn)自動組卷時效率可以提高大約一倍，達到了數(shù)據(jù)存儲與算法有效結(jié)合的設(shè)計目的。

參考文獻:

[1] 肖洋，王強，劉鳳新.在線考試組卷算法研究[J].北京:北京化工大學學報，2006(4).

[2] 雷英杰等.MATLAB遺傳算法工具箱及應(yīng)用[M].西安:西安電子科技大學出版社，2005:11-31.

[3] 王珊，薩師煊.數(shù)據(jù)庫系統(tǒng)概論[M].北京:高等教育出版社，2006:84-113.

[4] Hoffer J A.現(xiàn)代數(shù)據(jù)管理[M].袁方，譯.北京:電子工業(yè)出版社，2006:67-102.

[5] 周學泳，石丹.短信息與WAP的開發(fā)及應(yīng)用[M].北京:電子工業(yè)出版社，2002:61-92.