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

周嘉懿

（遼寧鐵道職業技術學院,遼寧 錦州 121000）

一、智能考試題庫系統模型設計

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

（一）智能考試題庫系統需求

智能考試題庫系統旨在通過不斷學習構建一個高效、穩定、科學且功能強大的系統。系統可以準確地記錄試題在考試中已經出現過的頻次和時間,然后根據題目的解答情況進行分析,運用適當的算法調整試題的難度,再根據考試的要求以及教師對試卷的要求,按照生成試卷算法自動生成適合的試卷。

（二）智能考試題庫系統功能模塊

系統需要建立以下基本模塊:

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

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

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

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

（5）成績管理:成績查詢、統計和導出等。

二、智能考試題庫系統模型

（一）試題庫結構設計

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

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

（二）組卷問題的數學建模

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

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

表1 以章節為單位的樹型結構知識點管理

（三）組卷中自適應度函數的設計

適應度函數的設計直接影響到遺傳算法的收斂速度以及能否找到最優解。在函數優化中,適應度函數可由目標函數變換后得到。本系統所采用的適應度函數與問題的目標函數一致,即把目標函數轉換為適應度函數,采用如下的映射關系:

其中Fit（f（x））,表示適應度函數;f（x）為目標函數。

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

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

三、遺傳算法概述

1.遺傳算法的基本概念

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

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

（1）編碼設計

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

表2 試卷的染色體表

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

（2）初始化題庫

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

（3）錦標賽選擇算法

根據表1得知第1章共有3節9個知識點。子種群規模作為算法的一個參數,可以在一定范圍內改變。圖中種群規模為9,子種群規模為3的錦標賽樹。

圖1 錦標賽樹

（4）單點交叉

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

（5）變異

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

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

附表1 分段單點交叉前

附表2 分段單點交叉后

附表3 變異前

附表4 變異后

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

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

[3]王小平,曹立明.遺傳算法——理論應用與軟件實現[M].西安:西安交通大學出版社,2002.

[4]張琨,楊會菊,宋繼紅.基于遺傳算法的自動組卷系統的設計與實現[J].計算機工程與科學,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.