基于錦標賽選擇算法的智能考試題庫系統(tǒng)研究

周嘉懿

（遼寧鐵道職業(yè)技術(shù)學(xué)院,遼寧 錦州 121000）

一、智能考試題庫系統(tǒng)模型設(shè)計

本文旨在采用一種多目標優(yōu)化模型對生成試卷問題進行數(shù)學(xué)建模,對知識點、難度和區(qū)分度等約束條件進行分析處理,并在已有的遺傳算法的基礎(chǔ)上,改變傳統(tǒng)的輪盤賭的選擇操作,使用新的基于錦標賽選擇算法,從而加快抽取試題生成試卷的效率,增加試卷的合理性。

（一）智能考試題庫系統(tǒng)需求

智能考試題庫系統(tǒng)旨在通過不斷學(xué)習(xí)構(gòu)建一個高效、穩(wěn)定、科學(xué)且功能強大的系統(tǒng)。系統(tǒng)可以準確地記錄試題在考試中已經(jīng)出現(xiàn)過的頻次和時間,然后根據(jù)題目的解答情況進行分析,運用適當(dāng)?shù)乃惴ㄕ{(diào)整試題的難度,再根據(jù)考試的要求以及教師對試卷的要求,按照生成試卷算法自動生成適合的試卷。

（二）智能考試題庫系統(tǒng)功能模塊

系統(tǒng)需要建立以下基本模塊:

（1）用戶信息管理:用戶查詢、注冊、權(quán)限和角色等;

（2）學(xué)科知識點管理:學(xué)科添刪改、知識點添刪改、學(xué)科查詢和知識點查詢;

（3）題庫管理:題庫查詢、試題添刪改等;

（4）組卷管理:管理試卷、生成試卷等;

（5）成績管理:成績查詢、統(tǒng)計和導(dǎo)出等。

二、智能考試題庫系統(tǒng)模型

（一）試題庫結(jié)構(gòu)設(shè)計

試題庫的結(jié)構(gòu)并不僅僅體現(xiàn)在試題本身所涵蓋的知識點,而是要綜合試卷生成的主要原則,這樣才能保證選題的準備性和合理性。

為滿足系統(tǒng)需求,題庫設(shè)計結(jié)構(gòu)主要包括試題編號、試題內(nèi)容、題型、難度系數(shù)、試題答案等。其中難度系數(shù)是指試題的難易程度,包括簡單、基本、中等、稍難和難題五個等級,分別用1～5來表示。試題類型按表1所示的五種題型,分別用1～5來表示。知識點考核層次分為四級:了解、理解、掌握和熟練掌握,其權(quán)重對應(yīng)定義用1～4來表示。

（二）組卷問題的數(shù)學(xué)建模

由于生成一份試卷是多重約束組合優(yōu)化問題,在實際組卷過程中,用戶對試卷提出多方面的要求,每一個要求對應(yīng)試卷中的一個約束條件。若要從大量的試題庫中抽取出最優(yōu)的試題,生成一份高質(zhì)量的試卷,根據(jù)朱婧等在論文《自適應(yīng)遺傳算法在工程訓(xùn)練在線考試中的應(yīng)用》一文中提到的數(shù)學(xué)模型的基礎(chǔ)之上,需要滿足的約束條件除了包括試卷總分約束分布、題型分布約束條件、章節(jié)分數(shù)分布約束、難度分數(shù)分布約束和區(qū)分度分數(shù)分布約束等之外,本文重點提出了第6個約束條件:知識點分布約束,需要滿足的函數(shù):

Wt為第t個章節(jié)要求的知識點（1≤t≤5）。通常,知識點分布應(yīng)以章節(jié)為單位,保證在抽題的過程中對該章節(jié)的知識點選取可以實現(xiàn)均勻分布。因此,如果知識點定義密度過小,則無法區(qū)別相似的知識點,也無法確定題目的歸屬范圍,則會出現(xiàn)同一知識點選題過多的問題;如果知識點定義密度過大,則相似的知識點會被認為是完全不同的,在隨機選取中也有可能導(dǎo)致題目相似度過高。故在知識點的管理上,采用樹型結(jié)構(gòu)可以解決知識點的密度問題,在智能考試系統(tǒng)的組卷中可以真正實現(xiàn)知識的均勻分布。如表1所示:

表1 以章節(jié)為單位的樹型結(jié)構(gòu)知識點管理

（三）組卷中自適應(yīng)度函數(shù)的設(shè)計

適應(yīng)度函數(shù)的設(shè)計直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解。在函數(shù)優(yōu)化中,適應(yīng)度函數(shù)可由目標函數(shù)變換后得到。本系統(tǒng)所采用的適應(yīng)度函數(shù)與問題的目標函數(shù)一致,即把目標函數(shù)轉(zhuǎn)換為適應(yīng)度函數(shù),采用如下的映射關(guān)系:

其中Fit（f（x））,表示適應(yīng)度函數(shù);f（x）為目標函數(shù)。

根據(jù)約束條件重要性的不同,將每一個知識點設(shè)定一個權(quán)重,再把所有的目標分量與設(shè)定的權(quán)重相乘后相加,得到了組卷問題的目標函數(shù):

其中:Wi為第i個約束的權(quán)重;ei為第i約束因素對組卷目標的誤差,且目標函數(shù)越小越好。由表1可統(tǒng)計出的知識點權(quán)重總量M=[2,2,2,3]。

三、遺傳算法概述

1.遺傳算法的基本概念

遺傳算法（Genetic Algorithm,GA）是基于自然選擇的生物進化模型,一種模仿生物進化過程的隨機方法。現(xiàn)如今,GA已經(jīng)比較成熟且成功地應(yīng)用于很多搜索優(yōu)化領(lǐng)域。過程基本描述為:首先設(shè)計編碼,產(chǎn)生個體初始種群;然后計算出合理的適應(yīng)度函數(shù),目的是評定個體的優(yōu)劣程度,從而決定基因可被遺傳的概率;最后重復(fù)一系列運算,包括選擇、交叉和變異,直到每個種群中的個體適應(yīng)度滿足指定的適應(yīng)度值,完成模擬生物進化的過程,類似于“適者生存”。

2.改進的遺傳算法的運算過程

（1）編碼設(shè)計

本系統(tǒng)采用整數(shù)編碼方式,也就是說一個染色體代表一套試卷,而染色體則由不同基因組合而成。從表2所示試卷的試題量得知,選擇題的編碼范圍是00～99,每道選擇題編號用2位十進制值表示;填空題的編碼范圍是00～79,每道填空題編號用2位十進制值表示;簡答題的編碼范圍是00～49,每道簡答題編號用2位十進制值表示,計算題的編碼范圍為 00～49,每道計算題編號用2位十進制值表示,則染色體的總長度為:2×5+2×5+2×5+2×4=38位。組卷時,將選中的試題號作為染色體的一個基因,其中基因的個數(shù)就是試卷中試題的個數(shù),試卷的染色體表如表2所示。

表2 試卷的染色體表

采用整數(shù)編碼機制,大大減少了染色體的長度,同時取消了編碼、解碼的過程,縮短了求解的時間。

（2）初始化題庫

在選擇初始化群體時,要根據(jù)用戶提出的約束條件,把試題庫分成幾個子試題庫,在子試題庫中選擇初始群體。為產(chǎn)生初始題庫而設(shè)計的函數(shù)為initexam（）。產(chǎn)生染色體編碼后,再對個體進行解碼和每個個體的適應(yīng)度fitfunc（）計算。

（3）錦標賽選擇算法

根據(jù)表1得知第1章共有3節(jié)9個知識點。子種群規(guī)模作為算法的一個參數(shù),可以在一定范圍內(nèi)改變。圖中種群規(guī)模為9,子種群規(guī)模為3的錦標賽樹。

圖1 錦標賽樹

（4）單點交叉

交叉運算是遺傳算法中生成新個體過程中重要的操作過程,用以交換某兩個體之間的部分染色體。本文采用了單點交叉方法,其操作過程是:首先對群體進行隨機配對,然后設(shè)置一個交叉點所在的位置,最后再相互交換配對染色體之間的部分基因。在交叉點前面的基因稱為父代基因,子代在交叉前面的基因從一個父代基因那里得到,后面的部分從另外一個父代基因那里得到。見附表1、2。

（5）變異

變異是指依據(jù)變異概率（pm）將個體編碼串中的某些基因值用其他基因值來替換,從而形成一個新的個體。遺傳算法中的變異運算是產(chǎn)生新個體的輔助方法,它決定了遺傳算法的局部搜索能力,同時保持種群的多樣性。本文采用了整數(shù)編碼方式,變異就是變量的替換,指在編碼串中隨機替換一位基因作為新的個體。具體的操作步驟是:首先隨機產(chǎn)生基因變異位置,然后依據(jù)某一概率將變異點的原有基因變量的值改變。如下有19位變量的個體,在第12位時發(fā)生了變異。見表3、4。

從附表3、4可以看出,簡答題中的22發(fā)生了變異,而簡答題共有50道,即試題題號為01～50,所以隨機產(chǎn)生33,通過檢查其他試題題號沒有重復(fù)題目,將33代替22,實現(xiàn)了變異操作。

附表1 分段單點交叉前

附表2 分段單點交叉后

附表3 變異前

附表4 變異后

[1]朱婧,戴青云,王美林等.自適應(yīng)遺傳算法在工程訓(xùn)練在線考試中的應(yīng)用[J].計算機工程與應(yīng)用,2013,49（14）:222-246.

[2]楊巍巍,宋海峰,高巍巍等.基于遺傳算法的自動組卷技術(shù)[J].黑龍江工程學(xué)院學(xué)報（自然科學(xué)版）,2013,27（2）:72-74.

[3]王小平,曹立明.遺傳算法——理論應(yīng)用與軟件實現(xiàn)[M].西安:西安交通大學(xué)出版社,2002.

[4]張琨,楊會菊,宋繼紅.基于遺傳算法的自動組卷系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機工程與科學(xué),2012,34（5）:178-183.

[5]Linhart J M.Algorithm 885:computing the logarithm of thenrmal distribution[J].ACM Transactions on Mathematical Software,2009,25（3）:102-109.