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

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

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

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

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

1 遺傳算法

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

1.1 初始化

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

1.2 迭代的執行下面操作

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

1.3 輸出適應度值最優的染色體作為最優解

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

2 自動組卷算法的實現

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

2.1 編碼

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

2.2 生成初始群體

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

2.3 計算初始群體適應度

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

2.4 選擇

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

2.5 交叉遺傳

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

2.6 變異

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

2.7 算法終止條件

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

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

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

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

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

參考文獻

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

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

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

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

作者簡介

曹鑫（1981-），女，現為石家莊信息工程職業學院講師，研究方向為信息系統開發。

韓莉（1977-），女，現為石家莊信息工程職業學院講師，研究方向為數據庫應用于開發。

韓紅彩（1980-），女，現為石家莊信息工程職業學院講師，研究方向為數據庫應用于。

張亞娜（1979-），女，現為石家莊信息工程職業學院講師，研究方向為信息系統開發。

作者單位

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