淺議在線考試系統(tǒng)中基于遺傳算法的自動組卷算法的設計

曹鑫+韓莉+韓紅彩+張亞娜

遺傳算法在考試系統(tǒng)的自動組卷方面具有其他傳統(tǒng)組卷算法所不能比擬的優(yōu)點，通過交叉、變異等操作來產生新的個體，擴大了搜索范圍，使得優(yōu)化的結果是全局最優(yōu)解而不是局部的最優(yōu)解，適合于大規(guī)模、復雜問題的求解，其計算簡單但功能強大。

【關鍵詞】組卷；遺傳算法；操作

在線考試系統(tǒng)的設計與開發(fā)中，組卷是實現(xiàn)考試系統(tǒng)自動化的核心問題之一。組卷是指由用戶先輸入對試卷試題的要求，然后系統(tǒng)自動地從試題庫中選出符合用戶要求的試題，組成一份試卷的過程。

1 遺傳算法

遺傳算法是將孟德爾的遺傳變異理論與達爾文的“優(yōu)勝劣汰，適者生存”自然進化學說進行模擬，實現(xiàn)的一種迭代式的搜索算法。遺傳算法的步驟如下：

1.1 初始化

先產生足夠數(shù)量的個體，然后將這些個體組成一個種群。

1.2 迭代的執(zhí)行下面操作

在種群中，將每個個體的適應度值計算出來，根據某個規(guī)則，選出一個能進入到下一代的個體，產生一個新的種群。在這個新的種群中，按照交叉概率Pc進行交叉操作，按照變異概率Pm進行變異操作；如果不能滿足任何一個停止條件，那么就轉到第（1）步操作。

1.3 輸出適應度值最優(yōu)的染色體作為最優(yōu)解

把問題的解用“染色體”來表示，把這染色體放到某個具體 “環(huán)境”中，根據適應度函數(shù)值選出適應度較高的“染色體”，并復制這些染色體，按照這個過程，將進化工作一代一代的進行下去，必將產生一個最適應環(huán)境的 “染色體”，從而獲得問題的最優(yōu)解。

2 自動組卷算法的實現(xiàn)

根據前面所介紹的有關遺傳算法的相應知識，下面就對自動組卷的算法進行設計：

2.1 編碼

遺傳算法進行優(yōu)化問題是通過編碼來實現(xiàn)的，因此編碼和解碼是遺傳算法的一個主題。首先是編碼算法的確定。由于標準化試卷每種題型所占的分數(shù)、試題的個數(shù)和每題分數(shù)的乘積是相同的，所以采用獨立的編碼策略。具體來講就是編碼的依據要結合題目的類型，在每種題型的內部應用常規(guī)編碼策略，也就是0-1編碼。這種方式的編碼使組與組之間的編碼是相互獨立，每一組的編碼都反映一種題型，試題庫中該題型的題目數(shù)量決定每一組編碼的長度，一份試卷的編碼長度就是總的編碼長度，這是由試題庫中所含的試題總數(shù)決定。

2.2 生成初始群體

在初始群體產生的時候，首先將各個個體的所有位上均設置為“0”，然后參照每種題型題數(shù)的限制，隨機產生與試題數(shù)目相同的“1”位，這樣可以保證初始群體各個個體都滿足試卷的標準格式和滿分都為100分的特點。另外，這也解決了因試題數(shù)目過多而造成編碼長度過長的問題。種群規(guī)模n較大則進化較慢，但是對全局最優(yōu)解的搜索會較為容易，而n較小時，則進化速度快，但對全局的最優(yōu)解的搜索灰較為復雜。

2.3 計算初始群體適應度

由于采用獨立編碼方式，所以在初始種群產生時，題型、題數(shù)和題分都是滿足要求的，因此在組卷過程的實際操作中，只需要考慮知識點的難度系數(shù)、范圍、試題區(qū)分度和教學要求等因素即可。在此可將知識單元的權值取1.0，試題區(qū)分度的權值取1.0，教學要求的權值取0.9，難度系數(shù)的權值取1.1。以上這些權值是在模擬組卷過程中使用的，而實際權值的確定應該根據考試的要求或目標進行設定。

2.4 選擇

首先根據適應度對群體中所有的個體進行由小到大的排序，然后將排在最前面的一半染色體選取出，在對這些選取出的染色體進行下面的操作。

2.5 交叉遺傳

交叉遺傳是針對編碼進行的，此方法必須得保證試卷編碼中的各段1的位數(shù)恒定不變，否則將會引起試卷中每個題型的題數(shù)發(fā)生變化，導致生成的試卷不符合標準化試卷的要求。因此在組卷過程中，采用單親遺傳法，這種方法可以避免兩條染色體在進行交叉時，所引起的試卷中不同類型的題數(shù)發(fā)生變化的情況。交叉操作是各段分別通過隨機數(shù)隨機產生交叉位，它是一種以染色體中點為軸心進行的對稱交叉。

2.6 變異

為了使各題型組內題目數(shù)量不會受變異操作而發(fā)生改變，可以采用一種一次變異操作，使組內可同時變異兩位的方法，即一位0到1（1到0），而在該位所在的組內，應采用先向前、再向后的搜索方式，將與該位最近的1變?yōu)?（0到1）。

2.7 算法終止條件

遺傳算法中的優(yōu)化準則，是一種依據問題的不同而有所不同的確定方式，可以采用如下準則之一來作為判斷的條件：種群中個體的平均適應度基本上達到了用戶預先設定的值；用戶輸入的值要大于種群中個體的最大適應度；世代數(shù)超過預先設定的值。這里的終止條件是：設置遺傳最大代數(shù)為200，那么進化到200后就會終止進化過程。

為了防止組出相同的試卷，還需要對試題庫進行一定的修改，即修改從試題庫中抽取的試題的使用次數(shù)和最近使用的時間，以便保證在連續(xù)生成的幾份試卷中或在某一段時間內不會重復出現(xiàn)同一試題。

3 基于遺傳算法的組卷流程

在實現(xiàn)自動選題時，可以采用父輩挑選與生存選擇兩種選題的方式。父輩挑選的方式是將每次選出的隨機抽樣不再返回，這種方式使得試題庫中的每道題目都有可能被選中；生存選擇的方式是指父輩與子代之間進行競爭，能進入到下一輪競爭環(huán)境的是二者中的優(yōu)良者，這是一種擇優(yōu)選擇。這兩種方法共同作用于試題的選擇，可以保證順利完成選題。在選題的過程中，題目的選擇是隨機的，而且哪一道題目被選中是一個非均勻的隨機事件，題目被選中的概率要依賴于上一次選題的過程。

遺傳算法在考試系統(tǒng)的自動組卷方面具有其他傳統(tǒng)組卷算法所不能比擬的優(yōu)點，通過交叉、變異等操作來產生新的個體，擴大了搜索范圍，使得優(yōu)化的結果是全局最優(yōu)解而不是局部的最優(yōu)解，適合于大規(guī)模、復雜問題的求解，其計算簡單但功能強大。

參考文獻

[1]劉彬，金濤，陳太平.遺傳算法在試題組卷中的應用[J].燕山大學學報，2002，26（03）：193-195.

[2]王娜.多目標組卷模型及其算法研究[J].沈陽師范大學學報（自然科學版），2006，24（02）：189-191.

[3]管寶云，尹琦.基于混合智能算法的自動組卷問題研究[J].天津工業(yè)大學學報，2006（04）：97-100.

[4]曾一，一冉忠，郭永林.試題庫中自動組卷的算法及試卷測評策略[J].計算機工程與設計，2006，27（06）：3024-3027.

作者簡介

曹鑫（1981-），女，現(xiàn)為石家莊信息工程職業(yè)學院講師，研究方向為信息系統(tǒng)開發(fā)。

韓莉（1977-），女，現(xiàn)為石家莊信息工程職業(yè)學院講師，研究方向為數(shù)據庫應用于開發(fā)。

韓紅彩（1980-），女，現(xiàn)為石家莊信息工程職業(yè)學院講師，研究方向為數(shù)據庫應用于。

張亞娜（1979-），女，現(xiàn)為石家莊信息工程職業(yè)學院講師，研究方向為信息系統(tǒng)開發(fā)。

作者單位

石家莊信息工程職業(yè)學院 河北省石家莊市 050035